刷题记录 2

7.7

433. 最小基因变化 - 力扣（LeetCode）

图的广度优先遍历的题大多都是用队列存储每轮搜索到的结点,再用一个visited记录已经搜索过的结点 理解了其实思路都差不多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        if (startGene.equals(endGene)) {return 0;}
        Set<String> visited = new HashSet<String>();
        Set<String> bankSet = new HashSet<String>(Arrays.asList(bank));
        if (!bankSet.contains(endGene)) {return -1;}
        char[] keys = {'A', 'C', 'G', 'T'};
        bankSet.add(startGene);
        Queue<String> queue = new ArrayDeque<>();
        queue.add(startGene);
        visited.add(startGene);
        int ans = 0;
        while(!queue.isEmpty()){
            ans++;
            int size = queue.size();
            for(int i=0;i<size;i++){
                String gene = queue.poll();
                for(int j = 0;j<8;j++){
                    for(int k=0;k<4;k++){
                        if(keys[k]!=gene.charAt(j)){
                            StringBuilder s = new StringBuilder(gene);
                            s.setCharAt(j,keys[k]);
                            String str = s.toString();
                            if(!visited.contains(str)&&bankSet.contains(str)){
                                if(s.toString().equals(endGene)) return ans;
                                visited.add(str);
                                queue.add(str);
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
}

127. 单词接龙 - 力扣（LeetCode）

感觉和上一道题差不多 字符串的长度和keys不一样而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (beginWord.equals(endWord)) {return 1;}
        Set<String> visited = new HashSet<String>();
        Set<String> bankSet = new HashSet<String>(wordList);
        if (!bankSet.contains(endWord)) {return 0;}
        char[] keys = new char[26];
        for(int i=0;i<26;i++){keys[i] = (char) ('a'+i);}
        bankSet.add(beginWord);
        Queue<String> queue = new ArrayDeque<>();
        queue.add(beginWord);
        visited.add(beginWord);
        int ans = 1;
        while(!queue.isEmpty()){
            ans++;
            int size = queue.size();
            for(int i=0;i<size;i++){
                String gene = queue.poll();
                for(int j = 0;j<gene.length();j++){
                    for(int k=0;k<26;k++){
                        if(keys[k]!=gene.charAt(j)){
                            StringBuilder s = new StringBuilder(gene);
                            s.setCharAt(j,keys[k]);
                            String str = s.toString();
                            if(!visited.contains(str)&&bankSet.contains(str)){
                                if(s.toString().equals(endWord)) return ans;
                                visited.add(str);
                                queue.add(str);
                            }
                        }
                    }
                }
            }
        }
        return 0;
    }
}

有一个优化搜索空间的方法: 双向BFS 简单来说就是两个队列分别从起点和终点双向bfs 当访问到已经被访问过的结点就说明遍历到了 这有三叶姐的说明: 127. 单词接龙 - 力扣（LeetCode）

70. 爬楼梯 - 力扣（LeetCode）

最简单的动态规划 每级台阶 = 前一级台阶走一步 + 前前一级台阶走两步 也就是前一级台阶的方法数加前前一级台阶的方法数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int climbStairs(int n) {
        if(n==1) return 1;
        else if(n==2) return 2;
        else{
            int step1=1,step2=2;boolean flag = true;
            for(int i=3;i<=n;i++){
                if(flag) step1 += step2;
                else step2+=step1;
                flag = !flag;
            }
            return Math.max(step1, step2);
        }
    }
}

198. 打家劫舍 - 力扣（LeetCode）

根据前两家是否被打劫和到前两家最多能打劫多少决定目前这家要不要打劫 因为只需要关注两家所以可以用队列 list也可以不过空间和维护有一个会比较差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int rob(int[] nums) {
        if(nums.length==1) return nums[0];
        else if(nums.length==2) return Math.max(nums[0],nums[1]);
        Queue<int[]> dp = new ArrayDeque<>();
        int []one = {nums[0],0},two = {Math.max(nums[0],nums[1]),nums[0]>nums[1]?0:1};
        dp.add(one);dp.add(two);
        for(int i=2;i<nums.length;i++){
            int[] ll = dp.remove(),l = dp.peek();
            int maxLL=ll[0]+nums[i],maxL;
            if(l[1]==1)maxL = l[0];
            else maxL = l[0]+nums[i];
            if(maxLL>maxL){
                ll[0] = maxLL;ll[1]=1;
                dp.add(ll);
            }else{
                ll[0]=maxL;ll[1]=l[1]==1?0:1;
                dp.add(ll);
            }
        }
        dp.remove();
        return dp.remove()[0];
    }
}

139. 单词拆分 - 力扣（LeetCode）

我写的是BFS解, 用动态规划和DFS也能解, set记忆访问过的字符串剪枝搜索空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>();
        Queue<String> dp = new ArrayDeque<>();
        dp.add(s);set.add(s);
        while(!dp.isEmpty()){
            for(int i=0;i< dp.size();i++){
                String sss = dp.remove();
                for(String str:wordDict){
                    String ss = sss;
                    if(str.length()<=ss.length()&&str.equals(ss.substring(0,str.length()))&&!set.contains(ss.substring(str.length()))){
                        if(ss.substring(str.length()).equals("")) return true;
                        dp.add(ss.substring(str.length()));set.add(ss.substring(str.length()));
                    }
                }
            }
        }
        return false;
    }
}

又写了个动态规划版本的 不过时间复杂度和空间都不如BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length()];
        for(int i=0;i<s.length();i++){
            for(int k=0;k<=i;k++){
                if(k==0||dp[k-1]){
                    String str = s.substring(k,i+1);
                    if(words.contains(str)){
                        dp[i] = true;break;
                    }
                }
            }
        }
        return dp[s.length()-1];
    }
}

7.8

322. 零钱兑换 - 力扣（LeetCode）

dp 边界条件不好弄 该换数组初始值时就换 不然又要加一堆条件判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//辣鸡 一堆条件判断 时间损失还大
class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount==0) return 0;
        if(coins.length==1) return amount%coins[0]==0?amount/coins[0]:-1;
        int [] dp = new int[amount+1];
        for(int i=1;i<=amount;i++){
            for(int k=0;k<coins.length;k++){
                if(i-coins[k]==0||(i-coins[k]>0&&dp[i-coins[k]]!=0))
                    if(dp[i]==0)
                        dp[i]=dp[i-coins[k]]+1;
                    else
                        dp[i]=Math.min(dp[i-coins[k]]+1,dp[i]);
            }
        }
        return dp[amount]!=0?dp[amount]:-1;
    }
}

//设置数组初始值 非常好写
class Solution {
    public int coinChange(int[] coins, int amount) {
        int result[] = new int[amount+1];
        Arrays.fill(result, 100_000);
        result[0] = 0;
      
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                result[i] = Math.min(result[i], result[i - coin] + 1);
            }
        }
      
        return result[amount] != 100_000 ? result[amount] : -1;
    }
}

