剑指offer(第二版)

剑指Offer（第二版）学习笔记

剑指Offer

题目列表
03、数组中重复的数字
04、二维数组的查找
05、替换空格
06、从尾到头打印链表
07、重建二叉树
09、用两个栈实现队列
10-I、斐波拉契数列
10-II、青蛙跳台阶问题
11、旋转数组中的最小数字
12、矩阵中的路径
13、机器人的运动范围
14、剪绳子I
14、剪绳子 II
15、二进制中1的个数
16、数值的整数次方
17、打印从1到最大的n位数（待完善）
18、删除链表的节点
19、正则表达式匹配（待完善）
20、表示数组的字符串（待完善）
21、调整数组顺序使奇数位于偶数前面
22、链表中倒数第k个节点
24、反转链表
25、合并两个有序链表（递归待完善）
26、树的子结构
27、二叉树的镜像
28、对称的二叉树（迭代待完善）
29、顺时针打印矩阵
30、包含min函数的栈
31、栈的压入、弹出序列
32-I、从上到下打印二叉树
32-II、从上到下打印二叉树II
33-III、从上到下打印二叉树III
33、二叉搜索树的后序遍历序列（待完善）
34、二叉树中和为某一值的路径（待完善）
35、复杂链表的复制（待完善）
分割线
36、二叉搜索树与双向链表（待完善）
37、序列化二叉树（待完善）
38、字符串的排列（待完善）
39、数组中出现次数超过一般的数字
40、最小的k个数
41、数据流的中位数
42、连续子数组的最大和
43、1~n整数中1的出现次数
44、数字序列中某一位的数字
45、把数组排成最小的数
46、把数字翻译成字符串
47、礼物的最大价值
48、最长不含重复字符的子字符串
49、丑数
50、第一个只出现一次的字符
总结

题目列表

03、数组中重复的数字

数组中的数字在0~n-1内，找出数组中任意一个重复的元素

思路：

排序 + 遍历：时间O(nlogn)、空间O(1)
hash + 遍历：时间O(nlogn)、空间O(n)
原地置换：时间O(n)、空间O(1)

class Solution {
public:
    int findRepeatNumber(vector& nums) {
        
        sort(nums.begin(), nums.end());
        for(int i = 1; i < nums.size(); i++){
            if(nums[i-1] == nums[i])
                return nums[i];
        }
        return -1;
		
		set iset;
        for(int i = 0; i < nums.size(); i++){
            if(iset.count(nums[i]))
                return nums[i];
            iset.insert(nums[i]);
        }
        return -1;
        
        for(int i = 0; i < nums.size(); i++){
        	while(nums[i] != i){
        		if(nums[i] == nums[nums[i]])
        			return nums[i];
        		else
        			swap(nums[i], nums[nums[i]]);
        	}
        }
        return -1;
    }
};

知识点：原地置换，找索引与元素值之间的对应关系

04、二维数组的查找

n*m数组，左到右递增，上到下递增。判断数字是否存在。

暴力：时间O(n^2)、空间O(1)
线性扫描：左下角 || 右上角，时间O(n + m)、空间O(1)

 bool findNumberIn2DArray(vector>& matrix, int target) {
        
        int m = matrix.size();
        if(m == 0)
        	return false;
        int n = matrix[0].size();
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				if(matrix[i][j] == target)
					return true;
			}
		}
		return false;
	
		
		int x = matrix.size() - 1;
        int y = 0;
        while(x >= 0 && y < matrix[0].size()){
            if(target == matrix[x][y])
                return true;
            else if(target > matrix[x][y])
                y++;
            else
                x--;
        }
        return false;
        
        
        // 测试用例：[]  0
        if(matrix.size() == 0)
            return false;
        int y = matrix[0].size() - 1;
        int x = 0;
        while(y >= 0 && x < matrix.size()){
            if(target == matrix[x][y])
                return true;
            else if(target > matrix[x][y])
                x++;
            else
                y--;
        }
        return false;
    }

05、替换空格

将字符串中的每个空格替换成%20

新字符串接收：时间O(n)、空间O(n)
原地修改：时间O(n)、空间O(1)

