摘要
448. 找到所有数组中消失的数字
package 数组问题算法;
import java.util.ArrayList;
import java.util.List;
public class findDisappearedNumbers448 {
/**
* 1 使用去判断的存入list 中的来判断是否存在 时间复杂度为0（n）
* 2 对数组的数据进行排序，然后再遍历一次
* 3 由于 nums 的数字范围均在 [1,n] 中，我们可以利用这一范围之外的数字，来表达「是否存在」的含义。
* 具体来说，遍历 nums，每遇到一个数 x，就让 nums[x−1] 增加 nn。由于 nums中所有数均在 [1,n] 中，增加以后，这些数必然大于 n。
* 最后我们遍历 nums，若 nums[i] 未大于 n，就说明没有遇到过数 i+1。这样我们就找到了缺失的数字。
* @param nums
* @return
*/
public List findDisappearedNumbers(int[] nums) {
int n = nums.length;
// 将数组作为hashmap 的存储 第一遍遍历的时候将数据设置为该
for (int num : nums) {
int x = (num - 1) % n;
nums[x] += n;
}
List ret = new ArrayList();
for (int i = 0; i < n; i++) {
if (nums[i] 1];
}
/**
* 采用的hashmap的表的来进行来判断
*
* @param nums
* @return
*/
public int majorityElementV2(int[] nums) {
Map map = Arrays.stream(nums).boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
long limit = nums.length >> 1;
for (Map.Entry entry : map.entrySet())
if (entry.getValue() > limit)
return entry.getKey();
return -1;
}
/**
* 摩尔投票的来实现
*
* @param nums
* @return
*/
public int majorityElementV3(int[] nums) {
int count = 0;
int curr = 0;
for (int i = 0; i < nums.length; i++) {
if (count == 0) {
curr = nums[i];
count++;
} else if (curr == nums[i]) {
count++;
} else {
count--;
}
}
return curr;
}
}
283. 移动零
package 数组算法;
import org.junit.Test;
public class moveZeroes283 {
/**
* 使用的遍历的方式 但是的这个是方法是n^2
*
* @param nums
*/
public void moveZeroes(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] != 0) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
break;
}
}
}
}
}
/**
* 使用的双指针的效果
*
* @param nums
*/
public void moveZeroesV2(int[] nums) {
int n = nums.length, left = 0, right = 0;
while (right < n) {
if (nums[right] != 0) {
swap(nums, left, right);
left++;
}
right++;
}
}
public void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
public void moveZeroesV3(int[] nums) {
if (nums.length == 0) {
return;
}
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[index++] = nums[i];
}
}
for (int i = index; i < nums.length; i++) {
nums[i]=0;
}
}
@Test
public void test() {
moveZeroes(new int[]{0, 1, 0, 3, 12});
}
}
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 = new ArrayList();
if (nums.length 0) break;
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
lists.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return lists;
}
}
39. 组合总和
class Solution {
public List combinationSum(int[] candidates, int target) {
int len = candidates.length;
List res = new ArrayList();
if (len == 0) {
return res;
}
// 排序是剪枝的前提
Arrays.sort(candidates);
Deque path = 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) {
// 由于进入更深层的时候，小于 0 的部分被剪枝，因此递归终止条件值只判断等于 0 的情况
if (target == 0) {
res.add(new ArrayList(path));
return;
}
for (int i = begin; i < len; i++) {
// 重点理解这里剪枝，前提是候选数组已经有序，
if (target - candidates[i] < 0) {
break;
}
path.addLast(candidates[i]);
dfs(candidates, i, len, target - candidates[i], path, res);
path.removeLast();
}
}
}31. 下一个排列
33. 搜索旋转排序数组
package 数组算法;
public class search33 {
/**
* 变性的二分法
*
* @param nums
* @param target
* @return
*/
public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
int left = 0, right = n - 1;
while (left > 1;
if (nums[mid] == target) {
return mid;
}
// 判断中间值的大于0
if (nums[left] = target)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
}
}46. 全排列
package 数组算法;
import java.util.ArrayList;
import java.util.List;
public class permute46 {
/**
* 回溯算法
*
* @param nums
* @return
*/
public List permute(int[] nums) {
List lists = new ArrayList();
if (nums.length == 0) {
return lists;
}
boolean[] vis = 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 == nums.length) {
if (!lists.contains(list)) {
lists.add(new ArrayList(list));
}
return;
}
for (int i = 0; i < nums.length; i++) {
if (!vis[i]) {
vis[i] = true;
list.add(nums[i]);
dfs(nums, index + 1, list, lists, vis);
lists.remove(list.size() - 1);
vis[i] = false;
}
}
}
}
48. 旋转图像
package 数组算法;
public class rotate48 {
/**
* 将数组沿着 对角线的翻转 然后在沿着上翻转
* 时间复杂度：O(N2)O(N^2)O(N2)，其中 NNN 是 matrix\textit{matrix}matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。
* 空间复杂度：O(1)O(1)O(1)。为原地翻转得到的原地旋转。
*/
public void rotate(int[][] matrix) {
int n = matrix.length;
// 水平翻转
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < n; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - i - 1][j];
matrix[n - i - 1][j] = temp;
}
}
// 主对角线翻转
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
}
55. 跳跃游戏
package 数组算法;
public class canJump55 {
/**
* 贪心算法问题
* 求解最大 最远 等问题……
*
* @param nums
* @return
*/
public boolean canJump(int[] nums) {
// 记录可以到达的最远的位置
int rightmost = 0;
// 数组的长度
int n = nums.length;
for (int i = 0; i < n; ++i) {
if (i = 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 {
/**
* @param intervals
* @return
*/
public int[][] merge(int[][] intervals) {
if (intervals.length == 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 = new ArrayList();
for (int i = 0; i < intervals.length; ++i) {
int L = intervals[i][0];
int R = intervals[i][1];
// 当list等于空的时候的 或者是最后的一个元素的有点的元素小于左边的时候
if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
merged.add(new int[]{L, R});
} else {
// 否者就是将最后一个元素的右边设置为新的元素的右边的值
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
}
}
return merged.toArray(new int[merged.size()][]);
}
/**
* 将数据排序的 按照的顺序来实现的数据的存储
*
* @param intervals
* @return
*/
public int[][] mergeV1(int[][] intervals) {
if (intervals.length == 0) {
return new int[0][2];
}
Arrays.sort(intervals, new Comparator() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
List list = new ArrayList();
for (int i = 0; i < intervals.length; i++) {
int L = intervals[i][0];
int R = intervals[i][1];
if (list.size() == 0 || list.get(list.size() - 1)[1] < L) {
list.add(new int[]{L, R});
} else {
list.get(list.size() - 1)[1] = Math.max(list.get(list.size() - 1)[1], R);
}
}
return list.toArray(new int[list.size()][]);
}
}
64. 最小路径和
package 数组算法;
public class minPathSum64 {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length, columns = grid[0].length;
int[][] dp = new int[rows][columns];
dp[0][0] = grid[0][0];
for (int i = 1; i < rows; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int j = 1; j < columns; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[rows - 1][columns - 1];
}
}
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 = new ArrayList();
// 添加一个空的数组
lists.add(new ArrayList());
// 遍历数组
for (int num : nums) {
//每遍历一个元素就在之前子集中的每个集合追加这个元素，让他变成新的子集
for (int i = 0; i < lists.size(); i++) {
List list = new ArrayList(lists.get(i));
list.add(num);
lists.add(list);
}
}
return lists;
}
public List subsetsV2(int[] nums) {
List lists = new ArrayList();
lists.add(new ArrayList());
for (int num : nums) {
for (int i = 0; i < lists.size(); i++) {
// 获取每一个list的数组
List list = 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 = false;
// 定义好四个方向
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};
// 定义时候被访问
boolean[][] vis;
// 需要遍历整个数组
public boolean exist(char[][] board, String word) {
len = board.length;
if (len = len || y < 0 || y >= row || word.charAt(index) != board[x][y] || vis[x][y]==true) {
return;
}
// 开始访问
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int xx = dx[i] + x;
int yy = dy[i] + y;
dfs(board, xx, yy, word, index + 1, vis);
}
// 回溯
vis[x][y] = false;
}
}
105. 从前序与中序遍历序列构造二叉
128. 最长连续序列
package 数组算法;
import java.util.HashSet;
import java.util.Set;
public class longestConsecutive128 {
/**
* 最长连续序列
*
* 1 将数组排序 然后判断前面是否为后面的+1 如果是count++ 如果不是那就比较max值和count谁大 时间复杂度为nlog(n)
*
* 2 将数组进行去重处理 然后再遍历一次数据存储在hashmap中 然后再进行一次遍历 通过判断这个数的下一个是否在map中的 然后在
*
* @param nums
* @return
*/
public int longestConsecutive(int[] nums) {
// 去重进行处理
Set num_set = new HashSet();
for (int num : nums) {
num_set.add(num);
}
// 最大的连续的长度是0
int longestStreak = 0;
// 遍历数组
for (int num : num_set) {
// 判断是否包含 当前的数组的小于1在set中 如果在那就设置
if (!num_set.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
// 循环的判断时候存在数组大于1的
while (num_set.contains(currentNum + 1)) {
// 那就直接复制 同时将最长的值家那个1
currentNum += 1;
currentStreak += 1;
}
// 每次走完一个数组都更新一下当前最大长度
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}
152. 乘积最大子数组
198. 打家劫舍
200. 岛屿数量
详细的分析和结果：算法训练——岛屿类问题（DFS框架）_庄小焱的博客-CSDN博客_岛屿问题算法
215. 数组中的第K个最大元素
221. 最大正方形
详细的分析和结果：算法训练——动态规划问题_庄小焱的博客-CSDN博客
238. 除自身以外数组的乘积
class Solution {
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
// L 和 R 分别表示左右两侧的乘积列表
int[] L = new int[length];
int[] R = new int[length];
int[] answer = new int[length];
// L[i] 为索引 i 左侧所有元素的乘积
// 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
L[0] = 1;
for (int i = 1; i < length; i++) {
L[i] = nums[i - 1] * L[i - 1];
}
// R[i] 为索引 i 右侧所有元素的乘积
// 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
R[length - 1] = 1;
for (int i = length - 2; i >= 0; i--) {
R[i] = nums[i + 1] * R[i + 1];
}
// 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
for (int i = 0; i < length; i++) {
answer[i] = L[i] * R[i];
}
return answer;
}
}package 数组算法;
/**
* @Classname productExceptSelf238
* @Description TODO
* @Date 2022/3/22 8:01
* @Created by xjl
*/
public class productExceptSelf238 {
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
int[] answer = new int[length];
// answer[i] 表示索引 i 左侧所有元素的乘积
// 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
answer[0] = 1;
for (int i = 1; i < length; i++) {
answer[i] = nums[i - 1] * answer[i - 1];
}
// R 为右侧所有元素的乘积
// 刚开始右边没有元素，所以 R = 1
int R = 1;
for (int i = length - 1; i >= 0; i--) {
// 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
answer[i] = answer[i] * R;
// R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
R *= nums[i];
}
return answer;
}
}
240. 搜索二维矩阵 II
287. 寻找重复数
300. 最长递增子序列
309. 最佳买卖股票时机含冷冻期
322. 零钱兑换
347. 前 K 个高频元素
399. 除法求值
406. 根据身高重建队列
416. 分割等和子集
494. 目标和
560. 和为 K 的子数组
581. 最短无序连续子数组
621. 任务调度器
建立大小为 n+1 的桶子，个数为任务数量最多的那个任务，比如下图，等待时间 n=2，A 任务个数 6 个，我们建立 6 桶子，每个容量为 3： 我们可以把一个桶子看作一轮任务
先从最简单的情况看起，现在就算没有其他任务，我们完成任务 A 所需的时间应该是 (6-1)*3+1=16，因为最后一个桶子，不存在等待时间。
接下来我们添加些其他任务
可以看到 C 其实并没有对总体时间产生影响，因为它被安排在了其他任务的冷却期间；而 B 和 A 数量相同，这会导致最后一个桶子中，我们需要多执行一次 B 任务，现在我们需要的时间是 (6-1)*3+2=17.
前面两种情况，总结起来：总排队时间 = (桶个数 - 1) * (n + 1) + 最后一桶的任务数
当冷却时间短，任务种类很多时
比如上图，我们刚好排满了任务，此时所需时间还是 17，如果现在我还要执行两次任务 F，该怎么安排呢？
739. 每日温度
博文参考
