今天肝作业，时间紧迫，只能随便做几道题了。

397. 整数替换

今天的每日一题。

给定一个正整数 n ，你可以做如下操作：

  1. 如果 n 是偶数，则用 n / 2 替换 n 。
  2. 如果 n 是奇数，则可以用 n + 1 或 n - 1 替换 n 。

n 变为 1 所需的最小替换次数是多少？

示例 1：

输入：n = 8
输出：3
解释：8 -> 4 -> 2 -> 1

示例 2：

输入：n = 7
输出：4
解释：7 -> 8 -> 4 -> 2 -> 1
或 7 -> 6 -> 3 -> 2 -> 1

示例 3：

输入：n = 4
输出：2

我的想法是取 2 的对数。然后比较差值。但是试了一下不行。然后想到可以针对 mod 2 不为 0 进行优化，凑到能除以 2 的数字。

class Solution {
public:
  int integerReplacement(int n) {
    int cnt = 0;
    while (n != 1) {
      cnt++;
      if (n % 2) {
        if (n - 1 % 2 == 0) {
          n--;
        }else{
          n++;
        }
        continue;
      }
      n /= 2;
      cout << n << endl;
    }
    return cnt;
  }
};

结果发现有如下问题：

47
48
24
12
6
3
4
2
1
    
9

3 之后变成了 4. 最后想到就是暴力法：

class Solution {
public:
  int integerReplacement(size_t n, int cnt = 0) {
    if (n == 1) {
      return cnt;
    }
    cnt++;
    if (n % 2 == 0) {
      n = n / 2;
      return integerReplacement(n, cnt);
    }
    return min(integerReplacement(n + 1, cnt), integerReplacement(n - 1, cnt));
  }
};

缺点：可能会有大量重复计算。

想着加 memo，但是似乎很浪费空间。

2. 两数相加

就普通进位加法。内存管理一团糟。

class Solution {
public:
  ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    int carry = 0; // 进位标识
    auto ret = new ListNode (); // 可以改成 auto ret = l2; 提高利用率但是破坏原来的数据。
    auto head = ret;
    while (l1 || l2) {
      if (l1 == nullptr) {
        l1 = new ListNode(0);
      }
      if (l2 == nullptr) {
        l2 = new ListNode(0);
      }
      ret->val = l1->val + l2->val + carry;
      carry = 0;
      if (ret->val >= 10) {
        ret->val -= 10;
        carry = 1;
      }
      l1 = l1->next;
      l2 = l2->next;
      if (l1 || l2) {
        ret->next = new ListNode();
        ret = ret->next;
      }
    }
    if(carry){
        ret->next = new ListNode(carry);
    }
    return head;
  }
};

106. 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

    3
   / \
  9   20
 /\  /  \
1 2 15   7

i = [1,9,2,3,15,20,7]
p = [1,2,9,15,7,20,3]

首先 p.last=3 是根 =>

i = [1,9,2,<--3-->,15,20,7]
p = [1,2,9,15,7,20,<--3]

3

i = [1,9,2,<--3-->,15,20,7]
p = [1,2,9,15,7,20,<--3]

3

然后针对 i = [1,9,2] 和 p = [1,2,9]，p.last = 9 是根。

可以发现已经找到规律了。

  1. 在 p 的末尾找到根元素
  2. 在 i 的中间找到根元素。利用唯一性可以遍历搜索。
  3. 然后用 i 的左边构造左子树
  4. 然后用 i 的右边构造右子树
