剑指offer题解【全】

蔚落 2022-12-22 09:37 164阅读 0赞

最近把之前刷过的剑指offer题目总结一下，先列举一部分，待更新……

### [剑指 Offer 03. 数组中重复的数字][Offer 03.] ###

**题意**：

> 找出数组中重复的数字。
> 
> 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

**思路**：

> 假设当前值为x，我们将其放在下标为x的位置，也就是令nums\[x\] = x；如果在交换前发现nums\[x\]=x,即已经存在x这个数了就找到重复的数字了。
> 
> 时间复杂度：O(n) 空间复杂度：O(1)

**代码**：

class Solution { 
    public:
        int findRepeatNumber(vector<int>& nums) { 
        if(nums.empty()) return -1;
        for(int i = 0; i < nums.size(); ++i)
        { 
            if(nums[i] == i) continue;
            if(nums[i] == nums[nums[i]]) return nums[i];
            else swap(nums[i], nums[nums[i]]);
        }
        return -1;
        }
    };
    //https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

### [剑指 Offer 04. 二维数组中的查找][Offer 04.] ###

**题意**：

> 在一个 n \* m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

**思路：**

> 假设我们从右上角开始遍历，每次可以向左或者向右走一步，就会发现向左值就会变小，向下值就会变大，这不就是二叉搜索树吗？所以我们从右上角开始遍历就可以了
> 
> 时间复杂度：O（N) 空间复杂度：O（1）

**代码：**

class Solution 
    { 
    public:
    	bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) 
    	{ 
    		int n = matrix.size();
            if(!n) return false;
            int m = matrix[0].size();
    		if(!m) return false;
            int row = 0, col = m - 1;
    		while(row < n && col >= 0)
            { 
                if(matrix[row][col] == target) return true;
                else if(matrix[row][col] > target) --col;
                else ++row;
            }
    		return false;
    	}
    };
    //https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
    //右上角开始遍历，往左变小，往右变大，相当于二叉搜索树，遍历即可。

### [剑指 Offer 07. 重建二叉树][Offer 07.] ###

**题意：**

> 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

**思路：**

> 对于前序遍历的第一个结点一定是二叉树的根节点，那么中序遍历中根节点之前的结点一定都是左子树。所以我们记录一下中序遍历中每个数出现的位置，然后将中序遍历划分成两个序列，即左子树，根结点，右子树。然后我们对左右子树同样的方法处理即可。
> 
> 时间复杂度：O（N） 空间复杂度O（N）

**代码：**

/** * 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* build(vector<int>& preorder, vector<int>& inorder, int L1, int R1, int L2, int R2)
        { 
            if(L1 > R1 || L2 > R2) return NULL;
            TreeNode *head = new TreeNode(preorder[L1]);
            int pos = mp[preorder[L1]];
            head->left = build(preorder, inorder, L1 + 1, L1 + pos - L2, L2, pos - 1);
            head->right = build(preorder, inorder, R1 - R2 + pos + 1, R1, pos + 1, R2);
            return head;
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 
            for(int i = 0; i < inorder.size(); ++i) mp[inorder[i]] = i;
            return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
        }
    };
    //https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
    //先序第一个点是根节点，找到中序中根节点，左边是左子树，右边是右子树，递归分治

### [剑指 Offer 09. 用两个栈实现队列][Offer 09.] ###

**题意：**

> 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 `appendTail` 和 `deleteHead`，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，`deleteHead` 操作返回 `-1` )

**思路：**

> 首先对于入队列操作，我们将其入栈S1。对于出队操作，我们将栈S2的元素直接出栈，如果栈为空就将栈S1的元素取出来放入栈S2中，这样顺序正好是对的。
> 
> 时间复杂度：O（N） 空间复杂度：O（N）

**代码：**

class CQueue 
    { 
    public:
        stack<int> s1, s2;
        CQueue() 
        { 
            while(!s1.empty()) s1.pop();
            while(!s2.empty()) s2.pop();
        }
        void appendTail(int value) 
        { 
            s1.push(value);
        }
        int deleteHead() 
        { 
            if(s2.empty() && s1.empty()) return -1;
            int x;
            if(!s2.empty()) x = s2.top(), s2.pop();
            else
            { 
                while(!s1.empty())
                { 
                    s2.push(s1.top());
                    s1.pop();
                }
                x = s2.top();
                s2.pop();
            }
            return x;
        }
    };
    
    /** * Your CQueue object will be instantiated and called as such: * CQueue* obj = new CQueue(); * obj->appendTail(value); * int param_2 = obj->deleteHead(); */
    //题目链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

