剑指Offer

她的店里只卖樱花

发布于 2022-10-31 16:50:13

5920

发布于 2022-10-31 16:50:13

文章被收录于专栏：常用算法模板

1.找出数组中重复的数字

给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0 \sim n - 1的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 0 \sim n - 1 的范围内，或数组中不包含重复数字，则返回 -1；

数据范围

0 \le n \le 1000

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

题解

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        set<int> s;
        int res = -1;
        for(auto ite : nums)
        {
            if(ite < 0 || ite >= nums.size())
                return -1;
            if(s.count(ite))
                res = ite;
            s.insert(ite);
        }
        return res;
    }
};

2. 不修改数组找出重复的数字

2.不修改数组找出重复的数字

给定一个长度为 n + 1的数组nums，数组中所有的数均在 1 \sim n 的范围内，其中 n \ge 1。

请找出数组中任意一个重复的数，但不能修改输入的数组。

数据范围

1 \le n \le 1000

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

思考题：如果只能使用 O(1) 的额外空间，该怎么做呢？

题解

code 1
code 2

method1：用set判重

时间复杂度: O(n)

空间复杂度: O(n)

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        set<int> s;
        for(auto ite : nums)
        {
            if(s.count(ite))
                return ite;
            s.insert(ite);
        }
        return -1;
    }
};

</div>

method2: 抽屉原理

时间复杂度: O(nlogn)

空间复杂度: O(1)

可以将所有数的范围划分成[1, n / 2], [n / 2 + 1, n - 1]两个子区间，然后分别统计两个区间中数出现的个数，又根据抽屉原理如果有重复的数出现，那么必定有一个区间中数的个数大于区间的长度。

如此可以进行分治操作，每次我们可以把区间长度缩小一半，直到区间长度为1时，我们就找到了答案。

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        
        int l = 1, r = nums.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            int s = 0;
            for(auto ite : nums)
                s += ite >= l && ite <= mid;
            if(s > mid - l + 1) r = mid;
            else 
                l = mid + 1;
        }
        return l;
        
    }
};

</div></div></div>

3. 二维数组中的查找

3.二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

数据范围

二维数组中元素个数范围 [0,1000]

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

数据范围

二维数组中元素个数范围 [0,1000][0,1000]

样例

输入数组：

[
  [1,2,8,9]，
  [2,4,9,12]，
  [4,7,10,13]，
  [6,8,11,15]
]

如果输入查找数值为7，则返回true，

如果输入查找数值为5，则返回false

输入数组：

[
  [1,2,8,9]，
  [2,4,9,12]，
  [4,7,10,13]，
  [6,8,11,15]
]

如果输入查找数值为7，则返回true，

如果输入查找数值为5，则返回false

题解

method1：用set判重

class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        set<int> s;
        for(auto i : array)
            for(auto j : i)
                s.insert(j);
        return s.count(target) ? true : false;
    }
};

method2：判断每一行是否满足条件然后二分

class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        if(!array.size() || !array[0].size())
            return false;
        for(auto ite : array)
        {
            int n = ite.size();
            if(target >= ite[0] && target <= ite[n - 1])
            {
                int index = lower_bound(ite.begin(), ite.end(), target) - ite.begin();
                if(index != n && ite[index] == target)
                    return true;
            }
            
        }
        return false;
    }
};

4. 替换空格

4.替换空格

请实现一个函数，把字符串中的每个空格替换成"%20"。

数据范围

0 \le 输入字符串的长度 \le 1000 。注意输出字符串的长度可能大于 1000。

样例

输入："We are happy."

输出："We%20are%20happy."

题解

class Solution {
public:
    string replaceSpaces(string &str) {
        string res = "";
        for(auto s : str)
        {
            if(s == ' ')
                res += "%20";
            else 
                res += s;
        }
        return res;
    }
};

5. 从尾到头打印链表

5.从尾到头打印链表

输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

数据范围

0 \le 链表长度 \le 1000 。

样例

输入：[2, 3, 5]
返回：[5, 3, 2]

题解

method1：递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        if(!head)
            return {};
        auto res = printListReversingly(head->next);
        res.push_back(head->val);
        return res; 
    }
};

method2：用vector存储

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int> v;
        while(head)
            v.push_back(head->val), head = head->next;

        return vector<int>(v.rbegin(), v.rend());
    }
};

6. 重建二叉树

6.重建二叉树

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

注意:

二叉树中每个节点的值都互不相同；
输入的前序遍历和中序遍历一定合法；

数据范围

树中节点数量范围 [0,100]。

样例

给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
    3
   / \
  9  20
    /  \
   15   7

题解

/**
 * 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:
    unordered_map<int, int> mp;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = inorder.size();
        for(int i = 0; i < n; i ++)
            mp[inorder[i]] = i;
        return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
    }
    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int il, int ir, int pl, int pr){
        if(pl > pr || il > il) return NULL;
        int root = preorder[pl];
        int k = mp[root] - il; // 代表左右子树的宽度
        auto res = (TreeNode*)malloc(sizeof (struct TreeNode));
        res->val = root;
        res->left = dfs(preorder, inorder, il, il + k - 1, pl + 1, pl + k);
        res->right = dfs(preorder, inorder, il + k + 1, ir, pl + k + 1, pr);
        return res;
        
    }
};

7. 二叉树的下一个节点

7.二叉树的下一个节点

给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。

注意：

如果给定的节点是中序遍历序列的最后一个，则返回空节点;
二叉树一定不为空，且给定的节点一定不是空节点；

数据范围

树中节点数量 [0,100]。

样例

假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。

则应返回值等于3的节点。

解释：该二叉树的结构如下，2的后继节点是3。
  2
 / \
1   3

题解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        if(p->right)
        {
            p = p->right;
            while(p->left) p = p->left;
            return p;
        }
        cout << 1 << endl;
        while(p->father && p == p->father->right) p = p->father;
        cout << p->val << endl;
        return p->father;
        
    }
};

8. 用两个栈实现队列

8.用两个栈实现队列

请用栈实现一个队列，支持如下四种操作：

push(x) – 将元素x插到队尾；
pop() – 将队首的元素弹出，并返回该元素；
peek() – 返回队首元素；
empty() – 返回队列是否为空；

注意：

你只能使用栈的标准操作：push to top，peek/pop from top, size 和 is empty；
如果你选择的编程语言没有栈的标准库，你可以使用list或者deque等模拟栈的操作；
输入数据保证合法，例如，在队列为空时，不会进行pop或者peek等操作；

数据范围

每组数据操作命令数量 [0,100]。

样例

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

题解

class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        stk.push(x);
    }
    
    void copy(stack<int>& a, stack<int>& b){
        while(a.size())
        {
            b.push(a.top());
            a.pop();
        }
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        copy(stk, cache);
        int res = cache.top();
        cache.pop();
        copy(cache, stk);
        return res;
    }
    
    /** Get the front element. */
    int peek() {
        copy(stk, cache);
        int res = cache.top();
        copy(cache, stk);
        return res;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return stk.empty();
    }
