根据这个站刷的：剑指 Offer 题解 | CS-Notes 面试笔记 (cyc2018.xyz)

题目总数76

错误总结

初始化错误

错误：

1
2
3
4
5
6
7
class Solution
{
public:
    vector<char> order(256, '\0');    // 记录字符最早出现的次序；
    vector<int> mark(256, 0);   // 标记是否出现过；
    
}

正确：

在C++中，类的成员变量不能在类内部进行初始化，需要在构造函数中或者类外部进行初始化。因此，你不能在类的定义中直接对order和mark进行初始化，会导致编译错误。

解决方法是将变量的初始化移到构造函数中，或者在类外部进行初始化。

以下是修正后的代码：

1
2
3
4
5
6
7
8
class Solution
{
public:
    Solution() : order(256, '\0'), mark(256, 0) {} // 在构造函数中进行初始化
private:
    vector<char> order;    // 记录字符最早出现的次序；
    vector<int> mark;      // 标记是否出现过；
};

在这个修正后的版本中，我们将order和mark的初始化移到了构造函数中，并且将它们从类的定义中移动到了私有成员变量部分。这样就能够正确地初始化这两个向量。


问：

为什么int cnt = 0;这样的可以呢

GPT：

在C++中，你可以在类的定义内部初始化非静态成员变量，但是这只适用于常规的数据类型（例如int、double等）和某些类类型（例如std::string）。

这种方式的初始化是一种方便的语法糖，它允许你在类的定义中直接指定成员变量的初始值，而不需要在构造函数中显式地初始化它们。编译器会在对象创建时自动调用合适的构造函数来初始化这些成员变量。

例如，下面是一个示例：

1
2
3
4
class MyClass {
public:
    int cnt = 0; // 直接在类内部初始化成员变量 cnt
};

在这个示例中，cnt被初始化为0，这意味着当创建一个MyClass对象时，它的cnt成员变量会自动被设置为0。

string生命周期问题

来自下面的 - 树小节中的题目序列化二叉树

实际上，std::string的c_str()方法并不返回一个新的char[]数组。它返回的是一个指向内部数据结构中以'\0'结尾的字符数组的指针。这个返回的指针是const char*类型，指向的内存区域由std::string对象管理，你不应该尝试修改它指向的内容。重要的是，这个指针仅在相关的std::string对象没有被修改（包括但不限于内容的修改、重新分配内存等）和没有被销毁的情况下保持有效。

关键点：

  • 生命周期管理：返回的const char*指针所指向的内存是由std::string对象负责管理的。如果std::string对象被销毁或其内容被修改（可能导致重新分配内存），那么之前通过c_str()获得的指针可能会变得无效。
  • 非独立的内存区域：c_str()方法返回的指针并不指向一个独立分配的内存区域，而是直接指向std::string内部用于存储字符串的内存。因此，没有必要（也不应该）尝试释放这个指针指向的内存。
new的问题

也是来自下面的 - 树小节中的题目序列化二叉树

这是一个常见的错误，很容易被忽视。在C++中：

  • new char[ans.length() + 1] 正确地分配了一个字符数组，长度为ans.length() + 1。
  • new char(ans.length() + 1) 则是分配了单个字符，并用ans.length() + 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
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        /*
            时间复杂度 O(N)，空间复杂度 O(1)
            思想第i个位置放值为i
        */
        int n = numbers.size();
        for (int i = 0; i < n; i++) {
            while (numbers[i] != i) {
                if (numbers[i] == numbers[numbers[i]]) {
                    return numbers[i];
                }
                swap(numbers[i], numbers[numbers[i]]);
            }
        }
        return -1;
    }
};
查看代码

目标：时间复杂度 O(M + N)，空间复杂度 O(1)

  1. 设置一个索引i来表示行，初始值为0，另一个索引j来表示列，初始值为n - 1。

  2. 当i < m且j >= 0

    时进行搜索：

    • 如果target等于matrix[i][j]，返回true。
    • 如果target小于matrix[i][j]，则target不可能在当前列中，因此j--。
    • 如果target大于matrix[i][j]，则target不可能在当前行中，因此i++。

  3. 如果退出循环，说明没有找到target，返回false。

为什么从右上角开始，因为每一次操作都可以缩小查找范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) return true;
            if (matrix[i][j] > target) {
                j--;
                continue;
            }
            if (matrix[i][j] < target) {
                i++;
                continue;
            }
        }
        return false;
    }
};
查看代码

代码随想录中写过原题

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
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
         // --计算空格数--
        int oldSize = s.size();
        int cnt = 0;
        for (int i = 0; i < oldSize; i++) {
            if (s[i] == ' ') cnt++;
        }
        // --扩大数组，加上所有空格的大小（本来就占用一个了）--
        s.resize(oldSize + cnt *2);
        int newSize = s.size();
        // --slow遍历，fast指向下一个存放的位置--
        int slow = oldSize - 1, fast = newSize - 1;
        while (slow < fast) {
            if (s[slow] == ' ') {
                s[fast--] = '0';
                s[fast--] = '2';
                s[fast--] = '%';
                slow--;
            }
            else s[fast--] = s[slow--];
        }
        return s;
    }
};
查看代码

代码随想录中写过类似的

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Solution {
public:
    enum Direction {LEFT_, DOWN_, RIGHT_, UP_};
    bool isOver(int i, int j, int m, int n) {   // 检查是否越界
        if (i >= m || j >= n || i < 0 || j < 0) return true;
        return false;
    }
    vector<int> printMatrix(vector<vector<int> > matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> ans;
        vector<vector<int>> mark(m, vector<int>(n, 0));     // 标记数组，0未访问过，1访问过
        int i = 0, j = 0;   // 当前位置
        int t = m * n;
        Direction d = RIGHT_; // 当前的方向
        while (t--) {
            switch (d) {
                case LEFT_: {
                    if (!isOver(i, j, m, n) && mark[i][j] == 0) {
                        // 记录 + 标记 + 前进
                        ans.push_back(matrix[i][j]);
                        mark[i][j] = 1;
                        j++;
                    }
                    else {
                        // 回退 + 转向 + 前进
                        j--;
                        t++;
                        d = DOWN_;
                        i++;
                    }
                    break;
                }
                case DOWN_: {
                    if (!isOver(i, j, m, n) && mark[i][j] == 0) {
                        // 记录 + 标记 + 前进
                        ans.push_back(matrix[i][j]);
                        mark[i][j] = 1;
                        i++;
                    }
                    else {
                        // 回退 + 转向 + 前进
                        i--;
                        t++;
                        d = RIGHT_;
                        j--;
                    }
                    break;
                }
                case RIGHT_: {
                    if (!isOver(i, j, m, n) && mark[i][j] == 0) {
                        // 记录 + 标记 + 前进
                        ans.push_back(matrix[i][j]);
                        mark[i][j] = 1;
                        j--;
                    }
                    else {
                        // 回退 + 转向 + 前进
                        j++;
                        t++;
                        d = UP_;
                        i--;
                    }
                    break;
                }
                case UP_: {
                    if (!isOver(i, j, m, n) && mark[i][j] == 0) {
                        // 记录 + 标记 + 前进
                        ans.push_back(matrix[i][j]);
                        mark[i][j] = 1;
                        i--;
                    }
                    else {
                        // 回退 + 转向 + 前进
                        i++;
                        t++;
                        d = LEFT_;
                        j++;
                    }
                    break;
                }
            }
        }
        return ans;
    }
};
查看代码

