offer(第二版)2021-06-02

还差差14个题完结

面试题1：赋值运算符函数

面试题2：实现Singleton模式

面试题3：数组中重复的数字

面试题4：二维数组中的查找

面试题5：替换空格

面试题6：从尾到头打印链表

面试题7：重建二义树

面试题8：二叉树的下一个节点

面试题9：用两个栈实现队列

面试题10：斐波那契数列

面试题11：旋转数组的最小数字

面试题12：矩阵中的路径 。。。

面试题13：机器人的运动范围 。。。

面试题14：剪绳子 。。。

面试题15：二进制中1的个数

面试题16：数值的整数次方

面试题17：打印1到最大的n位数

面试题18：删除链表结点

面试题19：正则表达式匹配 。。。

面试题20：表示数值的字符串 。。。

面试题21：调整数组顺序使奇数位于偶数前面 。。。

面试题22：链表中倒数第k个节点串

面试题23：链表中环的入口节点

面试题24：反转链表

面试题25：合并两个排序的链表

面试题26：树的子结构

面试题27：二叉树的镜像

面试题28：对称的二叉树

面试题29：顺时针打印矩阵

面试题30：包含min函数的栈

面试题31：栈的压入、弹出序列

而试题32：从上到下打印二叉树

面试题33：二叉搜索树的后序遍历序列

面试题34：二叉树中和为某一值的路径 。。。

面试题35：复杂链表的复制

面试题36：二叉搜索树与双向链表

面试题37：序列化二叉树

面试题38：字符串的排列

面试题39：数组中出现次数超过一半的数字

面试题40：最小的k个数

面试题41：数据流中的中位数

面试题42：连续子数组的最大和

面试题43： 1〜n整数中1出现的次数

面试题44：数字序列中某一位的数字 。。。

面试题45：把数组排成最小的数

面试题46：把数字翻译成字符串 。。。

面试题47：礼物的最大价值

面试题48：最长不含重复字符的子字符串 。。。

面试题49：丑数

面试题50：第一个只出现一次的字符

面试题51：数组中的逆序对

面试题52：两个链表的第一个公共节点

而试题53：在排序数组中查找数字

面试题54：二叉搜索树的第k大节点

面试题55：二叉树的深度

面试题56：数组中数字出现的次数

面试题57：和为s的数字

面试题58：翻转字符串

面试题59：队列的最大值 。。。差offer解法

面试题60：n个骰子的点数 。。。

面试题61：扑克牌中的顺子

而试题62：圆圈中最后剩下的数字

面试题63：股票的最大利润 。。。

面试题64：求1+2+・・・+n

面试题65：不用加减乘除做加法

面试题66：构建乘枳数组 。。。

面试题1：赋值运算符函数

参考：剑指Offer(第一版)面试题1：赋值运算符函数

面试题2：实现Singleton模式

参考：剑指Offer(第一版)面试题2：实现Singleton模式

面试题3：数组中重复的数字

力扣平台：数组中重复的数字

