C++ : 力扣_Top(218-289)_力扣里面怎样编写代码

C++ : 力扣_Top(218-289)

---

218、天际线问题（困难）

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在，假设您获得了城市风光照片（图A）上显示的所有建筑物的位置和高度，请编写一个程序以输出由这些建筑物形成的天际线（图B）。

每个建筑物的几何信息用三元组 [Li，Ri，Hi] 表示，其中 Li 和 Ri 分别是第 i 座建筑物左右边缘的 x 坐标，Hi 是其高度。可以保证 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX 和 Ri - Li > 0。您可以假设所有建筑物都是在绝对平坦且高度为 0 的表面上的完美矩形。

例如，图A中所有建筑物的尺寸记录为：[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] 。

输出是以 [ [x1,y1], [x2, y2], [x3, y3], … ] 格式的“关键点”（图B中的红点）的列表，它们唯一地定义了天际线。关键点是水平线段的左端点。请注意，最右侧建筑物的最后一个关键点仅用于标记天际线的终点，并始终为零高度。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

例如，图B中的天际线应该表示为：[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]。

说明:
任何输入列表中的建筑物数量保证在 [0, 10000] 范围内。
输入列表已经按左 x 坐标 Li 进行升序排列。
输出列表必须按 x 位排序。
输出天际线中不得有连续的相同高度的水平线。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[…[2 3], [4 5], [12 7], …]

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<vector<int>> res;
        vector<pair<int, int>> h; // 存储建筑的左右坐标和高度对
        for (const auto& b : buildings) { // 遍历所有的建筑，将三元对拆分为二元对，数量变为两倍
            h.push_back(make_pair(b[0], -b[2])); // 建筑的<左下标，-高度>
            h.push_back(make_pair(b[1], b[2]));  // 建筑的<右下标，高度>
        } 
        sort(h.begin(), h.end()); // 对所有的二元对进行排序
        int pre = 0, cur = 0; // 楼层之前的高度、现在的高度
        multiset<int> m; // 哈希表，存储当前遍历的二元组的下标处的各楼层高度，顺带可以从小到大排序（重点）
        m.insert(0); // 默认当前楼层高度为0，防止为空，并且最后的时候可以加入（cur， 0）
        for (const auto& e : h) { // 从左到右遍历所有的二元对
            if (e.second < 0) m.insert(-e.second); // 如果是<左下标，-高度>，在高度集中插入该建筑高度
            else m.erase(m.find(e.second)); // 如果是<右下标，高度>，在高度集中删除该建筑高度
            cur = *m.rbegin(); // 获得到当前二元组下标处最高的楼层高度（multiset中的自动排序）
            if (pre != cur) {  // 如当前下标处，旧的最高高度pre不等于新的最高高度cur，则说明新建筑更高，要记录轮廓
                res.push_back({e.first, cur}); // 输出当前楼层左侧下标和高度
                pre = cur; // 将”之前的楼层高度“更新为”当前楼层高度“
            }
        }
        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
24
25

思路：比较绕的一道题，编写代码也比较讲究技巧。主要的思路是：输出轮廓的每个点其实都是当前下标处的几栋楼中的最高值，三元组不方便进行处理和分析，比较简单的方法是将其分为 <左下标，-高度> 和 <右下标，高度> 的两个二元组，一个二元组指向一个固定的下标，顺便还能根据高度的正负区分是左侧二元组还是右侧二元组，对所有二元组进行从左到右的排序，就可以根据下标从左到右离散遍历分析了；另外一个要点是建立一个multiset，用于存放当前遍历的下标处的所有楼层高度。如果遇到左侧二元组，则加入当前set，如果遇到右侧二元组，则弹出set。新加入的高度如果被放置在了set最后，则说明这是最高的高度，则可以记录下这个轮廓，如果不是最高，就不用记录了，一直遍历完即可；

---

227、基本计算器II（中等）

实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

