代码随想录算法训练营第七天| 454.四数相加II 383. 赎金信15. 三数之和18. 四数之和

简介: 代码随想录算法训练营第七天| 454.四数相加II 383. 赎金信15. 三数之和18. 四数之和

今日学习的文章链接和视频链接

代码随想录(programmercarl.com)

自己看到题目的第一想法

#(454.四数相加II

暴力解法:四层for循环。超时…拆解:两个一组分别进行两层for循环,细节不会实现了..

#(383. 赎金信
1// 第一个思路:
2// 字符串转数组
3
4// map封装遍历判断ransomNote中每个字符出现的次数是否小于等于magazine与之对应的字符出现的次数
5
6// 第二个思路:
7// 因为都是英文小写字母,将ransomNote中每个字符出现的次数做记录;
8// 同时对magazine中的字符做记录,判断与之对应的字符出现的次数

#(15. 三数之和 )

  1. 1// 排序
  2. 2// 前后指针 + 移动指针(具体实现有些复杂,逻辑不清晰)
  3. #(18. 四数之和)

双指针 + 两个循环判断


看完代码随想录之后的想法

#(454.四数相加II )

逻辑:分两组,拆解着做。关键在于怎么存放数据;map很巧妙,具有封装性。


#(383. 赎金信 )

暴力没想出来!!

和有效字母异位词同一个模板,拿来改改就能用。


#(15. 三数之和 )

逻辑相似,但实现逻辑更清晰,通过>0和<0进行判断左右的移动,a去重细节清晰。


#(18. 四数之和)

多加一层for循环遍历,应注意去重剪枝的小细节。


自己实现过程中遇到哪些困难

#(454.四数相加II )

key存放两组元素之和,value存放该和出现次数;

map.put()调用,map.getOrDefault(0 - i - j, 0)方法内涵等不了解;

增强for循环不是很了解,大概先背下来。


#(383. 赎金信 )

基础语法不熟悉,需要记忆。如字符数组转换,字符偏移量位置字符检索操作。


#(15. 三数之和 )

排序实现方式,a去重细节,其他两个数去重细节。


#(18. 四数之和)

首层for循环的剪枝操作,两层for循环去重细节


今日收获,记录一下自己的学习时长

3.5h

 1// 自己实现:暴力
 2class Solution {
 3    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
 4        int n = nums1.length;
 5        int count = 0;
 6        // 第一想法:四层for循环遍历判等,返回即可
 7        for (int i = 0; i < n; i++) {
 8            for (int j = 0; j < n; j++) {
 9                for (int k = 0; k < n; k++) {
10                    for (int l = 0; l < n; l++) {
11                        if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) {
12                            count++;
13                        }
14                    }
15                }
16            }
17        }
18        return count;
19    }
20}
21
22// 自己实现:暴力二(编译没通过...越来越复杂,止损!)
23// class Solution {
24//     public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
25//         int n = nums1.length;
26//         int count = 0;
27//         int m = n * n;
28//         int[] res1 = new int[n * n];
29//         int[] res2 = new int[n * n];
30
31//         // 拆解
32//         for (int i = 0; i < n; i++) {
33//             for (int j = 0; j < n; j++) {
34//                 res1[m--] = nums1[i] + nums2[j];
35//             }
36//         }
37//         for (int k = 0; k < n; k++) {
38//             for (int l = 0; l < n; l++) {
39//                 res2[m--] = nums3[k] + nums4[l];
40//             }
41//         }
42//         for (int i = 0; i < m; i++) {
43//             for (int j = 0; j < m; j++) {
44//                 if (res1[i] + res2[j] == 0) {
45//                     count++;
46//                 }
47//             }
48//         }
49
50//         return count;
51//     }
52// }
53
54class Solution {
55    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
56        // 初始化结果变量
57        int res = 0;
58        // 创建一个 HashMap,用于存储两个数组中元素之和及其出现的次数
59        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
60
61        // 统计 nums1 和 nums2 数组中元素之和的情况,将结果存入 map
62        for (int i = 0; i < nums1.length; i++) {
63            for (int j = 0; j < nums2.length; j++) {
64                int sum = nums1[i] + nums2[j];
65                // 将 sum 作为 key,将其出现次数作为 value 存入 map
66                // 如果 sum 已经在 map 中,取出其对应的 value 加 1,否则默认值为 0
67                map.put(sum, map.getOrDefault(sum, 0) + 1);
68            }
69        }
70
71        // 统计 nums3 和 nums4 数组中元素之和的情况,查找 map 中是否存在与之相加为 0 的情况,并将次数累加到结果变量 res 上
72        for (int i : nums3) {
73            for (int j : nums4) {
74                // 查找与当前元素 i 和 j 相加为 0 的情况在 map 中的次数,并将次数加到结果变量 res 上
75                res += map.getOrDefault(0 - i - j, 0);
76            }
77        }
78
79        // 返回最终结果
80        return res;
81    }
82}