300. 最长递增子序列 - 力扣（LeetCode）

dp 无语了 提交一看一堆人比我快几十毫秒 一看算法好像也没有优化很多啊? 一运行才发现原来数据集改过了😅

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int lengthOfLIS(int[] nums) {
        int []dp = new int[nums.length];
        int ans=0;
        Arrays.fill(dp,1);
        for(int i=0;i<nums.length;i++){
            for(int k=0;k<i;k++){
                if(nums[k]<nums[i])
                    dp[i] = Math.max(dp[k]+1,dp[i]);
            }
            ans = Math.max(dp[i],ans);
        }
        return ans;
    }
}

还有一种dp+二分查找的解法 时间复杂度O(N*logN) 普通dp是O(N^2) 比较好的说明:最长递增子序列（nlogn 二分法、DAG 模型 和 延伸问题） | 春水煎茶 (writings.sh)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int lengthOfLIS(int[] nums) {
        //用来存储所有长度递增子序列的最小尾值
        int[] tails = new int[nums.length];
        //记录最长递增子序列的长度
        int res = 0;
        for(int num : nums) {
            int i = 0, j = res;
            //二分查找
            while(i < j) {
                int m = (i + j) / 2;
                if(tails[m] < num) i = m + 1;
                else j = m;
            }
            //更新下标为i的位置的元素为num
            tails[i] = num;
            //如果当前的j == res说明，num 被添加到 tails 数组的最后
            //res加一
            if(res == j) res++;
        }
        return res;
    }
}

215. 数组中的第K个最大元素 - 力扣（LeetCode）

自己写的用了大顶堆 时间复杂度O(Nlogk) 能过但是没到题目要求的O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findKthLargest(int[] nums, int k) {
        //将大顶堆大小定义为k，并重写类函数
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b){
                return b - a;	//大顶堆：参数2-参数1；小顶堆：参数1-参数2
            }
        });
        for(int num:nums) queue.add(num);
        for(int i=0;i<k-1;i++) queue.remove();
        return queue.remove();
    }
}

看了别人的题解 可以用桶排序 完美符合题目要求的O(N) 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int[] buckets = new int[20001];
        for (int i = 0; i < nums.length; i++) {
            buckets[nums[i] + 10000]++;
        }
        for (int i = 20000; i >= 0; i--) {
            k -= buckets[i];
            if (k <= 0) {
                return i - 10000;
            }
        }
        return 0;
    }
}

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

简单分治 划分数组为 left mid right 三部分分别建树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return fun(nums,new int[]{0,nums.length-1});
    }
    public TreeNode fun(int []nums, int []index){
        if(index[0]>index[1]) return null;
        if(index[0]==index[1]) return new TreeNode(nums[index[0]]);
        int mid = (index[0]+index[1])/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = fun(nums, new int[]{index[0], mid - 1});
        root.right = fun(nums, new int[]{mid + 1, index[1]});
        return root;
    }
}

33. 搜索旋转排序数组 - 力扣（LeetCode）

image-20240708230506877

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    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 l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

7.9

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

三次二分 第一次找到target 第二次找target左边的分界点 第三次找右边的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length==0) return new int[]{-1,-1};
        if(nums.length==1) return nums[0]==target?new int[]{0,0}:new int[]{-1,-1};
        int l=0,r= nums.length-1;
        int index1=-1,indexL=-1,indexR=-1;
        while(l<=r){
            int mid = l+(r-l)/2;
            if(nums[mid]==target) {index1 = mid;break;}
            if(nums[mid]<target){l = mid+1;}
            else{r = mid-1;}
        }
        if(index1==-1) return new int[]{-1,-1};
        l=0;r=index1;
        if(nums[0]==target) indexL=0;
        else
            while(l<=r){
                int mid = l+(r-l)/2;
                if(nums[mid]==target&&nums[mid-1]<target) {indexL = mid;break;}
                if(nums[mid]<target){l = mid+1;}
                else{r = mid-1;}
            }
        l=index1;r= nums.length-1;
        if(nums[nums.length-1]==target) indexR=nums.length-1;
        else
            while(l<=r){
                int mid = l+(r-l)/2;
                if(nums[mid]==target&&nums[mid+1]>target) {indexR = mid;break;}
                if(nums[mid]<=target){l = mid+1;}else{r = mid - 1;}
            }
        return new int[]{indexL,indexR};
    }
}

然而实际上只用两次二分就好了 第一次找第一个等于target的 第二次找最后一个等于target的 来源

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// 两次二分查找，分开查找第一个和最后一个
 // 时间复杂度 O(log n), 空间复杂度 O(1)
 // [1,2,3,3,3,3,4,5,9]
 public int[] searchRange2(int[] nums, int target) {
   int left = 0;
   int right = nums.length - 1;
   int first = -1;
   int last = -1;
   // 找第一个等于target的位置
   while (left <= right) {
     int middle = (left + right) / 2;
     if (nums[middle] == target) {
       first = middle;
       right = middle - 1; //重点
     } else if (nums[middle] > target) {
       right = middle - 1;
     } else {
       left = middle + 1;
     }
   }

   // 最后一个等于target的位置
   left = 0;
   right = nums.length - 1;
   while (left <= right) {
     int middle = (left + right) / 2;
     if (nums[middle] == target) {
       last = middle;
       left = middle + 1; //重点
     } else if (nums[middle] > target) {
       right = middle - 1;
     } else {
       left = middle + 1;
     }
   }

   return new int[]{first, last};
 }

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

又是一道非有序数组用二分的

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findMin(int[] nums) {
        if(nums.length==1) return nums[0];
        int l=0,r=nums.length-1;
        while(l<=r){
            int mid = (r+l)/2;
            //l为断点的情况 直接返回nums[l]
            if(nums[mid]>=nums[l]&&nums[r]>=nums[l]) return nums[l];
            else{
                //为了下面l和r能等于mid 这里加个判断
                if(r-l==1) return Math.min(nums[l],nums[r]);
                //l不是断点的情况 注意l和r要等于mid mid可能是断点
                if(nums[mid]>=nums[l]){l=mid;}
                else{r=mid;}
            }
        }
        return nums[0];
    }
}

373. 查找和最小的 K 对数字 - 力扣（LeetCode）