ASCII实际上确实有128个不同的符号，这是因为它是一个7位的字符编码标准，覆盖了从0到127的值。但是，经常有一种扩展的ASCII版本被称为“扩展ASCII”或“8位ASCII”，它使用了第八位来扩展字符集，允许256个不同的值（从0到255）。

在很多情况下，尽管原始ASCII只定义了128个字符，程序员仍然会创建一个大小为256的数组，来包含可能的扩展ASCII字符。这是一种预防措施，以确保程序可以处理非标准的ASCII值，尤其是那些可能出现在某些特殊文本编码或者用户输入中的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
   
    int FirstNotRepeatingChar(string str) {
        vector<int> cnt(256, 0);    // 标记出现次数
        for (char c : str) {
            cnt[c]++;
        }
        // 再次遍历字符串，查找第一个出现次数为1的字符
        for (int i = 0; i < str.size(); i++) {
            if (cnt[str[i]] == 1) return i;
        }
        return -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
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if (stack2.empty()) {
            // 将队尾栈全部压到队头栈
            while(!stack1.empty()) {
                int tmp = stack1.top();
                stack1.pop();
                stack2.push(tmp);
            }
        }
        int res = stack2.top();
        stack2.pop();
        return res;
    }

private:
    stack<int> stack1;  // 队尾
    stack<int> stack2;  // 队头
};
查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    /*
        同步操作两个栈
        特别之处：minStack压栈，比栈顶小直接放，比栈顶大复制一份栈顶
    */
    stack<int> commonStack;
    stack<int> minStack;
    void push(int value) {
        commonStack.push(value);
        if (minStack.empty()) minStack.push(value);     // 第一个直接放
        else minStack.push(value < minStack.top() ? value : minStack.top());
    }
    void pop() {
        commonStack.pop();
        minStack.pop();
    }
    int top() {
        return commonStack.top();
    }
    int min() {
        return minStack.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
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        if (pushV.size() != popV.size()) return false;
        stack<int> imitate;     // 用一个栈来模拟这个过程
        int j = 0;
        for (int i : pushV) {
            imitate.push(i);
            while (!imitate.empty() && imitate.top() == popV[j]) {
                imitate.pop();
                j++;
            }
        }
        if (imitate.empty()) return true;
        else return false;
    }
};
查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型vector 
     * @param k int整型 
     * @return int整型vector
     */
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        priority_queue<int, vector<int>, greater<int>> heap;
        vector<int> ans;
        for (int i : input) 
            heap.push(i);
        while (k--) {
            ans.push_back(heap.top());
            heap.pop();
        }
        return ans;
    }
};
查看代码 
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
59
60
61
62
63
64
65
66
67
68
#include <queue>
class Solution {
  public:
    /*
        思路：
        建立两个堆，一个大根堆，一个小根堆，然后使得
        - 奇数时：两个根的数量相差一
        - 偶数时：两个根数量相等
        - 大根堆中的数字都小于小根堆（也就是比较堆顶大小）
        [大根堆，中位数，小根堆]

        实现:
        以下实现中
        - 奇数时，minHeap比maxHeap多一个
        - 偶数时，minHeap和maxHeap数量相等
    */
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    int cnt = 0;
    void Insert(int num) {
        cnt++;
        // 特判只有一个和两个的时候
        if (cnt == 1) {
            minHeap.push(num);
            return;
        }
        if (cnt == 2) {
            if (num > minHeap.top()) {
                maxHeap.push(minHeap.top());
                minHeap.pop();
                minHeap.push(num);
            }
            else maxHeap.push(num);
            return;
        }
        // 其他情况
        if (num >= maxHeap.top() && num <= minHeap.top()) {
            if (cnt % 2 == 0) {
                maxHeap.push(num);
            } else {
                minHeap.push(num);
            }
        }
        else if (num < maxHeap.top()) {
            maxHeap.push(num);
            if (cnt % 2 == 1) {     // 补一个给minHeap来维持数量差
                minHeap.push(maxHeap.top());
                maxHeap.pop();
            }
        }
        else {
            minHeap.push(num);
            if (cnt % 2 == 0) {     // 补一个给maxHeap来维持数量差
                maxHeap.push(minHeap.top());
                minHeap.pop();
            }
        }
    }

    double GetMedian() {
        if (cnt % 2 == 0) {
            return (double)(maxHeap.top() + minHeap.top()) / 2;
        } else { // minHeap比maxHeap的数量多一个
            return minHeap.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
class Solution
{
public:
    Solution() : order(256, '\0'), cnt(256, 0) {} // 在构造函数中进行初始化
  //Insert one char from stringstream
    void Insert(char ch) {
        if (cnt[ch] == 0) {    // 首次出现
           order.push_back(ch);
           cnt[ch]++;
        }
        else cnt[ch]++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce() {     // 用order[]来限制每次操作都为O(1)
        for (int i = 0; i < order.size(); i++) {
            if (cnt[order[i]] == 1) {
                return order[i];
            }
        }
        return '#';
    }
private:
    vector<char> order;    // 记录字符最早出现的次序；
    vector<int> cnt;      // 标记是否出现过；
};
查看代码

法一：堆

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
#include <queue>
#include <utility>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @param size int整型 
     * @return int整型vector
     */
    vector<int> maxInWindows(vector<int>& num, int size) {
        /*
            分析：每次移动都会出去一个，进来一个
            思路：维护一个大根堆
            但是出堆怎么解决呢？
            问了gpt，堆内存的是(索引，值)
            1. 出堆：如果堆顶索引不在窗口内，就一直出堆
            2. 入堆：新元素入堆
            但是这样的最坏时间复杂度是o(n log n)啊
        */
        vector<int> ans;
        if (size == 0 || size > num.size()) return ans;
        priority_queue<pair<int, int>> maxHeap;     // (索引，值)
        for (int i = 0; i < size; i++) {    // 初始窗口
            maxHeap.push(make_pair(num[i], i));
        }
        ans.push_back(maxHeap.top().first);
        for (int i = 1; i <= num.size() - size; i++) {   // 窗口为i ~ i+size-1
            // 1. 出堆
            while (!maxHeap.empty() && maxHeap.top().second < i) maxHeap.pop();
            // 2. 入堆
            maxHeap.push(make_pair(num[i + size - 1], i + size - 1));
            // 3. 当前最大值
            ans.push_back(maxHeap.top().first);
        }
        return ans;
    }
};

法二：双端队列




双指针

查看代码

法一：双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int left = 0, right = array.size() - 1;
        vector<int> ans;
        while (left < right) {
            int curSum = array[left] + array[right];
            if (curSum == sum) {
                ans.push_back(array[left]);
                ans.push_back(array[right]);
                return ans;
            }
            else if (curSum > sum) right--;  // 变小点
            else left++;    // 变大点
        }
        return ans;
    }
};

法二：哈希表（代码随想录中刷过）

查看代码 
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
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param sum int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > ans;
        int left = 1, right = 2;
        int curSum = 3;
        while (left < right) {
            if (curSum == sum) {
                vector<int> tmp;
                for (int i = left; i <= right; i++) tmp.push_back(i);
                ans.push_back(tmp);
                // 继续寻找
                curSum -= left;
                left++; 
            }
            else if (curSum > sum)  {   // 太大了，减点
                curSum -= left;
                left++;
            }     
            else {  // 太小了，加点
                right++;
                curSum += right;
            }   
        }
        return ans;
    }
};
查看代码 
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
class Solution {
public:
    string ReverseSentence(string str) {
        /*
            思路：先翻转单词，在翻转全部
        */ 
        string ans;
        bool status = false;    // 是否是单词
        for (int i = 0; i < str.size(); i++) {
            bool old_status = status;
            if (str[i] == ' ') status = false;
            else status = true;
            // 由false跳true，表示接下来是单词
            if (old_status == false && status == true) {
                int curi = i;
                while (i < str.size() && str[i] !=  ' ') i++;
                i--;    // 回退一下，for循环有i++
                // 翻转单词
                for (int j = i; j >= curi; j--) ans.push_back(str[j]); 
                ans.push_back(' ');
            }
        }
        ans.pop_back();     // 去掉最后一个单词后面的空格
        int i = 0, j = ans.size() - 1;
        while (i < j) {
            char tmp = ans[i];
            ans[i] = ans[j];
            ans[j] = tmp;
            i++, j--;
        };
        return ans;
    }
};
查看代码 
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:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param n int整型 
     * @return string字符串
     */
    void reverseString(string &str, int left, int right) {  // [left, right]
        for (;left < right; left++, right--) {
            char tmp = str[left];
            str[left] = str[right];
            str[right] = tmp;
        }
    }
    string LeftRotateString(string str, int n) {
        /*
            思路：先将两个子串翻转，再总体翻转
        */
        if (str.empty()) return str;    // 特俗情况：str为空
        n %= str.size();                // 特俗情况：n>str.size();
        reverseString(str, 0, n - 1);
        reverseString(str, n, str.size()-1);
        reverseString(str, 0, str.size()-1);
        return str;
    }
};