### [剑指 Offer 11. 旋转数组的最小数字][Offer 11.] ###

**题意：**

> 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组`[3,4,5,1,2]` 为`[1,2,3,4,5]` 的一个旋转，该数组的最小值为1。

**思路：**

> 显然这题要用到二分查找，比较当前区间右端点与mid位置的值大小，如果大于的话就让r=mid；如果小于的话另l = mid + 1；否则相等的话说明有重复元素就另r–。
> 
> 时间复杂度：O（logN） 空间复杂度：O（1）

**代码：**

class Solution { 
    public:
        int minArray(vector<int>& numbers) 
        { 
            int x = numbers[0], y = numbers[numbers.size() - 1], ans = x;
            if(x < y) ans = x;
            else
            { 
                int l = 0, r = numbers.size() - 1, mid;
                while(l <= r)
                { 
                    mid = (l + r) >> 1;
                    if(numbers[r] > numbers[mid]) r = mid;
                    else if(numbers[mid] > numbers[r]) l = mid + 1;
                    else --r;
                }
                ans = numbers[l];
            }
            return ans;
        }
    };
    //题目链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

### [剑指 Offer 14- II. 剪绳子 II][Offer 14- II. _ II] ###

**题意：**

> 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0\],k\[1\]…k\[m - 1\] 。请问 k\[0\]*k\[1\]*…\*k\[m - 1\] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
> 
> 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

**思路：**

> 通过对几个数的尝试我们不难发现一些规律，就是尽可能将其划分成3，这样得到的乘积最大。
> 
> 时间复杂度：O（N） 空间复杂度O（1）

**代码：**

class Solution { 
    public:
        int mod = 1e9 + 7;
        long long res = 1;
        int cuttingRope(int n) { 
            if(n < 3) res = 1;
            else if(n == 3) res = 2;
            else if(n % 3 == 0)
            { 
                res = 1;
                for(int i = 1; i <= n / 3; ++i)
                { 
                    res = res * 3 % mod;
                }
            }
            else if(n % 3 == 1)
            { 
                if(n == 1) res = 1;
                else
                { 
                    for(int i = 1; i <= n /3 - 1; ++i)
                        res = res * 3 % mod;
                    res = res * 4 % mod;
                }
            }
            else if(n % 3 == 2)
            { 
                for(int i = 1; i <= n / 3; ++i)
                    res = res * 3 % mod;
                res = res * 2 % mod;
            }
            return (int)res;
        }
    };
    //https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/

### [剑指 Offer 18. 删除链表的节点][Offer 18.] ###

**题意：**

> 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
> 
> 返回删除后的链表的头节点。

**思路：**

> 模拟即可，注意边界范围。
> 
> 时间复杂度：O（N） 空间复杂度：O（1）

**代码：**

class Solution { 
    public:
        ListNode* deleteNode(ListNode* head, int val) { 
            ListNode* h = head;
            if(head->val == val)
            { 
                h = head->next;
            }
            else
            { 
                ListNode* pre = head;
                while(head != NULL)
                { 
                    if(head->val == val)
                    { 
                        //pre = head->next;
                        break;
                    }
                    pre = head;
                    head = head->next;
                }
                head = h;
                while(head != NULL)
                { 
                    if(head->val == pre->val)
                    { 
                        head->next = head->next->next;
                        break;
                    }
                    head = head->next;
                }
            }
            return h;
        }
    };

### [剑指 Offer 19. 正则表达式匹配][Offer 19.] ###

**题意：**

> 请实现一个函数用来匹配包含’. ‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab\*a"均不匹配。

**思路：**