一开始暴力 直接爆内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    class KY{
        int a,b;
        int value;
        KY(int a,int b){this.a=a;this.b=b;value=a+b;}
    }
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<KY> queue = new PriorityQueue<>(new Comparator<KY>() {
            @Override
            public int compare(KY o1, KY o2) {
                return o1.value - o2.value;
            }
        });
        int limit1 = Math.min(k,nums1.length),limit2 = Math.min(k,nums2.length);
        for(int i=0;i<limit1;i++){
            for(int j=0;j<limit2;j++){
                queue.add(new KY(nums1[i],nums2[j]));
            }
        }KY ky ;
        List<List<Integer>> ans = new ArrayList<>();
        for(int i=0;i<k;i++){
            ky = queue.remove();
            List<Integer> nums = new ArrayList<>();
            nums.add(ky.a);nums.add(ky.b);
            ans.add(nums);
        }
        return ans;
    }
}

看了半天题解才理解是什么意思 简单来说就是一边出一边进 维护一个链表 利用小顶堆的性质每次出的时候就知道下个要进哪两个下标 同时在最开始就把一条链表上的下标队全进堆 比较难理解 下面是链表维护的图解:

一开始进堆:

1642133430-NIIiwX-学生登录用例图 (10)(1)

出堆之后有两种可能 因为最小堆的性质不用处理自动就知道是 图1 还是 图2

1642133430-NIIiwX-学生登录用例图 (10)(2)

1642133430-NIIiwX-学生登录用例图 (10)(3)

以此类推一直出到k个下标对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(k, (o1, o2)->{
            return nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]];
        });
        List<List<Integer>> ans = new ArrayList<>();
        int m = nums1.length;
        int n = nums2.length;
        for (int i = 0; i < Math.min(m, k); i++) {
            queue.offer(new int[]{i,0});
        }
        while (k-- > 0 && !queue.isEmpty()) {
            int[] idxPair = queue.poll();
            List<Integer> list = new ArrayList<>();
            list.add(nums1[idxPair[0]]);
            list.add(nums2[idxPair[1]]);
            ans.add(list);
            if (idxPair[1] + 1 < n) {
                queue.offer(new int[]{idxPair[0], idxPair[1] + 1});
            }
        }
        return ans;
    }
}

53. 最大子数组和 - 力扣（LeetCode）

一种解法: 简单dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length==1) return nums[0];
        int []dp = new int[nums.length];
        dp[0]=nums[0];
        int ans = dp[0];
        for(int i=1;i<nums.length;i++){
            if(nums[i]+dp[i-1]>nums[i]) dp[i]=nums[i]+dp[i-1];
            else dp[i] = nums[i];
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
}

第二种: 分治 也称Kadane 算法 这次官解破天荒的讲得还行 官解

image-20240710001649481

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r) {
            return new Status(a[l], a[l], a[l], a[l]);
        }
        int m = (l + r) >> 1;
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    public Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }
}

第三: 写完下面那道题我才发现 根本不用维护dp数组啊 只要维护一个最大子数组和就行了

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxSubArray(int[] nums) {
       int maxSum = nums[0], curMax = 0;
        for (int a : nums) {
            curMax = Math.max(curMax + a, a);
            maxSum = Math.max(maxSum, curMax);
        }
        return maxSum;
    }
}

918. 环形子数组的最大和 - 力扣（LeetCode）

这题解写得真是太牛逼了 比官解强100个官解 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxSubarraySumCircular(int[] A) {
        int total = 0, maxSum = A[0], curMax = 0, minSum = A[0], curMin = 0;
        for (int a : A) {
            curMax = Math.max(curMax + a, a);
            maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(curMin + a, a);
            minSum = Math.min(minSum, curMin);
            total += a;
        }
        return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
    }
}

7.10

17. 电话号码的字母组合 - 力扣（LeetCode）

一开始一直想用queue存储 浪费了半天

有点像深度优先遍历 其实就是StringBuilder用完一个字符之后删掉再用下一个字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public List<String> letterCombinations(String digits) {
        if(digits.length()==0) return new ArrayList<>();
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        List<Character> queue = new ArrayList<>();
        for(char ch : digits.toCharArray()) queue.add(ch);
        List<String> ans = new ArrayList<>();
        getString(new StringBuilder(),ans,queue,phoneMap,0);
        return ans;
    }
    public void getString(StringBuilder str,List<String> list,List<Character> queue,Map<Character, String> phoneMap,int index){
        char []chars = phoneMap.get(queue.get(index)).toCharArray();
        if(index==queue.size()-1){
            for(char ch:chars){
                str.append(ch);
                list.add(str.toString());
                str.deleteCharAt(str.length()-1);
            }return;
        }
        for(char ch:chars){
            str.append(ch);
            getString(str,list,queue,phoneMap,index+1);
            str.deleteCharAt(str.length()-1);
        }
    }
}

77. 组合 - 力扣（LeetCode）

dfs遍历 话说回溯跟我原来想的不太一样啊 原来回溯是指操作完一个状态之后回溯到上个状态再接着操作啊 我还以为是指递归的回溯呢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> combines = new ArrayList<>();
        List<Integer> combine = new ArrayList<>();
        dfs(combines,combine,n,k);
        return combines;
    }
    public void dfs(List<List<Integer>> combines,List<Integer> combine,int n,int k){
        if(n-k>=0){
            if(k==1){
                for(int i=n;i>=1;i--){
                    List<Integer> nums = new ArrayList<>(combine);
                    nums.add(i);
                    combines.add(nums);
                }
                return;
            }
            for(int i=n;i>=1;i--){
                combine.add(i);
                dfs(combines,combine,i-1,k-1);
                combine.remove(combine.size()-1);
            }
        }
    }
}

46. 全排列 - 力扣（LeetCode）

用了类似上面两题的解法 结果超慢啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> permutes = new ArrayList<>();
        List<Integer> permute = new ArrayList<>();
        Set<Integer> set = new HashSet<>();int k=nums.length;
        dfs(permutes,permute,set,k,nums);
        return permutes;
    }
    // set用来记录用了哪些数字 k用来记录还要排列几个数字
    public void dfs(List<List<Integer>> permutes,List<Integer> permute,Set<Integer> set,int k,int[] nums){
        if(k==1){
            for(int i=0;i<nums.length;i++){
                if(!set.contains(nums[i])) {
                    List<Integer> list=new ArrayList<>(permute);
                    list.add(nums[i]);permutes.add(list);
                    return;
                }
            }
        }
        for(int i=0;i<nums.length;i++){
            if(!set.contains(nums[i])) {
                permute.add(nums[i]);set.add(nums[i]);
                dfs(permutes,permute,set,k-1,nums);
                permute.remove(permute.size()-1);
                set.remove(nums[i]);
            }
        }
    }
}

