算法训练——数组算法问题（LeetCodeHOT100）

448. 找到所有数组中消失的数字

package 数组问题算法;import java.util.ArrayList;
import java.util.List;public class findDisappearedNumbers448 {/*** 1 使用去判断的存入list 中的来判断是否存在 时间复杂度为0&＃xff08;n&＃xff09;* 2 对数组的数据进行排序&＃xff0c;然后再遍历一次* 3 由于 nums 的数字范围均在 [1,n] 中&＃xff0c;我们可以利用这一范围之外的数字&＃xff0c;来表达「是否存在」的含义。* 具体来说&＃xff0c;遍历 nums&＃xff0c;每遇到一个数 x&＃xff0c;就让 nums[x−1] 增加 nn。由于 nums中所有数均在 [1,n] 中&＃xff0c;增加以后&＃xff0c;这些数必然大于 n。* 最后我们遍历 nums&＃xff0c;若 nums[i] 未大于 n&＃xff0c;就说明没有遇到过数 i&＃43;1。这样我们就找到了缺失的数字。* &＃64;param nums* &＃64;return*/public List findDisappearedNumbers(int[] nums) {int n &＃61; nums.length;// 将数组作为hashmap 的存储 第一遍遍历的时候将数据设置为该for (int num : nums) {int x &＃61; (num - 1) % n;nums[x] &＃43;&＃61; n;}List ret &＃61; new ArrayList();for (int i &＃61; 0; i }


1. 两数之和

package 数组算法;import java.util.HashMap;public class twoSum1 {/*** 因为数组的只有一次出现的总的和结果** &＃64;param nums* &＃64;param target* &＃64;return*/public int[] twoSum(int[] nums, int target) {HashMap hashtable &＃61; new HashMap<>();for (int i &＃61; 0; i map &＃61; new HashMap<>();for (int i &＃61; 0; i }


53. 最大子数组和

最大的子数组和的数组&＃xff1f;

连续递增数组是怎么样的&＃xff1f;

package 数组算法;import java.util.ArrayList;public class maxSubArray53 {public int maxSubArray(int[] nums) {int max &＃61; nums[0];for (int i &＃61; 1; i }


121. 买卖股票的最佳时机

package 数组算法;import org.junit.Test;public class maxProfit121 {/*** 每次都是记录当前的最小的是 然后在判断的最大的值的是多少* 也是里利用栈的数据结构 但是利用了额外空间复杂度* 直接遍历也是可以* &＃64;param prices* &＃64;return*/public int maxProfit(int[] prices) {if (prices.length <&＃61; 0) {return 0;}int max &＃61; 0;int min &＃61; prices[0];for (int i &＃61; 1; i }


136. 只出现一次的数字

package 数组算法;public class singleNumber136 {/*** 使用list 存放 来判断是否存在 如果有那就是的如果没有的那就是不直接存储* 使用的数组的遍历方式** 排序后遍历的一次就一发现了 但是时间是的nlog(n)** 使用的是位运算的相关算法* &＃64;param nums* &＃64;return*/public int singleNumber(int[] nums) {int res&＃61;0;for (int i:nums){res^&＃61;i;}return res;}
}


169. 多数元素

上述两种方法 在时间和空间复杂度上或多或少都有一些不满足题目要求&＃xff0c;摩尔投票法可以时间复杂度为 O(n)、空间复杂度为 O(1) 要求解决该问题

比如有一组数字 用字母代替 x x y z m x x&＃xff0c;我们从头遍历&＃xff0c;计数为0的时候则记录当前数字且计数加1&＃xff0c;遇到和记录相同的数字则计数加1 和记录不同的数字则count减1 .

摩尔投票的核心就是不同数字之间的消耗&＃xff0c;无论y z m的计数是互相消耗 还是全部或者部分和x的计数消耗 最后剩下的记录的数字肯定是x
下面介绍下过程
        1 开始计数为0 记录x 计数&＃43;1&＃61;1
        2 x与记录相同均为x 计数&＃43;1&＃61;2
        3 y与记录不同 计数-1&＃61; 1
        4 z与记录不同 计数-1&＃61;0
        5 计数&＃61;0 记录m 计数&＃43;1&＃61;1
        6 x与记录不同 计数-1&＃61;0
        7 计数&＃61;0 记录x 计数&＃43;1&＃61;1

package 数组算法;import java.util.Arrays;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;public class majorityElement169 {/*** 可以采用的遍历的方式的*

* 但是也是可以将数组作为Hashmp的一种数据结构 来记录相关的顺序** &＃64;param nums* &＃64;return*/public int majorityElement(int[] nums) {// 排序中间的元素可定是大于一半以上的Arrays.sort(nums);return nums[nums.length >> 1];}/*** 采用的hashmap的表的来进行来判断** &＃64;param nums* &＃64;return*/public int majorityElementV2(int[] nums) {Map map &＃61; Arrays.stream(nums).boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));long limit &＃61; nums.length >> 1;for (Map.Entry entry : map.entrySet())if (entry.getValue() > limit)return entry.getKey();return -1;}/*** 摩尔投票的来实现** &＃64;param nums* &＃64;return*/public int majorityElementV3(int[] nums) {int count &＃61; 0;int curr &＃61; 0;for (int i &＃61; 0; i }


283. 移动零

package 数组算法;import org.junit.Test;public class moveZeroes283 {/*** 使用的遍历的方式 但是的这个是方法是n^2** &＃64;param nums*/public void moveZeroes(int[] nums) {for (int i &＃61; 0; i }


11. 盛最多水的容器

15. 三数之和

package 数组算法;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class threeSum15V2 {public List> threeSumV2(int[] nums) {List> lists &＃61; new ArrayList<>();if (nums.length <3 || nums &＃61;&＃61; null) {return lists;}Arrays.sort(nums);for (int i &＃61; 0; i 0) break;if (i > 0 && nums[i] &＃61;&＃61; nums[i - 1]) {continue;}int left &＃61; i &＃43; 1;int right &＃61; nums.length - 1;while (left }


39. 组合总和

class Solution {public List> combinationSum(int[] candidates, int target) {int len &＃61; candidates.length;List> res &＃61; new ArrayList<>();if (len &＃61;&＃61; 0) {return res;}// 排序是剪枝的前提Arrays.sort(candidates);Deque path &＃61; new ArrayDeque<>();dfs(candidates, 0, len, target, path, res);return res;}private void dfs(int[] candidates, int begin, int len, int target, Deque path, List> res) {// 由于进入更深层的时候&＃xff0c;小于 0 的部分被剪枝&＃xff0c;因此递归终止条件值只判断等于 0 的情况if (target &＃61;&＃61; 0) {res.add(new ArrayList<>(path));return;}for (int i &＃61; begin; i }

31. 下一个排列

33. 搜索旋转排序数组

package 数组算法;public class search33 {/*** 变性的二分法** &＃64;param nums* &＃64;param target* &＃64;return*/public int search(int[] nums, int target) {int n &＃61; nums.length;if (n &＃61;&＃61; 0) {return -1;}if (n &＃61;&＃61; 1) {return nums[0] &＃61;&＃61; target ? 0 : -1;}int left &＃61; 0, right &＃61; n - 1;while (left <&＃61; right) {int mid &＃61; (left &＃43; right) >> 1;if (nums[mid] &＃61;&＃61; target) {return mid;}// 判断中间值的大于0if (nums[left] <&＃61; nums[mid]) {// 左边有序的if (nums[0] <&＃61; target && target }


34. 在排序数组中查找元素的第一

class Solution {public int[] searchRange(int[] nums, int target) {// 左边的最开始的位置int leftIdx &＃61; binarySearch(nums, target, true);// 右边最开始的位置int rightIdx &＃61; binarySearch(nums, target, false) - 1;if (leftIdx <&＃61; rightIdx && rightIdx > 1;// 通过的lower的真假来控制的 具体的nums[mid] > taget 还是的nums[mid] target || (lower && nums[mid] >&＃61; target)) {right &＃61; mid - 1;ans &＃61; mid;} else {left &＃61; mid &＃43; 1;}}return ans;}
}

46. 全排列

package 数组算法;import java.util.ArrayList;
import java.util.List;public class permute46 {/*** 回溯算法** &＃64;param nums* &＃64;return*/public List> permute(int[] nums) {List> lists &＃61; new ArrayList<>();if (nums.length &＃61;&＃61; 0) {return lists;}boolean[] vis &＃61; new boolean[nums.length];dfs(nums, 0, new ArrayList(), lists, vis);return lists;}private void dfs(int[] nums, int index, ArrayList list, List> lists, boolean[] vis) {if (index &＃61;&＃61; nums.length) {if (!lists.contains(list)) {lists.add(new ArrayList<>(list));}return;}for (int i &＃61; 0; i }


48. 旋转图像

package 数组算法;public class rotate48 {/*** 将数组沿着 对角线的翻转 然后在沿着上翻转* 时间复杂度&＃xff1a;O(N2)O(N^2)O(N2)&＃xff0c;其中 NNN 是 matrix\textit{matrix}matrix 的边长。对于每一次翻转操作&＃xff0c;我们都需要枚举矩阵中一半的元素。* 空间复杂度&＃xff1a;O(1)O(1)O(1)。为原地翻转得到的原地旋转。*/public void rotate(int[][] matrix) {int n &＃61; matrix.length;// 水平翻转for (int i &＃61; 0; i }


55. 跳跃游戏

package 数组算法;public class canJump55 {/*** 贪心算法问题* 求解最大 最远 等问题……** &＃64;param nums* &＃64;return*/public boolean canJump(int[] nums) {// 记录可以到达的最远的位置int rightmost &＃61; 0;// 数组的长度int n &＃61; nums.length;for (int i &＃61; 0; i &＃61; n - 1) {return true;}}}return false;}
}


56. 合并区间

package 数组算法;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;public class merge56 {/*** &＃64;param intervals* &＃64;return*/public int[][] merge(int[][] intervals) {if (intervals.length &＃61;&＃61; 0) {return new int[0][2];}Arrays.sort(intervals, new Comparator() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});List merged &＃61; new ArrayList();for (int i &＃61; 0; i () {&＃64;Overridepublic int compare(int[] o1, int[] o2) {return o1[0] - o2[0];}});List list &＃61; new ArrayList<>();for (int i &＃61; 0; i

64. 最小路径和

package 数组算法;public class minPathSum64 {public int minPathSum(int[][] grid) {if (grid &＃61;&＃61; null || grid.length &＃61;&＃61; 0 || grid[0].length &＃61;&＃61; 0) {return 0;}int rows &＃61; grid.length, columns &＃61; grid[0].length;int[][] dp &＃61; new int[rows][columns];dp[0][0] &＃61; grid[0][0];for (int i &＃61; 1; i }


75. 颜色分类

78. 子集

package 数组算法;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class subsets78 {public List> subsets(int[] nums) {List> lists &＃61; new ArrayList<>();// 添加一个空的数组lists.add(new ArrayList<>());// 遍历数组for (int num : nums) {//每遍历一个元素就在之前子集中的每个集合追加这个元素&＃xff0c;让他变成新的子集for (int i &＃61; 0; i list &＃61; new ArrayList<>(lists.get(i));list.add(num);lists.add(list);}}return lists;}public List> subsetsV2(int[] nums) {List> lists &＃61; new ArrayList<>();lists.add(new ArrayList<>());for (int num : nums) {for (int i &＃61; 0; i list &＃61; new ArrayList<>(lists.get(i));// 添加当前的元素list.add(num);// 然后再添加回去lists.add(list);}}return lists;}
}


79. 单词搜索

package 数组算法;public class exist79 {// 定义好长度宽度private int len;private int row;// 返回的结果boolean flag &＃61; false;// 定义好四个方向int[] dx &＃61; {1, 0, -1, 0};int[] dy &＃61; {0, 1, 0, -1};// 定义时候被访问boolean[][] vis;// 需要遍历整个数组public boolean exist(char[][] board, String word) {len &＃61; board.length;if (len <&＃61; 0) {return flag;}row &＃61; board[0].length;vis &＃61; new boolean[len][row];for (int i &＃61; 0; i &＃61; len || y <0 || y >&＃61; row || word.charAt(index) !&＃61; board[x][y] || vis[x][y]&＃61;&＃61;true) {return;}// 开始访问vis[x][y] &＃61; true;for (int i &＃61; 0; i <4; i&＃43;&＃43;) {int xx &＃61; dx[i] &＃43; x;int yy &＃61; dy[i] &＃43; y;dfs(board, xx, yy, word, index &＃43; 1, vis);}// 回溯vis[x][y] &＃61; false;}
}


105. 从前序与中序遍历序列构造二叉

128. 最长连续序列

package 数组算法;import java.util.HashSet;
import java.util.Set;public class longestConsecutive128 {/*** 最长连续序列*

* 1 将数组排序 然后判断前面是否为后面的&＃43;1 如果是count&＃43;&＃43; 如果不是那就比较max值和count谁大 时间复杂度为nlog(n)*

* 2 将数组进行去重处理 然后再遍历一次数据存储在hashmap中 然后再进行一次遍历 通过判断这个数的下一个是否在map中的 然后在** &＃64;param nums* &＃64;return*/public int longestConsecutive(int[] nums) {// 去重进行处理Set num_set &＃61; new HashSet();for (int num : nums) {num_set.add(num);}// 最大的连续的长度是0int longestStreak &＃61; 0;// 遍历数组for (int num : num_set) {// 判断是否包含 当前的数组的小于1在set中 如果在那就设置if (!num_set.contains(num - 1)) {int currentNum &＃61; num;int currentStreak &＃61; 1;// 循环的判断时候存在数组大于1的while (num_set.contains(currentNum &＃43; 1)) {// 那就直接复制 同时将最长的值家那个1currentNum &＃43;&＃61; 1;currentStreak &＃43;&＃61; 1;}// 每次走完一个数组都更新一下当前最大长度longestStreak &＃61; Math.max(longestStreak, currentStreak);}}return longestStreak;}
}


152. 乘积最大子数组

198. 打家劫舍

200. 岛屿数量

详细的分析和结果&＃xff1a;算法训练——岛屿类问题&＃xff08;DFS框架&＃xff09;_庄小焱的博客-CSDN博客_岛屿问题算法

215. 数组中的第K个最大元素

221. 最大正方形

详细的分析和结果&＃xff1a;算法训练——动态规划问题_庄小焱的博客-CSDN博客

238. 除自身以外数组的乘积

class Solution {public int[] productExceptSelf(int[] nums) {int length &＃61; nums.length;// L 和 R 分别表示左右两侧的乘积列表int[] L &＃61; new int[length];int[] R &＃61; new int[length];int[] answer &＃61; new int[length];// L[i] 为索引 i 左侧所有元素的乘积// 对于索引为 &＃39;0&＃39; 的元素&＃xff0c;因为左侧没有元素&＃xff0c;所以 L[0] &＃61; 1L[0] &＃61; 1;for (int i &＃61; 1; i &＃61; 0; i--) {R[i] &＃61; nums[i &＃43; 1] * R[i &＃43; 1];}// 对于索引 i&＃xff0c;除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积for (int i &＃61; 0; i }

package 数组算法;/*** &＃64;Classname productExceptSelf238* &＃64;Description TODO* &＃64;Date 2022/3/22 8:01* &＃64;Created by xjl*/
public class productExceptSelf238 {public int[] productExceptSelf(int[] nums) {int length &＃61; nums.length;int[] answer &＃61; new int[length];// answer[i] 表示索引 i 左侧所有元素的乘积// 因为索引为 &＃39;0&＃39; 的元素左侧没有元素&＃xff0c; 所以 answer[0] &＃61; 1answer[0] &＃61; 1;for (int i &＃61; 1; i &＃61; 0; i--) {// 对于索引 i&＃xff0c;左边的乘积为 answer[i]&＃xff0c;右边的乘积为 Ranswer[i] &＃61; answer[i] * R;// R 需要包含右边所有的乘积&＃xff0c;所以计算下一个结果时需要将当前值乘到 R 上R *&＃61; nums[i];}return answer;}
}


240. 搜索二维矩阵 II

287. 寻找重复数

300. 最长递增子序列

309. 最佳买卖股票时机含冷冻期

322. 零钱兑换

347. 前 K 个高频元素

399. 除法求值

406. 根据身高重建队列

416. 分割等和子集

494. 目标和

560. 和为 K 的子数组

581. 最短无序连续子数组

621. 任务调度器

建立大小为 n&＃43;1 的桶子&＃xff0c;个数为任务数量最多的那个任务&＃xff0c;比如下图&＃xff0c;等待时间 n&＃61;2&＃xff0c;A 任务个数 6 个&＃xff0c;我们建立 6 桶子&＃xff0c;每个容量为 3&＃xff1a;
我们可以把一个桶子看作一轮任务

先从最简单的情况看起&＃xff0c;现在就算没有其他任务&＃xff0c;我们完成任务 A 所需的时间应该是 (6-1)*3&＃43;1&＃61;16&＃xff0c;因为最后一个桶子&＃xff0c;不存在等待时间。

接下来我们添加些其他任务

可以看到 C 其实并没有对总体时间产生影响&＃xff0c;因为它被安排在了其他任务的冷却期间&＃xff1b;而 B 和 A 数量相同&＃xff0c;这会导致最后一个桶子中&＃xff0c;我们需要多执行一次 B 任务&＃xff0c;现在我们需要的时间是 (6-1)*3&＃43;2&＃61;17.

前面两种情况&＃xff0c;总结起来&＃xff1a;总排队时间 &＃61; (桶个数 - 1) * (n &＃43; 1) &＃43; 最后一桶的任务数

当冷却时间短&＃xff0c;任务种类很多时

比如上图&＃xff0c;我们刚好排满了任务&＃xff0c;此时所需时间还是 17&＃xff0c;如果现在我还要执行两次任务 F&＃xff0c;该怎么安排呢&＃xff1f;

739. 每日温度