leetcode解题思路分析（一百二十四）1025 - 1031 题

1025. 除数博弈
      爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。最初，黑板上有一个数字 n 。在每个玩家的回合，玩家需要执行以下操作：选出任一 x，满足 0 < x < n 且 n % x == 0 。用 n - x 替换黑板上的数字 n 。如果玩家无法执行这些操作，就会输掉游戏。只有在爱丽丝在游戏中取得胜利时才返回 true 。假设两个玩家都以最佳状态参与游戏。

数学题：先写几项观察规律，然后采用归纳演绎法证明。

class Solution {
public:
    bool divisorGame(int n) {
        return n % 2 == 0;
    }
};

1
2
3
4
5
6
7

1026. 节点与其祖先之间的最大差值
      给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

递归的传入当前祖先中的最大和最小值，然后比较即可

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxAncestorDiff(TreeNode* root) 
    {
        nRet = 0;
        if (root)
            findMostVal(root->val, root->val, root);
        return nRet;
    }

private:
    int nRet;
    void findMostVal(int nUp, int nDown, TreeNode* pNode)
    {
        if (pNode == NULL) return;

        int nMax = max(abs(nUp - pNode->val), abs(nDown - pNode->val));
        nRet = max(nRet, nMax);

        nUp   = max(nUp, pNode->val);
        nDown = min(nDown, pNode->val);

        findMostVal(nUp, nDown, pNode->left);
        findMostVal(nUp, nDown, pNode->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

1027. 最长等差数列
      给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], …, nums[ik] ，且 0 <= i1 < i2 < … < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

很容易想到用动态规划求解：dp[i][d]表示以i结尾公差为d的子数组长度，循环的时候为了不用遍历d，所以采用j = 0到 i - 1，然后依次取出公差，对对应的公差项进行++操作即可

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) 
    {
        int nRet  = 0;
        int nSize = nums.size();
        vector<vector<int>> dp(nSize, vector<int>(1001, 0));

        for (int i = 1; i < nSize; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                int diff = nums[i] - nums[j] + 500;
                dp[i][diff] = dp[j][diff] + 1;
                nRet = max(nRet, dp[i][diff]);
            }
        }

        return nRet + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1028. 从先序遍历还原二叉树
      我们从二叉树的根节点 root 开始进行深度优先搜索。在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。如果节点只有一个子节点，那么保证该子节点为左子节点。给出遍历输出 S，还原树并返回其根节点 root。

先序遍历的特点是先根，然后左，最后右。对应于本题，首先需要读取当前的深度及值，然后根据深度判断和上一个节点的关系：左节点，或者前面某一位置的右节点（一定不可能是上一节点的右节点，因为题目规定了必须保证只有一个子节点的时候是左节点，所以最多只能同级）。因此用一个栈来保存前面的节点们，然后依次出栈直至刚好栈深度为当前深度。之后再将该节点入栈即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* recoverFromPreorder(string traversal) 
    {
        stack<TreeNode*> path;
        int pos = 0;
        while (pos < traversal.size()) 
        {
            int level = 0;
            while (traversal[pos] == '-') 
            {
                ++level;
                ++pos;
            }

            int value = 0;
            while (pos < traversal.size() && isdigit(traversal[pos])) 
            {
                value = value * 10 + (traversal[pos] - '0');
                ++pos;
            }
            
            TreeNode* node = new TreeNode(value);
            if (level == path.size()) 
            {
                if (!path.empty()) 
                {
                    path.top()->left = node;
                }
            }
            else 
            {
                while (level != path.size()) 
                {
                    path.pop();
                }
                path.top()->right = node;
            }
            path.push(node);
        }
        while (path.size() > 1) 
        {
            path.pop();
        }
        return path.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

1029. 两地调度
      公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] 。第 i 人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。

贪心算法：假设所有人都去B，然后从中挑一些去A，则费用的变化是priceA - priceB，肯定是优先挑选差值小的，所以就按差值排序，然后取前一半去A后一半去B即可

class Solution {
    public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        // Sort by a gain which company has 
        // by sending a person to city A and not to city B
        sort(begin(costs), end(costs),
                [](const vector<int> &o1, const vector<int> &o2) {
            return (o1[0] - o1[1] < o2[0] - o2[1]);
        });

        int total = 0;
        int n = costs.size() / 2;
        // To optimize the company expenses,
        // send the first n persons to the city A
        // and the others to the city B
        for (int i = 0; i < n; ++i) total += costs[i][0] + costs[i + n][1];
        return total;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1030. 距离顺序排列矩阵单元格
      给定四个整数 rows , cols , rCenter 和 cCenter 。有一个 rows x cols 的矩阵，你在单元格上的坐标是 (rCenter, cCenter) 。返回矩阵中的所有单元格的坐标，并按与 (rCenter, cCenter) 的 距离 从最小到最大的顺序排。你可以按 任何 满足此条件的顺序返回答案。

遍历+输出

class Solution {
public:
    int dist(int r1, int c1, int r2, int c2) {
        return abs(r1 - r2) + abs(c1 - c2);
    }

    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int maxDist = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter);
        vector<vector<vector<int>>> bucket(maxDist + 1);

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int d = dist(i, j, rCenter, cCenter);
                vector<int> tmp = {i, j};
                bucket[d].push_back(move(tmp));
            }
        }
        vector<vector<int>> ret;
        for (int i = 0; i <= maxDist; i++) {
            for (auto &it : bucket[i]) {
                ret.push_back(it);
            }
        }
        return ret;
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

1031. 两个非重叠子数组的最大和
      给出非负整数数组 A ，返回两个非重叠（连续）子数组中元素的最大和，子数组的长度分别为 L 和 M。（这里需要澄清的是，长为 L 的子数组可以出现在长为 M 的子数组之前或之后。）

先取前缀和，然后遍历即可。

class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int L, int M) {
        int n = nums.size();
        vector<int> p(n+1);
        for(int i=1; i<=n; i++) p[i] = p[i-1] + nums[i-1];
        int res = 0;
        // 枚举 L
        for(int i=0; i+L<=n; i++){
            int sumL = p[i+L] - p[i];
            for(int j=0; j+M<i; j++){  // L前面 M 部分
                int sumM = p[j+M] - p[j];
                res = max(res, sumL + sumM);
            }
            for(int j = i+L; j+M<=n; j++){ // L后面的 M 部分
                int sumM = p[j+M]-p[j];
                res = max(res, sumL+sumM);
            }
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23