看了一下别人的题解 发现问题在我用了set记录用过的数字 改用bool数组直接快一倍 击败96%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> permutes = new ArrayList<>();
        List<Integer> permute = new ArrayList<>();
        boolean[] set = new boolean[nums.length];int k=nums.length;
        dfs(permutes,permute,set,k,nums);
        return permutes;
    }
    // set用来记录用了哪些数字 k用来记录还要排列几个数字
    public void dfs(List<List<Integer>> permutes,List<Integer> permute,boolean[] set,int k,int[] nums){
        if(k==1){
            for(int i=0;i<nums.length;i++){
                if(!set[i]) {
                    List<Integer> list=new ArrayList<>(permute);
                    list.add(nums[i]);permutes.add(list);
                    return;
                }
            }
        }
        for(int i=0;i<nums.length;i++){
            if(!set[i]) {
                permute.add(nums[i]);set[i]=true;
                dfs(permutes,permute,set,k-1,nums);
                permute.remove(permute.size()-1);
                set[i]=false;
            }
        }
    }
}

39. 组合总和 - 力扣（LeetCode）

又用set写了一个搞笑的解法 时间复杂度O(2^N) 有点绷不住了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> combinations = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        int sum = 0;Set<String> set = new HashSet<>();
        find(combinations,combination,0,target,candidates,set);
        return combinations;
    }
    public void find(List<List<Integer>> combinations,List<Integer> combination,int sum,int target,int[] candidates,Set<String> set){
        if(sum==target) {
            List<Integer> list1 = new ArrayList<>(combination);
            Collections.sort(list1);
            if(!set.contains(list1.toString())){
                List<Integer> list = new ArrayList<>(combination);
                set.add(list1.toString());
                combinations.add(list);return;
            }
        }
        for(int i=0;i<candidates.length;i++){
            if(sum+candidates[i]<=target){
                combination.add(candidates[i]);
                find(combinations,combination,sum+candidates[i],target,candidates,set);
                combination.remove(combination.size()-1);
            }
        }
    }
}

自己改了一下 先把nums排序就不用担心录入重复的问题了 找到一个思路和我差不多的题解:题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> combinations = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        int sum = 0,index=0;Arrays.sort(candidates);
        find(combinations,combination,0,target,candidates,index);
        return combinations;
    }
    public void find(List<List<Integer>> combinations,List<Integer> combination,int sum,int target,int[] candidates,int index){
        if(sum>target) return;
        if(sum==target) {
            List<Integer> list = new ArrayList<>(combination);
            combinations.add(list);return;
        }
        for(int i=index;i<candidates.length;i++){
            int curSum = sum + candidates[i],step = 0;
            while(curSum<=target){
                combination.add(candidates[i]);step++;
                find(combinations,combination,curSum,target,candidates,i+1);
                curSum+=candidates[i];
            }
            while(step--!=0){
                combination.remove(combination.size()-1);
            }
        }
    }
}

22. 括号生成 - 力扣（LeetCode）

image-20240711014612729

为什么有人就是能把代码写得又优雅又简洁 题解还一目了然 而我连题都做不出来呢😭

这题的回溯 不需要循环 直接把我整懵逼了 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

7.11

79. 单词搜索 - 力扣（LeetCode）

经典用set记录通过用例然后消耗时间惨不忍睹 两千多毫秒也算打破记录了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    int [][]direction = {{1,0},{-1,0},{0,1},{0,-1}};
    int limitR,limitC;
    String target;
    public boolean exist(char[][] board, String word) {
        limitR = board.length;limitC = board[0].length;target=word;
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<board.length;i++)
            for(int k=0;k<board[0].length;k++)
                if(board[i][k]==word.charAt(0))
                    if(find(i,k,new StringBuilder(),word.length(),board,set))
                        return true;
        return false;
    }
    public boolean find(int row,int col,StringBuilder str,int len,char[][] board,Set<Integer> set){
        if(len==0) return str.toString().equals(target);
        int hashcode = row*10+col;
        if(row<limitR&&row>=0&&col<limitC&&col>=0&&!set.contains(hashcode)){
            str.append(board[row][col]);set.add(hashcode);
            for(int []dir:direction){
                if(find(row+dir[0],col+dir[1],str,len-1,board,set)) return true;
            }
            str.deleteCharAt(str.length()-1);set.remove(hashcode);
        }
        return false;
    }
}

改用Boolean二维数组记录之后还是要一秒多 看来问题出在算法上 需要剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    int [][]direction = {{1,0},{-1,0},{0,1},{0,-1}};
    int limitR,limitC;
    String target;
    public boolean exist(char[][] board, String word) {
        limitR = board.length;limitC = board[0].length;target=word;
        boolean[][] set = new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++)
            for(int k=0;k<board[0].length;k++)
                if(board[i][k]==word.charAt(0))
                    if(find(i,k,new StringBuilder(),word.length(),board,set))
                        return true;
        return false;
    }
    public boolean find(int row,int col,StringBuilder str,int len,char[][] board,boolean[][] set){
        if(len==0) return str.toString().equals(target);
        if(row<limitR&&row>=0&&col<limitC&&col>=0&&!set[row][col]){
            str.append(board[row][col]);set[row][col]=true;
            for(int []dir:direction){
                if(find(row+dir[0],col+dir[1],str,len-1,board,set)) return true;
            }
            str.deleteCharAt(str.length()-1);set[row][col]=false;
        }
        return false;
    }
}

通过传参希望的char剪枝将消耗时间减少到了三百多毫秒 跟前排还差两百毫秒

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    int [][]direction = {{1,0},{-1,0},{0,1},{0,-1}};
    int limitR,limitC;
    String target;
    public boolean exist(char[][] board, String word) {
        limitR = board.length;limitC = board[0].length;target=word;
        boolean[][] set = new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++)
            for(int k=0;k<board[0].length;k++)
                if(board[i][k]==word.charAt(0))
                    if(find(i,k,new StringBuilder(),0,board,set,word.charAt(0)))
                        return true;
        return false;
    }
    public boolean find(int row,int col,StringBuilder str,int len,char[][] board,boolean[][] set,char need){
        if(len==target.length()) return str.toString().equals(target);
        if(row<limitR&&row>=0&&col<limitC&&col>=0&&!set[row][col]){
            if(need!=board[row][col]) return false;
            str.append(board[row][col]);set[row][col]=true;
            for(int []dir:direction){
                if(find(row+dir[0],col+dir[1],str,len+1,board,set,len+1==target.length()?need:target.charAt(len+1))) return true;
            }
            str.deleteCharAt(str.length()-1);set[row][col]=false;
        }
        return false;
    }
}