string replaceSpace(string s) {
	
	string str = "";
	for(char c : s){
		if(c == ' ')
			str += "%20";
		else 
			str += c;
	}
	return str;
	
	
	int n = s.size();
	int cnt = 0;
	for(char c : s)
		if(c == ' ')
			cnt++;
	s.resize(n + cnt * 2);
	for(int i = n - 1, j = n + cnt * 2 - 1; i < j; i--, j--){
		if(s[i] == ' '){
			s[j] = '0';
			s[j-1] = '2';
			s[j-2] = '%';
			j = j - 2;
		}
		else
			s[j] = s[i];
	}
	return s;
}

06、从尾到头打印链表

给定链表头节点，反向打印链表值

递归：后序遍历，时间O(n)、空间O(n)
辅助栈：时间O(n)、空间O(n)
vector顺序存储，reverse结果反转：时间O(n)、空间O(n)
迭代反转链表，顺序存储：时间O(n)、空间O(1)

vector reversePrint(ListNode* head){
	
	if(!head)
		return vector{};
	vector res;
	res = reversePrint(head->next);
	res.push_back(head->val);
	return res;
	
	 
	if(!head)
		return vector{};
	stack stk;
	while(head){
		stk.push(head->val);
		head = head->next;
	}
	vector res;
	while(!stk.empty()){
		res.push_back(stk.top());
		stk.pop();
	}
	return res;
	
	
	if(!head)
            return vector{};
    vector res;
    while(head){
        res.push_back(head->val);
        head = head->next;
    }
    reverse(res.begin(), res.end());
    return res;

	
	if(!head)
            return vector{};
    ListNode* prev = nullptr;
    ListNode* cur = head;
    while(cur){
        ListNode* tmp = cur->next;
        cur->next = prev;
        prev = cur;
        cur = tmp;
    }
    vector res;
    while(prev){
        res.push_back(prev->val);
        prev = prev->next;
    }
    return res;
}

反思：反转有多种形式==（栈、结构反转、结果反转）==

07、重建二叉树

根据前序遍历和中序遍历构建二叉树

递归构建即可

class Solution {
public:
    unordered_map imap;
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        int n = preorder.size();
        for(int i = 0; i < n; i++){
            imap[inorder[i]] = i;
        }
        return rebuild(preorder, 0, n-1, inorder, 0, n-1);
    }
    TreeNode* rebuild(vector& preorder, int preS, int preE, vector& inorder, int inS, int inE){
        if(preS > preE)
            return nullptr;
        int rootVal = preorder[preS];
        int index = imap[rootVal];
        int leftLen = index - inS;
        TreeNode* root = new TreeNode(rootVal);
        root->left = rebuild(preorder, preS + 1, preS +leftLen, inorder, inS, index - 1);
        root->right = rebuild(preorder, preS + leftLen + 1, preE, inorder, index + 1, inE);
        return root;
    }
};

09、用两个栈实现队列

appendTail：队尾插入元素；
deleteHead：队头删除整数，若不存在则返回-1；

栈2不为空，直接返回头部元素
否则，如果栈1为空，返回-1；
否则，栈1不为空，将栈1元素全部移至栈2，返回栈2首部元素。

class CQueue {
public:
    stack stk1;
    stack stk2;
    CQueue() {

    }
    
    void appendTail(int value) {
        stk1.push(value);
    }
    
    int deleteHead() {
        if(stk2.empty()){
            if(stk1.empty())
                return -1;
            while(!stk1.empty()){
                stk2.push(stk1.top());
                stk1.pop();
            }
            int res = stk2.top();
            stk2.pop();
            return res;
        }
        else{ 
            int ans = stk2.top();
            stk2.pop();
            return ans;
        }
    }
};

10-I、斐波拉契数列

暴力递归
备忘录递归
dp动态规划（可空间优化）

const int mod = 1e9+7;
class Solution {
public:
    int fib(int n) {
        if(n == 0 || n == 1)
            return n;
        return (fib(n - 1) %mod + fib(n - 2)%mod)%mod;
    }
};


const int maxn = 101;
const int mod = 1e9+7;
int demo[maxn];
class Solution {
public:

    int fib(int n) {
        return dp(n);
    }
    int dp(int n){
        if(n == 0 || n == 1)
            return n;
        if(demo[n])
            return demo[n];
        int res = (dp(n - 1) %mod + dp(n - 2)%mod)%mod;
        demo[n] = res;
        return res;
    }
};