> 定义状态f\[i\] \[j\]串匹配i个字符t串匹配j个字符能否匹配，主要是情况繁多比较麻烦，需要细细分析各种情况。
> 
> 时间复杂度：O（N2) 空间复杂度：O（N2)

**代码：**

class Solution { 
    public:
    	vector<vector<bool> > f;
    	bool isMatch(string s, string p) { 
    		if(!s.empty() && p.empty()) return false;
    		if(s.empty())
    		{ 
    			if(p.empty()) return true;
    			if(p.size() < 2 || (int)p.size() % 2 == 1) return false;
    			bool flag = 1;
    			for(int i = 0; i < p.size() - 1; ++i)
    			{ 
    				if(p[i] != '*' && p[i + 1] != '*') flag = 0;
    			}
    			return flag;
    		}
    		int n = s.size(), m = p.size();
    		vector<bool> v;
    		for(int j = 0; j <= n; ++j) v.push_back(0);
    		for(int i = 0; i <= m; ++i)
    		{ 
    			f.push_back(v);
    		}
    		f[0][0] = 1;
    		bool emp = true; //记录前面的是否能被消除完
    		for(int i = 1; i <= m; ++i)
    		{ 
    			if(i > 1 && p[i - 1] != '*' && p[i - 2] != '*') emp = false;
    			if(emp && p[i - 1] == '.') f[i][1] = 1;
    			if(i > 1 && p[i - 1] == '*' && p[i - 2] == '.')
    			{ 
    				if(emp)
    				{ 
    					for(int k = 1; k <= n; ++k)
    						f[i][k] = f[i - 1][k] = 1;
    				}
    				else
    				{ 
    					for(int k = 0; k <= n; ++k)
    					{ 
    						bool flag = 0;
    						for(int h = 0; h <= k; ++h)
    							if(f[i - 1][h] || f[i - 2][h])
    								flag = 1;
    						f[i][k] = f[i][k] || flag;
    					}
    				}
    				continue;
    			}
    			for(int j = 1; j <= n; ++j)
    			{ 
    				if(p[i - 1] == s[j - 1] || p[i - 1] == '.') f[i][j] = f[i][j] || f[i - 1][j - 1];
    				if(p[i - 1] == '*' && i > 1)
    				{ 
    					f[i][j] = f[i - 1][j] || f[i - 2][j]; //当前位为'*',保留1个或者保留0个
    					if(p[i - 2] == s[j - 1])
    						f[i][j] = f[i][j] || f[i - 1][j - 1] || f[i][j - 1];
    				}
    				if(i > 2 && p[i - 2] == '*' && (p[i - 1] == s[j - 1] || p[i - 1] == '.')) //前一位为'*'
    				{ 
    					f[i][j] = f[i][j] || f[i - 3][j - 1];
    				}
    			}
    		}
    		return f[m][n];
    	}
    };
    //https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/
    //f[i][j] s串匹配i个字符t串匹配j个字符能否匹配

### [剑指 Offer 24. 反转链表][Offer 24.] ###

**题意：**

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

**思路：**

> 双指针法，定义now和next两个指针，next=now->next，另next->next = now，不断遍历操作。
> 
> 时间复杂度：O（N） 空间复杂度：O（1）

**代码：**