看了题解知道了 原来根本不需要StringBuilder和下一个char 去掉之后时间是190ms 跟上大部队了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    int [][]direction = {{1,0},{-1,0},{0,1},{0,-1}};
    int limitR,limitC;
    String target;
    public boolean exist(char[][] board, String word) {
        limitR = board.length;limitC = board[0].length;target=word;
        boolean[][] set = new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++)
            for(int k=0;k<board[0].length;k++)
                if(board[i][k]==word.charAt(0))
                    if(find(i,k,0,board,set))
                        return true;
        return false;
    }
    public boolean find(int row,int col,int len,char[][] board,boolean[][] set){
        if(row<limitR&&row>=0&&col<limitC&&col>=0&&!set[row][col]){
            if(len==target.length()-1){
                if(board[row][col]==target.charAt(len))return true;
                return false;
            }
            if(target.charAt(len)!=board[row][col]) return false;
            set[row][col]=true;
            for(int []dir:direction){
                if(find(row+dir[0],col+dir[1],len+1,board,set)) return true;
            }
            set[row][col]=false;
        }
        return false;
    }
}

再优化没用的参数和臃肿的循环 缩短到161ms了 到这地步算法都大差不差了 剩下的就是细节优化了 不写了(更快的写法是不新建数组记录用过的字符 而是直接用原二维数组记录 这样写不太好理解而且没那个必要了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean exist(char[][] board, String word) {
        boolean[][] set = new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++)
            for(int k=0;k<board[0].length;k++)
                if(board[i][k]==word.charAt(0))
                    if(find(i,k,0,board,set,word))
                        return true;
        return false;
    }
    public boolean find(int row,int col,int len,char[][] board,boolean[][] set,String word){
        if(!(row<board.length&&row>=0&&col<board[0].length&&col>=0&&!set[row][col])) return false;
        if(len==word.length()-1){
            return board[row][col] == word.charAt(len);
        }
        if(word.charAt(len)!=board[row][col]) return false;
        set[row][col]=true;
        boolean res = find(row+1,col,len+1,board,set,word) ||find(row-1,col,len+1,board,set,word)
                || find(row,col+1,len+1,board,set,word) ||find(row,col-1,len+1,board,set,word);
        set[row][col]=false;
        return res;
    }
}

148. 排序链表 - 力扣（LeetCode）

题目有分治的标签 但我只是重写了ListNode的比较函数后用快排排序了…(完美符合时间复杂度O(nlogn)有没有)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public ListNode sortList(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        while(head!=null){
            list.add(head);
            head=head.next;
        }
        list.sort(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        ListNode ans = new ListNode(-1);head=ans;
        for(ListNode node:list) {
            head.next=node;head=node;
        }
        head.next=null;
        return ans.next;
    }
}

当然不能偷懒啦…所以还是学了分治的方法😔

之前我纠结的是分治之后的两个链表要怎么合并 结果题解说参考. - 力扣（LeetCode） 不是直接合并而是遍历合并啊… 还有快慢指针划分链表也是个新思路 最后合并链表的处理也挺巧妙的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null) return null;
        if(head.next==null) return head;
        ListNode fast=head,slow=head;
        while(fast.next!=null&&fast.next.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
        }
        fast=slow.next;slow.next=null;
        ListNode list1 = sortList(fast),list2 = sortList(head),ans = new ListNode(-1),p=ans;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                p.next = list1;list1=list1.next;p=p.next;
            }else{
                p.next = list2;list2=list2.next;p=p.next;
            }
        }
        if(list1!=null) p.next=list1;
        if(list2!=null) p.next=list2;
        return ans.next;
    }
}

427. 建立四叉树 - 力扣（LeetCode）

写得有点慢了 还调试了半天 一个原因是题目描述的输出不够清楚 如果是叶子节点就不能连接四个子网格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public Node construct(int[][] grid) {
        Node ans = fun(grid,new int[]{0,0}, new int[]{grid.length-1, grid[0].length-1});
        return ans;
    }
    public Node fun(int[][] grid,int []topLeftIndex,int []bottomRightIndex){
        if(bottomRightIndex[0]==topLeftIndex[0]) return new Node(grid[topLeftIndex[0]][topLeftIndex[1]]==1,true);
        int []half={(bottomRightIndex[0]-topLeftIndex[0]+1)/2-1+topLeftIndex[0],(bottomRightIndex[1]-topLeftIndex[1]+1)/2-1+topLeftIndex[1]};
        Node topLeft = fun(grid,topLeftIndex,half);
        Node topRight = fun(grid,new int[]{topLeftIndex[0],half[1]+1},new int[]{half[0],bottomRightIndex[1]});
        Node bottomLeft = fun(grid,new int[]{half[0]+1,topLeftIndex[1]},new int[]{bottomRightIndex[0],half[1]});
        Node bottomRight = fun(grid,new int[]{half[0]+1,half[1]+1},bottomRightIndex);
        boolean isLeaf = topLeft.isLeaf&& topRight.isLeaf&& bottomLeft.isLeaf&& bottomRight.isLeaf&&(topLeft.val==topRight.val&&topLeft.val==bottomLeft.val&&topLeft.val==bottomRight.val);
        if(isLeaf) return new Node(grid[topLeftIndex[0]][topLeftIndex[1]]==1, true);
        return new Node(grid[topLeftIndex[0]][topLeftIndex[1]]==1,isLeaf,topLeft,topRight,bottomLeft,bottomRight);
    }
}

208. 实现 Trie (前缀树) - 力扣（LeetCode）

倒是自己实现了 不过执行时间不太好 用的是map记录的树形结构 用数组会不会好点?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Trie {
    class Node {
        public char val;
        Map<Character,Node> map = new HashMap<>();
        Node(char val){this.val = val;}
    }
    Node root;
    public Trie() {
        root  = new Node('#');
    }
    public void insert(String word) {
        char [] chars = word.toCharArray();
        Node p=root;
        for(char ch:chars){
            if(!p.map.containsKey(ch)){
                p.map.put(ch,new Node(ch));
                p=p.map.get(ch);
            }else p=p.map.get(ch);
        }p.map.put('_',new Node('_'));//终止符
    }
    public boolean search(String word) {
        char [] chars = word.toCharArray();
        Node p=root;
        for(char ch:chars){
            if(!p.map.containsKey(ch)){return false;}
            p=p.map.get(ch);
        }
        if(p.map.containsKey('_')) return true;
        return false;
    }
    public boolean startsWith(String prefix) {
        char [] chars = prefix.toCharArray();
        Node p=root;
        for(char ch:chars){
            if(!p.map.containsKey(ch)){return false;}
            p=p.map.get(ch);
        }
        return true;
    }
}

把map换成数组 超过72%了 还行 而且我发现这玩意不能认真 执行用时和消耗内存随机波动太大了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Trie {
    class Node {
        public char val;
        public boolean end;
        Node [] map = new Node[26];
        Node(char val){this.val = val;end = false;}
    }
    Node root;
    public Trie() {
        root  = new Node('#');
    }

    public void insert(String word) {
        char [] chars = word.toCharArray();
        Node p=root;
        for(char ch:chars){
            if(p.map[ch-'a']==null){
                p.map[ch-'a'] = new Node(ch);
                p=p.map[ch-'a'];
            }else p=p.map[ch-'a'];
        }p.end=true;//终止符
    }

    public boolean search(String word) {
        char [] chars = word.toCharArray();
        Node p=root;
        for(char ch:chars){
            if(p.map[ch-'a']==null){return false;}
            p=p.map[ch-'a'];
        }
        return p.end;
    }

    public boolean startsWith(String prefix) {
        char [] chars = prefix.toCharArray();
        Node p=root;
        for(char ch:chars){
            if(p.map[ch-'a']==null){return false;}
            p=p.map[ch-'a'];
        }
        return true;
    }
}