#(383. 赎金信 )

 1// 枚举暴力输出
 2class Solution {
 3    public boolean canConstruct(String ransomNote, String magazine) {
 4        char[] str1 = ransomNote.toCharArray();
 5        char[] str2 = magazine.toCharArray();
 6        for (int i = 0; i < str1.length; i++) {
 7            for (int j = 0; j < str2.length; j++) {
 8                if (str1[i] == str2[j]) {
 9                    str1[i] = '0';
10                    str2[j] = '0';
11                    continue;
12                }
13            }
14        }
15
16        for (int i = 0; i < str1.length; i++) {
17            if (str1[i] != '0') {
18                return false;
19            }
20        }
21        return true;
22    }
23}
24
25//借鉴242.有效的字母异位词的模板
26class Solution {
27    public boolean canConstruct(String ransomNote, String magazine) {
28        int[] res = new int[26];
29        for (int i = 0; i < ransomNote.length(); i++) {
30            res[ransomNote.charAt(i) - 'a']--;
31        }
32
33        for (int i = 0; i < magazine.length(); i++) {
34            res[magazine.charAt(i) - 'a']++;
35        }
36        for (int i = 0; i < res.length; i++) {
37            if (res[i] < 0) {
38                return false;
39            }
40        }
41
42        return true;
43    }
44}

#(15. 三数之和 )

 1class Solution {
 2    public List<List<Integer>> threeSum(int[] nums) {
 3        // 排序
 4        Arrays.sort(nums);
 5        List<List<Integer>> res = new ArrayList<>();
 6
 7        // 前后指针 + 移动指针
 8
 9        for (int i = 0; i < nums.length; i++) {
10            if (nums[i] > 0) {
11                return res;
12            }
13            // 去重第一个数
14            if (i > 0 && nums[i] == nums[i - 1]) {
15                continue;
16            }
17
18            int left = i + 1;
19            int right = nums.length - 1;
20            while (right > left) {
21                int sum = nums[i] + nums[left] + nums[right];
22                if (sum > 0) {
23                    right--;
24                } else if (sum < 0) {
25                    left++;
26                } else {
27                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
28                    // right去重
29                    while (left < right && nums[right] == nums[right - 1]) {
30                        right--;
31                    }
32                    // left去重
33                    while (left < right && nums[left] == nums[left + 1]) {
34                        left++;
35                    }
36                    // 加入和为 0 的元素后,right--,而left不变,此时,和为负数。所以两者同时移动。
37                    right--;;
38                    left++;
39
40                }
41            }
42        }
43        return res;
44    }
45}

#(18. 四数之和)

 1class Solution {
 2    public List<List<Integer>> fourSum(int[] nums, int target) {
 3        List<List<Integer>> result = new ArrayList<>();
 4        Arrays.sort(nums);
 5
 6        for (int i = 0; i < nums.length; i++) {
 7
 8            // nums[i] > target 直接返回, 剪枝操作
 9            if (nums[i] > 0 && nums[i] > target) {
10                return result;
11            }
12
13            if (i > 0 && nums[i - 1] == nums[i]) {    // 对nums[i]去重
14                continue;
15            }
16
17            for (int j = i + 1; j < nums.length; j++) {
18
19                if (j > i + 1 && nums[j - 1] == nums[j]) {  // 对nums[j]去重
20                    continue;
21                }
22
23                int left = j + 1;
24                int right = nums.length - 1;
25                while (right > left) {
26            // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
27                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
28                    if (sum > target) {
29                        right--;
30                    } else if (sum < target) {
31                        left++;
32                    } else {
33                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
34                        // 对nums[left]和nums[right]去重
35                        while (right > left && nums[right] == nums[right - 1]) right--;
36                        while (right > left && nums[left] == nums[left + 1]) left++;
37
38                        left++;
39                        right--;
40                    }
41                }
42            }
43        }
44        return result;
45    }
46}
相关文章
|
5天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
5天前
|
机器学习/深度学习 运维 算法
【储能选址定容】基于多目标粒子群算法的配电网储能选址定容(Matlab代码实现)
【储能选址定容】基于多目标粒子群算法的配电网储能选址定容(Matlab代码实现)
|
5天前
|
存储 机器学习/深度学习 算法
基于A星算法的无人机三维路径规划算法研究(Mattlab代码实现)
基于A星算法的无人机三维路径规划算法研究(Mattlab代码实现)
|
5天前
|
机器学习/深度学习 算法 Java
基于灰狼优化算法(GWO)解决柔性作业车间调度问题(Matlab代码实现)
基于灰狼优化算法(GWO)解决柔性作业车间调度问题(Matlab代码实现)
|
5天前
|
算法 机器人 Serverless
【机器人路径规划】基于6种算法(黑翅鸢优化算法BKA、SSA、MSA、RTH、TROA、COA)求解机器人路径规划研究(Matlab代码实现)
【机器人路径规划】基于6种算法(黑翅鸢优化算法BKA、SSA、MSA、RTH、TROA、COA)求解机器人路径规划研究(Matlab代码实现)
|
7天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
|
7天前
|
机器学习/深度学习 算法 调度
基于NSGA-III算法求解微电网多目标优化调度研究(Matlab代码实现)
基于NSGA-III算法求解微电网多目标优化调度研究(Matlab代码实现)
|
9天前
|
机器学习/深度学习 运维 算法
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
|
6天前
|
传感器 算法 数据挖掘
基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
基于协方差交叉(CI)的多传感器融合算法,通过MATLAB仿真对比单传感器、SCC与CI融合在位置/速度估计误差(RMSE)及等概率椭圆上的性能。采用MATLAB2022A实现,结果表明CI融合在未知相关性下仍具鲁棒性,有效降低估计误差。
|
7天前
|
负载均衡 算法 调度
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
76 11

热门文章

最新文章