/** * 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 == NULL) return head;
            ListNode *h = head, *w = head->next, *tmp = head;
            while(w != NULL)
            { 
                tmp = w->next;
                w->next = h;
                h = w;
                w = tmp;
            }
            head->next = NULL;
            return h;
        }
    };
    //双指针法 将后面的指针的next指向前一个
    //https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

### [剑指 Offer 25. 合并两个排序的链表][Offer 25.] ###

**题意：**

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

**思路：**

> 模拟。
> 
> 时间复杂度：O（N） 空间复杂度：O（1）

**代码：**

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { 
            if(l1 == NULL) return l2;
            if(l2 == NULL) return l1;
            ListNode* ret = l1;
            ListNode *p;
            while(l2 != NULL)
            { 
                while(l1->next != NULL && l1->next->val < l2->val)
                    l1 = l1->next;
                if(l1->val > l2->val) swap(l1->val, l2->val);
                p = l2->next;
                l2->next = l1->next;
                l1->next = l2;
                l2 = p;
            }
            return ret;
        }
    };

### [剑指 Offer 28. 对称的二叉树][Offer 28.] ###

**题意：**

> 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

**思路：**

> 对于根节点的两个儿子left和right，如果满足left->left = right->right && left->right == right->left，那么我们就可以继续往下一层遍历，直到遍历到底层。
> 
> 时间复杂度：O（N） 空间复杂度：O（1）

**代码：**

/** * 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 isequal(TreeNode* rt1, TreeNode* rt2)
        { 
            if(rt1 == NULL && rt2 == NULL) return true;
            if(rt1 == NULL || rt2 == NULL || rt1->val != rt2->val) return false;
            return isequal(rt1->left, rt2->right) && isequal(rt1->right, rt2->left);
        }
        bool isSymmetric(TreeNode* root) { 
            if(root == NULL) return true;
            return isequal(root->left, root->right);
        }
    };
    //https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/

### [剑指 Offer 30. 包含min函数的栈][Offer 30. _min] ###

**题意：**

> 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

**思路：**

> 考虑使用两个栈来模拟，对于第一个栈我们就正常存储值，第二个栈存储当前栈中的最小值，push与pop时执行同样的操作。
> 
> 时间复杂度：O（N） 空间复杂度：O（N）

**代码：**

class MinStack { 
    public:
    	/** initialize your data structure here. */
    	stack<int> s1, s2;
    	MinStack() { 
    	}
    
    	void push(int x) { 
    		s1.push(x);
    		if(!s2.empty() && x > s2.top())
    			x = s2.top();
    		s2.push(x);
    	}
    
    	void pop() { 
    		s1.pop(), s2.pop();
    	}
    
    	int top() { 
            if(s1.empty()) return NULL;
    		return s1.top();
    	}
    
    	int min() { 
            if(s2.empty()) return NULL;
    		return s2.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->min(); */
    //https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
    //用另一个栈记录每个位置的最小值

**思路二：**

> 这道题目有一个比较巧妙的解法，只需要一个栈就行。栈中存放的是当前元素减去最小值的差，如果为负，说明最小值需要更新了。具体看代码：
> 
> 时间复杂度：O（N） 空间复杂度：O（1）

**代码：**

class MinStack { 
    public:
        /** initialize your data structure here. */
        stack<long long> s; //数据比较极限，做差值会超过int表示范围
        long long Min = 0;;
        MinStack() { 
        }
        void push(int x) { 
            if(s.empty())
            { 
                Min = x;
                s.push(0);
            }
            else
            { 
                s.push((long long)x - Min);
                Min = Min < x ? Min : x;
            }
        }
        void pop() { 
            long long x = s.top();
            if(x < 0) //需要更新最小值
                Min = Min - x;
            s.pop();
        }
        int top() { 
            if(s.top() >= 0)
                return  (s.top() + Min);
            long long x = Min;
            return x;
        }
        int min() { 
            return Min;
        }
    };
    
    /** * 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->min(); */

### [剑指 Offer 31. 栈的压入、弹出序列][Offer 31.] ###

**题意：**

> 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 \{1,2,3,4,5\} 是某栈的压栈序列，序列 \{4,5,3,2,1\} 是该压栈序列对应的一个弹出序列，但 \{4,3,5,1,2\} 就不可能是该压栈序列的弹出序列。

**思路：**

> 利用一个辅助栈模拟来实现，我们每次压入一个元素，用一个指针记录出栈序列的下标。如果栈顶元素与当前出栈序列的下标对应的元素相等就一直执行pop操作，最后判断辅助栈是否为空即可。
> 
> 时间复杂度：O（N） 空间复杂度：O（N）

**代码：**

class Solution 
    { 
    public:
    	bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    	{ 
    		if(pushed.empty()) return true;
    		stack<int> s;
    		int p1 = 0, p2 = 0;
    		for(; p1 < pushed.size(); ++p1)
    		{ 
    			s.push(pushed[p1]);
    			while(!s.empty() && s.top() == popped[p2] && p2 < popped.size())
    			{ 
    				s.pop();
    				p2++;
    			}
    		}
    		return (s.empty());
    	}
    };
    //https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
    //压入栈中，栈顶与pop序列指针位置的值相同时一直pop，看最后栈是否为空

### [剑指 Offer 32 - III. 从上到下打印二叉树 III][Offer 32 - III. _ III] ###

**题意：**

> 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

**思路：**

> 记录一下每层有多少个节点，然后记录一下该层是正序还是逆序。当然也可以用双端队列
> 
> 时间复杂度：O（N） 空间复杂度：O（N）

**代码：**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
    	vector<vector<int>> levelOrder(TreeNode* root) 
    	{ 
    		queue<TreeNode* > q;
    		vector<vector<int> > vc;
    		if(root == NULL) return vc;
    		vector<int> v;
    		q.push(root);
    		int now = 1, nxt = 0, flag = 0;
    		while(!q.empty())
    		{ 
    			TreeNode* p = q.front();
    			q.pop();
    			v.push_back(p->val);
    			if(p->left != NULL) q.push(p->left), ++nxt;
    			if(p->right != NULL) q.push(p->right), ++nxt;
    			--now;
    			if(now == 0) //当前层遍历完了
    			{ 
    				if(flag) reverse(v.begin(), v.end());
    				flag ^= 1;
    				vc.push_back(v);
    				v.clear();
    				now = nxt;
    				nxt = 0;
    			}
    		}
    		return vc;
    	}
    };
    //https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
    //可以两个循环，内循环每次遍历一层，用deque不需要reverse