const int mod = 1e9+7;
class Solution {
public:
    int fib(int n) {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1; 
        vector dp(n + 1);
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = (dp[i - 1] %mod + dp[i - 2] %mod) %mod;
        }
        return dp[n];
    }
};

10-II、青蛙跳台阶问题

暴力递归：超时
备忘录递归：
dp动态规划（可空间优化）

const int mod = 1e9 + 7;
class Solution {
public:
    int numWays(int n) {
        if(n == 0)
            return 1;
        if(n == 1)
            return 1;
        return (numWays(n - 1)  % mod + numWays(n - 2)) %mod;
    }
};


const int mod = 1e9+7;
int demo[101];
class Solution {
public:
    int numWays(int n) {
        return dp(n);
    }
    int dp(int n){
        if(n == 0)
            return 1;
        if(n == 1)
            return 1;
        if(demo[n])
            return demo[n];
        int res = (dp(n-1) % mod + dp(n-2) % mod) % mod;
        demo[n] = res;
        return res;
    }
};


const int mod = 1e9+7;
class Solution {
public:
    int numWays(int n) {
        if(n == 0)
            return 1;
        if(n == 1)
            return 1;
        vector dp(n + 1);
        dp[0] = 1, dp[1] = 1;
        for(int i = 2; i <= n; i++)
            dp[i] = (dp[i-1] % mod + dp[i-2] % mod) % mod;
        return dp[n];
    }
};

11、旋转数组中的最小数字

可能存在重复元素的数组进行旋转后，找最小数字。

最小值左侧的元素一定大于最小值，右侧的元素一定都大于最小值。

暴力遍历查找：O(n)
二分：O(logn)（可进一步优化）

class Solution {
public:
    int minArray(vector& numbers) {
        
        int n = numbers.size();
        int imin = 5001;
        for(auto num : numbers)
            if(imin > num)
                imin = min(imin, num);
        return imin;

        
        int n = numbers.size();
        int i = 0, j = n - 1;
        while(i < j){ //  注意
            int m = i + (j - i) / 2;
            if(numbers[m] > numbers[j])
                i = m + 1;
            else if(numbers[m] < numbers[j])
                j = m;
            else   
                j = j - 1;
        }
        return numbers[i];
        
		
        int n = numbers.size();
        int i = 0, j = n - 1;
        while(i < j){
            int m = i + (j - i) / 2;
            if(numbers[m] > numbers[j])
                i = m + 1;
            else if(numbers[m] < numbers[j])
                j = m;
            else{
                int x = i;
                for(int k = x; k < j; k++)
                    if(numbers[k] < numbers[x])
                        x = k;
                return numbers[x];
            }
        }
        return numbers[i];
    }
};

思考：为什么是i < j

12、矩阵中的路径

board二维数组，判断是否存在word单词。

dfs + 剪枝

class Solution {
public:
    bool exist(vector>& board, string word) {
        int m = board.size(), n = board[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(dfs(board, word, i, j, 0))
                    return true;
            }
        }
        return false;
    }
    bool dfs(vector>& board, string word, int i, int j, int idx){
        if(idx == word.size()) // 如果先返回false的话，下面则是word.size() - 1
            return true;
        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || word[idx] != board[i][j])
            return false;
        board[i][j] = '*'; // 手动标记  || 或者引入一个used全局数组判断
        bool res = dfs(board, word, i-1, j, idx + 1) || dfs(board, word, i+1, j, idx+1) || dfs(board, word, i,j-1, idx+1) || dfs(board, word, i,j+1, idx+1);
        board[i][j] = word[idx];  
        return res;
    }
};


class Solution {
public:
    bool exist(vector>& board, string word) {
        int m = board.size(), n = board[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(dfs(board, word, i, j, 0))
                    return true;
            }
        }
        return false;
    }
    bool dfs(vector>& board, string word, int i, int j, int idx){
        
        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || word[idx] != board[i][j])
            return false;
        if(idx == word.size() - 1) // 如果先返回false的话，下面则是word.size() - 1
            return true;
        board[i][j] = '*'; // 手动标记  || 或者引入一个used全局数组判断
        bool res = dfs(board, word, i-1, j, idx + 1) || dfs(board, word, i+1, j, idx+1) || dfs(board, word, i,j-1, idx+1) || dfs(board, word, i,j+1, idx+1);
        board[i][j] = word[idx];  
        return res;
    }
};