链表

查看代码 
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
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
#include <vector>
class Solution {
public:
    /*
        用回溯法
     */
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ans;
        traverse(ans, head);
        return ans;
    }
private:
    void traverse(vector<int> &ans, ListNode* node) {
        if (node == nullptr) return;
        traverse(ans, node->next);
        ans.push_back(node->val);
    }
};
查看代码 
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // --初值为空的情况--
        if (!head)  return nullptr;
        // --增加一个哨兵节点--
        ListNode* head0 = new ListNode;
        head0->next = head;
        ListNode* tmp = head0;
        // --遍历--
        while (tmp) {
            // --删除--
            if (tmp->next && tmp->next->val == val) {
                ListNode* need2Delete = tmp->next;
                tmp->next = tmp->next->next;
                delete need2Delete;
                continue;   // 不然会跳判
            }
            tmp = tmp->next;
        }
        return head0->next;
    }
};
查看代码 
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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
#include <utility>
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (!pHead) return pHead;
        map<int, int> cnt;  // <val , 出现次数>
        traverse(pHead, cnt);
        ListNode *head = new ListNode(0);
        head->next = pHead;
        ListNode *p = head;
        while (p->next) {
            if (cnt[p->next->val] > 1) {    // 出现次数大于1的删除
                ListNode *need2delete = p->next;
                p->next = p->next->next;
                delete need2delete;
                continue;
            }
            p = p->next;
        }
        return head->next;
    }
private: 
    void traverse(ListNode *node, map<int, int> &cnt) {
        if (node == nullptr) return;
        if (cnt.count(node->val) == 0) cnt.insert(make_pair(node->val, 1));
        else cnt[node->val]++;
        traverse(node->next, cnt);
    }
};
查看代码

代码随想录类似题：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

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
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        ListNode *fast = pHead;
        while (fast && k--) fast = fast->next;  
        if (fast == nullptr && k > 0) return nullptr;    // 比k还短
        while (fast) {
            fast = fast->next;
            pHead = pHead->next;
        }
        return pHead;
    }
};
查看代码

代码随想录中刷过，用的方法不一样

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
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {
        // 头插法
        ListNode *head0 = new ListNode(0);
        ListNode *p = head;
        while (p) {
            ListNode *tmp = p;
            p = p->next;
            tmp->next = head0->next;
            head0->next = tmp;
        }
        return head0->next;
    }
};
查看代码 
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
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstdio>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode *head0 = new ListNode(0);
        ListNode *p = head0;
        while (pHead1 && pHead2) {
            if (pHead1->val > pHead2->val) {
                p->next = pHead2;
                pHead2 = pHead2->next;
            }
            else {
                p->next = pHead1;
                pHead1 = pHead1->next;
            }
            p = p->next;
        }
        if (pHead1) p->next = pHead1;
        else p->next = pHead2;
        return head0->next;
    }
};
查看代码 
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
/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
#include <cstdio>
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        /*
            看题解了
        */
        if (pHead == nullptr) return nullptr;
        // 第一步，在每个节点的后面插入复制的节点。
        RandomListNode *p = pHead;
        while (p) {
            RandomListNode *newNode = new RandomListNode(p->label);
            newNode->next = p->next;
            p->next = newNode;
            p = p->next->next;
        }
        // 第二步，对复制节点的 random 链接进行赋值。
        p = pHead;
        while (p) {
            if (p->random != nullptr) 
                p->next->random = p->random->next;
            p = p->next->next;
        }
        // 第三步，拆分。（原链表也要还原，不然出错）
        RandomListNode* copyHead = pHead->next;
        RandomListNode* tmp;
        p = pHead;
        while (p) {
            tmp = p->next;
            p->next = tmp->next;
            if(tmp->next) tmp->next = tmp->next->next;
            p = p->next;
        }
        return copyHead;
    }
};
查看代码 
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
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        int len1 = lenListNode(pHead1);
        int len2 = lenListNode(pHead2);
		// 让1链表更长
		if (len1 < len2) {
			swap(len1, len2);
			swap(pHead1, pHead2);
		}
		for (int i = 0; i < len1 - len2; i++, pHead1 = pHead1->next);
		for (; pHead1; pHead1 = pHead1->next, pHead2 = pHead2->next) {
			if (pHead1 == pHead2) return pHead1;
		}
		return nullptr;
    }
private:
	int lenListNode(ListNode *node) {
		if (node == nullptr) return 0;
		return lenListNode(node->next) + 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
37
38
39
40
41
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型vector 
     * @param vinOrder int整型vector 
     * @return TreeNode类
     */
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        return rebuidBTree(preOrder, vinOrder, 
                    0, preOrder.size()-1, 
                    0, vinOrder.size()-1);
    }
private:
    TreeNode* rebuidBTree(vector<int>& preOrder, vector<int>& vinOrder, 
                            int preBegin, int preEnd, int vinBegin, int vinEnd) {
        if (preBegin > preEnd) return nullptr;
        TreeNode *newNode = new TreeNode(preOrder[preBegin]);
        int vinRootIndex = vinBegin;
        for (; 
            vinRootIndex <= vinEnd && vinOrder[vinRootIndex] != preOrder[preBegin]; 
            vinRootIndex++) ;
        newNode->left = rebuidBTree(preOrder, vinOrder, 
                            preBegin+1, preBegin + (vinRootIndex - vinBegin), 
                            vinBegin, vinRootIndex - 1);
        newNode->right = rebuidBTree(preOrder, vinOrder, 
                            preBegin + (vinRootIndex - vinBegin) + 1, preEnd,
                            vinRootIndex + 1, vinEnd);
        return newNode; 
    }
};
查看代码 
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
/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        // 情况1. 有右子树，那就在自己的右子树中不断向左寻找
        TreeLinkNode *nextNode = pNode->right;
        while (nextNode && nextNode->left) nextNode = nextNode->left;
        if (nextNode) return nextNode;
        // 情况2. 没有右子树，则向上遍历，找到自己处于的某棵最小左子树，那么根节点就是下一个
        nextNode = pNode->next;
        TreeLinkNode *old_nextNode = pNode;
        bool flag = false;
        while (nextNode) {
            if (nextNode->left == old_nextNode) {
                flag = true;
                break;
            }
            old_nextNode = nextNode;
            nextNode = nextNode->next;
        }
        if (flag) return nextNode;
        return nullptr;
    }
};
查看代码