public:
    stack<int> stk, cache;
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * bool param_4 = obj.empty();
 */

9. 斐波那契数列

9.斐波那契数列

输入一个整数 n ，求斐波那契数列的第 n 项。

假定从 0 开始，第 0 项为 0。

数据范围

0 \le n \le 39

样例

输入整数 n=5 

返回 5

题解

class Solution {
public:
    int Fibonacci(int n) {
        int l = 0, r = 1;
        for(int i = 0; i < n; i ++) 
        {
            int t = l + r;
            l = r;
            r = t;
        }
        return l;
    }
};

10. 旋转数组的最小数字

10.旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个升序的数组的一个旋转，输出旋转数组的最小元素。

例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转，该数组的最小值为 1。

数组可能包含重复项。

注意：数组内所含元素非负，若数组大小为 0，请返回 -1。

数据范围

数组长度 [0,90]。

样例

输入：nums = [2, 2, 2, 0, 1]

输出：0

题解

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size() - 1;
        if(n < 0) return -1;
        while(n >= 0 && nums[n] == nums[0]) n -- ;
        if(nums[n] >= nums[0]) return nums[0];
        int l = 0, r = n;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] < nums[0]) r = mid;
            else 
                l = mid + 1;
        } 
        return nums[l];
    }
};

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(!nums.size())
            return -1;
        for(int i = 1; i < nums.size(); i ++)
            if(nums[i] < nums[i - 1])
                return nums[i];
            
        return nums[0];
    }
};

11. 矩阵中的路径

11.矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

注意：

输入的路径不为空；
所有出现的字符均为大写英文字母；

数据范围

矩阵中元素的总个数 [0,900]。路径字符串的总长度 [0,900]。

样例

matrix=
[
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]

str="BCCE" , return "true" 

str="ASAE" , return "false"

题解

class Solution {
public:

    bool dfs(vector<vector<char>>& matrix, string &str, int u, int x, int y){
        if(str[u] != matrix[x][y]) return false;
        if(u == str.size() - 1)
            return true; 
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        char t = matrix[x][y];
        matrix[x][y] = '*';
        for(int i = 0; i < 4; i ++)
        {
            int a = dx[i] + x, b = dy[i] + y;
            if(a < 0 || b < 0 || a >= matrix.size() || b >= matrix[0].size())
                continue;
            if(dfs(matrix, str, u + 1, a, b))
                return true;
            
        }
        matrix[x][y] = t;
        return false;
    }

    bool hasPath(vector<vector<char>>& matrix, string &str) {
        int n = matrix.size();
        if(!n)
            return false;
        int m = matrix[0].size();
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
                if(dfs(matrix, str, 0, i, j))
                    return true;
        return false;
    }
};

12. 机器人的运动范围

12.机器人的运动范围

地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0 \sim m - 1 和 0 \sim n - 1。

一个机器人从坐标 (0,0) 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

请问该机器人能够达到多少个格子？

注意:

0<=m<=50
0<=n<=50
0<=k<=100

样例1

输入：k=7, m=4, n=5

输出：20

样例2

输入：k=18, m=40, n=40

输出：1484

解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
      但是，它不能进入方格（35,38），因为3+5+3+8 = 19。

题解

class Solution {
public:
    
    int g[51][51];
    bool st[51][51];
    
    int getNum(int x){
        int t = 0;
        while(x) t += x % 10, x /= 10;
        return t;
    }
    
    int bfs(int n, int m){
        if(!n || !m)
            return 0;
        queue<pair<int, int>> q;
        q.push({0, 0});
        memset(st, false, sizeof st);
        st[0][0] = true;
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        int cnt = 0;
        while(q.size())
        {
            auto t = q.front();
            q.pop();
            cnt ++ ;
            for(int i = 0; i < 4; i ++)
            {
                int a = dx[i] + t.first, b = dy[i] + t.second;
                if(a < 0 || b < 0 || a >= n || b >= m || g[a][b] || st[a][b])
                    continue;
                st[a][b] = true;
                q.push({a, b});   
            }
            
        }
        return cnt;
    }
    
    int movingCount(int threshold, int n, int m)
    {
        
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
                if(getNum(i) + getNum(j) <= threshold)
                    g[i][j] = 0;
                else
                    g[i][j] = 1;
        return bfs(n, m);
    }
};

13. 剪绳子

13.剪绳子

给你一根长度为 n 绳子，请把绳子剪成 m段（m、n 都是整数，2 \le n \le 58 并且 m \ge 2）。

每段的绳子的长度记为 k[1]、k[2]、……、k[m]。

k[1]k[2] … k[m] 可能的最大乘积是多少？

例如当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到最大的乘积 18。

样例

输入：8

输出：18

题解

class Solution {
public:
    
    int maxProductAfterCutting(int length) {
        if(length <= 3)
            return 1 * (length - 1);
        int res = 1;
        if(length % 3 == 1)
            length -= 4, res *= 4;
        if(length % 3 == 2)
            length -= 2, res *= 2;
        return res * pow(3, length / 3);
    }
};

class Solution {
public:
    
    int maxProductAfterCutting(int length) {
        int f[60] = {0};
        f[1] = 1;
        for(int i = 2; i <= length; i ++)
            for(int j = 1; j < i; j ++)
                f[i] = max(f[i], max((i - j) * j, f[i - j] * j));
        return f[length];
    }
};

14.二进制中1的个数

输入一个 32 位整数，输出该数二进制表示中 1 的个数。

注意：

负数在计算机中用其绝对值的补码来表示。

数据范围

-100 \le 输入整数 \le 100

样例1

输入：9
输出：2
解释：9的二进制表示是1001，一共有2个1。

样例2

输入：-2
输出：31
解释：-2在计算机里会被表示成11111111111111111111111111111110，
      一共有31个1。

题解

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        for(int i = 0; i < 32; i ++)
            res += n >> i & 1;
        return res;
    }
};

15. 数值的整数次方

15.数值的整数次方

实现函数double Power(double base, int exponent)，求base的 exponent次方。

不得使用库函数，同时不需要考虑大数问题。

只要输出结果与答案的绝对误差不超过 10^{-2} 即视为正确。

注意：

不会出现底数和指数同为0的情况
当底数为0时，指数一定为正
底数的绝对值不超过 10，指数的绝对值不超过 10^9。

样例1

输入：10 ，2

输出：100

样例2

输入：10 ，-2  

输出：0.01

题解

class Solution {
public:

    double Power(double base, int exponent) {
        double res = 1;
        long long t = abs((long long)exponent);
        while(t)
        {
            if(t & 1)
                res *= base;
            base *= base;
            t >>= 1;
        }
        if(exponent < 0)
            return 1.0 / res;
        return res;
    }
};

16. 在O(1)时间删除链表结点

16.在O(1)时间删除链表结点

给定单向链表的一个节点指针，定义一个函数在O(1)时间删除该结点。

假设链表一定存在，并且该节点一定不是尾节点。

数据范围

链表长度 [1,500]。

样例

输入：链表 1->4->6->8
      删掉节点：第2个节点即6（头节点为第0个节点）

输出：新链表 1->4->8

题解

/**
 * 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 = *node->next;
    }
};

17. 删除链表中重复的节点

17.删除重复的节点

在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，重复的节点不保留。

数据范围

链表中节点 val 值取值范围 [0,100]。链表长度 [0,100]。

样例1

输入：1->2->3->3->4->4->5

输出：1->2->5

样例2

输入：1->1->1->2->3

输出：2->3

题解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        ListNode* temp = new ListNode(-1); 
        temp->next = head;
        auto p = temp;
        while(p->next)
        {
            auto q = p->next;
            while(q && p->next->val == q->val) q = q->next;
            if(p->next->next == q) p = p->next;
            else 
                p->next = q;
        }
        return temp->next;
    }
};

18. 正则表达式匹配

18.正则表达式匹配

请实现一个函数用来匹配包括'.'和'*'的正则表达式。

模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。

数据范围

输入字符串长度 [0,300]。

样例

输入：

s="aa"
p="a*"

输出:true

题解

19. 表示数值的字符串

19.表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。

但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

注意:

小数可以没有整数部分，例如.123等于0.123；
小数点后面可以没有数字，例如233.等于233.0；
小数点前面和后面可以有数字，例如233.666;
当e或E前面没有数字时，整个字符串不能表示数字，例如.e1、e1；
当e或E后面没有整数时，整个字符串不能表示数字，例如12e、12e+5.4;

数据范围

输入字符串长度 [0,25]。字符串中不含空格。

样例：

输入: "0"

输出: true

题解

class Solution {
public:
    bool isNumber(string s) {
        int n = s.size();
        int i = 0;
        bool flg;
        while(s[i] == ' ') ++ i;
        if(s[i] == '+' || s[i] == '-')
            ++ i;
        while(isdigit(s[i]))
            ++ i, flg = true;
        if(s[i] == '.')
            ++ i;
        while(isdigit(s[i]))
            ++ i, flg = true;
        if(flg && (toupper(s[i]) == 'E'))
        {
            ++ i, flg = false;
            if(s[i] == '+' || s[i] == '-')
                ++ i;
            while(isdigit(s[i]))
                ++ i, flg = true;
        }
        return (i == n && flg);
    }
};

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

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

输入一个整数数组，实现一个函数来调整该数组中数字的顺序。

使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

数据范围

数组长度 [0,100]。

样例

输入：[1,2,3,4,5]

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

题解

class Solution {
public:

    void reOrderArray(vector<int> &array) {
         int n = array.size();
         int l = 0, r =  n - 1;
         while(l < r)
         {
             while(l < n && array[l] & 1) l ++ ;
             while(r >= 0 && array[r] % 2 == 0) r -- ;
             if(l < r)
                swap(array[l], array[r]);
         }
    }
};

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

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

输入一个链表，输出该链表中倒数第 kk 个结点。

注意：

k >= 1;
如果 kk 大于链表长度，则返回 NULL;

数据范围

链表长度 [0,30][0,30]。

样例

输入：链表：1->2->3->4->5 ，k=2

输出：4

题解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* head, int k) {
        int cnt = 0;
        vector<ListNode* > v;
        while(head)
        {
            v.push_back(head);
            head = head->next;
        }
        if(k > v.size())
            return NULL;
        reverse(v.begin(), v. end());
        return v[k - 1];
    }
};

22. 链表中环的入口结点

22.链表中环的入口结点

给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出null。

数据范围

节点 val 值取值范围 [1,1000]。链表长度 [0,500]。

样例

给定如上所示的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.

题解

method1：用set判重

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        set<ListNode*> s;
        auto temp = head;
        while(temp)
        {
            if(s.count(temp))
                return temp;
            s.insert(temp);
            temp = temp->next;
        }
        return NULL;
    }
};

method2：快慢指针

**(链表，快慢指针扫描) O(n)

本题的做法比较巧妙。用两个指针 first, second 分别从起点开始走，first 每次走一步，second 每次走两步。如果过程中 second 走到null，则说明不存在环。否则当 first 和 second 相遇后，让 first 返回起点，second 待在原地不动，然后两个指针每次分别走一步，当相遇时，相遇点就是环的入口。

证明：如上图所示，a 是起点，b 是环的入口，c 是两个指针的第一次相遇点，ab之间的距离是 x，bc 之间的距离是 y。则当 first 走到 b 时，由于 second 比 first 多走一倍的路，所以 second 已经从 b 开始在环上走了 x 步，可能多余1圈，距离 b 还差 y 步（这是因为第一次相遇点在 b 之后 y 步，我们让 first 退回 b 点，则 second 会退 2y 步，也就是距离 b 点还差 y 步）；所以 second从 b 点走 x + y 步即可回到 b 点，所以 second 从 c 点开始走，走 x 步即可恰好走到 b 点，同时让 first 从头开始走，走 x 步也恰好可以走到 b 点。所以第二次相遇点就是 b 点。

时间复杂度

first总共走了 2x + y 步，second 总共走了 2x + 2y + x 步，所以两个指针总共走了 5x + 3y 步。由于当第一次 first 走到 b 点时，second 最多追一圈即可追上 first，所以 y 小于环的长度，所以 x+y 小于等于链表总长度。所以总时间复杂度是 O(n)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        auto l = head, r = head;
        while(l && r)
        {
            l = l->next;
            r = r->next;
            if(r) r = r->next;
            else
                return NULL;
            if(l == r)
            {
                l = head;
                while(l != r)
                {
                    l = l->next;
                    r = r->next;
                }
                return r;
            }
        }
        return NULL;
    }
};

23. 反转链表

23.反转链表

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

思考题：

请同时实现迭代版本和递归版本。 数据范围

链表长度 [0,30]。

样例

输入:1->2->3->4->5->NULL

输出:5->4->3->2->1->NULL

题解

/**
 * 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){
        if(!head || !head->next)
            return head;
        auto tail = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return tail;
    }
};

/**
 * 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) {
        if(!head || !head->next) return head;
        auto a = head, b = a->next;
        while(b)
        {
            auto c = b->next;
            b->next = a;
            a = b, b = c;
        }
        head->next = NULL;
        return a;
    }
};

24. 合并两个排序的链表

24.合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

数据范围

链表长度 [0,500]。

样例

输入：1->3->5 , 2->4->5

输出：1->2->3->4->5->5

题解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        auto res = new ListNode(-1);
        auto r = res;
        while(l1 && l2)
        {
            int a = l1->val, b = l2->val;
            res->next = a < b ? l1 : l2;
            a < b ? l1 = l1->next : l2 = l2->next;
            res = res->next;
        }
        res->next = l1 ? l1 : l2;
        return r->next;
    }
};

25. 树的子结构

25.树的子结构

输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。

我们规定空树不是任何树的子结构。

数据范围

每棵树的节点数量 [0,1000]。

样例

树 A：

树 B：

  8
 / \
9   2

返回 true，因为 B 是 A 的子结构。

题解

/**
 * 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 hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!pRoot1 || !pRoot2)
            return false;
        if(isSame(pRoot1, pRoot2))
            return true;
        return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
    }
    bool isSame(TreeNode* pRoot1, TreeNode* pRoot2){
        if(!pRoot2)
            return true;
        if(!pRoot1 || pRoot1->val ^ pRoot2->val)
            return false;
        return isSame(pRoot1->left, pRoot2->left) && isSame(pRoot1->right, pRoot2->right);
    }
};

26. 二叉树的镜像

26.二叉树的镜像

输入一个二叉树，将它变换为它的镜像。

数据范围

树中节点数量 [0,100]。

样例

输入树：
      8
     / \
    6  10
   / \ / \
  5  7 9 11

 [8,6,10,5,7,9,11,null,null,null,null,null,null,null,null] 
输出树：
      8
     / \
    10  6
   / \ / \
  11 9 7  5

 [8,10,6,11,9,7,5,null,null,null,null,null,null,null,null]

题解

/**
 * 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:
    void mirror(TreeNode* root) {
        if(!root)
            return; 
        swap(root->left, root->right);
        mirror(root->left);
        mirror(root->right);
    }
};

27. 对称的二叉树

27.对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。

如果一棵二叉树和它的镜像一样，那么它是对称的。

数据范围

树中节点数量 [0,100]。

样例

如下图所示二叉树[1,2,2,3,4,4,3,null,null,null,null,null,null,null,null]为对称二叉树：
    1
   / \
  2   2
 / \ / \
3  4 4  3

如下图所示二叉树[1,2,2,null,4,4,3,null,null,null,null,null,null]不是对称二叉树：
    1
   / \
  2   2
   \ / \
   4 4  3

题解

/**
 * 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) {
        return !root || dfs(root->left, root->right);
    }
    
    bool dfs(TreeNode* l, TreeNode* r){
        if(!l || !r) return !r && !l; 
        return l->val == r->val && dfs(l->left, r->right) && dfs(l->right, r->left);
    }
};

28. 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

数据范围

矩阵中元素数量 [0,400]。

样例

输入：
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]

输出：[1,2,3,4,8,12,11,10,9,5,6,7]

题解

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> res;
        if(matrix.empty() || matrix[0].empty())
            return {};
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        int d = 1;
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<bool> > st(n, vector<bool>(m, false));
        int x = 0, y = 0;
        st[x][y] = true;
        res.push_back(matrix[0][0]);
        while(1)
        {
            int a = dx[d] + x, b = dy[d] + y;
            if(a < 0 || a >= n || b < 0 || b >= m || st[a][b])
            {
                d = (d + 1) % 4;
                a = dx[d] + x, b = dy[d] + y;
            }
            x = a, y = b;
            st[a][b] = true; 
            res.push_back(matrix[a][b]);
            if(res.size() >= n * m) 
                return res;
        }
        return res;
    }
};

29. 包含min函数的栈

设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈。

push(x)–将元素x插入栈中
pop()–移除栈顶元素
top()–得到栈顶元素
getMin()–得到栈中最小元素

数据范围

操作命令总数 [0,100]。

样例

MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin();   --> Returns -4.
minStack.pop();
minStack.top();      --> Returns 3.
minStack.getMin();   --> Returns -1.

题解

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s;
    stack<int> Min;
    MinStack() {
        
    }
    
    void push(int x) {
        s.push(x);
        if(!Min.size() || Min.top() >= x)
            Min.push(x);
    }
    
    void pop() {
        if(Min.top() == s.top())
            Min.pop();
        s.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return Min.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();
 */

30. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

假设压入栈的所有数字均不相等。

例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。

注意：若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。

数据范围

序列长度 [0,1000]。

样例

输入：[1,2,3,4,5]
      [4,5,3,2,1]

输出：true

题解

class Solution {
public:
    bool isPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size() ^ popV.size())
            return false;
        stack<int> s; 
        int idx = 0;
        for(int i = 0; i < pushV.size(); i ++)
        {
            s.push(pushV[i]);
            while(!s.empty() && s.top() == popV[idx])
                ++ idx, s.pop();
        }
        return s.empty();
    }
};

31. 不分行从上往下打印二叉树

从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。

数据范围

树中节点的数量 [0,1000]。

样例

输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
    8
   / \
  12  2
     /
    6
   /
  4

输出：[8, 12, 2, 6, 4]

题解

/**
 * 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> printFromTopToBottom(TreeNode* root) {
        if(!root)
            return {};
        queue<TreeNode* > q;
        q.push(root);
        vector<int> v;
        v.push_back(root->val);
        while(q.size())
        {
            auto t = q.front();
            q.pop();
            auto l = t->left;
            auto r = t->right;
            if(l)
                v.push_back(l->val), q.push(l);
            if(r)
                v.push_back(r->val), q.push(r);
        }
        return v;
    }
};

32. 分行从上往下打印二叉树

从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。

数据范围

树中节点的数量 [0,1000]。

样例

输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
    8
   / \
  12  2
     /
    6
   /
  4

输出：[[8], [12, 2], [6], [4]]

题解

/**
 * 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:
    int cnt;
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        if(!root)
            return {};
        auto head = root;
        vector<vector<int> > res;
        vector<int> v;
        queue<TreeNode* > q;
        q.push(root);
        q.push(NULL);
        while(q.size())
        {
            auto t = q.front();
            q.pop();
            if(t)
            {
                v.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            else 
            {
                if(q.size())
                    q.push(NULL);
                res.push_back(v);
                v.clear();
            }
            
        }
        return res;
    }
    void dfs(TreeNode* root, int depth){
        if(!root)
        {
            cnt = max(cnt, depth - 1);
            return;
        }
        dfs(root->left, depth + 1);
        dfs(root->right, depth + 1);
    }
};

33. 之字形打印二叉树

请实现一个函数按照之字形顺序从上向下打印二叉树。

即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

数据范围

树中节点的数量 [0,1000]。

样例

输入如下图所示二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]
    8
   / \
  12  2
     / \
    6   4
输出：[[8], [2, 12], [6, 4]]

题解

/**
 * 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>> printFromTopToBottom(TreeNode* root) {
        int cnt = 0;
        if(!root)
            return {};
        vector<vector<int> > res;
        vector<int> v;
        queue<TreeNode*> q;
        q.push(root);
        q.push(NULL);
        while(q.size())
        {
            auto t = q.front();
            q.pop();
            if(t)
            {
                v.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
                
            }
            else 
            {
                if(cnt & 1)
                    res.push_back(vector<int>(v.rbegin(), v.rend()));
                else 
                    res.push_back(v);
                if(q.size())
                    q.push(NULL);
                
                v.clear();
                cnt ++ ;
            }
        }
        return res;
    }
};

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

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。

数据范围

数组长度 [0,1000]。

样例

输入：[4, 8, 6, 12, 16, 14, 10]

输出：true

题解

class Solution {
public:
    vector<int> seq;
    bool verifySequenceOfBST(vector<int> sequence) {
        seq = sequence;
        if(!seq.size())
            return true;
        return dfs(0, seq.size() - 1);
    }
    bool dfs(int l, int r){
        if(l >= r)
            return true;
        int root = seq[r];
        int k = l; 
        while(l < r && seq[k] < root) k ++ ;
        for(int i = k; i < r; i ++)
            if(seq[i] < root)
                return false;
        return dfs(l, k - 1) && dfs(k, r - 1);
    }
};

35. 二叉树中和为某一值的路径

输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。

从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

保证树中结点值均不小于 00。

数据范围

树中结点的数量 [0,1000][0,1000]。

样例

给出二叉树如下所示，并给出num=22。
      5
     / \
    4   6
   /   / \
  12  13  6
 /  \    / \
9    1  5   1

输出：[[5,4,12,1],[5,6,6,5]]

题解

/**
 * 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> path;
    vector<vector<int> > res;
    int ans;
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        ans = sum;
        dfs(root, 0);
        return res;
    }
    void dfs(TreeNode* root, int sum){
        if(!root)
            return;
        path.push_back(root->val);
        sum += root->val;
        if(sum == ans && !root->left && !root->right)
            res.push_back(path);
        dfs(root->left, sum); 
        dfs(root->right, sum);
        path.pop_back();
    }
};

36. 复杂链表的复刻

请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

注意：

函数结束后原链表要与输入时保持一致。

数据范围

链表长度 [0,500]。

题解

/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        unordered_map<ListNode*, ListNode*> mp;
        mp[NULL] = NULL;
        auto res = new ListNode(-1), tail = res;
        while(head)
        {
            if(!mp.count(head)) mp[head] = new ListNode(head->val);
            if(!mp.count(head->random)) mp[head->random] = new ListNode(head->random->val);
            tail->next = mp[head];
            tail->next->random = mp[head->random];
            
            tail = tail->next;
            head = head->next;
            
        }
        return res->next;
    }
};

37. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点，只能调整树中结点指针的指向。

注意：

需要返回双向链表最左侧的节点。

例如，输入下图中左边的二叉搜索树，则输出右边的排序双向链表。

数据范围

树中节点数量 [0,500]。

题解

38. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

您需要确保二叉树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。

数据范围

树中节点数量 [0,1000]。

样例

你可以序列化如下的二叉树
    8
   / \
  12  2
     / \
    6   4

为："[8, 12, 2, null, null, 6, 4, null, null, null, null]"

注意:

以上的格式是AcWing序列化二叉树的方式，你不必一定按照此格式，所以可以设计出一些新的构造方式。

题解

39. 数字排列

输入一组数字（可能包含重复数字），输出其所有的排列方式。

数据范围

输入数组长度 [0,6]。

样例

输入：[1,2,3]

输出：
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]

题解

class Solution {
public:
    vector<vector<int> > res;
    vector<int> path;
    set<vector<int> > s;
    bool st[10];
    
    void dfs(int u, vector<int>& nums){
        if(u == nums.size())
        {
            if(!s.count(path))
            res.push_back(path), s.insert(path);
            return;
        }
        for(int i = 0; i < nums.size(); i ++)
            if(!st[i])
            {
                st[i] = true;
                path.push_back(nums[i]);
                dfs(u + 1, nums);
                path.pop_back();
                st[i] = false;
            }
    }
    
    vector<vector<int>> permutation(vector<int>& nums) {
        dfs(0, nums);
        return res;
    }
};

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

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

假设数组非空，并且一定存在满足条件的数字。

思考题：

假设要求只能使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？

数据范围

数组长度 [1,1000]。

样例

输入：[1,2,1,1,3]

输出：1

题解

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt = 1, val = nums[0];
        for(int i = 0; i < nums.size(); i ++)
        {
            if(nums[i] == val) 
                cnt ++ ; 
            else cnt -- ; 
            if(cnt == 0)
                val = nums[i], cnt = 1;
        }
        return val;
    }
};

41. 最小的k个数

输入 n 个整数，找出其中最小的 k 个数。

注意：

输出数组内元素请按从小到大顺序排序;

数据范围

1 \le k \le n \le 1000

样例

输入：[1,2,3,4,5,6,7,8] , k=4

输出：[1,2,3,4]

题解

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        priority_queue<int, vector<int>, greater<int> > q;
        for(auto ite : input)
            q.push(ite);
        for(int i = 0; i < k; i ++)
            res.push_back(q.top()), q.pop();
        return res;
    }
};

42. 数据流中的中位数

如何得到一个数据流中的中位数？

如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。

如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

数据范围

数据流中读入的数据总数 [1,1000]。

样例

输入：1, 2, 3, 4

输出：1,1.5,2,2.5

解释：每当数据流读入一个数据，就进行一次判断并输出当前的中位数。

题解

43. 连续子数组的最大和

输入一个非空整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为 O(n)。

数据范围

数组长度 [1,1000] 。数组内元素取值范围 [-200,200]。

样例

输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

题解

class Solution {
public:
    int f[1010];
    int maxSubArray(vector<int>& nums) {
        int res = -1e9;
        for(int i = 0; i < nums.size(); i ++)
        {
            f[i] = max(f[i - 1] + nums[i], nums[i]);
            res = max(f[i], res);
        }
        return res;
    }
};

44. 从从1到n整数中1出现的次数

题解

45. 数字序列中某一位的数字

数字以 0123456789101112131415… 的格式序列化到一个字符序列中。

在这个序列中，第 5 位（从 0 开始计数）是 5，第 13 位是 1，第 19 位是 4，等等。

请写一个函数求任意位对应的数字。

数据范围

0 \le 输入数字 \le 2147483647

样例

输入：13

输出：1

题解

class Solution {
public:
    const int N = 2147483647;
    int digitAtIndex(int n) {
        long long i = 1, num = 9, base = 1;
        while(n > i * num)
        {
            n -= i * num;
            i ++ ;
            num *= 10;
            base *= 10;
        }
        // 向上取整加上 i - 1
        int number = base + (n + i - 1) / i - 1;
        int r = n % i ? n % i : i;
        string str = to_string(number);
        return str[r - 1] - '0';
        for(int j = 0; j < i - r; j ++) number /= 10;
        return number % 10;
    }
};

46. 把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

例如输入数组 [3, 32, 321]，则打印出这 3 个数字能排成的最小数字 321323。

数据范围

数组长度 [0,500]。

样例

输入：[3, 32, 321]

输出：321323

注意：输出数字的格式为字符串。

题解

class Solution {
public:
    
    static bool cmp(string a, string b){
        return a + b < b + a;
    }
    
    string printMinNumber(vector<int>& nums) {
        
        vector<string> strnum;
        string str = "";
        for(auto ite : nums)
            strnum.push_back(to_string(ite));
        sort(strnum.begin(), strnum.end(), cmp);
        for(auto ite : strnum)
            str += ite;
        return str;
    }
};

47. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：

0 翻译成 a，1 翻译成 b，……，11 翻译成 l，……，25 翻译成 z。

一个数字可能有多个翻译。

例如 12258 有 5 种不同的翻译，它们分别是 bccfi、bwfi、bczi、mcfi 和 mzi。

请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

数据范围

输入数字位数 [1,101]。

样例

输入："12258"

输出：5

题解

class Solution {
public:
    int f[110];
    int getTranslationCount(string s) {
        f[0] = 1;
        int n = s.size();
        for(int i = 1; i <= n; i ++)
        {
            f[i] = f[i - 1];
            int t = 0;
            if(i >= 2)
                t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
            if(t >= 10 && t <= 25)
                f[i] += f[i - 2];
        }
        return f[n];
    }
};

48. 礼物的最大价值

在一个 m \times n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。

你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格直到到达棋盘的右下角。

给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？

注意：

m, n \gt 0
m \times n \le 1350

样例：

输入：
[
  [2,3,1],
  [1,7,1],
  [4,6,1]
]

输出：19

解释：沿着路径 2→3→7→6→1 可以得到拿到最大价值礼物。

题解

class Solution {
public:
    int f[1360][1360];
    int getMaxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + grid[i - 1][j - 1];
        return f[n][m];
    }
};

49. 最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

假设字符串中只包含从 a 到 z 的字符。

数据范围

输入字符串长度 [0,1000]。

样例

输入："abcabc"

输出：3

题解

class Solution {
public:
    int s[200];
    int longestSubstringWithoutDuplication(string str) {
        int n = str.size();
        int len = 0;
        for(int i = 0, j = 0; i < n; i ++)
        {
            s[str[i]] ++ ;
            while(s[str[i]] > 1)
                s[str[j ++ ]] -- ;
            len = max(i - j + 1, len);
        }
        return len;
    }
};

50. 丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。

例如 6、8 都是丑数，但 14 不是，因为它包含质因子 7。

求第 n 个丑数的值。

数据范围

1 \le n \le 1000

样例

输入：5

输出：5

注意：习惯上我们把 11 当做第一个丑数。

题解

class Solution {
public:
    int getUglyNumber(int n) {
        vector<int> q(1, 1);
        int i = 0, j = 0, k = 0;
        while(-- n) 
        {
            int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5));
            q.push_back(t);
            if(q[i] * 2 == t)
                i ++ ;
            if(q[j] * 3 == t)
                j ++ ;
            if(q[k] * 5 == t)
                k ++ ;
        }
        return q.back();
        
    }
};

51. 字符串中第一个只出现一次的字符

在字符串中找出第一个只出现一次的字符。

如输入"abaccdeff"，则输出b。

如果字符串中不存在只出现一次的字符，返回 # 字符。

数据范围

输入字符串长度 [0,1000]。

样例：

输入："abaccdeff"

输出：'b'

题解

class Solution {
public:
    unordered_map<char, int> mp;
    char firstNotRepeatingChar(string s) {
        for(auto ite : s)
            mp[ite] ++ ;
        for(auto ite : s)
            if(mp[ite] == 1)
                return ite;
        return '#';
    }
};

52. 字符流中第一个只出现一次的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。

例如，当从字符流中只读出前两个字符 go 时，第一个只出现一次的字符是 g。

当从该字符流中读出前六个字符 google 时，第一个只出现一次的字符是 l。

如果当前字符流没有存在出现一次的字符，返回 # 字符。

数据范围

字符流读入字符数量 [0,1000]。

样例

输入："google"

输出："ggg#ll"

解释：每当字符流读入一个字符，就进行一次判断并输出当前的第一个只出现一次的字符。

题解

class Solution{
public:
    map<char, int> mp;
    queue<char> q;
    //Insert one char from stringstream
    void insert(char ch){
        if(++ mp[ch] > 1)
            while(q.size() && mp[q.front()] > 1) q.pop();
        else 
            q.push(ch);
    }
    //return the first appearence once char in current stringstream
    char firstAppearingOnce(){
        return q.size() ? q.front() : '#';
    }
};

53. 数组中的逆序对

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

输入一个数组，求出这个数组中的逆序对的总数。

数据范围

给定数组的长度 [0,100]。

样例

输入：[1,2,3,4,5,6,0]

输出：6

题解

class Solution {
public:
    vector<int> v;
    int q[110];
    int merge_sort(int l, int r){
        if(l >= r)
            return 0;
        int mid = l + r >> 1;
        int res = merge_sort(l, mid) + merge_sort(mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        while(i <= mid && j <= r)
        {
            if(v[i] <= v[j])
                q[k ++ ] = v[i ++ ]; 
            else 
            {
                res += mid - i + 1;
                q[k ++ ] = v[j ++ ];
            }
        }
        while(i <= mid)
            q[k ++ ] = v[i ++ ];
        while(j <= r)
            q[k ++ ] = v[j ++ ];
        for(i = 0, j = l; j <= r; i ++ , j ++)
            v[j] = q[i];
        return res;
    }
    int inversePairs(vector<int>& nums) {
        v = nums;
        int n = v.size();
        int res = merge_sort(0, n - 1);
        return res;
    }
};

54. 两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点。

当不存在公共节点时，返回空节点。

数据范围

链表长度 [1,2000]。

样例

给出两个链表如下所示：
A：        a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

输出第一个公共节点c1

题解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        if(!headB || !headA)
            return NULL;
        auto p = headA, q = headB;
        while(p != q)
        {
            p = p ? p->next : headB;
            q = q ? q->next : headA;
        }
        return q;
    }
};

55. 数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。

例如输入排序数组 [1, 2, 3, 3, 3, 3, 4, 5] 和数字 3，由于 3 在这个数组中出现了 4 次，因此输出 4。

数据范围

数组长度 [0,1000]。

样例

输入：[1, 2, 3, 3, 3, 3, 4, 5] ,  3

输出：4

题解

class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        int l = lower_bound(nums.begin(), nums.end(), k) - nums.begin();
        int r = upper_bound(nums.begin(), nums.end(), k) - nums.begin();
        return r - l;
    }
};

56. 0到n-1中缺失的数字

一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 到 n-1 之内。

在范围 0 到 n-1 的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

数据范围

1 \le n \le 1000

样例

输入：[0,1,2,4]

输出：3

题解

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if(!nums.size())
            return 0;
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] ^ mid) r = mid;
            else 
                l = mid + 1;
        }
        if(nums[l] == l) l ++ ;
        return l;
    }
};

57. 数组中数值和下标相等的元素

假设一个单调递增的数组里的每个元素都是整数并且是唯一的。

请编程实现一个函数找出数组中任意一个数值等于其下标的元素。

例如，在数组 [-3, -1, 1, 3, 5] 中，数字 3 和它的下标相等。

数据范围

数组长度 [1,100]。

样例

输入：[-3, -1, 1, 3, 5]

输出：3

注意:如果不存在，则返回-1。

题解

class Solution {
public:
    int getNumberSameAsIndex(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] - mid >= 0) r = mid;
            else l = mid + 1;
        }
        if(nums[l] != l)
            return -1;
        return l;    
    }
};

58. 二叉搜索树的第k个结点

给定一棵二叉搜索树，请找出其中的第 k 小的结点。

你可以假设树和 k 都存在，并且 1≤k≤ 树的总结点数。

数据范围

树中节点数量 [1,500]。

样例

输入：root = [2, 1, 3, null, null, null, null] ，k = 3

    2
   / \
  1   3

输出：3

题解

kizk 1
kizk 2

/**
 * 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;
    TreeNode* kthNode(TreeNode* root, int k) {
        dfs(root, k);
        return ans;
    }
    void dfs(TreeNode* root, int& k){
        if(!root || !k)
            return;
        dfs(root->left, k);
        -- k;
        if(!k)
            ans = root;
        else 
            dfs(root->right, 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: 
    vector<TreeNode* > v;
    TreeNode* kthNode(TreeNode* root, int k) {
        dfs(root);
        return v[k - 1];
    }
    void dfs(TreeNode* root){
        if(!root)
            return;
        dfs(root->left);
        v.push_back(root);
        dfs(root->right);
    }
};

59. 二叉树的深度

输入一棵二叉树的根结点，求该树的深度。

从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

数据范围

树中节点数量 [0,500]。

样例

输入：二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示：
    8
   / \
  12  2
     / \
    6   4

输出：3

题解

/**
 * 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:
    int ans;
    int treeDepth(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode* root, int depth){
        if(!root)
        {
            ans = max(ans, depth);
            return;
        }
        dfs(root->left, depth + 1);
        dfs(root->right, depth + 1);
    }
};

60. 平衡二叉树

输入一棵二叉树的根结点，判断该树是不是平衡二叉树。

如果某二叉树中任意结点的左右子树的深度相差不超过 11，那么它就是一棵平衡二叉树。

注意：

规定空树也是一棵平衡二叉树。

数据范围

树中节点数量 [0,500]。

样例

输入：二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示，
    5
   / \
  7  11
    /  \
   12   9

输出：true

题解

/**
 * 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 l = dfs(root->left), r = dfs(root->right);
        if(abs(l - r) > 1) ans = false;
        return max(l, r) + 1;
    }
};

61. 数组中只出现一次的两个数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

你可以假设这两个数字一定存在。

数据范围

数组长度 [1,1000]。

样例

输入：[1,2,3,3,4,4]

输出：[1,2]

题解

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        int sum = 0;
        for(auto ite : nums)
            sum ^= ite;
        // 找到第一个1的位置
        int k = 0;
        while(!(sum >> k & 1)) k ++ ;
        int first = 0;
        for(auto ite : nums)
            if(ite >> k & 1)
                first ^= ite;
        return vector<int>({first, sum ^ first});
    }
};

62. 数组中唯一只出现一次的数字

在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。

请找出那个只出现一次的数字。

你可以假设满足条件的数字一定存在。

思考题：

如果要求只使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？

数据范围

数组长度 [1,1500]。

样例

输入：[1,1,1,2,2,2,3,4,4,4]

输出：3

题解

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        int ones = 0, twos = 0;
        for (auto x : nums) {
            ones = (ones ^ x) & ~twos;
            twos = (twos ^ x) & ~ones;
        }
        return ones;
    }
};

63. 和为S的两个数字

输入一个数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。

如果有多对数字的和等于 s，输出任意一对即可。

你可以认为每组输入中都至少含有一组满足条件的输出。

数据范围

数组长度 [1,1002]。

样例

输入：[1,2,3,4] , sum=7

输出：[3,4]

题解

class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        vector<int> v;
        set<int> s;
        for(auto ite : nums)
        {
            s.insert(ite);
            if(s.count(target - ite))
            {
                return vector<int>({ite, target - ite});
            }
        }
        return v;
    }
};

64. 和为S的连续正数序列

输入一个非负整数 S，打印出所有和为 S 的连续正数序列（至少含有两个数）。

例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以结果打印出 3 个连续序列 1 \sim 5、4 \sim 6 和 7 \sim 8。

数据范围

0 \le S \le 10000 \le S \le 1000

样例

输入：15

输出：[[1,2,3,4,5],[4,5,6],[7,8]]

题解

65. 翻转单词顺序

输入一个英文句子，单词之间用一个空格隔开，且句首和句尾没有多余空格。

翻转句子中单词的顺序，但单词内字符的顺序不变。

为简单起见，标点符号和普通字母一样处理。

例如输入字符串"I am a student."，则输出"student. a am I"。

数据范围

输入字符串长度 [0,1000]。

样例

输入："I am a student."

输出："student. a am I"

题解

class Solution {
public:
    string reverseWords(string s) {
        string str = "";
        string res = "";
        for(auto ite : s)
        {
            if(ite != ' ')
                str += ite;
            else 
            {
                reverse(str.begin(), str.end());
                res += str + " ";
                str = "";
            }
        }
        if(str.size())
        {
            reverse(str.begin(), str.end());
            res += str;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

66. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。

请定义一个函数实现字符串左旋转操作的功能。

比如输入字符串"abcdefg"和数字 2得到的结果"cdefgab"。

注意：

数据保证 nn 小于等于输入字符串的长度。

数据范围

输入字符串长度 [0,1000]。

样例

输入："abcdefg" , n=2

输出："cdefgab"

题解

class Solution {
public:
    string leftRotateString(string str, int n) {
        return str.substr(n) + str.substr(0, n);
    }
};

67. 滑动窗口的最大值

给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。

例如，如果输入数组 [2, 3, 4, 2, 6, 2, 5, 1] 及滑动窗口的大小 3，那么一共存在 6个滑动窗口，它们的最大值分别为 [4, 4, 6, 6, 6, 5]。

注意：

数据保证 k 大于 0，且 k小于等于数组长度。

数据范围

数组长度 [1,1000]。

样例

输入：[2, 3, 4, 2, 6, 2, 5, 1] , k=3

输出: [4, 4, 6, 6, 6, 5]

题解

class Solution {
public:
    int q[1010], hh = 0, tt = -1;
    vector<int> maxInWindows(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res;
        for(int i = 0; i < n; i ++)
        {
            if(hh <= tt && i - k + 1 > q[hh]) hh ++ ;
            while(hh <= tt && nums[i] > nums[q[tt]]) tt -- ;
            q[ ++ tt ] = i;
            if(i - k + 1 >= 0)
                res.push_back(nums[q[hh]]);
        }
        return res;
    }
};

68. 骰子的点数

将一个骰子投掷 n 次，获得的总点数为 s，s 的可能范围为 n \sim 6n。

掷出某一点数，可能有多种掷法，例如投掷 2 次，掷出 3 点，共有 [1,2],[2,1] 两种掷法。

请求出投掷 n 次，掷出 n \sim 6n 点分别有多少种掷法。

数据范围

1 \le n \le 10

样例1

输入：n=1

输出：[1, 1, 1, 1, 1, 1]

解释：投掷1次，可能出现的点数为1-6，共计6种。每种点数都只有1种掷法。所以输出[1, 1, 1, 1, 1, 1]。

样例2

输入：n=2

输出：[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

解释：投掷2次，可能出现的点数为2-12，共计11种。每种点数可能掷法数目分别为1,2,3,4,5,6,5,4,3,2,1。

      所以输出[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]。

题解

class Solution {
public:
    int f[12][12 * 6];
    vector<int> numberOfDice(int n) {
        f[0][0] = 1;
        vector<int> res;
        for(int i = 1; i <= n; i ++)
            for(int j = i; j <= 6 * i; j ++)
                 for(int k = 1; k <= 6; k ++)
                    if(j >= k)
                        f[i][j] += f[i - 1][j - k];
        for(int i = n; i <= 6 * n; i ++)
            res.push_back(f[n][i]);
        return res;
    }
};

69. 扑克牌的顺子

从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。

2 \sim 10 为数字本身，A 为 1，J 为 11，Q 为 12，K 为 13，大小王可以看做任意数字。

为了方便，大小王均以 0 来表示，并且假设这副牌中大小王均有两张。

样例1

输入：[8,9,10,11,12]

输出：true

样例2

输入：[0,8,9,11,12]

输出：true

题解

class Solution {
public:
    bool isContinuous( vector<int> numbers ) {
        int n = numbers.size();
        if(!n)
            return false;
        sort(numbers.begin(), numbers.end());
        int d = 0, cnt = 0;
        for(int i = 0; i < n - 1; i ++)
        {
            if(!numbers[i])
                cnt ++ ;
            else 
            {
                d = numbers[i + 1] - numbers[i];
                if(!d)
                    return false;
                while(d > 1 && cnt)
                    d --, cnt -- ;
                if(d > 1)
                    return false;
            }
        }
        
        return true;
    }
};

70. 圆圈中最后剩下的数字

0, 1, …, n-1 这 n个数字 (n>0)0 开始每次从这个圆圈里删除第 mm 个数字。

求出这个圆圈里剩下的最后一个数字。

数据范围

1 \le n,m \le 4000

样例

输入：n=5 , m=3

输出：3

题解

class Solution {
public:
    int lastRemaining(int n, int m){
        if(n == 1)
            return 0;
        return (lastRemaining(n - 1, m) + m) % n;
    }
};

71. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖一次该股票可能获得的利润是多少？

例如一只股票在某些时间节点的价格为 [9, 11, 8, 5, 7, 12, 16, 14]。

如果我们能在价格为 5 的时候买入并在价格为 16 时卖出，则能收获最大的利润 11。

数据范围

输入数组长度 [0,500]。

样例

输入：[9, 11, 8, 5, 7, 12, 16, 14]

输出：11

题解

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        for(int i = 0, j = 1e9; i < n; i ++)
        {
            if(nums[i] > j)
                res = max(res, nums[i] - j);
            j = min(nums[i], j);
        }
        return res;
    }
};

72. 求1+2+…+n

求 1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句 (A?B:C)。

数据范围

1 \le n \le 1000。

样例

输入：10

输出：55

题解

class Solution {
public:
    int getSum(int n) {
        if(n == 1)
            return 1;
        return n + getSum(n - 1);
    }
};

73. 不用加减乘除做加法

## 73. 不用加减乘除做加法

### 题解

74. 构建乘积数组

## 74. 构建乘积数组

### 题解

75. 把字符串转换成整数

题解

76. 树中两个结点的最低公共祖先

题解

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-07-18，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

文件存储

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

二叉树

编程算法

文件存储

剑指Offer

剑指Offer

1.找出数组中重复的数字

题解

2.不修改数组找出重复的数字

题解

3.二维数组中的查找

题解

4.替换空格

题解

5.从尾到头打印链表

题解

6.重建二叉树

题解

7.二叉树的下一个节点

题解

8.用两个栈实现队列

题解

9.斐波那契数列

题解

10.旋转数组的最小数字

题解

11.矩阵中的路径

题解

12.机器人的运动范围

题解

13.剪绳子

题解

14.二进制中1的个数

题解

15.数值的整数次方

题解

16.在O(1)时间删除链表结点

题解

17.删除重复的节点

题解

18.正则表达式匹配

题解

19.表示数值的字符串

题解

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

题解

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

题解

22.链表中环的入口结点

题解

23.反转链表

题解

24.合并两个排序的链表

题解

25.树 的子结构

题解

26.二叉树的镜像

题解

27.对称的二叉树

数据范围

样例

题解

28. 顺时针打印矩阵

题解

29. 包含min函数的栈

题解

30. 栈的压入、弹出序列

题解

31. 不分行从上往下打印二叉树

题解

32. 分行从上往下打印二叉树

数据范围

样例

题解

33. 之字形打印二叉树

题解

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

题解

35. 二叉树中和为某一值的路径

题解

36. 复杂链表的复刻

题解

37. 二叉搜索树与双向链表

题解

25.树的子结构