总结：return true的位置不同，判断条件也不同；遍历过的标记可用bool数组或者，改变字符并回溯；

–

13、机器人的运动范围

DFS + 回溯
优化版本（待完善）

class Solution {
public:
    // vector> used;
    int cnt = 0;
    int movingCount(int m, int n, int k) {
        // bool used[m][n];
        // memset(used, false, sizeof(used));
        // used.resize(m, vector(n));
        vector> used(m, vector(n, false));
        dfs(m, n, 0, 0, k, used);
        return cnt;
    }
    // 可以定义一个有返回值的dfs
    void dfs(int m, int n, int i, int j, int k, vector>& used){
        if(i < 0 || i >= m || j < 0 || j >= n)
            return ;
        if(sum(i) + sum(j) > k)
            return ;
        if(used[i][j])
            return ;
        used[i][j] = true;
        cnt++;
        dfs(m, n, i + 1, j, k, used);
        dfs(m, n, i, j + 1, k, used);
    }
    int sum(int n){
        int res = 0;
        while(n){
            res += n % 10;
            n = n / 10;
        }
        return res;
    }
};

14、剪绳子I

动态规划
贪心算法
可以证明，将绳子剪成最多的以3位长度的段，剩下的直接统计结果；这是可以经过数学证明的贪心思路。

class Solution {
public:
    int cuttingRope(int n) {
    	
        if(n == 2)
            return 1;
        vector dp(n + 1);
        dp[2] = 1;
        for(int i = 3; i <= n; i++){
            for(int j = 1; j < i; j++)
                dp[i] = max({dp[i], (i-j) * j, dp[j] * (i - j)});
            cout << i << "*" << dp[i] << endl;
        }
        return dp[n];
	
		
		if(n == 2)
			return 1;
		if(n == 3)
			return 2;
		if(n == 4)
			return 4;
		int res = 1;
		while(n > 4){
			res *= 3;
			n -= 3;
		}
		return res*n;
    }
};

14、剪绳子 II

此题是在剪绳子I的进阶版，涉及了大数越界时的求余问题，存在着数学上的解题方法，但此刻只采用贪心算法进行求解，后续回炉再次完善本题的学习。

int cuttingRope(int n){
	if(n == 2)
		return 1;
	if(n == 3)
		return 2;
	if(n == 4)
		return 4;
	long res = 1; // 注意此处的不同
	while(n > 4){
		res = res * 3 % mod;
		n = n - 3;
	} 
	return (int)(res * n % mod); // 注意要将返回值显式类型转换
}

15、二进制中1的个数

必备知识点：计算二进制1的个数就是采用位运算技巧，n&(n-1)和n&1都可以计算1的个数，但第一种方法相对更优，遍历次数较少；

class Solution {
public:
    int hammingWeight(uint32_t n) {
    	
        int cnt = 0;
        while(n){
            n = n & (n - 1);
            cnt++;
        }
        cout << cnt << endl;
        return cnt;
		
		
		int cnt = 0;
        while(n){
            cnt += n & 1;
            n = n >> 1;

        }
        cout << cnt << endl;
        return cnt;
    }
};

16、数值的整数次方

实现pow(x, n)；快速幂计算；大数计算必备

double myPow(double x, int n) {
        if(x == 0.0)
            return 0.0;
        long p = n;
        if(p < 0){ // 负数次幂转化
            p = -p;
            x = 1 / x;
        }
        double res = 1.0;
        while(p){
            if(p&1) // 二进制中是否为1
                res *= x;
            x = x*x;
            p = p >> 1;
            // cout << res << "*" << p << endl;
        }
        return res;
    }

17、打印从1到最大的n位数（待完善）

借助pow函数：不考虑大数
递归全排列：
大数打印解法：（待完善）

vector printNumbers(int n) {
    vector res;
    int num = pow(10, n);
    for(int i = 1; i < num; i++){
        res.push_back(i);
    }
    return res; 
}


vector res;
string s;
char nums[10] = {'0','1','2','3','4','5','6','7','8','9'};
vector printNumbers(int n) {
    for(int i = 1; i <= n; i++){
        dfs(0, i);
    }
    vector ans;
    for(int i = 0; i < res.size(); i++)
        ans.push_back(stoi(res[i]));
    return ans;
}
void dfs(int x, int len){
    if(x == len){
        res.push_back(s);
        return;
    }
    int start = x == 0 ? 1 : 0;
    for(int i = start; i < 10; i++){
        s.push_back(nums[i]);
        dfs(x + 1, len);
        s.pop_back();
    }
}