### [剑指 Offer 33. 二叉搜索树的后序遍历序列][Offer 33.] ###

**题意：**

> 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 `true`，否则返回 `false`。假设输入的数组的任意两个数字都互不相同。

**思路：**

> 对于当前序列来说，最后一个结点一定是根结点，那么往前遍历，大于根结点的值一定是右子树，其余的则是左子树部分。然后再分别对这两部分进行同样的操作，就可以

**代码：**

class Solution { 
    public:
    	bool dfs(vector<int>& arr, int l, int r) //后序遍历最后一个是根，将其拆分左右子树递归判断
    	{ 
    		if (l >= r) return true;
    		int p = l;
    		while (arr[p] < arr[r]) ++p;
    		int mid = p;
    		while (arr[p] > arr[r]) ++p;
    		return (p == r && dfs(arr, l, mid - 1) && dfs(arr, mid, r - 1));
    	}
    	bool verifyPostorder(vector<int>& postorder) 
    	{ 
    		return dfs(postorder, 0, postorder.size() - 1);
    	}
    };
    //https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

**优化：**

> 思路：将序列反转，就变成根->右子树->左子树 的遍历序列了，按照这样的遍历方式  
> 如果当前正在遍历右子树，那么序列是递增，遇到变小的数说明遍历到左子树了，这时候  
> 我们就要找到当前子树的根，也就是单调栈不断pop，最后一个大于左子树的点就是根  
> 更新根的值，继续遍历。

**代码：**

class Solution { 
    public:
    	bool verifyPostorder(vector<int>& postorder) 
    	{ 
    		stack<int> s;
    		int root = 0x3f3f3f3f;
    		for (int i = postorder.size() - 1; i >= 0; --i)
    		{ 
    			if (postorder[i] > root) return false;
    			while (!s.empty() && postorder[i] < s.top()) //单调递增栈
    			{ 
    				root = s.top();
    				s.pop();
    			}
    			s.push(postorder[i]);
    		}
    		return true;
    	}
    };

### [剑指 Offer 39. 数组中出现次数超过一半的数字][Offer 39.] ###

**题意：**

> 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
> 
> 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

**思路：**

> 记录一下当前记录的数字，如果与当前记录的数字相同就+1，否则就-1.如果cnt=0的话就更换一下记录的数字并更新cnt，由于出现次数大于一半，所以最后记录的一定是答案。
> 
> 时间复杂度：O（N） 空间复杂度：O（1）

**代码：**

