typedefstruct { int max_distance; int max_depth; } result_t;
// get max distance of two nodes in a tree result_tget_max(tree_node_t* root) { result_t result; if (!root) { result.max_distance = 0; result.max_depth = -1; return result; }
result_t left = get_max(root->left); result_t right = get_max(root->right);
// 利用面积,如果 D 和 ABC 分别构成的三角形的面积小于 ABC 的面积,那么 D 在三角形内部 double area(Point A, Point B, Point, C) { double a, b, c; b = distance(A, C); a = distance(B, C); c = distance(A, B);
double p = (a + b + c) / 2; return sqrt((p-a) * (p-b) * (p-c) * p); }
voidfindSum(TreeNode* root, int sum, vector<int> path, int level) { if (!root) return;
path[level] = root->val; for (int i = level, t= 0; i >= 0; i--) { t += path[i]; if (t == sum) print(path, i ,level); // printing out path from i to level }
string printBinary(double num){ if (num >= 1 || num <= 0) return"error";
string result; result += "."; while (num > 0) { if (result.size() >= 32) return"error"; num *= 2; if (num >= 1) { result += "1"; num -= 1; } else { result += "0"; } }
intneg(int a) { int result = 0; int d = a < 0 ? 1 : -1; while (a) { result += d; a += d; } return result; }
intabs(int a) { return a > 0 ? a : neg(a); }
intminus(int a, int b) { return a + neg(b); }
intmultiply(int a, int b) { int sign = (a > 0) == (b > 0) ? 1 : -1; a = abs(a); b = abs(b); int result = 0; while (b--) result += a; return sign == 1 ? result : neg(result); }
// 迭代 intcountSteps(int n) { int n3 = 1; // starts from n = 0 int n2 = 1; // starts from n = 1 int n1 = 2; // starts from n = 2
if (n < 0) return0; if (n == 0 || n == 1) return1; int steps = 0; for (int i = 3; i <= n; i++) { steps = n3 + n2 + n1; n3 = n2; n2 = n1; n1 = steps; } return steps; }
8.1 设计一种算法,机器人只能向右向下移动,从(0, 0)移动到(x, y)有几种走法
LeetCode 62 63
9.1 在有序数组A[0…n-1]中存在A[i] == i,找出该数字。如果存在重复值,又该如何做
1 2 3 4 5 6 7 8 9 10 11 12 13
intmagic(int* A, n) { int left = 0; right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (A[mid] == mid) return mid; elseif (A[mid] < mid) left = mid + 1; else right = mid - 1; } return-1; }
9.2 返回一个集合的所有子集
LeetCode 78
9.3 全排列
LeetCode
9.4 生成n对括号的全部有效集合
LeetCode
9.5 实现填充颜色功能
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
voidpaintFill(vector<vector<int>> screen, int x, int y, int color){ if (screen[y][x] == color) return; paintFill(screen, int x, int y, screen[y][x], int color); }
voidpaintFill(vector<vector<int>> screen, int x, int y, int start, int color){ if (x < 0 || x >= screen[0].size() || y < 0 || y >= screen.size()) return; if (screen[y][x] == start) { screen[y][x] == color; paintFill(screen, int x-1, int y, start, color); paintFill(screen, x+1, y, start, color); paintFill(screen, x, y+1, start, color); paintFill(screen, x, y-1, start, color); } }
vector<int> twoSum(vector<int>& nums, int target){ unordered_map<int, int> hash; vector<int> result(2); for (int i = 0; i != nums.size(); ++i) { int reminder = target - nums[i]; if (hash.find(reminder) != hash.end()) { result[0] = hash[reminder] + 1; result[1] = i + 1; return result; } hash[nums[i]] = i; } return result; }
Python 解答
1 2 3 4 5 6 7 8 9
classSolution: deftwoSum(self, nums: List[int], target: int) -> List[int]: seen = {} for i, num inenumerate(nums): if target - num in seen: return [seen[target-num], i] else: seen[num] = i return [-1, -1]
functwoSum(nums []int, target int) []int { m := make(map[int]int) for index, num := range nums { last_index, ok := m[num] if ok { return []int{last_index, index} } else { m[target - num] = index } } return []int{-1, -1} }
Follow up: 如果数组是已经排序的呢?
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13
sort(nums.begin(), nums.end()) // 假设已经排序,只有一个结果 pair<int> twoSum(vector<int>& nums, int target){ int left = 0, right = nums.size() - 1; while (left < right) { int s = nums[left] + nums[right]; if (s == target) returnmake_pair(left, right); elseif (s < sum) left++; else right--; } }
2 给两个列表,数字在其中按低位到高位存储,求他们的和
直接迭代遍历数组,考察细节操作。注意 dummy head 的使用。
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { structListNodedummy, *p = &dummy; int carry = 0; // 注意最后如果有 carry 的话,需要再生成一个节点 while (l1 || l2 || carry) { int v1 = l1 ? l1->val: 0; int v2 = l2 ? l2->val: 0; int v = v1 + v2 + carry; p->next = malloc(sizeof(struct ListNode)); p = p->next; p->val = v % 10; p->next = NULL; carry = v / 10;
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None
classSolution: defaddTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode(-1) p = dummy carry = 0 while l1 or l2 or carry: if l1: v1 = l1.val l1 = l1.next else: v1 = 0 if l2: v2 = l2.val l2 = l2.next else: v2 = 0 v = v1 + v2 + carry # 别忘了这里 if v >= 10: carry = 1 v -= 10 else: carry = 0 p.next = ListNode(v) p = p.next return dummy.next
3 最长不重复子串
tags: #slidewindow
滑动窗口解决
注意,当字符有限的时候,比如限定为 ASCII 字符,可以使用一个数组代替 Hash。
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14
intlengthOfLongestSubstring(char* s) { int indices[256]; for (int i = 0; i < 256; i++) // init the array, memset can only be used for char indices[i] = -1; int left = 0; int longest = 0;
for (int i = 0; s[i] != '\0'; i++) { left = max(left, indices[s[i]] + 1); // 考虑新加入字符后对左边界的影响 indices[s[i]] = i; // 更新元素上次出现位置 longest = max(longest, i - left + 1); // 应用动态规划 } return longest; }
Python 解答
1 2 3 4 5 6 7 8 9 10
classSolution: deflengthOfLongestSubstring(self, s: str) -> int: last_seen = {} ans = 0 lo = 0 for i, c inenumerate(s): lo = max(lo, last_seen.get(c, -1) + 1) # 更新下边界 last_seen[c] = i ans = max(ans, i - lo + 1) return ans
// 这个方法不容易理解,建议看 Python 的 char* convert(char* s, int numRows) { int len = strlen(s); if (!s || numRows <= 1 || len < numRows) return s; // no need to convert
char* zigzag = malloc(sizeof(char) * (len + 1)); int cur = 0;
for (int i = 0; i < numRows; i++) { for (int j = i; j < len; j += 2 * (numRows - 1)) { // 每个 v 字型长度 zigzag[cur++] = s[j]; if (i != 0 && i != numRows - 1) { // 中间行有斜线 int t = j + 2 * (numRows - 1) - 2 * i; // V 的第二笔 if (t < len) zigzag[cur++] = s[t]; } } } zigzag[cur] = '\0'; return zigzag; }
classSolution: defconvert(self, s: str, numRows: int) -> str: if numRows <= 1orlen(s) <= numRows: # 没有这个条件会超时 return s interval = 2 * numRows - 2 ans = [] # 第一行 j = 0 while j < len(s): ans.append(s[j]) j += interval # 中间行 for i inrange(1, numRows-1): j = 0 while j < len(s): if i + j < len(s): ans.append(s[i+j]) if interval - i + j < len(s): # 一定要注意这里的索引 ans.append(s[interval - i + j]) j += interval # 最后一行 j = numRows - 1 while j < len(s): ans.append(s[j]) j += interval return"".join(ans)
7 翻转数字,溢出返回 0
注意溢出
C 解答
1 2 3 4 5 6 7 8 9 10 11 12
intreverse(int x) { if (x == INT_MIN) return0; if (x < 0) return -reverse(-x);
long result = 0; while (x) { result = result * 10 + x % 10; x /= 10; }
return result > INT_MAX ? 0 : result; }
Python 解答
1 2 3 4 5 6 7 8 9 10 11
classSolution: defreverse(self, x: int) -> int: sign = 1if x >= 0else -1 x *= sign y = 0 while x > 0: y = y * 10 + x % 10 x //= 10 if y > 2**31: return0 return y * sign
8 实现 atoi
这道题考察各种细节,注意各种特殊情况:
首先过滤空格
判定符号,符号只能出现一次
是否溢出,溢出返回 INT_MAX 或者 INT_MIN
Python 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution: defmyAtoi(self, s: str) -> int: s = s.lstrip() ifnot s: return0 sign = 1 ans = 0 i = 0 if s[i] == "-": sign = -1 i += 1 elif s[i] == "+": i += 1 while i < len(s) and s[i].isdigit(): ans = ans * 10 + ord(s[i]) - ord("0") i += 1 ans *= sign returnmax(min(ans, 2**31-1), - 2 ** 31)
intmyAtoi(char* str) { if (!str) return0; int sign = 1; int result = 0;
// discarding spaces while (isspace(*str)) str++;
// determining sign if (*str == '-' || *str == '+') { if (*str == '-') sign = -1; if (*str == '+') sign = 1; str++; }
// constructing integer while (isdigit(*str)) { // handling overflow if (result > INT_MAX / 10 || result == INT_MAX / 10 && *str - '0' > INT_MAX % 10) return sign > 0 ? INT_MAX : INT_MIN; result = *str - '0' + result * 10; str++; }
return result * sign; }
9 是否是回文数字
限定不能用额外空间,所以直接把 x 取余得到的数字作为一个反向作为一个新的数字
Python 解答
1 2 3 4 5 6 7 8 9 10 11 12
classSolution: defisPalindrome(self, x: int) -> bool: if x < 0: returnFalse if x != 0and x % 10 == 0: returnFalse y = 0 # 回文走到一半就行了,没必要完全翻转过来 while x > y: y = y * 10 + x % 10 x //= 10 return x == y or x == y // 10
C 解答
1 2 3 4 5 6 7 8 9 10 11 12
boolisPalindrome(int x) {
// tricky here, for x == k * 10^j if (x < 0 || x && (x % 10 == 0)) returnfalse; int y = 0; while (x > y) { y = y * 10 + x % 10; x /= 10; }
return x == y || x == y / 10; // 注意 x 可能是奇数长度也可能是偶数 }
boolisMatch(char* s, char* p) { for (char c = *p; c != 0; s++, c = *p) { // if next char in pattern is not * if (*(p+1) != '*') p++; // if we got an *, check if we can skip `.*` or `x*` elseif (isMatch(s, p + 2)) returntrue;
// s ends or p and s differs if (*s == 0 || c != '.' && c != *s) returnfalse; } return *s == 0; }
11 盛最多水的容器
从左右向中间逼近,如果有更大的就更新。简单的一道双指针题目,别想太多。
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13
intmaxArea(vector<int>& height){ int left = 0, right = height.size() - 1; int result = 0; while (left < right) { water = min(height[left], height[right]) * (right - left) result = max(result, water); if (height[left] < height[right]) left++; else right--; } return result; }
Python 解答
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution: defmaxArea(self, height: List[int]) -> int: lo = 0 hi = len(height) - 1 ans = 0 while lo < hi: water = min(height[lo], height[hi]) * (hi - lo) ans = max(ans, water) if height[lo] < height[hi]: lo += 1 else: hi -= 1 return ans
// acts like a dict or map intgetVal(char c) { switch (c) { case'I': return1; case'V': return5; case'X': return10; case'L': return50; case'C': return100; case'D': return500; case'M': return1000; } }
intromanToInt(char* s) { int result = 0; for (int i = 0; s[i] != 0; ) { if (getVal(s[i]) < getVal(s[i+1])) result += getVal(s[i+1]) - getVal(s[i]), i += 2; else result += getVal(s[i]), i++; } return result; }
14 最长公共前缀
纵向扫描,从头到尾,如果不一致,返回当前子串即可。
Python 解答
1 2 3 4 5 6 7 8 9 10 11 12
classSolution: deflongestCommonPrefix(self, strs: List[str]) -> str: ifnot strs: return"" iflen(strs) == 1: return strs[0] minlen = min([len(str) forstrin strs]) for i inrange(minlen): for j inrange(1, len(strs)): if strs[j][i] != strs[0][i]: return strs[0][:i] return strs[0][:minlen]
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
// 纵向扫描 char* longestCommonPrefix(char** strs, int strsSize) { if (!strs || !strs[0]) return""; if (strsSize == 1) return strs[0]; int len = strlen(strs[0]);
for (int i = 0; i < len; i++) { for (int j = 1; j < strsSize; j++) { if (strs[j][i] != strs[0][i]) { strs[0][i] = '\0'; return strs[0]; } } } return strs[0]; }
15 从数组中找出三个数使得他们的和是 0
首先把数组排序,然后使用类似 two sum 的方法做就好了。做这种数组题的套路就是实在不行排个 序。
classSolution: defthreeSum(self, nums: List[int]) -> List[List[int]]: iflen(nums) < 3: return [] nums.sort() ans = [] for i inrange(len(nums)): if i > 0and nums[i] == nums[i-1]: continue k = len(nums) - 1 j = i + 1 while j < k: sum = nums[i] + nums[j] + nums[k] ifsum > 0: k -= 1 elifsum < 0: j += 1 else: ans.append([nums[i], nums[j], nums[k]]) while j < k and nums[j] == nums[j+1]: j += 1 while j < k and nums[k] == nums[k-1]: k -= 1 j += 1 k -= 1 return ans
intthreeSumClosest(int* nums, int numsSize, int target) { if (numsSize <= 3) return nums[0] + nums[1] + nums[2]; qsort(nums, numsSize, sizeof(int), cmp);
int result = nums[0] + nums[1] +nums[2]; for (int i = 0; i < numsSize; i++) { int j = i + 1; int k = numsSize - 1; while (j < k) { int sum = nums[i] + nums[j] + nums[k]; if (sum == target) return target; if (abs(target - sum) < abs(target - result)) result = sum; if (sum > target) k--; else j++; } } return result; }
17 生成电话键盘按键数字对应的所有可能的字符串,不限制返回结果的顺序
tags: #backtracking
递归:
这道题是一道典型的,最简单的深度优先遍历,生成所有可能解的问题。
迭代:
遍历数字,设当前结果为{a, b, c}, 下一个数字是3, 找出对应的字母{d, e, f}, 则新的结果是
for (int i = 0; i < digits.size(); i++) { int digit = digits[i] - '0'; if (mapping[digit].empty()) continue; vector<string> temp; for (auto& c : mapping[digit]) for (auto& combination : combinations) temp.push_back(combination + c); swap(combinations, temp); } return combinations; }
defnSum(self, nums, target, n): defdfs(pos: int, cur: List[int], n: int, target: int): if n == 2: j = pos k = len(nums) - 1 while j < k: sum = nums[j] + nums[k] ifsum < target: j += 1 elifsum > target: k -= 1 else: solution = cur[:] + [nums[j], nums[k]] ans.append(solution) while j < k and nums[j] == nums[j+1]: j += 1 while j < k and nums[k] == nums[k-1]: k -= 1 j += 1 k -= 1 return i = pos while i < len(nums) - n + 1: # 剪枝的一种情况 if nums[i] * n > target or nums[-1] * n < target: break # 排除重复数字 if i > pos and nums[i] == nums[i-1]: i += 1 continue cur.append(nums[i]) dfs(i+1, cur, n-1, target-nums[i]) cur.pop() i += 1 ans = [] nums.sort() dfs(0, [], n, target) return ans
// left 剩下的左括号,right 剩下的右括号 voidgen(vector<string>& result, string s, int left, int right){ if (left == 0 && right == 0) { result.push_back(s); return; } if (left != 0) gen(result, s + '(', left - 1, right); if (left < right) gen(result, s + ')', left, right - 1); }
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) { if (!lists || listsSize < 1) return NULL;
while (listsSize > 1) { // listsize is halfed for (int i = 0; i < listsSize / 2; i++) // merge i and last i list lists[i] = mergeTwoLists(lists[i], lists[listsSize-1-i]); listsSize = (listsSize + 1) / 2; // 注意这里!
defreverseList(self, head): prev = None curr = head while curr: next = curr.next curr.next = prev prev = curr curr = next return prev
defreverseKGroup(self, head: ListNode, k: int) -> ListNode: dummy = ListNode(-1) dummy.next = head p = dummy
while p.next: n = k q = p # 找到下一组接点的头 while n > 0and q.next: q = q.next n -= 1 # 如果节点不够了直接退出 if n > 0: break # 把这段链表先截下来 next = q.next q.next = None tail = p.next p.next = self.reverseList(p.next) p = tail p.next = next return dummy.next
classSolution: defremoveDuplicates(self, nums: List[int]) -> int: iflen(nums) < 2: returnlen(nums) length = 0 for i inrange(len(nums)): # 处理 i == 0 的情况也是需要注意的 if i == 0or nums[i] != nums[length-1]: nums[length] = nums[i] length += 1 return length
C 解答
1 2 3 4 5 6 7 8
intremoveDuplicates(int* nums, int numsSize) { if (numsSize <= 1) return numsSize; int len = 0; for (int i = 0; i < numsSize; i++) if (i == 0 || nums[i] != nums[len - 1]) nums[len++] = nums[i]; return len; }
27 删除元素
和上一题类似,注意细节
Python 解答
1 2 3 4 5 6 7 8 9 10
classSolution: defremoveElement(self, nums: List[int], val: int) -> int: ifnot nums: return0 length = 0 for i inrange(len(nums)): if nums[i] != val: nums[length] = nums[i] length += 1 return length
C 解答
1 2 3 4 5 6 7 8 9
intremoveElement(int* nums, int numsSize, int val) { if (!nums || numsSize == 0) return0; int len = 0; for (int i = 0; i < numsSize; i++) { if (nums[i] != val) nums[len++] = nums[i]; } return len; }
# kmp 算法 classSolution: defstrStr(self, haystack: str, needle: str) -> int: ifnot needle: return0 next = [0] j = 0 # 特别注意这里的 1 for i inrange(1, len(needle)): while j > 0and needle[i] != needle[j]: j = next[j-1] if needle[i] == needle[j]: j += 1 next.append(j) j = 0 for i inrange(len(haystack)): while j > 0and haystack[i] != needle[j]: j = next[j-1] if haystack[i] == needle[j]: j += 1 if j == len(needle): return i - j + 1 return -1
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/* * Brute Force */ intstrStr(char* haystack, char* needle) { int h = strlen(haystack); int n = strlen(needle); if (n == 0) return0; // note h - n + 1 for (int i = 0; i < h - n + 1; i++) { for (int j = 0; j < n; j++) { if (needle[j] != haystack[i+j]) break; if (j == n - 1) return i; } } return-1; }
intdivide(int dividend, int divisor) { // abs(INT_MIN) == INT_MAX + 1 if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX; int sign = (dividend > 0) == (divisor > 0) ? 1 : -1; longlong n = labs(dividend); longlong d = labs(divisor);
int result = 0; while (n >= d) { longlong temp = d; longlong multi = 1; while (n >= (temp << 1)) { temp <<= 1; multi <<= 1; } n -= temp; result += multi; }
classSolution: defsearch(self, nums: List[int], target: int) -> int: ifnot nums: return -1 lo = 0 hi = len(nums) - 1 while lo <= hi: mi = lo + (hi - lo) // 2 if nums[mi] == target: return mi # 这里为什么要包含等于号呢 if nums[lo] <= nums[mi]: if nums[lo] <= target < nums[mi]: hi = mi - 1 else: lo = mi + 1 else: if nums[mi] < target <= nums[hi]: lo = mi + 1 else: hi = mi - 1 return -1
classSolution: def searchRange(self, nums: List[int], target: int) -> List[int]: if not nums: return [-1, -1] lo =0 hi = len(nums) lower = -1 while lo < hi: mi = lo + (hi - lo) // 2 if nums[mi] < target: lo = mi + 1 else: hi = mi if lo < len(nums) and nums[lo] == target: lower = lo
lo = 0 hi = len(nums) upper = -1 while lo < hi: mi = lo + (hi - lo) // 2 if nums[mi] <= target: lo = mi + 1 else: hi = mi if nums[lo-1] == target: upper = lo - 1
return [lower, upper]
35 二分查找数字,如果没有找到,返回应该插入的位置
就是最基础的二分查找
Python 解答
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution: defsearchInsert(self, nums: List[int], target: int) -> int: lo = 0 hi = len(nums) while lo < hi: mi = lo + (hi - lo) // 2 if nums[mi] == target: return mi elif nums[mi] < target: lo = mi + 1 else: hi = mi return lo
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13
intsearchInsert(int* nums, int numsSize, int target) { int left = 0, right = numsSize - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; elseif (nums[mid] < target) left = mid + 1; else right = mid - 1; } return left; }
#define tonum(c) (c - '0') #define tochar(i) (i + '0')
char* multiply(char* num1, char* num2) { // 结果的长度不会超过 m+n, // 假设某个数是 n 位的 9, 则结果比另一个数结尾加上 n 个 0 还小 int n = strlen(num1), m = strlen(num2); int len = m+n; char* result = malloc(sizeof(char) * (len + 1)); for (int i = 0; i < len; i++) result[i] = '0'; result[len] = '\0';
for (int i = n - 1; i >= 0; i--) { int carry = 0; for (int j = m - 1; j >= 0; j--) { int v = tonum(result[i+j+1]) + tonum(num1[i]) * tonum(num2[j]) + carry; result[i+j+1] = tochar(v % 10); carry = v / 10; } result[i] += carry; }
for (int i = 0; i < len; i++) if (result[i] != '0') return result+i;
return"0"; }
44 通配符匹配,? 代表任意一个字符,*代表任意一个或多个字符
注意和正则表达式的区别,要求完全匹配。这道题的关键在于对星号的处理,如果出现星号的时候,我们记录当时的 p 和 s 的值,如果发生了不匹配的话,我们尝试回到该位置的下一个位置开始匹配
boolisMatch(char* s, char* p) { char* star = NULL; char* revert = s; while (*s) { if (*s == *p || *p == '?') s++, p++; elseif (*p == '*') star = p++, revert = s; elseif (star) p = star + 1, s = ++revert; else returnfalse; }
// 如果剩下了 p, 那应该全都是*才对 while (*p) { if (*p++ != '*') returnfalse; }
returntrue; }
45 跳跃游戏,给定一个数组,每个数字是在该位置可以向前移动的距离,返回最少需要多少次才能到达终点
比较简单,看注释吧
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
intjump(int* nums, int numsSize) { int steps = 0; int last = 0; // last range int cur = 0; // current range
for (int i = 0; i < numsSize; i++) { // beyond range, make another jump if (i > last) last = cur, steps++; // if we could reach longer? if (nums[i] + i > cur) cur = nums[i] + i; } return steps; }
voidper(vector<vector<int>>& result, vector<int> nums, int start){ if (start >= nums.size()) { result.push_back(nums); return; }
for (int i = start; i < nums.size(); i++) { if (start != i && nums[start] == nums[i]) continue; swap(nums[start], nums[i]); per(result, nums, start + 1); // 事实证明,传引用反倒会超时 } }
48 给定一个n*n的图像旋转图像,顺时针旋转 90 度
做法显然是从里到外,一层一层的旋转,这道题主要考察下标的操作
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
voidrotate(int** matrix, int m, int n) { for (int layer = 0; layer < n / 2; layer++) { int first = layer; int last = n - 1 - layer; for (int i = first; i < last; i++) { int offset = i - first; int top = matrix[first][i]; // up <- left matrix[first][i] = matrix[last-offset][first]; // left <- down matrix[last-offset][first] = matrix[last][last-offset]; // down <- right matrix[last][last-offset] = matrix[i][last]; // right <- up matrix[i][last] = top; } } }
49 给定字符数组,把他们按照 Anagram 分组
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// Anagram 分组 // 这道题没什么可做的,只需要统计 vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>> result; string temp; unordered_map<string, vector<string>> records; for (int i = 0; i < strs.size(); ++i) { temp = strs[i]; sort(temp.begin(), temp.end()); records[temp].push_back(strs[i]); } for (auto& record : records) { sort(record.second.begin(), record.second.end()); result.push_back(record.second); } return result; }
50 实现 pow(x, n)
显然不能直接阶乘过去,分治法
递归做法
C 解答
1 2 3 4 5 6 7 8 9 10 11 12
// recursive doublemyPow(double x, int n) { if (n == INT_MIN) return myPow(x, n - 1) * x; if (n < 0) return1 / myPow(x, -n); if (n == 0) return1; if (n == 1) return x; double y = myPow(x, n / 2); if (n & 0x1) return y * y * x; else return y * y; }
迭代做法
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13
// iteratively doublemyPow(double x, long p) { double result = 1; if (p < 0) return1 / myPow(x, -p); while (p) { if (p & 1) result *= x; x *= x; p /= 2; } return result; }
int* spiralOrder(int** matrix, int row, int col) { if (row == 0 || col == 0) returnNULL; int top = 0, right = col - 1, down = row - 1, left = 0; int index = 0; int* result = malloc(sizeof(int) * row * col); while (top <= down && left <= right) { for (int i = left; i <= right; i++) result[index++] = matrix[top][i]; top++; // for (int i = top; i <= down; i++) result[index++] = matrix[i][right]; right--; // // 注意这个 if 语句 if (top <= down) for (int i = right; i >= left; i--) result[index++] = matrix[down][i]; down--; // // 注意这个 if 语句 if (left <= right) for (int i = down; i >= top; i--) result[index++] = matrix[i][left]; left++; // } return result; }
55 给定一个数组,每个数字表示在当前步可以移动的距离,返回是不是能够到达终点
使用动态规划求解,如果当前距离大于最远距离,更新最远距离,如果已经超过了最远距离,跳出
C 解答
1 2 3 4 5 6 7
boolcanJump(int* nums, int numsSize) { int i; int reach = 0; for (i = 0; i < numsSize && i <= reach; i++) reach = max(reach, nums[i] + i); return i == numsSize; }
56 合并序列,给定一组序列,把其中重叠的序列合并
这道题用 Python 做竟然比用 C++ 还要快
Python 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
""" class Interval(object): def __init__(self, start=0, end=0): self.start = start self.end= end """
defmerge(intervals): intervals.sort(key=lambda x: x.start) combined = [] for interval in intervals: if combined and interval.start <= combined[-1].end: combined[-1].end = max(combined[-1].end, interval.end) else: combined.append(interval) return combined
57 添加序列,给定一组已经排序的序列,向其中插入一个序列,需要合并的合并
把剩余的部分都拷贝过来也不失为一种机智的做法。
Python 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution: definsert(self, intervals, newInterval): ans = [] start, end = newInterval remainder = 0 for x, y in intervals: # 未重叠 if start > y: ans.append([x, y]) # 进入重叠状态 else: if end < x: # 当前区间已经不重叠了 break# 找到了结尾了 start = min(start, x) end = max(end, y) remainder += 1 ans.append([start, end]) ans += intervals[remainder:] return ans
/** * Return an array of arrays. * Note: The returned array must be malloced, assume caller calls free(). */ int** generateMatrix(int n) { int** matrix = malloc(sizeof(int*) * n); for (int i = 0; i < n; i++) matrix[i] = malloc(sizeof(int) * n);
int top = 0, left = 0, down = n - 1, right = n - 1; int a = 1; while (top <= down && left <= right) { for (int i = left; i <=right; i++) matrix[top][i] = a++; top++; for (int i = top; i <= down; i++) { matrix[i][right] = a++; } right--; if (top <= down) for (int i = right; i >= left; i--) matrix[down][i] = a++; down--; if (left <= right) for (int i = down; i >= top; i--) matrix[i][left] = a++; left++; } return matrix; }
classSolution { public: /*The logic is as follows: for n numbers the permutations can be divided to (n-1)! groups, thus k/(n-1)! indicates the index of current number, and k%(n-1)! denotes remaining sequence (to the right). We keep doing this until n reaches 0, then we get n numbers permutations that is kth. */ string getPermutation(int n, int k){ int f = 1; string s(n, '0'); for (int i = 1; i <= n; i++) { f *= i; s[i-1] = i + '0'; } // 给定 n, 一共有 n! 个序列,f == n!
k--; for (int i = 0; i < n; i++) { f /= n - i; // f /= n, f /= n - 1 ... int j = i + k / f; char c= s[j]; for (;j > i; j--) // shift space to put `c`, actually we could use swap s[j] = s[j-1]; s[i] = c; k %= f; }
intuniquePathsWithObstacles(vector<vector<int>>& obstacleGrid){ int m = obstacleGrid.size(), n = obstacleGrid[0].size(); // 注意设定长宽均 +1,但是初始化为 0,边界就成了障碍 vector<vector<int>> pathes(m + 1, vector<int> (n + 1, 0)); pathes[0][1] = 1; // 给定一个入口 for (int i = 1; i < m + 1; i++) for (int j = 1; j < n + 1; j++) // 注意此处的偏移 if (obstacleGrid[i-1][j-1] == 1) pathes[i][j] = 0; else pathes[i][j] = pathes[i-1][j] + pathes[i][j-1]; return pathes[m][n]; }
64 给定一个m*n矩阵,每个数字代表经过该处的耗费,找出一条耗费最小的路径
依然是动态规划
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
intminPathSum(vector<vector<int>>& grid){ // if modifying the grid is disallowed, copy it int m = grid.size(), n = grid[0].size(); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (i == 0 && j == 0) continue; elseif (i == 0 && j != 0) grid[i][j] += grid[i][j-1]; elseif (i != 0 && j == 0) grid[i][j] += grid[i-1][j]; else grid[i][j] += min(grid[i-1][j], grid[i][j-1]); return grid[m-1][n-1]; }
defisNumber(self, s): BEFORE = 0# before dot AFTER = 1# after dot EXP = 2# after e phase = BEFORE allow_sign = True
s = s.strip()
ifnotany([c.isdigit() for c in s]): returnFalse
if s == ''or s[0] == 'e'or s[-1] == 'e'or s == '.': returnFalse if s[0] == '.'and s[1] == 'e': returnFalse if s[0] == '-'and s[1] == 'e': returnFalse
for c in s: if'0' <= c <= '9': allow_sign = False elif c == '.': allow_sign = False if phase == EXP or phase == AFTER: returnFalse else: phase = AFTER elif c == 'e': if phase == EXP: returnFalse allow_sign = True phase = EXP
elif c == '-'or c == '+': ifnot allow_sign: returnFalse allow_sign = False else: returnFalse
vector<int> plusOne(vector<int>& digits){ int n = digits.size(); for (int i = n - 1; i >= 0; i--) { if (digits[i] == 9) { digits[i] = 0; } else { digits[i]++; return digits; } // trick here, we know that the number is 999...999 digits[0] = 1; digits.push_back(0); return digits; }
#define tonum(c) (c - '0') #define tochar(i) (i + '0')
char* addBinary(char* a, char* b) { int m = strlen(a), n = strlen(b); int len = (m > n ? m : n) + 1; // strlen(c) char* c = malloc(sizeof(char) * len + 1); // with ending null memset(c, '0', len+1); c[len] = 0; int carry = 0; for (int i = 1; i <= len; i++) { c[len-i] = tochar((i <= m ? tonum(a[m-i]) : 0) ^ (i <= n ? tonum(b[n-i]) : 0) ^ carry); carry = ((i <= m ? tonum(a[m-i]) : 0) + (i <= n ? tonum(b[n-i]) : 0) + carry) >> 1; } return c[0] == '0' ? c+1 : c; }
68 文字对齐
待研究
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
vector<string> fullJustify(vector<string>& words, int L){ vector<string> res; for(int i = 0, k, l; i < words.size(); i += k) { for(k = l = 0; i + k < words.size() and l + words[i+k].size() <= L - k; k++) { l += words[i+k].size(); } string tmp = words[i]; for(int j = 0; j < k - 1; j++) { if(i + k >= words.size()) tmp += " "; else tmp += string((L - l) / (k - 1) + (j < (L - l) % (k - 1)), ' '); tmp += words[i+j+1]; } tmp += string(L - tmp.size(), ' '); res.push_back(tmp); } return res; }
69 给定整数 x,求 sqrt(x)
比较坑的是 LeetCode 要求的是 y*y < x 的最大整数
C 解答
1 2 3 4 5 6 7 8 9 10 11 12
intmySqrt(int x) { if (x <= 1) return x; constdouble EPS = x * 0.0001; double y = x / 2; // initial guess while (fabs(y * y - x) > EPS) { y = (y + x / y) / 2; }
long z = (long) y; while (z * z > x) z--; return z; }
70 爬梯子,一次可以爬一步或者两步,有几种方法爬完梯子
斐波那契数列,也可以理解为动态规划
C 解答
1 2 3 4 5 6
intclimbStairs(int n) { int a = 1, b = 1, t; for (int i = 1; i < n; i++) t = b, b += a, a = t; return b; }
71 简化 Unix 路径,需要处理., .. 和多个斜杠等情况
没有什么需要注意的,主要是使用 stringstream 用作 string.split
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
string simplifyPath(string& path){ vector<string> dirs; stringstream ss(path); string dir; while (getline(ss, dir, '/')) { if (dir == "." || dir == "") continue; elseif (dir == "..") { if (!dirs.empty()) dirs.pop_back(); } else dirs.push_back(dir); } string result; for (auto& dir : dirs) if (!dir.empty()) result += "/" + dir; return result.size() ? result : "/"; }
72 编辑距离,允许替换,删除,插入三种操作
对于两个字符串比较,往往要使用二维的动态规划。 使用 f[i][j] 表示 word1[1..i] 和 word2[1..j] 之间的距离。 see here
那么:
相等 f[i][j] = f[i-1][j-1];
不相等
替换:f[i][j] = f[i-1][j-1] + 1; 都向前一步
添加:f[i][j] = f[i][j-1] + 1; word2 向前一步
删除:f[i][j] = f[i-1][j] + 1; word1 向前一步
另外使用一维数组表示二维数组还需要了解
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
// unoptimized code intminDistance(string word1, string word2){ int m = word1.length(), n = word2.length(); vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0)); for (int i = 1; i <= m; i++) dp[i][0] = i; for (int j = 1; j <= n; j++) dp[0][j] = j; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1)); } } return dp[m][n]; }
// recursive code from beauty of programming // TLE on LeetCode intminDistance(string word1, string word2){ returnminDistance(&word1.front(), &word1.back(), &word2.front(), &word2.back()) }
if (*start1 == *start2) returnminDistance(start1 + 1, end1, start2 + 1, end2); else { int t1 = minDistance(start1 + 1, end1, start2 + 1, end2); int t2 = minDistance(start1 + 1, end1, start2, end2); int t3 = minDistance(start1, end1, start2 + 1, end2); returnmin(t1, min(t2, t3)) + 1; } }
73 给定一个矩阵,如果某个元素为零,把所在的行和所在的列都设为零
一种可以接受的方法是使用 O(m+n) 的空间,记录哪行哪列需要设为零
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
voidsetZeroes(vector<vector<int>>& matrix){ int m = matrix.size(); if (m == 0) return; int n = matrix[0].size(); if (n == 0) return;
vector<bool> row(m), column(n);
for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (matrix[i][j] == 0) row[i] = true, column[j] = true;
for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (row[i] || column[j]) matrix[i][j] = 0; }
74 搜索矩阵,矩阵每行从左到右依次增大,每行都比上一行大
当做数组直接二分搜索就可以了
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13
boolsearchMatrix(int** matrix, int row, int col, int target){ int left = 0, right = row * col - 1; while (left <= right) { int mid = left + (right - left) / 2; if (matrix[mid/col][mid%col] < target) left = mid + 1; elseif (matrix[mid/col][mid%col] == target) returntrue; else right = mid - 1; } returnfalse; }
75 颜色排序,每个物体有颜色属性,把他们按照 RGB 的顺序排序 (🇳🇱国旗问题)
一种方法是简单地 2 pass 解法,遍历一遍计数再输出。另一种方法是把红色往前交换,蓝色往后交换
C 解答
1 2 3 4 5 6 7 8 9 10 11 12
voidswap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
voidsortColors(int* nums, int numsSize) { constint RED = 0, GREEN = 1, BLUE = 2; int reds = 0, blues = numsSize - 1; for (int i = 0; i <= blues; i++) { while (nums[i] == BLUE && i < blues) swap(&nums[i], &nums[blues--]); while (nums[i] == RED && i > reds) swap(&nums[i], &nums[reds++]); } }
// 组合是不要求顺序的 vector<vector<int>> combine(int n, int k) { vector<vector<int>> result; if (n < k) return result; vector<int> temp(0, k); combine(result, temp, 0, 0, n, k); return result; }
voidcombine(vector<vector<int>>& result, vector<int>& temp, int start, int count, int n, int k){ // 1. 回溯条件,找到了一个解 if (count == k) { result.push_back(temp); return; } // 2. 深度优先搜索 for (int i = start; i < n; i++) { temp.push_back(i + 1); // 只搜索比 i 大的即可 combine(result, temp, i+ 1, count+1, n, k); temp.pop_back(); } }
78 给定一个集合,找到它的所有子集
这道题至少有 3 种解法:
DFS,我们知道对于 n 个元素的集合,有 2^n 个子集,通过每个元素在不在子集中构造一个状态空间树
// for each solution, the can be divided into two sub solutions: in or out voidsubsets(vector<int>& nums, vector<vector<int>>& result, vector<int> temp, int i){ if (i == nums.size()) { result.push_back(temp); return; }
vector<int> t = temp; subsets(nums, result, temp, i + 1); temp.push_back(nums[i]); subsets(nums, result, temp, i + 1); }
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
// iterative vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> result; result.push_back({}); if (nums.empty()) return result; result.push_back(vector<int>(1, nums[0])); for (int i = 1; i < nums.size(); i++) { int size = result.size(); // notice the cached size for (int j = 0; j < size; j++) { auto new_subset = result[j]; new_subset.push_back(nums[i]); sort(new_subset.begin(), new_subset.end()); result.push_back(new_subset); } } return result; }
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// tricky vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> result; int size = (1 << nums.size()); for (int i = 0; i < size; i++) { vector<int> subset; int k = i; for (int j = 0; j < nums.size(); j++) { if (k & 0x1) subset.push_back(nums[j]); k >>= 1; } sort(subset.begin(), subset.end()); result.push_back(subset); } return result; }
boolexist(vector<vector<char>>& board, string word){ int row = board.size(); int col = board[0].size(); vector<vector<bool>> visited(row, vector<bool> (col, false));
bool found = false; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (board[i][j] == word[0]) { if (findNext(board, word, visited, i, j, 0)) found = true; } } } return found; }
boolfindNext(vector<vector<char>>& board, string& word, vector<vector<bool>>& visited, int m, int n, int i){
if (i == word.size()) returntrue; if (m >= board.size() || n >= board[0].size() || m < 0 || n < 0|| visited[m][n] || board[m][n] != word[i]) returnfalse; char temp = board[m][n]; board[m][n] = -1;
bool exist = findNext(board, word, visited, m + 1, n, i+1) || findNext(board, word, visited, m - 1, n, i+1) || findNext(board, word, visited, m, n+1, i+1) || findNext(board, word, visited, m, n-1, i+1); board[m][n] = temp; return exist; }
80 从排序数组中删除重复元素,但是允许一个元素重复出现两次
巧妙地解法,和i-2的元素对比
C 解答
1 2 3 4 5 6 7 8 9
intremoveDuplicates(int* nums, int numsSize) { if (!nums || numsSize < 1) return0; int len = 0, counter = 0; for (int i = 0; i < numsSize; i++) { if (len < 2 || nums[i] != nums[len-2]) nums[len++] = nums[i]; } return len; }
boolsearch(int A[], int n, int key) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left)/2; if (A[mid] == key) returntrue; //return m in Search in Rotated Array I if (A[left] < A[mid]) { //left half is sorted if (A[left] <= key && key < A[mid]) right = mid - 1; else left = mid + 1; } elseif (A[left] > A[mid]) { //right half is sorted if (A[mid] < key && key <= A[right]) left = mid + 1; else right = mid - 1; } else { // A[left] == A[mid] left++; } } returnfalse; }
voidmerge(int* nums1, int m, int* nums2, int n) { int len = m + n - 1; m--, n--; while (m >= 0 && n >= 0) { if (nums1[m] > nums2[n]) { nums1[len--] = nums1[m--]; } else { nums1[len--] = nums2[n--]; } } while (n >= 0) { nums1[n] = nums2[n]; n--; }
}
89 生成格雷码 (Gray Code)
记住格雷码的生成规则
C++ 解答
1 2 3 4 5 6 7
vector<int> grayCode(int n){ vector<int> v; for (int i = 0; i < (1 << n); i++) { v.push_back((i >> 1) ^ i); } return v; }
while (*s) { if (*s == '0') r1 = 0; // 0 不能单独构成字母 if (*p == '1' || *p == '2' && *s < '7') { // 形成两种可能 int t = r1; r1 = r2 + r1; r2 = t; } else { r2 = r1; // 新加入的数字只能单独构成字母 }
p = s++; } return r1; }
92 在给定区间上翻转数组
同样是数组操作细节题
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) { if (m == n) return head; structListNodedummy, *p = &dummy, * small_node, * big_node; // actually the prev ones dummy.next = head; n -= m;
while (--m) // m starts from 1, so not m-- p = p->next; structListNode* start = p->next; while (n--) { structListNode* next = start->next; start->next = next->next; next->next = p->next; p->next = next; }
vector<TreeNode*> gen(int start, int end){ vector<TreeNode*> result; if (start > end) { result.push_back(NULL); return result; }
for (int i = start; i <= end; i++) { auto leftTrees = gen(start, i - 1); auto rightTrees = gen(i + 1, end); for (auto& l : leftTrees) { for (auto& r : rightTrees) { auto root = newTreeNode(i); root->left = l; root->right = r; result.push_back(root); } } } return result; }
96 给定数字 n,从 1 到 n 作为节点有多少种方式生成二叉树
这道题看似是树,实际上是一个动态规划问题。
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14
intnumTrees(int n) { if (n == 0) return0;
int* dp = malloc(sizeof(int) * (n+1)); dp[0] = 1;
for (int i = 1; i <= n; i++) { int num = 0; for (int j = 0; j <= i; j++) // 依次选取第 k 个点作为根 num += dp[j - 1] * dp[i - j]; dp[i] = num; } return dp[n]; }
vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> result; if (!root) return result; vector<TreeNode*> current, next; current.push_back(root); bool odd = true; while (!current.empty()) { next.resize(0); vector<int> vals; for (int i = 0; i < current.size(); i++) { if (current[i]->left) next.push_back(current[i]->left); if (current[i]->right) next.push_back(current[i]->right); vals.push_back(current[i]->val); } if (!odd) reverse(vals.begin(), vals.end()); odd = !odd; result.push_back(vals); current = next; } return result; }
104 树的最大深度
C 解答
1 2 3 4 5
intmaxDepth(struct TreeNode* root) { if (!root) return0; int left = maxDepth(root->left), right = maxDepth(root->right); return (left > right ?left : right) + 1; }
structListNode* list; intlen(struct ListNode* head) { int l = 0; while (head) head = head->next, l++; return l; }
struct TreeNode* bst(int n) { if (n == 0) returnNULL; structTreeNode* root =malloc(sizeof(struct TreeNode)); root->left = bst(n/2); root->val = list->val; list = list->next; root->right = bst(n - n / 2 - 1); return root; } struct TreeNode* sortedListToBST(struct ListNode* head) { if (!head) return0; list = head; return bst(len(head)); }
110 平衡二叉树
C 解答
1 2 3 4 5 6 7 8 9 10 11
intheight(struct TreeNode* root) { if (!root) return0; int left = height(root->left); int right = height(root->right); if (left > right + 1 || right > left + 1 || left == -1 || right == -1) return-1; return (left > right ? left : right) + 1; } boolisBalanced(struct TreeNode* root) { return height(root) != -1; }
111 二叉树最小高度
C 解答
1 2 3 4 5 6 7 8 9
intminDepth(struct TreeNode* root) { if (!root) return0; int left = minDepth(root->left); int right = minDepth(root->right); if (!right) return left + 1; if (!left) return right + 1; // tricky here, 当有空节点时,不能返回 0,而是返回另一个值
return (left < right ? left : right) + 1; }
112 二叉树中是否存在和为某个数的路径
C 解答
1 2 3 4 5 6
boolhasPathSum(struct TreeNode* root, int sum) { if (!root) returnfalse; if (!root->left && !root->right) return sum == root->val; return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); }
/** * Solution (DP): * 我们扫描字符串 s * Path[i][j] 代表 T.substr(1...i) 在 S(1...j) 不同的子序列的数量 * * Path[i][j] = Path[i][j-1] (discard S[j]) * + Path[i-1][j-1] (S[j] == T[i] and we are going to use S[j]) * or 0 (S[j] != T[i] so we could not use S[j]) * while Path[0][j] = 1 and Path[i][0] = 0. */
classSolution { public: intnumDistinct(string s, string t){ int m = t.size(); int n = s.size();
if (m > n) return0; vector<vector<int>> path(m+1, vector<int>(n+1, 0));
for (int i = 0; i <= n; i++) path[0][i] = 1;
for (int j = 1; j <= n; j++) // S for (int i = 1; i <= m; i++) // T path[i][j] = path[i][j-1] + (t[i-1] == s[j-1] ? path[i-1][j-1] : 0);
return path[m][n]; } };
116 完全二叉树中把每个节点指向他这一层的右面的节点
显然左节点的下一个节点是父节点的右节点,右节点的下一个节点是父节点下一个节点的左节点。
C 解答
1 2 3 4 5 6 7 8 9 10
voidconnect(struct TreeLinkNode *root) { if (!root) return; if (root->left) root->left->next = root->right; if (root->right) root->right->next = root->next ? root->next->left : NULL; connect(root->left); connect(root->right); }
// 1 intmaxProfit(int* prices, int pricesSize) int total = 0; for (int i=0; i< pricesSize-1; i++) if (prices[i+1]>prices[i]) total += prices[i+1]-prices[i];
// 2 intmaxProfit(int* prices, int pricesSize) { if (!prices) return0; int profit = 0;bool buy = true; int min = prices[0], max = prices[0]; for (int i = 0; i < pricesSize; i++) { if (prices[i] < min && buy) { min = prices[i]; max = prices[i]; } if (prices[i] > min && buy) buy = false; if (prices[i] > max && !buy) max = prices[i]; if ((prices[i] < max || i == pricesSize - 1) && !buy){ profit += max - min; min = prices[i]; max = prices[i]; buy = true; }
boolisPalindrome(char* s) { int len = strlen(s); if (len == 0) returntrue; int left = 0, right = len - 1; while (left < right) { char l = s[left], r = s[right]; if (isalnum(l) && isalnum(r)) { if (tolower(l) != tolower(r)) returnfalse; left++, right--; } else { if (!isalnum(l)) left++; if (!isalnum(r)) right--; } } returntrue; }
int dist = 2; while (!beginSet.empty() && !endSet.empty()) { if (beginSet.size() < endSet.size()) { set1 = &beginSet; set2 = &endSet; } else { set1 = &endSet; set2 = &beginSet; }
unordered_set<string> temp; for (auto word : *set1) { // notice word in not ref wordList.erase(word); for (auto& letter : word) { for (int i = 0; i < 26; i++) { char oldLetter = letter; letter = 'a' + i; if (set2->find(word) != set2->end()) return dist; if (wordList.find(word) != wordList.end()) { temp.insert(word); wordList.erase(word); } letter = oldLetter; } } } dist++; swap(*set1, temp);
} return0; }
128 最长递增子序列
使用动态规划
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
intlongestConsecutive(vector<int>& nums){ int result = 0; unordered_map<int, int> hash; // 每个元素和它们所在序列的长度
for (auto n : nums) { if (hash.find(n) == hash.end()) { // 查找两边的元素,如果找到,把新元素合并进去 int left = hash.find(n-1) != hash.end() ? hash[n-1] : 0; int right = hash.find(n+1) != hash.end() ? hash[n+1] : 0; int sum = left + right + 1; hash[n] = hash[n-left] = hash[n+right] = sum; // 注意此处的更新,并不需要更新区间内的每个值,只需要更新边界即可 result = max(result, sum); } }
return result; }
129 二叉树中只有 0-9 找出所有根节点到子节点的和
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
intsum(struct TreeNode* root, int x) { if (!root->left && !root->right) return x * 10 + root->val; int val = 0; if (root->left) val += sum(root->left, x * 10 + root->val); if (root->right) val += sum(root->right, x * 10 + root->val); return val; }
classSolution { public: voidsolve(vector<vector<char>>& board){ int n = board.size(); if (n == 0) return; int m = board[0].size(); UnionFind uf(n*m+1);
for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if ((i == 0 || j == 0 || i == n-1 || j == m-1) && board[i][j] == 'O') uf.unionify(i * m + j, n * m); elseif (board[i][j] == 'O') { if (board[i-1][j] == 'O') uf.unionify(i * m + j, (i - 1) * m + j); if (board[i+1][j] == 'O') uf.unionify(i*m+j, (i+1)*m+j); if (board[i][j-1] == 'O') uf.unionify(i*m+j, i*m+j-1); if (board[i][j+1] == 'O') uf.unionify(i*m+j, i*m+j+1); } } }
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (uf.find(i*m+j) != uf.find(n*m)) board[i][j] = 'X'; } };
voiddfs(vector<vector<string>>& result, const string& s, vector<string>& group, int start){ if (start == s.size()) { result.push_back(group); return; }
for (int i = start; i < s.size(); i++) { if (isPalindrome(s, start, i)) { group.push_back(s.substr(start, i - start + 1)); dfs(result, s, group, i + 1); group.pop_back(); } } }
boolisPalindrome(const string& s, int left, int right){ while (left < right) { if (s[left++] != s[right--]) returnfalse; } returntrue; }
132 如上题,找出最少需要分组几次
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14
intminCut(string s){ vector<int> cut(s.size() + 1, 0); for (int i = 0; i < s.size() + 1; i++) cut[i] = i - 1;
for (int i = 0; i < s.size(); i++) { for (int j = 0; i - j >= 0 && i + j < s.size() && s[i+j] == s[i-j]; j++) cut[i+j+1] = min(cut[i+j+1], cut[i-j] + 1); // i-j -> i+j 是 palindrome,所以只需要 cut[i-j] 在加上这一段就好了 for (int j = 1; i - j + 1 >= 0 && i + j < s.size() && s[i+j] == s[i-j+1]; j++) cut[i+j+1] = min(cut[i+j+1], cut[i - j + 1] + 1); }
return cut[s.size()]; }
133 复制有向图
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> hash; // old -> new pair UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node){ if (!node) returnNULL; if (hash.find(node) == hash.end()) { hash[node] = newUndirectedGraphNode(node->label); for (auto n : node->neighbors) hash[node]->neighbors.push_back(cloneGraph(n)); }
return hash[node]; }
134 加油站
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
intcanCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) { int total = 0; int j = -1;
for (int i = 0, sum = 0; i < gasSize; ++i) { sum += gas[i] - cost[i]; // 从此处经过能够净增多少汽油 total += gas[i] - cost[i]; // 记录总的汽油量是否是正的 if (sum < 0) { // 如果当前汽油量已经小于 0,说明之前的节点都是不行的,到下一个节点 j = i; sum = 0; // 同时重新开始计数 } }
boolwordBreak(string s, unordered_set<string>& wordDict){ if (wordDict.empty()) returnfalse; vector<bool> dp(s.size() + 1, false); dp[0] = true; // 动态规划,假设前 i 个字符已经匹配到了,尝试匹配 i 到 i+j,如果找到了,就匹配到了 i+j for (int i = 1; i <= s.size(); i++) { for (int j = i-1; j >= 0; j--) { if (dp[j]) { string word = s.substr(j, i-j); if (wordDict.find(word) != wordDict.end()) { dp[i] = true; break; } } } } return dp[s.size()]; }
141 列表是否有环
slow 每次走一步,而 fast 每次走两步,因此在进入环之后,两者一定会相遇
C 解答
1 2 3 4 5 6 7 8 9 10
boolhasCycle(struct ListNode *head) { structListNode* slow = head, * fast = head; while (fast && fast->next && fast->next->next) { fast = fast->next->next; slow = slow->next; if (slow == fast) returntrue; } returnfalse; }
142 列表是否有环?如果有找到环的开始
从两者出发,到两者相遇,slow 指针走了 p 步,而 fast 指针走了 2p 步,显然 fast 多走了一圈(或者多圈)。 设 p = k + x, 2p = k + x + loop -> 2k + 2x = k + x + loop -> k + x = loop -> k = loop - x,剩下的长度正好也是 k。 假设入口处距离起点的距离是 k,那么发生碰撞的点距离环的入口处距离也是 k,所以两个指针分别从开始和碰撞点出发匀速一定会在环的入口相遇。
vector<int> preorderTraversal(TreeNode* root){ vector<int> result; if (!root) return result;
stack<TreeNode*> stk; stk.push(root);
while (!stk.empty()) { TreeNode* node = stk.top(); stk.pop(); result.push_back(node->val); if (node->right) stk.push(node->right); if (node->left) stk.push(node->left);
intfindMin(int* A, int n) { int left = 0; int right = n - 1; while (left < right - 1) { int mid = left + (right - left) / 2; if (A[left] > A[mid]) right = mid; elseif (A[right] < A[mid]) left = mid; else right = mid; } return A[left] < A[right] ? A[left] : A[right]; }
154 在旋转数组中查找最小值,可能有重复
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14
intfindMin(int* A, int n) { int left = 0, right = n - 1; while (left < right) { int mid = left + (right - left) / 2; if (A[mid] > A[right]) { // 当需要找的是 left,也就是较小的数字,使用 right 比较不需要等于号 left = mid + 1; } elseif (A[right] < A[mid]) { right = mid; } else { right--; } } return A[left]; }
intfindPeakElement(int* nums, int numsSize) { int left = 0, right = numsSize - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < nums[mid + 1]) // mid in left part of summit left = mid + 1; else// mid in right part of summit right= mid; } return left; }
vector<int> ver(const string& version){ vector<int> result; int num = 0; for (auto c : version) { if (c != '.') { num = num * 10 + c - '0'; } else { result.push_back(num); num = 0; } } // 对于所有这种分割符中读取数字的都需要注意最后一个 result.push_back(num); // notice here return result; }
intcompareVersion(string version1, string version2){ auto v1 = ver(version1); auto v2 = ver(version2);
for (int i = 0; i < v1.size() || i < v2.size(); i++) { int a = i < v1.size() ? v1[i] : 0; int b = i < v2.size() ? v2[i] : 0; if (a != b) return a > b ? 1 : -1; }
/** * Your BSTIterator will be called like this: * BSTIterator i = BSTIterator(root); * while (i.hasNext()) cout << i.next(); */
174 地下城游戏
王子在格子的左上角,需要到右下角去救公主,在过程中王子不能死掉,和机器人走路一样,使用动态规划
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14
intcalculateMinimumHP(vector<vector<int>>& dungeon){ int row = dungeon.size(); int col = dungeon[0].size(); vector<vector<int>> bloods(row + 1, vector<int> (col + 1, INT_MAX)); bloods[row][col-1] = bloods[row-1][col] = 1; // 公主的两边 // 从公主那里逆向推 for (int i = row-1; i >= 0; i--) { for (int j = col-1; j >= 0; j--) { int need = min(bloods[i+1][j], bloods[i][j+1]) - dungeon[i][j]; // 缺乏的血量 = 到达下一步最少的血量 - 这一步消耗的血量 bloods[i][j] = need > 0 ? need : 1; // 王子的血量至少为 1 } } return bloods[0][0]; }
175-178 Missing
179 最大的数字
神奇的排序方法
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
string largestNumber(vector<int>& nums){ vector<string> num_strings(nums.size()); for (int i = 0; i < nums.size(); i++) num_strings[i] = to_string(nums[i]); auto comparator = [] (string& s1, string& s2) { return s1 + s2 > s2 + s1; }; sort(num_strings.begin(), num_strings.end(), comparator); string result; for (auto& num_string: num_strings) result += num_string; int start = result.find_first_not_of("0"); if (start == string::npos) return"0"; return result.substr(start); }
180-185 Missing
186 Locked
187 找到所有 10 个字母唱的重复 DNA 序列
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12
// naive 的做法从前往后,记录字符串 // 观察 ATCG 四个字符的特征,并把他们编码为一个 int // 十个字符正好编码在 32bit 的 int 中 vector<string> findRepeatedDnaSequences(string s){ unordered_map<int, int> hash; vector<string> result; for (int t = 0, i = 0; i < s.size(); i++) // 左移弹出老元素,求交为了只使用 30bit,求或添加新元素。 if (hash[t = t << 3 & 0x3FFFFFFF | s[i] & 0b111]++ == 1) // 等于 1 为了避免重复 result.push_back(s.substr(i - 9, 10)); return result; }
189 翻转树组
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
voidreverse(int* nums, int left, int right) { while (left < right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; }
}
voidrotate(int* nums, int numsSize, int k) { if (k >= numsSize) k %= numsSize; if (k <= 0) return; reverse(nums, 0, numsSize - k - 1); reverse(nums, numsSize - k, numsSize - 1); reverse(nums, 0, numsSize - 1); }
190 翻转二进制表示
C 解答
1 2 3 4 5 6 7 8 9 10 11 12
uint32_treverseBits(uint32_t n) { uint32_t r = 0; int len = sizeof(n) * 8 - 1; while (len--) { // 31 times shift r |= n & 0x1; n >>= 1; r <<= 1; // only shift 31 times }
r |= n & 0x1; return r; }
191 数字二进制表示中 1 的个数
我们知道 n&(n-1) 会把 n 中的最后一个 1 去掉,所以循环直到 n 为 0 即可
C 解答
1 2 3 4 5 6 7 8
inthammingWeight(uint32_t n) { int count = 0; while (n) { n &= n - 1; count++; } return count; }
introb(int* nums, int numsSize) { if (!nums) return0; // 因为不能相邻,所以可以从相隔一个的取值 // dp[n] = max(dp[n-1], dp[n-2] + A[n]) int temp, m = 0, n = nums[0]; for (int i = 1; i < numsSize; i++) { temp = n; if (m + nums[i] > n) n = m + nums[i]; m = temp; } return n; }
// level order 遍历 vector<int> rightSideView(TreeNode* root){ vector<int> result; if (!root) return result; queue<TreeNode*> q; q.push(root);
while (!q.empty()) { TreeNode* node; int len = q.size(); // 保存为了获得最后一个元素 for (int i = 0; i < len; i++) { // 当前数组的最后一个元素就是最右边的元素 node = q.front(); q.pop(); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } result.push_back(node->val); } return result; }
classSolution { conststaticchar LAND = '1'; conststaticchar WATER = '0';
public: intnumIslands(vector<vector<char>>& grid){ if (grid.empty() || grid[0].empty()) return0; int r = grid.size(), c = grid[0].size(); UnionFind uf(r * c + 1); // extra element is for water for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (grid[i][j] == LAND) { if (i != r - 1 && grid[i+1][j] == LAND) uf.unionify(i*c+j, (i+1)*c+j); if (j != c - 1 && grid[i][j+1] == LAND) uf .unionify(i*c+j, i*c+j+1); } else { uf.unionify(i*c+j, c*r); } } } return uf.getCount() - 1; // islands + water - 1; } };
uf = UnionFind(m * n + 1) for i inrange(m): for j inrange(n): if grid[i][j] == "1": up = max(i - 1, 0) if grid[up][j] == "1": uf.union(i * n + j, up * n + j) left = max(j - 1, 0) if grid[i][j - 1] == "1": uf.union(i * n + j, i * n + left) else: uf.union(i * n + j, m * n) return uf.count - 1
201 给定区间内,所有数字 AND 的结果
显然直接过一遍是会超时的,那么分析可知
C 解答
1 2 3 4 5 6 7 8 9 10
// 如果两个数不相等,一定是有不同的位,那么这一位一定为 0 intrangeBitwiseAnd(int m, int n) { int t = 0; while (m != n) { t++; m >>= 1; n >>= 1; } return m << t; }
202 快乐数字,各位数字平方相加得到下一个数字,如果最后等于 1
没啥,一直算就可以了。
C++ 解答
1 2 3 4 5 6 7 8 9 10 11
boolisHappy(int n){ while (n > 6) { int next = 0; while (n) { next += (n%10) * (n%10); n /= 10; } n = next; } return n == 1; }
203 删除链表中给定的值
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
struct ListNode* removeElements(struct ListNode* head, int val) { structListNodedummy, *p = &dummy; dummy.next = head; while (p) { if (p->next && p->next->val == val) { // not forward here structListNode* next = p->next; p->next = next->next; free(next); } else { p = p->next; }
boolcanFinish(int numCourses, vector<pair<int, int>>& prerequisites){ // next -> before vector<unordered_set<int>> graph(numCourses); // 每条边和他的下一步,临接表 for (auto& p : prerequisites) graph[p.second].insert(p.first);
vector<int> d(numCourses, 0); // in degree
for (auto& nexts : graph) for (auto next : nexts) d[next]++;
for (int i = 0; i < numCourses; i++) { int nondep; // in degree == 0 for (nondep = 0; nondep < numCourses && d[nondep] != 0; nondep++) ; if (nondep == numCourses) returnfalse; d[nondep] = -1; // remove for (auto next : graph[nondep]) // 所有下一步都 -1 d[next]--; }
// Inserts a word into the trie. voidinsert(string word){ TrieNode* location = root; for (auto& c : word) { if (!location->next[c - 'a']) location->next[c - 'a'] = new TrieNode; location = location->next[c - 'a']; } location->isWord = true; }
// Returns if the word is in the trie. boolsearch(string word){ TrieNode* location = root; for (auto& c : word) { location = location->next[c - 'a']; if (!location) returnfalse; } return location->isWord; }
// Returns if there is any word in the trie // that starts with the given prefix. boolstartsWith(string prefix){ TrieNode* location = root; for (auto& c : prefix) { location = location->next[c - 'a']; if (!location) returnfalse; } returntrue; }
private: TrieNode* root; };
// Your Trie object will be instantiated and called as such: // Trie trie; // trie.insert("somestring"); // trie.search("key");
209 最短子数组使得和大于某个数
双指针,超过和之后再尝试从开始处减去元素
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12
intminSubArrayLen(int s, vector<int>& nums){ int start = 0, sum = 0, len = INT_MAX; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; while (sum >= s) { len = min(len, i - start + 1); sum -= nums[start++]; } }
// Inserts a word into the trie. voidinsert(string word){ TrieNode* location = root; for (auto& c : word) { if (!location->next[c - 'a']) location->next[c - 'a'] = new TrieNode; location = location->next[c - 'a']; } location->isWord = true; }
// Returns if the word is in the trie. virtualboolsearch(string word){ TrieNode* location = root; for (auto& c : word) { location = location->next[c - 'a']; if (!location) returnfalse; } return location->isWord; }
// Returns if there is any word in the trie // that starts with the given prefix. boolstartsWith(string prefix){ TrieNode* location = root; for (auto& c : prefix) { location = location->next[c - 'a']; if (!location) returnfalse; } returntrue; }
TrieNode* getRoot(){ return root; }
private: TrieNode* root; };
classWordDictionary : public Trie{
public: WordDictionary() : Trie(){}
// Adds a word into the data structure. voidaddWord(string word){ insert(word); }
// Returns if the word is in the data structure. A word could // contain the dot character '.' to represent any one letter. boolsearch(string word)override{ returnsearch(word.c_str(), getRoot()); }
boolsearch(constchar* word, TrieNode* root){ TrieNode* run = root; for (int i = 0; word[i]; i++) { if (run && word[i] != '.') run = run->next[word[i] - 'a']; elseif (run && word[i] == '.') {
// skip checking this char TrieNode* tmp = run; for (int j = 0; j < 26; j++) { run = tmp->next[j]; if (search(word + i + 1, run)) returntrue; } } elsebreak; } return run && run->isWord; } };
// Your WordDictionary object will be instantiated and called as such: // WordDictionary wordDictionary; // wordDictionary.addWord("word"); // wordDictionary.search("pattern");
classSolution { private: Trie m_trie; public: vector<string> findWords(vector<vector<char>>& board, vector<string>& words){ for (auto& word : words) m_trie.insert(word); int row = board.size(); int col = board[0].size();
unordered_set<string> result_set; vector<vector<bool>> visited(row, vector<bool>(col, false)); for (int i = 0; i < row; i++) for(int j = 0; j < col; j++) find(result_set, board, visited, "", i, j); vector<string> result; for (auto& r : result_set) result.push_back(r); return result; }
voidfind(unordered_set<string>& r, vector<vector<char>>& board, vector<vector<bool>>& visited, string word, int i, int j){ if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j]) return; word += board[i][j]; if (!m_trie.startsWith(word)) return; if (m_trie.search(word)) r.insert(word);
visited[i][j] = true; find(r, board, visited, word, i-1, j); find(r, board, visited, word, i+1, j); find(r, board, visited, word, i, j-1); find(r, board, visited, word, i, j+1); visited[i][j] = false;
introbNonCyclic(int* nums, int numsSize) { if (!nums) return0; // 因为不能相邻,所以可以从相隔一个的取值 // dp[n] = max(dp[n-1], dp[n-2] + A[n]) int temp, m = 0, n = nums[0]; for (int i = 1; i < numsSize; i++) { temp = n; if (m + nums[i] > n) n = m + nums[i]; m = temp; } return n; }
intswap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
intpartition(int* nums, int start, int end) { int small = start - 1; int pivot = nums[end]; for (int i = start; i < end; i++) if (nums[i] < pivot) swap(&nums[++small], &nums[i]); swap(&nums[++small], &nums[end]); return small; }
intfindKthLargest(int* nums, int numsSize, int k) { int left = 0, right = numsSize - 1; while (1) { int index = partition(nums, left, right); if (index == numsSize - k) return nums[index]; if (index > numsSize - k) right = index - 1; else left = index + 1; } }
vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> result; dfs(result, {}, n, k); return result; }
voiddfs(vector<vector<int>>& result, vector<int> combination, int n, int k){ if (combination.size() == k) { if (n == 0) result.push_back(combination); return; } int i = combination.empty() ? 1 : combination.back() + 1; // 保证不重复切实递增序列 while (i <= n && i < 10) { combination.push_back(i); dfs(result, combination, n-i, k); combination.pop_back(); i++; } }
217 包含重复数字
这道题太简单了,也没有什么精妙的解法,可以使用排序,Hash 等多种解法
C++ 解答
1 2 3 4 5 6 7 8 9
boolcontainsDuplicate(vector<int>& nums){ unordered_set<int> s; for (auto& n : nums) if (s.find(n) != s.end()) returntrue; else s.insert(n); returnfalse; }
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) { vector<pair<int, int>> res; int cur=0, cur_X, cur_H =-1, len = buildings.size(); priority_queue< pair<int, int>> liveBlg; // first: height, second, end time while(cur<len || !liveBlg.empty()) { // if either some new building is not processed or live building queue is not empty cur_X = liveBlg.empty()? buildings[cur][0]:liveBlg.top().second; // next timing point to process
if(cur>=len || buildings[cur][0] > cur_X) { //first check if the current tallest building will end before the next timing point // pop up the processed buildings, i.e. those have height no larger than cur_H and end before the top one while(!liveBlg.empty() && ( liveBlg.top().second <= cur_X) ) liveBlg.pop(); } else { // if the next new building starts before the top one ends, process the new building in the vector cur_X = buildings[cur][0]; while(cur<len && buildings[cur][0]== cur_X) // go through all the new buildings that starts at the same point { // just push them in the queue liveBlg.push(make_pair(buildings[cur][2], buildings[cur][1])); cur++; } } cur_H = liveBlg.empty()?0:liveBlg.top().first; // outut the top one if(res.empty() || (res.back().second != cur_H) ) res.push_back(make_pair(cur_X, cur_H)); } return res; }
219 包含重复数字,并且两个的坐标不超过 k
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
// 滑动窗口保存前 k 个值,如果有重复的就返回 // num[i-k] num[i-1],如果滑过了,就删除该元素 boolcontainsNearbyDuplicate(vector<int>& nums, int k){ unordered_set<int> s; if (k <= 0) returnfalse; if (k >= nums.size()) // notice here k = nums.size() - 1;
for (int i = 0; i < nums.size(); i++) { if (i > k) s.erase(nums[i - k - 1]); // delete first note if (s.find(nums[i]) != s.end()) returntrue; s.insert(nums[i]); // insert }
returnfalse; }
220 同上一题,同时保证两个数字之间小于 t
保证两个数字之差小于 t
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
boolcontainsNearbyAlmostDuplicate(vector<int>& nums, int k, int t){ set<int> window; // 注意不能使用 unordered if (k <= 0) returnfalse; if (k >= nums.size()) // notice here k = nums.size() - 1; for (int i = 0; i < nums.size(); i++) { if (i > k) window.erase(nums[i - k - 1]); auto pos = window.lower_bound(nums[i] - t); // notice set.lower_bound if (pos != window.end() && *pos - nums[i] <= t) returntrue; window.insert(nums[i]); } returnfalse; }
intcomputeArea(int left1, int down1, int right1, int up1, int left2, int down2, int right2, int up2) { int left = max(left1, left2); // 靠右的 int right = max(min(right1, right2), left);// 靠左的,但是比左边大
int down = max(down1, down2); int up = max(min(up1, up2), down);
intcalculate(string s){ vector<int> stk; // 使用 vector 便于统计最后的值 char token = '+'; int num = 0; for (int i = 0; i < s.size(); i++) { if (isdigit(s[i])) num = num * 10 + s[i] - '0'; // 这里不是 else if if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == s.size() - 1) { // 注意最后一步还需要把最后的值计算 int a; switch (token) { case'+': stk.push_back(num); break; case'-': stk.push_back(-num); break; case'*': a = stk.back(); stk.pop_back(); stk.push_back(a * num); break; case'/': a = stk.back(); stk.pop_back(); stk.push_back(a / num); break; }; token = s[i]; num = 0; } }
int result = 0; for (auto i : stk) result += i; return result; }
228 聚合区间,给定一排序数组,把相邻的数字用区间表示
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
vector<string> summaryRanges(vector<int>& nums){ int n = nums.size(); vector<string> result; if (n == 0) return result;
for (int i = 0; i < n; ) { int start = i, end = i; while (end + 1 < n && nums[end + 1] == nums[end] + 1) end++; if (end > start) result.push_back(to_string(nums[start]) + "->" + to_string(nums[end])); else result.push_back(to_string(nums[start])); i = end + 1; }
for (auto n : nums) { if (count1 == 0 || n == a) { count1++; a = n; } elseif (count2 == 0 || n == b) { count2++; b = n; } else { count1--; count2--; } }
count1 = count2 = 0; for (int n : nums) { if (n == a) count1++; if (n == b) count2++; }
vector<int> result;
if (count1 > nums.size() / 3) // verify a result.push_back(a); if (count2 > nums.size() / 3 && a != b) // verify b result.push_back(b); return result; }
classQueue { public: // Push element x to the back of queue. voidpush(int x){ in.push(x); }
// Removes the element from in front of queue. voidpop(void){ if (empty()) return; if (out.empty()) transfer(); out.pop(); }
// Get the front element. intpeek(void){ if (empty()) return INT_MIN; if (out.empty()) transfer(); return out.top(); }
// Return whether the queue is empty. boolempty(void){ return in.empty() && out.empty(); } private: voidtransfer(){ while (!in.empty()) { out.push(in.top()); in.pop(); } }; stack<int> in; stack<int> out; };
233 小于 n 的数字中 1 的个数
对于每一位,有三种情况:
当是数字 0 的时候,可能出先 1 的情况完全由高位出现决定,因为这一位不能贡献 1
当是数字 1 的时候,同上,但是这一位和低位一起可以贡献一个 1
当时数字 2-9 的时候,相当于这一位的 1 可以任意出现,因此高位+1
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13
intcountDigitOne(int n) { int ones = 0; for (int m = 1; m <= n; m *= 10) { // m is the factor int a = n/m, b = n%m; // a is left half, b is right half if (a % 10 >= 2) ones += (a / 10 + 1) * m; if (a % 10 == 1) ones += (a / 10) * m + b + 1; if (a % 10 == 0) ones += (a / 10) * m; } return ones; }
二进制呢
C 解答
1 2 3 4 5 6 7 8 9 10
intcountDigitOneBinary(int n) { int ones = 0; for (int m = 1; m <= n; m <<= 1) { int a = n / m, b = n % m; if (a & 0x01) ones += (a >> 1) * m + b + 1; else ones += (a >> 1) * m; } }
defpop(self): x = self.q.popleft() if self.m[0] == x: self.m.popleft() return x
def__len__(self): returnlen(self.q)
deftop(self): return self.m[0]
classSolution: defmaxSlidingWindow(self, nums: List[int], k: int) -> List[int]: q = MonoQueue() for i inrange(k): q.push(nums[i]) ans = [] for i inrange(k, len(nums)): ans.append(q.top()) q.pop() q.push(nums[i]) ans.append(q.top()) return ans
另一种现在我已经看不懂的做法
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// 题目给定 k 一定是有效地 vector<int> maxSlidingWindow(vector<int>& nums, int k){ vector<int> result; if (nums.empty() || k <= 0) return result; deque<int> dq; // 存储的是索引,front 存储最大值,保证递减 for (int i = 0; i < nums.size(); i++) { while (!dq.empty() && dq.front() < i - k + 1) // 弹出滑过的窗口 dq.pop_front(); while (!dq.empty() && nums[dq.back()] < nums[i]) // 弹出小的 dq.pop_back(); dq.push_back(i); if (i >= k - 1) result.push_back(nums[dq.front()]); } return result; }
240 给定一个矩阵,每行从左到右都是增大的,每一列从上到下都是增大的,找出给定数字是否存在
我们考虑右上角的元素
如果这个元素比 taget 大,那么整列都比 target 大,我们可以 c–
如果这个元素比 target 小,那么正行都比 target 小,我们可以 r++
C 解答
1 2 3 4 5 6 7 8 9 10 11
boolsearchMatrix(int** matrix, int row, int col, int target) { int r = 0, c = col - 1; // 右上角 while (r < row && c > -1) // 向左下角 if (matrix[r][c] == target) returntrue; elseif (matrix[r][c] > target) c--; else r++; returnfalse; }
241 添加括号得到不同的结果
对每一个符号,在他的两边添加括号的好的不同结果再计算。
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14
vector<int> diffWaysToCompute(string input){ vector<int> output; for (int i = 0; i < input.size(); i++) { char token = input[i]; if (!isdigit(token)) // not digit for (int a : diffWaysToCompute(input.substr(0, i))) // 左半部分 for (int b : diffWaysToCompute(input.substr(i+1))) // 右半部分 output.push_back(token == '+' ? a + b : token == '-'? a - b: a *b); // 两半部分之和 }
if (output.empty()) output.push_back(stoi(input)); return output; }
inthIndex(int* cites, int n) { int hs[n+1]; // Hindex 不可能大于 N
for (int i = 0; i <= n; i++) hs[i] = 0;
for (int i = 0; i < n; i++) { if (cites[i] > n) hs[n]++; else hs[cites[i]]++; }
for (int i = n, papers = 0; i >= 0; i--) { // 从后往前,如果有符合条件的,那么就是 Hindex papers += hs[i]; if (papers >= i) return i; }
return0; }
275 H-index II,论文已经按照引用数量排序
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13
inthIndex(int* citations, int n) { int left = 0, right = n - 1; while (left <= right) { // 二分查找是小于等于 int mid = left + (right - left) / 2; if (citations[mid] == n - mid) return citations[mid]; elseif (citations[mid] < n - mid) left = mid + 1; else right = mid - 1; } return n - right - 1; }
276-277 Locked
278 第一个坏版本
C 解答
1 2 3 4 5 6 7 8 9 10 11 12
// 实际上是 lower_bound 函数 intfirstBadVersion(int n) { int left = 0, right = n; // 记住 lower_bound 的 right 是 n while (left < right) { // 使用小于号 int mid = left + (right - left) / 2; if (!isBadVersion(mid)) left = mid + 1; else right = mid; } return left; }
279 分解为平方数的和
最多 4 个即可,尝试在三个以内是否可以。
C 解答
1 2 3 4 5 6 7 8 9 10 11
intnumSquares(int n) { int ub = sqrt(n); for (int a=0; a<=ub; ++a) { for (int b=a; b<=ub; ++b) { int c = sqrt(n - a*a - b*b); if (a*a + b*b + c*c == n) return !!a + !!b + !!c; } } return4; }
// Below is the interface for Iterator, which is already defined for you. // **DO NOT** modify the interface for Iterator. classIterator { structData; Data* data; public: Iterator(const vector<int>& nums); Iterator(const Iterator& iter); virtual ~Iterator(); // Returns the next element in the iteration. intnext(); // Returns true if the iteration has more elements. boolhasNext()const; };
classPeekingIterator : public Iterator { public: PeekingIterator(const vector<int>& nums) : Iterator(nums) { // Initialize any member here. // **DO NOT** save a copy of nums and manipulate it directly. // You should only use the Iterator interface methods.
}
// Returns the next element in the iteration without advancing the iterator. intpeek(){ returnIterator(*this).next(); }
// hasNext() and next() should behave the same as in the Iterator interface. // Override them if needed. intnext(){ return Iterator::next(); }
我们把这个数组看做一个变幻方程 f(i) = A[i],把一些数字变幻到另一些,那么存在一个 i != j s.t. f(i) == f(j). 那么这个问题变成了链表求环的问题。对于链表,我们有 n = n->next 遍历列表,对于这个序列,则是 n = f(n)
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
intfindDuplicate(int* nums, int n) { // 从 n-1 开始 int fast = n - 1, slow = n - 1; do { slow = nums[slow] - 1; // 减一是为了转化为坐标 fast = nums[nums[fast] - 1] - 1; } while (slow != fast);
fast = n - 1; do { slow = nums[slow] - 1; fast = nums[fast] - 1; } while (slow != fast);
return slow + 1; // 从坐标到数字 }
288 Locked
289 Conway’s Game of Life
哈哈,机智,使用没有使用的第二个位存储下一代
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
intmax(int a, int b) {return a > b ? a :b;} intmin(int a, int b) {return a < b ? a :b;} voidgameOfLife(int** board, int row, int col) { for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { int count = 0; for (int m=max(i-1, 0); m<min(i+2, row); m++) // 这里的 min,max 使用的太屌了 for (int n=max(j-1, 0); n<min(j+2, col); n++) count += (board[m][n] & 1); if (count == 3 || count - board[i][j] == 3) // 当前为 0,周围为 3;or 当前为 1,周围为 2/3 here board[i][j] |= 2; } } for (int i = 0; i < row; i++) for (int j = 0; j < col; j++) board[i][j] >>= 1; }
290 单词模式,给定一个模式 abba 等,判断单词是否是这个模式的。
C++ 解答
1 2 3 4 5 6 7 8 9 10 11 12 13
boolwordPattern(string pattern, string str){ map<char, int> chars; // 使用两个 map 纪录 map<string, int> words; istringstream in(str); int i = 0, n = pattern.size(); // `i` is word count for (string word; in >> word; i++) { if (i == n || chars[pattern[i]] != words[word]) // 检查是否相等 returnfalse; chars[pattern[i]] = words[word] = i + 1; // distinct non zero }
return i == n; // 检查长度是否相等 }
291 Locked
292 Nim 游戏,每个人可以选择丢掉 1,2,3,最后一个操作者获胜
显然,当我们遇到 4 的时候会输,其他情况都可以赢。
C 解答
1 2 3
boolcanWinNim(int n) { return n % 4 != 0; }
300 最长递增子序列
最经典的动态规划题目
Python 解答
1 2 3 4 5 6 7 8 9 10 11 12
classSolution: deflengthOfLIS(self, nums: List[int]) -> int: ifnot nums: return0 iflen(nums) == 1: return1 dp = [1for _ inrange(len(nums))] for i inrange(len(nums)): for j inrange(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) returnmax(*dp)
344 翻转字符串
C 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
char* reverseString(char* s) { char* start = s; char* e = s; while (*e) ++e; e--; char t; while (s < e) { t = *s; *s = *e; *e = t; s++; e--; } return start; }
/** * @param {number[]} nums * @param {number} k * @return {number[]} */ let topKFrequent = function(nums, k) { let counter = {}; for (let num of nums) { if (num in counter) { counter[num]++; } else { counter[num] = 0; } }
let bucket = []; for (let num in counter) { let rev_freq = nums.length - counter[num] + 1; if (rev_freq in bucket) { bucket[rev_freq].push(num); } else { bucket[rev_freq] = [num]; } }
let rv = []; for (let bc of bucket) { if (! Array.isArray(bc)) continue; for (let num of bc) { if (rv.length == k) return rv; else rv.push(parseInt(num)) } }
classSolution: deflengthLongestPath(self, input: str) -> int: path = [] ans = 0 for name ininput.split("\n"): l = 0 for c in name: if c == "\t": l += 1 else: break iflen(path) > l: for i inrange(len(path) - l): path.pop() path.append(name.strip("\t")) if"."in name: length = sum([len(p) for p in path]) + len(path) - 1 ans = max(ans, length) print(path) return ans
435 无重叠区间
不要被题目迷惑,从反面开始思考,求去除多少个区间其实就是求最多有多少个有效区间
Python 解答
1 2 3 4 5 6 7 8 9 10
classSolution: deferaseOverlapIntervals(self, intervals: List[List[int]]) -> int: intervals.sort(key=lambda x: x[1]) max_intervals = 0 end = float("-inf") for interval in intervals: if interval[0] >= end: max_intervals += 1 end = interval[1] returnlen(intervals) - max_intervals
482 注册码格式化
要求每 K 个字符添加一个 “-“, 如果不够的话,第一个分组可以不全。
Python 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution: deflicenseKeyFormatting(self, S: str, K: int) -> str: key = [] i = 0 for c inreversed(S): if c == "-": continue key.append(c.upper()) i += 1 if i % K == 0: key.append("-") if key and key[-1] == "-": key = key[:-1] return"".join(reversed(key))
547 朋友圈
UnionFind 的定义见第 200 题
Python 解答
1 2 3 4 5 6 7 8 9
classSolution: deffindCircleNum(self, M: List[List[int]]) -> int: n = len(M) uf = UnionFind(n) for i inrange(n): for j inrange(i): if M[i][j] == 1: uf.union(i, j) return uf.count
739
单调栈的简单应用
Python 解答
1 2 3 4 5 6 7 8 9 10 11 12
classSolution: defdailyTemperatures(self, T: List[int]) -> List[int]: stack = [] ans = [0] * len(T) for i inrange(len(T)-1, -1, -1): # 如果当前温度大于当前最低温度 while stack and T[i] >= T[stack[-1]]: stack.pop() if stack: ans[i] = stack[-1] - i stack.append(i) return ans
```Rust use std::collections::HashMap; use std::cmp::max;
impl Solution { pub fn total_fruit(tree: Vec<i32>) -> i32 { let mut i = 0; let mut res = 0; let mut counter = HashMap::new(); for (j, el) in tree.iter().enumerate() { *counter.entry(el).or_insert(0) += 1; while counter.len() > 2 { *counter.get_mut(&tree[i]).unwrap() -= 1; if let Some(x)= counter.get(&tree[i]) { if *x == 0 { counter.remove(&tree[i]); } } i += 1; } res = max(res, j - i + 1); } res as i32 } }
986 区间列表的交集
tags: #interval
Python 解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution: defintervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]: i, j = 0, 0 ans = [] while i < len(A) and j < len(B): lo = max(A[i][0], B[j][0]) hi = min(A[i][1], B[j][1]) if lo <= hi: ans.append((lo, hi)) if A[i][1] < B[j][1]: i += 1 else: j += 1 return ans
classSolution: defpowerfulIntegers(self, x: int, y: int, bound: int) -> List[int]: if bound <= 0: return [] ans = set() limit = int(math.log2(bound)) + 1 for i inrange(limit): for j inrange(limit): v = x ** i + y ** j if v <= bound: ans.add(v) returnlist(ans)
1272 删除区间
python 解答
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution: defremoveInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]: lo, hi = toBeRemoved ans = [] for x, y in intervals: if y < lo or x > hi: ans.append([x, y]) else: if lo > x: ans.append([x, lo]) if hi < y: ans.append([hi, y]) return ans
1317 将整数转换为两个无零整数的和
python 解答
1 2 3 4 5 6 7
classSolution: defgetNoZeroIntegers(self, n: int) -> List[int]: for a inrange(1, n): b = n - a if"0"notinstr(a) and"0"notinstr(b): return [a, b] return []
1389 按既定顺序创建目标数组
Python 解答
1 2 3 4 5 6
classSolution: defcreateTargetArray(self, nums: List[int], index: List[int]) -> List[int]: target = [] for n, i inzip(nums, index): target = target[:i] + [n] + target[i:] return target
defsumFourDivisors(self, nums) -> int: ifnot nums: return0 iflen(nums) == 1: upper = nums[0] else: upper = max(*nums) # 首先在这里筛选素数 isPrim = [Truefor _ inrange(upper)] i = 2 while i * i < upper: if isPrim[i]: j = i * i while j < upper: isPrim[j] = False j += i i += 1 # 把素数都提取出来 prims = [i for i inrange(2, upper) if isPrim[i]] ans = 0 for num in nums: for prim in prims: # 已经不可能了,后续不算了 if prim * prim > num: break # 立方数是符合的,这个比较坑,开始没想到,比如 8 if prim * prim * prim == num: ans += (1 + num + prim + prim * prim) break # 可以分解成两个质数乘积 if num % prim == 0and isPrim[num // prim] and prim * prim != num: ans += (1 + num + prim + num // prim) break return ans