学一本好书《剑指offer》

数组中重复的数字 -> （中文版） https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

哈希思路，直接记录，找到直接跳。

unordered_map<int, int> mp; 是 C++ 中定义一个无序映射（哈希表）的声明，其中 int 是键类型，int 是值类型。这个数据结构会将整数键映射到整数值。

1. 数据结构说明

  • unordered_map 是 C++ 标准库提供的一种基于哈希表实现的关联容器。它允许我们通过键快速查找与之相关联的值。
  • 在这个声明中：
    • int 是键类型，表示键是整数。
    • int 是值类型，表示与每个键相关联的值也是整数。

2. 时间复杂度

  • 插入: 在平均情况下，插入键值对的时间复杂度为 O(1)，因为哈希表使用哈希函数来将键映射到对应的槽（bucket）。
  • 查找: 在平均情况下，通过键查找对应的值也是 O(1)，因为哈希表可以在常数时间内定位到目标槽。
  • 删除: 同样，删除键值对的平均时间复杂度为 O(1)。

最坏情况： 在最坏情况下，所有的键都可能映射到同一个槽（哈希冲突的极端情况），使得时间复杂度退化为 O(n)，其中 n 是容器中的元素个数。但是，由于哈希函数设计合理，最坏情况通常较少发生。

3. 有序性

  • unordered_map 是无序的映射，因此元素的存储顺序与插入顺序无关，也不能保证遍历时的顺序。
  • 如果需要按照插入顺序或键的顺序进行遍历，可以使用 map（有序映射）或 std::unordered_map 结合其他数据结构。

4. 使用场景

unordered_map<int, int> 适用于以下场景： - 需要高效地进行键值对的插入、查找、删除操作，且不关心键值对的顺序。 - 例如：统计频率、元素计数、唯一标识符的映射等。

5. 哈希表的基本原理

  • unordered_map 通过哈希函数将键映射到哈希表的槽中，不同的键可能映射到相同的槽（这称为哈希冲突）。
  • 当发生冲突时，unordered_map 会使用一些解决冲突的策略（如链表法、开放寻址法等）来确保多个键可以存储在同一个槽中。

6. 内存使用

unordered_map 的内存使用量通常比 map 要多，因为它会预留足够的槽位来减少哈希冲突，通常需要额外的空间来存储哈希表的结构和元素之间的链表或其他冲突处理机制。

7. 总结

unordered_map<int, int> 是一个高效的、基于哈希表的无序映射，适用于频繁的查找、插入、删除操作，而不需要元素按顺序存储。它的平均时间复杂度为 O(1)，在很多需要键值对映射的场景中非常适合使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findRepeatDocument(vector<int>& documents) {
        unordered_map<int,int>mp;
        int ans;
        for(auto x:documents)
        {
            if(mp[x])
            {
                ans=x;
                break;
            }
            else
            {
                mp[x]=1;
            }
        }
        return ans;
    }
};

也可以直接最后return -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findRepeatDocument(vector<int>& documents) {
        unordered_map<int, bool> map;
        for(int doc : documents) 
        {
            if(map[doc]) 
                return doc;
            map[doc] = true;
        }
        return -1;
    }
};

二维数组中的查找 ->LCR 121. 寻找目标值 - 二维数组 - 力扣（LeetCode）

直接暴力做法。

在第一个 for 循环中，auto 被推导为 vector<int> 类型，因为 plants 是 vector<vector<int>>。

在第二个 for 循环中，auto 被推导为 int 类型，因为 x 是 vector<int>，所以 j 是其中的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {
        for(auto x:plants)
        {
            for(auto j:x)
            {
                if(j==target)
                {
				return true;
                }
            }
        }
return false;
    }
};

由于每一行是有序的，因此天然满足二分的条件，因此可以考虑直接对每一行进行二分。

有一些坑点：就是需要判断是否存在空行，不然二分会出现边界错误。

lower_bound 函数原型：

1
2
template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
  • first 和 last：指向要搜索的范围 [first, last) 的迭代器，通常是容器的 begin() 和 end()。
  • value：我们要查找的目标值。
  • 返回值：返回指向第一个不小于目标值的元素的迭代器。如果没有找到目标值，返回 last。
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:
    bool findTargetIn2DPlants(vector<vector<int>> &plants, int target)
    {
        int n = plants.size();
        // 检查 plants 是否为空，或者是否有空行
        if (n == 0 || plants[0].size() == 0)
        {
            return false;
        }
        int m = plants[0].size();
        for (int i = 0; i < n; i++)
        {
            // 确保每行不为空
            if (plants[i].size() == 0)
                continue;
            int x = lower_bound(plants[i].begin(), plants[i].end(), target) - plants[i].begin();
            if (x < plants[i].size() && plants[i][x] == target)
            {
                return true;
            }
        }
        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
class Solution
{
public:
    bool findTargetIn2DPlants(vector<vector<int>> &plants, int target)
    {
        int n = plants.size()-1;
        int m=0;
        while(n>=0&&m<plants[0].size())
        {
            if(plants[n][m]>target)
            {
                n--;
            }
            else if(plants[n][m]<target)
            {
                m++;
            }
            else
            {
                return true;
            }
        }
        return false;
    }
};

替换空格 -> （中文版） https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

直接暴力，注意传引用。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string pathEncryption(string path) {
for(auto &c:path)
{
    if(c=='.')
    {
        c=' ';
    }
}
return path;
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string pathEncryption(string path) 
    {
        for(int i=0;i<path.length();i++)
        {
            if(path[i]=='.') path[i]=' ';
        }
        return path;
    }
};

从尾到头打印链表 -> （中文版） https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

直接模拟，似乎想不出其他办法了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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:
    vector<int> reverseBookList(ListNode* head) {
vector<int>ans;
while(head!=nullptr)
{
    ans.push_back(head->val);
    head=head->next;
}
reverse(ans.begin(),ans.end());
return ans;
    }
};

补充一下知识点

reverse() 是 C++ 标准库中的一个函数，用于反转容器或数组中元素的顺序。它位于 #include <algorithm> 头文件中，属于 STL（标准模板库）的算法部分。下面我们深入剖析这个函数的实现逻辑和它的使用场景。

reverse() 函数原型：

1
2
template< class BidirectionalIt >
void reverse( BidirectionalIt first, BidirectionalIt last );
  • first: 指向反转范围的起始迭代器。
  • last: 指向反转范围的结尾迭代器（不包括 last 所指的元素）。
  • Bidirectional Iterator: reverse() 需要双向迭代器 (BidirectionalIt)，这意味着该函数可以在向前和向后的方向上迭代，这正是双向迭代器的特性。常见的容器如 vector, deque, list 提供了双向迭代器支持。

reverse() 的工作原理：

reverse() 的主要作用是将 [first, last) 范围内的元素顺序反转。它的实现基于双向迭代器的特性，通过两端向中间逐步交换元素，直到所有元素的顺序被颠倒。

实现思路： 1. 从两个迭代器开始，一个从 first 位置指向开头，一个从 last 位置指向末尾。 2. 逐步交换这两个位置的元素，直到两个迭代器相遇或交错。 3. 当两个迭代器相遇或交错时，说明所有元素已经完成交换，反转结束。

可能的伪代码实现（简化）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last) {
    // 因为 last 是开区间，我们需要向前移动一位
    if (first == last || first == --last) return;
    
    // 不断交换 first 和 last 指向的元素，直到两者相遇或交错
    while (first < last) {
        // 交换 first 和 last 指向的元素
        std::iter_swap(first, last);

        // 分别移动 first 和 last
        ++first;
        --last;
    }
}

