LeetCode

1. 递归

递归要素：

• 参数中要有操作的数组或集合，以及目标。
• 结束条件，结束的判断需要由其它参数参与确定。
• 根据实际情况方法是否有返回。

2. 动态规划

动态规划要素：

• 创建一个(n+1)的数组来存放规划值。
• 数组第一个需要虚拟赋值，一般为0或false等。
• 由数组的最后一个或最后几个确定结果。

2.1 LeetCode198. 打家劫舍

创建一个长于数组的数组，用来存放每一次计算的结果，而每一次的计算又是从第一个到当前的**结果，一直重复到结束。

 public int rob(int[] nums) { 
    int result = 0; int length = nums.length; if (length == 1) { 
    result = nums[0]; } else if (length == 2) { 
    result = Math.max(nums[0], nums[1]); } else if (length > 2) { 
    int[] dp = new int[length + 1]; dp[0] = 0; dp[1] = nums[0]; dp[2] = nums[1]; for (int i = 3; i <= length; i++) { 
    // 动态规划(dynamic programming), 妙 啊！ dp[i] = Math.max(dp[i - 2], dp[i - 3]) + nums[i - 1]; } result = Math.max(dp[length], dp[length - 1]); } return result; } 

2.2 LeetCode139. 单词拆分

讯享网 / * 动态规划 (dynamic programming) * 以示例1为例，s为"leetcode"，wordDict为{"leet", "code"} * dp数组为[true, false, false, false, true, false, false, false, true] */ public static boolean wordBreak(String s, List<String> wordDict) { 
    HashSet<String> wordSet = new HashSet<>(wordDict); // 去除词典重复项 int length = s.length(); boolean[] dp = new boolean[length + 1]; dp[0] = true; for (int i = 1; i <= length; i++) { 
    for (int j = 0; j < i; j++) { 
    if (dp[j] && wordSet.contains(s.substring(j, i))) { 
    dp[i] = true; break; } } } return dp[length]; } 

3. 队列

3.1 优先队列 (PriorityQueue) 重排序

实例化示例：

讯享网

// 需要指定队列中存储的对象类型，如下为Integer。 // 可以指定初始容量，initialCapacity。 // 可以指定排序规则，如下为从小到大排序。 PriorityQueue<Integer> queueMin = new PriorityQueue<Integer>(new Comparator<Integer>() { 
    @Override public int compare(Integer o1, Integer o2) { 
    return (o1 < o2) ? 1 : ((o1 == o2) ? 0 : -1); } }); 

3.1 阻塞队列 (BlockingQueue) 重阻塞

实例化示例：

讯享网// 可以指定初始容量，initialCapacity。 // fair为阻塞时的策略，为true按队列先进先出的顺序处理元素，否则为未指定处理顺序。 BlockingQueue<CachedLocation> pendingLocations = new ArrayBlockingQueue<>(10000, true); 

4. 前缀和

4.1 LeetCode437. 路径总和 III