class Solution { 
    public:
        int majorityElement(vector<int>& nums) { 
            int cur = nums[0], cnt = 1;
            for(int i = 1; i < nums.size(); ++i)
            { 
                cnt += (nums[i] == cur ? 1 : -1); //与当前记录的数字相同就+1，否则就-1
                if(!cnt) cur = nums[i], cnt = 1;
            }
            return cur;
        }
    };
    //https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/

### [剑指 Offer 41. 数据流中的中位数][Offer 41.] ###

**题意：**

> 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
> 
> 例如，
> 
> \[2,3,4\] 的中位数是 3
> 
> \[2,3\] 的中位数是 (2 + 3) / 2 = 2.5
> 
> 设计一个支持以下两种操作的数据结构：
> 
> void addNum(int num) - 从数据流中添加一个整数到数据结构中。  
> double findMedian() - 返回目前所有元素的中位数。

**思路：**

> 用两个set来维护，一个用来记录前一半最小的，那么第二个set的首元素就是答案，接下来就是比较麻烦的维护过程了。
> 
> 时间复杂度：O（nLogn） 空间复杂度：O（N)

**代码：**

class MedianFinder { 
    public:
        /** initialize your data structure here. */
        multiset<int> s1, s2;
        MedianFinder() { 
        }
    
        void addNum(int num) { 
            if(s1.size() == 0)
                s1.insert(num);
            else
            { 
                if(s1.size() > s2.size())
                { 
                    if(*s1.rbegin() > num)
                    { 
                        auto it = s1.end();
                        --it;
                        s2.insert(*it);
                        s1.erase(it);
                        s1.insert(num);
                    }
                    else s2.insert(num);
                }
                else
                { 
                    if(*s2.begin() < num)
                    { 
                        s1.insert(*s2.begin());
                        s2.erase(s2.begin());
                        s2.insert(num);
                    }
                    else s1.insert(num);
                }
            }
        }
        double findMedian() { 
            if(s1.size() == 0) return NULL;
            double res = 0;
            if(s1.size() > s2.size()) res = *s1.rbegin();
            else res = 1.0 * (*s1.rbegin() + *s2.begin()) / 2;
            return res;
        }
    };
    /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */
    //https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
    //也可以用一个大根堆和一个小根堆来完成

### [剑指 Offer 45. 把数组排成最小的数][Offer 45.] ###

**题意：**

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

**思路：**

> 将其当做字符串排序，重载比较运算符。
> 
> 时间复杂度：O（nlogn） 空间复杂度：O(N)

**代码：**

class Solution { 
    public:
    	static bool cmp(string s1, string s2)
    	{ 
    		return s1 + s2 < s2 + s1;
    	}
    	string minNumber(vector<int>& nums) { 
    		vector<string> v;
    		for (auto val : nums) v.push_back(to_string(val));
    		sort(v.begin(), v.end(), cmp);
    		string s;
    		for (auto val : v) s += val;
    		return s;
    	}
    };

### [剑指 Offer 46. 把数字翻译成字符串][Offer 46.] ###

**题意：**

> 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

**思路：**

> 将其转换为字符串，定义f\[i\]表示以i结尾的数量，那么f\[i\] = f\[i - 1\] + f\[i - 2\] (如果中间的字符串转换成整数在\[1, 26\]中)。
> 
> 时间复杂度：O（N） 空间复杂度：O（N）

**代码：**

class Solution { 
    public:
        int f[22];
        bool check(char c1, char c2)
        { 
            if(c1 == '0') return false;
            int x = (c1 - '0') * 10 + c2 - '0';
            return x <= 25;
        }
        int translateNum(int num) { 
            string s;
            while(num)
            { 
                s.push_back('0' + num % 10);
                num /= 10;
            }
            s.push_back('0');
            reverse(s.begin(), s.end());
            int n = s.size() - 1;
            f[0] = 1;
            for(int i = 1; i <= n; ++i)
            { 
                f[i] = f[i - 1];
                if(i > 1)
                { 
                    if(check(s[i - 1], s[i]))
                        f[i] += f[i - 2];
                }
            }
            return f[n];
        }
    };
    //https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/