详细解析：

  1. 迭代器类型检查：函数模板要求 BidirectionalIterator，确保传入的迭代器能够双向遍历（如 vector 的迭代器）。
  2. 边界检查：if (first == last || first == --last)，用于检查 first 和 last 是否指向相同位置，或者 last 是否已经是前一个位置。这样可以避免不必要的交换和处理边界情况（比如只有一个元素的情况下无需反转）。
  3. 交换元素：std::iter_swap(first, last) 用于交换两个迭代器所指向的元素。这是一个泛型算法，适用于所有支持迭代器的容器。
  4. 移动迭代器：每次交换后，将 first 向前移动（++first），last 向后移动（--last），直到两个迭代器交错或相遇。

举例：

假设有一个 vector，内容为 {1, 2, 3, 4, 5}：

1
2
std::vector<int> ans = {1, 2, 3, 4, 5};
reverse(ans.begin(), ans.end());

反转后的结果是 {5, 4, 3, 2, 1}。反转过程如下： 1. 交换 ans[0] 和 ans[4]，得到 {5, 2, 3, 4, 1}。 2. 交换 ans[1] 和 ans[3]，得到 {5, 4, 3, 2, 1}。 3. 迭代器相遇，反转完成。

优点：

  • 泛型性：reverse() 能够处理任何提供双向迭代器的容器（如 vector, deque, list）。
  • 高效：时间复杂度是 O(n)，其中 n 是反转范围内的元素数量，空间复杂度是 O(1)，因为元素的交换是原地操作，没有额外的内存消耗。

reverse() 的其他特性：

  • reverse() 不仅适用于 STL 容器，如 vector，它同样可以应用于数组，双向链表等，只要其迭代器满足双向迭代器要求。

重建二叉树 -> LCR 124. 推理二叉树 - 力扣（LeetCode）

前序遍历 (Preorder Traversal)：根节点 -> 左子树 -> 右子树

中序遍历 (Inorder Traversal)：左子树 -> 根节点 -> 右子树

参数说明：

  • pre_root：当前递归中，前序遍历中根节点的位置。

  • in_left 和 in_right：当前递归中，中序遍历中需要考虑的子数组边界。

  • Base Case：

1
2
3
if (in_left > in_right) {
    return NULL;
}
  • 当中序遍历的左边界大于右边界时，说明当前子树为空，返回 NULL。

运行示例

输入：

  • 前序遍历：[3,9,20,15,7]
  • 中序遍历：[9,3,15,20,7]

步骤：

  1. 前序遍历中第一个元素 3 为根节点。在中序遍历中，3 的位置为索引 1，左边为左子树 [9]，右边为右子树 [15,20,7]。
  2. 左子树的根节点为前序遍历的第二个元素 9，此时没有左子树和右子树。
  3. 右子树的根节点为前序遍历的第三个元素 20，在中序遍历中，20 的位置为索引 3，左边为左子树 [15]，右边为右子树 [7]。
  4. 按照同样的逻辑继续递归，最终构建出完整的二叉树。
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
/**
 * 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) {}
 * };
 */
unordered_map<int,int>mp;
class Solution {
public:
    TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
    for(int i=0;i<inorder.size();i++)
    {
        mp[inorder[i]]=i;
    }
    return build(preorder,inorder,0,0,inorder.size()-1);
    }
    TreeNode *build(vector<int>&preorder,vector<int>&inorder,int pre_root,int in_left,int in_right)
{
    if(in_left>in_right)
    {
        return NULL;
    }
    TreeNode * root=new TreeNode(preorder[pre_root]);
    int in_root=mp[preorder[pre_root]];
    root->left=build(preorder,inorder,pre_root+1,in_left,in_root-1);
    root->right=build(preorder,inorder,pre_root+in_root-in_left+1,in_root+1,in_right);
    return root;
}
};

用两个栈实现队列 -> https://leetcode.com/problems/implement-queue-using-stacks/

记录一个入栈，一个出栈，一个存取末尾，一个存取开头部分。

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
class MyQueue {
private:
    stack<int> inStack, outStack;

    void in2out() {
        while (!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }

public:
    MyQueue() {}

    void push(int x) {
        inStack.push(x);
    }

    int pop() {
        if (outStack.empty()) {
            in2out();
        }
        int x = outStack.top();
        outStack.pop();
        return x;
    }

    int peek() {
        if (outStack.empty()) {
            in2out();
        }
        return outStack.top();
    }

    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

补充一下栈知识点

stack<int> 是 C++ 标准模板库（STL）中的一个容器适配器，提供了 后进先出（LIFO, Last In First Out）的数据结构。虽然 stack 本身不是一个独立的容器，而是通过现有容器（如 deque、vector、list 等）来实现，但它封装了这些容器的底层实现，以提供简化的栈操作接口。

stack<int> 的定义与使用

stack<int> 的实现是基于模板类的栈容器适配器。它常用于存储并按顺序处理 int 类型的元素。下面是 stack<int> 的常用接口和简单使用方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <stack>

int main() {
    std::stack<int> s; // 定义一个存储 int 类型的栈

    s.push(10);    // 将元素 10 压入栈中
    s.push(20);    // 将元素 20 压入栈中
    s.push(30);    // 将元素 30 压入栈中

    std::cout << "栈顶元素: " << s.top() << std::endl;  // 输出栈顶元素 30

    s.pop();   // 弹出栈顶元素
    std::cout << "弹出后栈顶元素: " << s.top() << std::endl;  // 输出栈顶元素 20

    std::cout << "栈的大小: " << s.size() << std::endl; // 输出栈大小

    return 0;
}

栈的基本操作：

  1. push()：将一个元素压入栈顶。
  2. pop()：移除栈顶元素（并不返回该元素，只是删除它）。
  3. top()：获取栈顶元素（不移除）。
  4. empty()：检查栈是否为空，返回布尔值。
  5. size()：返回栈中元素的个数。

stack<int> 的底层实现

stack<int> 是通过模板类实现的，接受任意类型的元素类型。它的底层实现是基于一个已有的序列容器，如 deque、vector 或 list，默认使用的是 deque。STL 通过容器适配器（adapter）的概念，将 stack 的操作映射到底层容器的操作上。

栈的定义：

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
template <class T, class Container = std::deque<T>>
class stack {
public:
    // 类型定义
    typedef typename Container::value_type value_type;
    typedef typename Container::size_type size_type;
    typedef typename Container::reference reference;
    typedef typename Container::const_reference const_reference;

protected:
    // 底层容器对象
    Container c;

public:
    // 构造函数
    explicit stack(const Container& cont = Container()) : c(cont) {}

    // 栈操作函数
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    reference top() { return c.back(); }
    const_reference top() const { return c.back(); }
    void push(const value_type& value) { c.push_back(value); }
    void pop() { c.pop_back(); }
};

1. 容器适配器：

stack 是一个 容器适配器，默认使用 deque 作为底层容器。它封装了底层容器的操作，使得用户只看到栈的操作接口，而不用关心底层容器的具体实现。你可以将 deque 替换为 vector 或 list，因为这些容器也提供了必要的接口（如 push_back()、pop_back()、back() 等）。

2. 底层容器的接口映射：

  • push() 操作是通过调用底层容器的 push_back() 来实现的，即将元素插入到容器的末尾。
  • pop() 操作是通过调用底层容器的 pop_back() 来实现的，即移除容器末尾的元素。
  • top() 操作是通过调用底层容器的 back() 来访问末尾的元素。

3. 重要的成员类型：

  • value_type：表示栈中存储的元素类型，即 int。
  • size_type：表示栈中元素个数的类型，通常是 size_t。
  • reference 和 const_reference：分别表示元素的引用和常量引用类型。

4. 默认构造函数：

stack 的构造函数允许你传递一个容器类型（如 deque 或 vector）作为参数。如果不提供，则默认使用 deque 作为底层容器。

deque 作为 stack 的默认容器

虽然 stack 可以使用任何支持双端操作的容器，但默认使用 deque 是因为它既支持从尾部高效地添加和删除元素（符合栈的操作需求），又能在常数时间内获取栈顶元素。

deque （双端队列）是一种双向队列，既支持快速的前后端元素插入和删除，也支持随机访问。相比 vector，deque 在某些情况下更适合栈，因为 vector 的末尾添加操作如果触发容量重新分配会比 deque 慢一些。

stack<int> 的工作原理分析

当你执行 stack<int> s; 时，C++ 会为栈对象 s 构建一个默认的 deque<int> 对象，作为其底层存储容器。然后，stack 的操作会依次调用 deque 的相应操作，如：

  • s.push(10)：会调用底层 deque<int> 的 push_back() 方法，将 10 插入到 deque 的末尾。
  • s.pop()：会调用 deque<int> 的 pop_back() 方法，移除 deque 的末尾元素。
  • s.top()：会调用 deque<int> 的 back() 方法，返回 deque 的末尾元素的引用。

栈的时间复杂度

  • push()：时间复杂度为 O(1)，因为它只是将元素添加到容器的末尾。
  • pop()：时间复杂度为 O(1)，因为它只是从容器末尾移除元素。
  • top()：时间复杂度为 O(1)，因为它直接访问末尾的元素。
  • size()：时间复杂度为 O(1)，因为底层容器提供了常数时间的大小查询操作。

斐波那契数列/青蛙跳台阶 -> https://leetcode.com/problems/fibonacci-number/

状态转移方程dp[i]=(dp[i-1]+dp[i-2])%mod

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int mod=1e9+7;
class Solution {
public:
    int trainWays(int num) {
vector<long long>dp(num+2);
dp[0]=1;
dp[1]=1;
for(int i=2;i<=num;i++)
{
    dp[i]=(dp[i-1]+dp[i-2])%mod;
}
return dp[num];
    }
};

也可以用更快的矩阵加速递推，不过面试应该不会涉及，就留给读者思考矩阵快速幂的做法了。

旋转数组的最小数字 -> https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

直接暴力。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int findMin(vector<int>& nums) {
int minn=1e9;
        for(auto x:nums)
{
minn=min(minn,x);
}
        return minn;
    }
};

也可以直接进行二分。

题目的图一定是这样的。

image-20240913103507738

如果nums[mid]<nums[r]，那么最小值一定在mid左侧，不然一定在mid右侧，或者等于mid。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findMin(vector<int>& nums) {
int l=-1;
int r=nums.size()-1;
while(l+1<r)
{
    int mid=l+(r-l)/2;
    if(nums[mid]<nums[r])
    {
        r=mid;
    }
    else
    {
        l=mid;
    }
}
return nums[r];
    }
};

