# 算法 (Algorithm) 先导课
# 暴力枚举
# 循环
知识点:
- 从头到尾循环
- 从尾到头循环
- 从中间向两边循环
- 从两边向中间循环
- 多重循环优化，通常是考虑省去内层循环，在外层循环的时候“记忆”必要信息
lc-1 两数之和: for-loop, nested-loop
练习地址 (opens new window)，在线视频 (opens new window)
输入是一维数组，使用暴力法找两个不同下标，难点：
- 二重循环
- 需要暴力枚举出所有下标组合情况，而非排列情况
- 因为是组合而非排列，所以要想清楚内层循环的控制变量从多少开始
- 为了优化多重循环，我们想办法删掉内层循环
class Solution:
def twoSum(self, nums, target):
for i in range(0, len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
s = Solution()
s.twoSum([2,7,11,15], 22)
class Solution:
def twoSum(self, nums, target):
hash = {}
for i in range(len(nums)):
need = target - nums[i]
if need in hash:
return [i, hash[need]]
hash[nums[i]] = i两数之差
力扣原题 (opens new window)的改造，将原题两数之和改为两数之差即可。
使用暴力法找两个不同下标，改造点在于：
- 原题使用暴力找两个下标的组合
- 改后使用暴力找两个下标的排列
def solution(nums, target):
for i in range(0, len(nums)):
for j in range(0, len(nums)):
if i == j: continue
if nums[i] + nums[j] == target:
return [i, j]
lc-5 最长回文子串
输入是字符串，即一维数组。这题需要从中间向两边遍历。
class Solution:
def longestPalindrome(self, s):
n = len(s)
maxLen = 0
maxL = maxR = 0
for mid in range(n):
l, r = mid, mid
while l >= 0 and r < n:
if s[l] != s[r]: break
if r - l > maxLen:
maxLen = r - l
maxL, maxR = l, r
l, r = l - 1, r + 1
l, r = mid, mid + 1
while l >= 0 and r < n:
if s[l] != s[r]: break
if r - l > maxLen:
maxLen = r - l
maxL, maxR = l, r
l, r = l - 1, r + 1
return s[maxL: maxR + 1]
lc-11 盛最多水的容器
输入是一维数组。这题需要从中间向两边遍历。难点：
- 循环迭代的动作二选一: i++、j--
- 需要在循环体内决定选哪个动作
public class Solution {
public int maxArea(int[] height) {
int i = 0;
int j = height.length - 1;
int res = 0;
while (i < j) {
int w = j - i;
int h = Math.min(height[i], height[j]);
res = Math.max(res, w * h);
if (height[i] < height[j]) { i++; }
else { j--; }
}
return res;
}
}
var maxArea = function(height) {
let l = 0;
let r = height.length -1 ;
let res = Math.min(height[l], height[r]) * (r - l);
while (l < r) {
if (height[l] < height[r]) {
l++;
} else {
r--;
}
res = Math.max(res, Math.min(height[l], height[r]) * (r - l));
}
return res;
};from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
i, j = 0, len(height) - 1
res = (j - i) * min(height[i], height[j])
while i < j:
if height[i] < height[j]: i += 1
else: j -= 1
res = max(res, (j - i) * min(height[i], height[j]))
return res
lc-42 接雨水
暴力做法，考虑每一根柱子能接的雨水量，外层循环遍历所有柱子，内层需要两个循环（一个向左、一个向右）。
- 二重循环，内层有 2 个循环
- 多重循环优化: 将内层循环移出去，形成 3 个并列的循环
class Solution {
public int trap(int[] height) {
int n = height.length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
int tmp = 0;
for (int i = 0; i < n; i++) {
leftMax[i] = tmp;
tmp = Math.max(tmp, height[i]);
}
tmp = 0;
for (int i = n - 1; i >= 0; i--) {
rightMax[i] = tmp;
tmp = Math.max(tmp, height[i]);
}
int res = 0;
for (int i = 0; i < n; i++) {
int diff = Math.min(leftMax[i], rightMax[i]) - height[i];
if (diff > 0) res += diff;
}
return res;
}
}
lc-14 最长公共前缀: two-dimensional-arrays
练习地址 (opens new window)，这题比较烦。
题目给的是字符串数组，因为字符串本身也是数组，所以这题是一个二维数组，需要用二重循环来处理。难点在于：
- 外层循环遍历数组的第二个维度、内层循环遍历数组的第一个维度，和以往相反
- 外层循环退出的时机由循环体内运行结果决定
- break 退出的条件
- 这题需要纵向遍历二维数组
class Solution:
def longestCommonPrefix(self, strs):
n = len(strs)
if n == 0: return ''
if n == 1: return strs[0]
i = 0
while True:
shouldExit = False
for j in range(n):
if i >= len(strs[j]):
shouldExit = True
break
if j > 0 and strs[j][i] != strs[j - 1][i]:
shouldExit = True
break
if shouldExit:
break
i += 1
return strs[0][:i]lc-15 三数之和: for-loop, nested-loop
练习地址 (opens new window)，这题很难。
先给数组排序，然后使用找三个不同下标，难点：
- 二重循环
- 内层循环顺序: 从两边向中间遍历
- 结果去重的方法有点超纲，比较难
# 递归与分治
lc-100 相同的树
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
if (p.val == q.val) {
return this.isSameTree(p.left, q.left) && this.isSameTree(p.right, q.right);
}
return false;
}
}lc-98 验证二叉搜索树
class Solution {
public boolean isValidBST(TreeNode root) {
return this.valid(root, null, null);
}
private boolean valid(TreeNode root, Integer min, Integer max) {
if (root == null) return true;
if ((min != null && root.val <= min) || (max != null && root.val >= max)) return false;
return this.valid(root.left, min, max == null ? root.val : Math.min(max, root.val))
&& this.valid(root.right, min == null ? root.val : Math.max(min, root.val), max);
}
}lc-70-暴力: fibonacci, recursion
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2: return n
return self.climbStairs(n - 1) + self.climbStairs(n - 2)
lc-70-记忆化: dynamic-array, loop
class Solution:
def __init__(self):
self.memo = { 0: 1, 1: 1, 2: 2 }
def climbStairs(self, n: int) -> int:
if n in self.memo:
return self.memo[n]
self.memo[n] = self.climbStairs(n - 1) + self.climbStairs(n - 2)
return self.memo[n]
# 数据结构: 树
树的算法题都是递归来做。