### [剑指 Offer 48. 最长不含重复字符的子字符串][Offer 48.] ###

**题意：**

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

**思路：**

> 一：哈希+双指针
> 
> 二：f\[i\]以i结尾的最长长度 s\[i\]上次出现位置pos，如果pos<f\[i - 1\], f\[i\] = f\[i -1\] + 1; 否则f\[i\] = i - pos;
> 
> 时间复杂度：O（N） 空间复杂度：O（N）

**代码：**

class Solution { 
    public:
    	unordered_map<char, int> vis;
    	int lengthOfLongestSubstring(string s) { 
    		if (s.empty()) return 0;
    		int L = 1, R = 1, ans = 1;
    		for (int i = 1; i <= s.size(); ++i)
    		{ 
    			vis[s[i - 1] - 'a']++;
    			while (vis[s[i - 1] - 'a'] > 1 && L <= i)
    			{ 
    				vis[s[L - 1] - 'a']--;
    				++L;
    			}
    			ans = max(ans, i - L + 1);
    		}
    		return ans;
    	}
    };
    //https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
    //双指针+哈希
    
    //动态规划 f[i]以i结尾的最长长度 s[i]上次出现位置pos，如果pos<f[i - 1], f[i] = f[i -1] + 1; 否则f[i] = i - pos;
    class Solution { 
    public:
    	int f[2];
    	unordered_map<char, int> vis;
    	int lengthOfLongestSubstring(string s) { 
    		if (s.empty()) return 0;
    		f[0] = 1;
    		int ans = 1;
    		for (int i = 1; i <= s.size(); ++i)
    		{ 
    			int now = i & 1, pos = 0;
    			if (vis.count(s[i - 1])) pos = vis[s[i - 1]];
    			if (pos < i - f[!now]) f[now] = f[!now] + 1;
    			else f[now] = i - pos;
    			vis[s[i - 1]] = i;
    			ans = max(ans, f[now]);
    		}
    		return ans;
    	}
    };

### [剑指 Offer 49. 丑数][Offer 49.] ###

**题意：**

> 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

**思路：**

**代码：**

class Solution { 
    public:
    	int f[1700];
    	int nthUglyNumber(int n) { 
    		f[1] = 1;
    		int p1 = 1, p2 = 1, p3 = 1;
    		for (int i = 2; i <= n; ++i)
    		{ 
    			f[i] = min({ f[p1] * 2, f[p2] * 3, f[p3] * 5});
    			if (f[i] == f[p1] * 2) ++p1;
    			if (f[i] == f[p2] * 3) ++p2;
    			if (f[i] == f[p3] * 5) ++p3;
    		}
    		return f[n];
    	}
    };
    //https://leetcode-cn.com/problems/chou-shu-lcof/

### [剑指 Offer 52. 两个链表的第一个公共节点][Offer 52.] ###

**题意：**

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

如下面的两个链表：

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qqCU3hXr-1605766551900)(C:\\Users\\先森\\Pictures\\photos\\160\_statement.png)\]

在节点 c1 开始相交。

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ySDyKape-1605766551903)(C:\\Users\\先森\\Pictures\\photos\\160\_example\_1.png)\]

示例 1：

输入：intersectVal = 8, listA = \[4,1,8,4,5\], listB = \[5,0,1,8,4,5\], skipA = 2, skipB = 3  
输出：Reference of the node with value = 8  
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 \[4,1,8,4,5\]，链表 B 为 \[5,0,1,8,4,5\]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

**思路：**

> 两个指针分别指向A的首节点和B的首节点，当A访问到尾后另其指向B的首节点，当B方问到尾后指向A的首节点，这样第一个相同的节点就是要找的节点。
> 
> 时间复杂度：O（N） 空间复杂度：O（1）

**代码：**

class Solution { 
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { 
            ListNode *node1 = headA;
            ListNode *node2 = headB;
            
            while (node1 != node2) { 
                node1 = node1 != NULL ? node1->next : headB;
                node2 = node2 != NULL ? node2->next : headA;
            }
            return node1;
        }
    };