√矩阵中的路径 -> LCR 129. 字母迷宫 - 力扣（LeetCode）

进行dfs。

传参：传地图，遍历到横坐标哪里了，纵坐标哪里了，匹配字符串哪里了，字符串。

什么时候开始搜索？

第一个字符串匹配时。

搜索之前要注意什么？

注意判断边界，注意判断答案合法情况。

搜索之后要注意什么？

注意回溯。

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
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n;
int m;
int vis[1000][1000]; 
bool dfs(vector<vector<char>> &grid, int i, int j, int now, string target)
{ 
    if (i < 0 || i >= n || j < 0 || j >= m)
    {
        return false;
    }
    if (vis[i][j] == 1)
    {
        return false;
    }
    if (grid[i][j] == target[now])
    {   
        if (now == target.size() - 1)
        {
            return true;
        }
        vis[i][j] = 1; 
        for (int k = 0; k <= 3; k++)
        {
            if (dfs(grid, i + dx[k], j + dy[k], now + 1, target))
            {
                return true;
            }
        }
        vis[i][j] = 0; 
    }
    return false;
}

class Solution
{
public:
    bool wordPuzzle(vector<vector<char>> &grid, string target)
    {
        n = grid.size();
        m = grid[0].size();        
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {                
                if (grid[i][j] == target[0])
                {
                    memset(vis, 0, sizeof(vis));                   
                    if (dfs(grid, i, j, 0, target))
                    {
                        return true;
                    }
                }
            }
        }
        return false; 
    }
};

机器人的运动范围 ->（中文版）https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

直接使用超好写的bfs即可。

bfs用队列实现。

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
int cnt_;
bool check(int i,int j)
{
    int ans=0;
    while(i)
    {
        ans+=i%10;
        i/=10;
    }
    while(j)
    {
        ans+=j%10;
        j/=10;
    }
    return ans<=cnt_;
}
class Solution {
public:
    int wardrobeFinishing(int m, int n, int cnt) {
        cnt_=cnt;
    queue<pair<int,int> >q;
    q.push({0,0});
    int ans=1;
    int dx[]={0,1};
    int dy[]={1,0};
    map<pair<int,int>,bool>vis;
    while(!q.empty())
    {
        pair<int,int>now=q.front();
        q.pop();
        int x=now.first;
        int y=now.second;
        for(int i=0;i<2;i++)
        {
            int kx=x+dx[i];
            int ky=y+dy[i];
            if(kx>m-1||ky>n-1||!check(kx,ky)||vis[{kx,ky}])
            {
                continue;
            }
            vis[{kx,ky}]=1;
            q.push({kx,ky});
            ans++;
        }
    }
return ans;


    }
};

剪绳子（dp） -> https://leetcode-cn.com/problems/integer-break/）

定义dp[i]为将i拆分为k个数字的最大乘积。

状态转移时候有两种情况。

一种是不拆分i-j

一种是拆分i-j

也就是dp[i]=max((i-j)*j,dp[i-j]*j)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int integerBreak(int n) {
vector<int>dp(n+1);
dp[1]=0;
dp[0]=0;
dp[2]=1;
for(int i=3;i<=n;i++)
{
    for(int j=1;j<i;j++)
    {
        dp[i]=max(dp[i],max(dp[i-j]*j,(i-j)*j));
    }
}
return dp[n];
    }
};

一种数学做法：不加证明的给出拆分为尽可能多的3会是最优秀的。

这里证明需要用到极值点偏移，因此就留给数学大佬证明了。

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:
    int integerBreak(int n) {
if(n<2)
{
    return 0;
}
if(n==2)
{
    return 1;
}
if(n==3)
{
    return 2;
}
int ans=1;
while(n>4)
{
ans*=3;
n-=3;
}
if(n)
{
    ans*=n;
}
return ans;
    }
};

√二进制中1的个数 ->191. 位1的个数 - 力扣（LeetCode）

第一种方法：直接暴力做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution 
{
public:
    int hammingWeight(uint32_t n) 
    {
        int ret = 0;
        for (int i = 0; i < 32; i++) 
        {
            if (n & (1 << i)) 
            {
                ret++;
            }
        }
        return ret;
    }
};

看题解得到一种更加优雅的做法。

每次去掉最后一个1的做法：n&=(n-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution 
{
public:
    int hammingWeight(uint32_t n) 
    {
        int ret = 0;
        while(n)
        {
            n&=(n-1);
            ret++;
        }
        return ret;
    }
};

数值的整数次方（溢出） -> https://leetcode.com/problems/powx-n/

快速幂做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using ll=long long;
double quick_pow(double x,ll n)
{
    double ans=1.0000;
    while(n)
    {
        if(n&1)
        {
            ans=ans*x;
        }
        x=x*x;
        n>>=1;
    }
    return ans;
}
class Solution {
public:
    double myPow(double x, int n) {
        ll N=n;
return N>=0?quick_pow(x,N):1.0/quick_pow(x,-N);
    }
};

LCR 135. 报数 - 力扣（LeetCode）

打个暴力。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> countNumbers(int n) {
        if(n <= 0) return vector<int>(0);
        vector<int> res;
        int num = 1;
        for(int i=0; i<n; ++i)
            num *= 10; // 比如 n=3，num就是1000
        for(int i=1; i<num; ++i) res.push_back(i);
        return res;
    }
};

237. 删除链表中的节点 - 力扣（LeetCode）