输入: “3+2*2”
输出: 7

输入: " 3/2 "
输出: 1

输入: " 3+5 / 2 "
输出: 5

你可以假设所给定的表达式都是有效的。请不要使用内置的库函数 eval。

class Solution {
public:
    int calculate(string s) {
        int result = 0;
        int size = s.size();
        stack<int> stk;
        char pre = '+';
        for(int i=0; i<size; ++i){
            if(s[i]==' ') continue; // 如果是空格，跳过
            if(s[i]>='0' && s[i]<='9'){ // 是数字
                int start = i;
                while(i<size-1 && s[i+1]>='0' && s[i+1]<='9'){
                    ++i;
                }
                int tmp = stoi(s.substr(start, i-start+1)); // 获取当前数字
                if(pre=='+'){ // 如果之前是加号
                    stk.push(tmp);
                }
                else if(pre=='-'){ // 减号
                    stk.push(-tmp);
                }
                else if(pre=='*'){ // 乘号
                    int tmp_res = stk.top() * tmp;
                    stk.pop();
                    stk.push(tmp_res);
                }
                else if(pre=='/'){ // 除号
                    int tmp_res = stk.top() / tmp;
                    stk.pop();
                    stk.push(tmp_res);
                }
                continue;
            }
            else{ // 是加减乘除号
                pre = s[i]; // 记录这个运算符
                continue;
            }
        }
        while(!stk.empty()){ // 相加栈中的所有元素
            result += stk.top();
            stk.pop();
        }
        return result;
    }
};
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

思路：这道题没啥难度，但过程流程思路和代码编写需要考虑挺多细节的；首先明确数字可能是个多位数，没有负数，给出的string保证有计算结果，可能有空格，没有括号；首先明确式子中只有四则运算，会先计算乘除部分，可以先将式子中的乘除部分进行计算，然后把结果代替原先的乘除部分，式子变成加减运算式。遍历string，遍历过程中遇到空格就直接跳过即可；利用一个栈保存加减运算式的每个项，利用一个char pre变量保存当前遍历到的数字之前的运算符，如果是±，则将对应的±数字入栈，如果是*/，则将栈顶元素和当前数字进行运算，当做新的栈顶元素。遍历完后，对栈中所有元素进行加和即可；

---

230、二叉搜索树中第K小的元素（中等）

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

class Solution {
    int index;
public:
    int kthSmallest(TreeNode* root, int k) {
        index = 0;
        stack<TreeNode*> stk;
        while(root || !stk.empty()){
            if(root){
                stk.push(root);
                root = root->left;
            }
            else{
                root = stk.top();
                ++index;           // 在中序遍历的位置计算这是第几个节点
                if(index==k) break; // 如果是第k个，则直接输出
                stk.pop();
                root = root->right;
            }
        }
        return root->val;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路：利用B二叉搜索树的中序遍历是递增序列的特性就可以解决；写成非递归比较方便，当当前遍历输出的节点为第k个时，就直接返回结果就好了；

---

234、回文链表（简单）

请判断一个链表是否为回文链表。

输入: 1->2
输出: false

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==nullptr) return true;
        ListNode * slow = head, * fast = head;
        ListNode * pre = nullptr, * p = nullptr;
        while(fast && fast->next){
            p = slow;
            slow = slow->next; // 快慢指针遍历
            fast = fast->next->next;
            
            p->next = pre; // 前半部分链表反转
            pre = p;
        }
        if(fast){ // 是奇数个节点链表
            slow = slow->next; // 后半部分链表的开始节点
        }
        while(p && slow){ // 位于中间部分的两侧链表的开始节点
            if(p->val!=slow->val) return false;
            p = p->next;
            slow = slow->next;
        }
        return true;
    }
};
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