前缀和结合二叉树TreeNode来使用。还使用Map来记录一些特殊值的次数。

 public static void main(String[] arg0) { 
    Object[] nums = { 
   10, 5, -3, 3, 2, null, 11, 3, -2, null, 1}; System.out.println("路径总和 = " + pathSum(new TreeNode(nums), 8)); } public static int pathSum(TreeNode root, int targetSum) { 
    Map<Integer, Integer> counts = new HashMap<>(); // 这里设置0对应的值为1，这样如果第一个根节点就等于目标和，在递归中给res赋的值就是1，不需要再判断 counts.put(0, 1); return childMethod(root, counts, 0, targetSum); } / * 递归 + 前缀和 */ public static int childMethod(TreeNode node, Map<Integer, Integer> counts, int currSum, int targetSum) { 
    if (node == null || !node.isValidVal()) { 
    // 递归到了最末端终止，并且返回0条符合条件路径 return 0; } int res = 0; currSum += node.val; res = counts.getOrDefault(currSum - targetSum, 0); // 这里赋值不明白 counts.put(currSum, counts.getOrDefault(currSum, 0) + 1); // 记录前缀和的次数 res += childMethod(node.left, counts, currSum, targetSum); res += childMethod(node.right, counts, currSum, targetSum); counts.put(currSum, counts.getOrDefault(currSum, 0) - 1); // 检查完当前分支就要减少当前前缀和的次数 return res; } 

附：时间复杂度 和 空间复杂度

1. 时间复杂度：假设单次操作的时间为单位时间，求出结果总共需要的大概次数。

讯享网 - 递归的时间复杂度一般为n。 - 动态规划的时间复杂度一般为n的平方。 

2. 空间复杂度：整个操作需要开辟的内存空间。

 - 递归需要在栈上开辟空间。首次执行开辟一个空间，每次递归多开辟一个空间，最多递归多少次就是空间复杂度。 - 动态规划需要创建一个(总长度+1)的数组来存放规划值，空间复杂度即为数组长度。 

牛客

1. 对一个数组或者集合中的所有元素做全部组合

– 采用递归，而且递归中含有for循环
– 数组或集合数据要全局，判断标准要全局
– 新建两个全局的数组，大小要和源数据相同，一个记录选中下标，一个记录对应的值
– dfs递归两个参数，一个p记录当前赋值位置并且下次递归也可使用，一个count记录使用前几个数据

讯享网public static int[] data; // 源数据 public static int number; // 判断标准 public static int[] tempIndex; // 记录选中下标 public static int[] tempData; // 记录选中下标对应的数据 { 
    List<List<Integer>> ans = new ArrayList<>(); dfs(0, 0, ans); // p 和 count 必须从0开始 } // 递归方法，第三个参数是结果，其实也可以做成全局变量 public static void dfs(int p, int count, List<List<Integer>> ans) { 
    int total = 0; List<Integer> temp = new ArrayList<>(); for (int i = 0; i < count; i++) { 
    temp.add(tempData[i]); total += temp.get(i); if (total == number) { 
    ans.add(temp); return; // 要根据判断标准来写，是否需要再增加count } if (total > number) { 
    return; // 要根据判断标准来写，是否需要再增加count } } int i = 0; if (p - 1 >= 0 && tempIndex[p - 1] != -1) { 
    i = tempIndex[p - 1] + 1; } for (; i < data.length; i++) { 
    tempData[p] = data[i]; tempIndex[p] = i; dfs(p + 1, count + 1, ans); } } 

• 举个例子并列下递归的执行顺序，例如：4, 3, 2, 1。
• dfs for循环第一个 4 ，临时数据数组第一个位置为4， count也变成1，之后第二次递归又for循环， 临时数据数组第一个位置为3，count也变成2，得到4, 3，类推走完 4, 3, 2， 4, 3, 2, 1，4, 3, 1。
• 之后第二次递归的for循环走下一个，也就是临时数据第二个位置是源数组第三个位置，得到4, 2，再4, 2, 1结束。
• 之后第二次递归的for循环走最后一个，得到4, 1，整个第一个循环以4开头的就全部完成。
• 接下来第一个循环以3开头，顺序3，3, 2，3, 2, 1，3, 1。
• 继续第一个循环以2开头，顺序为2，2, 1。
• 最后第一次循环只剩下1。

2. 数组只能向上下左右感染的问题

– 先将上下左右的偏移数组列出来，循环用
– 需要有一个队列记录已感染位置，先进先处理的原则，并且处理后做标记已处理
– 用感染数增加到最后的值做判断得结论，或者有dp[]记录感染步骤得结论

static int[][] offsets = new int[][]{ 
   { 
   1, 0}, { 
   -1, 0}, { 
   0, 1}, { 
   0, -1}}; Queue<int[]> queue = new LinkedList<>(); queue.offer(p1); queue.offer(p2); int count = m * n - 2; // 已经有两个作为扩散点了 int[][] dp = new int[m][n]; dp[p1[0]][p1[1]] = 1; dp[p2[0]][p2[1]] = 1; int day = 1; while (!queue.isEmpty() && count > 0) { 
    int[] p = queue.poll(); // 弹出并获取到队列首部对象 int x = p[0]; int y = p[1]; day = dp[x][y] + 1; for (int[] offset : offsets) { 
    int newX = x + offset[0]; int newY = y + offset[1]; if (newX >= 0 && newX < m && newY >= 0 && newY < n && dp[newX][newY] == 0) { 
    dp[newX][newY] = day; queue.offer(new int[]{ 
   newX, newY}); count --; } } } System.out.println(day - 1);