51.栈的压入与弹出序列(剑指offer原31题)
- 解题思路：模拟一遍整个过程，每次往栈里面加一个元素，加完后判断当前栈顶元素是否是当前弹出序列的元素。如果是，则将栈顶元素弹出。当栈里面已经是空时，弹出序列就是合法的，否则就是不合法的!
#include <iostream> #include <vector> #include <stack> using namespace std; class Solution{ public: bool isPopOrder(vector<int> pushV, vector<int> popV){ if(popV.size() != pushV.size()) return false; stack<int> s; int index = 0; for(int i = 0; i < pushV.size(); i++){ s.push(pushV[i]); while(!s.empty() && s.top() == popV[index]){ s.pop(); index++; } } if(s.empty()) return true; return false; } };
52.不分行从上往下打印二叉树[层序遍历](剑指offer原32题---题目一)
- 解题思路：宽度优先搜索BFS，利用队列这个数据结构来实现。
#include <iostream> #include <vector> #include <queue> using namespace std; struct TreeNode{ int val; TreeNode *left; TreeNode* right; TreeNode(int x): val(x), left(nullptr), right(nullptr){} }; class Solution{ public: vector<int> printFromTopToBottom(TreeNode* root){ vector<int> res; if(!root) return res; queue<TreeNode*> q; q.push(root); while(q.size()) { auto t = q.front(); q.pop(); res.push_back(t->val); if(t->left) q.push(t->left); if(t->right) q.push(t->right); } return res; } };
53.分行从上往下打印二叉树(剑指offer原32题---题目二)
- 解题思路：在队列中增加一个null标记，表示当前层的结点已经全部遍历结束。
#include <iostream> #include <vector> #include <queue> using namespace std; struct TreeNode{ int val; TreeNode *left; TreeNode* right; TreeNode(int x): val(x), left(nullptr), right(nullptr){} }; class Solution{ public: vector<vector<int>> printFromTopToBottom(TreeNode* root){ vector<vector<int>> res; if(!root) return res; queue<TreeNode*> q; q.push(root); q.push(nullptr); vector<int> level; // 辅助的数组表示每层中有多少个结点 while(q.size()){ auto t = q.front(); // 队首元素 q.pop(); if(!t) // t为空时，表示已经遍历完一层 { if(level.empty()) break; // level数组为空时，表示已经遍历完所有的结点，就直接返回 res.push_back(level); level.clear(); q.push(nullptr); continue; } level.push_back(t->val); // t不为空时，将当前的点加入到level中，进行扩展 if(t->left) q.push(t->left); if(t->right) q.push(t->right); } return res; } };
54.之字形打印二叉树(剑指offer原32题---题目三)
- 解题思路：在上一题的基础上增加一个布尔类型的变量zigzag，当zigzag为true时，表示从右到左打印；zigzag为false时，表示从左到右打印！
class Solution{ public: vector<vector<int>> printFromTopToBottom(TreeNode* root){ vector<vector<int>> res; if(!root) return res; queue<TreeNode*> q; q.push(root); q.push(nullptr); vector<int> level; // 辅助的数组表示每层中有多少个结点 bool zigzag = false; // 表示从左到右打印 while(q.size()){ auto t = q.front(); // 队首元素 q.pop(); if(!t) // t为空时，表示已经遍历完一层 { if(level.empty()) break; // level数组为空时，表示已经遍历完所有的结点，就直接返回 if(zigzag) reverse(level.begin(), level.end()); res.push_back(level); level.clear(); q.push(nullptr); zigzag = !zigzag; continue; } level.push_back(t->val); // t不为空时，将当前的点加入到level中，进行扩展 if(t->left) q.push(t->left); if(t->right) q.push(t->right); } return res; } };
55.机器人的运动范围(剑指offer原13题)
- 解题思路：一般考虑使用宽度优先遍历BFS，不建议使用深度优先遍历DFS。因为深度优先遍历在数据范围比较大时，可能会出现栈溢出！从(0,0)点开始遍历，每次将符合要求的格子加入到队列中去。最后一共遍历完多少个合法的格子，就是我们最终的结果。
class Solution { public: // 算出一个数字的各个位置上的数字之和 int get_single_sum(int x){ int s = 0; while(x) { s += x % 10; x /= 10; } return s; } // 算出一个格子中的各个位置上数字之和 int get_sum(pair<int, int> p){ return get_single_sum(p.first) + get_single_sum(p.second); // p.first是x坐标 p.second是y坐标 } int movingcount(int threshold, int rows, int cols){ int res = 0; if(!rows || !cols) return 0; vector<vector<bool>> st(rows, vector<bool> (cols, false)); // 全部初始化成false，记录每个格子是否已经被访问 queue<pair<int, int>> q; q.push({0, 0}); // 初始坐标初始化 int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; // 顺时针来记忆 上 右 下 左 while(q.size()){ auto t = q.front(); q.pop(); if(get_sum(t) > threshold || st[t.first][t.second]) continue; res++; st[t.first][t.second] = true; for(int i = 0; i < 4; i++) { int x = t.first + dx[i], y = t.second + dy[i]; if(x >= 0 && x < rows && y >= 0 && y < cols){ q.push({x, y}); } } } return res; } };
56.剪绳子(剑指offer原14题)
- 题目：给定一个正整数，将此整数划分成若干个更小的正整数的和使得划分出来的若干个正整数的乘积最大。
- 解题思路：目标：假设输入的正整数是N，拆分成尽可能多的3！。分下面几种情况：1.如果N % 3 == 0，则拆分成若干个3；2.如果N % 3 == 1，则先将N拆分成两个2，剩下的全部拆分成3；3.如果N % 3 == 2，则先将N拆分成一个2，剩下的全部拆分成3；
- 证明上面的三种情况：N > 0，N = n1 + n2 + n3 + ...+ nk 1.假设ni >= 5，3 * (ni - 3) >= ni(即3*ni-9 >= ni得到2ni >= 9)是否成立？2.ni = 4， 4 = 2 * 2。由前面的1和2得到拆分出来的数字一定不包含4和大于等于5的数字；因此可知所有拆分出来的ni不是2就是3。接下来证明拆分出来的数字中，最多只有两个2（因为2*2*2 < 3*3）。
class Solution { public: int maxProductAfterCutting(int n){ if(n <= 3) return 1 * (n-1); int res = 1; if(n % 3 == 1) res *= 4, n -= 4; // 拆成出来两个2 if(n % 3 == 2) res *= 2, n -= 2; // 拆出来一个2 while(n) res *= 3, n -= 3; // 拆出来全部都是3 return res; } };
57.二进制中1的个数(剑指offer原15题)
- 解题思路：s += n & 1是先统计n中个位上是数字1的个数，n>>1则是统计完n中个位的结果后，移除n的个位上的数字来进行更新。
class Solution { public: int numberOf1(int _n){ unsigned int n = _n; // 将有符号数转换成无符号数，为了下面的循环 int s = 0; while(n) { s += n & 1; // 每次将n的个位取出来，判断是否是1，是1的话就s++ n >> 1; // 然后将n的个位移除，即n右移一位 } return s; } };
58.数值的整数次方(剑指offer原16题)
- 解题思路：注意处理次方是负数的情况即可！
class Solution { public: double Power(double base, int exponent){ double res = 1; for(int i = 0; i < abs(exponent); i++){ res *= base; } if(exponent < 0) res = 1 / res; return res; } };
59.在O(1)的时间复杂度内删除链表结点（剑指offer原18题--题目一）
- 解题思路：此题不能使用常规方法！因为要删除的结点不是链表的最后一个结点，所以下一个结点一定不是空结点。删除的方法是：用下一个结点的值去覆盖当前结点的值，然后将下一个结点的值删掉。这种方法就不需要用到前驱结点了。
struct ListNode{ int val; ListNode* next; ListNode(int x): val(x), next(nullptr){} }; class Solution { public: void deleteNode(ListNode* node){ node->val = node->next->val; node->next = node->next->next; } };
60.删除链表中重复的结点（剑指offer原18题--题目二）
- 解题思路：建议凡是可能会把头结点删掉的链表问题，一般来说都会增加一个虚拟头结点来简化代码。使用两个指针，第一个指针p指向上一次保留的结点的最后一个位置，q指向的是下一段的第一个结点，q用来扫描下一段的所有结点。
struct ListNode{ int val; ListNode* next; ListNode(int x): val(x), next(nullptr){} }; class Solution{ public: ListNode* deleteDuplication(ListNode* head){ auto dummy = new ListNode(-1); dummy->next = head; auto p = dummy; while(p->next) { auto q = p->next; while(q && p->next->val == q->val){ q = q->next; } if(p->next->next == q) p = p->next; // 下一段的长度是1，没有重复结点，不用删 else p->next = q; // 下一段的长度超过1，则删除重复结点 } return dummy->next; } };
61.正则表达式的匹配（剑指offer原19题）
- 题目：实现一个函数用来匹配包括.和*的正则表达式。字符.表示任意一个字符；字符*表示它前面的字符可以出现任意次（含0次）。
- 解题思路：动态规划问题。状态表示f[i][j]:s[i,...]和p[j,...]是相匹配的；状态转移：情况1：如果p[j]是正常字符，则f[i][j] = s[i] == p[j] && f[i + 1][j + 1]；情况2：p[j]是.，f[i][j] = f[i + 1][j + 1]；情况3：p[j + 1] = *，*表示的字符是0次或*表示的字符匹配1次，则f[i][j] = f[i][j + 2] || f[i + 1][j]；边界问题：f[n][m] = true
class Solution{ public: int n, m; vector<vector<int>> f; string s, p; bool inMatch(string _s, string _p){ s = _s, p = _p; n = s.size(), m = p.size(); f = vector<vector<int>> (n + 1, vector<int>(m + 1, -1)); return dp(0, 0); } bool dp(int x, int y){ if(f[x][y] != -1) return f[x][y]; if(y == m) return f[x][y] = x == n; bool first_match = x < n && (p[y] == '.' || s[x] == p[y]); // 情况1和情况2 if(y + 1 < m && p[y + 1] == '*'){ // 情况3 f[x][y] = dp(x, y + 2) || dp(x + 1, y); } else{ f[x][y] = first_match && dp(x + 1, y + 1); } return f[x][y]; } };
62.表示数值的字符串（剑指offer原20题）
- 解题思路：分各种情况讨论
class Solution{ public: bool isNumber(string s){ int i = 0, j = s.size(); // 删除字符串s中的前后空格 while(i <= j && s[i] == ' ') i++; while(i <= j && s[j] == ' ') j--; if(i > j) return false; s = s.substr(i, j - i + 1); if(s[0] == '+' || s[0] == '-') s = s.substr(1); if(s.empty() || (s[0] == '.' && s.size() == 1)) return false; // + - . int dot = 0, e = 0; // 统计有多少个.和e for(int i = 0; i < s.size(); i++){ if(s[i] >= '0' && s[i] <= '9'); else if(s[i] == '.'){ dot++; if(dot > 1 || e) return false; // 3434.23232.4343, 23232e23232.2323 } else if(s[i] == 'e' || s[i] == 'E'){ e++; if(!i || i + 1 == s.size() || e > 1 || s[i - 1] == '.' && i == 1) return false; // e1223233, 11232e, 1212e32323e if(s[i + 1] == '+' || s[i + 1] == '-'){ if(i + 2 == s.size()) return false; // 12341e+ i++; } } else return false; } return true; } };
63.调整数组顺序使奇数位于偶数前面（剑指offer原21题）
- 题目：输入一个数组，实现数组中数字的顺序，使得所有的奇数位于数组的前半部分；所有的偶数位于后半部分。
- 解题思路：使用双指针，一个指针从前往后，另一个指针从后往前。保证第一个指针前面全部是奇数，第二个指针前面全部是偶数。
class Solution{ public: void reOrderArray(vector<int>& nums){ int first = 0, second = nums.size() - 1; while(first <= second){ while(first <= second && nums[first] % 2 == 1) first++; while(first <= second && nums[second] % 2 == 0) second--; if(first < second) swap(nums[first], nums[second]); } } };
64.链表中倒数第k个节点（剑指offer原22题）
- 解题思路：由于单链表不能从后往前遍历的，只能从前往后遍历。因此首先求出整个链表的长度n，求倒数第k个节点相当于求正序的n-k+1个节点，然后从前往后遍历到n-k+1个节点就可以了。
struct ListNode{ int val; ListNode* next; ListNode(int x): val(x), next(nullptr){} }; class Solution{ public: ListNode* findKthToTail(ListNode* head, int k){ int n = 0; for(auto p = head; p; p = p->next) n++; if(k > n) return nullptr; auto p = head; for(int i = 0; i < n - k; i++) p = p->next; return p; } };
65.链表中环的入口节点（剑指offer原23题）
- 解题思路：使用快慢指针算法，用两个指针first和second分别从起点开始走，first每次走一步，second每次走两步。如果过程中second走到null，则说明不存在环；否则当first和second相遇后，让first返回起点，second待在原地不动，然后两个指针每次分别走一步，当相遇时，相遇点就是环的入口。
struct ListNode{ int val; ListNode* next; ListNode(int x): val(x), next(nullptr){} }; class Solution{ public: ListNode* entryNodeOfLoop(ListNode* head){ auto i = head, j = head; // i是慢指针，每次走一步;j是快指针，每次走两步 while(i && j){ i = i->next; j = j->next; if(j) j = j->next; if(i == j){ // i和j相遇了 i = head; // 慢指针i回到起点 while(i != j){ // 慢指针和快指针同时向后移动一个位置 i = i->next; j = j->next; } return i; // 环入口的位置 } } return nullptr; // 无环存在 } };
66.找出数组中重复的数字（剑指offer原3题---题目一）
- 解题思路：从前往后遍历整个数组中的每个元素，如果元素的取值不在0到n-1范围内，就直接返回-1；如果元素的取值在0到n-1范围内时，检查数组下标是取值为该元素时的数组位置上存储的是哪个数字；如果存储的数字与其在数组中对应的下标相等，则找出了重复的数字，否则将两个位置上的数字进行交换，重复此步骤，直到存储的数字与其在数组中对应的下标相等为止。
class Solution{ public: int duplicateInArray(vector<int>& nums){ for(auto x : nums){ if(x < 0 || x >= nums.size()) return -1; } for(int i = 0; i < nums.size(); i++){ while(i != nums[i] && nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]); if(nums[i] != i && nums[nums[i]] == nums[i]) return nums[i]; } return -1; } };
67.不修改数组，找出数组中重复的数字（剑指offer原3题---题目二）
- 解题思路：根据抽屉原理，至少有2个数字会重复！利用递归的思想，将这个数组一分为二，分别计算左右子数组两边的长度和元素的个数，至少有一边元素的个数会大于子数组的长度。递归上面的过程即可！
class Solution{ public: int duplicateInArray(vector<int>& nums){ int l = 1, r = nums.size() - 1; while(l < r){ int mid = l + r >> 1; // [l, mid], [mid + 1, r] int s = 0; // 统计元素的个数 for(auto x : nums) s += x >= l && x <= mid; if(s > mid - l + 1) r = mid; else l = mid + 1; } return r; } };
68.二维数组中的查找（剑指offer原4题）
- 解题思路：从二维数组右上角的位置开始查找，如果要查找的目标数字比右上角的数字要大，则目标数字出现在二维数组的右下角位置；如果要查找的目标数字比右上角的数字要小，则目标数字出现在二维数组的左上角位置。
class Solution{ public: bool searchArray(vector<vector<int>> array, int target){ if(array.empty() || array[0].empty()) return false; int i = 0, j = array[0].size() - 1; while(i < array.size() && j >=0){ if(array[i][j] == target) return true; if(array[i][j] > target) j--; else i++; } return false; } };
69.替换空格（剑指offer原5题）
- 解题思路：开一个新的字符串，遍历原始的字符串，如果遇到空格字符，就将20%存储在新字符串中；否则，直接存储在新字符串中。
class Solution{ public: string replaceSpaces(string& str){ string res; for(auto x : str){ if(x == ' ') res += "20%"; else res += x; } return res; } };
70.从尾到头打印链表（剑指offer原6题）
- 解题思路：先将整个链表遍历一遍，然后将整个链表翻转一下即可。
class Solution{ public: vector<int> printListReversingly(ListNode* head){ vector<int> res; while(head){ res.push_back(head->val); head = head->next; } return vector<int>(res.rbegin(), res.rend()); } };
71.重建二叉树（根据前序遍历和中序遍历来重建二叉树）（剑指offer原7题）
- 解题思路：首先，根据前序遍历确定当前区间的根节点是哪个；然后，根据已经确定的根节点，从中序遍历中找到根节点的位置在哪，从而确定二叉树的左右子树中分别包含的数字；最后，在已经确定的左右子树中递归执行前面的两个步骤，即可重建二叉树。
struct TreeNode{ int val; TreeNode* left; TreeNode* right; TreeNode(int x): val(x), left(nullptr), right(nullptr){} }; class Solution{ public: map<int, int> hash; // 开一个hash表，记录每个节点在数组中的位置 vector<int> preorder, inorder; TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder){ preorder = _preorder, inorder = _inorder; for(int i = 0; i < inorder.size(); i++){ hash[inorder[i]] = i; } return dfs(0, preorder.size() - 1, 0, inorder.size() - 1); } TreeNode* dfs(int pl, int pr, int il, int ir){ if(pl > pr) return nullptr; auto root = new TreeNode(preorder[pl]); int k = hash[inorder[root->val]]; auto left = dfs(pl + 1, pl + 1 + k - il - 1, il, k - 1); auto right = dfs(pl + k - il + 1, pr, k + 1, ir); root->left = left; root->right = right; return root; } };
72.二叉树的下一个节点（剑指offer原8题）
- 题目：给定二叉树中的一个节点，找出中序遍历序列的下一个节点
- 解题思路：分情况进行讨论，情况1：如果给定的节点是存在右子树的，则下一个节点是右子树中最左边的节点；情况2：如果给定的节点是不存在右子树的，又分两种情况讨论：a.如果给定的节点存在父节点，并且给定的节点是父节点的左儿子的话，则下一个节点是给定节点的父节点；b.如果给定的节点存在父节点，并且给定的节点是父节点的右儿子的话，此时沿着父节点向上找，直到找到第一个节点是当前父节点的左儿子时停止，返回父节点。
class Solution{ public: TreeNode* inorderSuccessor(TreeNode* p){ if(p->right){ // 情况1 p = p->right; while(p->left) p = p->left; return p; } // 情况2 while(p->father && p == p->father->right) p = p->father; return p->father; } };
73.用两个栈实现一个队列（剑指offer原9题）
- 解题思路：先将元素依次压入栈1中，然后逐个弹出栈1中的元素，将每个元素依次压入栈2中。此时，栈2中的栈顶元素就是栈1中的栈底元素，再依次弹出栈2中的元素时，就实现了队列的先进先出功能（最先进入栈1中的元素，最先从栈2中弹出）。
class MyQueue{ public: stack<int> stk, cache; MyQueue(){ } void push(int x){ stk.push(x); } // 辅助函数 void copy(stack<int>& a, stack<int>& b){ while(a.size()){ b.push(a.top()); a.pop(); } } int pop(){ copy(stk, cache); int res = cache.top(); cache.pop(); copy(cache, stk); return res; } int peak(){ copy(stk, cache); int res = cache.top(); copy(cache, stk); return res; } bool empty(){ return stk.empty(); } };
74.斐波那契数列数列（剑指offer原10题）
class Solution{ public: int Fibonacci(int n){ int a = 0, b = 1; while(n--){ int c = a + b; a = b, b = c; } return a; } };
75.旋转数组的最小数字（剑指offer原11题）
- 解题思路：利用画图法来解决。输入数组是0 1 2 2 2 2 3 4 5,则旋转后的数组是2 2 3 4 5 0 1 2 2。将旋转数组分成两部分2 2 3 4 5和0 1 2 2，两部分是单调的增加。首先将后半部分相同值删除，然后观察剩下的结果可知，所有的元素都比前半部分的第一个元素小。前半部分中后面的值都大于或等于第一个元素。下面就可以使用二分法，找出后半部分中第一个比前半部分第一个元素小的那个数字，就是我们要找的最小数字。
class Solution{ public: int findMin(vector<int>& nums){ int n = nums.size() - 1; if(n < 0) return -1; while(n > 0 && nums[n] == nums[0]) n--; // 去掉后半部分相等的数值 if(nums[n] >= nums[0]) return nums[0]; int l = 0, r = n; while(l < r){ int mid = l + r >> 1; if(nums[mid] < nums[0]) r = mid; else l = mid + 1; } return nums[r]; } };
76.矩阵中的路径（剑指offer原12题）
- 解题思路：先枚举所有起点，然后枚举方向。直到走到不能走为止，这样就得到所有的路径。
class Solution{ public: bool hasPath(vector<vector<char>>& matrix, string str){ for(int i = 0; i < matrix.size(); i++){ for(int j = 0; j < matrix[0].size(); j++){ if(dfs(matrix, str, 0, i, j)) // 枚举所有起点i, j，从字符串str第0个字符串开始枚举 return true; } } return false; } bool dfs(vector<vector<char>>& matrix, string& str, int u, int x, int y){ // 当前字符串str中的第几个字符u，x和y是当前路径的坐标 if(u == str.size()) return true; if(matrix[x][y] != str[u]) return false; // 枚举四个方向 int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; char t = matrix[x][y]; // 已经访问过的字符，不能重新访问 matrix[x][y] = '*'; for(int i = 0; i < 4; i++){ int a = x + dx[i], b = y + dx[i]; if(a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size()){ if(dfs(matrix, str, u + 1, a, b)) return true; } } matrix[x][y] = t; return false; } };