class Solution {
private:
  int sliceIndexOf(vector<int> &haystack, int ifrom, int ito, int needle) {
    for (int i = ifrom; i <= ito; i++) {
      if (haystack[i] == needle) {
        return i;
      }
    }
    return -1;
  }
  TreeNode *buildTreeFromSlice(vector<int> &inorder, int ifrom, int ito,
                               vector<int> &postorder, int pfrom, int pto) {
    if (ifrom > ito || pfrom > pto) {
      return nullptr;
    }
    if (ifrom == ito) {
      return new TreeNode(inorder[ifrom]);
    }
    if (pfrom == pto) {
      return new TreeNode(postorder[pfrom]);
    }
    TreeNode *root = new TreeNode(postorder[pto]);
    int idiv = sliceIndexOf (inorder, ifrom, ito, postorder [pto]); // 分界线
    root->left = buildTreeFromSlice(inorder, ifrom, idiv - 1, postorder, pfrom,
                                    pfrom + idiv - ifrom -1);
    root->right = buildTreeFromSlice(inorder, idiv + 1, ito, postorder,
                                     pfrom + idiv - ifrom, pto - 1);
    return root;
  }

public:
  TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
    int ifrom = 0, ito = inorder.size() - 1, pfrom = 0,
        pto = postorder.size() - 1;
    return buildTreeFromSlice(inorder, ifrom, ito, postorder, pfrom, pto);
  }
};

3. 无重复字符的最长子串

和最大和子串同样的套路，略。

5. 最长回文子串

思路：首先想到两端逼近。但是哪边先逼近是个问题。

然后想到可以选一个 pivot 然后向两端比较。但是性能比较垃圾。

  <-d->
babadabab

然后还可以试试 DP，$f [i,j]$ 表示 $v [i:j]$ 回文长度。但是递推关系实在想不出来。

最后用了两端比较（也有叫中心发射的）方法。

没意识到中心可以在两数中间（比如 ab|bc），所以代码处理得比较差劲，分别尝试了两种情况：

class Solution {
public:
  string longestPalindrome(string s) {
    int n = s.size();
    if (n == 0) {
      return "";
    }
    string ret = s.substr(0, 1);
    if (n == 1) {
      return ret;
    }
    int l, m, r, maxlen = 1;
    // cbbd
    for (m = 0; m < n - 1; m++) {
      int len = 0;
      l = m - 1, r = m + 1;
      int offset = 1;
      // 保存现场
      int ml = l, mr = r;
      
      if (l + 1 == r - 1 && s[l + 1] == s[r]) {
        r++;
        len = 2;
      branch1:
        while (l >= 0 && r <= n - 1) {
          if (s[l] != s[r]) {
            break;
          }
          l--;
          r++;
          len += 2;
        }
        if (len > maxlen) {
          maxlen = len;
          ret = s.substr(l + 1, len);
          cout << ret << endl;
        }
      }
    branch2:
      // 恢复现场
      l = ml;
      r = mr;
      len = 1;
      while (l >= 0 && r <= n - 1) {
        if (s[l] != s[r]) {
          break;
        }
        l--;
        r++;
        len += 2;
      }
      if (len > maxlen) {
        maxlen = len;
        ret = s.substr(l + 1, len);
        cout << ret << endl;
      }
    }
    return ret;
  }
};

下面是官方的解法，原来使用一个额外函数处理两种情况。我还以为可以有办法只处理一次。

class Solution {
public:
    pair<int, int> expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return {left + 1, right - 1};
    }

    string longestPalindrome(string s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.size(); ++i) {
            auto [left1, right1] = expandAroundCenter(s, i, i);
            auto [left2, right2] = expandAroundCenter(s, i, i + 1);
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};

121. 买卖股票的最佳时机

先试试穷举

class Solution {
public:
  int maxProfit(vector<int> &prices) {
    int maxDelta = 0, n = prices.size();
    for (int ibudy = 0; ibudy < n - 1; ibudy++) {
      for (int isell = ibudy + 1; isell < n; isell++) {
        auto curDelta = prices[isell] - prices[ibudy];
        if (curDelta > maxDelta) {
          maxDelta = curDelta;
        }
      }
    }
    return maxDelta;
  }
};

结果：超时

或者考虑滑动窗口？维护一个价差，然后左右调整。