### [剑指 Offer 56 - I. 数组中数字出现的次数][Offer 56 - I.] ###

**题意：**

> 一个整型数组 `nums` 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

**思路：**

> 将所有数分成两组，满足1.所有相同的数在同一组；2.a与b在不同组  
> 取a^b=x，选x某位为1假设为第cnt位，那么对所有数如果第cnt位值相同就放一组  
> 不同就放不同组，结果显然
> 
> 时间复杂度：O（N） 空间复杂度：O（1）

**代码：**

class Solution 
    { 
    public:
    	vector<int> singleNumbers(vector<int>& nums) 
    	{ 
    		int x = 0, cnt = 0;
    		for (auto val : nums) x ^= val;
    		while (x)
    		{ 
    			if (x & 1) break;
    			++cnt;
    			x >>= 1;
    		}
    		int y = 0; x = 0;
    		for (auto val : nums)
    		{ 
    			if (val & (1 << cnt)) x ^= val;
    			else y ^= val;
    		}
    		return {  x, y };
    	}
    };
    //https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/submissions/

### [剑指 Offer 56 - II. 数组中数字出现的次数 II][Offer 56 - II. _ II] ###

**题意：**

> 在一个数组 `nums` 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

**思路：**

> 统计每一位1出现多少次，对3取模就是答案当前位是否为1
> 
> 时间复杂度：O（N） 空间复杂度：O（N）

**代码：**

class Solution { 
    public:
        int cnt[33];
        int singleNumber(vector<int>& nums) { 
            for(auto val : nums)
            { 
                for(int i = 0; i <= 30; ++i)
                { 
                    if(val & (1 << i))
                        cnt[i]++;
                }
            }
            int res = 0;
            for(int i = 0; i <= 30; ++i)
            { 
                if(cnt[i] % 3 == 1) res += (1 << i);
            }
            return res;
        }
    };
    //https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/

### [剑指 Offer 57 - II. 和为s的连续正数序列][Offer 57 - II. _s] ###

\{  
if (x & 1) break;  
\++cnt;  
x >>= 1;  
\}  
int y = 0; x = 0;  
for (auto val : nums)  
\{  
if (val & (1 << cnt)) x ^= val;  
else y ^= val;  
\}  
return \{ x, y \};  
\}  
\};  
//https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/submissions/

### [剑指 Offer 56 - II. 数组中数字出现的次数 II](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/)
    
    **题意：**
    
    > 在一个数组 `nums` 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
    
    **思路：**
    
    > 统计每一位1出现多少次，对3取模就是答案当前位是否为1
    >
    > 时间复杂度：O（N）    空间复杂度：O（N）
    
    **代码：**
    
    ```cpp
    class Solution {
    public:
        int cnt[33];
        int singleNumber(vector<int>& nums) {
            for(auto val : nums)
            {
                for(int i = 0; i <= 30; ++i)
                {
                    if(val & (1 << i))
                        cnt[i]++;
                }
            }
            int res = 0;
            for(int i = 0; i <= 30; ++i)
            {
                if(cnt[i] % 3 == 1) res += (1 << i);
            }
            return res;
        }
    };
    //https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/

### [剑指 Offer 57 - II. 和为s的连续正数序列][Offer 57 - II. _s] ###

[Offer 03.]: https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
[Offer 04.]: https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
[Offer 07.]: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
[Offer 09.]: https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
[Offer 11.]: https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
[Offer 14- II. _ II]: https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/
[Offer 18.]: https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/
[Offer 19.]: https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/
[Offer 24.]: https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
[Offer 25.]: https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
[Offer 28.]: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
[Offer 30. _min]: https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
[Offer 31.]: https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
[Offer 32 - III. _ III]: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
[Offer 33.]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
[Offer 39.]: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
[Offer 41.]: https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
[Offer 45.]: https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
[Offer 46.]: https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
[Offer 48.]: https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
[Offer 49.]: https://leetcode-cn.com/problems/chou-shu-lcof/
[Offer 52.]: https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
[Offer 56 - I.]: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
[Offer 56 - II. _ II]: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
[Offer 57 - II. _s]: https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/