代码随想录做过类似：572. 另一棵树的子树 - 力扣（LeetCode）

注意这题是子结构，不是子树

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
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool isSubStruct(TreeNode* p, TreeNode* q) {
        // --1. 子树都为空--
        if (!p && !q) return true;
        // --2. 子树有一个不为空--
        if (!p && q) return false;
        if (p && !q) return true;
        // --3. 子树都不为空--
        if (p->val == q->val      // 自己是否相等
            && isSubStruct(p->left, q->left)  // p左子树和q左子树是否相等
            && isSubStruct(p->right, q->right))  // p右子树和q右子树是否相等
            return true;
        return false;
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
		if (!pRoot2) return false;	// 特判空的情况
		if (!pRoot1) return false;
        return isSubStruct(pRoot1, pRoot2) 
            || HasSubtree(pRoot1->left, pRoot2) 
            || HasSubtree(pRoot1->right, pRoot2);
    }
};

查看代码 
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
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        traverse(pRoot);
        return pRoot;
    }
private:
    void traverse(TreeNode *&node) {
        if (!node) return;
        swap(node->left, node->right);
        traverse(node->left);
        traverse(node->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
38
39
40
/*
 * @lc app=leetcode.cn id=101 lang=cpp
 *
 * [101] 对称二叉树
 */

// @lc code=start
/**
 * 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:
    bool preOrdertraverse(TreeNode *t1, TreeNode *t2) {
        // --1. 子树都为空--
        if (!t1 && !t2) return true;
        // --2. 子树有一个不为空--
        if (t1 && !t2 || !t1 && t2) return false;
        // --3. 子树都不为空--
        if (t1->val == t2->val      // 自己是否相等
            && preOrdertraverse(t1->left, t2->right)  // t1左子树和t2右子树是否相等
            && preOrdertraverse(t1->right, t2->left))  // t1右子树和t2左子树是否相等
            return true;
        return false;
    }
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return preOrdertraverse(root->left, root->right);
    }
};
// @lc code=end


查看代码 
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
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
		vector<int> ans;
		queue<TreeNode *> que;
		que.push(root);
		while (!que.empty()) {
			TreeNode *curNode = que.front();
			que.pop();
			if (curNode) {
				ans.push_back(curNode->val);
				que.push(curNode->left);
				que.push(curNode->right);
			}
		}
		return ans;
    }
};

查看代码

代码随想录中的类似题目：102. 二叉树的层序遍历 - 力扣（LeetCode）

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
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > ans;
        if (!pRoot) return ans;
        queue<TreeNode *> que;
        que.push(pRoot);
        while(!que.empty()) {
            int curLevelNum = que.size();   // 当前层的个数
            vector<int> curLevelAns;
            while(curLevelNum--) {
                TreeNode *curNode = que.front();
                que.pop();
                curLevelAns.push_back(curNode->val);
                if (curNode->left) que.push(curNode->left);
                if (curNode->right) que.push(curNode->right);
            }
            ans.push_back(curLevelAns);
        }
        return ans;
    }
};
查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.size() == 0) return false;
        return traverse(sequence, 0, sequence.size() - 1);
    }
private:
    bool traverse(vector<int> sequence, int left, int right) {  // [left, right]
        if (left > right) return true;
        int rootVal = sequence[right];
        // 假设正确的情况下，找到左子树的右边界
        int i;
        for (i = right-1; i >= left && rootVal < sequence[i]; i--);
        // 假设右子树成功，验证左子树
        for (int j = left; j <= i; j++) {
            if (sequence[j] > rootVal) return false;
        }
        // 对于这个root来说没问题，接着找
        return traverse(sequence, left, i)
                && traverse(sequence, i + 1, right - 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
37
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	/*
		思路：中序遍历纪委二叉搜索树的递增序
	*/
    TreeNode* Convert(TreeNode* pRootOfTree) {
		if (!pRootOfTree) return pRootOfTree;	// 特判直接为空，不然whie处报错
		slow = nullptr;	// 一前一后来修改指针
		traverse(pRootOfTree);
        while (pRootOfTree->left) pRootOfTree = pRootOfTree->left;
		return pRootOfTree;
    }
private:
	TreeNode *slow;
	void traverse(TreeNode *node) {
		if (node == nullptr) return;
		traverse(node->left);
		if (slow == nullptr) node->left = nullptr;
		else {
			node->left = slow;
			slow->right = node;
		}
		slow = node;	// 更新slow
		traverse(node->right);
		
	}
};

查看代码

其他样例：

1
{8,4,12,2,6,10,14,1,3,5,7,9,11,13,15}
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
#include <cstdio>
#include <queue>
class Solution {
  public:
    /*
        参考了一下怎么存字符串的
    */
    char* Serialize(TreeNode* root) {
        string ans;
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            TreeNode* curNode = que.front();
            que.pop();
            if (!curNode) ans += "#!";
            else {
                ans += to_string(curNode->val) + '!';     // push_back只能插字符
                que.push(curNode->left);
                que.push(curNode->right);
            }
        }
        // 把样例的搞成 1!2!3!#!#!6!7!#!#!#!#!
        // return (char*)ans.c_str();   // 这么写是错的，因为这个函数结束时，string变量的生命周期结束了，
        // 然后这个指针悬空了

        // char* res = new char(ans.length() + 1);      // tmd，[]写成()，害我改了两个多小时
        char* res = new char[ans.length() + 1];
        strcpy(res, ans.c_str());
        return res;
    }
    TreeNode* Deserialize(char* str) {
        if (str[0] == '\0' || str[0] == '#') return nullptr; // 如果树为空
        int num, curIndex = 0;
        if (!getNum(str, curIndex,
                    num)) return nullptr; // 如果无法获取一个数字，返回nullptr

        TreeNode* root = new TreeNode(num);
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            TreeNode* curNode = que.front();
            que.pop();

            if (getNum(str, curIndex, num)) { // 左子树
                curNode->left = new TreeNode(num);
                que.push(curNode->left);
            }

            if (getNum(str, curIndex, num)) { // 右子树
                curNode->right = new TreeNode(num);
                que.push(curNode->right);
            }
        }
        return root;
    }

  private:
    // 从curIndex处开始取出一个数字，然后返回给num，如果是#则返回false
    bool getNum(char* str, int& curIndex, int& num) {
        if (str[curIndex] == '\0') return false;    // 没有了
        if (str[curIndex] == '#') {
            curIndex += 2;      // 移动到'!'后面
            return false;
        }
        // 说明接下来是数字了
        string n;
        while (str[curIndex] == '+' 
            || str[curIndex] == '-'
            || str[curIndex] >= '0' && str[curIndex] <= '9') {
            n.push_back(str[curIndex]);
            curIndex++;
        }
        curIndex++;      // 移动到'!'后面
        num = stoi(n);  // 转为数字
        return true;
    }
};
查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
		if (!pRoot) return 0;
		return 1 + max(TreeDepth(pRoot->left), TreeDepth(pRoot->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
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    bool IsBalanced_Solution(TreeNode* pRoot) {
        TreeDepth(pRoot);
        return isBalance;
    }
private:
    bool isBalance = true;
    int TreeDepth(TreeNode* node) {
		if (!node) return 0;
        int left = TreeDepth(node->left);
        int right = TreeDepth(node->right);
        if (abs(left - right) > 1) isBalance = false;
		return 1 + max(left, right);
    }
};




贪心思想

查看代码
  • 贪心解法：

这个问题实质上转化为了求函数 (y=(nm)my = \left(\frac{n}{m}\right)^m) 的最大值，其中 (mm) 是变量，(nn) 是常数。解决这个问题的关键是理解，当每段绳子的长度趋近于 (ee)（自然对数的底数，约等于2.71828）时，乘积 (yy) 达到最大。这是因为数学上可以证明，以 (ee) 为底的对数函数的增长速度与其函数值的增长速度相匹配，从而使得乘积最大化。

但在实际操作中，由于绳子长度必须是整数，我们不能直接用 (ee) 来分割绳子。因此，我们需要找到最接近 (e) 的整数，来近似达到最大乘积。最接近 (ee) 的整数是 2 和 3，而由于 (3n33^{\frac{n}{3}}) 的增长速度比 (2n22^{\frac{n}{2}}) 要快，所以选择3作为分割绳子的最优长度。

简而言之，虽然基于公式 (y=(nm)my = \left(\frac{n}{m}\right)^m) 求解时，我们试图找到某个最优的 (mm) 使得 (yy) 最大，但实际的最优策略涉及到将绳子尽可能分为长度为3的段，原因是这样分割接近于使每段长度等于自然对数的底 (ee)，在整数限制下可以获得最大乘积。

ps：如果没有要求整数的话，就变成求极值的问题了

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:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int cutRope(int n) {
        vector<int> little{0, 0, 1, 2};     // 前几个数特殊解决
        if (n < 4) return little[n];
        // 长度为3的个数
        int n3 = n / 3;
        // 长度为2的个数
        int tmp = n % 3;
        int n2;
        if (tmp == 1) {  // 将1补成2
            n3--;
            n2 = 2;
        }
        else n2 = tmp == 2 ? 1 : 0;
        // 乘起来
        int mul = 1;
        while (n3--) mul *= 3;
        while (n2--) mul *= 2;
        return mul;
    }
};
  • 动态规划：