多跑了几遍 现在已经超过98.92%了 有点搞笑

211. 添加与搜索单词 - 数据结构设计 - 力扣（LeetCode）

调了半天改来改去结果最后还是惨不忍睹的用时 (610ms)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class WordDictionary {
    class Node {
        public char val;
        public boolean end;
        Node[] map = new Node[26];
        Node(char val){this.val = val;end = false;}
    }
    Node root;
    public WordDictionary() {
        root  = new Node('#');
    }

    public void addWord(String word) {
        char [] chars = word.toCharArray();
        Node p=root;
        for(char ch:chars){
            if(p.map[ch-'a']==null){
                Node node = new Node(ch);
                p.map[ch-'a'] = node;
            }p=p.map[ch-'a'];
        }p.end=true;//终止符
    }

    public boolean search(String word) {
        return searchPoint(word,root);
    }

    public boolean searchPoint(String word,Node node){
        char [] chars = word.toCharArray();
        Node p=node;
        for(int i=0;i<word.length();i++){
            if(chars[i]!='.'){
                if(p.map[chars[i]-'a']==null){return false;}
                p=p.map[chars[i]-'a'];
            }else{
                StringBuilder str = new StringBuilder(word);
                while(str.charAt(0)!='.') str.delete(0,1);
                str.delete(0,1);
                for(int k=0;k<26;k++){
                    StringBuilder newStr = new StringBuilder(String.valueOf((char) (k + 'a')) + str);
                    if(searchPoint(newStr.toString(),p)) return true;
                }return false;
            }
        }
        return p.end;
    }
}

一个小小的剪枝就能快1.5倍 (398ms)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class WordDictionary {
    class Node {
        public char val;
        public boolean end;
        Node[] map = new Node[26];
        Node(char val){this.val = val;end = false;}
    }
    Node root;
    public WordDictionary() {
        root  = new Node('#');
    }

    public void addWord(String word) {
        char [] chars = word.toCharArray();
        Node p=root;
        for(char ch:chars){
            if(p.map[ch-'a']==null){
                Node node = new Node(ch);
                p.map[ch-'a'] = node;
            }p=p.map[ch-'a'];
        }p.end=true;//终止符
    }

    public boolean search(String word) {
        return searchPoint(word,root);
    }

    public boolean searchPoint(String word,Node node){
        char [] chars = word.toCharArray();
        Node p=node;
        for(int i=0;i<word.length();i++){
            if(chars[i]!='.'){
                if(p.map[chars[i]-'a']==null){return false;}
                p=p.map[chars[i]-'a'];
            }else{
                StringBuilder str = new StringBuilder(word);
                while(str.charAt(0)!='.') str.delete(0,1);
                str.delete(0,1);
                for(int k=0;k<26;k++){
                    if(p.map[k]!=null){
                        StringBuilder newStr = new StringBuilder(String.valueOf((char) (k + 'a')) + str);
                        if(searchPoint(newStr.toString(),p)) return true;
                    }
                }return false;
            }
        }
        return p.end;
    }
}

想不到怎么改了 看看164ms的代码 : 用了传参来记录目前遍历的字符串长度 我是铸币吗 为什么要执着于用字符串传这个信息???

改完了 183ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class WordDictionary {
    class Node {
        public char val;
        public boolean end;
        Node[] map = new Node[26];
        Node(char val){this.val = val;end = false;}
    }
    Node root;
    public WordDictionary() {
        root  = new Node('#');
    }

    public void addWord(String word) {
        char [] chars = word.toCharArray();
        Node p=root;
        for(char ch:chars){
            if(p.map[ch-'a']==null){
                Node node = new Node(ch);
                p.map[ch-'a'] = node;
            }p=p.map[ch-'a'];
        }p.end=true;//终止符
    }

    public boolean search(String word) {
        return searchPoint(word,root,0);
    }

    public boolean searchPoint(String word,Node node,int len){
        if(len==word.length()) return node.end;
        char ch = word.charAt(len);
        if(ch!='.'){
            if(node.map[ch-'a']==null){return false;}
            return searchPoint(word,node.map[ch-'a'],len+1);
        }else{
            for(int k=0;k<26;k++){
                if(node.map[k]!=null&&searchPoint(word,node.map[k],len+1)){
                    return true;
                }
            }return false;
        }
    }
}

7.12

120. 三角形最小路径和 - 力扣（LeetCode）

dp记录走过的路径 第一次用了二维list记录dp 17ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size()==1)return triangle.get(0).get(0);
        List<List<Integer>> dp = new ArrayList<>();
        dp.add(new ArrayList<>());dp.get(0).add(0,triangle.get(0).get(0));
        for(int i=0;i<triangle.size()-1;i++){
            dp.add(new ArrayList<>());
            for(int k = 0;k<triangle.get(i).size();k++){
                int k1 = triangle.get(i+1).get(k)+dp.get(i).get(k),k2=triangle.get(i+1).get(k+1)+dp.get(i).get(k);
                if(k==0){
                    dp.get(i+1).add(k1);
                }else{
                    dp.get(i+1).set(k,Math.min(k1,dp.get(i+1).get(k)));
                }
                dp.get(i+1).add(k2);
            }
        }
        int ans=dp.get(dp.size()-1).get(0);
        for(int i:dp.get(dp.size()-1)) ans = Math.min(ans,i);
        return ans;
    }
}

第二次 用二维数组记录dp 8ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size()==1)return triangle.get(0).get(0);
        int[][] dp = new int[201][201];
        dp[0][0]=triangle.get(0).get(0);
        for(int i=0;i<triangle.size()-1;i++){
            dp[i+1][0] = triangle.get(i+1).get(0)+dp[i][0];
            dp[i+1][1]=triangle.get(i+1).get(1)+dp[i][0];
            for(int k = 1;k<triangle.get(i).size();k++){
                int k1 = triangle.get(i+1).get(k)+dp[i][k],k2=triangle.get(i+1).get(k+1)+dp[i][k];
                dp[i+1][k] = Math.min(k1,dp[i+1][k]);
                dp[i+1][k+1]=k2;
            }
        }
        int ans=dp[triangle.size()-1][0];
        for(int i=0;i<triangle.size();i++) ans = Math.min(ans,dp[triangle.size()-1][i]);
        return ans;
    }
}

