不正经

这个屌丝很懒，什么也没留下！

热门标签

剑指offer刷题笔记整理

作者：不正经 | 2024-04-08 07:19:23

踩

剑指offer刷题笔记

day1
day2
day3
day4
day5
day6
day7

过去几天复习了一遍剑指offer，整理一下笔记方便以后复习，题目来源leetcode,题解来源acwing

day1

02 回文链表

/**
 * 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* SearchHalfNode(ListNode* head)
    {
        auto fast = head;
        auto slow = head;
        while (fast)
        {
            fast = fast -> next;
            slow = slow -> next;
            if (fast) fast = fast->next;
        }
        return slow;
    }

    ListNode* reverseList(ListNode* node)
    {
        ListNode* pre = nullptr;
        while (node)
        {
            auto next_ = node->next;
            node -> next = pre;
            pre = node;
            node = next_;
        }
        return pre;
    }
    bool isPalindrome(ListNode* head) {
        auto mid = SearchHalfNode(head);
        auto end = reverseList(mid);
        while (end)
        {
            if (head->val != end->val) 
                return false;
            head = head->next;
            end = end-> next;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

03 I 数组中重复的是数字

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int n  = nums.size();
        for (auto x: nums)
            if (x < 0 || x >= n ) 
                return -1;
        for (int i = 0; i < n; i ++)
        {
            while (i != nums[i] && nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);//交换i nums[i] nums[nums[i]]
            if (i != nums[i] && nums[nums[i]] == nums[i]) return nums[i];//交换位置已经有值，那么返回nums[i]
        }
        return -1; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

03II 不修改数组找出重复的数字

#include <iostream>
#include <vector>

using namespace std;
const int N = 1010;
vector<int> nums;

class Solution
{
public:
    int duplicateInArray(vector<int> &nums)
    {
        int l = 1, r = nums.size() - 1; //最大值、最小值
        while (l < r)
        {
            //无序数组二分
            int mid = l + r >> 1; //按中位数切分成两半
            // [l,mid] [mid+1,r]
            int s = 0;
            for (auto x : nums)
                s += x >= l && x <= mid; //按区间计数
            if (s > mid - l + 1)         //如果左边区间的点大于区间中的点位
                r = mid;                 //去左边查找
            else
                l = mid + 1; //否则去右边查找
        }
        return r;
    }

    void display()
    {
        cout << "this is my function!" << endl;
    }
};

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i <= n; i++)
    {
        int x;
        cin >> x;
        nums.push_back(x);
    }
    Solution solution;
    int res;
    // solution.display();
    res = solution.duplicateInArray(nums);
    cout << res << endl;
}
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

04 二维有序数组的查找

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        /*
        从左下角开始查找，上边的数一定小，右边的数一定大
        每次都会省略一行
        */
        int m, n;
        if (matrix.empty() || matrix[0].empty()) return false;
        m = matrix.size();
        n = matrix[0].size();
        int i = m - 1, j = 0;
        while (i >= 0 && j < n)
        {
            if (matrix[i][j] > target) i --;
            else if (matrix[i][j] < target) j ++;
            else 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

05 替换空格

class Solution {
public:
    string replaceSpace(string s) {
        string res;
        for (auto x: s)
        {
            if (x == ' ') res += "%20";
            else res += x;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

06 从尾到头打印链表

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {} //构造函数初始化，可以传入参数x
  };
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> res;
        while (head)
        {
            res.push_back(head -> val);
            head = head -> next;
        }
        return vector<int>(res.rbegin(), res.rend());//rbegin与begin正好相反
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

07 根据前序和中序重新构建二叉树

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

class Solution {
public:
    map <int, int> hash;
    vector<int> preorder, inorder;
    TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
        /*
        根左右找到根节点的值
        左根右找到根节点的位置，然后递归左子树和右子树
        */
        preorder = _preorder, inorder = _inorder;
        for (int i = 0; i < inorder.size(); i++) hash[inorder[i]] = i;//使用hash存储每个节点在中序遍历中的位置
        return dfs(0, preorder.size() - 1, 0, inorder.size() - 1);
    }
    TreeNode* dfs(int pl, int pr, int il, int ir)
    {
        if (pl > pr) return nullptr;
        auto root = new TreeNode(preorder[pl]);
        int k = hash[root -> val];
        auto left = dfs(pl + 1, pl  + k - il, il, k - 1);//左子树k-il个元素
        auto right = dfs(pl + k - il + 1, pr, k + 1, ir);
        root -> left = left;
        root -> right = right;
        return root;
    }
};
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

08 二叉树中序遍历的下一个节点

#include <cstdlib>

struct TreeLinkNode
{
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next; // father指针
    TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL){}
};

class Solution
{
public:
    TreeLinkNode *GetNext(TreeLinkNode *pNode)
    {
        //当前节点在中序遍历中的下一个节点：后继
        //二叉搜索树中比当前节点大的最小节点
        // next是父节点
        if (pNode->right)
        {
            pNode = pNode->right;
            while (pNode->left)
                pNode = pNode->left;//如果有右子树，那么下一个节点一定是右子树的最左节点
            return pNode;
        }
        // 如果没有右子树，中序遍历会向上看，如果是父节点的左节点那么直接返回父节点
        // 如果是父节点的右节点，那么沿着父节点继向上，直到某个节点是父节点的左节点，返回父节点
        // 两种情况可以统一为
        while (pNode->next && pNode == pNode->next->right)
            pNode = pNode->next;
        return pNode->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

09 两个栈实现队列

class CQueue {
public:
    stack<int> stk, cache;
    CQueue() {}
    void appendTail(int value) {
        stk.push(value);
    }
    void copy(stack<int> &a, stack<int> &b)
    {
        while (a.size())
        {
            b.push(a.top());
            a.pop();
        }
    }
    int deleteHead() {
        if (stk.size())
        {
            copy(stk, cache);//保存到缓存中
            int res = cache.top();//删除队头
            cache.pop();
            copy(cache, stk);//拷贝回去
            return res;
        }
        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
26
27
28
29

10 斐波那契数列、青蛙跳台阶

class Solution {
public:
    int fib(int n) {
        int  a = 0, b = 1;
        for (int i = 1; i <= n; i ++)
        {
            int r = (a + b) % 1000000007;// (a + b) % c = (a % c + b % c) % c 所以可以提前取余，避免整形溢出
            a = b;
            b = r;
        }
        return a;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

11 旋转数组中的最小数字

class Solution {
public:
    int minArray(vector<int>& numbers) {
        // 有序数组 搬移后仍然是有序数组
        // 左数组最左边 可能 等于右数组最右边 去掉右数组的右半边
        // 右边数组完全小于左边，可以找到右数组的最左元素
        // 使用二分
        int n = numbers.size() - 1;
        if (n < 0) return -1;
        while (n > 0 && numbers[0] == numbers[n]) n --;
        if (numbers[0] <= numbers[n]) return numbers[0]; //只剩左数组
        //二分搜索 小于numbers[0]的最左数
        int l = 0, r = n;
        while (l < r)
        {
            int mid = l + (r - l) /  2;//[l,mid] [mid+1,r]
            if (numbers[mid] < numbers[0]) r = mid;//mid落在了右半
            else l = mid + 1;//mid落在左半
        }
        return numbers[r];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

12 矩阵中的路径

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        //dfs 从首字母开始查找，如果找到立即返回
        if (board.empty()) return false;
        for (int i = 0; i < board.size(); i ++)
            for(int j = 0; j < board[i].size(); j++)
            {
                if (dfs(board, word, 0, i, j)) return true;
            }
        return false;

    }

    bool dfs(vector<vector <char>> &board, string word, int u, int x, int y)
    {
        if (board[x][y] != word[u]) return false;
        // 如果二维矩阵元素等于当前元素
        if (u == word.size() - 1) return true;
        // 如果当前元素相等且不是末尾元素，向下查找
        char t = board[x][y];
        board[x][y] = '*';
        int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};
        for (int i = 0; i < 4; i++)
        {
            int a = x + dx[i];
            int b = y + dy[i];
            //如果在范围内，寻找下一层
            if (a >=0 && a < board.size() && b >= 0 && b < board[a].size())
                if (dfs(board, word, u + 1, a, b)) return true;
        }
        board[x][y] = t;//回溯
        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
34
35

day2

13 机器人的运动范围

class Solution {
public:
    int get_single_sum(int x)
    {
        int s = 0;
        while (x)
        {
            s += x % 10;
            x /= 10;
        }
        return s;
    }

    int get_sum(pair<int, int> p) //坐标位数之和不能大于k
    {
        return get_single_sum(p.first) + get_single_sum(p.second);
    }
    int movingCount(int m, int n, int k) {
        int res = 0;
        if (!m || !n) return 0;

        vector<vector<bool>> st(m, vector<bool>(n));
        queue<pair<int, int>> q;
        
        q.push({0, 0});//pair列表初始化
        int dx[2] = {1, 0}, dy[2] = {0, 1};//只需要向下和向右查找即可
        while (!q.empty())
        {
            auto t = q.front();
            q.pop();
            if (get_sum(t) > k||st[t.first][t.second]) continue;
            //如果满足条件
            res ++;
            st[t.first][t.second] = true;
            // 广度优先搜索
            for (int i = 0; i < 2; i++)
            {
                int a = t.first + dx[i];
                int b = t.second + dy[i];
                if (a >= 0 && a < m &&b >= 0 && b < n)
                    q.push({a, b});
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

14 剪绳子

/*
整数拆分，使其因子乘积最大

结论：
  ni%3 余1 拆出一个2*2=4，剩下被3拆分
  ni%3 余2 拆出一个2，剩下被3拆分
分析过程：
    假设N > 0， 正整数N拆分成m个数，N = n1 + n2 + n3 + n4 + n..+nm
    1 最优解肯定没有1， 1*(x-1)< x
    2 最优解可以没有4， 2*2=4 可拆  最优解2 3 >4
    3 ni>5, ni必须拆成3*(ni-3)，最优解不能包含大于等于5的数，最优解只包含 2和3
                     3 * (ni - 3) >= ni
                     3 * ni - 9 >= ni
                     2 * ni >= 9 成立,拆了更好  
    4 最优解若有3个2： 2 * 2 *2 < 3 * 3 最优解最多两个2 
*/


class Solution {
public:
    int cuttingRope(int n) {
        int res = 1;
        if (n <= 3) return n -1;
        if (n % 3 == 1) res *= 4, n -= 4;
        if (n % 3 == 2) res *= 2, n -= 2;
        while (n)
        {
            res *= 3;
            n -= 3;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

15 二进制中1的个数

/*两种解法：
 1 lowbit 最后一位1的二进制表示的十进制数
   在原来的基础上减去即可消去最右边的1，每消一次计数+1
   1010 原码
   0110 补码
2 直接转换为正数的原码
   在原来的基础上每次右移1位，每次计数 + x&1
 */
//lowbit算法
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int s = 0;
        while (n)
        {
            int x = n & -n;
            n -= x;
            s ++;
        }
        return s;     
    }
};
//直接转化为正数
class Solution {
public:
    int hammingWeight(uint32_t n) {
        unsigned int n_ = n;
        int s = 0;
        while (n)
        {
            s += n & 1;
            n >>= 1;
        }
        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

16 数值的整数次幂

/*
快速幂：指数的二进制拆分
x^N = x2*x2^2*x2^3*x2^4...
N = 2^2+2^3+2^4...表示为二进制数即可。
N & 1
0 res*=x
1 res*=x*2
2 res*=x*4
3 res*=x*8
...
*/

class Solution {
public:
    double myPow(double x, int n) {
        //注意负指数

        double res = 1;
        long long  N = abs(n);
        while (N)
        {
            if (N & 1) res *= x;//二进制位=1,那么累加结果
            x *= x; 
            N >>= 1;//指数的二进制拆分
        }      
        if (n < 0) res = 1 / res;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

17 打印1到最大的n位数

class Solution {
public:
    vector<int> printNumbers(int n) {
        //输出所有的n位数
        int m = (pow(10, n)) - 1;
        vector<int> nums(m, 1);
        for (int i = 1; i < m; i ++)
            nums[i] = nums[i-1] + 1;
        return nums;
    }
};
1
2
3
4
5
6
7
8
9
10
11

18 删除链表的节点

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        //如果是头节点
        if (head -> val == val) return head -> next;
        //不是头节点
        ListNode* cur = head;
        while(cur-> next -> val != val)
            cur = cur -> next;
        cur -> next = cur -> next -> next;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

LC 83 删除有序链表中的重复节点

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // dummy 哨兵机制 头结点可能被删掉
        auto dummy = new ListNode(-1);
        dummy -> next = head;
        // 链表双指针 dummy 1 1 1 2 2 3 3 4 4 分段看
        auto p = dummy;
        while (p -> next)
        {
            auto cur = p -> next;
            while (cur -> next && cur -> val == cur -> next -> val) 
                cur = cur -> next;
            // 如果没有重复,p移动到cur，
            if (p -> next  == cur) p = cur;
            // 如果有重复，将p的next指针指向cur
            else p -> next = cur;//cur在下一个区间
        }
        return dummy -> next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

19 正则表达式匹配

class Solution {
public:
    int n, m;
    vector<vector<int>> f;
    string s, p;
    bool isMatch(string s_, string p_) {
        s = s_, p = p_;
        n = s.size(), m = p.size();
        f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
        return dp(0, 0);
    }

    bool dp(int x, int  y)
    {
        if (f[x][y] != -1) 
            return f[x][y];
        if (y == m) 
            return f[x][y] = x == n; // 初始化
        bool first_match = x < n && (p[y] == '.' || s[x] == p[y]);
        if (y + 1 < m && p[y + 1] == '*')
            //匹配0次跳过两个匹配字符
            //匹配一次以上： 当前字符匹配且f[x+1][y]后面字符也是匹配的
            f[x][y] = dp(x, y + 2) || (first_match && dp(x + 1, y));
        else
        {
            f[x][y] =  first_match && dp(x + 1, y + 1);
        }
        return f[x][y];
    }
};
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

20 PASS

21. 调整数组顺序使奇数位于偶数前面

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        /*双指针
         第一个指针前面全是奇数
         第二个指针后面全是偶数*/
         int l = 0, r = nums.size() - 1;
         while (l <= r)
         {
             while (l <= r && nums[l] % 2 == 1) l ++;
             while (l <= r && nums[r] % 2 == 0) r --;
             if (l < r) swap(nums[l], nums[r]);
         }
         return nums;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

22. 链表中倒数第k个节点

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        auto slow = head;
        int idx = 0;
        while (head)
        {
            if (idx >= k)
                slow = slow -> next;
            head = head->next;
            idx ++;
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

23 链表中环的入口

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 链表中环的检测
        auto fast = head;
        auto slow = head;
        bool find = false;
        while (slow && fast)
        {
            //fast走两步
            fast = fast -> next;
            if (fast) fast = fast -> next;
            //fast空时，无环
            if (!fast) return nullptr;
            //slow走一步
            slow = slow -> next;
            //如果相遇，那么停止
            if (fast == slow) 
            {
                find = true;  
                break;
            }
        }
        //没有环
        if (!find) return nullptr;
        //从头开始走，直到相遇
        slow = head;
        while (slow && fast && slow != fast)
        {
            fast = fast -> next;
            slow = slow -> next;
        }
        return slow;
    }
};
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

day3

24 反转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //记录一个前驱节点
        ListNode * pre = nullptr;
        auto cur = head;
        while (cur)
        {
            auto next = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};
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

25 合并两个排序链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //归并排序的并操作
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        while (l1 && l2)
        {
            if (l1 -> val <= l2 -> val) 
            {
                cur -> next = l1;
                l1 = l1 ->next;
            }
            else 
            {
                cur -> next = l2;
                l2 = l2 -> next;
            }
            cur = cur ->next;
        }
        if (l1) cur -> next = l1;
        else cur ->next = l2;
        return dummy -> 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

26 树的子结构

/**
 * 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:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        // B恰好能覆盖A的部分节点 类似字符串匹配 
        // 从树根开始看，如果不是，后移一位 暴力匹配 空树不是任意子结构 
        if (!A || !B) return false;//某棵树为空 返回fasle
        if (isPart(A, B)) return true;// 如果A\B匹配返回true
        return isSubStructure(A->left, B) || isSubStructure(A->right,B);//如果不匹配 看左右子树是否匹配
    }

    bool isPart(TreeNode* p1, TreeNode* p2)
    {
        if (!p2) return true;//如果p2没有点了，匹配成功
        if (!p1 || p1 -> val !=  p2 -> val) return false;//p1没有电，匹配失败
        //如果p1 p2有点且值相等，那么当前节点匹配，看左右节点是否匹配
        return isPart(p1 -> left, p2 -> left) && isPart(p1 -> right, p2 -> 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

27 二叉树镜像

/**
 * 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) return root;
        swap(root->left, root->right);
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

28 对称的二叉树

/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        // 除了根节点  
        // 左节点的左儿子和右节点的右儿子 相等
        // 左节点的右儿子和右节点的左儿子 相等
        if (!root) return true;
        // 看左右子树是否对称
        return dfs(root -> left,  root->right);
    }
    bool dfs(TreeNode* p1, TreeNode* p2)
    {
        if (!p1 || !p2) return !p1 && !p2;
        //只有两个同时为空才返回true;
        if (p1 -> val != p2 -> val) return false;
        //如果两个节点相等，则递归判断两个节点的左右儿子
        return dfs(p1 -> left, p2 -> right) && dfs(p1 -> right, p2 -> left);
    }
};
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:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector <int> res;
        if (matrix.empty()) return res;
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<bool>> st(m, vector<bool>(n, false));
        int dx[4] = {0,1,0,-1},  dy[4] = {1, 0, -1, 0};
        int x = 0, y = 0, d = 0;
        for (int i = 0; i < m * n; i ++)
        {
            res.push_back(matrix[x][y]);
            st[x][y] = true;
            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= m || b < 0 || b >= n || st[a][b])
            {
                //如果走出了矩阵范围，那么回退到x,y 然后调整方向
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;//新的坐标
        }
        return res;
 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

30 包含min函数的栈

class MinStack {
public:
    stack<int> stk, min_stk;
    /** initialize your data structure here. */
    MinStack() {
    }
    //单调栈
    
    void push(int x) {
        stk.push(x);
        if (min_stk.empty() || x <= min_stk.top()) min_stk.push(x);

    }
    
    void pop() {
        if (stk.top() == min_stk.top()) min_stk.pop();
        stk.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int min() {
        return min_stk.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

31 栈的输入和弹出序列

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int m = pushed.size();
        int n = popped.size();
        stack<int> stk;
        for (int i = 0, j = 0; i < m; i ++)
        {
            stk.push(pushed[i]);
            while (j < n && stk.size() && stk.top() == popped[j]) 
                stk.pop(), j++;
        }
        if (stk.size()) return false;
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

32 从上到下打印二叉树（不分行）

/**
 * 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:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size())
        {
            auto t = q.front();
            q.pop();
            res.push_back(t -> val);
            if (t -> left) q.push(t -> left);
            if (t -> right) q.push(t -> right);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

32 从上到下打印二叉树（分行）

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        // 第一行加入null标记
        // 遍历到第一行的null时，第二行自然也是null此时代表第二行结束...依次类推
        queue<TreeNode*> q;
        if (!root) return res;
        q.push(root);
        q.push(nullptr);
        vector<int> level;
        while (q.size())
        {
            auto t = q.front();
            q.pop();
            if (!t)
            {
                // 如果到达末尾
                if (level.empty()) return res;
                // 如果到达行尾
                res.push_back(level);
                level.clear();
                q.push(nullptr);
                continue;
            }
            level.push_back(t -> val);
            if (t -> left) q.push(t -> left);
            if (t -> right) q.push(t -> right);
        }
        return res;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

32 从上到下打印二叉树（之字形：左右左）

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        vector<int> level;
        queue<TreeNode*> q;
        q.push(root);
        q.push(nullptr);
        bool zigzag = false;
        while(q.size())
        {
            auto t = q.front();
            q.pop();
            if(!t)
            {
                if (level.empty()) return res;
                if (zigzag) reverse(level.begin(), level.end());
                res.push_back(level);
                level.clear();
                q.push(nullptr);
                zigzag = !zigzag;
                continue;
            }
            level.push_back(t -> val);
            if (t -> left) q.push(t -> left);
            if (t -> right) q.push(t -> right);
        }
        return res;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

day4

33. 二叉搜索树的后序遍历序列

// 中序+后序 nlogn
class Solution {
public:
    vector<int> inorder, postorder;
    map<int, int> hash;
    bool verifyPostorder(vector<int>& postorder_) {
        postorder = postorder_;
        sort(postorder_.begin(), postorder_.end()); 
        inorder = postorder_;
        for (int i = 0; i < postorder.size(); i ++) hash[inorder[i]] = i;
        return dfs(0, postorder.size() - 1, 0, inorder.size() - 1);
    }
    int dfs(int pl, int pr, int il, int ir)
    {
        if (pl > pr) return true;
        auto root = postorder[pr];
        int k = hash[root];
        if (k < il || k > ir) return false; //当前的根节点不在中序遍历的范围内
        bool left = dfs(pl, pl + k- il - 1 , il,  k - 1);//长度为k-il
        bool right = dfs(pl + k-il, pr - 1, k+ 1, ir);
        return left && right;
    }
};
//只用后序遍历 n*n
class Solution {
public:
    vector<int> postorder;
    bool verifyPostorder(vector<int>& postorder_) {
        postorder = postorder_;
        return dfs(0, postorder.size() - 1);
    }

    bool dfs(int l, int r)
    {
        if (l >= r) return true;
        int root = postorder[r];
        int k = l;
        //左子树的元素都小于根节点
        while (k < r && postorder[k] < root) 
            k++;//右子树的第一个元素
        for (int i = k; i < r; i ++)
            // 右子树的元素都大于根节点
            if (postorder[i] < root) 
                return false;
        return dfs(l, k - 1) && dfs(k, r - 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

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) {}
 * };
 */
class Solution {
public:
    vector<int> path;
    vector<vector<int>> ans;
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        dfs(root, target);
        return ans;
    }

    void dfs(TreeNode* root, int target)
    {
        if (!root) return;
        // 单层递归逻辑
        /*
        1 先放入当前节点
        2 检查是否为叶节点
            如果是
                满足和条件，直接加入答案
                不满足条件，回溯 if(!root) return 
            如果不是，递归 if(!root) return 
        */
        path.push_back(root->val);
        target -= root->val;
        if (!root-> left && !root->right && !target)
            ans.push_back(path);
        dfs(root-> left, target);
        dfs(root-> right, target);
        path.pop_back();
    }
};
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

35 复杂链表的复制

/*
// 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) return nullptr;
        //复制链表
        Node* cur = head;
        while (cur)
        {
            Node* post = new Node(cur->val);
            post-> next = cur -> next;
            cur -> next = post;
            cur = post -> next;
        }
        // 复制随机指针
        cur = head;
        while (cur)
        {
            if (cur -> random)
                cur -> next -> random = cur -> random -> next;
            cur = cur -> next -> next;
        }
        // 分离节点
        auto dummy = new Node(-1);
        cur = dummy;
        Node* raw = head;
        while (raw)
        {         
            cur -> next = raw -> next;
            raw -> next = cur -> next-> next;
            cur = cur -> next;
            raw = raw -> next;   
        }
        return dummy-> 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
46
47
48
49
50
51

36 二叉搜索树与双线链表

/*
// 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) return root;
        auto slides = dfs(root);
        slides.first -> left = slides.second;
        slides.second -> right = slides.first;
        return slides.first;
    }
    pair<Node*, Node*> dfs(Node* root)
    {
        if (!root->left && !root-> right) return {root, root};
        else if (root->left && root->right)
        {
            //pari存储双向链表的头尾节点，经过dfs后所有子树都链接成了双向链表
            // 将头尾指针连接即可得到双向循环链表
            auto lslide = dfs(root->left), rslide = dfs(root->right);
            lslide.second -> right = root, root-> left = lslide.second;
            root-> right = rslide.first,   rslide.first -> left = root;
            return {lslide.first, rslide.second};
        }
        else if (root->left)
        {
            auto lslide = dfs(root->left);
            lslide.second -> right = root, root-> left = lslide.second;
            return {lslide.first, root};
        }
        else
        {
            auto  rslide = dfs(root->right);
            root-> right = rslide.first, rslide.first -> left = root;
            return {root, rslide.second};
        }
    }
};
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

37 二叉树的序列化和反序列化

/**
 * 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) {
        string res;
        dfs_s(root, res);
        return res;        
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0;
        return dfs_d(data, u);
    }

    void dfs_s(TreeNode* root, string& res)
    {
        if (!root)
        {
            res += "null ";
            return;
        }
        res += to_string(root->val) + " ";
        dfs_s(root->left, res);
        dfs_s(root->right,res);
    }


    TreeNode* dfs_d(string data, int& u)
    {
        
        if (u == data.size()) return nullptr;
        int k = u;
        //当前节点的末尾后一位
        while (data[k] != ' ') k ++;
        //节点是null是null的话，空格的下一位 下一节点
        if (data[u] == 'n')
        {
            u = k + 1;
            return nullptr;
        }
        //如果是数字
        int val = 0;
        //负数
        if (data[u] == '-')
        {
            for (int i = u + 1; i < k; i++) 
                val = val * 10 + (data[i]- '0');
            val = -val;
        }
        //正数
        else
        {   
            for (int i = u; i < k; i++) 
                val = val * 10 + (data[i]- '0');
        }
        u = k + 1;
        auto root = new TreeNode(val);
        root-> left = dfs_d(data, u);//遍历到空节点，返回的是null
        root-> right = dfs_d(data, u);//遍历到空节点，返回的是null
        return root;
    }
};
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

38 字符串序列

class Solution {
public:
    vector<string> res;
    string path;
    vector<string> permutation(string s) {
        res.clear();
        path.clear();
        sort(s.begin(), s.end());
        vector<bool> used(s.size(), false);
        dfs(s, used);
        return res;
    }

    void dfs(string s, vector<bool>& used)
    {
        if (path.size() == s.size())
        {   
            res.push_back(path);
            return; 
        }
        for (int i = 0; i < s.size(); i ++)
        {    
            if (i > 0 && s[i] == s[i-1] && !used[i-1])
                continue;
            if (!used[i])
            {
                path += s[i];
                used[i] = true;
                dfs(s, used);
                used[i] = false;
                path.pop_back();
            }
        }
    }
};
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

39 数组中出现次数超过一半的数字

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int val, cnt;
        val = -1, cnt = 0;
        /*
        使用其他数字去抵消超过一半的数字，剩下的就是结果
        如果数字等于val，cnt++；
        如果数字不等于val，cnt--
        如果cnt=0，更新数字  val=nums[i], cnt = 1
        */
        for (int i = 0; i < nums.size(); i ++)
        {
            if (!cnt) val = nums[i], cnt =  1;
            else if (nums[i] == val) cnt ++;
            else cnt --;
        }
        return val;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

day5

40 最小的k个数

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        /*
        维护一个大根堆：因为大根堆元素比堆顶元素小
        */
        vector<int> res;
        priority_queue<int> heap;
        for (auto x : arr)
        {
            heap.push(x);
            if (heap.size() > k) heap.pop();
        }
        for (int i = 0; i < k; i ++)
        {
            res.push_back(heap.top());
            heap.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

41 数据流中位数

class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;
    MedianFinder() { }
    
    void addNum(int num) {
        max_heap.push(num);
        if (min_heap.size() && max_heap.top() > min_heap.top())
        {
            auto maxv = max_heap.top(), minv = min_heap.top();
            max_heap.pop(), min_heap.pop();
            max_heap.push(minv), min_heap.push(maxv);
        }
        if (max_heap.size() - min_heap.size() > 1)
        {
            min_heap.push(max_heap.top());
            max_heap.pop();
        }

    }
    
    double findMedian() {
        if (max_heap.size() + min_heap.size() & 1) return max_heap.top();
        else return (max_heap.top() + min_heap.top()) / 2.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

42 连续子数组最大和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int summ = 0;
        int res = INT_MIN;
        for (int i = 0; i < nums.size(); i ++)
        {
            //如果小于0从新开始计算数组和
            //以当前为结尾的前缀和
            summ = max(summ + nums[i], nums[i]);
            res = max(res, summ);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

43 1～n中1出现的次数

class Solution {
public:
    int countDigitOne(int n) {
        /*
        cur:当前位置
        left:cur左边
        right:cur右边  
        t: 10^右边的位数
        左边取0~left-1(cur肯定会有1) 右边可以取全部  left*t次
        左边取left的话，cur可能没有1
        当前cur是0时，res+= 0
        当前cur是1时，res+=right
        当前cur>1时，res+=t
        */
        if (!n) return 0;
        vector<int> nums;
        int res = 0;
        while(n) nums.push_back(n % 10), n /= 10;
        for (int i = nums.size() - 1; i >=0; i --)
        {
            int left = 0, right = 0, t = 1;
            for(int j = nums.size() - 1; j > i; j --) left = left * 10 + nums[j];
            for (int j = i - 1; j >=0; j --) right = right * 10 + nums[j], t *= 10;
            res += left * t;
            if (nums[i] == 1) res += right + 1;
            else if (nums[i] > 1) res += t;
            else res += 0;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

44 数字序列中某一位的数字

class Solution {
public:
    int findNthDigit(int n) {
        //确定是几位数 n-10-90*2-900*3-9000*4-..直到小于i*s 位数*9
        //确定该位数的第几个数  1000+235-1 =1234
        //属于该数的第几位  1234 % 
        long long i = 1, s = 9, base = 1;
        // 1 计算几位数i，剩下多少位n
        while (n > i * s)
        {
           n -= i * s;
           i ++;//位数+1
           s*= 10;//数量级扩大十倍
           base *=10; //基数扩大十倍
        }
        // 2 根据n,计算i位数的第多少个数字，下取整代替上取整
        //   计算n,属于i位数的第几位
        int number = base + (n + i - 1) /  i - 1;                 
        int r = n % i ? n % i : i;
        // 3 根据i，number，r 可以定位到真实的数字
        //  如果整除，那么就是最后一位，如果不整除，去掉r位后面的
        for (int j = 0; j < i - r; j ++) number /= 10;
        return number % 10;
    }
};
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

45 把数组排成最小的数

class Solution {
public:
/* 定义新的比较方式
   a < b  <=> ab < ba
   如果排好序的序列是  
   a1 a2 a3 a4.. an
   证明  假设最小序列是
   a1a2a4a3 ..an,且a4 > a3 即a4a3 > a3a4
   交换a3a4的位置显然可以得到更小的一个数
   a1a2|a3a4...an
*/
    static bool cmp(int a, int b)
    {
        auto as = to_string(a), bs = to_string(b);
        return as + bs < bs + as;
    }
    string minNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), cmp);
        string res;
        for (auto x: nums) res += to_string(x);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

46 数字翻译成字符串

class Solution {
public:
    int translateNum(int num) {
        /*
        1 状态表示 dp[i] 前i位数字有多少中不同表示
        2 状态计算 
            第i位数翻译成一位： dp[i-1] 
            i-1，i翻译成一位:   dp[i-2] 
                必须在10~25
            dp[i] = dp[i-1] + dp[i-2]
        3 边界
            dp[0] = 1
        */
        auto s = to_string(num);
        int n = s.size();
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i ++)
        {
            dp[i] = dp[i - 1];
            int t = (s[i - 2] - '0') * 10 + (s[i-1] - '0');
            if (t >=10 && t <= 25) dp[i] += dp[i - 2];
        }
        return dp[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

47 礼物的最大价值

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        /*
        1状态表示dp[i,j]走到当前各自能够获得的最大价值是多少      
        2 状态转移
           从上方dp[i-1,j] 或者从左边dp[i,j-1]的最大值
           dp[i,j] = max(dp[i-1,j],dp[i, j -1]) + grid[i][j]
        3 状态初始化   
           dp[i,0] = f[0,j] = 0; 
        */
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i ++)
            for (int j = 1; j <= n; j ++)
                dp[i][j] = max(dp[i-1][j], dp[i][j - 1])  + grid[i - 1][j - 1];
        return dp[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

48 最长不含重复子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        /*暴力做法
        先确定结尾，然后枚举前缀最长不重复子串
          双指针做法：借助哈希表
        如果i,j之间有重复，那么把i往后移动一位
        最后取最大值
        */
        unordered_map<char, int> cnt;
        int res = 0;
        for (int i = 0, j = 0; j < s.size(); j ++)
        {
            cnt[s[j]]++;
            if (cnt[s[j]] > 1)
            {
                while (cnt[s[i]] == 1)
                {
                    cnt[s[i]] --;
                    i++;
                }
                cnt[s[i]] --;
                i++;
            }
            res = max(res, j- i + 1);  
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

49 丑数

class Solution {
public:
    int nthUglyNumber(int n) {
        /*三路归并
        假设丑数序列为a1 a2 a3 a4 a5...
        设置三个序列
        nums1 = a1*2 a2*2 a3*2..
        nums2 = a1*3 a2*3 a3*3..
        nums3 = a1*5 a2*5 a3*5..
        那么这三个序列一定是丑数序列，如何避免遗漏呢？
        归并排序的思想
        t = min(2*dp[i],3*dp[j],5*dp[k])
        */
        if (n <= 1) return n;
        vector<int> dp(1, 1);
        int i = 0, j = 0, k = 0;
        long long  t = 0;
        while (--n)
        {
            t = min(min(2 * dp[i], 3 * dp[j]), 5 * dp[k]);
            if (t == 2 * dp[i]) i ++;
            if (t == 3 * dp[j]) j ++;
            if (t == 5 * dp[k]) k ++;
            dp.push_back(t);
        }
        return dp.back();
    }
}; 
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

50 第一个只出现一次的字符

class Solution {
public:
    char firstUniqChar(string s) {
        unordered_map<char, int> cnt;
        char res = ' ';
        for (auto x: s) cnt[x] ++;
        for (auto x: s)
            if (cnt[x] == 1) 
            {
                res =  x;
                break;
            }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

day6

51 数组中的逆序对

class Solution {
public:
    int merge_sort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return 0;
        int mid = l + r  >> 1;
        int res = merge_sort(nums, l, mid) + merge_sort(nums, mid + 1, r);
        vector<int> temp;
        int i = l, j = mid + 1;
        
        while (i <= mid && j <= r)
        {
            if (nums[i] > nums[j])
            {  
                temp.push_back(nums[j++]);
                res += mid - i + 1;
            }
            else  temp.push_back(nums[i++]);
        }

        while (i <= mid) temp.push_back(nums[i++]);
        while (j <= r) temp.push_back(nums[j++]);
        i = l;
        for (auto x: temp) nums[i++] = x;
        return res;
    }
    int reversePairs(vector<int>& nums) {
        //暴力做法：冒泡排序  n2
        // 归并排序模板题 nlogn
        return merge_sort(nums, 0, nums.size() - 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

52 两个链表的第一个公共节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        /*因为不等长，所以把两个链表拼接起来就登场了
          headA headB 时就相交了*/
        ListNode* prea = headA;
        ListNode* preb = headB;
        while (prea != preb)
        {

            prea = prea  != NULL? prea -> next: headB;
            preb = preb  != NULL? preb -> next: headA;
        }
        return prea;
        
    }
};
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

53I 排序数组中查找数字

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return 0;
        int l = 0, r = nums.size() - 1;
        // 分为三个区间
        // <target  =target > target
        while (l < r)
        {
            // 只要小于k就会往右走，直到找到左端点
            int mid = (l + r) / 2;
            if (nums[mid] < target) l = mid + 1;
            else r = mid;
        }
        
        if (nums[l] != target) return 0;
        int left = l;
        
        l = 0, r = nums.size() - 1;
        while (l < r)
        {
            //只要小于等于k就会往右走，直到找到做端点
            //l == mid时注意向上取整
            int mid = (l + r + 1) / 2;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        return r - left + 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

53II 0～n-1中缺失的数字

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int res = n * (n + 1) / 2; // 1~n 总共有n个数 
        for (auto x: nums) res -= x;
        return res;
    }
};


//二分查找
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] > mid) r = mid - 1;
            else if (nums[mid] == mid) l = mid + 1;
            else continue;
        }
        if (nums[l] == l) return l + 1;
        return l;
    }
};
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

53III 数组中数值和下标相等的元素

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

54 二叉搜索树的第k大节点

/**
 * 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* ans;
    int kthLargest(TreeNode* root, int k) {
        dfs(root, k);
        return ans->val;
    }

    void dfs(TreeNode* root, int& k)
    {
        if (!root) return;
        dfs(root-> right, k);
        k --;
        if (k == 0) ans = root;
        if (k > 0 ) dfs(root->left, k);
    }
};
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

55I 二叉树的深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        // 左子树深度+右子树深度+1
        if (!root) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};
1
2
3
4
5
6
7
8

55II 平衡二叉树

/**
 * 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:
    bool ans = true;
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode* root)
    {
        if (!root) return 0;
        int ldepth = dfs(root->left);
        int rdepth = dfs(root->right);
        if (abs(ldepth - rdepth) > 1) ans = false;
        return max(ldepth, rdepth) + 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

56I 数组中数字出现的次数

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        // 异或操作可以得到集合中计数为1的数（只能有1个）
        // 如果有两个  异或结果为 x^y 其二进制表示一定有一位为1，另一个数该位为0
        // 将所有数分成1集合和0集合，然后进行异或即可找出两个集合中计数为1的数
        int sum = 0;
        for (auto x: nums) sum ^= x;
        int k = 0;
        while (!(sum >> k & 1)) k ++;
        int first = 0;
        for (auto x: nums)
            if (x >> k & 1) 
                first ^= x;
        return vector<int>{first, sum ^ first};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

56II 数组中数字出现的次数

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // // 唯一数出现1次，其他出现3次
        // // 有限状态机
        // // 对于x的所有位（0,0）-> (1,0) -> (0,1) -> (0,0)
        // int ones = 0, twos = 0;
        // for (auto x: nums)
        // {
        //     ones = (ones ^ x) & (~twos);
        //     twos = (twos ^ x) & (~ones);
        // }
        // // ones相当于x的所有位 因为0遇到0->0  0遇到1->1
        // return ones;
        
        int ans = 0;
        for (int i = 0; i < 32; i ++)
        {   
            int cnt = 0;
            for (auto x: nums)
                if (x >> i & 1) cnt ++;
            if (cnt % 3)
                ans = ans | 1 << i;//%3=1的必定为唯一数
        }
        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

57I 和为s的数字

//两数之和
class Solution {
public:
    unordered_set<int> hash;
    vector<int> twoSum(vector<int>& nums, int target) {
        for (auto x: nums)
        {
            if (hash.count(target-x)) return vector<int> {target-x, x};
            else hash.insert(x);     
        } 
        return vector<int> {-1,-1};  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

57II 和为s的连续正数序列

//双指针的题目
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        for(int i = 1, j = 1 ,s = 1; i <= target; i ++)
        {
            while (s < target) s += ++ j;
            if (s == target && j - i + 1 > 1)
            {
                vector<int> line;
                for (int k = i; k <= j; k ++) line.push_back(k);
                res.push_back(line);

            }
            s -= i;//每次右移需要减去i
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

58I 翻转单词顺序

class Solution {
public:
    string reverseWords(string s) {
        string res;
        for (int i = 0; i < s.size(); i ++)
        {
            while (s[i] == ' ') i ++;//start of word
            int j = i;
            while (j < s.size() && s[j] != ' ') j ++;//end of word
            string word;
            for (int k = i; k < j; k ++) word += s[k];//word
            if (j < s.size()) res = ' ' + word + res;
            else if (j) res = word + res; 
            i = j;
        }
        return res[0] == ' '? res.substr(1) : res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

58II 左旋转字符串

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        // 全部翻转
        // 前n-k和翻转  后k个翻转
        reverse(s.begin(), s.end());
        reverse(s.begin(), s.begin() + s.size() - n);
        reverse(s.begin() + s.size() - n,s.end());
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11

59 队列的最大值

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

60I n个骰子的点数次数

// 可能的点数列表
// 背包问题：分组背包
class Solution {
public:
    vector<int> numberOfDice(int n) {
        vector<int> res;
        vector<int> dp(6 * n + 1, 0);//可能的得分
        for (int i = 1; i <= 6; i ++) dp[i] = 1;//第一次扔骰子1~6的投法都为1
        for (int i = 2; i <= n; i++) //分组数
            for (int j = 6 * i; j >= 0; j --) // 物品数 倒序遍历避免 当前dp[j-k]覆盖过去的dp[j-k]
            {   
                dp[j] = 0;//清空数组，dp[j]不会由上一个同一得分求出
                for (int k = 6; k >=1; k--)//价值
                    if (j > k) 
                        dp[j] += dp[j-k];
            }
        for (int i = n; i < 6 * n + 1; i ++) res.push_back(dp[i]);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

60II n个骰子的点数概率

//可能的点数对应的概率
class Solution {
public:
    vector<double> dicesProbability(int n) {
        //取值范围为n-6n  5n + 1中可能的值
        //dp[N][i] 表示有n颗骰子且和为i时的概率
        //dp[1][i] = 1/ 6
        //dp[2][i] = dp[1][i-1]+dp[1][i-2]...+dp[1][i-6]
        //res = dp[N]
        //当前骰子点数之和i+1,,i+2, i+6,只能由dp即过去的的i中递推过来
        //如果反向推到会导致数组越界
        vector<double> dp(6, 1.0/6.0);
        for (int i = 2; i <= n; i ++)
        {
            vector<double> temp(5*i + 1, 0.0);
            for (int j = 0; j < dp.size(); j ++)    
                for (int k = 0; k < 6; k ++)
                    temp[j + k] += dp[j] * (1.0/ 6.0);
            dp = temp;
        }
        return dp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

day7

61 扑克牌的顺子

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        /*1 删掉0
          2 重复
          3 差<=4  
        */
        if (!nums.size()) return false;
        sort(nums.begin(), nums.end());
        int k = 0;
        while (!nums[k]) k ++;
        for (int i = k + 1; i < nums.size(); i ++)
            if (nums[i] == nums[i-1]) 
                return false;
        return nums.back() - nums[k] <= 4;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

62 圆圈中最后剩下的数字（约瑟夫环）

class Solution {
public:
    int lastRemaining(int n, int m) {
        /*
        n个人每次删去第m个,最终剩下dp[n][m] 
        0 1 2 ...           m-1   m     m+1    m+2 ...n
        重新编号 .           ——    0     1      2  
        n-1个人则是，重新编号后的dp[n-1,m]  (此时原来的编号为 新的编号+m)%n右移了m位
        dp[n][m] = (dp[n-1][m] + m) % n
        dp[1][m] = 0
        */
        // vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        // for (int i = 2; i <= n; i ++)
        //     for (int j = 1; j <= m; j ++)
        //         dp[i][j] = (dp[i-1][j] + j) % i;
        // return dp[n][m];
        if (n == 1) return 0;
        return (lastRemaining(n - 1, m) + m) % n;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

63 股票的最大利润

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int res = 0;
        for (auto p: prices)
        {
            if (p < minPrice) minPrice = p;
            res = max(res, p - minPrice);
        }
        return res;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

64 1+2+…+n

class Solution {
public:
    int sumNums(int n) {
        int res = n;
        (n >0) && (res +=   sumNums(n- 1));
        return res;

    }
};
1
2
3
4
5
6
7
8
9

65 不用加减乘除的加法

class Solution {
public:
    int add(int a, int b) {
        // 位运算在计算机中的加法
        // a + b = cd 
        // d = a^b
        // c = a&b
        /*
        不考虑所有进位计算 a^b
        再加上所有进位     a&b 有进位的地方都是1，需要把结果左移1  a&b << 1;
        结果等于 a^b + a&b << 1 新的两个数相加
        b中的进位总会消失
        */
        while (b)
        {
            int sum1 = a ^ b;
            unsigned int carry = (unsigned int)(a & b) << 1;
            a =  sum1;
            b = carry;//
        }
        return a;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

66 构建乘积数组

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        if (!a.size()) return vector<int>();
        vector<int> res(a.size(),1);
        //左半边先乘进去 1 2 3 4 5
        // 1 1 2 6 24 
        for (int i = 0, lprod = 1; i < a.size(); i ++){
            res[i] = lprod;
            lprod*= a[i];      
        }
        //右半边再乘进去
        // i= 4  24*1  右边没有 rprod = 5
        // i= 3  6*5   右边是5 左边是123 rprod = 20
        // i= 2  2*20   左边是12 右边是45 rprod=60
        // i= 1  1*60   左边是1  rprod = 120
        // i= 0  120
        for (int i = a.size() - 1, rprod = 1; i >= 0; i --)
        {
            res[i]*= rprod;
            rprod*= a[i];
        }
        return res;

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

67 字符串转换为整数

class Solution {
public:
    int strToInt(string str) {
        int k = 0;
        while (k < str.size() && str[k] == ' ') k ++;
        long long num = 0;
        bool is_minus = false;
        if (str[k] == '+') k ++;
        else if (str[k] == '-')  
        {
            k++;
            is_minus=true;
        }
        while (k < str.size() && str[k] >= '0' && str[k] <= '9')
        {
            num = num * 10 +  str[k] - '0';
            k++;
            if (!is_minus && num > INT_MAX) return  INT_MAX;
            if (is_minus  && num > INT_MAX) return  INT_MIN;
        }
        if (is_minus) num *= -1;
        return (int)num;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

68 二叉树的最低公共祖先

/**
 * 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) return nullptr;
        if (root == p || root == q) return root;
        auto left = lowestCommonAncestor(root->left, p, q);//查找左子树中是否存在p q节点
        auto right = lowestCommonAncestor(root->right,p, q);//查找右子树中是否存在p q节点
        if (left && right) return root;
        else if (left) return left;
        return 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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/383792