18、删除链表的节点

给定一个链表的头结点和一个要删除的节点值，返回删除节点后的新链表
扩充：如何在O(1)时间内删除一个确定在链表中的节点（交换节点值，再进行删除）

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode* dummy = new ListNode(-1, head);
        ListNode* cur = head, *prev = dummy;
        while(cur->val != val){
            prev = cur;
            cur = cur->next;
        }
        prev->next = cur->next;
        return dummy->next;
    }
};

19、正则表达式匹配（待完善）

20、表示数组的字符串（待完善）

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

新开数组，先存储奇数，再存储偶数
原地置换，类似快速排序比较基准元素的过程

vector exchange(vector& nums) {
    int n = nums.size();
    int i = 0, j = n - 1;
    while(i < j){
        while(i < j && nums[j] % 2 == 0)
            j--;
        while(i < j && nums[i] % 2 == 1)
            i++;
        if(i < j){
            swap(nums[i], nums[j]);
        }
    }
    return nums;
}

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

经典的快慢指针的题目。

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    	// -1 1 2 3 4 5 null
        //  s f               原始指向
        //  s     f           只动fast
        //        s      f    同时移动，结束时指向
    	// 虚拟头结点，指向head
        ListNode* dummy = new ListNode(-1, head);
        // slow指向虚拟头结点，fast指向head
        ListNode* slow = dummy, *fast = head;
        
        for(int i = 0; i < k; i++)
            fast = fast->next;
        while(fast){
            fast = fast->next;
            slow = slow->next;
        }
        return slow->next;
    }
};

24、反转链表

迭代，前后指针交替反转
递归，后序遍历

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
    	
        if(!head ||!head->next)
            return head;
        ListNode* prev = nullptr, *cur = head;
        while(cur){
            ListNode* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
		
		
		if(!head ||!head->next)
            return head;
        ListNode* newNode = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newNode;
    }
};

25、合并两个有序链表（递归待完善）

迭代
递归

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
   		
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while(l1 && l2){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy->next;
    }   
};

26、树的子结构

自己做了好多遍都还是不熟

递归，理解清楚每个函数的作用

class Solution {
public:
	 
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A || !B) // 如果A为空,说明遍历完了A还是没找到B为子结构的树 || 如果B为空,题目说了空树不是任意一个子树的子结构
            return false;
        // B为子结构的前提：B是A左子树的子结构 || B是右子树的子结构 || B和A结构相同,且对应值相同
        return isSubStructure(A->left, B) || isSubStructure(A->right, B) || ok(A, B);
    }
    // ok函数：判断n1和n2两颗树是否结构相同且对应值也相同
    bool ok(TreeNode* n1, TreeNode* n2){
        if(!n2) // n2为空,说明n2遍历完了,n1和n2两树是相同的
            return true;
        if(!n1) // 如果n2非空,n1为空,此时n2非空说明n1不够匹配
            return false;
        if(n1->val != n2->val)// n1和n2均非空,但对应值不相同,匹配失败
            return false;
        // n1和n2均非空且值相同,继续匹配n1左n2左 和 n1右n2右
        return ok(n1->left, n2->left) && ok(n1->right, n2->right); 
    }
};

27、二叉树的镜像

递归、后序遍历
迭代交换（栈和队列都可以）

TreeNode* mirrorTree(TreeNode* root) {
	
	if(!root)
		return nullptr;
	TreeNode* le = mirrorTree(root->left); // 左子树做了镜像操作
	TreeNode* ri = mirrorTree(root->right); // 右子树做了镜像操作
	// 左子树和右子树交换
	root->left = ri; 
	root->right = le;
	return root;

	
	if(!root)
            return nullptr;
    queue q;
    q.push(root);
    while(!q.empty()){
        TreeNode* node = q.front();
        q.pop();
        TreeNode* tmp = node->left;
        node->left = node->right;
        node->right = tmp;
        if(node->left)
            q.push(node->left);
        if(node->right)
            q.push(node->right);
        // 此处交换也可以
        //TreeNode* tmp = node->left;
        //node->left = node->right;
        //node->right = tmp;
    }
    return root;
	
	
	if(!root)
            return nullptr;
    queue stk;
    stk.push(root);
    while(!q.empty()){
        TreeNode* node = stk.top();
        stk.pop();
        TreeNode* tmp = node->left;
        node->left = node->right;
        node->right = tmp;
        if(node->left)
            stk.push(node->left);
        if(node->right)
            stk.push(node->right);
        // 此处交换也可以
        //TreeNode* tmp = node->left;
        //node->left = node->right;
        //node->right = tmp;
    }
    return root;
}