及其简单的做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
     node->val=node->next->val;
     node->next=node->next->next;

    }
};

10. 正则表达式匹配 - 力扣（LeetCode）

定义dp[i][j]为字符串s前i个与字符串p的前j个能否匹配

dp[i][j]代表字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配

当 p[j - 1] = '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true ：

dp[i][j - 2]： 即将字符组合 p[j - 2] * 看作出现 0 次时，能否匹配。 dp[i - 1][j] 且 s[i - 1] = p[j - 2]: 即让字符 p[j - 2] 多出现 1 次时，能否匹配。 dp[i - 1][j] 且 p[j - 2] = '.': 即让字符 '.' 多出现 1 次时，能否匹配。 当 p[j - 1] != '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true ：

dp[i - 1][j - 1] 且 s[i - 1] = p[j - 1]： 即让字符 p[j - 1] 多出现一次时，能否匹配。 dp[i - 1][j - 1] 且 p[j - 1] = '.'： 即将字符 . 看作字符 s[i - 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
42
43
44
45
46
47
48
49
class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.size()+1;
        int n=p.size()+1;
        vector<vector<bool>>dp(m,vector<bool>(n,false));
        dp[0][0]=1;
        for(int j=2;j<n;j++)
        {
            if(p[j-1]=='*')
            {
                dp[0][j]=dp[0][j-2];
            }
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(p[j-1]=='*')
                {
                    if(dp[i][j-2])
                    {
                        dp[i][j]=1;
                    }
                    else if(dp[i-1][j]&&s[i-1]==p[j-2])
                    {
                        dp[i][j]=1;
                    }
                    else if(dp[i-1][j]&&p[j-2]=='.')
                    {
                        dp[i][j]=1;
                    }
                }
                else
                {
                    if(dp[i-1][j-1]&&s[i-1]==p[j-1])
                    {
                        dp[i][j]=1;
                    }
                    else if(dp[i-1][j-1]&&p[j-1]=='.')
                    {
                        dp[i][j]=1;
                    }
                }
            }
        }
            return dp[m-1][n-1];
    }
};

LCR 138. 有效数字 - 力扣（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
39
40
41
42
43
44
45
46
47
class Solution {
public:
    bool validNumber(string s) {
        //去掉首尾空格
        if(s==" ")
        {
            return false;
        }
        int i = 0;
        while (i < s.size() && s[i] == ' ')
            i++;
        if(i==s.size())
        {
            return false;
        }
        s = s.substr(i);
        while (s.back() == ' ')
            s.pop_back();
        bool numFlag = false;
        bool dotFlag = false;
        bool eFlag = false;
        for (int i = 0; i < s.size(); i++) {
            // 判定为数字，则标记numFlag
            if (isdigit(s[i])) {
                numFlag = true;
            }
            // 判定为'.'需要没出现过'.'并且没出现过'e'
            else if (s[i] == '.' && !dotFlag && !eFlag) {
                dotFlag = true;
            }
            // 判定为'e'，需要没出现过'e'，并且出现过数字
            else if ((s[i] == 'e' || s[i] == 'E') && !eFlag && numFlag) {
                eFlag = true;
                numFlag = false; // 'e'后面必须跟着一个整数，所以出现'e'之后就标志为false
            }
            // 判定为'+''-'符号，只能出现在第一位或者紧接'e'后面
            else if ((s[i] == '+' || s[i] == '-') && (i == 0 || s[i - 1] == 'e' || s[i - 1] == 'E')) {
                
            } 
            // 其他情况，都是非法的
            else {
                return false;
            }
        }
        return numFlag;
    }
};

LCR 139. 训练计划 I - 力扣（LeetCode）

经典双指针加上特判。

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:
    vector<int> trainingPlan(vector<int>& actions) {
int l=0;
int r=actions.size()-1;
while(l<r)
{
    while(l<r&&actions[l]&1)
    {
        l++;
    }
    while(r>l&&!(actions[r]&1))
    {
r--;
    }
    if(l<r)
    {
        swap(actions[l],actions[r]);
    }
}
return actions;
    }
};

面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

暴力模拟，超百分百。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
vector<int>ans;
int cnt=0;
while(head!=nullptr)
{
    ans.push_back(head->val);
    cnt++;
    head=head->next;
}
return ans[cnt-k];
    }
};

LCR 022. 环形链表 II - 力扣（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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*>q;
        while(head!=nullptr)
        {
        if(q.count(head))
        {
            return head;
        }
        q.insert(head);
        head=head->next;
        }
return NULL;
    }
};

回归正解，也就是快慢指针。

解法：快指针一次走两格，慢指针一次走一格，直到二者相遇。

接下来答案指针从头部出发，与慢指针一起动，直到重合即是。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
       //定义一个快指针，一个慢指针，一个最后的答案指针
       ListNode *fast=head;
       ListNode *slow=head;
       ListNode *ans=head;
        while(fast!=nullptr)
        {
            if(fast->next==nullptr||fast->next->next==nullptr)
            {
                return nullptr;
            }
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast)
            {
                while(slow!=ans)
                {
                    slow=slow->next;
                    ans=ans->next;
                }
                return ans;
            }
        }
        return NULL;
    }
};

206. 反转链表 - 力扣（LeetCode）

简单题目，定义三个指针，每次变换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};


21. 合并两个有序链表 - 力扣（LeetCode）

十分简单的比较和连接链表。

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:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dum = new ListNode(0);
        ListNode* cur = dum;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                cur->next = list1;
                list1 = list1->next;
            }
            else {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 != nullptr ? list1 : list2;
        return dum->next;
    }
};


LCR 143. 子结构判断 - 力扣（LeetCode）

递归判断。

B为A的子结构有3种情况,满足任意一种即可:

  • B的子结构起点为A的根节点,此时结果为recur(A,B)
  • B的子结构起点隐藏在A的左子树中,而不是直接为A的根节点,此时结果为isSubStructure(A.left, B)
  • B的子结构起点隐藏在A的右子树中,此时结果为isSubStructure(A.right, B)
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
bool recur(TreeNode *A,TreeNode *B)
{
    if(B==nullptr)
    {
        return true;
    }
    if(A==nullptr||A->val!=B->val)
    {
        return false;
    }
    return recur(A->left,B->left)&&recur(A->right,B->right);
}
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
if(A==nullptr||B==nullptr)
{
    return false;
}
return recur(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B);

    }
};

LCR 144. 翻转二叉树 - 力扣（LeetCode）

递归的做，注意要先保存左子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root==nullptr)
        {
            return nullptr;
        }
        TreeNode *temp=root->left;
        root->left=mirrorTree(root->right);
        root->right=mirrorTree(temp);
        return root;
    }
};

101. 对称二叉树 - 力扣（LeetCode）

也是直接递归的进行处理，判断根是否为空，然后判断左子树右子树是否对称。

左子树的左子树和右子树的右子树是否对称。

左子树的右子树和右子树的左子树是否对称。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return root == nullptr || recur(root->left, root->right);
    }
private:
    bool recur(TreeNode* L, TreeNode* R) {
        if (L == nullptr && R == nullptr) return true;
        if (L == nullptr || R == nullptr || L->val != R->val) return false;
        return recur(L->left, R->right) && recur(L->right, R->left);
    }
};

LCR 146. 螺旋遍历二维数组 - 力扣（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
39
40
41
42
43
class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array) {
//记录上下左右
if (array.size() == 0 || array[0].size() == 0) 
{
    return {};
}
int top=0;
int bottom=array.size()-1;
int l=0;
int r=array[0].size()-1;
vector<int>ans;
while(top<=bottom&&l<=r)
{
    for(int i=l;i<=r;i++)
    {
        ans.push_back(array[top][i]);
    }
    for(int i=top+1;i<=bottom;i++)
    {
        ans.push_back(array[i][r]);
    }
    if(bottom>top&&r>l)
    {
        for(int i=r-1;i>=l;i--)
    {
        ans.push_back(array[bottom][i]);
    }
    for(int i=bottom-1;i>=top+1;i--)
    {
        ans.push_back(array[i][l]);
    }
    }
    top++;
    bottom--;
    l++;
    r--;
}

return ans;
    }
};