动态规划是解决这类优化问题的一个非常有效的方法，特别是当问题可以被分解成一系列重叠的子问题时。对于这个特定的绳子切割问题，动态规划的思想是从底向上（从最小的子问题开始）计算每个长度的绳子的最大乘积，直到计算出原始长度的绳子的最大乘积为止。

动态规划算法的基本步骤如下：

  1. 定义状态：首先定义一个数组 dp[]，其中 dp[i] 表示长度为 i 的绳子切割后得到的最大乘积。

  2. 初始状态：初始化 dp[1] = 1，虽然按题目要求，绳子至少要切一刀，但这里初始化 dp[1] 是为了后续计算的方便。实际上，由于长度为1的绳子不能切割，这个值在逻辑上是不会被直接使用的。

  3. 状态转移方程：考虑长度为 i 的绳子，我们可以选择第一刀切割的位置 j（1 <= j < i），这样绳子就被分成了长度为 j 和 i-j 的两段。对于这两段绳子，我们可以选择继续切割或不切割，以获得最大乘积，因此 dp[i] 可以通过遍历所有可能的 j 来计算得出：

    dp[i]=max⁡1≤j<i{max⁡(j,dp[j])×max⁡(i−j,dp[i−j])}dp[i] = \max_{1 \leq j < i}\{ \max(j, dp[j]) \times \max(i-j, dp[i-j]) \}

    这里使用 max(j, dp[j]) 是因为我们可以选择不再进一步切割长度为 j 的那段绳子，即直接取 j 本身的长度作为乘积的一部分，或者是切割后的最大乘积 dp[j]。

  4. 计算顺序：从左到右依次计算 dp[2], dp[3], ..., dp[n] 的值。

  5. 结果：最终 dp[n] 就是长度为 n 的绳子切割后得到的最大乘积。

使用动态规划解决这个问题，当绳子长度为8时，得到的最大乘积确实是18。这个结果与题目中给出的示例相匹配，说明动态规划方法是有效的。

动态规划是一个强大的工具，尤其适用于解决那些可以被分解成重叠子问题的优化问题。这个方法通过避免重复计算相同的子问题来提高效率，从而能够高效地解决许多看似复杂的问题。希望这个解释和示例代码能帮助你复习和加深对动态规划的理解！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int cutRope(int n) {
        vector<int> little{0, 0, 1, 2};     // 前几个数特殊解决
        if (n < 4) return little[n];
        // 动态规划
        vector<int> dp(n + 1, 0);
        dp[0] = 0; 
        dp[1] = 1; 
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]));
            }
        }
        return dp[n];
    }
};


问：

我怎么从0得出这个思路?

GPT4：

从零开始构建动态规划（DP）解决方案的思路涉及理解问题的本质、识别重叠子问题、定义状态和决策，并形成状态转移方程。下面是一步步的指南，以帮助你自己从零开始得出动态规划的解决思路：

  1. 理解问题

首先彻底理解问题的要求和限制。在这个例子中，问题是如何将一根绳子切割成多段，使得这些段的长度乘积最大。

  1. 分析子问题

观察问题是否可以分解成更小的子问题。对于绳子切割问题，可以考虑每一次切割后剩下的部分作为一个新的子问题，即如果你已经决定了第一刀切在哪里，那么剩下的部分怎么切割以获得最大乘积就成为了一个新问题。

  1. 定义状态

动态规划的核心在于状态的定义。在这个问题中，状态可以定义为 dp[i]，表示长度为 i 的绳子切割后得到的最大乘积。

  1. 找出状态转移方程

考虑如何从已知的状态得到未知的状态。对于绳子切割问题，如果你考虑第一次切割产生的两段绳子，你可以用已知的最大乘积来计算更长绳子的最大乘积。这可以表述为：

dp[i]=max⁡1≤j<i(max⁡(j,dp[j])×max⁡(i−j,dp[i−j]))dp[i] = \max_{1 \leq j < i} (\max(j, dp[j]) \times \max(i-j, dp[i-j]))

这里考虑了所有可能的第一次切割位置 j，并用已知的最大乘积来计算新的最大乘积。

  1. 初始化基础状态

确定最简单的子问题，并给出它们的解。对于这个问题，最简单的情况就是长度为1的绳子，虽然它不能切割，但我们可以将 dp[1] 设置为1，以便它能在状态转移方程中使用。

  1. 确定遍历顺序

根据状态转移方程的依赖关系确定计算状态的顺序。通常情况下，你需要先计算出所有小问题的解，然后才能解决更大的问题。在本例中，你应该从小到大计算 dp[i]。

  1. 实现并优化

将上述思路转化为代码。一旦完成基本实现，可以考虑是否有空间或时间优化的可能，比如通过避免不必要的计算来优化。

通过遵循这些步骤，即使对动态规划不太熟悉，你也可以逐步构建出解决复杂问题的DP解决方案。随着练习，你将能更快地识别和定义问题的DP结构。


问：

