代码随想录算法训练营第七天| 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}
相关文章
|
22天前
|
存储 算法 程序员
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
|
23天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
54 1
|
1月前
|
存储 缓存 算法
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
|
1月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
1月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
17天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
23天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。
|
3天前
|
供应链 算法 调度
排队算法的matlab仿真,带GUI界面
该程序使用MATLAB 2022A版本实现排队算法的仿真,并带有GUI界面。程序支持单队列单服务台、单队列多服务台和多队列多服务台三种排队方式。核心函数`func_mms2`通过模拟到达时间和服务时间,计算阻塞率和利用率。排队论研究系统中顾客和服务台的交互行为,广泛应用于通信网络、生产调度和服务行业等领域,旨在优化系统性能,减少等待时间,提高资源利用率。
|
11天前
|
存储 算法
基于HMM隐马尔可夫模型的金融数据预测算法matlab仿真
本项目基于HMM模型实现金融数据预测,包括模型训练与预测两部分。在MATLAB2022A上运行,通过计算状态转移和观测概率预测未来值,并绘制了预测值、真实值及预测误差的对比图。HMM模型适用于金融市场的时间序列分析,能够有效捕捉隐藏状态及其转换规律,为金融预测提供有力工具。
|
19天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。