面试要点,算法,数据结构等练习大全

有趣的算法，面试常常碰到，多种语言实现~

1 从数组中找出两个数字使得他们的和是给定的数字

tags: #hash

使用一个散列，存储数字和他对应的索引。然后遍历数组，如果另一半在散列当中，那么返回
这两个数的索引，程序结束；如果不在，把当前数字加入到散列中。

C++ 解答

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 解答

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:seen = {}for i, num in enumerate(nums):if target - num in seen:return [seen[target-num], i]else:seen[num] = ireturn [-1, -1]

rust 解答

use std::collections::HashMap;impl Solution {pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {let mut map = HashMap::with_capacity(nums.len());for (idx, num) in nums.iter().enumerate() {match map.get(&(target - num)) {None => {map.insert(num, idx);},Some(sub_idx) => {return vec![*sub_idx as i32, idx as i32]; }}}vec! []}
}

go 解答

func twoSum(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++ 解答

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)return make_pair(left, right);else if (s < sum)left++;elseright--;}
}

2 给两个列表，数字在其中按低位到高位存储，求他们的和

直接迭代遍历数组，考察细节操作。注意 dummy head 的使用。

C 解答

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {struct ListNode dummy, *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;l1 = l1 ? l1->next: NULL;l2 = l2 ? l2->next: NULL;}return dummy.next;
}

C++ 解答