是需要有一个逐步扩展的过程吗，就像i由2到n

GPT4:

是的，动态规划（DP）的核心思想之一就是逐步构建解，从最小的子问题开始，逐渐扩展到整个问题的解。这个“逐步扩展”的过程通常体现在通过迭代计算从基本情况（通常是最小的子问题）开始，一直到目标问题大小的状态值。在绳子切割问题中，这正是通过逐渐增加绳子长度（即逐步扩展 i 从 2 到 n）来实现的。

这个过程背后的逻辑是：

  1. 基础情况：确定一些基础情况（最小的子问题），这些是直接可以知道答案的情况，比如在很多问题中，长度为 0 或 1 的情况。对于绳子切割问题，虽然 dp[1] 实际上不直接用于计算（因为至少要切一刀），但它帮助定义了DP数组的基础。

  2. 状态转移：通过已解决的子问题来解决更大的问题。每次循环迭代，你考虑一个稍大一点的问题（即绳子的长度），并尝试基于已经计算出的较小问题的解来找到当前问题的解。这意味着每一步都建立在之前步骤的基础上。

  3. 逐步扩展：从最基本的情况开始，逐步增加问题的规模，直到达到目标规模（n）。这个过程是通过外层循环实现的，i 从 2 到 n 的遍历就是这个“逐步扩展”的体现。

  4. 利用之前的计算结果：在计算每一步时，都会利用之前计算的结果。这是动态规划节省时间的关键所在，避免了对同一子问题的重复计算。

通过这种方式，动态规划确保了每个子问题只被解决一次，并且每次解决都是建立在之前已解决的子问题之上，最终达到解决整个问题的目的。这种方法不仅提高了效率，而且通过将问题分解为更易于管理的小块，也简化了复杂问题的解决方案。


问：

为什么会设置这样一个dp数组

GPT4：

选择构建一个动态规划（DP）数组是动态规划方法的核心部分，它出于以下几个关键原因：

  1. 存储中间结果

DP方法解决问题的方式是将问题分解成一系列重叠的子问题，然后解决每一个子问题。DP数组用于存储这些子问题的解，确保每个子问题只被计算一次。这样，当一个子问题在求解过程中多次遇到时，我们可以直接从DP数组中取得其结果，而不是重新计算。

  1. 避免重复计算

许多优化问题涉及到大量的重叠子问题。如果不存储这些子问题的解，我们可能会重复解决相同的问题，导致算法的效率极低。DP数组通过记录每个子问题的解，帮助我们避免这种不必要的重复工作，从而显著提高算法的效率。

  1. 实现状态转移

DP数组不仅仅是用来存储结果。它的结构和组织方式还能帮助我们以一种系统的方式实现状态转移。状态转移方程描述了从一个或多个较小子问题的解如何得到当前问题的解。DP数组使我们能够按照一定的顺序（通常是从小到大）计算并更新状态，确保在计算当前状态时，所有需要的前置状态都已经被计算并存储。

  1. 简化问题解决方案

DP数组为我们提供了一种将复杂问题简化为易于管理的小块的方法。通过逐步填充DP数组，我们可以逐渐构建出问题的解决方案。这种方法有助于我们直观地理解问题的结构，以及不同子问题是如何组合在一起解决整个问题的。

  1. 支持反向追踪解决方案

对于某些问题，仅仅知道最优解的值是不够的，我们还可能想知道如何达到这个最优解（例如，切割绳子的最佳方案是什么）。DP数组的结构使得在完成所有计算后，我们可以从最终状态开始反向追踪，找到构建这个最优解的每一步。

总而言之，构建DP数组是实现动态规划方法的基础，它不仅可以帮助我们以高效的方式存储和利用计算结果，而且也是理解和解决问题的关键组成部分。通过DP数组，我们能够将复杂问题分解成小问题，逐步构建解决方案，并最终以高效的方式解决整个问题。

查看代码

要解决这个问题，我们可以采用一种称为“一次遍历”的方法。思路是遍历整个股价数组，记录并更新我们遇到的最低股价，以及在每一天卖出时可能得到的最大利润。我们只需要遍历一次数组，就可以找到买入和卖出的最佳时机，从而获得最大利润。

算法步骤如下：

  1. 初始化两个变量：minPrice（到目前为止的最低股价）和 maxProfit（到目前为止的最大利润）。可以将 minPrice 初始化为正无穷大，maxProfit 初始化为0。
  2. 遍历价格数组 prices：
    • 对于每一天的价格 prices[i]
      • 更新 minPrice 为 min(minPrice, prices[i])，即当前价格和之前最低价格中的较小值。
      • 更新 maxProfit 为 max(maxProfit, prices[i] - minPrice)，即当前价格与最低购买价格之差（如果这个差值大于之前的最大利润，就更新最大利润）。
  3. 遍历结束后，maxProfit 将包含最大利润。如果没有利润可得，这个值将是0。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = 0x7ffffff;
        int MaxProfit = 0;
        for (int i : prices) {
            minPrice = min(minPrice, i);
            MaxProfit = max(MaxProfit, i - minPrice);
        }
        return MaxProfit;
    }
};




二分查找

查看代码

注意：有重复数字

其他样例：

1
[1,0,1,1,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
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int minNumberInRotateArray(vector<int>& nums) {
        // 将旋转数组对半分可以得到一个包含最小元素的新旋转数组，以及一个非递减排序的数组。
        int left = 0, right = nums.size() - 1;
        while (left < right) { // 修改循环条件为left < right
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) { // 如果中间元素小于右侧元素，最小值在左侧
                right = mid;
            } else if (nums[mid] > nums[right]) { // 如果中间元素大于右侧元素，最小值在右侧
                left = mid + 1;
            } else { // 当中间元素等于右侧元素，无法判断最小值位置，右指针左移
                right--;
            }
        }
        return nums[left];
    }
};
查看代码

法一：时间复杂度可能会退化为O(n);

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
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int GetNumberOfK(vector<int>& nums, int k) {
        if (nums.empty()) return 0;
        // 先二分，再左右找
        int left = 0, right = nums.size() - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == k) break; // 找到k，跳出循环
            else if (nums[mid] < k) left = mid + 1; // 调整左边界
            else right = mid - 1; // 调整右边界
        }
        if (left > right) return 0;
        int ans = 1;
        for (int i = mid - 1; i >= 0 && nums[i] == k; i--, ans++);  // 往左
        for (int i = mid + 1; i < nums.size() && nums[i] == k; i++, ans++);  // 往右
        return ans;
    }
};

法二：二分找到左右两边的k就能直接知道数量

如果要使用两次二分查找来分别找到k第一次和最后一次出现的位置，进而计算出k在数组中出现的次数，你可以按照下面的方式实现。这种方法会确保整体的时间复杂度为O(log n)。

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
class Solution {
public:
    int GetNumberOfK(vector<int>& nums, int k) {
        if (nums.empty()) return 0;
        // 找到k第一次出现的位置
        int first = findFirstK(nums, k);
        // 如果k不在数组中，则first返回-1，直接返回0
        if (first == -1) return 0;
        // 找到k最后一次出现的位置
        int last = findLastK(nums, k);
        // 返回k出现的次数，即last-first+1
        return last - first + 1;
    }

