Jayce's Blog

PROBLEM15. 三数之和 难度 中等 MY ANSWER无。 BETTER SOLUTION先排序，然后确定第一个数，使用双指针遍历第二和第三个数，左指针指向头右指针指向尾，和小于0则增加左指针，大于0则减少右指针，遇到重复数则跳过。时间复杂度O(n^2)，空间复杂度O(1)。 class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; if(nums.empty() || nums.size() < 3) { return res; } sort(nums.begin(), nums.end()); for(int i = 0; i < nums.size() - 2; i++) { if(nu ...

PROBLEM146. LRU 缓存机制 难度 中等 MY ANSWER无。 BETTER SOLUTION双向链表与哈希表实现，哈希表存储key与对应节点指针，双向列表保证删除和添加都为O(1)。双向链表使用虚拟头节点与尾节点来省略空结点判断，每当使用一个节点或增加一个节点，就把节点移到头部，满时将尾节点删除。 struct DLinkedNode { int key, value; DLinkedNode* prev; DLinkedNode* next; DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {} DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}};class LRUCache {private: unordered_map<int, DLinkedN ...

PROBLEM25. K 个一组翻转链表 难度 困难 MY ANSWER困难在于需要考虑的细节比较多，如何让代码更简洁。时间复杂度为O(n)，空间复杂度O(1)。 BETTER SOLUTION通过构造一个头节点dummy指向head，就可以避免一个特殊情况判断，将上一段的尾部指向下一段的头部。使用头插法来进行局部链表的反转，例如反转序列中的 123： prev=0, curr=1: 0 1 2 3 4 -> 0 2 1 3 4 -> 0 3 2 1 4 class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(0), prev = dummy, curr = head, next; dummy.next = head; int length = 0; while(head != null) { length++; ...

PROBLEM剑指 Offer 67. 把字符串转换成整数 难度 中等 MY ANSWER代码较为杂乱。 BETTER SOLUTION处理前置空格与符号不和读取数字放在一个if-else里，处理溢出时注意INT_MIN为-2^32，而INT_MAX为2^32-1。 class Solution {public: int strToInt(string str) { int res = 0; int i = 0; int flag = 1; // 1. 检查空格 while (str[i] == ' ') { i++; } // 2. 检查符号 if (str[i] == '-') { flag = -1; } if (str[i] == '+' || str[i] == ...

PROBLEM剑指 Offer 66. 构建乘积数组 难度 中等 MY ANSWER双循环计算时间复杂度为O(n^2)，TLE。 BETTER SOLUTION思路如图，时间复杂度为O(n)，下三角乘积使用res数组来储存，上三角乘积使用一个变量存储，空间复杂度降低到常数。 class Solution {public: vector<int> constructArr(vector<int>& a) { if(a.empty()) { return {}; } vector<int> res(a.size(), 1); int tmp = 1; for(int i = 1; i < res.size(); i++) { res[i] = res[i-1] * a[i-1]; } for(int i = res ...

PROBLEM剑指 Offer 68 - II. 二叉树的最近公共祖先 难度 简单 MY ANSWER无。 BETTER SOLUTION递归，时间空间复杂度O(n)。 终止条件：当越过叶节点，则直接返回 null；当 root 等于 p, q，则直接返回 root ； 递推工作：开启递归左子节点，返回值记为 left ；开启递归右子节点，返回值记为 right ； 返回值： 根据 left 和 right ，可展开为四种情况； 当 left 和 right 同时为空 ：说明 root 的左 / 右子树中都不包含 p,q ，返回 null ； 当 left 和 right 同时不为空 ：说明 p, q 分列在 root 的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root ； 当 left 为空 ，right 不为空 ：p,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况： p,q 其中一个在 root 的 右子树 中，此时 right 指向 pp（假设为 pp ）； p,q 两节点都在 root 的 右子树 ...

PROBLEM剑指 Offer 65. 不用加减乘除做加法 难度 简单 MY ANSWER无。 BETTER SOLUTION非进位和n=a^b，进位c=a&b<<1，s=a+b= n+c。循环求n和c，直到进位c=0。时间空间复杂度O(1)。需要使用无符号整数才可以移位。 class Solution {public: int add(int a, int b) { while(b != 0) { // 当进位为 0 时跳出 int c = (unsigned int) (a & b) << 1; // c = 进位 a ^= b; // a = 非进位和 b = c; // b = 进位 } return a; }}; SUMMARY熟悉加法的位运算实现，需要使用无符号整数才可以移位。

PROBLEM剑指 Offer 64. 求1+2+…+n 难度 中等 MY ANSWER使用&&来结束递归，时间空间复杂度都为O(n)。 class Solution {public: int sumNums(int n) { n && (n += sumNums(n-1)); return n; }}; BETTER SOLUTION题目对n进行了范围限制，所以可以手动展开进行二进制乘法运算，时间复杂度为O(logn)，空间复杂度O(1)。 乘法原理为：1011 * 101 = 1011 * 100 + 1011 * 1 = 55。同样使用&&进行条件判断。 class Solution {public: int sumNums(int n) { int ans = 0, A = n, B = n + 1; (B & 1) && (ans += A); A < ...

PROBLEM剑指 Offer 62. 圆圈中最后剩下的数字 难度 简单 MY ANSWER无。 BETTER SOLUTION约瑟夫环问题，使用动态规划解答。dp[n]表示n个数删除第m个的最终解，可由dp[n-1]得出，找出dp[n-1]与dp[n]删除一次第m个后的对应关系即可得出递推方程。 dp[n]删除一次后的序列：m, m+1, … , m-3, m-2 dp[n-1]的序列： 0, 1 , … , n-3, n-2 因此可得dp[n] = (dp[n-1] + m) % n 因为只需要上一步结果，因此使用一个变量存储上一步结果即可。 时间复杂度O(n)，空间复杂度O(1)。 class Solution {public: int lastRemaining(int n, int m) { int x = 0; for (int i = 2; i <= n; i++) { x = (x + m) % i; } ...

PROBLEM剑指 Offer 61. 扑克牌中的顺子 难度 简单 MY ANSWER遍历数组，跳过大小王，使用set检查是否有重复，重复则不连续。同时记录数组中最大最小值，若max - min > 4，则不可能连续。时间复杂度O(1)，空间复杂度O(1)。 class Solution {public: bool isStraight(vector<int>& nums) { set<int> dic; int max = 0, min = 14; for(int i = 0; i < nums.size(); i++) { if(nums[i]) { if(nums[i] < min) { min = nums[i]; } if(nums[i] > max) { ...