28、对称的二叉树（迭代待完善）

递归：
迭代：

// 函数作用：判断root为根节点的树是否对称
bool isSymmetric(TreeNode* root) {
        if(!root) // 为空,肯定是对称的
            return true;
        return ok(root->left, root->right);
    }
    bool ok(TreeNode* n1, TreeNode* n2){
        if(!n1 && !n2) // 均为空,遍历完了,肯定是对称的
            return true;
        if(!n1 || !n2 || n1->val != n2->val) // 一个节点为空或者都不为空的时候节点值不同,肯定不对称
            return false;
         // 继续判断n1左子树和n2右子树  以及   n1右子树和n2左子树 
        return ok(n1->left, n2->right) && ok(n1->right, n2->left);
    }

29、顺时针打印矩阵

对比两种遍历打印代码差异性

vector spiralOrder(vector>& matrix) {
    int m = matrix.size();
    if(m == 0)
        return vector{};
    int n = matrix[0].size();
    int left = 0, right = n - 1, top = 0, down = m - 1;
    vector res;
    while(left <= right && top <= down){
        for(int j = left; j <= right; j++)
            res.push_back(matrix[top][j]);
        if(++top > down)
            break;
        for(int i = top; i <= down; i++)
            res.push_back(matrix[i][right]);
        if(--right < left)
            break;
        for(int j = right; j >= left; j--)
            res.push_back(matrix[down][j]);
        if(--down < top)
            break;
        for(int i = down; i >= top; i--)
            res.push_back(matrix[i][left]);
        if(++left > right)
            break;
    }
    return res;
    
	
	if (nums.empty() || nums[0].empty())
        return {};
    vector res;
    int left = 0, right = nums[0].size() - 1, top = 0, bottom = nums.size() - 1;
    while (left <= right && top <= bottom) {
    	// 注意下面的不同
        for (int col = left; col <= right; col++)
            res.push_back(nums[top][col]);
        for (int row = top + 1; row <= bottom; row++)
            res.push_back(nums[row][right]);
        if (left < right && top < bottom) {
            for (int col = right - 1; col > left; col--)
                res.push_back(nums[bottom][col]);
            for (int row = bottom; row > top; row--)
                res.push_back(nums[row][left]);
        }
        left++;
        right--;
        top++;
        bottom--;
    } 
    return res;
}

30、包含min函数的栈

辅助栈

class MinStack {
public:
    
    stack stk;
    stack minStk;
    MinStack() {
        minStk.push(INT_MAX); // 存储理论上取不到的最大值
    }
    
    void push(int x) {
        stk.push(x);
        minStk.push(std::min(minStk.top(), x));
    }
    