    int findFirstK(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < k) {
                left = mid + 1;
            } else if (nums[mid] > k) {
                right = mid - 1;
            } else if (mid == 0 || nums[mid - 1] != k) { // 找到k的第一个位置
                return mid;
            } else {
                right = mid - 1; // 继续在左半边搜索
            }
        }
        return -1; // 没找到k
    }

    int findLastK(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < k) {
                left = mid + 1;
            } else if (nums[mid] > k) {
                right = mid - 1;
            } else if (mid == nums.size() - 1 || nums[mid + 1] != k) { // 找到k的最后一个位置
                return mid;
            } else {
                left = mid + 1; // 继续在右半边搜索
            }
        }
        return -1; // 没找到k
    }
};

这段代码首先定义了findFirstK和findLastK两个函数来分别找到k第一次和最后一次出现的位置。这两个函数通过二分查找实现，区别仅在于在找到一个k后如何决定是返回当前位置还是继续查找。在findFirstK中，如果找到一个k且它是数组的第一个元素或其前一个元素不是k，那么它就是第一个k；在findLastK中，如果找到一个k且它是数组的最后一个元素或其后一个元素不是k，那么它就是最后一个k。这样，通过计算这两个位置的差值加一，就可以得到k在数组中出现的总次数。




分治

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    double Power(double base, int exponent) {
        // O(n)的直接乘就好，下面是时、空复杂度都是O(logn)的
        if (base == 0) return 0;
        if (exponent == 0) return 1;
        if (exponent == 1) return base;
        if (exponent == -1) return 1/base;
        int half = exponent / 2;
        double res = Power(base, half);
        return res * res * Power(base, exponent % 2);
    }
};




搜索

查看代码 
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
class Solution {
public:
    int movingCount(int threshold, int rows, int cols) {
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));  // 是否访问过这个位置
        dfs(0, 0, visited, threshold, rows, cols);
        return cnt;
    }
private:
    // 类似求连通分量
    int cnt;
    int dirX[4] = {-1, 0, 1, 0};   // 上，左，下，右
    int dirY[4] = {0, -1, 0, 1};   // 上，左，下，右
    void dfs(int curX, int curY, vector<vector<bool>> &visited, int threshold, int rows, int cols) {
        // 当前点可走吗？走过了吗
        if (!isLeThreshold(threshold, curX, curY) || visited[curX][curY]) return;
        visited[curX][curY] = true;
        cnt++;
        // 找下一个点
        for (int i = 0; i < 4; i++) {
            int nextX = curX + dirX[i];
            int nextY = curY + dirY[i];
            if (!isOver(nextX, nextY, rows, cols)) {
                dfs(nextX, nextY, visited, threshold, rows, cols);
            }
        }
        
    }
    // 是否越界
    bool isOver(int curX, int curY, int rows, int cols) {
        if (curX > rows - 1 || curX < 0 || curY > cols - 1 || curY < 0) return true;
        return false;
    }
    // 是否小于等于阈值
    bool isLeThreshold(int threshold, int curX, int curY) {
        int sum = 0;
        while(curX) {
            sum += curX % 10;
            curX /= 10;
        }
        while(curY) {
            sum += curY % 10;
            curY /= 10;
        }
        if (sum <= threshold) return true;
        return false;
    }
};
查看代码

其他样例：

1
"qwertyuio"
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
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    vector<string> Permutation(string str) {
        vector<string> ans;
        vector<bool> visited(str.size(), false);
        dfs(str, visited, ans, "", 0);
        return ans;
    }
private:
    void dfs(string &str, vector<bool> &visited, vector<string> &ans, string tmpStr, int depth) {
        if (depth == str.size()) {
            ans.push_back(tmpStr);
            return;
        }
        int cnt[256] = {0};     // 用来处理aab这种样例
        for (int i = 0; i < str.size(); i++) {
            // 找到一个未选的走
            if (visited[i] == false && cnt[str[i]] == 0) {
                cnt[str[i]]++;
                visited[i] = true;
                dfs(str, visited, ans, tmpStr += str[i], depth + 1);
                // 回退
                tmpStr.pop_back();
                visited[i] = false; 
            }
        }
    }
};




排序

查看代码 
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
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArray(vector<int>& array) {
        /*
            思路：类似冒泡排序，出现 偶奇 相邻的情况就交换二者的位置
            时空复杂度正好符合进阶的要求
        */
        for (int i = 0; i < array.size(); i++) {
            int flag = true;
            for (int j = 0; j < array.size() - i - 1; j++) {
                if ((array[j] % 2 == 0) && (array[j + 1] % 2 == 1)) {
                    swap(array[j], array[j + 1]);
                    flag = false;
                }
            }
            if (flag) break;    // 提前终止
        }
        return array;
    }
};
查看代码

其他样例：

1
[39,397,6]
1
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
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
#include <string>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return string字符串
     */
    string PrintMinNumber(vector<int>& numbers) {
        // 如果 S1+S2 < S2+S1，那么应该把 S1 排在前面，否则应该把 S2 排在前面
        sort(numbers.begin(), numbers.end(), compare);
        string ans = "";
        for (int i = 0; i < numbers.size(); i++) 
            ans += to_string(numbers[i]);
        return ans;
    }
private:
    static bool compare(int a, int b) {
        string str_a = to_string(a);
        string str_b = to_string(b);
        return str_a + str_b < str_b + str_a;
    }
};
查看代码

一点思路没有，问GPT了

GPT4：使用归并排序

通过一个具体的例子，比如数组 [1, 20, 6, 4, 5]，来模拟整个归并排序和计算逆序对的过程。

初始数组：[1, 20, 6, 4, 5]

  1. 分割数组直到每个子数组只有一个元素，因为单个元素的数组自然是有序的，不需要比较。

    • 分割成 [1, 20, 6] 和 [4, 5]
    • 再分 [1, 20, 6] 为 [1] 和 [20, 6]；[4, 5] 已经是分不可分。
    • [20, 6] 分为 [20] 和 [6]。

  2. 合并过程中计算逆序对：

    • 合并 [20] 和 [6]，得到 [6, 20]，这里有1个逆序对 (20, 6)。
    • 接下来，我们合并 [1] 和 [6, 20]，得到 [1, 6, 20]，没有增加新的逆序对。
    • 同时，[4, 5] 本身已经是有序的，无需计算。
    • 最后，合并 [1, 6, 20] 和 [4, 5]，当我们将 4 插入到 [1, 6, 20] 中时，4 会和 6, 20 形成逆序对，共2个新的逆序对。当 5 被插入时，它也会与 6, 20 形成逆序对，再增加2个逆序对。

通过上述分解和合并的过程，我们可以详细追踪逆序对的形成：

  • 在合并 [20] 和 [6] 时形成1个逆序对。
  • 在最后一步合并 [1, 6, 20] 和 [4, 5] 时，4 和 5 分别与 [6, 20] 形成2个和2个逆序对，共4个。

所以，对于初始数组 [1, 20, 6, 4, 5]，总共有5个逆序对。

这个过程展示了如何通过分割数组直到它们变得足够小，然后在合并的过程中计算逆序对的数量，同时也保持了数组的有序性。归并排序不仅帮助我们排序，而且在合并过程中很自然地就计算出了逆序对的数量。

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
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int InversePairs(vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        for (int i : nums) {
            printf("%d ", i);
        }
        return cnt;
    }
