Leetcode 601-700

617. Merge Two Binary Trees (Easy)

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Input: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
         3
        / \
       4   5
      / \   \ 
     5   4   7

即合并两个二叉树

思路

递归合并即可

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
    if (t1 == nullptr) return t2;
    if (t2 == nullptr) return t1;
    t1->val += t2->val;
    t1->left = mergeTrees(t1->left, t2->left);
    t1->right = mergeTrees(t1->right, t2->right);
    return t1;
}

---

621. Task Scheduler (Medium)

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

思路

找出现次数最多的任务，出现m次，间隔为n，那么排完这个任务至少需要(m-1)*(n+1)+1，这里还需要注意两点

• 如果出现次数最多的任务有k个，那么至少需要$(m-1)\times(n-1)+k$
• 以上算法是别的任务来填这些空没有超出，如果超出那么总长度就是任务个数，最后需要做一下比较

int leastInterval(vector<char>& tasks, int n) {
    vector<int> nums(26, 0);
    for (auto c : tasks) nums[c - 'A'] ++;
    int mx = nums[0], times = 0;
    for (auto num : nums) {
        if (num == mx) times ++;
        else if (num > mx) {
            mx = num;
            times = 1;
        }
    }
    int t = (mx - 1) * (n + 1) + times;
    return max(t, int(tasks.size()));
}

---

647. Palindromic Substrings (Medium)

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

给一个字符串，求其中所有回文串个数

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

DP

dp[i][j]表示从s[i]到s[j]是不是回文串

转移条件即s[i] == s[j] && (j - i <= 2 || dp[i+1][j-1])

32ms ()

int countSubstrings(string s) {
    int res = 0, n = s.size();
    vector<vector<bool> > dp(n, vector<bool>(n, false));
    for (int i = n - 1; i >= 0; i --)
        for (int j = i; j < n; j ++) {
            if (s[i] == s[j] && (j - i <= 2 || dp[i+1][j-1])) dp[i][j] = true;
            if (dp[i][j]) res ++;
        }
    return res;
}

普通查找

从每一个位置开始，向左右搜索，复杂度也为$O(N^2)$，但常数更小

这里需要区分奇偶两种长度

int countSubstrings(string s) {
    int res = 0, n = s.size();
    for (int i = 0; i < n; i ++) {
        int j = 0;
        while (i - j >= 0 && i + j < n && s[i-j] == s[i+j]) {
            res ++;
            j ++;
        }
        j = 1;
        while (i - j + 1 >= 0 && i + j < n && s[i-j+1] == s[i+j]) {
            res ++;
            j ++;
        }
    }
    return res;
}

---

670. Maximum Swap (Medium)

一个整数，最多交换其中两个数的位置，要求所得值最大

Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7
Input: 9973
Output: 9973
Explanation: No swap

思路

从最高位开始，如果后面有比其更大的数字，与最大的一个交换即可

需要注意的是如果有多个最大数字，应该与最后一个交换，这样得到的最大，随便举个例子就可以发现

int maximumSwap(int num) {
    string s = to_string(num);
    for (int i = 0; i < s.size(); i ++) {
        int k = i;
        for (int j = i + 1; j < s.size(); j ++) {
            if (s[j] >= s[k]) k = j;
        }
        if (s[k] > s[i]) {
            swap(s[k], s[i]);
            return stoi(s);
        }
    }
    return num;
}