2021-11-04
有的时候真的是坚持做一件事非常难，再而衰，三而竭。
L75. 颜色分类
L75. 颜色分类
双指针解法，最开始写了一个双指针解法，发现除了点儿问题。没考虑到二次交换的问题
//[1,2,0]
public void sortColors(int[] nums) {
//0的指针
int z = 0;
//2的指针
int t = nums.length - 1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
//而前面0后面必定跟的是1，比如0，0，1，2，0
// 当前i如果指向2，则2会交换到后面去，所以当前位置不可能出现交换后
// 当前元素只有是0的时候会和前面的1交换，此时因为只可能是1，所以不存在二次交换的问题
swap(nums, z++, i);
} else if (nums[i] == 2 && i < t) {
swap(nums, t--, i);
//因为新换过来的数可能是0，那么久还可能再交换一次
i--;
}
}
}
public void swap(int[] nums, int i, int j) {
if (i == j) {
return;
}
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}
2021-11-05
今天刷了两道简单题，不过都挺有意思的
543. 二叉树的直径
第一次见到这道题的时候，觉得很复杂，没啥思路，今天认真想了一下，你会发现要想使得路径最长，一定是一个点为基准，分别向左子树方向和右子树方向走出的最长路径，再加起来。因为dfs只能递归高度给上层调用，那么就还需要另外一个遍历记录最大路径。如果是java支持多返回值，或许就不用全局变量来记录最大路径的值了。
class Solution {
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
diameterOfBinaryTreeDepth(root);
return max;
}
public int diameterOfBinaryTreeDepth(TreeNode root) {
if (root == null ) {
return 0;
}
int r = diameterOfBinaryTreeDepth(root.right);
int l = diameterOfBinaryTreeDepth(root.left);
max = Math.max(max, r+l);
return Math.max(l, r) + 1;
}
}
283. 移动零
283. 移动零
自己想的最直接的方法肯定是把0直接往尾部较换，但因为其他元素得保持位置，所以想了半天还是没相处指针的解法。该题目明确说了不能复制数组，后来实在没找，想了一个map，其实还是复制数组，这个方法的原始思路就是，你能明确的知道最终每个元素的索引都是什么位置了，但完全没用，得开一个新数组来赋值，或者就是map了。算是不太满足要求。
class Solution {
public void moveZeroes(int[] nums) {
//int index[] = new int[nums.length];
Map<Integer,Integer> map= new HashMap<>();
//普通位置的偏移量
int flow = 0;
//高位0的占位偏移
int t = nums.length - 1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
flow++;
map.put(t--,nums[i]);
} else {
map.put(i - flow,nums[i]);
}
}
for (int i = 0; i < nums.length; i++) {
nums[i]= map.get(i);
}
}
}
看了其他网友得解。思路是：把不是0的数字往前换，换第一个0，如果前面没有0都可以不换。h指针记录第一个0，但如果第一个不是0，可以不换，也可以换，但h指针只要遇到不是指针就往后移动
class Solution {
public void moveZeroes(int[] nums) {
//h需要通第一个元素较换的非0元素
int h = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
swap(nums, i, h);
h++;
}
}
}
public void swap(int[] nums, int i, int j) {
if (i == j) {
return;
}
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}
}
上面这个还有个技巧，因为总是和0较换，所以可以直接把所有不为0的元素往前移动，最后补充后面的0就可以了。这里要记录需要补多少0，较换完所有的元素h指针指向第一个要赋值为0的位置
public void moveZeroes(int[] nums) {
int h = 0;
int i = 0;
while (i < nums.length) {
if (nums[i] != 0) {
nums[h++] = nums[i];
}
i++;
}
for(;h<nums.length;h++){
nums[h]=0;
}
}
2021-11-05
1218. 最长定差子序列
做过最长递增子序列的同学肯定想都不想就写出了下面的解法。
class Solution {
public int longestSubsequence(int[] arr, int difference) {
if (arr == null) {
return 0;
}
int dp[] = new int[arr.length];
int max = 1;
for (int i = 0; i < arr.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (arr[i] - arr[j] == difference) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
max = Math.max(dp[i], max);
}
return max;
}
}
提交之后，用例超时，这里注意到整个时间复杂度还是O(n2)，数据量大，题目下方还有数据规模说明。在没有想到其他方法的情况下我用优先级队列，来做中间这个循环的优化，这样不用比较所有的前面的元素了
class Solution {
public int longestSubsequence(int[] arr, int difference) {
if (arr == null) {
return 0;
}
PriorityQueue<Integer[]> queue = new PriorityQueue<Integer[]>((o1, o2) -> o2[1] - o1[1]);
int dp[] = new int[arr.length];
int max = 1;
for (int i = 0; i < arr.length; i++) {
dp[i] = 1;
PriorityQueue<Integer[]> cp = new PriorityQueue<Integer[]>(queue);
while (!cp.isEmpty()) {
Integer[] e = cp.poll();
int j = e[0];
if (arr[i] - arr[j] == difference) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
queue.add(new Integer[]{i, dp[i]});
max = Math.max(dp[i], max);
}
return max;
}
}
完全没用。考虑到这里因为有的用例基本上没有连续等差子序列，这种优先级排序基本没多大的优化效果。最后看了一下map的解法.
我是之前从dp数组来的，这题感觉固定思维了，开始写了个连续递增序列的思路超时了，就是没想到这里等差，还能运用和两束之和的思想。两数之和，两数之差，等差，都能map降维
class Solution {
public int longestSubsequence(int[] arr, int difference) {
Map<Integer, Integer> dpm = new HashMap<>();
//引入dp数组，只为更贴近之前做的dp，方便理解一些
int dp[] = new int[arr.length];
int max = 1;
for (int i = 0; i < arr.length; i++) {
int v = arr[i];
if (dpm.containsKey(v)) {
dp[i] = dpm.get(v);
} else {
dp[i] = 1;
}
dpm.put(v + difference, dp[i] + 1);
max = Math.max(dp[i], max);
}
return max;
}
}
2021-11-05
最大子矩阵
public class Solution {
/**
* @param matrix: the given matrix
* @return: the largest possible sum
*/
public int maxSubmatrix(int[][] matrix) {
// write your code here
if(matrix==null||matrix.length==0|| matrix[0].length==0)
return 0;
int h = matrix.length;
int w = matrix[0].length;
int[][] m = new int[h][w+1];
for (int i = 0; i < h; i++) {
for (int j = 1; j <=w; j++) {
m[i][j] = m[i][j - 1] + matrix[i][j-1];
}
}
int max = 0;
for (int f = 0; f < h; f++) {
for (int l = f+1; l <=w; l++) {
int childMax = 0;
for (int i = 0; i < h; i++) {
int x = m[i][l] - m[i][f];
if(x+childMax<=0){
childMax=0;
}else{
childMax= childMax+x;
max= Math.max(childMax,max);
}
}
}
}
//System.out.println(max);
return max;
}
}
这题是一本通中的一道动态规划，咋看这个题的题解是没啥dp的样子，但用到了前缀和，前缀和是dp的一个知识点。这题大的结构上还用到了贪心策略。这个解法有个小问题，就是如果所有元素都是负数，这个答案是有问题的，还需要调整一下。
2021-11-17
剑指 Offer II 052. 展平二叉搜索树
class Solution {
TreeNode h = new TreeNode(-1);
TreeNode cur =h;
public TreeNode increasingBST(TreeNode root) {
dfs(root);
cur.left=null;
return h.right;
}
public void dfs(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
dfs(root.left);
}
cur.left = null;
cur.right = root;
cur = root;
if (root.right != null) {
dfs(root.right);
}
}
}
这题如果用普通的解法，就直接遍历构造。而上面这个解法是比较秀的。感觉很像连表迭代。但这个题还要注意一点，dfs后，一定要把cur.left赋值为null，不然可能出现环。比如如下树。因为最后遍历的节点是4，遍历完之后就直接跳出dfs了，而此时4的右边节点还是引用着3节点。
2
/
1 4
/
3
2021-11-18
二叉搜索树中两个节点之和
二叉搜索树中两个节点之和
这道题第一种比较好想得解法是，先遍历所有节点，把所有节点放到数组里，这样这道题就转换为两数之和了。下面这种方法是两数之和的变形，避免了重复计算的问题，最多的情况一次遍历搞定。
class Solution {
public boolean findTarget(TreeNode root, int k) {
//Map<Integer,Integer> map= new HashMap<>();
Set<Integer> set = new HashSet<>();
return dfs(root,k,new HashSet<>());
}
public boolean dfs(TreeNode root, int k, Set<Integer> set) {
if (root == null)
return false;
if (set.contains(root.val)) {
return true;
}
set.add(k - root.val);
return dfs(root.left, k, set)||dfs(root.right, k, set);
}
}
剑指 Offer 34. 二叉树中和为某一值的路径
剑指 Offer 34. 二叉树中和为某一值的路径
dfs和回溯法，不断收集定点到根节点的路径
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int target) {
List<List<Integer>> st = new ArrayList<>();
List<Integer> c = new ArrayList<>();
dfs(root,target,st,c,0);
return st;
}
public void dfs(TreeNode root, int target, List<List<Integer>> st, List<Integer> c, int sum) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
if (sum + root.val == target) {
ArrayList<Integer> path = new ArrayList<>(c);
path.add(root.val);
st.add(path);
}
return;
}
c.add(root.val);
if (root.left != null) {
dfs(root.left, target, st, c, sum + root.val);
}
if (root.right != null) {
dfs(root.right, target, st, c, sum + root.val);
}
//回溯后一定要移除当前节点，因为当前节点在最后一个，所以移除最后一个
c.remove(c.size()-1);
}
}
2021-11-25
92 · 背包问题
92 · 背包问题
这道最原始背包问题，在我之前写过一下，以前对动态规划理解不够深，代码写得比较复杂了。经过大规模的训练之后，能把这块写的相对简单易于理解了。
- 1.dp[i]代表重量和为i是否能够拼出来，则dp[0]=true是一个初始化
- 2.每次拿着当前已经拼凑好的dp[i]去和新的物品凑新重量，因为这里dp[i]=true的情况只能在当前这轮的最大值以内产生，所以边界值是curMax=max
- 3.遍历dp[j]时，j一定不能从0到curMax，一定是从大到小的，不然将会出现一个物品被塞入两次的情况。比如【5,1,3,3】的物品，当i=3时，因为dp[1]=true推导出dp[4]=true，接下来又会遍历到dp[4]=true推导出dp[7]=true，事时上dp[4]是当前这个3加入背包后产生的，再次加入就相当于加入两次。
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
public int backPack(int m, int[] A) {
// write your code here
//n个物件的重量放在 A数组中
boolean[] dp = new boolean[m + 1];
dp[0] = true;
int max = 0;
for (int i : A) {
int curMax = max;
for (int j = curMax; j >= 0; j--) {
if (dp[j] && j + i <= m) {
max = Math.max(j + i, max);
dp[j + i]=true;
}
}
}
return max;
}
}
2021-11-26
125 · 背包问题（二）
125 · 背包问题（二）
本道题才是背包问题的本来的面目。也就是经典的0,1背包问题。前面的背包问题，仅仅考虑重量。
这里考虑dp[i] 代表 背包装i重量的体积的最大价值是多少。
往后推：dp[j + A[i]] = Math.max(dp[j + A[i]], dp[j] + V[i]);
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @param V: Given n items with value V[i]
* @return: The maximum value
*/
public int backPackII(int m, int[] A, int[] V) {
//write your code here
int dp[] = new int[m + 1];
int mv = 0;
for (int i = 0; i < A.length; i++) {
int cw = A[i];
for (int j = m; j >= 0; j--) {
if (j == 0 || dp[j] > 0 && j + cw <= m) {
dp[j + cw] = Math.max(dp[j + cw], dp[j] + V[i]);
mv = Math.max(mv, dp[j + cw]);
}
}
}
return mv;
}
}
另外一种往前推的 状态转移
dp[j]= dp[j-A[i]]+ V[i] 满足的条件是j这个体积够装A[i] 这个重量
public class P1267_3 {
public int backPackII(int m, int[] A, int[] V) {
// write your code here
int dp[] = new int[m + 1];
//dp[j]表示选择了第i个元素时， 重量为j时的最大价值
dp[0] = 0;
int max=0;
for (int i = 0; i < A.length; i++) {
for (int j = m; j >= 0; j--) {
if (j >= A[i]){
dp[j] = Math.max(dp[j - A[i]] + V[i], dp[j]);
max=Math.max(max,dp[j]);
}
}
}
return max;
}
}