class Solution {public:ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {if (l1 == NULL) return l2;if (l2 == NULL) return l1;int shift = 0;ListNode* result = new ListNode(0);ListNode* p = result;while (l1 != NULL || l2 != NULL) {ListNode* newNode = new ListNode(0);int v1 = l1 != NULL ? l1->val : 0;int v2 = l2 != NULL ? l2->val : 0;newNode->val = v1 + v2 + shift;if (newNode->val > 9) {newNode->val -= 10;shift = 1;} else {shift = 0;}if (l1) {l1 = l1->next;}if (l2) {l2 = l2->next;}p->next = newNode;p = p->next;}// 注意最后多余的一个进位处理if (shift == 1) {p->next = new ListNode(1);}return result->next;}
};

rust 解答

impl Solution {pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {let (mut l1, mut l2) = (l1, l2);let mut dummy = Box<ListNode::new(0)>;let mut carry = 0;let mut p = dummy;while l1.is_some() || l2.is_some() || carry != 0 {match l1, l2{Some(a), Some(b) => {let mut v = a + b + carry;l1 = l1.next();l2 = l2.next();},Some(a), None => {let mut v = a + carry;l1 = l1.next();},None, Some(b) => {let mut v = b + carry;l2 = l2.next();},None, None => {}}p.next = Some(Box<ListNode::new(v)>);p = p.next;p.val = v % 10;carry = v / 10;}dummy.next}
}

Python 解答

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:dummy = ListNode(-1)p = dummycarry = 0while l1 or l2 or carry:if l1:v1 = l1.vall1 = l1.nextelse:v1 = 0if l2:v2 = l2.vall2 = l2.nextelse:v2 = 0v = v1 + v2 + carry  # 别忘了这里if v >= 10:carry = 1v -= 10else:carry = 0p.next = ListNode(v)p = p.nextreturn dummy.next

3 最长不重复子串

tags: #slidewindow

滑动窗口解决

注意，当字符有限的时候，比如限定为 ASCII 字符，可以使用一个数组代替 Hash。

C 解答

int lengthOfLongestSubstring(char* s) {int indices[256];for (int i = 0; i < 256; i++)  // init the array, memset can only be used for charindices[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 解答

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:last_seen = {}ans = 0lo = 0for i, c in enumerate(s):lo = max(lo, last_seen.get(c, -1) + 1)  # 更新下边界last_seen[c] = ians = max(ans, i - lo + 1)return ans

4 找到两个排序数组的中位数

解法参见这里

使用两个数字 i 和 j, 分别作为 AB 的分隔元素，把 AB 分成两份，比如
A[0..i], B[0..j] 和 A[i, m], B[j, n]，这样我们只需要下面两个条件就可以了：

• i+j = m-i + n-j, 也就是 i+j = (m+n)/2
• B[j-1] <= A[i] && A[i-1] <= B[j], B 的前一半元素小于 A 的分隔符，A 的前一半元素小于 B 的分隔符

这时候我们就得到了 A[i] 就是我们的中位数，或者之一。 i 的初始值在 0 到 m 之间，
然后我们二分搜索 i = (imin + imax) / 2, j = mid - i。

C 解答

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
double findMedianSortedArrays(int* A, int m, int* B, int n) {if (m > n) return findMedianSortedArrays(B, n, A, m);int imin = 0, imax = m, i, j, num1, mid = (m + n + 1) >> 1, num2;while (imin <= imax) {i = (imin + imax) // 2;j = mid - i;if (i < m && j > 0 && B[j-1] > A[i]) {  // B 中的数字偏大imin = i + 1;} else if (i > 0 && j < n && B[j] < A[i-1]) { // A 中的数字偏大imax = i - 1;} else {if (i == 0)num1 = B[j-1];else if (j == 0)num1 = A[i - 1];elsenum1 = max(A[i-1],B[j-1]);  // 普通情况break;}}if ((m + n) & 0x1) // oddreturn num1;if (i == m)num2 = B[j];else if (j == n)num2 = A[i];elsenum2 = min(A[i], B[j]); // 普通情况return (num1 + num2) / 2.0; // 注意整数除法
}

5 最长回文子串

1. 以某个元素为中心，向两边展开，注意处理奇数和偶数两种情况
2. Manacher 算法，参见这里

Python 解答

class Solution:def longestPalindrome(self, s: str) -> str:ans = ""length = 0for i in range(len(s)):j = 0# 奇数长度回文子串while i - j >= 0 and i + j < len(s) and s[i-j] == s[i+j]:if j * 2 + 1 > length:length = j * 2 + 1ans = s[i-j:i+j+1]j += 1j = 0# 偶数长度回文子串while i - j >= 0 and i + j + 1 < len(s) and s[i-j] == s[i+j+1]:if j * 2 + 2 > length:length = j * 2 + 2ans = s[i-j:i+j+2]j += 1return ans

C 解答

char* longestPalindrome(char* s) {if (!s) return NULL;int length = 0; // length of the longest palindromic stringint start = -1; // start of the lonest palidromic stringint len = strlen(s);for (int i = 0; i < len; i++) {// 奇数长度的回文子串for (int j = 0; (i - j >= 0) && (i + j < len); j++) {if (s[i - j] != s[i + j])break;if (j * 2 + 1 > length) {length = j * 2 + 1;start = i - j;}}// 偶数长度的回文子串for (int j = 0; (i - j >= 0) && (i + j + 1 < len); j++) {if (s[i - j] != s[i + j + 1])break;if (j * 2 + 2 > length) {length = j * 2 + 2;start = i - j;}}}char* result = malloc(sizeof(char) * length + 1);strncpy(result, s + start, length);result[length] = 0;return result;
}

6 ZigZag 字符串，把字符串掰弯，然后再按行输出

考察数学，找出规律，所以实际上并不是 Z 子形，而是由 V 组成的，然后组合按行号重构后的字符串即可。

C 解答

// 这个方法不容易理解，建议看 Python 的
char* convert(char* s, int numRows) {int len = strlen(s);if (!s || numRows <= 1 || len < numRows) return s; // no need to convertchar* 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;
}

Python 解答

class Solution:def convert(self, s: str, numRows: int) -> str:if numRows <= 1 or len(s) <= numRows:  # 没有这个条件会超时return sinterval = 2 * numRows - 2ans = []# 第一行j = 0while j < len(s):ans.append(s[j])j += interval# 中间行for i in range(1, numRows-1):j = 0while 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 - 1while j < len(s):ans.append(s[j])j += intervalreturn "".join(ans)

7 翻转数字，溢出返回 0

注意溢出

C 解答

int reverse(int x) {if (x == INT_MIN) return 0;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 解答

class Solution:def reverse(self, x: int) -> int:sign = 1 if x >= 0 else -1x *= signy = 0while x > 0:y = y * 10 + x % 10x //= 10if y > 2**31:return 0return y * sign

8 实现 atoi

这道题考察各种细节，注意各种特殊情况：

1. 首先过滤空格
2. 判定符号，符号只能出现一次
3. 是否溢出，溢出返回 INT_MAX 或者 INT_MIN

Python 解答

class Solution:def myAtoi(self, s: str) -> int:s = s.lstrip()if not s:return 0sign = 1ans = 0i = 0if s[i] == "-":sign = -1i += 1elif s[i] == "+":i += 1while i < len(s) and s[i].isdigit():ans = ans * 10 + ord(s[i]) - ord("0")i += 1ans *= signreturn max(min(ans, 2**31-1), - 2 ** 31)

C 解答

int myAtoi(char* str) {if (!str) return 0;int sign = 1;int result = 0;// discarding spaceswhile (isspace(*str))str++;// determining signif (*str == '-' || *str == '+') {if (*str == '-') sign = -1;if (*str == '+') sign = 1;str++;}// constructing integerwhile (isdigit(*str)) {// handling overflowif (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 解答

class Solution:def isPalindrome(self, x: int) -> bool:if x < 0:return Falseif x != 0 and x % 10 == 0:return Falsey = 0# 回文走到一半就行了，没必要完全翻转过来while x > y:y = y * 10 + x % 10x //= 10return x == y or x == y // 10

C 解答

bool isPalindrome(int x) {// tricky here, for x == k * 10^jif (x < 0 || x && (x % 10 == 0)) return false;int y = 0;while (x > y) {y = y * 10 + x % 10;x /= 10;}return x == y || x == y / 10; // 注意 x 可能是奇数长度也可能是偶数
}

10 正则表达式

实现正则表达式，只需要实现.代表任意字符，*代表任意重复。只需要特殊处理*，
如果遇到了*，贪婪地向后匹配。和通配符的不同之处在于，正则表达式需要两个字母
组成模式，*是对前一个字母的修饰。

C 解答

bool isMatch(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*`else if (isMatch(s, p + 2))return true;// s ends or p and s differsif (*s == 0 || c != '.' && c != *s)return false;}return *s == 0;
}

11 盛最多水的容器

从左右向中间逼近，如果有更大的就更新。简单的一道双指针题目，别想太多。

C++ 解答

int maxArea(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++;elseright--;}return result;
}

Python 解答

class Solution:def maxArea(self, height: List[int]) -> int:lo = 0hi = len(height) - 1ans = 0while lo < hi:water = min(height[lo], height[hi]) * (hi - lo)ans = max(ans, water)if height[lo] < height[hi]:lo += 1else:hi -= 1return ans

12 十进制转换为罗马数字

直接按每位把罗马数字转换出来在拼接就好了，使用 C 的话，拼接字符串很麻烦。

Python 解答

class Solution:def intToRoman(self, x: int) -> str:thousands = ["", "M", "MM", "MMM"]hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]return thousands[x//1000] + hundreds[x%1000//100] + tens[x%100//10] + ones[x%10]

C++ 解答

string intToRoman(int num) {// note, the leading empty string is the trick herestring thousands[] = {"", "M", "MM", "MMM"};string handreds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};string tens[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};string ones[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};return thousands[num / 1000] + handreds[num % 1000 / 100] + tens[num % 100 / 10] + ones[num % 10];
}

C 解答

char *intToRoman(int num) {int digits[4] = {0};char* romans = (char*)malloc(sizeof(char));char* cursor = romans;// if num = 1234, then// digits = {1, 2, 3, 4};int base = 1000;for (int i = 0; i < 4; i++) {digits[i] = num / base;num = num % base;base /= 10;}doRoman(digits[0], '_', '_', 'M', &cursor); // '_' can be anythingdoRoman(digits[1], 'M', 'D', 'C', &cursor);doRoman(digits[2], 'C', 'L', 'X', &cursor);doRoman(digits[3], 'X', 'V', 'I', &cursor);*cursor = '\0';return romans;
}void doRoman(int number, char ten, char five, char one, char** str) {switch (number) {case 9:(*str)[0] = one;(*str)[1] = ten;(*str) += 2;break;case 8:(*str)[0] = five;(*str)[1] = one;(*str)[2] = one;(*str)[3] = one;(*str) += 4;break;case 7:(*str)[0] = five;(*str)[1] = one;(*str)[2] = one;(*str) += 3;break;case 6:(*str)[0] = five;(*str)[1] = one;(*str) += 2;break;case 5:(*str)[0] = five;(*str) += 1;break;case 4:(*str)[0] = one;(*str)[1] = five;(*str) += 2;break;case 3:(*str)[0] = one;(*str)[1] = one;(*str)[2] = one;(*str) += 3;break;case 2:(*str)[0] = one;(*str)[1] = one;(*str) += 2;break;case 1:(*str)[0] = one;(*str) += 1;break;case 0:default:break;}
}

13 罗马数字转为十进制

主要是当前一个数字小于后一个数字的时候，需要添加的是后一个数和前一个数字的差。

Python 解答

class Solution:def romanToInt(self, s: str) -> int:vals = {"I": 1,"V": 5,"X": 10,"L": 50,"C": 100,"D": 500,"M": 1000}ans = 0i = 0while i < len(s):if i+1<len(s) and vals[s[i]] < vals[s[i+1]]:ans += vals[s[i+1]] - vals[s[i]]i += 2else:ans += vals[s[i]]i += 1return ans

C 解答

// acts like a dict or map
int getVal(char c) {switch (c) {case 'I': return 1;case 'V': return 5;case 'X': return 10;case 'L': return 50;case 'C': return 100;case 'D': return 500;case 'M': return 1000;}
}int romanToInt(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;elseresult += getVal(s[i]), i++;}return result;
}

14 最长公共前缀

纵向扫描，从头到尾，如果不一致，返回当前子串即可。

Python 解答

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if not strs:return ""if len(strs) == 1:return strs[0]minlen = min([len(str) for str in strs])for i in range(minlen):for j in range(1, len(strs)):if strs[j][i] != strs[0][i]:return strs[0][:i]return strs[0][:minlen]

C 解答

// 纵向扫描
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 的方法做就好了。做这种数组题的套路就是实在不行排个
序。

Python 解答

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:if len(nums) < 3:return []nums.sort()ans = []for i in range(len(nums)):if i > 0 and nums[i] == nums[i-1]:continuek = len(nums) - 1j = i + 1while j < k:sum = nums[i] + nums[j] + nums[k]if sum > 0:k -= 1elif sum < 0:j += 1else:ans.append([nums[i], nums[j], nums[k]])while j < k and nums[j] == nums[j+1]:j += 1while j < k and nums[k] == nums[k-1]:k -= 1j += 1k -= 1return ans

C++ 解答

vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> result;for (int i = 0; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i-1])continue;int k = nums.size() - 1;int j = i + 1;while (j < k) {if (nums[i] + nums[j] + nums[k] > 0)k--;else if (nums[i] + nums[j] + nums[k] < 0)j++;else {result.push_back({nums[i], nums[j], nums[k]});// skipping duplicateswhile (j < k && nums[k] == nums[k - 1])k--;while (j < k && nums[j] == nums[j + 1])j++;k--; // 别忘了这里，还要继续寻找下一组j++;}}}return result;
}

16 在数组中找到三个数字使得他们得和尽可能的接近给定数字，假设结果唯一

和上一题解法类似，在 http://stackoverflow.com/q/2070359 有详尽解释

Python 解答

class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:if len(nums) < 3:return []nums.sort()ans = nums[0] + nums[1] + nums[2]for i in range(len(nums)):j = i + 1k = len(nums) - 1while j < k:sum = nums[i] + nums[j] + nums[k]if sum == target:return targetelif abs(target-sum) < abs(target-ans):ans = sumelse:if sum > target:k -= 1else:j += 1return ans

C 解答

int cmp(int* a, int* b) {return *a - *b;
}int threeSumClosest(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--;elsej++;}}return result;
}

17 生成电话键盘按键数字对应的所有可能的字符串，不限制返回结果的顺序

tags: #backtracking

递归：

这道题是一道典型的，最简单的深度优先遍历，生成所有可能解的问题。

迭代：

遍历数字，设当前结果为{a, b, c}, 下一个数字是3, 找出对应的字母{d, e, f}, 则新的结果是

{ a + {def}, b + {def}, c + {def}}

然后把新获得的数组作为下一轮的初始数组。最开始时，使用空数组开始。

Python 解答

class Solution:def letterCombinations(self, digits: str) -> List[str]:c2n = {"2": "abc","3": "def","4": "ghi","5": "jkl","6": "mno","7": "pqrs","8": "tuv","9": "wxyz"}def dfs(combination, next_digits):if not next_digits:ans.append(combination)returnfor char in c2n[next_digits[0]]:dfs(combination + char, next_digits[1:])if not digits:return []ans = []dfs("", digits)return ans

C++ 解答

// iterative
vector<string> letterCombinations(string digits) {if (digits.size() == 0) return vector<string> {};string mapping[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};vector<string> combinations(1, ""); // 注意使用空字符串作为种子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;
}

还可以使用深度优先的搜索方法

追问：如何通过用户按的数字来查找是否有对应的单词呢

1. 通过把所有的单词计算出来，然后查询哪个是合法的，查询可以使用 Trie
2. 通过把已经有的单词字典转换为数字字典，然后通过数字序列查询可能的单词组合。

18 4Sum

tags: #backtracking

其实可以用 深度优先搜索的方式直接解答 nSum

Python 解答

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:return self.nSum(nums, target, 4)def nSum(self, nums, target, n):def dfs(pos: int, cur: List[int], n: int, target: int):if n == 2:j = posk = len(nums) - 1while j < k:sum = nums[j] + nums[k]if sum < target:j += 1elif sum > target:k -= 1else:solution = cur[:] + [nums[j], nums[k]]ans.append(solution)while j < k and nums[j] == nums[j+1]:j += 1while j < k and nums[k] == nums[k-1]:k -= 1j += 1k -= 1returni = poswhile 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 += 1continuecur.append(nums[i])dfs(i+1, cur, n-1, target-nums[i])cur.pop()i += 1ans = []nums.sort()dfs(0, [], n, target)return ans

下面的 C++ 解法是一个传统解法

C++ 解答

vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> result;int n = nums.size();if (n < 4) return result;sort(nums.begin(), nums.end());unordered_map<int, vector<pair<int, int>>> hash;for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){hash[nums[i]+nums[j]].push_back(make_pair(i,j));}}for (int i = 0; i < n; i++) {if (i > 0 && nums[i] == nums[i-1])continue;for (int j = i+1; j < n; j++) {if (j > i + 1 && nums[j] == nums[j-1])continue;int re = target - nums[i] - nums[j];if (hash.find(re) != hash.end()) {for (auto match : hash[re]) {int k = match.first, l = match.second;if (k > j) {if (!result.empty()&& result.back()[0] == nums[i] && result.back()[1] == nums[j]&& result.back()[2] == nums[k] && result.back()[3] == nums[l])continue;result.push_back({nums[i], nums[j], nums[k], nums[l]});}}}}}return result;
}

19 删除链表中倒数第 k 的节点

tags: #pointers

双指针经典题目，一个快指针先走 k 步，另一个慢指针再出发，注意链表长度小于 k 时。

注意：LeetCode 给定的 n 都是有效地，但要求返回头指针，如果头指针被删除需要额外注意，因此采用 dummy head

Python 解答

class Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:dummy = ListNode(-1)dummy.next = headp = dummywhile n >= 0:p = p.nextn -= 1q = dummywhile p:q = q.nextp = p.nextq.next = q.next.nextreturn dummy.next

C 解答

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode dummy, *fast, *slow;dummy.next = fast = head;slow = &dummy;while (n--)fast = fast->next;while (fast) {fast = fast->next;slow = slow->next;}struct ListNode* next = slow->next;slow->next = next->next;free(next); // remeber to free memoryreturn dummy.next;
}

20 判定给定的字符串是否是合法的括号序列，可能包括大中小三类

tags: #stack

使用栈的基础题，注意逻辑简化

Python 解答

class Solution:def isValid(self, s: str) -> bool:valid = Truestack = []match = {")": "(", "]": "[", "}": "{"}for c in s:if c in ("(", "[", "{"):stack.append(c)else:if not stack:return Falseif stack[-1] != match[c]:return Falsestack.pop()return not stack

C 解答

char opposite(char c) {switch (c) {case ')' : return '(';case ']' : return '[';case '}' : return '{';}
}bool isValid(string s) {stack<char> stk;for (auto& c : s) {if (c == '(' || c == '[' || c == '{')stk.push(c);else if (!stk.empty() && stk.top() == opposite(c))stk.pop();elsereturn false;}return stk.empty(); // 注意为空的条件
}

Rust 解答

impl Solution {pub fn is_valid(s: String) -> bool {let mut stack = vec![];// let map =for ch in s.chars() {match ch {'(' | '{' | '[' => stack.push(ch),')' => if let Some('(') = stack.pop() {} else { return false },'}' => if let Some('{') = stack.pop() {} else { return false },']' => if let Some('[') = stack.pop() {} else { return false },_ => return false}}stack.len() == 0}
}

21 合并两个已经排序的链表

tags: #pointers

考察链表的基本操作，很简单

Python 解答

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:dummy = ListNode(-1)p = dummywhile l1 and l2:if l1.val < l2.val:p.next = l1l1 = l1.nextelse:p.next = l2l2 = l2.nextp = p.nextif l1:p.next = l1if l2:p.next = l2return dummy.next

C 解答

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {if (l1 == NULL) return l2;if (l2 == NULL) return l1;struct ListNode dummy;dummy.next == NULL;struct ListNode* p = &dummy;while (l1 && l2) {if (l1->val < l2->val) {p->next = l1;l1 = l1->next;} else {p->next = l2;l2 = l2->next;}p = p->next;}if (l1)p->next = l1;if (l2)p->next = l2;return dummy.next;
}

22 给定数字 n, 生成所有合法的 n 个括号组成的序列

tags: #backtracking

一道典型的深度优先搜索题目

Python 解答

class Solution:def generateParenthesis(self, n: int) -> List[str]:def dfs(s, lefts, rights):if lefts == 0 and rights == 0:ans.append(s)returnif lefts > 0:dfs(s+"(", lefts-1, rights)if (lefts < rights):dfs(s+")", lefts, rights-1)ans = []dfs("", n, n)return ans

C++ 解答

vector<string> generateParenthesis(int n) {vector<string> result;gen(result, "", n, n);return result;
}// left 剩下的左括号，right 剩下的右括号
void gen(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);
}

23 合并 K 个排序的列表

使用优先级队列，复杂度最小。

Python 解答

把列表看做一个队列，每次拿出两个列表，合并他们后放回到列表中，每次遍历列表的一半，这样每次遍历完一遍，
列表的长度都会减半，直到列表的长度为 1, 合并函数使用 21 题中的合并两个列表的函数

C 解答

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {// see above
}struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {if (!lists || listsSize < 1)return NULL;while (listsSize > 1) {// listsize is halfedfor (int i = 0; i < listsSize / 2; i++)// merge i and last i listlists[i] = mergeTwoLists(lists[i], lists[listsSize-1-i]);listsSize = (listsSize + 1) / 2; // 注意这里！}return lists[0];
}

24 给定一个链表，交换两个相邻节点的值

最简单的做法显然是直接把前后两个节点的值交换，但是 LeetCode 规定不能改变节点的值。
主要考察链表的指针操作，注意各种细节，一定要在纸上先把链表画出来。

Python 解答

class Solution:def swapPairs(self, head: ListNode) -> ListNode:dummy = ListNode(-1)dummy.next = headp = dummywhile p.next and p.next.next:t = p.nextp.next = t.nextt.next = p.next.nextp.next.next = tp = p.next.nextreturn dummy.next

C 解答

struct ListNode* swapPairs(struct ListNode* head) {struct ListNode dummy, *temp, *pnext, *p = &dummy;dummy.next = head;while (p->next && p->next->next) {temp = p->next;p->next = temp->next;temp->next = p->next->next;p->next->next = temp;p = temp;}return dummy.next;
}

25 给定一个链表，把相邻的 k 个节点反转

和上题一样，同样禁止改变节点的值。比较简单地解法是浪费一点空间，使用 Stack, 实现
逆转 k 个节点，注意如果 k 较大的话，这种方法是不合适的。另一种方法是直接翻转，空间是
O(1) 的，但是时间复杂度是 2N。

Python 解答

class Solution:def reverseList(self, head):prev = Nonecurr = headwhile curr:next = curr.nextcurr.next = prevprev = currcurr = nextreturn prevdef reverseKGroup(self, head: ListNode, k: int) -> ListNode:dummy = ListNode(-1)dummy.next = headp = dummywhile p.next:n = kq = p# 找到下一组接点的头while n > 0 and q.next:q = q.nextn -= 1# 如果节点不够了直接退出if n > 0:break# 把这段链表先截下来next = q.nextq.next = Nonetail = p.nextp.next = self.reverseList(p.next)p = tailp.next = nextreturn dummy.next

使用 Stack 的 C++ 解法

C++ 解答

ListNode* reverseKGroup(ListNode* head, int k) {stack<ListNode*> stk;ListNode dummy(-1), *p = &dummy, *pp;dummy.next = head;while (1) {pp = p;for (int i = 0; i < k; i++) {if (pp->next) {stk.push(pp->next);pp = pp->next;} else {break;}}if (stk.size() < k) // 剩下的节点不够 k 个了return dummy.next;pp = stk.top()->next; // 下一组中的第一个while (!stk.empty()) {p->next = stk.top();stk.pop();p = p->next;}p->next = pp;}
}

26 删除排序数组中的重复项

tags: #naive

in-place 的删除重复元素，使用两个指针，一个遍历，一个指向当前的结尾。

PS：这个基础题竟然做了半个小时才做对，⊙﹏⊙b 汗，要加强基础啊！

这类数组中去除中间元素的题写的时候还是很容易出错，重点是使用一个 length 变量，
然后还是要遍历整个数组。不要想什么双指针了。

Python 解答

class Solution:def removeDuplicates(self, nums: List[int]) -> int:if len(nums) < 2:return len(nums)length = 0for i in range(len(nums)):# 处理 i == 0 的情况也是需要注意的if i == 0 or nums[i] != nums[length-1]:nums[length] = nums[i]length += 1return length

C 解答

int removeDuplicates(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 解答

class Solution:def removeElement(self, nums: List[int], val: int) -> int:if not nums:return 0length = 0for i in range(len(nums)):if nums[i] != val:nums[length] = nums[i]length += 1return length

C 解答

int removeElement(int* nums, int numsSize, int val) {if (!nums || numsSize == 0) return 0;int len = 0;for (int i = 0; i < numsSize; i++) {if (nums[i] != val)nums[len++] = nums[i];}return len;
}

28 实现 strstr 函数，即查找子串

使用暴力算法，时间复杂度 O(n)。也可以用 kmp 算法。

Python 解答

# kmp 算法
class Solution:def strStr(self, haystack: str, needle: str) -> int:if not needle:return 0next = [0]j = 0# 特别注意这里的 1for i in range(1, len(needle)):while j > 0 and needle[i] != needle[j]:j = next[j-1]if needle[i] == needle[j]:j += 1next.append(j)j = 0for i in range(len(haystack)):while j > 0 and haystack[i] != needle[j]:j = next[j-1]if haystack[i] == needle[j]:j += 1if j == len(needle):return i - j + 1return -1

C 解答

/** Brute Force*/
int strStr(char* haystack, char* needle) {int h = strlen(haystack);int n = strlen(needle);if (n == 0) return 0;// note h - n + 1for (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;
}

29 给定连个整数，不使用乘法和除法计算除法。

这里 有一个非常好的算法

计算可以从被除数中减去除数的次数

C 解答

int divide(int dividend, int divisor) {// abs(INT_MIN) == INT_MAX + 1if (divisor == 0 || (dividend == INT_MIN && divisor == -1))return INT_MAX;int sign = (dividend > 0) == (divisor > 0) ? 1 : -1;long long n = labs(dividend);long long d = labs(divisor);int result = 0;while (n >= d) {long long temp = d;long long multi = 1;while (n >= (temp << 1)) {temp <<= 1;multi <<= 1;}n -= temp;result += multi;}return sign * result;
}

30 包串联所有单词的子串

tags: #slidewindow

一道诡异的滑动窗口的题目，对这类问题还是不很熟啊。

Python 解答

C++ 解答

vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string, int> counts;for (string word : words)counts[word]++;int n = s.length(), num = words.size(), len = words[0].size();vector<int> indexes;for (int i = 0; i < n - num * len + 1; i++) {unordered_map<string, int> seen;int j = 0;for (; j < num; j++) {string word = s.substr(i + j * len, len);if (counts.find(word) != counts.end()) {seen[word]++;if (seen[word] > counts[word])break;} else {break;}}if (j == num)indexes.push_back(i);}return indexes;
}

31 全排列，下一个

首先，对于所有的组合，最小的一个一定是按照升序排序的，最大的一定是倒过来，因此

1. 如果我们发现是完全倒序的，直接翻转就好了；
2. 如果是一般情况，从后向前遍历，找到逆序的数字的边界，假设是 k。那么后边这段已经是完全
   逆序的，无法变小了，为了保证生成的数字变大，我们再从后向前找到第一个比 k 大的数字，交
   换这两个数字，再把后续的逆序数组翻转。

Python 解答

class Solution:def nextPermutation(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""# 前后都是闭区间def reverse(nums, lo, hi):while lo < hi:nums[lo], nums[hi] = nums[hi], nums[lo]lo += 1hi -= 1k = -1for i in range(len(nums)-2, -1, -1):if nums[i] < nums[i + 1]:k = ibreakif k == -1:reverse(nums, 0, len(nums)-1)returnl = -1for i in range(len(nums)-1, k, -1):if nums[i] > nums[k]:l = ibreaknums[l], nums[k] = nums[k], nums[l]reverse(nums, k+1, len(nums)-1)

C++ 解答

void nextPermutation(vector<int>& nums) {int k = -1; // 升序排列的最后一个数字for (int i = nums.size() - 2; i >= 0; i--) {if (nums[i] < nums[i + 1]) {k = i;break;}}// 完全是逆序的，直接返回第一个，也就是升序排列if (k == -1) {reverse(nums.begin(), nums.end());return;}int l = -1; // 逆序数字中比 k 大的最小的数字for (int i = nums.size() - 1; i > k; i--) {if (nums[i] > nums[k]) {l = i;break;}}swap(nums[k], nums[l]); // 保证变大reverse(nums.begin() + k + 1, nums.end()); // 保证是下一个
}

32 从一个括号构成的字符串中找出最长的合法括号序列

动态规划的基础题目。

Python 解答

class Solution:def longestValidParentheses(self, s: str) -> int:dp = [0] * len(s)ans = 0for i in range(1, len(s)):if s[i] == ")":if s[i-1] == "(":if i >= 2:dp[i] = dp[i-2] + 2else:dp[i] = 2elif i - dp[i-1] > 0 and s[i-dp[i-1]-1] == "(":if i - dp[i-1] >= 2:dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2else:dp[i] = dp[i-1] + 2ans = max(ans, dp[i])return ans

也可以使用栈来解。但是这种方法非常 tricky, 因为要考虑到 ()() 的情况。

33 在排序后又被反转的数组中搜索

既然是部分有序的，自然还是使用二分搜索了，注意终止条件。
不同于普通二分搜索的两种情况，我们有了四种情况：

1. 前半部分有序，并且在前半部分当中，
2. 前半部分有序，但是不在前半部分
3. 后半部分有序，并且在后半部分
4. 后半部分有序，但是不在后半部分

Python 解答

class Solution:def search(self, nums: List[int], target: int) -> int:if not nums:return -1lo = 0hi = len(nums) - 1while lo <= hi:mi = lo + (hi - lo) // 2if nums[mi] == target:return mi# 这里为什么要包含等于号呢if nums[lo] <= nums[mi]:if nums[lo] <= target < nums[mi]:hi = mi - 1else:lo = mi + 1else:if nums[mi] < target <= nums[hi]:lo = mi + 1else:hi = mi - 1return -1

C 解答

int search(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;// left half is sortedif (nums[left] <= nums[mid]) {if (nums[left] <= target && target < nums[mid])right = mid - 1;elseleft = mid + 1;// right half is sorted} else {if (nums[mid] < target && target <= nums[right])left = mid + 1;elseright = mid - 1;}}return -1;
}

34 在排序数组中查找元素的第一个和最后一个位置

在 C++ 的标准库中包含了这两个函数，分别是std::lower_bound和std::upper_bound.

C++ 解答

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:if not nums:return [-1, -1]lo = 0hi = len(nums)lower = -1while lo < hi:mi = lo + (hi - lo) // 2if nums[mi] < target:lo = mi + 1else:hi = miif lo < len(nums) and nums[lo] == target:lower = lolo = 0hi = len(nums)upper = -1while lo < hi:mi = lo + (hi - lo) // 2if nums[mi] <= target:lo = mi + 1else:hi = miif nums[lo-1] == target:upper = lo - 1return [lower, upper]

35 二分查找数字，如果没有找到，返回应该插入的位置

就是最基础的二分查找

Python 解答

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:lo = 0hi = len(nums)while lo < hi:mi = lo + (hi - lo) // 2if nums[mi] == target:return mielif nums[mi] < target:lo = mi + 1else:hi = mireturn lo

C 解答

int searchInsert(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;else if (nums[mid] < target)left = mid + 1;elseright = mid - 1;}return left;
}

36 合法数独，给定一个数独表，判定当前是否合法

Python 解答

class Solution:def isValidSudoku(self, board: List[List[str]]) -> bool:"""这道题的关键就在于小格子也是可以用 i 和 j 来计算的：box_index = (row / 3) * 3 + columns / 3"""# 特别注意浅拷贝的问题used_i = [[0] * 9 for _ in range(9)]used_j = [[0] * 9 for _ in range(9)]used_k = [[0] * 9 for _ in range(9)]for i in range(9):for j in range(9):piece = board[i][j]if piece == ".":continuen = int(piece) - 1k = i // 3 * 3 + j // 3if used_i[i][n] or used_j[j][n] or used_k[k][n]:return Falseused_i[i][n] = used_j[j][n] = used_k[k][n] = 1return True

C 解答

// 有点浪费空间
bool isValidSudoku(char** board, int row, int col) {bool used_row[9][9] = {false}, used_col[9][9] = {false}, used_box[9][9] = {false};for (int i = 0; i < row; i++)for (int j = 0; j < col; j++)if (board[i][j] != '.') {int num = board[i][j] - '0' - 1;int k = i / 3 * 3 + j / 3;if (used_row[i][num] || used_col[j][num] || used_box[k][num])return false;used_row[i][num] = used_col[j][num] = used_box[k][num] = true;}return true;
}

37 求解数独

C++ 解答

void solveSudoku(vector<vector<char>>& board) {solve(board, 0);
}
bool solve(vector<vector<char>>& board, int ind){if(ind==81) return true;int i=ind/9, j=ind%9;if(board[i][j]!='.')return solve(board, ind+1);else{for(char f = '1'; f <= '9'; f++) {if(isValidFill(board, i, j, f)) {board[i][j]= f;if(solve(board, ind+1)) return true;board[i][j]='.';}}return false;}
}
bool isValidFill(vector<vector<char>>& board, int i, int j, char fill) {for(int k=0; k<9; k++) {if(board[i][k]==fill) return false; //check the rowif(board[k][j]==fill) return false; //check the columnint r= i/3*3+j/3;   //select the blockif(board[r/3*3+k/3][r%3*3+k%3]==fill) return false; //check the block}return true;
}

38 数数并说出来

不太理解这道题有什么意义，直接暴力做出来了

C++ 解答

string countAndSay(int n) {string result = "1";for (int i = 0; i < n -1; i++) {string temp;for (int j = 0; j < result.size(); j++) {int count = 1;while (j + 1 < result.size() && result[j+1] == result[j]) {j++; count++;}temp += count + '0';temp += result[j];}result = temp;}return result;
}

39 给定一个集合，在集合中找出和为 target 的数字，数字可以使用多次，集合中没有重复数字

典型的深度优先搜索

C++ 解答

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> result;dfs(result, candidates, {}, target);return result;
}void dfs(vector<vector<int>>& result, vector<int>& candidates, vector<int> comb, int target) {if (target == 0) {result.push_back(comb);return;}for (auto c : candidates) {if (c > target) continue; // 数字太大了if (!comb.empty() && c < comb.back()) continue; // 保证不重复且升序comb.push_back(c);dfs(result, candidates, comb, target - c);comb.pop_back(); // 注意此处还需要弹出，因为需要循环}
}

40 同上题一样，但是集合中的数字只能使用一次，并且集合中有重复数字

C++ 解答

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<vector<int>> result;sort(candidates.begin(), candidates.end());dfs(result, candidates, {}, target, 0);return result;
}void dfs(vector<vector<int>>& result, vector<int>& candidates, vector<int> comb, int target, int start) {if (target == 0) {result.push_back(comb);return;}for (int i = start; i < candidates.size(); i++) {if (candidates[i] > target)break;if (i != start && candidates[i] == candidates[i-1])continue;comb.push_back(candidates[i]);dfs(result, candidates, comb, target - candidates[i], i + 1);comb.pop_back();}
}

41 给定一个数组，找到第一个缺失的正数

显然，结果的范围是 [1…n+1]. 而数组的长度为 n 我们把每个位置都放上 i+1,
这样如果有位置不是 i+1, 则找到了结果，如果都相等则是 n+1.

c 解答

void swap(int* a, int* b) {int t = *a; *a = *b; *b = t;
}int firstMissingPositive(int* nums, int numsSize) {for (int i = 0; i < numsSize; i++)// 注意此处的 whilewhile (nums[i] > 0 && nums[i] <= numsSize && nums[i] != nums[nums[i] - 1])swap(&nums[i], &nums[nums[i] - 1]);for (int i = 0; i < numsSize; i++)if (nums[i] != i + 1)return i + 1;return numsSize + 1;
}

42 给定一个数组表示柱子的高度，求能存贮的雨水的总量

从两边向中间收拢

C 解答

int trap(int* height, int heightSize) {int left = 0, right = heightSize - 1;int water = 0;int max_left = 0, max_right = 0;// 从两侧向中间缩小，可以算作是两个指针吧while (left <= right) {if (height[left] <= height[right]) {if (height[left] >= max_left)max_left = height[left];elsewater += max_left - height[left];left++;} else {if (height[right] >= max_right)max_right = height[right];elsewater += max_right - height[right];right--;}}return water;
}

Rust 解答

impl Solution {pub fn trap(height: Vec<i32>) -> i32 {if height.is_empty() {return 0;}let mut left = 0;let mut right = height.len() - 1;let mut water = 0;let mut max_left = 0;let mut max_right = 0;while left <= right {if height[left] <= height[right] {if height[left] >= max_left {max_left = height[left];} else {water += max_left - height[left];}left += 1;} else {if height[right] >= max_right {max_right = height[right];} else {water += max_right - height[right];}right -= 1;}}water}
}

t

43 给定两个任意长的字符串，返回一个字符串，代表他们相乘的结果

按整数除法运算即可，重点是下标的表示

C 解答

#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 的值，如果发生了不匹配的话，我们尝试回到该位置的下一个位置开始匹配

C 解答

bool isMatch(char* s, char* p) {char* star = NULL;char* revert = s;while (*s) {if (*s == *p || *p == '?')s++, p++;else if (*p == '*')star = p++, revert = s;else if (star)p = star + 1, s = ++revert;elsereturn false;}// 如果剩下了 p, 那应该全都是*才对while (*p) {if (*p++ != '*')return false;}return true;
}

45 跳跃游戏，给定一个数组，每个数字是在该位置可以向前移动的距离，返回最少需要多少次才能到达终点

比较简单，看注释吧

C 解答

int jump(int* nums, int numsSize) {int steps = 0;int last = 0; // last rangeint cur = 0; // current rangefor (int i = 0; i < numsSize; i++) {// beyond range, make another jumpif (i > last)last = cur, steps++;// if we could reach longer?if (nums[i] + i > cur)cur = nums[i] + i;}return steps;
}

46 生成全排列

Cracking 上给出了一种解法，通过不断的添加下一个元素到上一组元素的不同位置来生成全排列，这样固然可以，但是大规模的拼接数组或者字符串是很耗费资源的。

在已经有了字符串（或者数组）的初始排列以后，可以通过不断交换的方法生成每一组全排列。
比如对于 xyz，我们有全排列为

x + per(yx)
y + per(xz)
z + per(xy)

那么我们通过把每个元素交换到第一个位置，就把问题规模缩小了，知道把问题规模缩小为 1.

C++ 解答

vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> result;per(result, nums, 0);return result;
}void per(vector<vector<int>>& result, vector<int>& nums, int begin) {if (begin >= nums.size()) {result.push_back(nums);return;}for (int i = begin; i < nums.size(); i++) { // 注意是从 begin 开始，这样未改变的才能加入进来swap(nums[begin], nums[i]);per(result, nums, begin + 1);swap(nums[begin], nums[i]); // 注意因为参数中是传引用，这里需要复原}
}

Rust 解答

impl Solution {pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {let mut result: Vec<Vec<i32>> = vec![];Self::per(&mut result, nums, 0);result}pub fn per(result: &mut Vec<Vec<i32>>, nums: Vec<i32>, begin: usize) {if begin >= nums.len() {result.push(nums);return}for i in begin..nums.len() {let mut nums = nums.clone();nums.swap(begin, i);Self::per(result, nums, begin + 1);}}
}

47 全排列，数组中有重复元素

和上一题基本是一样的，注意跳过重复元素就好了

C++ 解答

vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> result;per(result, nums, 0);return result;
}void per(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 解答

void rotate(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 <- leftmatrix[first][i] = matrix[last-offset][first];// left <- downmatrix[last-offset][first] = matrix[last][last-offset];// down <- rightmatrix[last][last-offset] = matrix[i][last];// right <- upmatrix[i][last] = top;}}
}

49 给定字符数组，把他们按照 Anagram 分组

C++ 解答

// 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 解答

// recursive
double myPow(double x, int n) {if (n == INT_MIN) return myPow(x, n - 1) * x;if (n < 0) return 1 / myPow(x, -n);if (n == 0) return 1;if (n == 1) return x;double y = myPow(x, n / 2);if (n & 0x1)return y * y * x;elsereturn y * y;
}

迭代做法

C 解答

// iteratively
double myPow(double x, long p) {double result = 1;if (p < 0)return 1 / myPow(x, -p);while (p) {if (p & 1)result *= x;x *= x;p /= 2;}return result;
}

51 N 皇后问题

需要大幅度修改

C++ 解答

// N 皇后问题，皇后不能再一条直线，一条竖线，一条斜线上// 使用深度优先求解，对于 dfs 问题，我们首先把算法的框架写下来，然后确定这个问题的限制条件
// 对于这个问题，限制条件当前行的元素不能在以前的列中出现过，也不能在对角线中出现过
vector<vector<string>> result;vector<vector<string>> solveNQueens(int n) {if (n < 1) return result;vector<int> x(n);dfs(0, x, n);return result;}void dfs(int t, vector<int>& x, int n) {// 当新添加一个 Q 到当前解的时候if (t >= n) {// result.push_back(make_solution(x));// return;vector<string> solution;for (int i = 0; i < n; i++) {string line(n, '.');line[x[i]] = 'Q';solution.push_back(line);}result.push_back(solution);} else {for (int i = 0; i < n; i++) {bool skip = false;for (int j = 0; j < t; j++) {if (x[j] == i || abs(i - x[j]) == abs(t - j)) {skip = true;break;}}if (skip) continue;x[t] = i;dfs(t+1, x, n);}}
}

52 N 皇后一共有多少个解

不要直接把皇后放好，而是把占用的都记录下来，然后继续深度优先搜索

C++ 解答

class Solution {
public:unordered_set<int> cols, digs1, digs2;int totalNQueens(int n) {return total(0, 0, n);}int total(int row, int count, int n) {for (int col = 0; col < n; col++) {if (cols.find(col) != cols.end()|| digs1.find(row - col) != digs1.end()|| digs2.find(row + col) != digs2.end())continue;if (row == n-1)count++;else {cols.insert(col);digs1.insert(row-col);digs2.insert(row+col);count = total(row+1, count, n);cols.erase(col);digs1.erase(row-col);digs2.erase(row+col);}}return count;}
};

53 最大子序列和

动态规划经典题目，遍历数组，如果已经当前子序列已经小于 0 了，抛弃并置 sum = 0
如果比当前和更大，更新。对于一个子序列，要么使得序列和增大，要么减小。

dp[n+1] = max(dp[n], dp[n] + A[n+1])

C 解答

int maxSubArray(int* nums, int numsSize) {int sum = 0;int m = INT_MIN;for (int i =0; i< numsSize; i++) {sum += nums[i];if (sum > m)m = sum;if (sum < 0)sum = 0;}return m;
}

Python 解答

class Solution:def maxSubArray(self, nums: List[int]) -> int:current_sum = 0max_value = float('-inf')for i in nums:current_sum += imax_value = max(max_value, current_sum)current_sum = max(0, current_sum)return max_value

54 顺时针螺旋打印矩阵

一圈一圈地打印就好了

C 解答

int* spiralOrder(int** matrix, int row, int col) {if (row == 0 || col == 0) return NULL;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 解答

bool canJump(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 解答

"""
class Interval(object):def __init__(self, start=0, end=0):self.start = startself.end= end
"""def merge(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 解答

class Solution:def insert(self, intervals, newInterval):ans = []start, end = newIntervalremainder = 0for 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 += 1ans.append([start, end])ans += intervals[remainder:]return ans

58 给定一个字符串，求其中最后一个单词的长度

显然这道题可以用 strlen 求出长度然后从后往前数，但是，这样相当于多遍历了一次
直接从后往前可以保证只遍历一次

C 解答

int lengthOfLastWord(char* s) {int len = 0;bool inWord = false;while (*s) {if (isspace(*s)) {inWord = false;} else {if (!inWord) {len = 1;inWord = true;} else {len++;}}s++;}return len;
}

59 给定 n，把 1, 2, 3 … 螺旋打印到矩阵中

和上一个完全一样的思路，只是这次是打印罢了

C 解答

/*** 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;
}

60 给定 n 个数字，找出第 k 个 Permutation

C++ 解答

class Solution {
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 swaps[j] = s[j-1];s[i] = c;k %= f;}return s;}
};

61 把列表旋转到倒数第 k 位

需要注意的是 k 大于列表长度的情况，这时候需要取余

C 解答

struct ListNode* rotateRight(struct ListNode* head, int k) {if (!head || k <= 0) return head;int l = 1;struct ListNode* n = head;while (n->next) {n = n->next;l++;}// n is now the tail!if (k >= l) k %= l;if (k == 0) return head;struct ListNode dummy, *p = &dummy;dummy.next = head;int i = l - k;while (i--)p = p->next;dummy.next = p->next;p->next = NULL;n->next = head;return dummy.next;
}

62 给定一个m*n的矩阵，有多少种方法从左上角移动到右下角

显然可以使用组合数学直接求出来解，但是容易溢出。而且这是一道经典的动态规划题目，对于
每个格子，可以从他的上部或者左面移动过来。

C++ 解答

int uniquePaths(int m, int n) {vector<vector<int>> grid(m, vector<int> (n, 1));for (int i = 1; i < m; i++)for (int j = 1; j < n; j++)grid[i][j] = grid[i - 1][j] + grid[i][j - 1];return grid[m - 1][n - 1];
}

63 同上题，区别是在一些位置是有障碍物的

经过分析可知，递推关系是一样的，只需要把有障碍格子的到达方法设定为 0。这个主要是实现上的一些技巧，
见注释。

C++ 解答

int uniquePathsWithObstacles(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;elsepathes[i][j] = pathes[i-1][j] + pathes[i][j-1];return pathes[m][n];
}

64 给定一个m*n矩阵，每个数字代表经过该处的耗费，找出一条耗费最小的路径

依然是动态规划

C++ 解答

int minPathSum(vector<vector<int>>& grid) {// if modifying the grid is disallowed, copy itint 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;else if (i == 0 && j != 0)grid[i][j] += grid[i][j-1];else if (i != 0 && j == 0)grid[i][j] += grid[i-1][j];elsegrid[i][j] += min(grid[i-1][j], grid[i][j-1]);return grid[m-1][n-1];
}

65 判定一个字符串是否是合法的数字，包括了正负号，小数点，e等

一些例子：

"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

这道题就是细节题，用 C 处理字符串太蛋疼了，直接上 Python 了

Python 解答

def isNumber(self, s):BEFORE = 0 # before dotAFTER = 1 # after dotEXP = 2 # after ephase = BEFOREallow_sign = Trues = s.strip()if not any([c.isdigit() for c in s]):return Falseif s == '' or s[0] == 'e' or s[-1] == 'e' or s == '.':return Falseif s[0] == '.' and s[1] == 'e':return Falseif s[0] == '-' and s[1] == 'e':return Falsefor c in s:if '0' <= c <= '9':allow_sign = Falseelif c == '.':allow_sign = Falseif phase == EXP or phase == AFTER:return Falseelse:phase = AFTERelif c == 'e':if phase == EXP:return Falseallow_sign = Truephase = EXPelif c == '-' or c == '+':if not allow_sign:return Falseallow_sign = Falseelse:return Falseif phase == EXP:return s[-1].isdigit()return True

66 给定一个字符串代表的数字，返回加 1 后的数字

乍一看如果需要进位的话，可能需要拷贝整个数组。实际上并不需要，我们知道只有当数字是 999…999 的时候，才会使得数字的长度 +1 变为 1000…000。

C++ 解答

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...999digits[0] = 1;digits.push_back(0);return digits;
}

Rust 解答

impl Solution {pub fn plus_one(mut digits: Vec<i32>) -> Vec<i32> {for i in (0..digits.len()).rev() {match digits[i] {9 => digits[i] = 0,_ => {digits[i] += 1; return digits}}}digits[0] = 1;digits.push(0);digits}
}

67 给定两个字符串代表的二进制数字，返回他们相加的和

和上一题一样，按照加法定义做就好了

C 解答

#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 nullmemset(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++ 解答

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 解答

int mySqrt(int x) {if (x <= 1) return x;const double EPS = x * 0.0001;double y = x / 2; // initial guesswhile (fabs(y * y - x) > EPS) {y = (y + x / y) / 2;}long z = (long) y;while (z * z > x) z--;return z;
}

70 爬梯子，一次可以爬一步或者两步，有几种方法爬完梯子

斐波那契数列，也可以理解为动态规划

C 解答

int climbStairs(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++ 解答

string simplifyPath(string& path) {vector<string> dirs;stringstream ss(path);string dir;while (getline(ss, dir, '/')) {if (dir == "." || dir == "")continue;else if (dir == "..") {if (!dirs.empty())dirs.pop_back();} elsedirs.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

那么：

1. 相等 f[i][j] = f[i-1][j-1];

2. 不相等

   1. 替换：f[i][j] = f[i-1][j-1] + 1; 都向前一步
   2. 添加：f[i][j] = f[i][j-1] + 1; word2 向前一步
   3. 删除：f[i][j] = f[i-1][j] + 1; word1 向前一步

另外使用一维数组表示二维数组还需要了解

C++ 解答

// unoptimized code
int minDistance(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];
}

C++ 解答

// optimized
int minDistance(string word1, string word2) {int m = word1.length(), n = word2.length();vector<int> cur(m + 1, 0);// 把剩余的字符删掉的距离for (int i = 1; i <= m; i++)cur[i] = i;for (int j = 1; j <= n; j++) {int pre = cur[0];cur[0] = j;for (int i = 1; i <= m; i++) {int temp = cur[i];if (word1[i - 1] == word2[j - 1])cur[i] = pre;else cur[i] = min(pre + 1, min(cur[i] + 1, cur[i - 1] + 1));pre = temp;}}return cur[m];
}

C++ 解答

// recursive code from beauty of programming
// TLE on LeetCode
int minDistance(string word1, string word2) {return minDistance(&word1.front(), &word1.back(), &word2.front(), &word2.back())
}int minDistance(char* start1, char* end1, char* start2, char* end2) {if (start1 > end1)return start2 > end2 ? 0 : end2 - start2 + 1;if (start2 > end2)return start1 > end1 ? 0 : end1 - start1 + 1;if (*start1 == *start2)return minDistance(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);return min(t1, min(t2, t3)) + 1;}
}

73 给定一个矩阵，如果某个元素为零，把所在的行和所在的列都设为零

一种可以接受的方法是使用 O(m+n) 的空间，记录哪行哪列需要设为零

C++ 解答

void setZeroes(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++ 解答

bool searchMatrix(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;else if (matrix[mid/col][mid%col] == target)return true;elseright = mid - 1;}return false;
}

75 颜色排序，每个物体有颜色属性，把他们按照 RGB 的顺序排序 (🇳🇱国旗问题）

一种方法是简单地 2 pass 解法，遍历一遍计数再输出。另一种方法是把红色往前交换，蓝色往后交换

C 解答

void swap(int* a, int* b) {int t = *a; *a = *b; *b = t;
}void sortColors(int* nums, int numsSize) {const int 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++]);}
}

76 跳过

77 给定数字 n 和 k，生成从 n 中取出 k 个数字的所有情况

数学上的组合，使用回溯来做，对状态空间进行深度搜索。

回溯方法通常适合对状态空间树的深度优先搜索相结合的，当一个解已经不满足条件时，剪枝；
如果满足条件，直到找到完全解未知。

C++ 解答

// 组合是不要求顺序的
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;
}void combine(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 种解法：

1. DFS，我们知道对于 n 个元素的集合，有 2^n 个子集，通过每个元素在不在子集中构造一个状态空间树
2. 类似于电话键盘生成字母，迭代
3. 巧妙的利用 1…2^n 对应

C++ 解答

// use backtracking and do a dfs searchvector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> result;if (nums.empty()) return result;sort(nums.begin(), nums.end());vector<int> temp;subsets(nums, result, temp, 0);return result;
}// for each solution, the can be divided into two sub solutions: in or out
void subsets(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++ 解答

// 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 sizefor (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++ 解答

// 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;
}

79 给定一个二维字符数组，查找一个单词是否能够有连续的字母构成，不能交叉

也是深度优先的做法，首先找到开始的字母，然后依次向上下左右查找，注意还需要统计有没有访问过

C++ 解答

bool exist(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;
}bool findNext(vector<vector<char>>& board, string& word, vector<vector<bool>>& visited, int m, int n, int i) {if (i == word.size())return true;if (m >= board.size() || n >= board[0].size() || m < 0 || n < 0|| visited[m][n] || board[m][n] != word[i])return false;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 解答

int removeDuplicates(int* nums, int numsSize) {if (!nums || numsSize < 1) return 0;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;
}

81 在被翻转的数组中查找元素，可能包含重复元素

经典题目，还是一个二分查找问题，只是要分很多种情况

C 解答

bool search(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)return true; //return m in Search in Rotated Array Iif (A[left] < A[mid]) { //left half is sortedif (A[left] <= key && key < A[mid])right = mid - 1;elseleft = mid + 1;} else if (A[left] > A[mid]) { //right half is sortedif (A[mid] < key && key <= A[right])left = mid + 1;elseright = mid - 1;} else { // A[left] == A[mid]left++;}}return false;
}

82 从已经排序的链表中删除所有重复过的元素，只留下只出现一次的元素

考察链表操作

C 解答

struct ListNode* deleteDuplicates(struct ListNode* head) {struct ListNode dummy, *p = &dummy;dummy.next = head;while (p && p->next && p->next->next) {if (p->next->val == p->next->next->val) {struct ListNode* distinct = p->next;int dup = p->next->val;while (distinct && distinct->val == dup) {distinct = distinct->next; // TODO: fix mem leak}p->next = distinct;} else {p=p->next;}}return dummy.next;
}

83 从已经排序的链表中删除所有重复过的元素，但是重复过的也留下一个，即，使新链表不重复

同样是考察链表基本操作

C 解答

struct ListNode* deleteDuplicates(struct ListNode* head) {struct ListNode dummy, *p = &dummy; dummy.next = head; dummy.val = head->val + 1;while (p && p->next) {if (p->val == p->next->val) {int dup = p->val;while (p->next && p->next->val == dup)p->next = p->next->next; // TODO: fix mem leak} elsep = p->next;}return dummy.next;
}

84 在柱状图中查找最大的矩形

见注释

C++ 解答

int largestRectangleArea(vector<int>& height) {stack<int> stk;height.push_back(0); // dummy endint result  =0;// 总结，对于需要查找上一次最大元素的问题，可以考虑使用栈存储for (int i = 0; i < height.size(); ) {// 当遇到更高的柱子时候，先存入堆栈if (stk.empty() || height[i] > height[stk.top()]) // meet higherstk.push(i++);// 当遇到低一些的柱子时候，计算这些柱子到上一个更矮的柱子之间的最大举行，如果已经清空，说明之前所有柱子都更低else { // lowerint h = stk.top();stk.pop();result = max(result, height[h] * (stk.empty() ? i : i - stk.top() -1));}}return result;
}

85 最大的长方形

C 解答

int max(int a, int b) {return a > b ? a : b;
}int min(int a, int b) {return a < b ? a : b;
}int maximalRectangle(char** matrix, int row, int col) {if (!matrix) return 0;int left[col], right[col], height[col];for (int i = 0; i < col; i++)left[i] = 0, right[i] = col, height[i] = 0;int area = 0;for (int i = 0; i < row; i++) {int cur_left = 0, cur_right = col;for (int j = 0; j < col; j++)if (matrix[i][j] == '1')  // 在第 j 列的高度height[j]++;elseheight[j] = 0;for (int j = 0; j < col; j++)if (matrix[i][j] == '1')left[j] = max(left[j], cur_left);elseleft[j] = 0, cur_left = j + 1;for (int j = col - 1; j >= 0; j--)if (matrix[i][j] == '1')right[j] = min(right[j], cur_right);elseright[j] = col, cur_right = j;for (int j = 0; j < col; j++)area = max(area, (right[j] - left[j]) * height[j]);}return area;
}

86 链表分区，要求把小于某个值得元素全都放到前面

对于链表这道题很简单，分两个列表在合并就好了，问题是当我们处理类似的数组问题时，也有一种巧妙地 O(n) 的解法

C 解答

struct ListNode* partition(struct ListNode* head, int x) {struct ListNode small, *psmall = &small; // double dummy headstruct ListNode big, *pbig = &big;psmall->next = pbig->next = NULL;while (head != NULL) {if (head->val < x) {psmall->next = head;psmall = psmall->next;} else {pbig->next = head;pbig = pbig->next;}head = head->next;}psmall->next = big.next;pbig->next = NULL;return small.next;
}

87 把字符串分区后，交换得到的字符串

C++ 解答

bool isScramble(string s1, string s2) {if(s1==s2)return true;// 先判断字符是否一致int len = s1.size();int count[26] = {0};for(int i=0; i<len; i++) {count[s1[i]-'a']++;count[s2[i]-'a']--;}for(int i = 0; i < 26; i++)if(count[i]!=0)return false;for(int i = 1; i < len; i++) {if( isScramble(s1.substr(0,i), s2.substr(0,i)) && isScramble(s1.substr(i), s2.substr(i)))return true;if( isScramble(s1.substr(0,i), s2.substr(len-i)) && isScramble(s1.substr(i), s2.substr(0,len-i)))return true;}return false;
}

88 合并已排序数组，要求合并到其中一个空间较大的数组中

对于这种要求 in-place 的算法，从后往前往往可以解决

C 解答

void merge(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++ 解答

vector<int> grayCode(int n) {vector<int> v;for (int i = 0; i < (1 << n); i++) {v.push_back((i >> 1) ^ i);}return v;
}

90 由给定元素生成子集，可能包含重复元素

使用了和手机键盘生成字符串号码类似的迭代算法，注意其中对重复元素的处理，当然也可以用 DFS 来做

C++ 解答

vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<vector<int>> sets;sets.push_back({});sort(nums.begin(), nums.end()); // 处理包含重复元素的一半需要预排序for (int i = 0; i < nums.size(); ) {int count = 0; // dup countwhile (count + i < nums.size() && nums[count+i] == nums[i])count++;int prev_n = sets.size();for (int j = 0; j < prev_n; j++) {vector<int> instance = sets[j];// put dup element `count` timesfor (int k = 0; k < count; k++) {instance.push_back(nums[i]);sets.push_back(instance);}}i += count;}return sets;
}

91 给定一个数组只包含 1-9，可以用 1-26 代表字母，求出从其中能都得到多少字符串

使用动态规划，但是注意其中 0 的处理，很玄妙

C 解答

int numDecodings(char* s) {if (!s || strlen(s) == 0 || s[0] == '0') return 0;int r1 = 1, r2 = 1; // r1: 前一个字符， r2：前两个字符char* p = s++; // 上一个字符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 解答

struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {if (m == n) return head;struct ListNode dummy, *p = &dummy, * small_node, * big_node; // actually the prev onesdummy.next = head;n -= m;while (--m) // m starts from 1, so not m--p = p->next;struct ListNode* start = p->next;while (n--) {struct ListNode* next = start->next;start->next = next->next;next->next = p->next;p->next = next;}return dummy.next;
}

93 恢复 IP 地址，给定一个字符串，适当插入点，一共有多少种方式构成 IP 地址

又是一道 DFS 的题，注意对于字符串问题如何处理

C++ 解答

vector<string> restoreIpAddresses(string s) {vector<string> result;restore(result, s, "", 0, 0);return result;
}void restore(vector<string>& result, string& s, string restored, int start, int dots) {if (dots > 4) return;if (dots == 4 && start == s.size())result.push_back(restored);for (int i = 1; i < 4; i++) {if (start + i > s.size())break;string part = s.substr(start, i);if (part[0] == '0' && part.size() > 1 || i == 3 && stoi(part) > 255)continue;restore(result, s, restored + part + (dots==3 ? "" : "."), start + i, dots + 1);}
}

94 中序遍历二叉树

当然是使用栈了

C++ 解答

vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> stk;TreeNode* current = root;while (!stk.empty() || current) {if (current) {stk.push(current);current = current->left;} else {current = stk.top();stk.pop();result.push_back(current->val);current = current->right;}}return result;
}

递归解法

go 解答

func inorderTraversal(root *TreeNode) []int {if root == nil {return nil}left := inorderTraversal(root.Left)right := inorderTraversal(root.Right)return append(append(left, root.Val), right...)
}

95 生成二叉树，同下题一样

C++ 解答

vector<TreeNode*> generateTrees(int n) {return gen(1, n);
}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 = new TreeNode(i);root->left = l;root->right = r;result.push_back(root);}}}return result;
}

96 给定数字 n，从 1 到 n 作为节点有多少种方式生成二叉树

这道题看似是树，实际上是一个动态规划问题。

C 解答

int numTrees(int n) {if (n == 0) return 0;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];
}

97 给定两个字符串交叉是否能够构成第三个字符串

这道题是一道二维的 DP 问题，因为需要对于每个字符串的每个位置用另一个字符串尝试匹配

C 解答

bool isInterleave(char* s1, char* s2, char* s3) {int l1 = strlen(s1), l2 = strlen(s2), l3 = strlen(s3);if (l1 + l2 != l3) return false;// 在 i+j 位置 s1[i] s2[j] 是否能够构成 s[i+j]bool** dp = malloc(sizeof(bool*) * (l1 + 1));for (int i = 0; i <= l1; i++)dp[i] = malloc(sizeof(bool) * (l2 + 1));for (int i = 0; i <= l1; i++)for (int j = 0; j <= l2; j++)if (i == 0 && j == 0)dp[i][j] = true;else if (i == 0)dp[i][j] = (dp[i][j-1] && s2[j-1] == s3[i+j-1]); // 注意：赋值的优先级更高else if (j == 0)dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1]);elsedp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1] || dp[i][j-1] && s2[j-1] == s3[i+j-1]);return dp[l1][l2];
}

98 验证二叉搜索树是否合法

先序遍历即可

C 解答

bool valid(struct TreeNode* root, long left, long right) {return root == NULL || root->val > left && root->val < right &&valid(root->left, left, root->val) &&valid(root->right, root->val, right);
}bool isValidBST(struct TreeNode* root) {return valid(root, INT_MIN - 1l, INT_MAX + 1l);
}

99 在二叉搜索树中有两个节点被调换了，找出这两个节点，并恢复该二叉树

C 解答

struct TreeNode* prev = NULL;
struct TreeNode* first = NULL;
struct TreeNode* second = NULL;void traverse(struct TreeNode* root) {if (!root) return;traverse(root->left);if (prev && prev->val > root->val) {if (!first) first = prev;second = root;}prev = root;traverse(root->right);
}void recoverTree(struct TreeNode* root) {prev = first = second = NULL;traverse(root);if (!first) return;int temp = first->val;first->val = second->val;second->val = temp;
}

100 判断是否是相同的树

C 解答

bool isSameTree(struct TreeNode *p, struct TreeNode *q) {if (p == NULL || q == NULL) {return p == q;} else {return p->val == q->val&& isSameTree(p->left, q->left)&& isSameTree(p->right, q->right);}
}

101 判断是不是左右对称的树

C 解答

bool sym(struct TreeNode* left, struct TreeNode* right) {if (left && !right || !left && right)return false;return !left && !right ||left->val == right->val &&sym(left->left, right->right) &&sym(right->left, left->right);
}bool isSymmetric(struct TreeNode* root) {if (!root) return true;return sym(root->left, root->right);
}

102 二叉树层序遍历

C++ 解答

vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;if (!root) return result;vector<TreeNode*> current, next;current.push_back(root);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);}result.push_back(vals);current = next;}return result;
}

103 二叉树 ZigZag 层序遍历

这道题更好的做法是使用一个栈，从而使得每行的顺序都是上一行的翻转

C++ 解答

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 解答

int maxDepth(struct TreeNode* root) {if (!root) return 0;int left = maxDepth(root->left), right = maxDepth(root->right);return (left > right ?left : right) + 1;
}

105 从前序遍历和中序遍历生成生二叉树

C 解答

struct TreeNode* build(int* prestart, int* preend, int* instart, int* inend) {struct TreeNode* root = malloc(sizeof(struct TreeNode));root->val = *prestart;root->left = root->right = NULL;if (prestart == preend)return root;int* root_inorder = instart;while (root_inorder <= inend && *root_inorder != *prestart)root_inorder++;int left_len = root_inorder - instart;int right_len = inend - root_inorder;if (left_len > 0)root->left = build(prestart + 1, prestart + left_len, instart, root_inorder - 1);if (right_len > 0)root->right = build(prestart + left_len + 1, preend, root_inorder + 1, inend);return root;
}
// m always equals n, otherwise it's bad input
struct TreeNode* buildTree(int* preorder, int m, int* inorder, int n) {if (n==0) return NULL;return build(preorder, preorder + n - 1, inorder, inorder + n - 1);
}

106 从中序遍历和后序遍历生成二叉树

C 解答

struct TreeNode* build(int* instart, int* inend, int* poststart, int* postend) {struct TreeNode* root = malloc(sizeof(struct TreeNode));root->val = *postend;root->left = root->right = NULL;if (poststart == postend)return root;int* root_inorder = instart;while (root_inorder <= inend && *root_inorder != *postend)root_inorder++;int left_len = root_inorder - instart;int right_len = inend - root_inorder;if (left_len > 0)root->left = build(instart, root_inorder - 1, poststart, poststart + left_len - 1);if (right_len > 0)root->right = build(root_inorder + 1, inend, poststart + left_len, postend - 1);return root;
}
struct TreeNode* buildTree(int* inorder, int m, int* postorder, int n) {if (n == 0) return NULL;return build(inorder, inorder + n - 1, postorder, postorder +n - 1);
}

107 二叉树层序遍历，但要生成翻转的遍历序列

C++ 解答

vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> result;if (!root) return result;vector<TreeNode*> current, next;current.push_back(root);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);}result.push_back(vals);current = next;}reverse(result.begin(), result.end());return result;
}

108 把排序数组转化为二叉树

C 解答

 struct TreeNode* bst(int* left, int* right) {int* mid = left + (right - left) / 2;struct TreeNode* root = malloc(sizeof(struct TreeNode));root->val = *mid;root->left = root->right = NULL;if (left < mid)root->left = bst(left, mid-1);if (mid < right)root->right = bst(mid+1, right);return root;
}
struct TreeNode* sortedArrayToBST(int* nums, int n) {if (n == 0) return NULL;return bst(nums, nums + n -1);
}

109 把排序列表转化为二叉树

C 解答

struct ListNode* list;
int len(struct ListNode* head) {int l = 0;while (head)head = head->next, l++;return l;
}struct TreeNode* bst(int n) {if (n == 0) return NULL;struct TreeNode* 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) return 0;list = head;return bst(len(head));
}

110 平衡二叉树

C 解答

int height(struct TreeNode* root) {if (!root) return 0;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;
}
bool isBalanced(struct TreeNode* root) {return height(root) != -1;
}

111 二叉树最小高度

C 解答

int minDepth(struct TreeNode* root) {if (!root) return 0;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 解答

bool hasPathSum(struct TreeNode* root, int sum) {if (!root) return false;if (!root->left && !root->right) return sum == root->val;return hasPathSum(root->left, sum - root->val) ||hasPathSum(root->right, sum - root->val);
}

113 接上题，把这个路径找出来

C++ 解答

vector<vector<int>> pathSum(TreeNode* root, int sum) {vector<vector<int>> result;vector<int> path;getPaths(result, path, root, sum);return result;
}void getPaths(vector<vector<int>>& result, vector<int> path, TreeNode* root, int sum) {if (!root)return;path.push_back(root->val);if (!root->left && !root->right && sum == root->val) {result.push_back(path);return;}getPaths(result, path, root->left, sum - root->val);getPaths(result, path, root->right, sum - root->val);
}

114 把二叉树扁平成列表

C++ 解答

TreeNode* prev;
void flatten(TreeNode* root) {if (!root) return;flatten(root->right);flatten(root->left);root->right = prev;root->left = NULL;prev = root; // last flattened element
}

115 通过删掉一些字母得到子序列，问有多少种方法能够得到子序列呢

使用 DP，

C++ 解答

/*** 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.*/class Solution {
public:int numDistinct(string s, string t) {int m = t.size();int n = s.size();if (m > n)return 0;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++) // Sfor (int i = 1; i <= m; i++) // Tpath[i][j] = path[i][j-1] + (t[i-1] == s[j-1] ? path[i-1][j-1] : 0);return path[m][n];}
};

116 完全二叉树中把每个节点指向他这一层的右面的节点

显然左节点的下一个节点是父节点的右节点，右节点的下一个节点是父节点下一个节点的左节点。

C 解答

void connect(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);
}

117 同上题，但是是任意的🌲

通过上一层已经被连接的 next 指针，顺序层序访问，从而连接下一层。

C 解答

void connect(struct TreeLinkNode *root) {struct TreeLinkNode* head = root, * prev = NULL, *p = NULL;while (head) { // head 是每层的开始p = head;prev = head = NULL;while (p) {if (p->left) {if (prev)prev->next = p->left;elsehead = p->left;prev = p->left;}if (p->right) {if (prev)prev->next = p->right;elsehead = p->right;prev = p->right;}p = p->next;}}
}

118 杨辉三角

注意坐标关系，不要被骗了

C++ 解答

vector<vector<int>> generate(int n) {vector<vector<int>> result(n);for (int i = 0; i < n; i++) {result[i].resize(i+1);result[i][0] = result[i][i] = 1;for (int j = 1; j < i; j++)result[i][j] = result[i-1][j-1] + result[i-1][j];}return result;
}

119 返回杨辉三角的第 k 行

要求只能使用 O(k) 的额外空间，比较蛋疼的是这里的 k 是从 0 计数的。

C++ 解答

vector<int> getRow(int rowIndex) {rowIndex++;vector<int> row;for (int i = 0; i < rowIndex; i++) {vector<int> newRow(i+1);newRow[0] = newRow[i] = 1;for (int j = 1; j < i; j++)newRow[j] = row[j-1] + row[j];swap(row, newRow);}return row;
}

120 给定一个类似杨辉三角形状的数组，求从顶部到底部的最短路径

显然是使用 DP，但是有一个问题，如果是 top down 的话，最后还需要遍历一下，而如果是 bottom up 就只需要返回 dp[0] 就好了。

C++ 解答

int minimumTotal(vector<vector<int>>& triangle) {vector<int> dp(triangle.back()); // 复制最后一行for (int layer = triangle.size() - 2; layer >= 0; layer--)for (int i = 0; i <= layer; i++)dp[i] = triangle[layer][i] + min(dp[i], dp[i+1]);return dp[0];
}

121 买卖股票最佳时机，只能交易一次

C 解答

int maxProfit(int* prices, int pricesSize) {if (pricesSize < 2) return 0;int profit = 0;int min = prices[0];// 从前到后依次遍历，如果有更好的收益更新，或者更新 min，限制条件是先出现最小值for (int i = 0; i < pricesSize; i++) {if (prices[i] > min) {profit = max(profit, prices[i] - min);} else {min = prices[i];}}return profit;
}

122 买卖股票的最佳时机，可以做任意多比交易

有两种解法，一种是不断做交易，完全不考虑交易次数，这种做法不符合实际情况。
另一种做法是模拟交易，这样会生成最少的交易次数，结果也是对的。

C 解答

// 1
int maxProfit(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];return total;
}

C 解答

// 2
int maxProfit(int* prices, int pricesSize) {if (!prices) return 0;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;}}return profit;}

123 股票交易，限制只能交易两股

每次求解的是：卖出两股以后的最大值，刚刚买入第二股的最大值，卖出第一股时候的最大值，买入第一股时候的最大值。

C++ 解答

int maxProfit(vector<int>& prices) {int hold1 = INT_MIN, hold2 = INT_MIN;int release1 = 0, release2 = 0;for (auto i : prices) {release2 = max(release2, hold2 + i);hold2 = max(hold2, release1 - i);release1 = max(release1, hold1 + i);hold1 = max(hold1, -i);}return release2;
}

124 二叉树路径最大和，路径可以从任意一个节点开始到任意一个节点结束

C 解答

int max(int a, int b) {return a > b ? a : b;
}int doSum(struct TreeNode* root, int* sum) {if (!root)return 0;int left = max(0, doSum(root->left, sum));int right = max(0, doSum(root->right, sum));*sum = max(*sum, left+right+root->val);return max(left, right) + root->val;
}int maxPathSum(struct TreeNode* root) {int sum = INT_MIN;doSum(root, &sum);return sum;
}

这道题是把最终答案放在了全局变量中，并采用了辅助函数的方法。全局变量中存储两条路径的和，
而返回值中存储当前子树中最长的单边。

Python 解答

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def __init__(self):self.ans = float('-inf')def _maxPathSum(self, root: TreeNode) -> int:if root is None:return 0# 注意这里要取 max，以防添加了负路径left = max(0, self._maxPathSum(root.left))right = max(0, self._maxPathSum(root.right))self.ans = max(self.ans, left + right + root.val)return max(left, right) + root.valdef maxPathSum(self, root: TreeNode) -> int:self._maxPathSum(root)return self.ans

125 给定一个字符串，只考虑字母和数字，忽略大小写，判断是否是回文字符串

太简单了，没啥可说的

C 解答

bool isPalindrome(char* s) {int len = strlen(s);if (len == 0) return true;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))return false;left++, right--;} else {if (!isalnum(l))left++;if (!isalnum(r))right--;}}return true;
}

127 单词梯子

给定梯子，和开始单词和结束单词，最少需要多少个中间单词，才能变化过去，每次只能变化一个字母

C++ 解答

int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {unordered_set<string> beginSet, endSet, *set1, * set2;beginSet.insert(beginWord);endSet.insert(endWord);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 refwordList.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);}return 0;
}

128 最长递增子序列

使用动态规划

C++ 解答

int longestConsecutive(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 解答

int sum(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;
}int sumNumbers(struct TreeNode* root) {if (!root) return 0;return sum(root, 0);
}

130 把所有被包围的 O 置为 X

使用并查集

C++ 解答

class UnionFind {
private:vector<int> m_father, m_rank;
public:UnionFind(int n): m_father(n), m_rank(n, 0) {for (int i = 0; i < m_father.size(); i++)m_father[i] = i;}int find(int x) {if (x != m_father[x])m_father[x] = find(m_father[x]);return m_father[x];}void unionify(int x, int y) {x = find(x);y = find(y);if (x == y) return;if (m_rank[x] > m_rank[y]) {m_father[y] = x;} else {if (m_rank[x] == m_rank[y])m_rank[y]++;m_father[x] = y;}}
};class Solution {
public:void solve(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);else if (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';}
};

131 对字符串分组，是的每个字串都是回文，返回所有可能的分组

C++ 解答

vector<vector<string>> partition(string s) {vector<vector<string>> result;vector<string> group;dfs(result, s, group, 0);return result;
}void dfs(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();}}
}bool isPalindrome(const string& s, int left, int right) {while (left < right) {if (s[left++] != s[right--])return false;}return true;
}

132 如上题，找出最少需要分组几次

C++ 解答

int minCut(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++ 解答

unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> hash; // old -> new pair
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {if (!node)return NULL;if (hash.find(node) == hash.end()) {hash[node] = new UndirectedGraphNode(node->label);for (auto n : node->neighbors)hash[node]->neighbors.push_back(cloneGraph(n));}return hash[node];
}

134 加油站

C 解答

int canCompleteCircuit(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; // 同时重新开始计数}}return total >= 0 ? j + 1 : -1;
}

135 糖块，成绩高的需要比他身边成绩低的获得更多的糖

C++ 解答

int candy(vector<int>& ratings) {int n = ratings.size();if (n <= 1)return n;vector<int> candies(n, 1);for (int i =1; i < n; i++)if (ratings[i] > ratings[i-1])candies[i] = candies[i-1] + 1;for (int i = n - 1; i > 0; i--)if (ratings[i-1] > ratings[i])candies[i-1] = max(candies[i] + 1, candies[i-1]);int result = 0;for (auto i : candies)result += i;return result;
}

136 找出数组中只出现一次的数字

C 解答

int singleNumber(int* nums, int numsSize) {int result = nums[0];for (int i = 1; i < numsSize; i++)result ^= nums[i];return result;
}

137 一个数组中，所有数字都出现三次，除了一个数字以外，找出这个数字

C 解答

// 使用二进制计算
// 00->10->01->00(0->1->2->3/0)
// ones = ones ^ A[i]; if (twos == 1) then ones = 0
// twos = twos ^ A[i]; if (ones* == 1) then twos = 0int singleNumber(int* nums, int numsSize) {int ones = 0, twos = 0;for (int i = 0; i < numsSize; i++) {ones = (ones ^ nums[i]) & ~twos;twos = (twos ^ nums[i]) & ~ones;}return ones;
}

138 复制复杂结构链表

C 解答

/*** Definition for singly-linked list with a random pointer.* struct RandomListNode {*     int label;*     struct RandomListNode *next;*     struct RandomListNode *random;* };*/
struct RandomListNode *copyRandomList(struct RandomListNode *head) {struct RandomListNode* p;p = head;while (p) {struct RandomListNode* node = malloc(sizeof(struct RandomListNode));node->next = node->random = NULL; // spicial notice to struct initialization in cnode->label = p->label;node->next = p->next;p->next = node;p = node->next;}p = head;while (p) {if (p->random)p->next->random = p->random->next;p = p->next->next;}struct RandomListNode dummy, *q = &dummy;dummy.next = dummy.random = NULL;p = head;while (p) {q->next = p->next;q = q->next;p->next = p->next->next;p = p->next;}return dummy.next;
}

139 查找单词是否能组成句子

C++ 解答

bool wordBreak(string s, unordered_set<string>& wordDict) {if (wordDict.empty()) return false;vector<bool> dp(s.size() + 1, false);dp[0] = true;// 动态规划，假设前 i 个字符已经匹配到了，尝试匹配 i 到 i+j，如果找到了，就匹配到了 i+jfor (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 解答

bool hasCycle(struct ListNode *head) {struct ListNode* slow = head, * fast = head;while (fast && fast->next && fast->next->next) {fast = fast->next->next;slow = slow->next;if (slow == fast)return true;}return false;
}

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，所以两个指针分别从开始和碰撞点出发匀速一定会在环的入口相遇。

C 解答

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow = head, * fast = head, *entry = NULL;bool found = false;while (!found && fast && fast->next && fast->next->next) {fast = fast->next->next;slow = slow->next;if (slow == fast)found = true;}if (!found) return NULL;slow = head;while (slow != fast) {slow = slow->next;fast = fast->next;}return slow;
}

144 前序遍历

C++ 解答

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);}return result;}

145 二叉树的后序遍历

参见树的遍历

C++ 解答

vector<int> postorderTraversal(TreeNode* root) {vector<int> result;if (!root) return result;stack<TreeNode*> stk, output;stk.push(root);while (!stk.empty()) {auto node = stk.top();stk.pop();output.push(node);if (node->left)stk.push(node->left);if (node->right)stk.push(node->right);}while (!output.empty()) {result.push_back(output.top()->val);output.pop();}return result;
}

146 LRU 缓存

C++ 解答

class LRUCache{
public:
typedef unordered_map<int, pair<int, list<int>::iterator>> cache_t; // k: v, iterLRUCache(int capacity) : m_capacity(capacity) {}int get(int key) {auto it = m_cache.find(key);if (it == m_cache.end())return -1;touch(it);return it->second.first;}void set(int key, int value) {auto it = m_cache.find(key);if (it != m_cache.end()) {touch(it);} else {if (m_cache.size() == m_capacity) {m_cache.erase(m_used.back());m_used.pop_back();}m_used.push_front(key);}m_cache[key] = {value, m_used.begin()};}
private:void touch(cache_t::iterator it) {int key = it->first;m_used.erase(it->second.second);m_used.push_front(key);it->second.second = m_used.begin();}cache_t m_cache;list<int> m_used;int m_capacity;
};

147 链表插入排序

C 解答

struct ListNode* insertionSortList(struct ListNode* head) {if (!head) return NULL;struct ListNode dummy, *p = head;dummy.val = INT_MIN;dummy.next = NULL;while (p) {struct ListNode* iter = &dummy;while (iter->next && iter->next->val < p->val)iter = iter->next;struct ListNode* pnext = p->next;p->next = iter->next;iter->next = p;p = pnext;}return dummy.next;
}

148 排序链表，要求达到 O(nlogn) 时间复杂度

C 解答

void split(struct ListNode* source, struct ListNode** frontptr, struct ListNode** backptr) {struct ListNode* fast, * slow;if (!source || !source->next)*backptr = source;else {slow = source;fast = source->next;while (fast && fast->next) {fast = fast->next->next;slow = slow->next;}*backptr = slow->next;slow->next = NULL;}*frontptr = source;
}struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {if (l1 == NULL) return l2;if (l2 == NULL) return l1;struct ListNode dummy;dummy.next == NULL;struct ListNode* p = &dummy;while (l1 && l2) {if (l1->val < l2->val) {p->next = l1;l1 = l1->next;} else {p->next = l2;l2 = l2->next;}p = p->next;}if (l1)p->next = l1;if (l2)p->next = l2;return dummy.next;
}// merge sort
struct ListNode* sortList(struct ListNode* head) {struct ListNode* front, * back;if (!head || !head->next) return head;split(head, &front, &back);front = sortList(front);back = sortList(back);head = merge(front, back);return head;
}

149 在同一条线上的点最多的线

C++ 解答

int maxPoints(vector<Point>& points) {if (points.size() < 2) return points.size();int result = 0;// 对于每一个点for (int i = 0; i < points.size(); i++) {// 经过该点的直线，使用分数作为斜率，避免使用浮点数map<pair<int, int>, int> lines;int localMax = 0, overlap = 0;for (int j = i + 1; j < points.size(); j++) { // 避免重复计算if (points[j].x == points[i].x && points[j].y == points[i].y) {overlap++; // 同一个点continue;} else {int x = points[j].x - points[i].x;int y = points[j].y - points[i].y;int g = gcd(x, y);x /= g, y /= g; // verticle case: x == 0 -> (0, 1)lines[make_pair(x, y)]++;localMax = max(localMax, lines[make_pair(x, y)]);}}// overlap 算在任意条线上result = max(result, localMax + overlap + 1);}return result;
}int gcd(int x, int y) {if (y == 0) return x;else return gcd(y, x % y);
}

150 后缀表达式求值

C++ 解答

bool is_operator(char t) {return t == '+' || t == '-' || t == '*' || t == '/';
}
int calc(int left, char op, int right) {switch(op) {case '+': return left + right;case '-': return left - right;case '*': return left * right;case '/': return left / right;}
}
int evalRPN(vector<string>& tokens) {stack<int> nums;for (auto& token : tokens) {if (is_operator(token[0]) && token.size() == 1) {char op = token[0];int right_num = nums.top();nums.pop();int left_num = nums.top();nums.pop();nums.push(calc(left_num, op, right_num));} else {nums.push(stoi(token));}}return nums.top();
}

151 反转句子中的单词顺序

一般面试的时候会假定没有多余字符的，解法是

C 解答

LeetCode 需要处理多余空格：

C 解答

void swap(char *a, char *b) {char tmp = *a; *a = *b; *b = tmp;
}void reverse(char* start, char* end) {while(start < end)swap(start++, end--);
}void trim(char* s) {char* fast, *slow;for (fast = s; *fast !='\0'; fast++) {if (isspace(*fast)) {while(isspace(*(fast + 1)) && *(fast + 1) != 0)fast++;if(*(fast+1) == 0)break;if(slow == s)continue;}swap(fast, slow++);}*slow = 0;
}void reverseWords(char *s) {int len = strlen(s);if (len == 0)return;trim(s);len = strlen(s);if (len == 0)return;reverse(s, s + len - 1);char* head = s, * tail =s ;while (*(tail + 1) != '\0') {tail = head;while (!isspace(*(tail + 1)) && *(tail + 1) != '\0')tail++;reverse(head, tail);}
}

152 最大子序列乘积

C 解答

int maxProduct(vector<int>& A) {int n = A.size();int r = A[0];for (int i = 1, imax = r, imin = r; i < n; i++) {if (A[i] < 0)swap(imax, imin);imax = max(A[i], imax * A[i]);imin = min(A[i], imin * A[i]);r = max(r, imax);}return r;
}

153 在旋转数组中查找最小值

C 解答

int findMin(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;else if (A[right] < A[mid])left = mid;elseright = mid;}return A[left] < A[right] ? A[left] : A[right];
}

154 在旋转数组中查找最小值，可能有重复

C 解答

int findMin(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;} else if (A[right] < A[mid]) {right = mid;} else {right--;}}return A[left];
}

155 设计一个栈，在普通栈的基础上支持 getmin 操作

解法 1: 使用额外的栈，每个值都记录一个当前最小值，浪费空间

解法 2: 也是使用额外的栈，但是惰性记录，只有当需要更新的时候才去记录

C++ 解答

class MinStack {
private:stack<int> m_stk;stack<int> m_min;
public:void push(int x) {if (x <= getMin())m_min.push(x);m_stk.push(x);}void pop() {if (m_stk.top() == getMin())m_min.pop();m_stk.pop();}int top() {return m_stk.top();}int getMin() {return m_min.empty() ? INT_MAX : m_min.top();}
};

156-159 Locked

160 求两个链表的交叉点

分析题目可知，如果有一个交叉点，那么在这之后的所有点都是交叉的。这里有一个非常巧妙
的做法。使用两个指针，如果到达结尾就指向另一个链表，会产生一下三种情况：

1. 如果交叉点前面的节点数目相同，显然会返回正确节点。
2. 如果不同假设 A 的节点为 a + c，B 的节点为 b + c，则在下一次遍历时：
   a + c + b == b + c + a，恰好到达相同部分的第一个顶点 C1
3. 如果两个列表不相交，那么经过 a + b, b + a 距离后，恰好都等于 NULL

C 解答

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {if (!headA || !headB) return NULL;struct ListNode *p1 = headA, *p2=headB;while (p1 != p2) {// 两个列表手尾相接，如果有一个点相同，一定会返回// a + c + b == b + c + a   --> C1// a + b == b + a    --> NULLp1 = p1 ? p1->next : headB;p2 = p2 ? p2->next : headA;}return p1;
}

161 Locked

162 找到极大值，给定一个数组，可能有多个极大值，找到任意一个即可，给定数组中 A[i] != A[i+1]

题目要求在对数时间内做出来，二分搜索，如果中间的数在左半部分，就向右找。

C 解答

int findPeakElement(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 summitleft = mid + 1;else                           // mid in right part of summitright= mid;}return left;
}

163 Locked

164 未排序数组中相差最大的两个数之间的差

根据抽屉原理，最大差不可能小于 (max - min) / (n - 1)。证明：如果小于，那么整个数组的大小就会小于 max - min。
因此我们把

165 比较版本号大小

C++ 解答

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 herereturn result;
}int compareVersion(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;}return 0;
}

166 分数生成小数

C++ 解答

string fractionToDecimal(long numerator, long denominator) {if (numerator == 0) return "0";string result;// 符号if (numerator < 0 ^ denominator < 0)result += "-";long n = abs(numerator), d = abs(denominator);// 整数部分result += to_string(n / d);if (n % d == 0) return result;// 小数部分result+= ".";unordered_map<int, int> map;for (long r = n % d; r != 0; r %= d) { // 模拟手工除法if (map.count(r) > 0) {result.insert(map[r], 1, '(');result += ")";break;}map[r] = result.size(); // 记录对应的位置，以便插入括号r *= 10; // 从上借位result += to_string(r / d);}return result;
}

167 Locked

168 生成 Excel 表格标题

注意 A 对应的是 1 而不是 0，而且数字也是从 1 开始的

C++ 解答

string convertToTitle(int n) {string title;while (n) {char c = (n-1) % 26 + 'A';n = (n-1) / 26;title = c + title;}return title;
}

169 给定一个数组，有一个数字的出现频率超过了一半，找出这个数字

非常经典的一道题，首先我们假设拿到的数字就是目标，并记录他出现的次数，如果下一个
数字和他不一样，那么我们减一，当次数为 0 的时候，我们知道这个数字在已经遍历过的数字
中出现小于一半了，这时候我们换下一个数字，最后剩下的一定是超过一半的数字。

C++ 解答

int majorityElement(vector<int>& nums) {int candidate, count = 0;for (auto i : nums) {if (count == 0 || candidate == i) {count++;candidate = i;} else {count--;}}return candidate;
}

170 Locked

171 Excel 标题转换为数字

同样，我们需要注意 A 对应的是 1，而不是 0

C 解答

int titleToNumber(char* s) {int result = 0;while (*s)result = result * 26 + *s++ - 'A' + 1;return result;
}

172 阶乘中能有几个 0

显然先算出阶乘数字是会溢出的，而有 0 的话，就是需要 10，也就是就需要 2 和 5，
显然 2 是比 5 多的。那么我们只要考虑 5 的个数就行了， 这时候需要注意，5/15 等是算一个 5，
而 25/75 包含了两个 5，所以我们计算的时候，数一遍包含 5 的（这时 25 等也被计算了），
然后再数一遍包含 25 的就像当于数了两次了。

C 解答

int trailingZeroes(int n) {if (n < 0)return -1;int fives = 0;for (int i = 5; n / i > 0; i *= 5)fives += n / i;return fives;
}

173 二叉树中序遍历迭代器

C 解答

class BSTIterator {
public:BSTIterator(TreeNode *root) {pushAll(root);}/** @return whether we have a next smallest number */bool hasNext() {return !m_stack.empty();}/** @return the next smallest number */int next() {TreeNode* temp = m_stack.top();m_stack.pop();pushAll(temp->right);return temp->val;}private:stack<TreeNode*> m_stack;void pushAll(TreeNode* root) {while (root) {m_stack.push(root);root = root->left;}}
};/*** Your BSTIterator will be called like this:* BSTIterator i = BSTIterator(root);* while (i.hasNext()) cout << i.next();*/

174 地下城游戏

王子在格子的左上角，需要到右下角去救公主，在过程中王子不能死掉，和机器人走路一样，使用动态规划

C++ 解答

int calculateMinimumHP(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++ 解答

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++ 解答

// 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 解答

void reverse(int* nums, int left, int right) {while (left < right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}}void rotate(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 解答

uint32_t reverseBits(uint32_t n) {uint32_t r = 0;int len = sizeof(n) * 8 - 1;while (len--) { // 31 times shiftr |= 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 解答

int hammingWeight(uint32_t n) {int count = 0;while (n) {n &= n - 1;count++;}return count;
}

还可以采用查表法，对于表我们可以预先构造，或者利用上一个方法生成，对于长度过大的，我们可以分块查表。

C 解答

#include <stdio.h>
#include <stdlib.h>int counts[16];int _get_count(n) {int count = 0;while (n) {n &= n-1;count++;}return count;
}int init_counts() {for (int i = 0; i < 16; i++)counts[i] = _get_count(i);
};int get_count(n) {int count = 0;while (n) {int index = n & 0xF;count += counts[index];n >>= 4;}return count;
}int main() {init_counts();for (int i = 0; i < 100; i++)printf("%d: %d\n", _get_count(i), get_count(i));return 0;
}

192-197 Missing

198 有一排房子，每个房子中都有一定财产，但是不能偷相邻的两个房子，求能偷到的最大值

使用 DP，对于每个房子，可以选择不偷或者前 i-1 个房子加上偷当前房子，即dp[i+1] = max(dp[i], dp[i-1] + A[i])

C 解答

int rob(int* nums, int numsSize) {if (!nums) return 0;// 因为不能相邻，所以可以从相隔一个的取值// 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;
}

199 从右边看二叉树的效果

C++ 解答

// 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;
}

200 找出小岛的数量

采用并查集，找到最后集合的数量

C++ 解答

class UnionFind {
private:vector<int> m_father, m_rank;int m_count; // sets count
public:UnionFind(int n): m_father(n), m_rank(n, 0), m_count(n) {for (int i = 0; i < m_father.size(); i++)m_father[i] = i;}int find(int x) {if (x != m_father[x])m_father[x] = find(m_father[x]);return m_father[x];}void unionify(int x, int y) {x = find(x);y = find(y);if (x == y) return;if (m_rank[x] > m_rank[y]) {m_father[y] = x;} else {if (m_rank[x] == m_rank[y])m_rank[y]++;m_father[x] = y;}m_count--;}int getCount() {return m_count;}
};class Solution {
const static char LAND = '1';
const static char WATER = '0';public:int numIslands(vector<vector<char>>& grid) {if (grid.empty() || grid[0].empty())return 0;int r = grid.size(), c = grid[0].size();UnionFind uf(r * c + 1); // extra element is for waterfor (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;}
};

python 解答

class UnionFind:def __init__(self, count):self.count = countself.parents = list(range(count))  # 初始化时 parent 指针指向自己self.ranks = [1] * count  # 记录每棵树的大小def union(self, p, q):"""把 p, q 两个节点连通起来"""p_root = self.find(p)q_root = self.find(q)if p_root == q_root:returnif self.ranks[p_root] > self.ranks[q_root]:self.parents[q_root] = p_rootelse:if self.ranks[p_root] == self.ranks[q_root]:self.ranks[q_root] += 1self.parents[p_root] = q_rootself.count -= 1def find(self, p):"""找到 p 节点的根节点"""while self.parents[p] != p:# 神奇的路径压缩self.parents[p] = self.parents[self.parents[p]]p = self.parents[p]return pdef is_connected(self, p, q):p_root = self.find(p)q_root = self.find(q)return p_root == q_rootclass Solution:def numIslands(self, grid: List[List[str]]) -> int:if not grid or not grid[0]:return 0m = len(grid)n = len(grid[0])uf = UnionFind(m * n + 1)for i in range(m):for j in range(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 解答

// 如果两个数不相等，一定是有不同的位，那么这一位一定为 0
int rangeBitwiseAnd(int m, int n) {int t = 0;while (m != n) {t++;m >>= 1;n >>= 1;}return m << t;
}

202 快乐数字，各位数字平方相加得到下一个数字，如果最后等于 1

没啥，一直算就可以了。

C++ 解答

bool isHappy(int n) {while (n > 6) {int next = 0;while (n) {next += (n%10) * (n%10);n /= 10;}n = next;}return n == 1;
}

203 删除链表中给定的值

C 解答

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode dummy, *p = &dummy;dummy.next = head;while (p) {if (p->next && p->next->val == val) { // not forward herestruct ListNode* next = p->next;p->next = next->next;free(next);} else {p = p->next;}}return dummy.next;
}

204 找出素数

什么筛子，忘了

C++ 解答

int countPrimes(int n) {vector<bool> primes(n, true);primes[0] = primes[1] = false;for (int i = 2; i * i < n; i++) // 注意，只到 sqrt(n)if (primes[i])for (int j = i * i; j < n; j += i) // 从 i * i 开始，因为 i* i-- 已经被杀过了primes[j] = false;int count = 0;for (int i = 2; i < n; i++)if (primes[i])count++;return count;
}

205 同构字符串，可以看作 word pattern 的简化

C 解答

bool isIsomorphic(char* s, char* t) {int ss[256] = { 0 };int ts[256] = { 0 };if (strlen(s) != strlen(t))return false;int i = 0;while (s[i]) {if (ss[s[i]] != ts[t[i]])return false;ss[s[i]] = ts[t[i]] = i + 1;i++;}return true;
}

206 反转链表

tags: #pointers

最最基础的指针操作题目了

Python 解答

class Solution:def reverseList(self, head: ListNode) -> ListNode:prev = Nonecurr = headwhile curr:next = curr.nextcurr.next = prevprev = currcurr = nextreturn prev  # 关键在这里

C 解答

struct ListNode* reverseList(struct ListNode* head) {if (!head || !head->next)return head;struct ListNode *p = NULL, *cur = head, *next;while (cur) {next = cur->next; // cachecur->next = p; // reverse pointingp = cur; // moves forwardscur = next;}return p;
}

C 解答

// recursive

207 标准的拓扑排序

给定边这种方法表示图也是醉了

C++ 解答

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { // next -> beforevector<unordered_set<int>> graph(numCourses); // 每条边和他的下一步，临接表for (auto& p : prerequisites)graph[p.second].insert(p.first);vector<int> d(numCourses, 0); // in degreefor (auto& nexts : graph)for (auto next : nexts)d[next]++;for (int i = 0; i < numCourses; i++) {int nondep; // in degree == 0for (nondep = 0; nondep < numCourses && d[nondep] != 0; nondep++);if (nondep == numCourses)return false;d[nondep] = -1; // removefor (auto next : graph[nondep]) // 所有下一步都 －1d[next]--;}return true;
}

208 实现前缀树

C++ 解答

class TrieNode {
public:static const int branchCount = 26;bool isWord;TrieNode* next[branchCount];// Initialize your data structure here.TrieNode() : isWord(false) {for (int i = 0; i < branchCount; i++)next[i] = NULL;}
};class Trie {
public:Trie() {root = new TrieNode();}// Inserts a word into the trie.void insert(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.bool search(string word) {TrieNode* location = root;for (auto& c : word) {location = location->next[c - 'a'];if (!location)return false;}return location->isWord;}// Returns if there is any word in the trie// that starts with the given prefix.bool startsWith(string prefix) {TrieNode* location = root;for (auto& c : prefix) {location = location->next[c - 'a'];if (!location)return false;}return true;}private:TrieNode* root;
};// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");

209 最短子数组使得和大于某个数

双指针，超过和之后再尝试从开始处减去元素

C++ 解答

int minSubArrayLen(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++];}}return len == INT_MAX? 0 : len;
}

210 Course Schedule II

BFS

C++ 解答

class Solution {
public:vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);vector<int> degrees = compute_indegree(graph);queue<int> zeros;for (int i = 0; i < numCourses; i++)if (!degrees[i]) zeros.push(i);vector<int> toposort;for (int i = 0; i < numCourses; i++) {if (zeros.empty()) return {};int zero = zeros.front();zeros.pop();toposort.push_back(zero);for (int neigh : graph[zero]) {if (!--degrees[neigh])zeros.push(neigh);}}return toposort;}
private:vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {vector<unordered_set<int>> graph(numCourses);for (auto pre : prerequisites)graph[pre.second].insert(pre.first);return graph;}vector<int> compute_indegree(vector<unordered_set<int>>& graph) {vector<int> degrees(graph.size(), 0);for (auto neighbors : graph)for (int neigh : neighbors)degrees[neigh]++;return degrees;}
};

211 添加和搜索字符串

C++ 解答

class TrieNode {
public:static const int branchCount = 26;bool isWord;TrieNode* next[branchCount];// Initialize your data structure here.TrieNode() : isWord(false) {for (int i = 0; i < branchCount; i++)next[i] = NULL;}
};class Trie {
public:Trie() {root = new TrieNode();}// Inserts a word into the trie.void insert(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.virtual bool search(string word) {TrieNode* location = root;for (auto& c : word) {location = location->next[c - 'a'];if (!location)return false;}return location->isWord;}// Returns if there is any word in the trie// that starts with the given prefix.bool startsWith(string prefix) {TrieNode* location = root;for (auto& c : prefix) {location = location->next[c - 'a'];if (!location)return false;}return true;}TrieNode* getRoot() {return root;}private:TrieNode* root;
};class WordDictionary : public Trie{public:WordDictionary() : Trie(){}// Adds a word into the data structure.void addWord(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.bool search(string word) override {return search(word.c_str(), getRoot());}bool search(const char* word, TrieNode* root) {TrieNode* run = root;for (int i = 0; word[i]; i++) {if (run && word[i] != '.')run = run->next[word[i] - 'a'];else if (run && word[i] == '.') {// skip checking this charTrieNode* tmp = run;for (int j = 0; j < 26; j++) {run = tmp->next[j];if (search(word + i + 1, run))return true;}}else break;}return run && run->isWord;}
};// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

212 单词搜索

Trie 结构见前面，注意要记录 visited，还有边界的问题，另外集合的使用

C++ 解答

class Solution {
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;}void find(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;}};

213 小偷偷环状数组

C 解答

int max(int a, int b) {return a > b ? a : b;
}int robNonCyclic(int* nums, int numsSize) {if (!nums) return 0;// 因为不能相邻，所以可以从相隔一个的取值// 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;
}int rob(int* nums, int numsSize) {return max(robNonCyclic(nums, numsSize - 1), robNonCyclic(nums + 1, numsSize - 1));
}

214 最短回文字符串，给指定的字符串添加字母获得回文

C++ 解答

// based on kmp next array
string shortestPalindrome(string s) {string rev_s = s;reverse(rev_s.begin(), rev_s.end());string l = s + "#" + rev_s;vector<int> p(l.size(), 0);for (int i = 1; i < l.size(); i++) {int j = p[i - 1];while (j > 0 && l[i] != l[j])j = p[j - 1];p[i] = (j += l[i] == l[j]);}return rev_s.substr(0, s.size() - p[l.size() - 1]) + s;
}

215 数组中第 k 大的数字

实际上这道题更可能的题目是找到前 k 大的所有数字。
首先，设计到数组排序的问题一定向面试官要问清楚数据量的大小，这影响到接下来的实现，
同时和面试官探讨数据量大小对实现的影响，有助于更好的把握局面。

我们先假设数据量是比较小的，也就是能够放到内存中。

0. 使用排序就实在是 naive 了，不过面试官非要问的话，当然是使用选择排序更好了。
1. 使用快排中的 partition 算法，时间复杂度 O(n*logk)。
2. 使用 size 为 k 的堆，时间复杂度也是 O(n*logk)，不管数字多大，都只需要遍历一遍。
3. 使用类似插入排序的方法，保持数组大小不变，这样的时间复杂度是 O(n*k)。
4. 数据的范围有限时候，使用计数排序。

当数据过大的时候，我们可以想通过哈希取模之后把文件分组，找出每个文件中最大的 k 个数字

如果数字中有重复呢？使用计数排序，计数强制按一算
如果既有重复又是浮点数呢？

C 解答

int swap(int* a, int* b) {int t = *a;*a = *b;*b = t;
}int partition(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;
}int findKthLargest(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;elseleft = index + 1;}
}

216 找到 k 个数字 [1…9]，使得他们的和是 n

C++ 解答

vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> result;dfs(result, {}, n, k);return result;
}void dfs(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++ 解答

bool containsDuplicate(vector<int>& nums) {unordered_set<int> s;for (auto& n : nums)if (s.find(n) != s.end())return true;elses.insert(n);return false;
}

218 获得矩形重合部分的拐点

抄过来的，还没仔细研究

C++ 解答

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 timewhile(cur<len || !liveBlg.empty()) { // if either some new building is not processed or live building queue is not emptycur_X = liveBlg.empty()? buildings[cur][0]:liveBlg.top().second; // next timing point to processif(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 onewhile(!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 vectorcur_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 queueliveBlg.push(make_pair(buildings[cur][2], buildings[cur][1]));cur++;}}cur_H = liveBlg.empty()?0:liveBlg.top().first; // outut the top oneif(res.empty() || (res.back().second != cur_H) ) res.push_back(make_pair(cur_X, cur_H));}return res;
}

219 包含重复数字，并且两个的坐标不超过 k

C++ 解答

// 滑动窗口保存前 k 个值，如果有重复的就返回
// num[i-k] num[i-1]，如果滑过了，就删除该元素
bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_set<int> s;if (k <= 0)return false;if (k >= nums.size()) // notice herek = nums.size() - 1;for (int i = 0; i < nums.size(); i++) {if (i > k)s.erase(nums[i - k - 1]); // delete first noteif (s.find(nums[i]) != s.end())return true;s.insert(nums[i]); // insert}return false;
}

220 同上一题，同时保证两个数字之间小于 t

保证两个数字之差小于 t

C++ 解答

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {set<int> window; // 注意不能使用 unorderedif (k <= 0)return false;if (k >= nums.size()) // notice herek = 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_boundif (pos != window.end() && *pos - nums[i] <= t)return true;window.insert(nums[i]);}return false;
}

221 找到最大的正方形

使用动态规划 https://leetcode.com/discuss/38489/easy-solution-with-detailed-explanations-8ms-time-and-space

C++ 解答

int maximalSquare(vector<vector<char>>& matrix) {if (matrix.empty()) return 0;int m = matrix.size(), n = matrix[0].size();vector<int> dp(m + 1, 0);int maxsize = 0, pre = 0;for (int j = 0; j < n; j++) { // 每一列for (int i = 1; i <= m; i++) { // notice i rangeint temp = dp[i];if (matrix[i - 1][j] == '1') {dp[i] = min(dp[i], min(dp[i - 1], pre)) + 1;maxsize = max(maxsize, dp[i]);}else dp[i] = 0;pre = temp;}}return maxsize * maxsize;
}

222 给定一个完全树，计算节点的数量。

C++ 解答

int countNodes(struct TreeNode* root) {if (!root)return 0;int left_height = 0, right_height = 0;struct TreeNode* left = root, *right = root;while (left) {left = left->left;left_height++;}while (right) {right = right->right;right_height++;}if (left_height == right_height) // 满树 2^h - 1return (1 << left_height) - 1;return countNodes(root->left) + countNodes(root->right) + 1;
}

223 找出两个长方形覆盖的面积

C 解答

int computeArea(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);// 不小心写反了。return -((left1 - right1) * (up1 - down1) + (left2 - right2) * (up2 - down2) - (left - right) * (up - down));
}

224 给定一个字符串，包含加减和括号，计算值

难点是对括号的处理，注意每次都要和 signs.top() 相乘

C++ 解答

int calculate(string s) {stack<int> signs; // signs before bracesint sign = 1;int num = 0;int result = 0;signs.push(1);for (auto c : s) {if (isdigit(c)) {num = 10 * num + (c - '0');} else if (c == '+' || c == '-') {result += signs.top() * sign * num;num = 0;sign = c == '+' ? 1 : -1;} else if (c == '(') {signs.push(sign * signs.top()); // trickysign = 1;} else if (c == ')') {result += signs.top() * sign * num;num = 0;signs.pop();sign = 1;}}result += signs.top() * sign * num; // trickyreturn result;
}

225 使用队列模拟栈

其实有两种做法，一种是在 push 的时候，把队列清空，把 x 放到最底下。
另一种是在 pop 的时候，把队列清空到 1，然后弹出。应当询问面试官究竟是 push 居多还是 pop 居多

C++ 解答

class Stack {
public:// Push element x onto stack.void push(int x) {while (!nums.empty()) {temp.push(nums.front());nums.pop();}nums.push(x);while (!temp.empty()) {nums.push(temp.front());temp.pop();}}// Removes the element on top of the stack.void pop() {nums.pop();}// Get the top element.int top() {return nums.front();}// Return whether the stack is empty.bool empty() {return nums.empty();}
private:queue<int> nums;queue<int> temp;
};

226 反转二叉树

C 解答

struct TreeNode* invertTree(struct TreeNode* root) {if (!root) return NULL;struct TreeNode* temp = root->left;root->left = invertTree(root->right);root->right = invertTree(temp);return root;
}

227 给定一个字符串包含 +-*/ 计算他的值

C++ 解答

int calculate(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 ifif (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++ 解答

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]));elseresult.push_back(to_string(nums[start]));i = end + 1;}return result;
}

229 找出超过三分之一的元素

C++ 解答

vector<int> majorityElement(vector<int>& nums) {int count1 = 0, count2 = 0;int a, b;for (auto n : nums) {if (count1 == 0 || n == a) {count1++;a = n;} else if (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 aresult.push_back(a);if (count2 > nums.size() / 3 && a != b) // verify bresult.push_back(b);return result;
}

230 二叉树中第 k 小的数字

C 解答

// 传递指针
void inorder(struct TreeNode* root, int* k, int* number) {if (!root)return;inorder(root->left, k, number);(*k)--;if (*k == 0) {*number = root->val;return;}inorder(root->right, k, number);
}
int kthSmallest(struct TreeNode* root, int k) {int number;inorder(root, &k, &number);return number;
}

231 2 的次方

C 解答

bool isPowerOfTwo(int n) {if (n <= 0) return false;return (n & (n - 1)) == 0;
}

Rust 解答

impl Solution {pub fn is_power_of_two(n: i32) -> bool {if n <= 0 {return false;}(n & (n-1)) == 0}
}

232 使用栈模拟队列

C++ 解答

class Queue {
public:// Push element x to the back of queue.void push(int x) {in.push(x);}// Removes the element from in front of queue.void pop(void) {if (empty())return;if (out.empty())transfer();out.pop();}// Get the front element.int peek(void) {if (empty())return INT_MIN;if (out.empty())transfer();return out.top();}// Return whether the queue is empty.bool empty(void) {return in.empty() && out.empty();}
private:void transfer() {while (!in.empty()) {out.push(in.top());in.pop();}};stack<int> in;stack<int> out;
};

233 小于 n 的数字中 1 的个数

对于每一位，有三种情况：

1. 当是数字 0 的时候，可能出先 1 的情况完全由高位出现决定，因为这一位不能贡献 1
2. 当是数字 1 的时候，同上，但是这一位和低位一起可以贡献一个 1
3. 当时数字 2-9 的时候，相当于这一位的 1 可以任意出现，因此高位＋1

C 解答

int countDigitOne(int n) {int ones = 0;for (int m = 1; m <= n; m *= 10) { // m is the factorint a = n/m, b = n%m;  // a is left half, b is right halfif (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 解答

int countDigitOneBinary(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;elseones += (a >> 1) * m;}
}

求最大的 countDigitOne(n) == n

9    1
99   20
999  300
...
99999999  10000000

234 判断一个链表是否是回文

解法 1: 如果链表是可以改变的，不妨反转它的前半部分，然后再与后半部分比较

解法 2: 如果是只读的，复制一份也可以，但是不如使用堆栈

注意对奇数偶数的处理

C++ 解答

bool isPalindrome(ListNode* head) {if (!head || !head->next)return true;int len = 0;ListNode* temp = head;while (temp) {len++;temp = temp->next;}stack<int> stk;temp = head;int mid = len / 2;while (mid--) {stk.push(temp->val);temp = temp->next;}if (len & 0x01)temp = temp->next;while (temp != NULL && !stk.empty()) {int a = stk.top();stk.pop();int b = temp->val;temp = temp->next;if (a != b) {return false;}}return true;
}

235 二叉搜索树公共祖先

C 解答

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {while (root) {if (root->val > p->val && root->val > q->val)root = root->left;else if (root->val < p->val && root->val < q->val)root = root->right;elsereturn root;}
}

236 二叉树公共祖先

如果二叉树的根就是其中一个节点，那显然是这个。
在两颗子树中分别查找，如果找到了，返回一个非 NULL 值，如果都找到了，则这个节点就是 LCA

C 解答

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {if (!root || root == p || root == q)return root;struct TreeNode* left = lowestCommonAncestor(root->left, p, q);struct TreeNode* right = lowestCommonAncestor(root->right, p, q);if (!left) // not in left subtreereturn right;if (!right)return left;return root; // both left and right are found!
}

237 删除链表中的元素

直接将后继节点的值复制到当前节点

C 解答

void deleteNode(struct ListNode* node) {if (!node || !node->next)return;struct ListNode* next = node->next;node->val = next->val;node->next = next->next;free(next);
}

238 数组除了自己以外的乘积，规定不能用除法

首先从前往后乘，错开一位元素，这样每个元素都乘到了他之前的所有元素，最后一个元素已经是结果了。
然后从后往前乘，同样错开一位，这样每个元素又把他之后的元素都得到了。

239 滑动窗口最大值，给定一个滑动窗口，返回它移动过程中的最大值

单调队列的应用，复杂度是 O(n) 的。

Python 解答

from collections import dequeclass MonoQueue:def __init__(self):self.q = deque()  # 实际储存数据self.m = deque()  # 维护单调关系，队首元素总是最大值def push(self, x):self.q.append(x)while len(self.m) > 0 and self.m[-1] < x:self.m.pop()self.m.append(x)def pop(self):x = self.q.popleft()if self.m[0] == x:self.m.popleft()return xdef __len__(self):return len(self.q)def top(self):return self.m[0]class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:q = MonoQueue()for i in range(k):q.push(nums[i])ans = []for i in range(k, len(nums)):ans.append(q.top())q.pop()q.push(nums[i])ans.append(q.top())return ans

另一种现在我已经看不懂的做法

C++ 解答

// 题目给定 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 给定一个矩阵，每行从左到右都是增大的，每一列从上到下都是增大的，找出给定数字是否存在

我们考虑右上角的元素

1. 如果这个元素比 taget 大，那么整列都比 target 大，我们可以 c–
2. 如果这个元素比 target 小，那么正行都比 target 小，我们可以 r++

C 解答

bool searchMatrix(int** matrix, int row, int col, int target) {int r = 0, c = col - 1; // 右上角while (r < row && c > -1) // 向左下角if (matrix[r][c] == target)return true;else if (matrix[r][c] > target)c--;elser++;return false;
}

241 添加括号得到不同的结果

对每一个符号，在他的两边添加括号的好的不同结果再计算。

C++ 解答

vector<int> diffWaysToCompute(string input) {vector<int> output;for (int i = 0; i < input.size(); i++) {char token = input[i];if (!isdigit(token)) // not digitfor (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;
}

242 一个单词是否能由另一个变幻而来

还是，对于 ASCII 字符，直接用数组代替字典

C 解答

bool isAnagram(char* s, char* t) {char ss[26] = {0};char ts[26] = {0};while (*s) {ss[*s - 'a']++;s++;ts[*t - 'a']++;t++;}if (*t) return false;return memcmp(ss, ts, sizeof(ss)) == 0;
}

243-256 Locked

257 二叉树左右路径

典型的 DFS，发挥所有从根节点到叶节点的路径

C++ 解答

vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;if (!root) return result;paths(result, "", root);return result;
}void paths(vector<string>& result, string path, TreeNode* root) {if (path.empty())path += to_string(root->val);elsepath += "->" + to_string(root->val);if (root->left)paths(result, path, root->left);if (root->right)paths(result, path, root->right);if (!root->left && !root->right)result.push_back(path);
}

258 把数字的每一位加起来，直到变成一个一位的数字

这完全是一道数学题，对于每个进制的数字都有规律 (n - 1) % (x - 1) + 1。实际上是把 10 进制的转化为 9 进制数字

C 解答

int addDigits(int num) {return (num - 1) % 9 + 1;
}

259 Locked

260 给定一个数组，每个数字都是重复的，只有两个数字不是，找出这两个数字

这道题很奇妙，依然可以使用 XOR 来解，首先遍历一遍，这时候由于有两个数字是不同的，那么一定结果不为 0，那么其中一个 bit 位一定是一个数字有，另一个数字没有。
在遍历一遍，同时把数字分两组，一组是有这个 bit 位，一组没有。就得出了结果。

C++ 解答

vector<int> singleNumber(vector<int>& nums) {int r = 0;for (auto& n : nums)r ^= n;int bit = r & -r; // last sig bitvector<int> result = {0, 0};for (auto& n : nums)if (n & bit)result[0] ^= n;elseresult[1] ^= n;return result;
}

261 262 Locked

263 丑陋的数字，质数因子只含有 2,3,5 的数字

按定义做就好了

C 解答

bool isUgly(int n) {if (n <= 0)return false;if (n == 1)return true;while (n > 1)if (n % 2 == 0)n /= 2;else if (n % 3 == 0)n /= 3;else if (n % 5 == 0)n /= 5;elsereturn false;return true;
}

264 找出第 n 个丑陋数字

使用数列记录 n 个丑陋数字，每一个丑陋数字肯定是之前数字乘以 235 得到的，然后用三个指针分别指向上一个做乘法的数字，每次找出最小的一个

C 解答

#define MIN(a,b) ((a)<(b)?(a):(b))int nthUglyNumber(int n) {if (n <= 0)return -1;if (n < 6) // 1..6 恰好都是return n;int s2 = 0, s3 = 0, s5 = 0;int* uglies[n];uglies[0] = 1;for (int i = 1; i < n; i++) {int c2 = uglies[s2] * 2, c3 = uglies[s3] * 3, c5 = uglies[s5] * 5;uglies[i] = MIN(c2, MIN(c3, c5));if (uglies[i] == c2) s2++;if (uglies[i] == c3) s3++;if (uglies[i] == c5) s5++;}return uglies[n-1];
}

268 丢失的数字，给定 0…n，丢失了一个，然后放在长度为 n 的数组之中，找出这个数字

显然还是使用异或，注意 0 ^ x == x，所以直接把 0 忽略就行了。把每个数字都和 i 异或，丢失的数字就出来了

C 解答

int missingNumber(int* nums, int n) {int result = 0;for (int i = 0; i < n; i++)result = result ^ (i + 1) ^ nums[i];return result;
}

269-272 Locked

273 数字转换为英语单词

C++ 解答

class Solution {
public:vector<string> digits = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};vector<string> tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};vector<string> seps = {"", " Thousand ", " Million ", " Billion "}; // notice the trailing spacesstring numberToWords(int num) {if (num == 0)return "Zero";if (num < 0)return "Negative " + numberToWords(-num);int count = 0;string result;while (num) {if (num % 1000 != 0)result = s2word(num % 1000) + seps[count] + result;num /= 1000;count++;}// removw unnecessary tailing spaceif (isspace(result.back()))result.resize(result.size() - 1);return result;}string s2word(int num) {string result;if (num >= 100) {result += digits[num/100] + " Hundred ";num %= 100;}if (num >= 20) {result += tens[num / 10] + " ";num %= 10;}if (num >= 1 && num <= 19)result += digits[num];// remove tailing spacesif (isspace(result.back()))result.resize(result.size() - 1);return result;}
};

274 H-Index

H-Index 的定义：一个科学家的 N 篇论文 h 个至少有 h 个引用，而且剩下的 N-h 篇论文都没有超过 h 个引用。

C 解答

int hIndex(int* cites, int n) {int hs[n+1]; // Hindex 不可能大于 Nfor (int i = 0; i <= n; i++)hs[i] = 0;for (int i = 0; i < n; i++) {if (cites[i] > n)hs[n]++;elsehs[cites[i]]++;}for (int i = n, papers = 0; i >= 0; i--) { // 从后往前，如果有符合条件的，那么就是 Hindexpapers += hs[i];if (papers >= i)return i;}return 0;
}

275 H-index II，论文已经按照引用数量排序

C 解答

int hIndex(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];else if (citations[mid] < n - mid)left = mid + 1;elseright = mid - 1;}return n - right - 1;
}

276-277 Locked

278 第一个坏版本

C 解答

// 实际上是 lower_bound 函数
int firstBadVersion(int n) {int left = 0, right = n; // 记住 lower_bound 的 right 是 nwhile (left < right) {   // 使用小于号int mid = left + (right - left) / 2;if (!isBadVersion(mid))left = mid + 1;elseright = mid;}return left;
}

279 分解为平方数的和

最多 4 个即可，尝试在三个以内是否可以。

C 解答

int numSquares(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;}}return 4;
}

282 添加运算符使得算式成立

C++ 解答

vector<string> addOperators(string num, int target) {vector<string> result;if (num.size() == 0)return result;dfs(num, target, result, num[0] - '0', num.substr(0, 1), 1, 1);return result;
}void dfs(string num, int target, vector<string> & v, long long last, string s, int idx, int left) {if (idx == num.length()){if (target == last*left)v.push_back(s);return;} else {if(last!=0)dfs(num, target,         v, last * 10 + num[idx] - '0', s + num.substr(idx, 1), idx + 1, left); // 尝试拼成 10dfs(num, target,             v, num[idx] - '0', s + '*' + num.substr(idx, 1), idx + 1, last*left);dfs(num, target - left*last, v, num[idx] - '0', s + '+' + num.substr(idx, 1), idx + 1, 1);dfs(num, target - left*last, v, num[idx] - '0', s + '-' + num.substr(idx, 1), idx + 1, -1);}
}

283 移动 0

注意 swap 的使用

C++ 解答

void moveZeroes(vector<int>& nums) {int n = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] != 0)swap(nums[n++], nums[i]);}
}

284 Peek Iterator

C++ 解答

// Below is the interface for Iterator, which is already defined for you.
// **DO NOT** modify the interface for Iterator.
class Iterator {struct Data;Data* data;
public:Iterator(const vector<int>& nums);Iterator(const Iterator& iter);virtual ~Iterator();// Returns the next element in the iteration.int next();// Returns true if the iteration has more elements.bool hasNext() const;
};class PeekingIterator : 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.int peek() {return Iterator(*this).next();}// hasNext() and next() should behave the same as in the Iterator interface.// Override them if needed.int next() {return Iterator::next();}bool hasNext() const {return Iterator::hasNext();}
};

285 ~ 286 Locked

287 一个 n 的数组包含了 1…n-1 中的这些数字，证明一定存在重复，并找出这个重复

使用抽屉原理可以证明一定存在重复。据说高纳德解这个问题花了四个小时。

我们把这个数组看做一个变幻方程 f(i) = A[i]，把一些数字变幻到另一些，那么存在一个 i != j s.t. f(i) == f(j).
那么这个问题变成了链表求环的问题。对于链表，我们有 n = n->next 遍历列表，对于这个序列，则是 n = f(n)

C 解答

int findDuplicate(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 解答

int max(int a, int b) {return a > b ? a :b;}
int min(int a, int b) {return a < b ? a :b;}
void gameOfLife(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 hereboard[i][j] |= 2;}}for (int i = 0; i < row; i++)for (int j = 0; j < col; j++)board[i][j] >>= 1;
}

290 单词模式，给定一个模式 abba 等，判断单词是否是这个模式的。

C++ 解答

bool wordPattern(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 countfor (string word; in >> word; i++) {if (i == n || chars[pattern[i]] != words[word]) // 检查是否相等return false;chars[pattern[i]] = words[word] = i + 1; // distinct non zero}return i == n; // 检查长度是否相等
}

291 Locked

292 Nim 游戏，每个人可以选择丢掉 1，2，3，最后一个操作者获胜

显然，当我们遇到 4 的时候会输，其他情况都可以赢。

C 解答

bool canWinNim(int n) {return n % 4 != 0;
}

300 最长递增子序列

最经典的动态规划题目

Python 解答

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if not nums:return 0if len(nums) == 1:return 1dp = [1 for _ in range(len(nums))]for i in range(len(nums)):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)return max(*dp)

344 翻转字符串

C 解答

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;
}

347 出现最多的几个数字

C 实在缺乏相关的基础数据结构，这道题用 JS 做了

JavaScript 解答

/*** @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;elserv.push(parseInt(num))}}return rv;
};

349 两个数组中都出现的元素

先排序，降低复杂度

C 解答

static int compare(const void* a, const void* b) {return *(int*)a - *(int*)b;
}
int* intersection(int* A, int m, int* B, int n, int* k) {qsort(A, m, sizeof(int), compare);qsort(B, n, sizeof(int), compare);int* C = malloc((m + n) * sizeof(int));*k = 0;int i = 0;int j = 0;while (i < m && j < n) {if (A[i] == B[j]) {if (*k == 0)C[(*k)++] = A[i];else if (C[*k - 1] != A[i])C[(*k)++] = A[i];i++;j++;} else if (A[i] < B[j]) {i++;} else {j++;}}return C;
}

345 翻转一个字符串里面的元音字母

使用两个指针，不过需要注意元音字母包括了大小写

Python 解答

class Solution:def reverseVowels(self, s):""":type s: str:rtype: str"""if not s:return svowels = set("AEIOUaeiou")s = list(s)i = 0j = len(s) - 1while True:while s[i] not in vowels and i < j:i += 1while s[j] not in vowels and i < j:j -= 1if i >= j:breaks[i], s[j] = s[j], s[i]i += 1j -= 1return ''.join(s)

371 两个数之和

这道题要求不用 + 和 - 来计算出两个数之和，显然应该使用位运算，使用异或计算每一位的值，在使用或计算是否需要进位

C 解答

int getSum(int a, int b) {int rv = 0;int carry = 0;for (int i = 0; i < 32; i++) {int last_bit_of_a = a & 1;int last_bit_of_b = b & 1;rv |= (last_bit_of_a ^ last_bit_of_b ^ carry) << i;carry = (carry & last_bit_of_a) | (carry & last_bit_of_b) | (last_bit_of_a & last_bit_of_b);a >>= 1;b >>= 1;}return rv;
}

388

使用栈的一道简单题目, 其实计算长度部分还可以优化

Python 解答

class Solution:def lengthLongestPath(self, input: str) -> int:path = []ans = 0for name in input.split("\n"):l = 0for c in name:if c == "\t":l += 1else:breakif len(path) > l:for i in range(len(path) - l):path.pop()path.append(name.strip("\t"))if "." in name:length = sum([len(p) for p in path]) + len(path) - 1ans = max(ans, length)print(path)return ans

435 无重叠区间

不要被题目迷惑，从反面开始思考，求去除多少个区间其实就是求最多有多少个有效区间

Python 解答

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key=lambda x: x[1])max_intervals = 0end = float("-inf")for interval in intervals:if interval[0] >= end:max_intervals += 1end = interval[1]return len(intervals) - max_intervals

482 注册码格式化

要求每 K 个字符添加一个 “-”, 如果不够的话，第一个分组可以不全。

Python 解答

class Solution:def licenseKeyFormatting(self, S: str, K: int) -> str:key = []i = 0for c in reversed(S):if c == "-":continuekey.append(c.upper())i += 1if i % K == 0:key.append("-")if key and key[-1] == "-":key = key[:-1]return "".join(reversed(key))

547 朋友圈

UnionFind 的定义见第 200 题

Python 解答

class Solution:def findCircleNum(self, M: List[List[int]]) -> int:n = len(M)uf = UnionFind(n)for i in range(n):for j in range(i):if M[i][j] == 1:uf.union(i, j)return uf.count

739

单调栈的简单应用

Python 解答

class Solution:def dailyTemperatures(self, T: List[int]) -> List[int]:stack = []ans = [0] * len(T)for i in range(len(T)-1, -1, -1):# 如果当前温度大于当前最低温度while stack and T[i] >= T[stack[-1]]:stack.pop()if stack:ans[i] = stack[-1] - istack.append(i)return ans

864 矩形重叠

Python 解答

class Solution:def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:# 注意要包含等于号x_overlap = not(rec1[0] >= rec2[2] or rec1[2] <= rec2[0])y_overlap = not(rec1[1] >= rec2[3] or rec1[3] <= rec2[1])return x_overlap and y_overlap

904 找出包含了两个不同数字的最长子序列

这道题的题目很坑爹，但是翻译过来其实要求很明确。解题思路也很简单，存储一下当前的最长序列
就好了。

C++ 解答

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 解答

class Solution:def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:i, j = 0, 0ans = []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 += 1else:j += 1return ans

929 唯一邮件地址

类似 Gmail 的规则，. 去掉，+ 后面的也去掉。但是要注意域名中的 . 不能去掉

Python 解答

class Solution:def normalize(self, username: str) -> str:username = username.replace('.', "")# 使用 split 更好，懒得改了username = re.sub(r"\+.*$", "", username)return usernamedef numUniqueEmails(self, emails: List[str]) -> int:unique_emails = set()for email in emails:username, domain = email.split("@")username = self.normalize(username)# print(username, domain)unique_emails.add(f"{username}@{domain}")return len(unique_emails)

970 强力数字

暴力解法

python 解答

import mathclass Solution:def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:if bound <= 0:return []ans = set()limit = int(math.log2(bound)) + 1for i in range(limit):for j in range(limit):v = x ** i + y ** jif v <= bound:ans.add(v)return list(ans)

1272 删除区间

python 解答

class Solution:def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:lo, hi = toBeRemovedans = []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 解答

class Solution:def getNoZeroIntegers(self, n: int) -> List[int]:for a in range(1, n):b = n - aif "0" not in str(a) and "0" not in str(b):return [a, b]return []

1389 按既定顺序创建目标数组

Python 解答

class Solution:def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:target = []for n, i in zip(nums, index):target = target[:i] + [n] + target[i:]return target

1390 四因数

解释见注释，这道题还是很坑的。不过其实也很简单，四个因数就是能够分解成两个质数乘积或者是立方数。

比如：

1. 21 = 3 * 7
2. 8 = 2 * 4

py 解答

class Solution:def sumFourDivisors(self, nums) -> int:if not nums:return 0if len(nums) == 1:upper = nums[0]else:upper = max(*nums)# 首先在这里筛选素数isPrim = [True for _ in range(upper)]i = 2while i * i < upper:if isPrim[i]:j = i * iwhile j < upper:isPrim[j] = Falsej += ii += 1# 把素数都提取出来prims = [i for i in range(2, upper) if isPrim[i]]ans = 0for num in nums:for prim in prims:# 已经不可能了，后续不算了if prim * prim > num:break# 立方数是符合的，这个比较坑，开始没想到，比如 8if prim * prim * prim == num:ans += (1 + num + prim + prim * prim)break# 可以分解成两个质数乘积if num % prim == 0 and isPrim[num // prim] and prim * prim != num:ans += (1 + num + prim + num // prim)breakreturn ans