思路：这道题的主要问题是在 O(n) 时间复杂度和 O(1) 空间复杂度下实现，所以不能用额外内存；这样的话只能改变这个链表来实现，比较巧妙的做法是设置快慢指针，然后边遍历，边把前半部分的链表反转，等到快节点走到头了，慢节点就走到中间位置了，然后前半段链表被反转，这样从中间往两侧遍历，并进行等值判断，就可判断回文了；

---

236、二叉树的最近公共祖先（中等）

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:所有节点的值都是唯一的。p、q 为不同节点且均存在于给定的二叉树中。

class Solution {
    int index;
    vector<TreeNode*> res[2]; // 两个vector的数组，存放两个节点的完整路径
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || !p || !q) return nullptr;
        vector<TreeNode* > path; 
        index = 0;
        Traversal(root, p, q, path); // DFS，存在res[2]中遍历树找到两个节点的路径
        return FindCommon(); // 寻找两条路径的第一个共同节点
    }
    void Traversal(TreeNode* root, TreeNode* p, TreeNode* q, vector<TreeNode*>& path){
        if(root){
            path.push_back(root); // 当前节点入栈
            if(root==p || root==q){ // 如果是指定节点，则存入该路径，共执行两次
                res[index++].assign(path.begin(), path.end()); 
            }
            Traversal(root->left, p, q, path); 
            Traversal(root->right, p, q, path); 
            path.pop_back(); // 该节点遍历结束，返回之前节点
        }
    }
    TreeNode* FindCommon(){ // 寻找两条路径的第一个共同节点
        int size1 = res[0].size();
        int size2 = res[1].size();
        int diff = abs(size1-size2); // 两条路径之差
        int i = size1>size2 ? 0 : 1; // 找到更长的那条路径
        auto iter_i = res[i].rbegin(); // 定义两个反向迭代器，进行反向遍历
        auto iter_j = res[1-i].rbegin();
        while(diff>0){ // 更长的路径提前前进diff步
            ++iter_i;
            --diff;
        }
        while(*iter_i!=*iter_j){ // 寻找第一个共同节点
            ++iter_i; 
            ++iter_j;
        }
        return *iter_i;
    }
};
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

思路：上述方法是一种常规思路，需要DFS遍历树，然后保存两条完整的节点路径，之后看作是在两条链表中找第一个公共节点就行了，但这种方法的代码比较繁琐；另一种非常巧妙的方法如下：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root; // 如果该节点为空、或直接就是一个目的节点，则直接返回节点本身
        // 注意，这里可能是遍历到p节点，然后q节点是p节点的子节点，则公共节点还是p，故直接返回p节点本身就行了
        // 故该函数只能返回null、p、q三种节点；
        TreeNode *left = lowestCommonAncestor(root->left, p, q); // 遍历左子树，找到左子树的公共节点left
        TreeNode *right = lowestCommonAncestor(root->right, p, q); // 找到右子树的公共节点right
        // 如果左右子树的公共节点都不为空，则说明pq节点分别在左右子树中，当前节点就是最近公共祖先！
        if (left && right) return root; 
        // 如果只有一边是空，则返回另一边节点就好，如果都空，就返回空
        return left ? left : right; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

思路：这种方法的思想是如果在最近公共祖先处，则p和q肯定位于祖先的左右子树之中，所以深度遍历树左右节点时返回左右子树中的pq公共祖先，只有在最近公共祖先节点处，左右子树的结果都不为空，其他情况下，就返回了空节点；具体思路不太好想，注意遍历终止条件，见代码注释；这道题的思路和代码应重点研究；

---

237、删除链表中的节点（简单）

给定参数是一个链表中的节点，这个节点不是链表的尾节点，写一个函数删除这个节点；

输入: node = 5，在链表 [4,5,1,9] 中
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:

输入: node = 1，在链表 [4,5,1,9] 中
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明:

链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};
1
2
3
4
5
6
7

