给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0] 输出: 3
示例 2:
输入: [3,4,-1,1] 输出: 2
示例 3:
输入: [7,8,9,11,12] 输出: 1
题解： 将所有的数用map存起来，然后从1依次开始找没有出现在map中的最小的正整数
python版
class Solution: def firstMissingPositive(self, nums: List[int]) -> int: n = len(nums) for i in range(1, n + 2): if i not in nums: return ic++版
class Solution { public: int firstMissingPositive(vector<int>& nums) { map<int, int> mp; int n = nums.size(); for(int i = 0; i < n; i++) mp[nums[i]] = 1; for(int i = 1; i <= n; i++){ if(mp.count(i) == 0) return i; } return n + 1; } };给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
题解： 单调栈的应用 我们用栈保存每堵墙。 当遍历墙的高度的时候，如果当前高度小于栈顶的墙高度，说明这里会有积水，我们将墙的高度的下标入栈。 如果当前高度大于栈顶的墙的高度，说明之前的积水到这里停下，我们可以计算下有多少积水了。计算完，就把当前的墙继续入栈，作为新的积水的墙。 总体的原则就是， 1.当前高度小于等于栈顶高度，入栈，指针后移。 2.当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。 直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。
python版
class Solution: def trap(self, height: List[int]) -> int: l = [] res = 0 n = len(height) for i in range(n): while len(l) != 0 and height[l[-1]] < height[i]: h = height[l[-1]] l.pop() if len(l) == 0: break d = i - l[-1] - 1 h = min(height[l[-1]], height[i]) - h res += d * h l.append(i) return resc++版
class Solution { public: int trap(vector<int>& height) { stack<int> st; int n = height.size(); int res = 0; for(int i = 0; i < n; i++){ while(st.size() && height[st.top()] < height[i]){ int h = height[st.top()]; st.pop(); if(st.empty()) break; int d = i - st.top() - 1; h = min(height[st.top()], height[i]) - h; res += d * h; } st.push(i); } return res; } };给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = “2”, num2 = “3” 输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456” 输出: “56088”
说明：
num1 和 num2 的长度小于110。 num1 和 num2 只包含数字 0-9。 num1 和 num2 均不以零开头，除非是数字 0 本身。 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
题解： 高精度乘法问题
python版
class Solution: def multiply(self, num1: str, num2: str) -> str: if num1 == "0" or num2 == "0": return "0" ans = "0" m, n = len(num1), len(num2) for i in range(n - 1, -1, -1): add = 0 y = int(num2[i]) curr = ["0"] * (n - i - 1) for j in range(m - 1, -1, -1): product = int(num1[j]) * y + add curr.append(str(product % 10)) add = product // 10 if add > 0: curr.append(str(add)) curr = "".join(curr[::-1]) ans = self.addStrings(ans, curr) return ans def addStrings(self, num1: str, num2: str) -> str: i, j = len(num1) - 1, len(num2) - 1 add = 0 ans = list() while i >= 0 or j >= 0 or add != 0: x = int(num1[i]) if i >= 0 else 0 y = int(num2[j]) if j >= 0 else 0 result = x + y + add ans.append(str(result % 10)) add = result // 10 i -= 1 j -= 1 return "".join([str(x) for x in ans][::-1])c++版
class Solution { public: string multiply(string num1, string num2) { int n1 = num1.size(); int n2 = num2.size(); vector<int> a, b, c(n1 + n2); for(int i = n1 - 1; i >= 0; i--) a.push_back(num1[i] - '0'); for(int i = n2 - 1; i >= 0; i--) b.push_back(num2[i] - '0'); for(int i = 0; i < n1; i++) for(int j = 0; j < n2; j++){ c[i + j] += a[i] * b[j]; c[i + j + 1] += c[i + j] / 10; c[i + j] %= 10; } int l = n1 + n2 - 1; while(l > 0 && c[l] == 0) l--; string s = ""; while(l >= 0) s += c[l--] + '0'; return s; } };给定一个字符串 (s) 和一个字符模式 § ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。
‘?’ 可以匹配任何单个字符。 ‘*’ 可以匹配任意字符串（包括空字符串）。 两个字符串完全匹配才算匹配成功。
说明:
s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1:
输入: s = “aa” p = “a” 输出: false 解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:
输入: s = “aa” p = "" 输出: true 解释: '’ 可以匹配任意字符串。
示例 3:
输入: s = “cb” p = “?a” 输出: false 解释: ‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
示例 4:
输入: s = “adceb” p = “ab” 输出: true 解释: 第一个 ‘’ 可以匹配空字符串, 第二个 '’ 可以匹配字符串 “dce”.
示例 5:
输入: s = “acdcb” p = “a*c?b” 输出: false
题解： (动态规划) O(nm) 1.设状态 f(i,j) 表示 s 串的前 i 个字符与 p 串的前 j 个字符是否匹配。这里的有效下标从 1 开始。 2.假设 s 串的长度为 n，p 串的长度为 m。 3.初始化 f(0,0)=true，其余待定。 4.转移方程，假设 s 串的第 i 个字符为变量 x，p 串的第 j 个字符为变量 y。
python版
class Solution: def isMatch(self, s: str, p: str) -> bool: n = len(s) m = len(p) s = ' ' + s p = ' ' + p f = [[False for _ in range(m + 1)] for _ in range(n + 1)] f[0][0] = True for i in range(0, n + 1): for j in range(1, m + 1): if p[j] == '*': f[i][j] = f[i][j - 1] or i and f[i - 1][j] else: f[i][j] = (p[j] == s[i] or p[j] == '?') and i and f[i - 1][j - 1] return bool(f[n][m])c++版
class Solution { public: bool isMatch(string s, string p) { int n = s.size(); int m = p.size(); s = ' ' + s; p = ' ' + p; vector<vector<bool>> f(n + 1, vector<bool>(m + 1)); f[0][0] = true; for(int i = 0; i <= n; i++) for(int j = 1; j <= m; j++){ if(p[j] == '*') f[i][j] = f[i][j - 1] || i && f[i - 1][j]; else f[i][j] = (p[j] == s[i] || p[j] == '?') && i && f[i - 1][j - 1]; } return f[n][m]; } };给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
题解： (动态规划，贪心优化) O(n) 首先定义两个指针 last 和 i，数组 f[i] 表示到达 i 所需要的最少步数。 定义 last 为第一次到达 i 时上一步的位置，last 从 0 开始。 根据贪心得知，令 f[i] = f[last] + 1 后，f[i] 就会是最优值。 故可以根据 i 来让 last 向后移动，找到最早的可以一步到达 i 的位置，然后根据 f[last] 更新 f[i]。
python版
class Solution: def jump(self, nums: List[int]) -> int: n = len(nums) f = [0 for _ in range(n)] last = 0 for i in range(1, n): while i > last + nums[last]: last += 1 f[i] = f[last] + 1 return f[n - 1]c++版
class Solution { public: int jump(vector<int>& nums) { int n = nums.size(); vector<int> f(n); int last = 0; f[0] = 0; for(int i = 1; i < n; i++){ while(i > last + nums[last])last++; f[i] = f[last] + 1; } return f[n - 1]; } };给定一个 没有重复 数字的序列，返回其所有可能的全排列。 示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
题解：
(回溯) O(n×n!) 我们从前往后，一位一位枚举，每次选择一个没有被使用过的数。 选好之后，将该数的状态改成“已被使用”，同时将该数记录在相应位置上，然后递归。 递归返回时，不要忘记将该数的状态改成“未被使用”，并将该数从相应位置上删除。
c++版
class Solution { public: vector<vector<int>> ans; vector<int> path; vector<bool> st; vector<vector<int>> permute(vector<int>& nums) { path = vector<int>(nums.size()); st = vector<bool>(nums.size()); dfs(nums, 0); return ans; } void dfs(vector<int> nums, int cur){ if(cur == nums.size()){ ans.push_back(path); return ; } for(int i = 0; i < nums.size(); i++){ if(!st[i]){ path[cur] = nums[i]; st[i] = true; dfs(nums, cur + 1); st[i] = false; } } } };python版
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: st = [False] * len(nums) path = [0] * len(nums) ans = [] def dfs(nums, cur): if(cur == len(nums)): ans.append(path[::]) return for i in range(len(nums)): if(not st[i]): st[i] = True path[cur] = nums[i] dfs(nums, cur + 1) st[i] = False dfs(nums, 0) return ans给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
题解： 搜索 剪枝 选择nums[i]作为递归搜索树的当前节点时,发现nums[i]==nums[i-1] (1)若nums[i-1]的状态刚刚恢复，说明nums[i-1]与num[i]在递归树中属于同一层的相邻状态结点 而这数值相等会产生重复的递归实例，故在num[i]结点处进行剪枝回溯 (2)nums[i-1]状态还未恢复，说明nums[i-1]与nums[i]在递归树中属于同一路径的上下层， 二者数值相等不会产生重复递归实例。
c++版
class Solution { public: vector<vector<int>> ans; vector<int> path; vector<bool> st; vector<vector<int>> permuteUnique(vector<int>& nums) { path = vector<int> (nums.size()); st = vector<bool>(nums.size()); sort(nums.begin(), nums.end()); dfs(nums, 0); return ans; } void dfs(vector<int> nums, int cur){ if(cur == nums.size()){ ans.push_back(path); return ; } for(int i = 0; i < nums.size(); i++){ if(!st[i]){ if(i > 0 && !st[i - 1] && nums[i] == nums[i - 1]) // 去重 continue; st[i] = true; path[cur] = nums[i]; dfs(nums, cur + 1); st[i] = false; } } } };python版
class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: ans = [] path = [0] * len(nums) st = [False] * len(nums) def dfs(nums, cur): if cur == len(nums): ans.append(path[::]) return for i in range(len(nums)): if not st[i]: if i > 0 and nums[i] == nums[i - 1] and not st[i - 1]: continue st[i] = True path[cur] = nums[i] dfs(nums, cur + 1) st[i] = False nums.sort() dfs(nums, 0) return ans给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ], 原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3] ]
示例 2:
给定 matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], 原地旋转输入矩阵，使其变为: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ]
题解： (操作分解) O(n2) 直接操作旋转 90 度比较困难，我们可以将它分解成两个操作： 先以左上-右下对角条线为轴做翻转； 再以中心的竖线为轴做翻转；
c++版
class Solution { public: void rotate(vector<vector<int>>& matrix) { for(int i = 0; i < matrix[0].size(); i++) for(int j = i + 1; j < matrix[0].size(); j++) swap(matrix[i][j], matrix[j][i]); for(int i = 0; i < matrix[0].size(); i++) for(int j = 0, k = matrix[0].size() - 1; j < k; j++, k--) swap(matrix[i][j], matrix[i][k]); } };python版
class Solution: def rotate(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ n = len(matrix[0]) for i in range(n): for j in range(i + 1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] for i in range(n): j = 0 k = n - 1 while j < k: matrix[i][j], matrix[i][k] = matrix[i][k], matrix[i][j] j += 1 k -= 1给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [ [“ate”,“eat”,“tea”], [“nat”,“tan”], [“bat”] ]
说明：
所有输入均为小写字母。不考虑答案输出的顺序。题解： (哈希表) O(NLlogL) 定义从string 映射到 vector的哈希表：unordered_map<string, vector>，哈希表用法参见 这里 。 我们将每个字符串的所有字符从小到大排序，将排好序的字符串作为key，然后将原字符串插入key对应的vector中。 时间复杂度分析：N 是字符串个数，L 是字符串平均长度。对于每个字符串，哈希表和vector的插入操作复杂度都是 O(1)， 排序复杂度是 O(LlogL)。所以总时间复杂度是 O(NLlogL)。
c++版
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string,vector<string>> hash; for(auto str : strs){ string key = str; sort(key.begin(), key.end()); hash[key].push_back(str); } vector<vector<string>> res; for(auto i = hash.begin(); i != hash.end(); i++) res.push_back(i->second); return res; } }; class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: Hash = {} for s in strs: key = ''.join(sorted(list(s))) if Hash.get(key) is not None: Hash[key].append(s) else: Hash[key] = [s] return list(Hash.values())实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10 输出: 1024.00000
示例 2:
输入: 2.10000, 3 输出: 9.26100
示例 3:
输入: 2.00000, -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25
题解： 快速幂 c++版
class Solution { public: #define ll long long double myPow(double x, int n) { double ans = 1, p = x; ll t = abs((ll)(n)); for(; t; t >>= 1){ if(t & 1) ans = ans * p; p = p * p; } return n > 0 ? ans : 1 / ans; } };python版
class Solution: def myPow(self, x: float, n: int) -> float: ans = 1.0 d = x t = n if t < 0: t = -t while t: if t % 2 == 1: ans *= d d *= d t //= 2 return ans if n >= 0 else 1.0 / ans