LCR 147. 最小栈 - 力扣（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
39
40
41
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int>a,b;
    MinStack() {

    }
    
    void push(int x) {
a.push(x);
if(b.empty()||b.top()>=x)
{
    b.push(x);
}
    }
    
    void pop() {
if(b.top()==a.top())
{
    b.pop();
}
a.pop();
    }
    
    int top() {
return a.top();
    }
    
    int getMin() {
return b.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

LCR 148. 验证图书取出顺序 - 力扣（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
class Solution {
public:
    bool validateBookSequences(vector<int>& putIn, vector<int>& takeOut) {
stack<int>a;
int i=0;
for(auto c:putIn)
{
    while(!a.empty()&&a.top()==takeOut[i])
    {
        i++;
        a.pop();
    }
if(c==takeOut[i])
{
    i++;
        while(!a.empty()&&a.top()==takeOut[i])
    {
        i++;
        a.pop();
    }
}
else
{
    a.push(c);
}
}
return a.size()==0;
    }
};

LCR 149. 彩灯装饰记录 I - 力扣（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
/**
 * 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:
    vector<int> decorateRecord(TreeNode* root) {
vector<int>a;
if(!root)
{
    return a;
}
queue<TreeNode*>q;
q.push(root);
while(!q.empty())
{
    TreeNode* now=q.front();
    q.pop();
    a.push_back(now->val);
    if(now->left!=nullptr)
    {
        q.push(now->left);
    }
    if(now->right!=nullptr)
    {
        q.push(now->right);
    }
}
return a;
    }
};

LCR 152. 验证二叉搜索树的后序遍历序列 - 力扣（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
bool recur(vector<int>&postorder,int i,int j)
{
    if(i>=j)
    {
return true;
    }
    int p=i;
    while(postorder[p]<postorder[j])
    {
        p++;
    }
    int m=p;
    while(postorder[p]>postorder[j])
    {
        p++;
    }
    return p==j&&recur(postorder,i,m-1)&&recur(postorder,m,j-1);

}
class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
//遵循左子树，右子树，根的顺序进行递归
//左子树小于根，右子树大于根
//只需要抓住这个规律不断进行递归即可。
return recur(postorder,0,postorder.size()-1);
//数组，左子树的起始点，右子树的终结点，也就是一棵树
    }
};

√二叉树中和为某一值得路径 -> https://leetcode.com/problems/path-sum/

普通递归加回溯

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
/**
 * 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:
    vector<vector<int>> pathTarget(TreeNode* root, int target) {
dfs(root,target);
return res;
    }
private:
vector<vector<int>>res;
vector<int>path;
void dfs(TreeNode *root,int target)
{
    if(root==nullptr)
    {
        return ;
    }
    path.push_back(root->val);
    target-=root->val;
    if(target==0&&root->left==nullptr&&root->right==nullptr)
    {
        res.push_back(path);
    }
    dfs(root->left,target);
    dfs(root->right,target);
    path.pop_back();
    //回溯
}
};

LCR 154. 复杂链表的复制 - 力扣（LeetCode）

哈希表做法，先存储。

坑点：一定要重新new一个Node。

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==nullptr)
        {
            return nullptr;
        }
        unordered_map<Node *,Node *>map;
        Node *now=head;
        while(now!=nullptr)
        {
            map[now]=new Node(now->val);
            now=now->next;
        }
        now=head;
        while(now!=nullptr)
        {
            map[now]->next=map[now->next];
            map[now]->random=map[now->random];
            now=now->next;
        }
        return map[head];
    
    }
};

LCR 155. 将二叉搜索树转化为排序的双向链表 - 力扣（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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(root==nullptr)
        {
            return nullptr;
        }
        dfs(root);
        pre->right= now;
        now->left=pre;
        return now;
    }
private:
Node *pre;
Node *now;
void dfs(Node *n)
{
if(n==nullptr)
{
    return ;
}
dfs(n->left);
if(pre!=nullptr)
{
    pre->right=n;
}
else
{
    now=n;
}
if(pre!=nullptr)
{
n->left=pre;
}
pre=n;
dfs(n->right);
}

};

297. 二叉树的序列化与反序列化 - 力扣（LeetCode）

很明显的层序遍历，也就是bfs啊。

直接用队列写即可。

字符串处理有一定细节。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root==NULL)
        {
            return "[]";
        }
            string ans="[";
            queue<TreeNode*>q;
            q.push(root);
            while(!q.empty())
            {
                TreeNode *now=q.front();
                q.pop();
                if(now!=NULL)
                {
                    ans+=to_string(now->val)+",";
                    q.push(now->left);
                    q.push(now->right);
                }
                else
                {
                    ans += "null,";
                }
            }
            ans.pop_back();
            //去掉最后面的,号
            ans+="]";
            return ans;
        }


    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data=="[]")
        {
            return NULL;
        }
        string ans=data.substr(1);
        ans.pop_back();
        stringstream ss(ans);
        string a;
        vector<string>vals;
        while(getline(ss,a,','))
        {
            vals.push_back(a);
        }
        TreeNode *root=new TreeNode(stoi(vals[0]));
        queue<TreeNode *>q;
        q.push(root);
        int i=1;
        while(!q.empty())
        {
            TreeNode *now=q.front();
            q.pop();
            if(vals[i]!="null")
            {
                now->left=new TreeNode(stoi(vals[i]));
                q.push(now->left);
            }
            i++;
            if(vals[i]!="null")
            {
                now->right=new TreeNode(stoi(vals[i]));
                q.push(now->right);
            }
            i++;
        }
return root;
    }
};


// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

√字符串的排列 -> 567. 字符串的排列 - 力扣（LeetCode）

image-20240913193429791

使用滑窗思想。

先将前面n个存储，加或减。判断为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
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
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int>cnt1(27);
        int n=s1.length();
        int m=s2.length();
        if(n>m)
        {
            return false;
        }
        for(int i=0;i<n;i++)
        {
            cnt1[s2[i]-'a']++;
            cnt1[s1[i]-'a']--;
        }
        int different=0;
        for(auto c:cnt1)
        {
            if(c)
            {
                different++;
            }
        }
        if(!different)
        {
            return true;
        }
        for(int i=n;i<m;i++)
        {
            if(!cnt1[s2[i]-'a'])
            {
                different++;
            }
            cnt1[s2[i]-'a']++;
            if(!cnt1[s2[i]-'a'])
            {
                different--;
            }
            int x=s2[i-n]-'a';
            if(!cnt1[x])
            {
                different++;
            }
            cnt1[x]--;
            if(!cnt1[x])
            {
                different--;
            }
            if(!different)
            {
                return true;;
            }
        }
return false;
    }
};

√数组中出现次数超过一半的数字 -> https://leetcode.com/problems/majority-element/ ->

直接用哈希表即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};


√最小的k个数 -> *（类似）https://leetcode.com/problems/kth-largest-element-in-an-array/

直接用最大堆做。

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
class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
priority_queue <int > q;
vector<int>ans;
if(k==0)
{
    return ans;
}
for(auto x:arr)
{
    if(q.size()<k)
    {
        q.push(x);
    }
    else
    {
        if(q.top()>x)
        {
            q.pop();
            q.push(x);
        }
    }
}
while(!q.empty())
{
    ans.push_back(q.top());
    q.pop();
}
return ans;
    }
};

另一种做法:

这段代码的功能是从给定的数组 arr 中找到前 k 个最小的元素。代码使用了 C++ 标准库中的 nth_element 算法来实现这一点。我们可以逐步解释其中的语法和工作原理：

代码结构：

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        nth_element(arr.begin(), arr.begin() + k, arr.end());
        vector<int> res(k);
        copy(arr.begin(), arr.begin() + k, res.begin());
        return res;
    }
};

1. vector<int> smallestK(vector<int>& arr, int k)

这是 smallestK 函数的声明，函数接受两个参数： - arr：传入的整数向量，传递方式是引用 &，以避免复制整个数组。 - k：指定要返回的最小的 k 个元素。

返回值是一个整数向量 vector<int>，包含从 arr 中找到的前 k 个最小元素。

2. nth_element(arr.begin(), arr.begin() + k, arr.end())

  • nth_element 是 C++ 标准库中的一个算法，用来对数组中的第 n 个元素（这里是 arr.begin() + k）进行重新排列。

  • 语法解释：

    • arr.begin()：指向 arr 的起始位置。
    • arr.begin() + k：指向 arr 中第 k 个元素的位置（索引从 0 开始）。
    • arr.end()：指向 arr 的末尾（末尾后一个位置）。

  • nth_element 的工作原理：

    • nth_element 对数组 arr 的元素进行部分排序，使得第 k 个位置上的元素（arr[k]）在排序后的数组中是有序的。换句话说，在 arr.begin() 到 arr.begin() + k 之间的所有元素都是数组中最小的 k 个元素（但不保证它们是有序的）。
    • 这使得你可以通过一次 O(n) 的操作快速找到数组中前 k 个最小的元素，而不需要对整个数组进行完全排序。

3. vector<int> res(k)

  • 这行代码创建了一个大小为 k 的向量 res，用于存储结果。
  • vector<int> res(k)：创建一个长度为 k 的 vector，所有元素默认初始化为 0。

4. copy(arr.begin(), arr.begin() + k, res.begin())

  • copy 是 C++ 标准库中的一个函数，用来将一个范围内的元素复制到另一个容器中。

  • 语法解释：

    • arr.begin()：起始位置，表示从 arr 的第一个元素开始。
    • arr.begin() + k：结束位置（不包括该位置的元素），表示要复制的范围是 arr 中前 k 个元素。
    • res.begin()：目标容器的起始位置，表示复制到 res 向量的开头。

  • 作用：这行代码将 arr 中最小的 k 个元素（在调用 nth_element 后）复制到 res 向量中。

5. return res;

  • 返回保存了前 k 个最小元素的结果向量 res。

示例：

假设输入是： 

1
2
vector<int> arr = {3, 2, 1, 5, 6, 4};
int k = 3;
在调用 nth_element 后，arr 的前 3 个位置将包含最小的 3 个元素，但这些元素不一定是有序的，比如 {1, 2, 3, 5, 6, 4}。然后，copy 将前 3 个元素 {1, 2, 3} 复制到 res 中并返回。

总结：

  • nth_element 是一个高效的部分排序算法，用于找到前 k 个最小的元素，时间复杂度为 O(n)。
  • copy 用来将这些最小的元素复制到结果向量中。
  • 这段代码利用了 STL 函数的强大功能，简洁地实现了从数组中提取前 k 个最小元素的操作。
1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        nth_element(arr.begin(), arr.begin() + k, arr.end());
        vector<int> res(k);
        copy(arr.begin(), arr.begin() + k, res.begin());
        return res;
    }
};

295. 数据流的中位数 - 力扣（LeetCode）

对顶堆维护中位数。

最大堆存比较小的数字，最小堆存比较大的数字。

动态维护两个堆的大小，满足最大堆的元素个数大于或等于最小堆的元素个数，但不能大于超过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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class MedianFinder {
private:
priority_queue<int>p;
priority_queue<int,vector<int>,greater<int>>q;
public:
    MedianFinder() {

    }
    
    void addNum(int num) {
if(p.empty())
{
    p.push(num);
}
else 
{
    if(num<=p.top())
{
p.push(num);
}
else 
{
  q.push(num);  
}
while(p.size()>q.size()+1)
{
q.push(p.top());
p.pop();    
}
while(q.size()>p.size())
{
    p.push(q.top());
    q.pop();
}
}


    }
    
    double findMedian() {
if(q.size()==p.size())
{
return (double)(p.top()+q.top())/2.0;
}
else
{
    return double(p.top());
}

    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

53. 最大子数组和 - 力扣（LeetCode）

很经典的O(n)做法。

讲解一下是怎么进行贪心的：

如果加上这个数字反而不优秀了，那么为什么不只要这个数字呢，因为你加上他反而不优秀，那么说明前面那一部分实际上是个拖累，是可有可无的，我们自然贪心的去掉他。

最后每次都取一下最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
        for (const auto &x: nums) {
            pre = max(pre + x, x);
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};

LCR 162. 数字 1 的个数 - 力扣（LeetCode）

这或许是目前感觉最难的一题--数位dp。参考灵总的板子区间dp。

函数 f 是一个匿名递归函数，用于递归处理每一位的数字。它有三个参数：

  • i: 当前正在处理的位数（从高位到低位）。

  • cnt1: 当前统计的 1 出现的次数。

  • is_limit: 表示当前是否受原始数字 n 的限制，如果为 true，表示当前位不能超过 n 中对应的数字。

  • 函数工作流程：
    1. 递归结束条件：i == m，如果处理到最后一位，那么返回当前统计的 1 出现的次数 cnt1。
    2. 记忆化动态规划：如果当前不受限制 is_limit == false 并且这个状态已经计算过 dp[i][cnt1] >= 0，则直接返回这个已计算的结果，避免重复计算。
    3. 获取当前位的上限：如果 is_limit 为 true，说明当前位受原始数字的限制，那么本位最多只能取到原数字对应的位数 s[i] - '0'。否则，可以取到 9。
    4. 递归处理：
      • 对当前位 i，尝试每个可能的数字 d，从 0 到 up，递归到下一位 i + 1。
      • 对每种情况，更新当前已统计的 1 的个数 cnt1 + (d == 1)，并判断下一个位置是否继续受限于原始数字（is_limit && d == up）。
    5. 更新状态：如果当前不受限制（is_limit == false），则将结果存储在 dp[i][cnt1] 中，以便下次复用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int digitOneInNumber(int n) {
        auto s = to_string(n);
        int m = s.length(), dp[m][m];
        memset(dp, -1, sizeof(dp));
        function<int(int, int, bool)> f = [&](int i, int cnt1, bool is_limit) -> int {
            if (i == m) return cnt1;
            if (!is_limit && dp[i][cnt1] >= 0) return dp[i][cnt1];
            int res = 0;
            int up = is_limit ? s[i] - '0' : 9;
            for (int d = 0; d <= up; d++) 
                res += f(i + 1, cnt1 + (d == 1), is_limit && d == up);
            if (!is_limit) dp[i][cnt1] = res;
            return res;
        };
        return f(0, 0, true);
    }
};


LCR 163. 找到第 k 位数字 - 力扣（LeetCode）

找规律题目。暂时留着。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findKthNumber(int k) {
        int digit = 1;
        long start = 1;
        long count = 9;
        while (k > count) { // 1.
            k -= count;
            start *= 10;
            digit += 1;
            count = digit * start * 9;
        }
        long num = start + (k - 1) / digit; // 2.
        return to_string(num)[(k - 1) % digit] - '0'; // 3.
    }
};

LCR 164. 破解闯关密码 - 力扣（LeetCode）

重写排序函数即可。

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

bool cmp(string s1,string s2){
    return s1+s2<s2+s1;
}
class Solution {
public:
    string crackPassword(vector<int>& password) {
vector<string>p;
for(auto x:password)
{
p.push_back(to_string(x));
}
sort(p.begin(),p.end(),cmp);
string ans="";
for(auto c:p)
{
    ans+=c;
}
return ans;
    }
};

LCR 165. 解密数字 - 力扣（LeetCode）

简单dp，和斐波那契几乎一致的状态转移方程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int crackNumber(int ciphertext) {
//很明显是一道dp题目
//定义dp[i]为前i位共有多少种解密结果，那么只需要用到前i-1位和前i-2位数
string s=to_string(ciphertext);
int n=s.length();
vector<int>dp(n+1);
dp[1]=1;
dp[0]=1;
for(int i=2;i<=n;i++)
{
dp[i]=dp[i-1];
if((s[i-2]=='2'&&s[i-1]<='5')||s[i-2]=='1')
{
    dp[i]=dp[i-2]+dp[i-1];
}
}
return dp[n];
    }
};

LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

直接使用状态转移方程：

f[i][j]=max(f[i][j-1],f[i-1][j])+grid[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
int m = frame.size(), n = frame[0].size();
        vector<vector<int>> f(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i > 0) {
                    f[i][j] = max(f[i][j], f[i - 1][j]);
                }
                if (j > 0) {
                    f[i][j] = max(f[i][j], f[i][j - 1]);
                }
                f[i][j] += frame[i][j];
            }
        }
        return f[m - 1][n - 1];
    }
};

3. 无重复字符的最长子串 - 力扣（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
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
if(s.size()==0)
{
    return 0;
}
int n=s.length();
int l=0;
int ans=0;
unordered_set<char>q;
for(int i=0;i<n;i++)
{
while(q.find(s[i])!=q.end())
{
    q.erase(s[l]);
    l++;
}
q.insert(s[i]);
ans=max(i-l+1,ans);
}
return ans;
    }
};

263. 丑数 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        vector<int> factors = {2, 3, 5};
        for (int factor : factors) {
            while (n % factor == 0) {
                n /= factor;
            }
        }
        return n == 1;
    }
};


来一道升级版的。

264. 丑数 II - 力扣（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
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> factors = {2, 3, 5};
        unordered_set<long> seen;
        priority_queue<long, vector<long>, greater<long>> heap;
        seen.insert(1L);
        heap.push(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long curr = heap.top();
            heap.pop();
            ugly = (int)curr;
            for (int factor : factors) {
                long next = curr * factor;
                if (!seen.count(next)) {
                    seen.insert(next);
                    heap.push(next);
                }
            }
        }
        return ugly;
    }
};

LCR 169. 招式拆解 II - 力扣（LeetCode）

直接哈希表即可，怎么写都行。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    char dismantlingAction(string arr) {
        unordered_map<char, bool> hmap;
        for(char c : arr)
            hmap[c] = hmap.find(c) == hmap.end();
        for(char c : arr)
            if(hmap[c]) return c;
        return ' ';
    }
};

LCR 170. 交易逆序对的总数 - 力扣（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
39
40
class Solution {
public:
    int mergeSort(vector<int>& record, vector<int>& tmp, int l, int r) {
        if (l >= r) {
            return 0;
        }

        int mid = (l + r) / 2;
        int inv_count = mergeSort(record, tmp, l, mid) + mergeSort(record, tmp, mid + 1, r);
        int i = l, j = mid + 1, pos = l;
        while (i <= mid && j <= r) {
            if (record[i] <= record[j]) {
                tmp[pos] = record[i];
                ++i;
                inv_count += (j - (mid + 1));
            }
            else {
                tmp[pos] = record[j];
                ++j;
            }
            ++pos;
        }
        for (int k = i; k <= mid; ++k) {
            tmp[pos++] = record[k];
            inv_count += (j - (mid + 1));
        }
        for (int k = j; k <= r; ++k) {
            tmp[pos++] = record[k];
        }
        copy(tmp.begin() + l, tmp.begin() + r + 1, record.begin() + l);
        return inv_count;
    }

    int reversePairs(vector<int>& record) {
        int n = record.size();
        vector<int> tmp(n);
        return mergeSort(record, tmp, 0, n - 1);
    }
};

LCR 171. 训练计划 V - 力扣（LeetCode）

两个指针一直走：走完A从B开始走，走完B从A开始走，总会相遇的。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA, *B = headB;
        while (A != B) {
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans(2, -1);
        ans[0] = getleftposition(nums, target);
        ans[1] = getrightposition(nums, target);
        return ans;
    }

private:
    int getleftposition(vector<int>& nums, int target) {
         
        int left = 0, right = nums.size() - 1; 
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(target > nums[mid]) {
               
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
               
                right = mid - 1;
            }
        }

        if(left == nums.size() || nums[left] != target)
            return -1;
        
        return left;
    }   

    int getrightposition(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(target < nums[mid]) {
                right = mid - 1;
            } else if (target == nums[mid]) {
              
                left = mid + 1;
            } else {
                left = mid + 1;
            }
        }

        if(right == - 1 || nums[right] != target) {
            return -1;
        }

        return right;
    } 
};

库函数写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ret(2, -1); 
        auto lb = lower_bound(nums.begin(), nums.end(), target);
        if (lb != nums.end() && *lb == target) {
            ret[0] = distance(nums.begin(), lb);
            auto ub = upper_bound(lb, nums.end(), target);
            ret[1] = distance(nums.begin(), ub) - 1;
        }
        return ret;
    }
};

二叉搜索树的第K大节点 -> https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

写一个中序遍历的倒序遍历即可。

中序遍历是左子树->根->右子树

只需要翻转回来，变成右子树->根->左子树即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findTargetNode(TreeNode* root, int cnt) {
        this->cnt = cnt;
        dfs(root);
        return res;
    }
private:
    int res, cnt;
    void dfs(TreeNode* root) {
        if(root == nullptr) return;
        dfs(root->right);
        if(cnt == 0) return;
        if(--cnt == 0) res = root->val;
        dfs(root->left);
    }
};

二叉树的深度 -> https://leetcode.com/problems/maximum-depth-of-binary-tree/

一个非常简单的dfs即可。

1
2
3
4
5
6
7
8
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

数组中数字出现的次数 -> 442. 数组中重复的数据 - 力扣（LeetCode）

我们也可以给nums[i] 加上「负号」表示数 i+1已经出现过一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int>ans;
        for(auto &c:nums)
        {
            int x=abs(c);
            if(nums[x-1]>0)
            {
                nums[x-1]=-nums[x-1];
            }
            else
            {
                ans.push_back(x);
            }
        }
        return ans;
    }

};

和为S的数字 —>LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

使用双指针做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int i = 0, j = price.size() - 1;
        while(i < j) {
            int s = price[i] + price[j];
            if(s < target) i++;
            else if(s > target) j--;
            else return { price[i], price[j] };
        }
        return {};
    }
};

翻转字符串 ->344. 反转字符串 - 力扣（LeetCode）

一个左指针，一个右指针，两边交换，然后指针递增递减即可。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            swap(s[left], s[right]);
        }
    }
};


队列的最大值 -> 239. 滑动窗口最大值 - 力扣（LeetCode）

滑动窗口使用双端队列实现，存放的是下标。如果当前数字比窗口里面的大，直接弹出去即可。

并且前面如果不满足答案区间段也要弹出。

如果已经到达可以输出答案的区间段，记录答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.size() == 0) return nums;
        vector<int> arr;
        deque<int> dq;
        for(int i = 0; i < nums.size(); i++)
        {
            while(!dq.empty() && nums[i] > nums[dq.back()]) dq.pop_back();
            if(!dq.empty() && dq.front() <= (i - k)) dq.pop_front();
            dq.push_back(i);
            if(i >= k - 1) arr.push_back(nums[dq.front()]);
        }
        return arr;
    }
};

n个骰子的点数 -> （中文版）https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/

详细见注释。

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:
    vector<double> statisticsProbability(int num) {
        // 创建 dp 数组, dp[i][s] 代表 i 个骰子点数和为 s 的次数
        int n=num;
        vector<vector<int>> dp(n + 1, vector<int>(6 * n + 1, 0));
        
        // 初始化第一个骰子
        for (int s = 1; s <= 6; ++s) {
            dp[1][s] = 1;
        }
        
        // 动态规划填表，i表示骰子数，s表示点数和
        for (int i = 2; i <= n; ++i) {
            for (int s = i; s <= 6 * i; ++s) {
                for (int b = 1; b <= 6; ++b) {
                    if (s - b >= i - 1&&s-b<=(i-1)*6) {  // 确保点数合法
                        dp[i][s] += dp[i - 1][s - b];
                    }
                }
            }
        }
        
        // 计算概率
        vector<double> res;
        int total = pow(6, n);  // 总共的排列数为 6^n
        for (int s = n; s <= 6 * n; ++s) {
            res.push_back(static_cast<double>(dp[n][s]) / total);
        }
        
        return res;
    }
};

扑克牌中的顺子 -> （中文版）https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/

简单map。注意判断重复。

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:
    bool checkDynasty(vector<int>& places) {
int cnt=0;
vector<int>a;
for(auto c:places)
{
    if(c==0)
    {
        cnt++;
    }
    else
    {
        a.push_back(c);
    }
}
sort(a.begin(),a.end());
for(int i=1;i<a.size();i++)
{
    if(cnt>=a[i]-a[i-1]-1&&a[i]!=a[i-1])
    {
        cnt-=a[i]-a[i-1]-1;
    }
    else
    {
        return false;
    }
}
return true;


    }
};

圆圈中最后剩下的数字 -> （中文版） https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

约瑟夫环的数学解法。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int iceBreakingGame(int num, int target) {
        int ans = 0;
        for (int i = 2; i <= num; i++) {
            ans = (ans + target) % i;
        }
        return ans;
    }
};

股票的最大利润 -> 121. 买卖股票的最佳时机 - 力扣（LeetCode）

维护一个前面的最小值，因为只能买卖一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int inf = 1e9;
        int minprice = inf, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};


求1+2+…+n -> （中文版） https://leetcode-cn.com/problems/qiu-12n-lcof/

模拟龟速乘法

根据求和公式

target*(target+1)/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
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
// int quick_chen(int a,int b)
// {
//     int ans =0;
//     while(b)
//     {
//         if(b&1)
//         {
//             ans+=a;
//         }
//         a+=a;
//         b>>=1;
//     }
//     return  ans;
// }
class Solution {
public:
    int mechanicalAccumulator(int target) {
        int ans = 0, A = target, B = target + 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        return ans >> 1;
    }
};


不用加减乘除做加法 -> （中文版） https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/

使用加法器来计算和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int encryptionCalculate(int dataA, int dataB) {
        int a=dataA;
        int b=dataB;
while(b)
{
    int carry=a&b;
    a^=b;
    b=carry<<1;
}
return a;
    }
};

构建乘积数组 -> （中文版） https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/

一次遍历即可，注意特殊判断一下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
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<int> statisticalResult(vector<int>& arrayA) {
        long long sum=1;
        map<int,int>mp;
        for(auto a:arrayA)
        {
            sum*=a;
            mp[a]++;
        }
        long long res=1;
        for(auto a:arrayA)
        {
if(a)
{
    res*=a;
}
        }
        vector<int>ans;
        for(auto a:arrayA)
        {
            if(a==0&&mp[a]==1)
            {
                ans.push_back(res);
            }
            else if(a==0)
            {
                ans.push_back(0);
            }
            else
            ans.push_back(sum/a);
        }
        return ans;
    }
};

把字符串转换成整数 -> https://leetcode.com/problems/string-to-integer-atoi/

写了个一坨出来。这个建议好好模拟。

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
class Solution {
public:
    int myAtoi(string s) {
int n=s.length();
int ans=1;
vector<int>res;
for(int i=0;i<n;i++)
{
    bool fal=1;
    if(i==0)
    {
while(s[i]==' ')
{
    i++;
}
bool flag=1;
if(s[i]=='+')
{
    ans=1;
    i++;
    flag=0;
    if(s[i]==' ')
    {
        return 0;
    }
}
if(s[i]=='-')
{
    if(!flag)
    {
        return 0;
    }
    ans=-1;
    i++;
}
while(s[i]==' '||s[i]=='0')
{
    if(s[i]=='0')
    {
        fal=0;
    }
    if(!fal&&s[i]==' ')
    {
        return 0;
    }
    i++;
}
if(!(s[i]>='0'&&s[i]<='9'))
{
    return 0;
}
    }
    if(!fal&&s[i]==' ')
    {
        continue;
    }
    if(!(s[i]>='0'&&s[i]<='9'))
{
    break;
}
res.push_back(s[i]-'0');
}
long long ret=0;
for(auto a:res)
{
    ret=ret*10+a;
    if(ret*ans>=2147483647)
    {
        return ans*2147483647;
    }
    if(ret*ans<=-2147483648)
    {
        return -2147483648;
    }
}
return ans*ret;
    }
};

更简单的做法

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int myAtoi(string s) {
        stringstream liu(s);
        int n=0;
        liu>>n;
        return n;
    }
};

这段代码实现了一个简单的 myAtoi 函数，用于将字符串转换为整数。它使用了 C++ 标准库中的 stringstream 来解析输入字符串，并将其转换为整数。

代码的主要部分：

  1. stringstream liu(s);:
    • 这里创建了一个 stringstream 对象 liu，并将字符串 s 传入。
    • stringstream 是 C++ 标准库中的类，属于 <sstream> 头文件，用于在字符串和其他数据类型（如整数、浮点数等）之间进行输入/输出操作。它内部维护了一个流对象，可以像处理文件流一样操作字符串。
  2. int n = 0;:
    • 定义了一个整数变量 n，用于存储从字符串转换得到的整数。
  3. liu >> n;:
    • 使用流操作符 >> 试图从 stringstream 中提取整数。该操作符会自动跳过字符串开头的空白字符，并从第一个有效字符开始读取。如果遇到非数字字符（除了可能的负号或正号），解析会停止。
    • 如果字符串中的内容无法解析为有效的整数，例如当字符串没有数字时（如 "abc"），n 将保持其初始值 0。如果字符串开头有数字字符（如 "123abc"），它会正确解析前面的数字部分，并忽略后面的字符。
  4. return n;:
    • 返回解析得到的整数 n。

工作原理总结：

  • stringstream 提供了流输入/输出接口，将字符串作为输入，通过 >> 操作符解析并转换为指定类型（这里是 int）。
  • 如果字符串中有合法的数字字符，stringstream 会将其正确解析并转换为整数。否则，返回的结果可能是默认值 0 或解析的前缀整数。
  • 这种方法非常简洁，但没有处理可能出现的错误情况（如整数溢出）以及符号、前缀空白等细节。对于更严格的要求，可以参考 std::stoi 或手动实现解析逻辑。

示例：

1
2
3
4
5
Solution sol;
int result1 = sol.myAtoi("42");         // 输出 42
int result2 = sol.myAtoi("   -42abc");  // 输出 -42
int result3 = sol.myAtoi("abc123");     // 输出 0
int result4 = sol.myAtoi("2147483647"); // 输出 2147483647

优缺点：

  • 优点：使用 stringstream 非常简单，可以快速实现将字符串转换为整数的功能。
  • 缺点：它不处理溢出情况，且无法严格控制字符串中的格式。

二叉搜索树的最近公共祖先 -> https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

直接递归的做，左子树和右子树不断递归。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL||root==p||root==q)
        {
             //只要当前根节点是p和q中的任意一个，就返回
            return root;
        }
        TreeNode *left=lowestCommonAncestor(root->left,p,q);
        TreeNode *right=lowestCommonAncestor(root->right,p,q);
        if(left==NULL&&right==NULL)
        {
            return NULL;
        }
        if(left==NULL)
        {
            return right;
        }
        if(right==NULL)
        {
            return left;
        }
        return root;
    }
};