offer解法：先排序再找这个重复数字

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        sort(numbers.begin(), numbers.end());
        for(int i=0; i<numbers.size()-1; ++i){
            if(numbers[i] == numbers[i+1])
                return numbers[i];
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

set去重O(n^2)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        set<int> se;
        for(int i=0; i<numbers.size(); ++i){
            if(se.find(numbers[i]) == se.end())
                se.insert(numbers[i]);
            else
                return numbers[i];
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

map计数O(n^2)

采用hash的思维

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        map<int, int> mp;
        for(int i=0; i<numbers.size(); ++i){
            if(mp.find(numbers[i]) == mp.end())
                mp[numbers[i]] = 1;
            else{
                mp[numbers[i]] += 1;
                return numbers[i];
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

map改进成O(n)

在map中查找numbers[i]改成mp[nums[i]] == 0,等于零说明nums[i]这个key不存在

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        map<int, int> mp;
        for(int i=0; i<numbers.size(); ++i){
            if (mp[numbers[i]] == 0)
                mp[numbers[i]] = 1;
            else{
                mp[numbers[i]] += 1;
                return numbers[i];
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

面试题4：二维数组中的查找

参考：剑指Offer(第一版)二维数组中的查找

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if (!array.size() || !array[0].size()) return false;
        //以主对角线为划分，遇到第一个大于target的元素，则在上一个对角线元素和当前这个对角线元素中间遍历所有元素就一定可以找到
        int row = array.size(); //n
        int col = array[0].size(); //m
        int i = 0, j = col - 1; //右上角下标
        while (i < row && j >= 0 ) {
            if (target > array[i][j]) i++;
            else if (target < array[i][j]) j--;
            else return true; //target == matrix[i][j]
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

面试题5：替换空格

参考：剑指Offer(第一版)替换空格

C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
        int len = s.size();
        string tmp = "";
        for (int i = 0; i < len; ++i) {
            if (s[i] == ' '){
                tmp += "%20";
                continue;
            }
            tmp += s[i];
        }
        return tmp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

C

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return string字符串
 */
char* replaceSpace(char* s ) {
    int countBlank = 0, len = 0;
	char* tmp = s;
	while (*tmp != '\0') {
		if (*tmp++ == ' ')
			countBlank++;
		len++;
	}
	//使用辅助空间
	tmp = (char*)malloc(len + 1 + countBlank * 2);
	memset(tmp, 0, len + 1 + countBlank * 2);
		int index = len - 1 + countBlank * 2;
	for (int i = len - 1; i >= 0; --i) {
		if (s[i] != ' ')
			tmp[index--] = s[i];
		else {
			tmp[index--] = '0';
			tmp[index--] = '2';
			tmp[index--] = '%';
		}
	}
	return tmp;
}
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

面试题6：从尾到头打印链表

参考：剑指Offer(第一版)从尾到头打印链表

借助数组

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        //得到节点数
        int count = 0;
        ListNode* tmp = head;
        while(tmp != NULL){
            count++;
            tmp = tmp->next;
        }
        tmp = head;
        vector<int> res(count, 0);
        //遍历数组得到初步结果数组
        count--;
        while(tmp != NULL){
            res[count--] = tmp->val;
            tmp = tmp->next;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

借助栈

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        stack<int, vector<int>> st;
        while(head != nullptr){
            st.push(head->val);
            head = head->next;
        }
        vector<int> res(st.size(), 0);
        int index = 0;
        while(!st.empty()){
            res[index++] = st.top();
            st.pop();
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

面试题7：重建二义树

参考：剑指Offer(第一版)重建二义树

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return build(pre, vin, 0, 0, vin.size() - 1);
    }
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int root, int start, int end){// 中序的start和end
        if(start > end) return NULL;
        TreeNode *tree = new TreeNode(preorder[root]);
        int i = start;
        while(i < end && preorder[root] != inorder[i]) i++;
        tree->left = build(preorder, inorder, root + 1, start, i - 1);
        tree->right = build(preorder, inorder, root + 1 + i - start, i + 1, end);
        return tree;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

面试题8：二叉树的下一个节点

offer书中balabala一堆，不兴看，自己想…

按中序遍历顺序找规律

给的节点存在这几种情况：是顶层根节点、中间根节点、叶子节点

顶层根节点：有右子树，无右子树¹
中间根节点：有右子树，无右子树
叶子节点：左叶子节点(反回根)，右叶子节点(往左上找根，直到根在右上)

如果给的节点有右子树，右子树有左分支则返回右子树的最左叶子节点；右子树没有左分支但有右分支就返回最右叶子节点；右子树没有左分支也没有右分支则返回右子树的根

给的节点是左叶子节点就返回它的根

给的节点是右叶子节点，则往左上方找根，一旦根在右上则返回右上的根
1
2
3
4
5

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if(!pNode) return nullptr;
        //给定节点有右子树
        if(pNode->right){
            TreeLinkNode* tmp = pNode->right;
            //往左找
            while(tmp->left) tmp = tmp->left;
                return tmp;
            //往右找(没有左子树往右找)
            while(tmp->right) tmp = tmp->right;
                return tmp;
            //直接返回根(没有左右子树)
            return tmp;
        }
        
        //在叶子节点-->给的节点根的左子节点是自己则返回根
        if(pNode->next && pNode->next->left == pNode)
            return pNode->next;
        
        //右叶子节点-->给的节点没有右子树(往前找节点是右子树的根节点)
        while(pNode->next && pNode->next->right == pNode)
            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

面试题9：用两个栈实现队列

参考：剑指Offer(第一版)用两个栈实现队列

class Solution
{
public:
    void push(int node) {
        //首先将Pop栈全挪到Push栈
        while(!stack2.empty()){
            stack1.push(stack2.top());
            stack2.pop();
        }
        stack1.push(node);
    }

    int pop() {
        //首先将Push栈全部挪到pop栈
        while(!stack1.empty()){
            stack2.push(stack1.top());
            stack1.pop();
        }
        if(stack2.empty())return -1;
        int tmp = stack2.top();
        stack2.pop();
        return tmp;
    }

private:
    stack<int> stack1; //push栈
    stack<int> stack2; //pop栈
};
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

面试题10：斐波那契数列

参考：剑指Offer(第一版)斐波那契数列

offer书上提到的相关题目:经典青蛙跳台阶、矩形覆盖(铺地砖)

递归

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0)return 0;
        if(n == 1 || n == 2)return 1;
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
};
1
2
3
4
5
6
7
8

动规

class Solution {
public:
    int Fibonacci(int n) {
        if(n<=1) return n;
        int cur=1, pre=0;
        for(int i=2; i<=n; ++i){
            int tmp = cur;
            cur += pre;
            pre = tmp;
        }
        return cur;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

求斐波那契数列转化为求矩阵的n次方(详情请看参考文章)

class Solution {
public:
    int Fibonacci(int n) {
        if (!n) return 0;
        if (1 == n) return 1;
        if (2 == n) return 1;
        //矩阵a
        vector<vector<int>> a(2, vector<int>(2, 1));
        a[1][1] = 0;
        vector<vector<int>> a_tmp(2, vector<int>(2, 1));
        a_tmp[1][1] = 0;
        for (int i = 1; i < n-2; ++i) {
                int res_0_0 = a_tmp[0][0] * a[0][0] + a_tmp[0][1] * a[1][0];
                int res_0_1 = a_tmp[0][0] * a[0][1] + a_tmp[0][1] * a[1][1];
                int res_1_0 = a_tmp[1][0] * a[0][0] + a_tmp[1][1] * a[1][0];
                int res_1_1 = a_tmp[1][0] * a[0][1] + a_tmp[1][1] * a[1][1];
                a_tmp[0][0] = res_0_0;
                a_tmp[0][1] = res_0_1;
                a_tmp[1][0] = res_1_0;
                a_tmp[1][1] = res_1_1;
        }
        return a_tmp[0][0] + a_tmp[1][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

面试题11：旋转数组的最小数字

参考：剑指Offer(第一版)旋转数组的最小数字

将旋转之后的数组划分成成两个排序的子数组

找到数组的中间元素，如果该中间元素位于前面的递增子数组，则中间元素一定大于等于第一个指针指向的元素，最小元素就位于该中间元素后面，第一个指针指向该中间元素；如果该中间元素位于后面的递增数组，则中间元素小于等于最后一个指针指向的元素，此时最小元素就位于该中间元素的前面，第二个指针指向该中间元素

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int left = 0;
        int right = rotateArray.size()-1;
        int mid = 0;
        if(rotateArray[left] < rotateArray[right]) return rotateArray[left];
        while(left+1 < right){
            mid = (left+right)>>1;
            if(rotateArray[left] == rotateArray[right] && rotateArray[right] == rotateArray[mid]){ //顺序查找
                int min = rotateArray[left];
                for(int i=left+1; i<=right; ++i)
                    if(min > rotateArray[i])
                        min = rotateArray[i];
                return min;
            }
            else if(rotateArray[mid]>=rotateArray[left])
                left = mid;
            else if(rotateArray[mid]<=rotateArray[right])
                right = mid;
        }
        return rotateArray[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

面试题12：矩阵中的路径

。。。

面试题13：机器人的运动范围

。。。

1

面试题14：剪绳子

1

面试题15：二进制中1的个数

参考：剑指Offer(第一版)二进制中1的个数

不对原数据进行移位，而是使用一个无符号整形不断左移去试探n的每一位

class Solution {
public:
     int  NumberOf1(int n) {
        uint32_t flag = 1;
        char res = 0;
        while(flag){
            if(n&flag)res++;
            flag <<= 1;
        }
        return res;
     }
};
1
2
3
4
5
6
7
8
9
10
11
12

面试题16：数值的整数次方

参考：剑指Offer(第一版)数值的整数次方

快速幂

class Solution {
public:
    bool equal(double x, double y) {
        if (x - y > -0.0000001 && x - y < 0.0000001)
            return true;
        else
            return false;
    }
    double Power(double base, int exponent) {
        if (equal(base, 1.0)) return 1.0;
        unsigned int n_tmp = exponent; //防止n=-2147483648时 n*=-1溢出
        
        //n<0
        if (exponent < 0) {
            base = 1.0 / base;
            //n *= -1
            exponent += 1;
            exponent *= -1;
            n_tmp = exponent;
            ++n_tmp;
        }
        
        //x == -1.0
        if (equal(base, -1.0) && n_tmp % 2) return -1.0;
        if (equal(base, -1.0) && !(n_tmp % 2)) return 1.0;
        double res = 1.0;
        for (int i = 1; i <= n_tmp; ++i) {
            res *= base;
            if (equal(res, 0.0)) return 0.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
32
33

面试题17：打印1到最大的n位数

参考：剑指Offer(第一版)打印1到最大的n位数

面试题18：删除链表结点

参考：剑指Offer(第一版)删除链表结点

offer书中同类型题目：删除链表中重复的结点

链表是排序，遍历一遍使用O(1)的删除要目标值相同的节点方式

双指针法找到两个以上节点相同的区间，然后使用O(1)复杂度的算法删除

class Solution {
public:
    //删除节点核心函数O(1)
    ListNode* deleteNode(ListNode** head, ListNode* del) {
        //del是头节点并且链表只有一个节点
        if (del == *head && !del->next) {
            return *head = del->next;
        }

        //del不是最后一个节点,-->O(1)删除方式
        if (del->next) {
            del->val = del->next->val;
            del->next = del->next->next;
            return *head;
        }
        //del已经是最后一个节点了，只能遍历找到del的前一个节点然后删除-->退变为O(n)方式
        ListNode* cur = *head;
        while (cur != nullptr) {
            if (cur->next == del)
                break;
            cur = cur->next;
        }
        cur->next = cur->next->next;
        return *head;
    }
    ListNode* deleteDuplication(ListNode* pHead) {
        ListNode* pre = pHead, * nex = pHead;
        while (nex) {
            if (!nex->next) break;
            while (nex->next && nex->next->val == pre->val)
                nex = nex->next;
            ListNode* conti = nex->next;
            //删除[pre, nex]上的节点
            if (pre != nex) {
                pre->next = nex->next;
                conti = pre;
                pHead = deleteNode(&pHead, pre);
            }
            pre = nex = conti;
        }
        return pHead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

面试题：

参考：剑指Offer(第一版)面试题4：二维数组中的查找

1

面试题：

参考：剑指Offer(第一版)面试题4：二维数组中的查找

1

面试题21：调整数组顺序使奇数位于偶数前面

参考：剑指Offer(第一版)调整数组顺序使奇数位于偶数前面

牛客和力扣不同的地方：调整数组顺序使奇数位于偶数前面，偶数和偶数之间的相对位置不变

。。。未过OJ

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArray(vector<int>& array) {
        int first = 0, last = array.size() - 1;
        while (first < last-1) {
            //first：当前状态下从前往后第一个偶数
            while (first < array.size() && array[first] % 2 != 0) ++first;
            //last：当前状态下从后往前第一个奇数
            while (last > 0 && array[last] % 2 == 0) --last;
            //first >= last:说明已经奇前偶后
            //first或者last已经超出数组边界，说明数组全是奇数或者偶数则不需要任何交换
            if (first >= array.size() || last < 0 || first >= last)break;
            //位操作的交换效率可能高一点
            array[first] ^= array[last];
            array[last] ^= array[first];
            array[first] ^= array[last];
        }
        return array;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

面试题22：链表中倒数第k个节点

参考：剑指Offer(第一版)链表中倒数第k个节点

牛客不同于力扣：如果该链表长度小于k，请返回空

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        ListNode* res = nullptr;
        stack<ListNode*> st;
        while(pHead){
            st.push(pHead);
            pHead = pHead->next;
        }
        while(k){
            if(st.empty()) return nullptr; //该链表长度小于k
            res = st.top();
            st.pop();
            --k;
        }
        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

面试题23：链表中环的入口节点

offer书思路

快慢指针判断链表有环的同时，计数构成环的节点个数

步长为环节点个数的两个指针同时往后走，直到两个指针指向同一个节点那么就找到环的入口节点了

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* fast = pHead, * slow = pHead;
        while (fast && slow) {
            fast = fast->next;
            slow = slow->next;
            slow = !slow?slow:slow->next;
            if (fast == slow) break;
        }
        //没有环
        if (!fast || !slow) return nullptr;

        int count = 1; //计算环的节点数
        slow = slow->next;
        while (slow != fast) {
            slow = slow->next;
            ++count;
        }
        fast = pHead;
        slow = pHead;
        while (count) {
            slow = slow->next;
            --count;
        }
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};
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

使用map

遍历有环的链表，当第一次访问已经访问过的节点时，那么这个节点就是环的入口节点

遍历链表，链表的节点地址作为key插入map(采用重载的[]操作运算符)，map[key]访问如果没有key对应的键值对，说明是第一次访问这个节点，map会创建这个键值对并且值是0，我们立刻将它的值改成1标记这个节点访问过了，如果不是第一次在map中创建这个节点那么就是1，说明链表访问到环的入口节点了

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        map<ListNode*, char > mp;
        while(pHead){
            if(!mp[pHead]) mp[pHead] = 1;
            else
                return pHead;
            pHead = pHead->next;
        }
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

面试题24：反转链表

参考：剑指Offer(第一版)反转链表

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* newHead = nullptr;
        while(pHead){
            ListNode* tmp = pHead;
            pHead = pHead->next;
            if(!newHead){
                newHead = tmp;
                newHead->next = nullptr;
            }
            else{
                tmp->next = newHead;
                newHead = tmp;
            }
        }
        return newHead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

面试题25：合并两个排序的链表

参考：剑指Offer(第一版)合并两个排序的链表

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* tmp = nullptr;
        ListNode* res = nullptr;
        ListNode* res_end = nullptr;
        //取两个链表中最小值的节点尾插到结果链表
        while(pHead1 && pHead2){
            tmp = pHead1->val <= pHead2->val ? pHead1 : pHead2;
            tmp == pHead1 ? pHead1 = pHead1->next : pHead2 = pHead2->next;
            res_end = !res ? res = tmp : res_end->next = tmp;
        }
        //有一个链表是空了就将非空连接到结果链表尾
        if(pHead1)
            !res ? res = pHead1 : res_end->next = pHead1;
        else
            !res ? res = pHead2 : res_end->next = pHead2;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

面试题26：树的子结构

参考：剑指Offer(第一版)树的子结构

class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        return isSubStructure(pRoot1, pRoot2);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        bool result = false;
        if(A && B){
            if(A->val == B->val)
                result = doesTree1HaveTree2(A, B);
            if(!result)
                result = isSubStructure(A->left, B);
            if(!result)
                result = isSubStructure(A->right, B);
        }
        return result;
    }
    bool doesTree1HaveTree2(TreeNode* Tree1, TreeNode* Tree2){
        if(!Tree2)
            return true;
        if(!Tree1)
            return false;
        if(Tree1->val != Tree2->val)
            return false;
        return doesTree1HaveTree2(Tree1->left, Tree2->left) && doesTree1HaveTree2(Tree1->right, Tree2->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：二叉树的镜像

参考：剑指Offer(第一版)二叉树的镜像

递归

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        if(!pRoot) return pRoot;
        TreeNode* tmp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = tmp;
        Mirror(pRoot->left);
        Mirror(pRoot->right);
        return pRoot;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

循环

栈

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        stack<TreeNode*> sck;
        sck.push(pRoot);
        while(!sck.empty())
        {
            TreeNode* tmp = sck.top();
            sck.pop();
            if(!tmp) continue;
            swap(tmp->left,tmp->right);
            if(tmp->right != NULL) sck.push(tmp->right);
            if(tmp->left != NULL) sck.push(tmp->left);
        }
        return pRoot;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

队列

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        queue<TreeNode*> que;
        que.push(pRoot);
        while(!que.empty())
        {
            TreeNode* tmp = que.front();
            que.pop();
            if(tmp == NULL) continue;
            swap(tmp->left,tmp->right);
            if(tmp->left) que.push(tmp->left);
            if(tmp->right) que.push(tmp->right);
        }
        return pRoot;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

面试题28：对称的二叉树

参考：剑指Offer(第一版)对称的二叉树

递归

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        if(pRoot == NULL) return true;
        return comRoot(pRoot->left, pRoot->right);
    }
    bool comRoot(TreeNode* left, TreeNode* right){
        if(left == NULL)
            return right == NULL;
        if(right == NULL)
            return false;
        if(left->val != right->val)
            return false;
        return comRoot(left->left, right->right) && comRoot(left->right, right->left);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

迭代

队列

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        if (pRoot == NULL) return true;
        queue<TreeNode*> que;
        que.push(pRoot->left);   // 将左子树头结点加入队列
        que.push(pRoot->right);  // 将右子树头结点加入队列
        while (!que.empty()) {  // 接下来就要判断这这两个树是否相互翻转
            TreeNode* leftNode = que.front(); que.pop();    
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 左节点为空、右节点为空，此时说明是对称的
                continue;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) { 
                return false;
            }
            que.push(leftNode->left);   // 加入左节点左孩子
            que.push(rightNode->right); // 加入右节点右孩子
            que.push(leftNode->right);  // 加入左节点右孩子
            que.push(rightNode->left);  // 加入右节点左孩子
        }
        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

栈

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        if (pRoot == NULL) return true;
        stack<TreeNode*> st; // 这里改成了栈
        st.push(pRoot->left);
        st.push(pRoot->right);
        while (!st.empty()) {
            TreeNode* leftNode = st.top(); st.pop();
            TreeNode* rightNode = st.top(); st.pop();
            if (!leftNode && !rightNode) {
                continue;
            }
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            st.push(leftNode->left);
            st.push(rightNode->right);
            st.push(leftNode->right);
            st.push(rightNode->left);
        }
        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

面试题29：顺时针打印矩阵

参考：剑指Offer(第一版)顺时针打印矩阵

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        int left = 0;
        int right = col-1;
        int top = 0;
        int floor = row - 1;
        int count = 0;
        vector<int> res(row*col, 0);
        while(left<right && top<floor){
            //往右
            for(int i=left; i<=right; ++i)
                res[count++] = matrix[top][i];
            top++;
            //往下
            for(int i=top; i<=floor; ++i)
                res[count++] = matrix[i][right];
            right--;
            //往左
            for(int i=right; i>=left; --i)
                res[count++] = matrix[floor][i];
            floor--;
            //往上
            for(int i=floor; i>=top; --i)
                res[count++] = matrix[i][left];
            left++;
        }
        if(left == right) //往下
            for (int i = top; i <= floor; ++i)
                res[count++] = matrix[i][right];
        else if(top == floor) //往右
            for(int i=left; i<=right; ++i)
                res[count++] = matrix[top][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
27
28
29
30
31
32
33
34
35
36
37
38

面试题30：包含min函数的栈

参考：剑指Offer(第一版)包含min函数的栈

class Solution {
public:
    void push(int value) {
        this->s_stack.push(value);
        if(this->min_stack.empty() || value <= this->min_stack.top())
            this->min_stack.push(value);
        else
            this->min_stack.push(this->min_stack.top());
    }
    
    void pop() {
        this->s_stack.pop();
        this->min_stack.pop();
    }
    
    int top() {
        return s_stack.top();
    }
    
    int min() {
        return this->min_stack.top();
    }
private:
    stack<int> min_stack;
    stack<int> s_stack;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

面试题31：栈的压入、弹出序列

参考：剑指Offer(第一版)栈的压入、弹出序列

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> pushed_st;
        //依次查看popped[i]
        int index = 0;
        for (int i = 0; i < popV.size(); ++i) {
            //栈空，就直接入栈到popV[i];栈非空但栈顶元素不是popV[i]也需要入栈(pushed_st.empty() || !pushed_st.empty() && pushed_st.top() != popV[i])
            //循环每次都是入栈直到ppopV[i]入栈才停止，栈顶元素不是popV[i]说明这个元素还未入栈
            if (index < popV.size() && (pushed_st.empty() || !pushed_st.empty() && pushed_st.top() != popV[i])) {
                //按照pushV顺序入栈，循环入栈直到遇到popV[i]才停止
                while (index < popV.size() && pushV[index] != popV[i])
                    pushed_st.push(pushV[index++]);
                //popV[i]入栈
                if(index < popV.size())
                    pushed_st.push(pushV[index++]);
            }
            //栈顶此时是popV[i]就出栈
            if (pushed_st.top() == popV[i])
                pushed_st.pop();
        }
        //最终栈空说明按pushed顺序入栈以及出栈操作可以得到popped栈
        return pushed_st.empty();
    }
};
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

而试题32：从上到下打印二叉树

参考：剑指Offer(第一版)从上到下打印二叉树

class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        //空树，直接返回空
		if (!root) return res;
        
		//队列
		queue<TreeNode*> qu;
		qu.push(root);
		
		//结果字符串
		vector<int> res;
        
		//保存层次遍历的节点
		TreeNode* element;
		//层次遍历
		while (!qu.empty()) {
			element = qu.front();
            if(element)
			    res.push_back(element->val);
			qu.pop(); //出队一个根节点
			//入队这个根的两个子节点(先左后右)
			if (element) qu.push(element->left);
			if (element) qu.push(element->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

面试题33：二叉搜索树的后序遍历序列

参考：剑指Offer(第一版)二叉搜索树的后序遍历序列

牛客不同于力扣，序列是空时返回false

递归

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(!sequence.size()) return false;
        return _verifyPostorder(sequence, 0, sequence.size() - 1);
    }
     bool _verifyPostorder(vector<int>& postorder, int start, int end) { //[start, end]
        if (end < start) return false;
        if (start == end) return true;
        //if (start + 1 == end) return postorder[start] < postorder[end]; //子树没有右节点
        int s1 = start, e1 = start, s2 = start, e2 = end - 1;
        while (postorder[s2] < postorder[end]) s2++;

        // if (s2 == end) return true; //只有左子树,判断所有节点是不是都小于根节点
        if (s2 == end) return _verifyPostorder(postorder, start, end - 1); //只有左子树

        if (s2 == start) { //只有右子树,判断所有节点是不是都大于根节点
            for (int i = start; i < end; ++i)
                if (postorder[i] < postorder[end])
                    return false;
            return _verifyPostorder(postorder, start, end - 1);
        }

        e1 = s2 - 1;
        //判断右子树节点全部大于根 postorder[s2, e2]>postorder[end]
        for (int i = s2; i <= e2; ++i)
            if (postorder[i] < postorder[end])
                return false;
        return _verifyPostorder(postorder, s1, e1) && _verifyPostorder(postorder, s2, e2);
    }
};
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

面试题34：二叉树中和为某一值的路径

参考：剑指Offer(第一版)面试题4：二维数组中的查找

面试题35：复杂链表的复制

参考：剑指Offer(第一版)复杂链表的复制

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(!pHead) return nullptr;
        map<RandomListNode*, RandomListNode*> ma;//记录原节点和复制节点的映射关系
        RandomListNode* cur = pHead;
        RandomListNode* newHead = nullptr, * newHeadEnd = nullptr;
        while(cur){
            //复制链表
            if(cur == pHead)
                newHead = newHeadEnd = new RandomListNode(cur->label);
            else{
                newHeadEnd->next = new RandomListNode(cur->label);
                newHeadEnd = newHeadEnd->next;
            }
            //建立原节点和复制之后的节点的映射关系
            ma[cur] = newHeadEnd;
            cur = cur->next;
        }
        for(map<RandomListNode*, RandomListNode*>::iterator it = ma.begin(); it != ma.end(); ++it){
            if(it->first->random)
                it->second->random = ma[it->first->random];
        }
        return newHead;
    }
};
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

面试题36：二叉搜索树与双向链表

参考：剑指Offer(第一版)二叉搜索树与双向链表

借助队列和中序遍历

牛客不同于力扣，力扣是得到循环双向链表，牛客得到非循环双向链表

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        return treeToDoublyList(pRootOfTree);
    }
    TreeNode* treeToDoublyList(TreeNode* root) {
        if(!root) return nullptr;
        queue<TreeNode*> que = inOrderTraverse2(root); //得到中序遍历的队列
        TreeNode* head = nullptr, *end = nullptr;
        //出队链接成双向循环链表
        while(!que.empty()){
            TreeNode* cur = que.front();
            if(!head){
                end = head = cur;
            } 
            else{
                cur->left = end;
                end->right = cur;
                end = cur;
            }
            que.pop();
        }
        return head;
    }
    //中序遍历,返回中序遍历得到的队列
    queue<TreeNode*> inOrderTraverse2(TreeNode* des) {
        stack<TreeNode*> st;
        queue<TreeNode*> res; //结果数组
        TreeNode* pNode = des;
        while (pNode != nullptr || !st.empty()) {
            if (pNode != nullptr) {
                st.push(pNode);
                pNode = pNode->left;
            }
            else { //pNode == null && !stack.isEmpty()
                TreeNode* node = st.top();
                st.pop();
                res.push(node);
                pNode = node->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
43
44
45
46
47
48
49
50
51
52
53

递归

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        return treeToDoublyList(pRootOfTree);
    }
    TreeNode* treeToDoublyList(TreeNode* root) {
        TreeNode *pLastNodeInList = nullptr;
        ConvertNode(root, &pLastNodeInList);

        // pLastNodeInList指向双向链表的尾结点，
        // 我们需要返回头结点
        TreeNode *pHeadOfList = pLastNodeInList;
        while(pHeadOfList != nullptr && pHeadOfList->left != nullptr)
            pHeadOfList = pHeadOfList->left;

        return pHeadOfList;
    }
    void ConvertNode(TreeNode* pNode, TreeNode** pLastNodeInList)
    {
        if(pNode == nullptr)
            return;

        TreeNode *pCurrent = pNode;

        if (pCurrent->left != nullptr)
            ConvertNode(pCurrent->left, pLastNodeInList);

        pCurrent->left = *pLastNodeInList; 
        if(*pLastNodeInList != nullptr)
            (*pLastNodeInList)->right = pCurrent;

        *pLastNodeInList = pCurrent;

        if (pCurrent->right != nullptr)
            ConvertNode(pCurrent->right, pLastNodeInList);
    }
};
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

面试题37：序列化二叉树

参考：剑指Offer(第一版)序列化二叉树

循环方式层次遍历的二叉树序列化和反序列化

class Solution {
public:
    char* Serialize(TreeNode *root) {    
        //空树，直接返回空
        char* r = new char(0);
		if (!root) return r;
		//队列
		queue<TreeNode*> qu;
		qu.push(root);
		//结果字符串
		string res = "[";
		//保存层次遍历的节点
		TreeNode* element;
		//层次遍历
		while (!qu.empty()) {
			element = qu.front();
			res += !element ? "#," : to_string(element->val) + ",";
			qu.pop(); //出队一个根节点
			//入队这个根的两个子节点(先左后右)
			if (element) qu.push(element->left);
			if (element) qu.push(element->right);
		}
		res.erase(res.size() - 1, 1); //删除最后一个多的,
		res += "]";
        char* re = new char[res.size()+1]();
        strcpy(re, res.c_str());
		return re;
    }
    TreeNode* Deserialize(char *str) {
        string data(str);
        if (!data.size()) return nullptr;
		data.erase(0, 1);
		data.erase(data.size()-1, 1);
		//string --> vector<string>
		queue<string> series;
		int i = 0, n = data.size();
		while (i < data.size()) {
			string tmp = "";
			while (i < data.size() && data[i] != ',')
				tmp += data[i++];

			series.push(tmp);
			++i;
		}
		TreeNode* root = nullptr;
		TreeNode* left, * right;
		TreeNode*  child_left = nullptr, * child_right = nullptr;
		queue<TreeNode*> child_left_queue;
		queue<TreeNode*> child_right_queue;
		//按层次遍历顺序建立二叉树
		while (!series.empty()) {
			if (!root) {
				left = right = str2node(series.front()); series.pop();
			}
			else {
				left = child_left_queue.front(); child_left_queue.pop();
				right = child_right_queue.front(); child_right_queue.pop();
			}
			if (left) {
				child_left = !series.empty() ? str2node(series.front()) : nullptr; if(!series.empty())series.pop();
				child_right = !series.empty() ? str2node(series.front()) : nullptr; if (!series.empty())series.pop();
				left->left = child_left;
				left->right = child_right;
				child_left_queue.push(child_left);
				child_right_queue.push(child_right);
			}
			if (root) {
				if (right) {
					child_left = !series.empty() ? str2node(series.front()) : nullptr; if(!series.empty())series.pop();
					child_right = !series.empty() ? str2node(series.front()) : nullptr; if (!series.empty())series.pop();
					right->left = child_left;
					right->right = child_right;
					child_left_queue.push(child_left);
					child_right_queue.push(child_right);
				}
			}
			if (!root)root = left;
		}
		return root;
    }
    //将字符串转化成节点
	TreeNode* str2node(string& str) {
		if (!str.compare("#")) return nullptr;
		return new TreeNode(stoi(str));
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

面试题38：字符串的排列

参考：剑指Offer(第一版)字符串的排列

深度优先搜索

class Solution {
public:
    vector<string> res;
    vector<string> Permutation(string str) {
        vector<char> temp;
        for(int i = 0;i < str.length();i++)
            temp.push_back(str[i]);
        sort(temp.begin(),temp.end(),compare);
        dfs(temp,0);
        return res;
    }
    void dfs(vector<char> temp,int left){
        if(left == temp.size()-1){
            string s;
            for(int i = 0;i < temp.size();i++)
                s += temp[i];
            res.emplace_back(s);
            return;
        }
        for(int i = left;i < temp.size();i++){
            if(i != left && temp[left] == temp[i])
                continue;
            swap(temp[left],temp[i]);
            dfs(temp,left+1);
        }
    }
    static bool compare(const char& a,const char& b){
        return a <= b;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

面试题39：数组中出现次数超过一半的数字

参考：剑指Offer(第一版)数组中出现次数超过一半的数字

partition思想

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        partition(numbers,0,numbers.size()-1);
         return numbers[numbers.size()/2];
    }
    void partition(vector<int>& nums, int lo, int hi){
            int num = nums[lo];
            int i =lo,j=hi+1;
            while(true){
                while(i<hi && nums[++i]<num);
                while(j>lo && nums[--j]>num);
                if(i>=j) break;
                swap(nums,i,j);
            }
            swap(nums,lo,j);
            int mid = nums.size()>>1;
            if(j == mid) return;
            if(j>mid) partition(nums,lo,j-1);
            else partition(nums,j+1,hi);
    }
    void swap(vector<int>& nums, int i ,int j ){
        int temp = nums[i];nums[i] = nums[j];nums[j] = temp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

摩尔投票法

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int res = 0, count = 0;
        for(int i = 0; i < numbers.size(); i++){
            if(count == 0){
                res = numbers[i];
                count++;
            }
            else
                res==numbers[i] ? count++:count--;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

哈希法

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        unordered_map<int,int> hash;
        int res = 0, len = numbers.size();
        for(int i = 0; i < len; i++){
            hash[numbers[i]]++;
            //不必等到哈希表完全建立再进行此判断
            if(hash[numbers[i]] > len/2)
                res = numbers[i];
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

面试题40：最小的k个数

参考：剑指Offer(第一版)最小的k个数

牛客相较于力扣：K>数组的长度，返回一个空的数组

排序

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(k > input.size()) return {};
        sort(input.begin(), input.end());
        return vector<int> (input.begin(), input.begin()+k);
    }
};
1
2
3
4
5
6
7
8

分治

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(k<=0 || k > input.size()) return {};
        int start = 0;
        int end = input.size()-1;
        int index = Partition(input, start, end);
        while(index != k-1){
            if(index > k-1){
                end = index - 1;
                index = Partition(input, start, end);
            }else{
                start = index + 1;
                index = Partition(input, start, end);
            }
        }
        return vector<int> (input.begin(), input.begin()+k);
    }
    void swap(vector<int>& nums, int i_a, int i_b){
        int tmp = nums[i_a];
        nums[i_a] = nums[i_b];
        nums[i_b] = tmp;
    }
    int Partition(vector<int>& a,int left,int right)
    {
        int i=left;
        int j=right+1;
        int pivot=a[left];
        while(true)
        {
            while(i<right && a[++i]<pivot) {}
            while(j>0 && a[--j]>pivot)     {}
            if(i>=j)
                break;
            else
                swap(a,i,j);
        }
        swap(a,left,j);
        return j;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

堆

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(k > input.size()) return {};
        priority_queue<int, vector<int>, greater<int>> pq;
        vector<int > res;
        for(int i=0; i<input.size(); ++i)
                pq.push(input[i]);
        for(int i=0; i<k; ++i){
            res.push_back(pq.top());
            pq.pop();
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

面试题41：数据流中的中位数

参考：算法博客12.实时获取中位数

class Solution {
public:
	void Insert(int num) {
		//插入大小堆
		//大根堆初始没有元素、小于等于大根堆堆顶就插入大根堆
		if (0 == bigRootHeap.size() || num <= bigRootHeap.top())
			bigRootHeap.push(num);
		//大于大根堆堆顶就放入小根堆
		else
			littleRootHeap.push(num);

		//调整大小堆，使它们元素个数相差不大于1
		//大堆元素多，弹出堆顶元素放入另一个
		if ((int)(bigRootHeap.size() - littleRootHeap.size()) > 1) {
			//弹出大堆堆顶
			int tmp = bigRootHeap.top();
			bigRootHeap.pop();
			//插入小堆
			littleRootHeap.push(tmp);
		}
		if ((int)(littleRootHeap.size() - bigRootHeap.size()) > 1) {
			//弹出小堆堆顶
			int tmp = littleRootHeap.top();
			littleRootHeap.pop();
			//插入大堆
			bigRootHeap.push(tmp);
		}
	}

	double GetMedian() {
		int notNUll = 0;  //记录当有一个堆是空堆时，另一个堆必然只有一个元素，便是当前状态的中位数
		//中位数就是任意时刻大根堆和小根堆的堆顶元素之和的均值
		if (0 == bigRootHeap.size())
			notNUll = littleRootHeap.top();
		else
			notNUll = bigRootHeap.top();
        if(1 == bigRootHeap.size() - littleRootHeap.size()) return bigRootHeap.top();
        if(1 == littleRootHeap.size() - bigRootHeap.size()) return littleRootHeap.top();
		return bigRootHeap.size() > 0 && littleRootHeap.size() > 0 ?
			(bigRootHeap.top() + littleRootHeap.top()) / 2 : notNUll;
	}
private:
	priority_queue<double, vector<double>, greater<double>> littleRootHeap;
	priority_queue<double, vector<double>, less<double>> bigRootHeap;
};
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

面试题42：连续子数组的最大和

参考：剑指Offer(第一版)连续子数组的最大和

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.empty())
            return 0;
        //F[0] = a[0]
        vector<int> maxSum(array);
        for(int i=1; i<array.size(); ++i){
            //F[i] = max(F[i-1]+a[i], a[i])
            maxSum[i] = max(maxSum[i-1]+array[i], array[i]);
        }
        //max(F[i])
        int ret = maxSum[0];
        for(int i=1; i<maxSum.size(); ++i){
            ret = max(ret, maxSum[i]);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

面试题43： 1〜n整数中1出现的次数

参考：剑指Offer(第一版)1〜n整数中1出现的次数

offer书中的做法找规律

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        return numberOf1Between1AndN(n);
    }
    int PowerBase10(unsigned int n) { //return 10^n
        int result = 1;
        for (unsigned int i = 0; i < n; ++i)
            result *= 10;
        return result;
    }
    int numberOf1(const char* strN) {
        if (!strN || *strN < '0' || *strN>'9' || *strN == '\0')
            return 0;

        int first = *strN - '0';
        unsigned int length = static_cast<unsigned int>(strlen(strN)); //

        if (length == 1 && first == 0)
            return 0;

        if (length == 1 && first > 0)
            return 1;

        //假设strN是"21345"
        //numFirstDigit 是数字10000~19999的第一个位中的数目
        int numFirstDigit = 0;
        if (first > 1) //最高位大于1则数最高位是1的个数
            numFirstDigit = PowerBase10(length-1);
        else if(first == 1) //最高位是1则最高位1出现的次数就是后面数+1
            numFirstDigit = atoi(strN+1)+1;

        //numOtherDigits是1346~21345除了第一位之外的数位中的数目
        int numOtherDigits = first * (length - 1) * PowerBase10(length-2);
        //numRecursive 是1~1345中的数目
        int numRecursize = numberOf1(strN+1);

        return numFirstDigit + numOtherDigits + numRecursize;
    }
    int numberOf1Between1AndN(int n) {
        if (n <= 0)
            return 0;

        char strN[11];
        sprintf(strN, "%d", n); //将整形数字变成字符串

        return numberOf1(strN);
    }
};
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

在力扣中AC能接近双百,牛客中差得多，等后续吧

面试题44：数字序列中某一位的数字

参考：剑指Offer(第一版)数字序列中某一位的数字

面试题45：把数组排成最小的数

参考：剑指Offer(第一版)把数组排成最小的数

之前牛客判题有问题这个题没有过，同样的代码在力扣中可以过了

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        sort(numbers.begin(), numbers.end(), compare);
        // sort(nums.begin(), nums.begin() + nums.size(), compare);
        string res = "";
        int i = 0;
        while (i < numbers.size()) {
            res += to_string(numbers[i]);
            ++i;
        }
        return res;
    }
    static bool compare(int a, int b) {
        string a_str = to_string(a);
        string b_str = to_string(b);
        //if (a_str.size() == b_str.size()) return a_str.compare(b_str) < 0;
        int i_a = 0, i_b = 0;
        while (a_str[i_a] == b_str[i_b]) {
            i_a = i_a < a_str.size() - 1 ? i_a + 1 : i_a;
            i_b = i_b < b_str.size() - 1 ? i_b + 1 : i_b;
            if (a_str[i_a + 1] == b_str[i_b + 1] && b_str[i_b + 1] == '\0')
                break;
        }
        return a_str[i_a] - b_str[i_b] < 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

面试题46：把数字翻译成字符串

参考：剑指Offer(第一版)把数字翻译成字符串

面试题47：礼物的最大价值

动规

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

面试题48：最长不含重复字符的子字符串

参考：剑指Offer(第一版)面试题4：二维数组中的查找

面试题49：丑数

参考：剑指Offer(第一版)丑数

动规

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if (index<=0) return 0;
        if (index==1) return 1;
        vector<int>k(index);k[0]=1;
        int i_2=0,i_3=0,i_5=0;
        for (int i=1;i<index;i++) {
            //a[i] = min(2\*a[i_2], 3\*a[i_3], 5*a[i_5])
            k[i] = min(k[i_2]*2,min(k[i_3]*3,k[i_5]*5));
            //状态变化
            if (k[i] == k[i_2]*2) i_2++;
            if (k[i] == k[i_3]*3) i_3++;
            if (k[i] == k[i_5]*5) i_5++;
        }
        return k[index-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

面试题50：第一个只出现一次的字符

参考：剑指Offer(第一版)第一个只出现一次的字符

哈希法

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        char arr[58]; //一个字符最多的出现次数是10000次，因此使用short就能存储下
        memset(arr, 0, 58*sizeof(arr[0]));
        for(int i=0; i<str.size(); ++i)
            arr[str[i]-'A'] += 1;
        for(int i=0; i<str.size(); ++i)
            if(1 == arr[str[i]-'A']) return i;
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

面试题51：数组中的逆序对

参考：剑指Offer(第一版)数组中的逆序对

分治思想

class Solution {
public:
    int InversePairs(vector<int> data){
        if(data.size() < 0)
            return 0;
        vector<int> copy(data.begin(), data.end());
        int count = InversePairsCore(data, copy, 0, data.size() - 1);
        return count;
    }
    int InversePairsCore(vector<int> &data, vector<int> &copy, int start, int end){
        if(start == end){
            copy[start] = data[start];
            return 0;
        }

        int length = (end - start) / 2;

        int left = InversePairsCore(copy, data, start, start + length);
        int right = InversePairsCore(copy, data, start + length + 1, end);

        // i初始化为前半段最后一个数字的下标
        int i = start + length;
        // j初始化为后半段最后一个数字的下标
        int j = end;
        int indexCopy = end;
        int count = 0;
        while(i >= start && j >= start + length + 1) {
            if(data[i] > data[j]) {
                copy[indexCopy--] = data[i--];
                count = (count +j - start - length)%1000000007;
            }
            else
                copy[indexCopy--] = data[j--];
        }

        for(; i >= start; --i)
            copy[indexCopy--] = data[i];

        for(; j >= start + length + 1; --j)
            copy[indexCopy--] = data[j];

        return (left + right + count)%1000000007;
    }
};
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

面试题52：两个链表的第一个公共节点

参考：剑指Offer(第一版)两个链表的第一个公共节点

使用栈O(n)

class Solution {
public:
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        stack<ListNode* > list1Stack;
        stack<ListNode* > list2Stack;
        ListNode* res = nullptr;
        while (pHead1) {
            list1Stack.push(pHead1);
            pHead1 = pHead1->next;
        }
        while (pHead2) {
            list2Stack.push(pHead2);
            pHead2 = pHead2->next;
        }
        while (!list1Stack.empty() && !list2Stack.empty()
            && list1Stack.top() == list2Stack.top()) {
            res = list1Stack.top();
            list1Stack.pop();
            list2Stack.pop();
        }
        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

而试题53：在排序数组中查找数字

参考：剑指Offer(第一版)在排序数组中查找数字

双指针法

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int first = 0, last = data.size()-1;
        while(first < data.size() && data[first] != k) ++first;
        while(last >= 0 && data[last] != k) --last;
        if(last < first) return 0;
        return last-first+1;
    }
};
1
2
3
4
5
6
7
8
9
10

双指针使用二分法提速

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int lbound = 0, rbound = 0;
        // 寻找上界
        int l = 0, r = data.size();
        while (l < r) {
            //int mid = l + (r - l) / 2;
            int mid = (r + l) >> 1;
            if (data[mid] < k)
                l = mid + 1;
            else
                r = mid;
        }
        lbound = l;
        // 寻找下界
        r = data.size();
        while (l < r) {
            int mid = (r + l) >> 1;
            if (data[mid] <= k) 
                l = mid + 1;
            else
                r = mid;
        }
        rbound = l;
        return rbound - lbound;
    }
};
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

面试题54：二叉搜索树的第k大节点

参考：剑指Offer(第一版)二叉树的遍历之递归和非递归的广度、深度优先遍历的中序遍历算法

中序遍历得到遍历序列,返回第k个值

class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        if(k<=0) return NULL;
        vector<TreeNode*> res;
        inOrderTraverse2(pRoot, res);
        if(k>res.size()) return NULL;
        return res[k-1];
    }
    //非递归方式得到中序遍历序列
    void inOrderTraverse2(TreeNode* des, vector<TreeNode*> &res) {
        stack<TreeNode*> st;
        TreeNode* pNode = des;
        while (pNode != nullptr || !st.empty()) {
            if (pNode != nullptr) {
                st.push(pNode);
                pNode = pNode->left;
            }
            else { //pNode == null && !stack.isEmpty()
                TreeNode* node = st.top();
                st.pop();
                res.push_back(node);
                pNode = node->right;
            }
        }
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

面试题55：二叉树的深度

参考：剑指Offer(第一版)二叉树的深度

借助层次遍历得到树深

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
        if(!pRoot)
            return 0;
        return levelTraverse(pRoot);
    }
    //层次遍历(利用队列)
    int levelTraverse(TreeNode* des) {
        //空树，直接返回空数组
        if (!des) return {};
        //计数树层
        //队列
        queue<TreeNode*> qu;
        qu.push(des);
        //保存层次遍历的节点
        TreeNode* element;
        int depth = 0, count = 0, nextCount = 1;
        //层次遍历
        while (!qu.empty()) {
            element = qu.front();
            qu.pop(); //出队一个根节点
            count++;
            //入队这个根的两个子节点(先左后右)
            if (element->left) qu.push(element->left);
            if (element->right) qu.push(element->right);
            if(count == nextCount){
                nextCount = qu.size();
                count = 0;
                depth++;
            }
        }
        return depth;
    }
};
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

面试题56：数组中数字出现的次数

参考：剑指Offer(第一版)数组中数字出现的次数

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        //从头到尾异或数组中每一个元素
        int xor_ = array[0];
        for (int i = 1; i < array.size(); ++i)
            xor_ ^= array[i];
        //探索异或结果的最高非零位
        unsigned int tar = INT_MAX +1; //探子 2^31
        while (!(tar & xor_)) //(tar & xor) != 0
            tar >>= 1;
        //循环结束tar就是xor_最高非零位是1的数，通过tar划分数组
        //子数组不用保存，直接异或进去
        int min = 0, max = 0;
        for (int i = 0; i < array.size(); ++i) {
            if (array[i] & tar) //某一位是1的划分
                min ^= array[i];
            else
                max ^= array[i];
        }
        //保证min是最小值
        if (min > max) {
            int tmp = min;
            min = max;
            max = tmp;
        }
        return { min, max };
    }
};
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

面试题57：和为s的数字

参考：剑指Offer(第一版)和为s的数字

同类型题：和为s的连续正数序列参考：和为s的连续正数序列

双指针法

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array, int sum) {
        char left = 0, right = array.size() - 1;
        int min = 0, max = 0;
        char find = 0;
        while (left < right) {
            if (array[right] >= sum || array[right] + array[left] > sum)
                --right;
            else if (array[right] + array[left] < sum)
                ++left;
            //array[left] + array[right] == sum
            else {
                if(!find){
                    min = array[left];
                    max = array[right];
                    find = 1;
                }
                if(find && min*max > array[left]*array[right]){
                    min = array[left];
                    max = array[right];
                }
                ++left; --right;
            }
        }
        if(find)
            return {min, max};
        else
            return {};
    }
};
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

面试题58：翻转字符串

参考：剑指Offer(第一版)翻转字符串

将整个字符串逆转，然后将每个单词逆转

class Solution {
public:
    string ReverseSentence(string str) {
        reverseWord(str, 0, str.size()-1);
        int pre = 0, tal = 0;
        while(tal < str.size()){
            while(str[tal] != ' ' && str[tal] != '\0') tal++;
            reverseWord(str, pre, tal-1);
            pre = tal = tal+1;
        }
        return str;
    }
    void reverseWord(string &str, int begin, int end){ //[begin, end]
        while(begin < end){
            char tmp = str[begin];
            str[begin] = str[end];
            str[end] = tmp;
            ++begin;
            --end;
        }  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

面试题59：队列的最大值

参考：剑指Offer(第一版)面试题4：二维数组中的查找

同时维护一个最大栈

维护一个最大值的栈，给数值例子：

队列：8
栈：8

–>1

队列：8 1
栈：8 1

–>4

队列：8 1 4
栈：8 4 4

–>5

队列：8 1 4 5
栈：8 5 5 5

–>6

队列：8 1 4 5 6
栈：8 6 6 6 6

–>7

队列：8 1 4 5 6 7
栈：8 7 7 7 7 7

class MaxQueue {
public:
    MaxQueue() {

    }
    
    int max_value() {
        if(q.empty()) return -1;
        return st_max.top();
    }
    
    void push_back(int value) {
        q.push(value);
        if(st_max.empty())
            st_max.push(value);
        else{
            stack<int> tmp;
            while(!st_max.empty()){
                tmp.push(st_max.top());
                st_max.pop();
            }
            st_max.push(value);
            while(!tmp.empty()){
                st_max.push(st_max.top()>=tmp.top()?st_max.top():tmp.top());
                tmp.pop();
            }
        }
    }
    
    int pop_front() {
        if(q.empty()) return -1;
        int res = q.front();
        q.pop();
        st_max.pop();
        return res;
    }
private:
    queue<int> q;
    stack<int> st_max;
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */
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

offer思路，采用滑动窗口

。。。

面试题60：n个骰子的点数

参考：剑指Offer(第一版)面试题4：二维数组中的查找

面试题61：扑克牌中的顺子

现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：

1. A为1，J为11，Q为12，K为13，A不能视为14
2. 大、小王为 0，0可以看作任意牌
3. 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。

例如：给出数据[6,0,2,0,4]
中间的两个0一个看作3，一个看作5 。即：[6,3,2,5,4]
这样这五张牌在[2,6]区间连续，输出true
数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]
1
2
3
4
5
6
7
8

参考：剑指Offer(第一版)扑克牌中的顺子

class Solution {
public:
    bool IsContinuous(vector<int> numbers) {
        //排序
        set<int> se;
        char count_0 = 0; //非零个数
        for (int i = 0; i < 5; ++i)
            if (!numbers[i]) count_0++;
        for (int i = 0; i < 5; ++i)
            if(numbers[i])
                se.insert(numbers[i]);
        set<int>::iterator it = se.begin();
        if (*(se.rbegin()) - *it + 1 == 5 || count_0 + *(se.rbegin()) - *it + 1 == 5)
            return true;
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

而试题62：圆圈中最后剩下的数字

参考：剑指Offer(第一版)圆圈中最后剩下的数字

offer书–找函数关系

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if (m == 0 || n == 0) return -1;
        int index = 0;
        for(int i=2; i<=n; ++i){
            index = (index+m)%i;
        }
        return index;
    }
};
1
2
3
4
5
6
7
8
9
10
11

面试题63：股票的最大利润

参考：剑指Offer(第一版)面试题4：二维数组中的查找

面试题64：求1+2+・・・+n

参考：剑指Offer(第一版)求1+2+・・・+n

面试题65：不用加减乘除做加法

参考：剑指Offer(第一版)不用加减乘除做加法

class Solution {
public:
    int Add(int num1, int num2) {
        int res;
        while(num2){
            res = num1^num2;
            num2 = (num1&num2)<<1;
            num1 = res;
        }
        return num1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

面试题66：构建乘枳数组

参考：剑指Offer(第一版)面试题4：二维数组中的查找

---

1. OJ中不太可能出现这种测试用例，并且题目也没有提示，如果要返回那只能返回nullptr或者标志值 ↩︎