第三次 可以只用两个n长度的数组记录dp 5ms 内存消耗很大减少 (写完了才发现题目原来有提示)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size()==1)return triangle.get(0).get(0);
        int[] dp = new int[triangle.size()];
        int [] dpLast = new int[triangle.size()];
        dp[0]=triangle.get(0).get(0);dpLast[0] = dp[0];
        for(int i=0;i<triangle.size()-1;i++){
            for(int k = 0;k<=i;k++){
                int k1 = triangle.get(i+1).get(k)+dpLast[k],k2=triangle.get(i+1).get(k+1)+dpLast[k];
                if(k==0) dp[0] = triangle.get(i+1).get(0)+dpLast[0];
                else dp[k] = Math.min(k1,dp[k]);
                dp[k+1]=k2;
                dpLast[k]=dp[k];
            }dpLast[triangle.get(i).size()]=dp[triangle.get(i).size()];
        }
        int ans=dp[0];
        for(int i=0;i<triangle.size();i++) ans = Math.min(ans,dp[i]);
        return ans;
    }
}

没忍住看了别人的代码 太天才了 倒着遍历三角形 每次循环操作大大减少而且只要一个n长度数组 2ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
     public int minimumTotal(List<List<Integer>> triangle) {

        int size = triangle.size();

        int[] dp = new int[size + 1];

        for (int i = size - 1; i >= 0; i--) {

            for (int j = 0; j <= i; j++) {

                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1]);
            }
        }
        return dp[0];
    }
}

64. 最小路径和 - 力扣（LeetCode）

用原数组记录路径 dp 先计算顶部和左侧的dp防止越界问题 沿最小边的对角线遍历每行每列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        for(int k = 1 ;k<n;k++){
            grid[0][k] += grid[0][k-1];
        }
        for(int k = 1 ;k<m;k++){
            grid[k][0] += grid[k-1][0];
        }
        for(int i = 1;i<Math.max(m,n);i++){
            if(i<Math.min(m,n))
                grid[i][i] += Math.min(grid[i-1][i],grid[i][i-1]);
            for(int k =i+1 ;k<n&&i<m;k++){
                grid[i][k] += Math.min(grid[i][k-1],grid[i-1][k]);
            }
            for(int k=i+1;k<m&&i<n;k++){
                grid[k][i] += Math.min(grid[k][i-1],grid[k-1][i]);
            }
        }
        return grid[m-1][n-1];
    }
}

7.13更新: 写完某题后蓦然回首发现我是傻逼 直接按行遍历就完了干嘛要行列遍历折磨自己

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        for(int k = 1 ;k<n;k++){
            grid[0][k] += grid[0][k-1];
        }
        for(int k = 1 ;k<m;k++){
            grid[k][0] += grid[k-1][0];
        }
        for(int i = 1;i<m;i++){
            for(int k = 1 ;k<n;k++){
                grid[i][k] += Math.min(grid[i][k-1],grid[i-1][k]);
            }
        }
        return grid[m-1][n-1];
    }
}

63. 不同路径 II - 力扣（LeetCode）

改了一下上面那道题的代码 击败100% 也是用原数组记录dp 灵光一现把1换成0 然后记录能走的路有多少种路径能到达(用负数记录的原因是一开始想的时候觉得可能变1被判断成石头 后来把1都换成0了就没这个问题了 用正负数都行)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length,n=obstacleGrid[0].length;
        if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1) return 0;
        obstacleGrid[0][0]=-1;
        for(int k = 1 ;k<n;k++){
            if(obstacleGrid[0][k]==1){obstacleGrid[0][k]=0;continue;}
            obstacleGrid[0][k] += obstacleGrid[0][k-1];
        }
        for(int k = 1 ;k<m;k++){
            if(obstacleGrid[k][0]==1){obstacleGrid[k][0]=0;continue;}
            obstacleGrid[k][0] += obstacleGrid[k-1][0];
        }
        for(int i = 1;i<Math.max(m,n);i++){
            if(i<Math.min(m,n))
                if(obstacleGrid[i][i]==1){obstacleGrid[i][i]=0;}
                else obstacleGrid[i][i] =obstacleGrid[i-1][i]+obstacleGrid[i][i-1];
            for(int k =i+1 ;k<n&&i<m;k++){
                if(obstacleGrid[i][k]==1){obstacleGrid[i][k]=0;continue;}
                obstacleGrid[i][k] = obstacleGrid[i][k-1]+obstacleGrid[i-1][k];
            }
            for(int k=i+1;k<m&&i<n;k++){
                if(obstacleGrid[k][i]==1){obstacleGrid[k][i]=0;continue;}
                obstacleGrid[k][i] = obstacleGrid[k][i-1]+obstacleGrid[k-1][i];
            }
        }
        return -obstacleGrid[m-1][n-1];
    }
}

7.13 : 同上题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length,n=obstacleGrid[0].length;
        if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1) return 0;
        obstacleGrid[0][0]=-1;
        for(int k = 1 ;k<n;k++){
            if(obstacleGrid[0][k]==1){obstacleGrid[0][k]=0;continue;}
            obstacleGrid[0][k] += obstacleGrid[0][k-1];
        }
        for(int k = 1 ;k<m;k++){
            if(obstacleGrid[k][0]==1){obstacleGrid[k][0]=0;continue;}
            obstacleGrid[k][0] += obstacleGrid[k-1][0];
        }
        for(int i = 1;i<m;i++){
            for(int k = 1 ;k<n;k++){
                if(obstacleGrid[i][k]==1){obstacleGrid[i][k]=0;continue;}
                obstacleGrid[i][k] = obstacleGrid[i][k-1]+obstacleGrid[i-1][k];
            }
        }
        return -obstacleGrid[m-1][n-1];
    }
}

221. 最大正方形 - 力扣（LeetCode）

依旧是上面的思路 7ms 不过这次时间只超过31%了 待我看看怎么优化一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int maximalSquare(char[][] matrix) {
        int m=matrix.length,n=matrix[0].length,ans=Integer.MIN_VALUE;
        int [][]dp = new int[m][n];
        dp[0][0]=matrix[0][0]-'0';ans = dp[0][0];
        for(int k = 1 ;k<n;k++){
            dp[0][k] = matrix[0][k]-'0';
            ans = Math.max(ans,dp[0][k]);
        }
        for(int k = 1 ;k<m;k++){
            dp[k][0] = matrix[k][0]-'0';
            ans = Math.max(ans,dp[k][0]);
        }
        for(int i = 1;i<Math.max(m,n);i++){
            if(i<Math.min(m,n)&&matrix[i][i]=='1'){
                dp[i][i] = Math.min(dp[i-1][i],Math.min(dp[i][i-1],dp[i-1][i-1]))+1;
                ans = Math.max(ans,dp[i][i]);
            }
            for(int k =i+1 ;k<n&&i<m;k++){
                if(matrix[i][k]=='1')
                    dp[i][k] = Math.min(dp[i][k-1],Math.min(dp[i-1][k],dp[i-1][k-1]))+1;
                ans = Math.max(ans,dp[i][k]);
            }
            for(int k=i+1;k<m&&i<n;k++){
                if(matrix[k][i]=='1')
                    dp[k][i] = Math.min(dp[k][i-1],Math.min(dp[k-1][i],dp[k-1][i-1]))+1;
                ans = Math.max(ans,dp[k][i]);
            }
        }
        return ans*ans;
    }
}

