剑指offer题解【全】 蔚落 2022-12-22 09:37 86阅读 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/
还没有评论,来说两句吧...