private:
    int cnt = 0;
    void mergeSort(vector<int>& nums, int left, int right) {    // [left, right]
        if (left < right) {
            int mid = left + (right - left) / 2; 
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }
    void merge(vector<int>& nums, int left, int mid, int right) {
        vector<int> numsLeft;
        vector<int> numsRight;
        // 复制为两个子数组，临时数组
        for (int i = left; i <= mid; numsLeft.push_back(nums[i]), i++);
        for (int i = mid + 1; i <= right; numsRight.push_back(nums[i]), i++);
        int indexL = 0, indexR = 0;
        int i = left;
        for (; i <= right && indexL < numsLeft.size() && indexR < numsRight.size(); i++) {
            if (numsLeft[indexL] <= numsRight[indexR]) {
                nums[i] = numsLeft[indexL];
                indexL++;
            }
            else {
                nums[i] = numsRight[indexR];
                cnt += numsLeft.size() - indexL;    // 计数
                cnt %= 1000000007;      // 取模防止溢出
                indexR++;
            }
        }
        // 剩下的直接放
        for (int j = indexL; j < numsLeft.size(); nums[i++] = numsLeft[j], j++);
        for (int j = indexR; j < numsRight.size(); nums[i++] = numsRight[j], j++);
    }
};




动态规划

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int Fibonacci(int n) {
        if (n == 1 || n == 2) return 1;
        int x1 = 1, x2 = 1;
        int sum = 0;
        n -= 2;
        while (n--) {
            sum = x1 + x2;
            x1 = x2;
            x2 = sum;
        }
        return sum;
    }
};
查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int rectCover(int number) {
        vector<int> dp(number+1, 0);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= number; i++) {
            // 取下一块，取下两块
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[number];
    }
};

可以明显看出来上面就是斐波那契数列，那我们可以将空间复杂度降为O(1)：

小小的区别就是，初值不一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int rectCover(int number) {
        if (number == 0) return 0;
        if (number == 1) return 1;
        if (number == 2) return 2;
        int x1 = 1, x2 = 2;
        int sum = 0;
        number -= 2;
        while (number--) {
            sum = x1 + x2;
            x1 = x2;
            x2 = sum;
        }
        return sum;
    }
};
查看代码

和前两题几乎一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    int jumpFloor(int number) {
        if (number == 1) return 1;
        if (number == 2) return 2;
        int x1 = 1, x2 = 2;
        int sum = 0;
        number -= 2;
        while (number--) {
            sum = x1 + x2;
            x1 = x2;
            x2 = sum;
        }
        return sum;
    }
};
查看代码

动态规划：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    int jumpFloorII(int number) {
        vector<int> dp(number + 1, 1);  // 至少都可以直接跳一次
        for (int i = 2; i <= number; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] += dp[j];
            }
        }
        return dp[number];
    }
};

进阶的要求：

数学推导

跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去…，那么

f(n−1)=f(n−2)+f(n−3)+...+f(0)f(n-1) = f(n-2) + f(n-3) + ... + f(0)

同样，跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去… ，那么

f(n)=f(n−1)+f(n−2)+...+f(0)f(n) = f(n-1) + f(n-2) + ... + f(0)

综上可得

f(n)−f(n−1)=f(n−1)f(n) - f(n-1) = f(n-1)

即

f(n)=2∗f(n−1)f(n) = 2*f(n-1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cmath>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    int jumpFloorII(int number) {
        return pow(2, number - 1);
    }
};
查看代码

样例 1

输入：

1
2
3
4
5
6
7
6 6
200 300 400 500 600 700
800 900 100 200 300 400
500 600 700 800 900 1000
600 700 800 900 1000 200
700 800 900 1000 200 300
800 900 1000 200 300 400

预期输出：6800

样例 2

输入：

1
2
3
4
5
6
7
6 6
500 600 700 800 900 1000
400 500 600 700 800 900
300 400 500 600 700 800
200 300 400 500 600 700
100 200 300 400 500 600
100 200 300 400 500 600

预期输出：8100

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
/*
    思路：动态规划
    present[][]表示礼物数组
    dp[][]记录礼物最大值
    算法dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + present[i][j];
*/ 
#include <iostream>
#include <vector>
#include <algorithm>    // max()
using namespace std;

class Solution {
public:
    int getMost(vector<vector<int>> &present, int rows, int cols) {
        vector<vector<int>> dp(rows, vector<int>(cols, 0));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i - 1 >= 0 && j - 1 >= 0) 
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + present[i][j];
                else if (i - 1 >= 0 && j - 1 < 0) 
                    dp[i][j] = dp[i - 1][j] + present[i][j];
                else if (i - 1 < 0 && j - 1 >= 0)
                    dp[i][j] = dp[i][j - 1] + present[i][j];
                else
                    dp[i][j] = present[i][j];
            }
        }
        return dp[rows - 1][cols - 1];
    }
};

int main() {
    int rows, cols;
    scanf("%d %d", &rows, &cols);
    vector<vector<int>> present(rows, vector<int>(cols));
    for (int i = 0; i < rows; i++) 
        for (int j = 0; j < cols; j++)
            scanf("%d", &present[i][j]);
    Solution solution;
    printf("%d", solution.getMost(present, rows, cols));
    return 0;
}
// 64 位输出请用 printf(\"%lld\")




数学

查看代码 
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
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        /*
            思路：计数cnt，与当前字符相同++，不同-- 
            但是这样只能找到一个候选的，因为有可能不存在超过半数的，但是这题保证有解了
        */
        struct {
            int val;
            int cnt;
        } ans;
        ans.val = numbers[0];
        ans.cnt = 1;
        for (int i = 1; i < numbers.size(); i++) {
            if (ans.val == numbers[i]) ans.cnt++;
            else {
                ans.cnt--;
                if (ans.cnt < 0) {
                    ans.val = numbers[i];
                    ans.cnt = 1;
                }
            }
        }
        return ans.val;
    }
};




位运算

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int NumberOf1(int n) {
        // 根据题意，int 32bit的情况下
        int cnt = 0;
        unsigned int tmp = 1;
        for (int i = 0; i < 32; i++, n >>= 1) {
            if ((n & tmp) == 1) cnt++;
        }
        return cnt;
    }
};




其它

查看代码

感觉这题和这个网站作者想要我们练习的不一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 最大位数
     * @return int整型vector
     */
    vector<int> printNumbers(int n) {
        vector<int> ans;
        n = pow(10, n) - 1;
        for (int i = 1; i <= n; ans.push_back(i), i++);
        return ans;
    }
};
查看代码

看题解析写的

具体做法：

  • step 1：通过对每个区间起点数字的计算，按照上述规律求得该区间的位数，n不断减去它前面区间的位数，定位到属于它的区间。
  • step 2：通过除以位数定位n在哪个数字上，用字符串形式表示。
  • step 3：通过在字符串上位置对几位数取模定位目标数字。

图示：

alt

用例输入 :

1
1000000000

预期输出:

1
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
#include <cstdio>
#include <string>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int findNthDigit(int n) {
        vector<int> little{0,1,2,3,4,5,6,7,8,9};
        if (n < 10) return little[n];
        
        long long level = 1; // 数位长度
        long long count = 9; // 当前数位长度下的数字总数
        // 确定 n 所在的数字长度区间
        while (n > level * count) {
            n -= level * count;
            level++;
            count *= 10;
        }
        
        int index = (n - 1) / level; // 计算在当前长度区间的第几个数字
        int offset = (n - 1) % level; // 计算在该数字中的位置
        long long start = pow(10, level - 1); // 当前长度区间的起始数字
        long long num = start + index; // 目标数字
        
        string numStr = to_string(num);
        return numStr[offset] - '0'; // 提取并返回正确的数字
    }
};