优化了一下ans的赋值判断逻辑 结果发现只是随机波动太大了 7ms是31% 6ms是90% 无语

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int maximalSquare(char[][] matrix) {
        int m=matrix.length,n=matrix[0].length,ans=Integer.MIN_VALUE;
        int [][]dp = new int[m][n];
        dp[0][0]=matrix[0][0]-'0';ans = dp[0][0];
        for(int k = 1 ;k<n;k++){
            dp[0][k] = matrix[0][k]-'0';
            if(ans!=1&&dp[0][k]==1) ans = 1;
        }
        for(int k = 1 ;k<m;k++){
            dp[k][0] = matrix[k][0]-'0';
            if(ans!=1&&dp[k][0]==1) ans = 1;
        }
        for(int i = 1;i<Math.max(m,n);i++){
            if(i<Math.min(m,n)&&matrix[i][i]=='1'){
                dp[i][i] = Math.min(dp[i-1][i],Math.min(dp[i][i-1],dp[i-1][i-1]))+1;
                ans = Math.max(ans,dp[i][i]);
            }
            for(int k =i+1 ;k<n&&i<m;k++){
                if(matrix[i][k]=='1'){
                    dp[i][k] = Math.min(dp[i][k-1],Math.min(dp[i-1][k],dp[i-1][k-1]))+1;
                    ans = Math.max(ans,dp[i][k]);
                }
            }
            for(int k=i+1;k<m&&i<n;k++){
                if(matrix[k][i]=='1'){
                    dp[k][i] = Math.min(dp[k][i-1],Math.min(dp[k-1][i],dp[k-1][i-1]))+1;
                    ans = Math.max(ans,dp[k][i]);
                }
            }
        }
        return ans*ans;
    }
}

又跑了几遍 优化还是有用的 第一次的代码多跑几次也没跑到6ms

7.13 : - _ -

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maximalSquare(char[][] matrix) {
        int m=matrix.length,n=matrix[0].length,ans=Integer.MIN_VALUE;
        int [][]dp = new int[m][n];
        dp[0][0]=matrix[0][0]-'0';ans = dp[0][0];
        for(int k = 1 ;k<n;k++){
            dp[0][k] = matrix[0][k]-'0';
            if(ans!=1&&dp[0][k]==1) ans = 1;
        }
        for(int k = 1 ;k<m;k++){
            dp[k][0] = matrix[k][0]-'0';
            if(ans!=1&&dp[k][0]==1) ans = 1;
        }
        for(int i = 1;i<m;i++){
            for(int k = 1 ;k<n;k++){
                if(matrix[i][k]=='1'){
                    dp[i][k] = Math.min(dp[i][k-1],Math.min(dp[i-1][k],dp[i-1][k-1]))+1;
                    ans = Math.max(ans,dp[i][k]);
                }
            }
        }
        return ans*ans;
    }
}

97. 交错字符串 - 力扣（LeetCode）

想了半天想不到状态转移方程 搞不懂怎么用dp记录 看了某大佬的题解豁然开朗醍醐灌顶 只看一眼下面的图便解开所有疑惑:

image-20240713013501292

一图胜千言啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (s3.length() != m + n) return false;
        // 动态规划，dp[i,j]表示s1前i字符能与s2前j字符组成s3前i+j个字符；
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for (int i = 1; i <= m && s1.charAt(i-1) == s3.charAt(i-1); i++) dp[i][0] = true; // 不相符直接终止
        for (int j = 1; j <= n && s2.charAt(j-1) == s3.charAt(j-1); j++) dp[0][j] = true; // 不相符直接终止
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = (dp[i - 1][j] && s3.charAt(i + j - 1) == s1.charAt(i - 1))
                        || (dp[i][j - 1] && s3.charAt(i + j - 1) == s2.charAt(j - 1));
            }
        }
        return dp[m][n];
    }
}

7.13

72. 编辑距离 - 力扣（LeetCode）

这真的是中等题吗? 看题解都看了一会才理解 题解

做完发现我之前做多维dp的时候直接一行行遍历就行了呀 一行一列地遍历又麻烦又容易错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minDistance(String word1, String word2) {
        int [][]dp=new int[word1.length()+1][word2.length()+1];
        int len1=word1.length(),len2 = word2.length();
        char [] chars1 = word1.toCharArray(),chars2 = word2.toCharArray();
        for(int i=1;i<=len1;i++) dp[i][0] = i;
        for(int i=1;i<=len2;i++) dp[0][i] = i;
        for(int i=1;i<=len1;i++){
            for(int k=1;k<=len2;k++){
                dp[i][k] = Math.min(dp[i-1][k-1],Math.min(dp[i-1][k],dp[i][k-1]))+1;
                if(chars1[i-1]==chars2[k-1])
                    dp[i][k] = Math.min(dp[i][k],dp[i-1][k-1]);
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

参考代码里有用递归做的 比一般遍历快一倍(4ms->2ms) 贴一下代码吧 也是计算三种操作分别的最小步数 不过它没扩大dp半圈所以遍历数减少了n+m次 所以比一般dp快 不过递归的话内存占用会变多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    String word1;
    String word2;
    int[][] dp;

    public int minDistance(String word1, String word2) {
        this.word1 = word1;
        this.word2 = word2;
        dp = new int[word1.length()][word2.length()];
        return dp(word1.length() - 1, word2.length() - 1);
    }

    public int dp(int index1, int index2) {
        if (index1 == -1) {
            return index2 + 1;
        }
        if (index2 == -1) {
            return index1 + 1;
        }
        if (dp[index1][index2] != 0) {
            return dp[index1][index2];
        }

        if (word1.charAt(index1) == word2.charAt(index2)) {
            int num = dp(index1 - 1, index2 - 1);
            dp[index1][index2] = num;
            return num;
        }

        int delete = dp(index1 - 1, index2) + 1;
        int add = dp(index1, index2 - 1) + 1;
        int replace = dp(index1 - 1, index2 - 1) + 1;

        int min = Math.min(delete, Math.min(add, replace));
        dp[index1][index2] = min;
        return min;
    }
}