剑指offer集锦"/>
LeecCode剑指offer集锦
文章目录
- 剑指 Offer 09. 用两个栈实现队列
- 剑指 Offer 30. 包含min函数的栈
- 剑指 Offer 06. 从尾到头打印链表
- 剑指 Offer 35. 复杂链表的复制
- 剑指 Offer 05. 替换空格
- 剑指 Offer 58 - II. 左旋转字符串
- 剑指 Offer 03. 数组中重复的数字
- 剑指 Offer 53 - I. 在排序数组中查找数字 I
- 剑指 Offer 53 - II. 0～n-1中缺失的数字
- 剑指 Offer 04. 二维数组中的查找
- 剑指 Offer 50. 第一个只出现一次的字符
- 面试题32 - I. 从上到下打印二叉树
- 剑指 Offer 26. 树的子结构
- 剑指 Offer 27. 二叉树的镜像
- 剑指 Offer 28. 对称的二叉树
- 剑指 Offer 10- I. 斐波那契数列
- 剑指 Offer 63. 股票的最大利润
- 剑指 Offer 47. 礼物的最大价值
- 剑指 Offer 46. 把数字翻译成字符串
- 剑指 Offer 48. 最长不含重复字符的子字符串
- 剑指 Offer 18. 删除链表的节点
- 剑指 Offer 22. 链表中倒数第k个节点
- 剑指 Offer 25. 合并两个排序的链表
- 剑指 Offer 52. 两个链表的第一个公共节点
- 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
- 剑指 Offer 57. 和为s的两个数字
- 剑指 Offer 58 - I. 翻转单词顺序
- 剑指 Offer 12. 矩阵中的路径
- 剑指 Offer 13. 机器人的运动范围
- 剑指 Offer 34. 二叉树中和为某一值的路径
- 剑指 Offer 36. 二叉搜索树与双向链表
- 剑指 Offer 54. 二叉搜索树的第k大节点
- 剑指 Offer 45. 把数组排成最小的数
- 剑指 Offer 61. 扑克牌中的顺子
- 剑指 Offer 41. 数据流中的中位数
- 剑指 Offer 55 - I. 二叉树的深度
- 剑指 Offer 55 - II. 平衡二叉树
- 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
- 剑指 Offer 68 - II. 二叉树的最近公共祖先
- 剑指 Offer 07. 重建二叉树
- 剑指 Offer 16. 数值的整数次方
- 剑指 Offer 33. 二叉搜索树的后序遍历序列
- 剑指 Offer 15. 二进制中1的个数
- 剑指 Offer 65. 不用加减乘除做加法
- 剑指 Offer 56 - I. 数组中数字出现的次数
- 剑指 Offer 56 - II. 数组中数字出现的次数 II
- 剑指 Offer 66. 构建乘积数组
- 剑指 Offer 57 - II. 和为s的连续正数序列
- 剑指 Offer 62. 圆圈中最后剩下的数字
- 剑指 Offer 29. 顺时针打印矩阵
- 剑指 Offer 31. 栈的压入、弹出序列
- 剑指 Offer 59 - I. 滑动窗口的最大值
- 剑指 Offer 59 - II. 队列的最大值
- 剑指 Offer 38. 字符串的排列
- 剑指 Offer 49. 丑数
- 1～n 整数中 1 出现的次数
- 剑指 Offer 44. 数字序列中某一位的数字
剑指 Offer 09. 用两个栈实现队列
题目很简单，在纸上画一下就懂了，不过可以复习一下类和STL的知识。
class CQueue {
public:stack<int> s1;stack<int> s2;CQueue() {}void appendTail(int value) {s1.push(value);}int deleteHead() {int head;if (s2.empty()) {if (s1.empty()) {return -1;}else {while (!s1.empty()) {s2.push(s1.top());s1.pop();}}}head = s2.top();s2.pop();return head;}
};
剑指 Offer 30. 包含min函数的栈
class MinStack {
public:/** initialize your data structure here. */int s[20000] = {};int size = 0;int smin = 0;MinStack() {}void push(int x) {if (size == 0) {smin = x;}else {smin = smin > x ? x : smin;}s[size++] = x;}void pop() {if (size > 0) {size--;}if (size > 0) {if (s[size] == smin) {smin = s[0];for (int i = 1; i < size; i++) {if (s[i] < smin) {smin = s[i];}}}}}int top() {if (size > 0) {return s[size-1];}else {return -1;}}int min() {return smin;}
};
从排名可以看出，这是一个比较蠢的做法，我申请的大数组浪费了一些内存空间，并且由于使用了遍历，pop函数的复杂度变成了O(n)。
看了一下大佬的解法，原来是要引入辅助栈来存储当前的最小值，新的解法如下
class MinStack {
public:/** initialize your data structure here. */stack<int> values;stack<int> curmins;MinStack() {}void push(int x) {values.push(x);if (curmins.empty() || x <= curmins.top()) {curmins.push(x);} }void pop() {if (values.top() == curmins.top()) {curmins.pop();}values.pop();}int top() {return values.top();}int min() {return curmins.top();}
};剑指 Offer 06. 从尾到头打印链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:vector<int> reversePrint(ListNode* head) {stack<int> s;vector<int> v;ListNode* t = head;while(t != NULL) {s.push(t->val);t = t->next;}while(!s.empty()) {v.push_back(s.top());s.pop();}return v;}
};
剑指 Offer 35. 复杂链表的复制
/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/
class Solution {
public:Node* copyRandomList(Node* head) {Node* tmp = head;if (head == NULL) {return tmp;}vector <Node*> Nodes;vector <Node*> ONodes;Nodes.push_back(new Node(tmp -> val));ONodes.push_back(tmp);int number = 1;while(tmp->next != NULL) {tmp = tmp -> next;Nodes.push_back(new Node(tmp -> val));ONodes.push_back(tmp);Nodes[number-1] -> next = Nodes[number];number ++;}for (int i = 0; i < number; i++) {Node * t = ONodes[i] -> random;if (t != NULL) {for (int j = 0; j < number; j++) {if (t == ONodes[j]) {Nodes[i] -> random = Nodes[j];break;}}}}return Nodes[0];}
};
很笨的遍历办法，不过简单易懂。看了下题解，原来可以用哈希表存储原链表节点 和新链表对应节点的键值对映射关系，这样我就不用二次遍历了。。。
剑指 Offer 05. 替换空格
class Solution {
public:string replaceSpace(string s) {string ss;string r = "%20";for (int i = 0; i < s.length(); i++) {if (s[i] == ' ') {ss += r;}else {ss += s[i];}}return ss;}
};
只能说too naive。。。
剑指 Offer 58 - II. 左旋转字符串
class Solution {
public:string reverseLeftWords(string s, int n) {return s.substr(n, s.length()-n)+s.substr(0, n);}
};
还看到了一个三次翻转法，非常有趣，虽然时间复杂度上去了，但空间复杂度下来了，reverse这个函数也很好用。
class Solution {
public:string reverseLeftWords(string s, int n) {reverse(s.begin(), s.begin()+n);reverse(s.begin()+n, s.end());reverse(s.begin(), s.end());return s;}
};
剑指 Offer 03. 数组中重复的数字
简单的思路是使用map，用无序的哈希表会更快一点，要是用bitset那就是超级无敌快
class Solution {
public:int findRepeatNumber(vector<int>& nums) {unordered_map <int, bool> m;for (int n: nums) {if (!m[n]) {m[n] = true;}else {return n;}}return nums[0];}
};
还有一种就是利用题目中的信息在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内，这说明可以在不申请额外空间的情况下，把当前索引和值的一一映射转换为索引和与索引相等值的一对多映射。
class Solution {
public:int findRepeatNumber(vector<int>& nums) {int curvalue = 0;for (int i = 0; i < nums.size(); i++) {while (nums[i] != i) {curvalue = nums[i];if (i != curvalue && nums[curvalue] == curvalue) {return curvalue;}nums[i] = nums[curvalue];nums[curvalue] = curvalue;}}return curvalue;}
};
剑指 Offer 53 - I. 在排序数组中查找数字 I
一个重要的教训：如果要同时判断数组索引是否越界和对应数组索引的值是否正确，要先判断前者，否则会出现访问地址越界的问题。另外，二分法更新left和right我这里其实写得不好，应该是left = mid+1; right = mid-1才对，以及while里面要写left和right的相对关系而不是对mid值的判断，这样才能找到最左边第一个符合条件的 值。
class Solution {
public:int search(vector<int>& nums, int target) {if (nums.empty()) {return 0;}int left = 0, right = nums.size()-1, mid = (left+right)/2;int count = 0;while(nums[mid] != target) {if (right - left <= 1) {if (nums[left] == target || nums[right] == target) {count++;}return count;}if (nums[mid] < target) {left = mid;}else {right = mid;}mid = (left+right)/2;}count++;for (int i = mid-1; i >= left && nums[i] == target; i--, count++);for (int i = mid+1; i <= right && nums[i] == target; i++, count++);return count;}
};
剑指 Offer 53 - II. 0～n-1中缺失的数字
class Solution {
public:int missingNumber(vector<int>& nums) {int left = 0, right = nums.size()-1;while(left <= right) {int mid = (left+right)/2;if (nums[mid] == mid) {left = mid+1;}else {right = mid-1;}}return left;}
};
剑指 Offer 04. 二维数组中的查找
class Solution {
public:bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {if (matrix.size() == 0 || matrix[0].size() == 0) {return 0;}int n = matrix.size(), m = matrix[0].size();int x1 = 0, y1 = m-1;while(x1 < n && y1 > -1) {if (target == matrix[x1][y1]) {return true;}for (; y1 > -1 && target < matrix[x1][y1]; y1--);for (; y1 > -1 && x1 < n && target > matrix[x1][y1]; x1++);}return false;}
};
思路较为简单，从右上或者左下往对角方向运动，注意对空矩阵和边界条件的判断
剑指 Offer 50. 第一个只出现一次的字符
class Solution {
public:char firstUniqChar(string s) {int cur_index = 0, first_index = 50002;int char_indexes[26] = {};for (int i = 0; i < s.length(); i++) {cur_index = s[i]-'a';if (char_indexes[cur_index] == 0) {char_indexes[cur_index] = i+1;}else if(char_indexes[cur_index] > 0) {char_indexes[cur_index] = -1;}}for (char c = 'a'; c <= 'z'; c++) {cur_index = char_indexes[c-'a'];if (cur_index > 0 && cur_index < first_index) {first_index = cur_index;}}if (first_index == 50002) {return ' ';}else {return s[first_index-1];}}
};
看到题解里有队列解法，赶紧试了试
class Solution {
public:char firstUniqChar(string s) {int cur_index = 0;queue <char> q;int char_indexes[26] = {};for (char c: s) {cur_index = c-'a';if (char_indexes[cur_index] == 0) {char_indexes[cur_index] = 1;q.push(c);}else if(char_indexes[cur_index] > 0) {Achar_indexes[cur_index] = -1;while (!q.empty() && char_indexes[q.front()-'a'] == -1) {q.pop();}}}if (q.empty()) {return ' ';}return q.front();}
};
面试题32 - I. 从上到下打印二叉树
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vector<int> levelOrder(TreeNode* root) {vector <int> V;if (root == NULL) {return V;}queue <TreeNode*> Q;Q.push(root);while (!Q.empty()) {V.push_back(Q.front()->val);if (Q.front()->left) {Q.push(Q.front()->left);}if (Q.front()->right) {Q.push(Q.front()->right);}Q.pop();}return V;}
};
一个变体是要把每一层的节点具体打印出来，那就要在更新队列时记录原先的大小
/*** 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) {vector<vector<int>> V;if (root == NULL) {return V;}int size;vector<int> L;queue <TreeNode*> Layer;Layer.push(root);while(!Layer.empty()) {size = Layer.size();for (int i = 0; i < size; i++) {L.push_back(Layer.front() -> val);if (Layer.front() -> left) {Layer.push(Layer.front() -> left);}if (Layer.front() -> right) {Layer.push(Layer.front() -> right);}Layer.pop();}V.push_back(L);L.clear();}return V;}
};
如果要求之字形打印，可以使用reverse翻转或者是vector的insert方法实现头插。
剑指 Offer 26. 树的子结构
首先变A不变B，然后AB一起变
/*** 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 isSubStructure(TreeNode* A, TreeNode* B) {if (A == NULL || B == NULL) {return false;}if (A -> val == B -> val && compareStructure(B, A)) {return true; }return isSubStructure(A -> left, B) || isSubStructure(A -> right, B);}bool compareStructure(TreeNode* B, TreeNode* A) {if (B == NULL) {return true;}if (A == NULL) {return false;}if (B -> val != A -> val) {return false;}return compareStructure(B -> left, A -> left) && compareStructure(B -> right, A -> right);}
};
剑指 Offer 27. 二叉树的镜像
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* mirrorTree(TreeNode* root) {if (root == NULL) {return NULL;}TreeNode* tmp;tmp = mirrorTree(root->right);root->right = mirrorTree(root->left);root->left = tmp;return root;}
};
剑指 Offer 28. 对称的二叉树
用两个队列相反方向遍历
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == NULL) {return true;}queue <TreeNode*> leftfirst;queue <TreeNode*> rightfirst;leftfirst.push(root);rightfirst.push(root);TreeNode* ll;TreeNode* lr; TreeNode* rl; TreeNode* rr;while (!leftfirst.empty() && !rightfirst.empty()) {ll = leftfirst.front()->left;lr = leftfirst.front()->right;rr = rightfirst.front()->right;rl = rightfirst.front()->left;if (notEqual(ll, rr) || notEqual(lr, rl)) {return false;}leftfirst.pop();rightfirst.pop();if (ll) {leftfirst.push(ll);rightfirst.push(rr);}if (lr) {leftfirst.push(lr);rightfirst.push(rl);}}return true;}bool notEqual(TreeNode* a, TreeNode* b) {int flag = int(a == NULL) + int(b == NULL);return flag == 0 ? a->val != b->val:flag == 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 isSymmetric(TreeNode* root) {if (root == NULL) {return true;}return isSymmetric(root->left, root->right);}bool isSymmetric(TreeNode* a, TreeNode* b) {int flag = int(a == NULL) + int(b == NULL);return flag == 0 ? a->val == b->val && isSymmetric(a->left, b->right) && isSymmetric(a->right, b->left):flag == 2;}
};
剑指 Offer 10- I. 斐波那契数列
class Solution {
public:int fib(int n) {if (n < 2) {return n;}int* F = new int[n+1]();F[1] = 1;for (int i = 2; i <= n; i++) {F[i] = (F[i-1]+F[i-2])%int(1e9+7);}return F[n];}
};
可以直接用变量代替数组
class Solution {
public:int fib(int n) {int result = 0;if (n < 2) {return n;}int first = 0, second = 1;for (int i = 2; i <= n; i++) {result = (first+second)%int(1e9+7);first = second;second = result;}return result;}
};
剑指 Offer 63. 股票的最大利润
这道题的难点主要在于要比较的是某一区间内的最大值和最小值的大小，因此需要用两个变量分别来记录当前最低的价格和最高的价差。
class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.empty()) {return 0;}int min_price = prices[0], max_diff = 0;for (int i = 1; i < prices.size(); i++) {if (prices[i] < min_price) {min_price = prices[i];}if (prices[i] - min_price > max_diff) {max_diff = prices[i] - min_price;}}return max_diff;}
};
剑指 Offer 47. 礼物的最大价值
class Solution {
public:int maxValue(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();for (int i = 1; i < m; grid[i][0]+=grid[i-1][0], i++);for (int i = 1; i < n; grid[0][i]+=grid[0][i-1], i++);for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {grid[i][j] += max(grid[i-1][j], grid[i][j-1]);}}return grid[m-1][n-1];}
};
剑指 Offer 46. 把数字翻译成字符串
class Solution {
public:int translateNum(int num) {if (num < 10) {return 1;}int twobit = num%100;int lastNum = 1, secondlastNum = 1+int(twobit<26 && twobit>9), finalNum = secondlastNum, lastDigit = (num%100)/10;num /= 100;while(num) {finalNum = secondlastNum;twobit = (num%10)*10+lastDigit;if (twobit > 9 && twobit < 26) {finalNum += lastNum;}lastDigit = num%10;lastNum = secondlastNum;secondlastNum = finalNum;num /= 10;}return finalNum;}
};
剑指 Offer 48. 最长不含重复字符的子字符串
笨办法回溯，碰到出现过的词就往前找，把上一次出现前的词都删了
class Solution {
public:int lengthOfLongestSubstring(string s) {int slength = s.length();if (slength < 2) {return slength;}unordered_map<char, bool> exist_char;int result = 0;char c;for (int i = 0; i < slength; i++) {c = s[i];if (exist_char[c]) {if (exist_char.size() > result) {result = exist_char.size();}exist_char.clear();for (int j = i-1; j > 0 && s[j] != c; exist_char[s[j]] = true, j--);}exist_char[c] = true;}if (exist_char.size() > result) {result = exist_char.size();}return result;}
};
如果让exist char中存储中存储索引而非bool值，那么就可以省去遍历索引的步骤，由于哈希表默认值是0，所以索引加1以区分0位置和不存在这两种情况。
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char, int> char_index;int cur_length = 0, max_length = 0;char c;for (int i = 1; i <= s.length(); i++) {c = s[i-1];cur_length = i-char_index[c] > cur_length ? cur_length + 1:i-char_index[c];char_index[c] = i;max_length = max_length < cur_length?cur_length:max_length;}return max_length;}
};
剑指 Offer 18. 删除链表的节点
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {if (head == NULL) {return NULL;}if (head->val == val) {return head->next;}ListNode* first = head;ListNode* second = head;while(first->val != val) {second = first;first = first->next;}second->next = first->next;return head;}
};
剑指 Offer 22. 链表中倒数第k个节点
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* getKthFromEnd(ListNode* head, int k) {ListNode* first = head;ListNode* last = first;for (int i = 0; i < k; i++) {last = last->next;}while(last != NULL) {first = first->next;last = last->next;}return first;}
};
剑指 Offer 25. 合并两个排序的链表
非递归
/*** 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* head;if (l1->val < l2->val) {head = l1;l1 = l1->next;}else {head = l2;l2 = l2->next;}ListNode* start = head;while(l1 != NULL && l2 != NULL) {if (l1->val < l2->val) {head->next = l1;l1 = l1->next;}else {head->next = l2;l2 = l2->next;}head = head->next;}if (l1) {head->next = l1;}if (l2) {head->next = l2;}return start;}
};
递归
/*** 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;}if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;}else {l2->next = mergeTwoLists(l1, l2->next);return l2;}}
};
剑指 Offer 52. 两个链表的第一个公共节点
使用栈，或者是使用unordered_set遍历
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (!headA || !headB) {return NULL;}ListNode* head = NULL;stack <ListNode*> A;stack <ListNode*> B;while(headA) {A.push(headA);headA = headA->next;}while(headB) {B.push(headB);headB = headB->next;}while(!A.empty() && !B.empty() && A.top() == B.top()) {head = A.top();A.pop();B.pop();}return head;}
};
假设两个链表在相遇之前各自走的路分别是 l 1 l_1 l1和 l 2 l_2 l2，共同走过的路是 l l l，则由于 l 1 + l + l 2 = = l 2 + l + l 1 l_1+l+l_2 == l_2+l+l_1 l1+l+l2==l2+l+l1，因此设置两个指针，先走完自己的路，再去走对方的路，相遇时就是在第一个交点
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *head1 = headA, *head2 = headB;while(head1 != head2) {if (head1 == NULL) {head1 = headB;}else {head1 = head1->next;}if (head2 == NULL) {head2 = headA;}else {head2 = head2->next;}}return head1;}
};
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
class Solution {
public:vector<int> exchange(vector<int>& nums) {int tmp = 0, start = 0, end = nums.size()-1;while(start < end) {for (; start < end && (nums[start] & 1); start++);for (; start < end && !(nums[end] & 1); end--);tmp = nums[start];nums[start] = nums[end];nums[end] = tmp;start++;end--;}return nums;}
};
剑指 Offer 57. 和为s的两个数字
遍历+二分
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> result;int left, mid, right, target_value;for (int i = 0; i < nums.size()-1; i++) {left = i+1;right = nums.size()-1;target_value = target-nums[i];if (target_value < nums[left] || target_value > nums[right]) {continue;}while(left <= right) {mid = (left+right)/2;if (nums[mid] == target_value) {result.push_back(nums[i]);result.push_back(target_value);return result;}else if (nums[mid] > target_value) {right = mid-1;}else {left = mid+1;}}}return result;}
};
双指针，用两个指针分别指向最右最大和最左最小的两个值，如果加起来比目标值大，说明大了，要小点，只能让最大值左移；如果小了，说明要大点，只能让最小值左移，为了提高效率，可以将其与二分结合。
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> result;int left = 0, right = nums.size()-1;while (left <= right) {if (nums[left]+nums[right] == target) {result.push_back(nums[left]);result.push_back(nums[right]);return result;}else if (nums[left]+nums[right] < target) {while(nums[(left+right)/2]+nums[right] < target) {left = (left+right)/2;}left++;}else {while(nums[(left+right)/2]+nums[left] > target) {right = (left+right)/2;}right--;}}return result;}
};
剑指 Offer 58 - I. 翻转单词顺序
class Solution {
public:string reverseWords(string s) {int wordstart = 0, wordend = 0;stack <string> words;string result = "";while(wordend < s.length()) {for(; wordstart < s.length() && s[wordstart] == ' '; wordstart++);wordend = wordstart;for(; wordend < s.length() && s[wordend] != ' '; wordend++);if (wordend != wordstart) {words.push(s.substr(wordstart, wordend-wordstart));}wordstart = wordend;}while(!words.empty()) {result += words.top();words.pop();if (words.empty()) {return result;}result += " ";}return result;}
};
这种解法是从前往后加栈，如果从后往前的话更简单，不需要使用栈了。
剑指 Offer 12. 矩阵中的路径
自己写了比较复杂的一个dfs版本，使用unordered_set来作为visited，算法本身不难，难点主要在于哈希函数的重载（需要让(x,y)和(y,x)这两种情况的哈希值不同）以及unordered_set的插入删除和判断。
class Solution {
public:struct pair_hash {template <class T1, class T2>size_t operator () (pair<T1, T2> const &pair) const {size_t h = hash<T1>()(pair.first*200+pair.second); return h;}};bool exist(vector<vector<char>>& board, string word) {int m = board.size();int n = board[0].size();unordered_set<pair<int, int>, pair_hash> visited;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == word[0] && dfs(board, word, visited, m, n, i, j, 0)) {return true;}}}return false;}bool dfs(vector<vector<char>>& board, string& word, unordered_set<pair<int, int>, pair_hash>& visited, const int& m, const int& n, int i, int j, int step) {visited.insert({i, j});if (step == word.length()-1) {return true;}if (i > 0 && board[i-1][j] == word[step+1] && visited.find({i-1, j}) == visited.end() && dfs(board, word, visited, m, n, i-1, j, step+1)) {return true;}if (i < m-1 && board[i+1][j] == word[step+1] && visited.find({i+1, j}) == visited.end() && dfs(board, word, visited, m, n, i+1, j, step+1)) {return true;}if (j > 0 && board[i][j-1] == word[step+1] && visited.find({i, j-1}) == visited.end() && dfs(board, word, visited, m, n, i, j-1, step+1)) {return true;}if (j < n-1 && board[i][j+1] == word[step+1] && visited.find({i, j+1}) == visited.end() && dfs(board, word, visited, m, n, i, j+1, step+1)) {return true;}visited.erase({i, j});return false;}
};
剑指 Offer 13. 机器人的运动范围
class Solution {
public:int movingCount(int m, int n, int k) {int total_number = 0;vector<vector<bool>> visited(m, vector<bool>(n, false));dfs(0, 0, m, n, k, visited, total_number);return total_number;}int int2bitsum(int n) {int result = 0;while(n) {result += n%10;n /= 10;}return result;}bool dfs(int i, int j, int m, int n, int k, vector<vector<bool>>& visited, int& total_number) {if (i < 0 || i > m-1 || j < 0 || j > n-1) {return false;}if (visited[i][j]) {return false;}if (int2bitsum(i)+int2bitsum(j) > k) {return false;}visited[i][j] = true;total_number++;dfs(i-1, j, m, n, k, visited, total_number);dfs(i+1, j, m, n, k, visited, total_number);dfs(i, j-1, m, n, k, visited, total_number);dfs(i, j+1, m, n, k, visited, total_number);return true;}
};
剑指 Offer 34. 二叉树中和为某一值的路径
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> pathSum(TreeNode* root, int target) {vector<vector<int>> paths;if (root == nullptr) {return paths;}vector<int> path;onepath(root, target, 0, path, paths);return paths;}void onepath(TreeNode* node, int target, int cursum, vector<int> path, vector<vector<int>> & paths) {path.push_back(node->val);if (node->left == nullptr && node->right == nullptr) {if (cursum+node->val == target) {paths.push_back(path);}return;}else {if (node->left) {onepath(node->left, target, cursum+node->val, path, paths);}if (node->right) {onepath(node->right, target, cursum+node->val, path, paths);}}return;}};
这里的一个不足是path每次都要重新复制，空间消耗很大，可以将其定义为函数可访问的类内元素，然后每次函数返回时使用pop_back删掉添加的元素。
剑指 Offer 36. 二叉搜索树与双向链表
/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node() {}Node(int _val) {val = _val;left = NULL;right = NULL;}Node(int _val, Node* _left, Node* _right) {val = _val;left = _left;right = _right;}
};
*/
class Solution {
public:Node* treeToDoublyList(Node* root) {if (root == NULL) {return NULL;}if (root->left == NULL && root->right == NULL) {root->left = root;root->right = root;return root;}Node* leftree = treeToDoublyList(root->left);Node* rightree = treeToDoublyList(root->right);if (leftree == NULL) {leftree = root;leftree->right = rightree;leftree->left = rightree->left;rightree->left->right = leftree;rightree->left = leftree;}else if (rightree == NULL) {root->left = leftree->left;root->right = leftree;leftree->left->right = root;leftree->left = root;}else {root->left = leftree->left;root->right = rightree;leftree->left->right = root;leftree->left = rightree->left;rightree->left->right = leftree;rightree->left = root;}// Node* tmp = leftree;// cout << "left: ";// do {// tmp = tmp->left;// cout << tmp->val << " ";// } while(tmp != leftree);// cout << endl;// cout << "right: ";// do {// tmp = tmp->right;// cout << tmp->val << " ";// } while(tmp != leftree);// cout << endl;return leftree;}
};
学习了一下大佬的方法，使用中序遍历，并且用类的元素来记录上一层遍历时的节点，并改变指针朝向。
剑指 Offer 54. 二叉搜索树的第k大节点
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int order = 0;int result = 0;int kthLargest(TreeNode* root, int k) {if (root == NULL) {return result;}kthLargest(root->right, k);order++;if (order == k) {result = root->val;return result;}if (order < k) {kthLargest(root->left,k);}return result;}
};
注意第k大要中序遍历先右后左，如果是第k小的话就中序遍历。这里是用了额外的变量与k比较，其实还可以直接k–，k为0出局，像下面这样。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int result = 0;int kthLargest(TreeNode* root, int k) {return dfs(root, k);}int dfs(TreeNode* root, int& k) {if (root == NULL) {return result;}dfs(root->right, k);k--;if (k) {dfs(root->left,k);}else {result = root->val;}return result;}
};
剑指 Offer 45. 把数组排成最小的数
class Solution {
public:static bool compare(const int & a, const int & b) {string sa = to_string(a);string sb = to_string(b);return sa+sb < sb+sa;}string minNumber(vector<int>& nums) {sort(nums.begin(), nums.end(), compare);string result = "";for (int i = 0; i < nums.size(); result+=to_string(nums[i]), i++);return result;}
};
剑指 Offer 61. 扑克牌中的顺子
class Solution {
public:bool isStraight(vector<int>& nums) {sort(nums.begin(), nums.end());int zeronum = 0, gapnum = 0;for (; nums[zeronum] == 0; zeronum++);for (int i = zeronum+1; i < nums.size(); i++) {if (nums[i] == nums[i-1]) {return false;}gapnum += nums[i]-nums[i-1]-1;}return gapnum <= zeronum;}
};
这是笨办法，其实要判断一串数是不是连续的，不需要排序，只需要看两点，第一，有没有重复值，第二，最大值和最小值之间的差是不是刚好等于这串数的长度-1，当然由于有大小王的存在，这里可以把等于的条件改成小于等于。
剑指 Offer 41. 数据流中的中位数
class MedianFinder {
public:/** initialize your data structure here. */MedianFinder() {}//存储最小的一半priority_queue<int> big_heap;//存储最大的一半priority_queue<int, vector<int>, greater<int>> small_heap;void addNum(int num) {if (big_heap.empty() && small_heap.empty()) {big_heap.push(num);}else {if (num < big_heap.top()) {big_heap.push(num);}else {small_heap.push(num);}}if (big_heap.size() > small_heap.size()+1) {small_heap.push(big_heap.top());big_heap.pop();}if (small_heap.size() > big_heap.size()+1) {big_heap.push(small_heap.top());small_heap.pop();}}double findMedian() {if (small_heap.size() == big_heap.size()) {return (double(small_heap.top())+big_heap.top())/2;}else if (small_heap.size() > big_heap.size()) {return small_heap.top();}else {return big_heap.top();}}
};
剑指 Offer 55 - I. 二叉树的深度
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {if (root == NULL) {return 0;}return max(maxDepth(root->left), maxDepth(root->right))+1;}
};
剑指 Offer 55 - II. 平衡二叉树
/*** 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 isBalanced(TreeNode* root) {return get_depth(root) != -1;}int get_depth(TreeNode* root) {if (root == NULL) {return 0;}int left_depth = get_depth(root->left);if (left_depth == -1) {return -1;}int right_depth = get_depth(root->right);if (right_depth == -1) {return -1;}if (right_depth-left_depth > 1 || left_depth-right_depth > 1) {return -1;}return max(left_depth, right_depth)+1;}
};
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root->val < p->val && root->val < q->val) {return lowestCommonAncestor(root->right, p, q);}if (root->val > p->val && root->val > q->val) {return lowestCommonAncestor(root->left, p, q);}return root;}
};
剑指 Offer 68 - II. 二叉树的最近公共祖先
/*** 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 {TreeNode* result = NULL;
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {count_son(root, p, q);return result;}int count_son(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == NULL || result != NULL) {return 0;}int count = count_son(root->left, p, q)+count_son(root->right, p, q);if (root == p || root == q) {count += 1;}if (count == 2 && result == NULL) {result = root;}return count;}
};
我的算法呢，其实是在用一个int值为0或者2来标记是否在子树中找到了目标节点，其实也可以用指针的NULL来标记，这样会更加简洁
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == NULL) {return NULL;}if (root == p || root == q) {return root;}TreeNode* leftTree = lowestCommonAncestor(root->left, p, q);TreeNode* rightTree = lowestCommonAncestor(root->right, p, q);if (leftTree && rightTree) {return root;}if (leftTree) {return leftTree;}return rightTree;}
};
剑指 Offer 07. 重建二叉树
前序序列遍历得到根节点， 然后在中序序列中找到根节点的位置并分成两半，递归执行。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int index = 0;return divideTree(preorder, inorder, 0, preorder.size(), index);}TreeNode* divideTree(vector<int>& preorder, vector<int>& inorder, int left, int right, int& index) {if (right-left < 1) {return NULL;}else {TreeNode* root = new TreeNode(preorder[index]);index++;if (right-left == 1) {return root;}else {int middle = left;for (; middle < right && inorder[middle] != preorder[index-1]; middle++);root->left = divideTree(preorder, inorder, left, middle, index);root->right = divideTree(preorder, inorder, middle+1, right, index);return root;}}}
};
优化方向有两个，一个是用哈希表存储节点值对应的中序遍历索引，再一个是将左子树和右子树对应的根节点作为参数传进去。
剑指 Offer 16. 数值的整数次方
class Solution {
public:double myPow(double x, int n) {if (n == 0) {return 1;}if (n == 1) {return x;}if (n == -1) {return 1/x;}int half = n/2;double halfresult = myPow(x, half);if (half == n-half) {return halfresult*halfresult;}else {if (n < 0) {return halfresult*halfresult/x;}else {return halfresult*halfresult*x;}}}
};
另一种思路是将n转换为二进制表示，然后把底数的2转换为指数的 x 2 x^2 x2
class Solution {
public:double myPow(double x, int n) {long nn = n;if (nn < 0) {nn = -nn;x = 1/x;}double result = 1;while(nn) {if (nn&1) {result *= x;}nn >>= 1;x *= x;}return result;}
};
剑指 Offer 33. 二叉搜索树的后序遍历序列
只要能递归找到这样一个点，在它之前的都比根节点小，之后的都比根节点大即可。
class Solution {
public:bool verifyPostorder(vector<int>& postorder) {return dividePostorder(postorder, 0, postorder.size()-1);}bool dividePostorder(vector<int>& postorder, int left, int right) {if (left >= right) {return true;}int middle = left;while(middle < right && postorder[middle] < postorder[right]) {middle++;}for (int i = middle; i < right; i++) {if (postorder[i] < postorder[right]) {return false;}}return dividePostorder(postorder, left, middle-1) && dividePostorder(postorder, middle, right-1);}
};
参考单调栈解法，注意对cur和parent的大小进行判断是因为cur是parent的左孩子的右子树，因此一定会比parent小。
class Solution {
public:bool verifyPostorder(vector<int>& postorder) {int parent = INT_MAX;stack<int> nodes;for (int i = postorder.size()-1; i >= 0; i--) {int cur = postorder[i];while(!nodes.empty() && nodes.top() > cur) {parent = nodes.top();nodes.pop();}if (cur > parent) {return false;}nodes.push(cur);}return true;}
};
剑指 Offer 15. 二进制中1的个数
class Solution {
public:int hammingWeight(uint32_t n) {int result = 0;while(n) {result += n&1;n >>= 1;}return result;}
};
还有一种解法是，注意到n&n-1的效果是将n的最右边的1置为0，所以可以比逐位判断更快一些
class Solution {
public:int hammingWeight(uint32_t n) {int result = 0;for(; n; result++, n &= n-1);return result;}
};
剑指 Offer 65. 不用加减乘除做加法
核心思想是，两个数相加，等价于按位加的结果加上进位的结果
异或运算相当于不考虑进位的求和，与运算相当于求每位的进位
由于LeetCode不支持负数左移，所以要把它强行转换成无符号数
class Solution {
public:int add(int a, int b) {if (!b) {return a;}return add(a^b, static_cast<unsigned int>(a&b)<<1);}
};
剑指 Offer 56 - I. 数组中数字出现的次数
这个的要点是将位运算与分组相结合，首先获取两个数的异或结果，然后截取其中为1的一位并将其他位置为零，最后通过判断所有的数在该位的取值分成两组，在两组内分别执行异或操作。
class Solution {
public:vector<int> singleNumbers(vector<int>& nums) {int result_xor = 0;vector<int> v(2);for (int n: nums) {result_xor ^= n;}int result_xor_right = result_xor ^ (result_xor & result_xor-1);for (int n: nums) {if (n & result_xor_right) {v[0] ^= n;}else {v[1] ^= n;}}return v;}
};
一个优化：v[1] = v[0] ^ result_xor;
剑指 Offer 56 - II. 数组中数字出现的次数 II
统计每一位出现的次数，如果不能被3整除就说明来自单独出现的数字
class Solution {
public:int singleNumber(vector<int>& nums) {vector<int> bits(32);for (int n: nums) {for (int i = 0; i < 32; i++) {bits[i] += (n >> i) & 1;}}int result = 0;for (int i = 0; i < 32; i++) {if (bits[i]%3) {result ^= 1 << i;}}return result;}
};
剑指 Offer 66. 构建乘积数组
很直观的思路是构造两个数组分别存储左乘和右乘的值
class Solution {
public:vector<int> constructArr(vector<int>& a) {if (a.empty()) {return a;}vector<int> left_product(a.size(), a.front());vector<int> right_product(a.size(), a.back());vector<int> result(a.size());for (int i = 1; i < a.size()-1; i++) {left_product[i] = left_product[i-1]*a[i];right_product[a.size()-1-i] = right_product[a.size()-i]*a[a.size()-1-i];}result[0] = right_product[1];result[a.size()-1] = left_product[a.size()-2];for (int i = 1; i < a.size()-1; i++) {result[i] = left_product[i-1]*right_product[i+1];}return result;}
};
也可以用两个变量来存储累积计算值
class Solution {
public:vector<int> constructArr(vector<int>& a) {if (a.empty()) {return a;}int len = a.size();vector<int> result(len,1);int leftProduct = 1, rightProduct = 1;for (int i = 0; i < len; i++) {result[i] *= leftProduct;leftProduct *= a[i];result[len-1-i] *= rightProduct;rightProduct *= a[len-1-i];}return result;}
};
剑指 Offer 57 - II. 和为s的连续正数序列
class Solution {
public:vector<vector<int>> findContinuousSequence(int target) {vector<vector<int>> result;//正整数序列的要求，target/length-length/2 > 0int max_count = sqrt(2*target);int middle_num = 0;int base2 = 0;for (int i = max_count; i > 1; i--) {// 如果i是奇数且能整除，那就可以直接使用// 注意运算符的优先级if (i%2 && !(target%i)) {vector<int> r;middle_num = target/i;for (int j = 0; j < i; j++) {r.push_back(middle_num-i/2+j);}result.push_back(r);}//如果i是偶数，那就需要判断是否可约分，且约分后的值是不是奇数//比如18,4约分后就变成了2,9if (!(i%2)) {base2 = i/2;if (!(target%base2) && (target/base2)%2) {vector<int> r;middle_num = target/i;for (int j = 0; j < i; j++) {r.push_back(middle_num+1-i/2+j);}result.push_back(r);}}}return result;}
};
我这个数学法还是略微麻烦了些，可以直接用求根公式来计算，另外一种解法就是滑动窗口,一个左边界一个右边界，窗口整体上从左到右运动，并根据和理想值的差距微调左右边界
class Solution {
public:vector<vector<int>> findContinuousSequence(int target) {vector<vector<int>> result;vector<int> r;int left = 1, right = 2, window_sum = 3;while(left < right) {if (window_sum == target) {for (int i = left; i <= right; i++) {r.push_back(i);}result.push_back(r);r.clear();}if (window_sum < target) {right++;window_sum += right;}else {//注意这里包含了等于的情况，窗口在这种情况下要右移window_sum -= left;left++;}}return result;}
};
剑指 Offer 62. 圆圈中最后剩下的数字
本来想用set模拟一下的，可惜超时了
class Solution {
public:int lastRemaining(int n, int m) {set<int> numbers;int deleted_number = 0;int deleted_index = 0;for (int i = 0; i < n; i++) {numbers.insert(i);}while (!numbers.empty()) {//从这里回溯deleted_index = (deleted_index+m-1)%numbers.size();auto b = numbers.begin();for (int j = 0; j < deleted_index; j++) {b++;}deleted_number = *(b);numbers.erase(b);}return deleted_number;}
};
这其实是个数学问题，所谓的约瑟夫环，从后往前，推导出一开始所在的下标索引
class Solution {
public:int lastRemaining(int n, int m) {int result = 0;for (int i = 2; i <= n; i++) {result = (result+m)%i;}return result;}
};
剑指 Offer 29. 顺时针打印矩阵
要么单独讨论最后一次
class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int> result;if (matrix.empty() || matrix[0].empty()) {return result;}int start = 0, width = matrix[0].size(), height = matrix.size();while(width > 1 && height > 1) {for (int i = 0; i < width; i++) {result.push_back(matrix[start][start+i]);}width--;for (int i = 1; i < height; i++) {result.push_back(matrix[start+i][start+width]);}height--;for (int i = width-1; i >= 0; i--) {result.push_back(matrix[start+height][start+i]);}width--;for (int i = height-1; i > 0; i--) {result.push_back(matrix[start+i][start]);}height--;start++;}if (width == 1) {for (int i = 0; i < height; i++) {result.push_back(matrix[start+i][start]);}}else {if (height == 1) {for (int i = 0; i < width; i++) {result.push_back(matrix[start][start+i]);}}}return result;}
};
要么加入判断语句
class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int> result;if (matrix.empty() || matrix[0].empty()) {return result;}int start = 0, width = matrix[0].size(), height = matrix.size();int total_number = width * height;while(width >= 1 && height >= 1) {for (int i = 0; i < width; i++) {result.push_back(matrix[start][start+i]);}width--;if (result.size() == total_number) {break;}for (int i = 1; i < height; i++) {result.push_back(matrix[start+i][start+width]);}height--;if (result.size() == total_number) {break;}for (int i = width-1; i >= 0; i--) {result.push_back(matrix[start+height][start+i]);}width--;if (result.size() == total_number) {break;}for (int i = height-1; i > 0; i--) {result.push_back(matrix[start+i][start]);}height--;if (result.size() == total_number) {break;}start++;}return result;}
};
剑指 Offer 31. 栈的压入、弹出序列
class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack <int> s;int index = 0;for (int p: pushed) {if (p == popped[index]) {index++;}else {s.push(p);}while(!s.empty() && s.top() == popped[index]) {index++;s.pop();}}return s.empty();}
};
剑指 Offer 59 - I. 滑动窗口的最大值
本质上是个聪明一点的暴力解
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> result;if (k == 0) {return result;}if (k == 1) {return nums;}int max = nums[0], left = 0, right = k;for (int i = left; i < right; i++) {if (max < nums[i]) {max = nums[i];}}result.push_back(max);while(right < nums.size()) {left++;right++;if (nums[left-1] < max) {max = max < nums[right-1] ? nums[right-1]: max;}else {max = nums[left];for (int i = left+1; i < right; i++) {if (max < nums[i]) {max = nums[i];}}}result.push_back(max);}return result;}
};
第二种方法，维护一个从头到尾索引对应值单调递减的双端队列，当插入新节点时，从尾往头删除比新节点小的，从头到尾删除不在当前范围的
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> result;if (k == 0) {return result;}if (k == 1) {return nums;}deque <int> max_index;max_index.push_front(0);for (int i = 1; i < k; i++) {while(!max_index.empty() && nums[max_index.back()] < nums[i]) {max_index.pop_back();}max_index.push_back(i);}result.push_back(nums[max_index.front()]);for (int i = k; i < nums.size(); i++) {while(!max_index.empty() && nums[max_index.back()] < nums[i]) {max_index.pop_back();}while(!max_index.empty() && max_index.front() <= i-k) {max_index.pop_front();}max_index.push_back(i);result.push_back(nums[max_index.front()]);}return result;}
};
剑指 Offer 59 - II. 队列的最大值
class MaxQueue {
public:queue <int> Q;deque <int> maxQ;MaxQueue() {}int max_value() {if (Q.empty()) {return -1;}return maxQ.front();}void push_back(int value) {Q.push(value);while (!maxQ.empty() && maxQ.back() < value) {maxQ.pop_back();}maxQ.push_back(value);}int pop_front() {if (Q.empty()) {return -1;}if (maxQ.front() == Q.front()) {maxQ.pop_front();}int r = Q.front();Q.pop();return r;}
};/*** 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();*/
这道题主要的思路就是维护一个递减的双端队列
和最大栈的区别：
新加入的元素如果比队列中的大，需要弹出队列的元素，min栈根本不用弹出
剑指 Offer 38. 字符串的排列
和一般的全排列问题相比，主要难度在于会出现重复的字符，那就要么用set标记，要么可以先排个序，然后看看和之前的词重不重复
class Solution {
public:vector<string> permutation(string s) {vector<string> result;substring(s, "", result);return result;}void substring(string originals, string curs, vector<string> & result) {unordered_set<char> visited;if (originals.length() == 1) {result.push_back(curs+originals);return;}for (int i = 0; i < originals.length(); i++) {if (visited.count(originals[i]) == 0) {substring(originals.substr(0,i)+originals.substr(i+1), curs+originals[i], result);visited.insert(originals[i]);}}return;}
};
class Solution {
public:vector<string> permutation(string s) {vector<string> result;sort(s.begin(), s.end());substring(s, "", result);return result;}void substring(string originals, string curs, vector<string> & result) {if (originals.length() == 1) {result.push_back(curs+originals);return;}for (int i = 0; i < originals.length(); i++) {if (i == 0 || (i > 0 && originals[i] != originals[i-1])) {substring(originals.substr(0,i)+originals.substr(i+1), curs+originals[i], result);}}return;}
};
剑指 Offer 49. 丑数
核心思想是，新的丑数是由已知丑数*2or3or5得到的。
class Solution {
public:int nthUglyNumber(int n) {if (n < 7) {return n;}queue <int> number2;queue <int> number3;queue <int> number5;number2.push(1);number3.push(1);number5.push(1);int result = 1;for (int i = 2; i <= n; i++) {result = min(2*number2.front(), min(3*number3.front(), 5*number5.front()));number2.push(result);number3.push(result);number5.push(result);if (2*number2.front() == result) {number2.pop();}if(3*number3.front() == result) {number3.pop();}if(5*number5.front() == result) {number5.pop();}}return result;}
};
};
要是用动态规划的话会更加简单一点，直接用a,b,c三个指针标记上述队列的首位对应的索引。
1～n 整数中 1 出现的次数
class Solution {
public:int countDigitOne(int n) {if (n<1) {return 0;}int count = 0;int base = 1;int left = n;int mid = 0;int right = 0;while (true) {mid = left%10;left /= 10;right = n%base;count += left*base;if (mid==1) {//从0加到rightcount += right+1;}else if(mid > 1)count += base;if (left == 0) {break;}base*=10;}return count;}
};
剑指 Offer 44. 数字序列中某一位的数字
class Solution {
public:int findNthDigit(int n) {if (n < 10) {return n;}//由于数字序列是从0开始的，为简化起见，假设其从1开始n--;long number_width = 1;long number_number = 9;long total_width = 0;long start_number = 1;while(total_width+number_number*number_width < n) {total_width += number_number*number_width;number_number *= 10;number_width++;start_number *= 10;}//判断当前的数字int number = start_number+(n-total_width)/number_width;//判断该取数字的第几位int index = (n-total_width)%number_width;return to_string(number)[index]-'0';}
};
更多推荐
LeecCode剑指offer集锦
发布评论