思路：力扣上这道题的题目给的有问题，容易误导人；这道题题目没有办法得知要删除节点的前一个节点，而且删除这个词用得也不准确，应该是从链表中“移除”。做法是将要删除节点自身变成下一个节点，然后将下一个节点从链表中移除，由于不知道原先的链表节点是new创建的还是直接创建的，所以这里也不需要delete，直接更改指针将其移出链表就行了；

---

238、除自身以外数组的乘积（中等）

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

输入: [1,2,3,4]
输出: [24,12,8,6]

提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size();
        int left = 1, right = 1;
        vector<int> result(size, 1); // 初始化结果矩阵
        // 正向遍历，计算每个节点左边的乘积
        for(int i=0; i<size; ++i){ 
            result[i] *= left;
            left *= nums[i];
        }
        // 反向遍历，每个节点在之前的左侧乘积基础上再乘以右侧乘积
        for(int i=size-1; i>=0; --i){ 
            result[i] *= right;
            right *= nums[i];
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

思路：首先不能使用除法，且空间复杂度须是1，故得想点特别的方法；首先注意到每个节点处的值等于该节点左侧的乘积乘以右侧的乘积，故可以利用两个数组保存每个节点的左右乘积，但不符合空间复杂度要求；又发现：可以先遍历累积计算左侧乘积，赋值到每个节点，再反向遍历累积计算右侧乘积，赋值到每个节点，就可以了；

---

239、滑动窗口最大值（困难）

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

进阶：你能在线性时间复杂度内解决此题吗？

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
 
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        if(nums.size()<k || k<=0 || nums.empty()) return result;
        deque<int> list; // 双端队列，存储当前划窗内有可能成为最大值的数字下标，front端永远是当前最大值下标
        for(int i=0; i<k; ++i){ // 先存放一个窗口
            while(!list.empty() && nums[list.back()]<=nums[i]){
                list.pop_back(); // 如果当前元素之前插入的元素比当前元素还小，直接pop了
            }
            list.push_back(i); // 加入当前元素下标
        }
        result.push_back(nums[list.front()]); // 存储第一个结果 
        for(int i=k; i<nums.size(); ++i){ // 划窗移动
            if(i-list.front()>=k) list.pop_front(); // 如果当前的最大值下标已经出了窗口了，pop掉
            while(!list.empty() && nums[list.back()]<=nums[i]){ 
                list.pop_back(); // 按照同样的思路pop掉之前插入的较小值的下标
            }
            list.push_back(i); // 插入当前下标
            result.push_back(nums[list.front()]); // 存储当前结果
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

思路：剑指offer第59题原题；利用双端队列存储当前窗口的最大值的下标；其中当前窗口的最大值下标永远在front一端；插入新元素下标时从back端插入，插入之前判断：如果当前要插入元素比队列中的back端的值要小，说明等大的值移出队列后这个元素有可能变成最大值，故直接push_back；如果当前元素大于back端元素，则说明之前插入的back端元素不可能是最大值了，pop_back掉，再push新元素；顺便每次滑动的时候，判断队列front端的元素是不是还在窗口中，不在就pop；这样的话，就可以保证当前队列front端存储的是最大值下标了；

---

240、搜索二维矩阵 II（中等）

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。每列的元素从上到下升序排列。

现有矩阵 matrix 如下：
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
1
2
3
4
5
6
7
8

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        int m = matrix.size() - 1;
        int n = matrix[0].size() - 1;
        int x = 0, y = n; // 从左上角坐标处开始查找
        int tmp;
        while(x<=m && y>=0){
            tmp = matrix[x][y];
            if(tmp==target) return true;
            if(tmp<target) ++x; // 如果右上角值小于目标，则说明当前行都小于目标，往下一行搜索
            else --y; // 如果右上角值大于目标，则说明当前列都大于目标，往左搜索一行
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路：剑指offer原题，从右上角或左下角开始搜索即可，思路见代码注释；

---

242、有效的字母异位词（简单）

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

输入: s = “anagram”, t = “nagaram”
输出: true

输入: s = “rat”, t = “car”
输出: false

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

class Solution {
public:
    bool isAnagram(string s, string t) {
        int dict[256] = {0}; // ASCII码字典
        for(auto c : s){ 
            ++dict[c]; // 遍历s，对应字符的数目+1
        }
        for(auto c : t){
            --dict[c]; // 遍历t，对应字符的数目-1
        }
        for(auto c : dict){ // 核查dict，如果有不为0的，则说明不匹配
            if(c!=0) return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

思路：简单的题，利用长度为256的数组当做ASCII码字符的哈希表，统计两个字符串中字符的个数是否相等即可；

---

268、缺失数字（简单）

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。

输入: [3,0,1]
输出: 2

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

// 求和公式方法（可能会溢出）
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n = nums.size() + 1;
        int sum = n*(n-1)/2; // 求和公式（a1n+n(n-1)d/2)
        for(auto i : nums){
            sum -= i; 
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

// 异或方法
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        if(nums.empty()) return 0;
        int res = 0, i = 0;
        for(; i<nums.size(); ++i){
            res ^= i;
            res ^= nums[i];
        }
        return res^i;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

思路：第一种使用等差求和公式，计算理论总和，然后全部减去，剩余就是结果，但可能会有溢出问题；更好的方法是利用：对一个数进行两次完全相同的异或运算会得到原来的数，来进行异或运算，先对0-n的全部值进行异或，然后再对数组中的元素全部异或，数组中存在的值都被异或了两次，只有缺失的值只有一次，故结果就是缺失的值；

---

279、完全平方数（中等）

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

class Solution {
public:
    int numSquares(int n) {
        vector<int> tmp(n+1, INT_MAX);
        tmp[0] = 0;
        for(int i=1; i<=n; ++i){ // 递推式：R(n) = 1 + R(n-j*j);
            for(int j=1; i-j*j>=0; ++j){ // 在之前的R(n-j*j)的解中找到最优值
                tmp[i] = min( tmp[i], tmp[i-j*j]+1 ); // 将当前n=i处的最优结果赋予最优解：1+(n=i-j*j处的最优解)
            }
        }
        return tmp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

思路：这道题还是有些难度，由于要求的是一个比较灵活的最优解，故暴力遍历等方法不太适用；这道题应该用动态规划的思路来想，首先发现规律：一个正整数N可以写为两部分的加和：N=I·I+N’; 而N’=J·J+N’’; 而题目要求的是加和项最小的数目，设数字n的最小和项数目为R(n), 则R(n)=1+R(n’), 故问题变成了动态规划；代码很巧妙，利用一个数组从1开始存储每个数的最少和项目数，即R(i), 而R(2)由R(1)计算得来，R(3)由R(2)计算而来；不明白的话可以手推一下代码；

---

283、移动零（简单）

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i = 0, j = 0; // i用来遍历检索非0数字，j指向当前要被交换的位置
        for(; i<nums.size(); ++i){ // 遍历数组
            if(nums[i]!=0){ // 当前不是零
                swap(nums[i], nums[j++]); // 交换两个值
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11

思路：双指针遍历交换即可，代码虽短但不太好想，举例推导一下就明白了；

---

287、寻找重复数（中等）

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

输入: [1,3,4,2,2]
输出: 2

输入: [3,1,3,4,2]
输出: 3

说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

// 位运算做法
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int count1[32] = {0};
        int count2[32] = {0};
        int result = 0;
        for(auto v : nums){  //  统计在n+1长的数组中，每位共有多少个1，count1
            for(int i=0; i<32; ++i){
                count1[i] += v & 1;
                v = v >> 1;
            }
        }
        for(int n=1; n<=nums.size()-1; ++n){ // 统计在1~n的序列中，每位共有多少个1，count2
            int tmp = n;
            for(int i=0; i<32; ++i){
                count2[i] += tmp & 1;
                tmp = tmp >> 1;
            }
        }
        for(int i=31; i>=0; --i){ // 如果count1中有重复的数，则这一位1的个数一定比count2中要多
            result = result << 1;
            if(count1[i]>count2[i]){
                result = result | 1; // 如果多了，则说明重复的数这一位是1
            }
        }
        return result;
    }
};
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

// 快慢指针做法
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0; // 快慢指针，象征链表节点
        while(true){
            slow = nums[slow]; // 元素的值象征节点的next指针
            fast = nums[fast];
            fast = nums[fast];
            if(slow==fast) break; // 在某个节点相遇
        }
        slow = 0;
        while(slow!=fast){ // 一个从头开始，一个从相遇点开始，都一次走一步，再次相遇就是环的入口节点；
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

思路：有趣且巧妙的题，首先由于各种复杂度限制，且不能改变原数组，不能使用排序法和哈希表；这里有两种巧妙的思路：1、利用位运算找规律，发现只要有重复的数，统计1_{n+1的数组里二进制各位的1的总数，和统计1}n连续序列中各位是1的总数，一定是前者在某几位大于后者，且哪一位的1多了，重复的数的对应位数一定是1，不清楚可以举例如13422；2、将数组看成是一个链表（数组下标0~n象征链表节点、数组元素值对应链表的next指针，指向下一个对应节点），如果有一个重复的数，说明链表有多个节点指向同一个节点，即存在环，只需要找到环的入口节点即可；即使用快慢指针，相遇后说明有环、然后一个从开始节点开始，一个从相遇节点开始，都一次走一步，再次相遇时的节点就是环的入口（重复的数）；

---

289、生命游戏（中等）

根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

输入：
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
输出：
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]

进阶：
你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        if(board.empty() || board[0].empty()) return;
        int x_index[] = {-1,0,1,-1,1,-1,0,1}; // 利用数组存储周围八个点的坐标移动值
        int y_index[] = {-1,-1,-1,0,0,1,1,1}; // 利用数组存储周围八个点的坐标移动值
        for(int i=0; i<board.size(); ++i){ // 遍历网格每个细胞
            for(int j=0; j<board[0].size(); ++j){  

                int sum = 0; // 统计周围的活细胞数
                for(int n=0; n<8; ++n){ // 遍历每个细胞周围的八个细胞
                    int x = i + x_index[n];
                    int y = j + y_index[n];
                    if(x>=0 && x<board.size() && y>=0 && y<board[0].size()){
                        sum += (board[x][y] & 1);  // 累积活细胞数
                    }
                }
                if(board[i][j]==1){ // 如果中间是活细胞
                    if(sum==2 || sum==3){ // 如果周围有2或3个活细胞，则存活，否则死亡
                        board[i][j] |= 2; // 或上一个2，把第二个bit位置1
                    } 
                }
                if(board[i][j]==0){ // 中间是死细胞
                    if(sum==3){
                        board[i][j] |= 2; // 死细胞周围有三个活的，则复活
                    }
                }
            }
        }
        for(int i=0; i<board.size(); ++i){ // 遍历网格每个细胞
            for(int j=0; j<board[0].size(); ++j){  
                board[i][j] = board[i][j] >> 1; // 右移一位，舍弃原先的值，赋予第二位比特位的新值
            }
        }
    }
};
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

思路：很棒的一道题，首先考虑使用遍历的方法法就可以，统计每个细胞周围的活细胞数，然后记录新的状态，但问题在于如何在不使用额外内存空间的前提下同时更改整个数组；巧妙的做法是数组中只有0和1两个值，只利用了int型32位bit中的第一位，其他几位都没有利用，可以将新的状态记录到第二个bit位，最后同时改变数组状态就是将所有的细胞右移一位即可；另外搜索周围八个细胞的坐标可以事先建立路径变化数组，然后写一个循环就可以了，比较方便，具体见代码；

---