    void pop() {
        stk.pop();
        minStk.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int min() {
        return minStk.top();
    }
};

31、栈的压入、弹出序列

思路：先将pushed元素依次入栈，入栈之后循环判断栈首元素是否和popped元素相等，不相等则跳过，否则循环将栈首元素出栈并指向popped下一个元素

bool validateStackSequences(vector& pushed, vector& popped) {
        int n = pushed.size();
        stack stk;
        int i = 0;
        for(auto n : pushed){
            stk.push(n);
            while(!stk.empty() && stk.top() == popped[i]){
                stk.pop();
                i++;
            }
        }
        return stk.empty();
    }

32-I、从上到下打印二叉树

层序遍历

vector levelOrder(TreeNode* root) {
    
	if(!root)
        return {};
    vector res;
    queue q;
    q.push(root);
    while(!q.empty()){
        TreeNode* cur = q.front();
        q.pop();
        res.push_back(cur->val);
        if(cur->left)
            q.push(cur->left);
        if(cur->right)
            q.push(cur->right);
    }
    return res;

}

32-II、从上到下打印二叉树II

层序遍历

vector> levelOrder(TreeNode* root) {
	
	if(!root)
        return {};
    vector> res;
    queue q;
    q.push(root);
    while(!q.empty()){
        int n = q.size();
        vector tmp;
        for(int i = 0; i < n; i++){
            TreeNode* cur = q.front();
            q.pop();
            tmp.push_back(cur->val);
            if(cur->left)
                q.push(cur->left);
            if(cur->right)
                q.push(cur->right);
        }
        res.push_back(tmp);
    }
    return res;
}

33-III、从上到下打印二叉树III

思路：数据结构上能头插和尾插的是deque；结果可以flag标记并通过reverse反转；

层序遍历

vector> levelOrder(TreeNode* root) {
    if(!root)
        return {};
    vector> res;
    queue q;
    q.push(root);
    int flag = 1;
    while(!q.empty()){
        int n = q.size();
        vector tmp;
        for(int i = 0; i 
            TreeNode* cur = q.front();
            q.pop();
            tmp.push_back(cur->val);
            if(cur->left)
                q.push(cur->left);
            if(cur->right)
                q.push(cur->right);  
        }
        if(flag == 1){
            res.push_back(tmp);
        }
        else{
            reverse(tmp.begin(), tmp.end());
            res.push_back(tmp);
        }
        flag = -flag;
    }
    return res;
}

33、二叉搜索树的后序遍历序列（待完善）

递归分治：左右根
[4 8 6] [12 16 14] 10
左子树右子树根
单调栈

bool verifyPostorder(vector& postorder) {
        int n = postorder.size();
        return help(postorder, 0, n - 1);
    }
    bool help(vector& postorder, int le, int ri){
        if(le >= ri) // 
            return true;
        int m = le; 
        // 找第一个大于根节点的值，就是右子树的起点
        while(m < ri && postorder[m] < postorder[ri])
            m++;
        int p = m; // 记录右子树的起始节点
        while(m < ri && postorder[m] > postorder[ri])
            m++;
        // [le, m-1]左子树   [m, ri-1]右子树   ri根节点
        return m == ri && help(postorder, le, p - 1) && help(postorder, p, ri - 1);
    }

34、二叉树中和为某一值的路径（待完善）

dfs、回溯
bfs

vector> res;
vector path;
vector> pathSum(TreeNode* root, int target) {
    dfs(root, target, 0);
    return res;
}
void dfs(TreeNode* root, int target, int sum){
    if(!root)
        return ;
    sum += root->val;
    path.push_back(root->val);
    if(!root->left && !root->right && sum == target)
        res.push_back(path);
    dfs(root->left, target, sum);
    dfs(root->right, target, sum);
    path.pop_back();
    sum -= root->val;
}


vector> res;
vector path;
vector> pathSum(TreeNode* root, int target) {
    dfs(root, target);
    return res;
}
void dfs(TreeNode* root, int sum){
    if(!root)
        return ;
    sum -= root->val;
    path.push_back(root->val);
    if(sum == 0 && !root->left && !root->right)
        res.push_back(path);
    dfs(root->left, sum);
    dfs(root->right, sum);
    path.pop_back();
}

35、复杂链表的复制（待完善）

哈希表：
递归：
原地修改：



class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)
            return nullptr;
        unordered_map imap;
        Node* cur = head;
        while(cur){
            imap[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        while(cur){
            imap[cur]->next = imap[cur->next];
            imap[cur]->random = imap[cur->random];
            cur = cur->next;
        }
        return imap[head];
    }
};



class Solution {
public:
    unordered_map imap;
    Node* copyRandomList(Node* head) {
       if(!head)
            return nullptr;
        if(!imap.count(head)){
            Node* newNode = new Node(head->val);
            imap[head] = newNode;
            newNode->next = copyRandomList(head->next);
            newNode->random = copyRandomList(head->random);
        }
        return imap[head];
    }
};

分割线 36、二叉搜索树与双向链表（待完善）

37、序列化二叉树（待完善）

38、字符串的排列（待完善）

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

40、最小的k个数

41、数据流的中位数

42、连续子数组的最大和

43、1~n整数中1的出现次数

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

45、把数组排成最小的数

46、把数字翻译成字符串

47、礼物的最大价值

48、最长不含重复字符的子字符串

49、丑数

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

总结

待完善ing

剑指offer(第二版)

C/C++/C#相关栏目本月热门文章