力扣爆刷第104天之CodeTop100五连刷6-10

2024-03-26 00:20

本文主要是介绍力扣爆刷第104天之CodeTop100五连刷6-10,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

力扣爆刷第104天之CodeTop100五连刷6-10

文章目录

      • 力扣爆刷第104天之CodeTop100五连刷6-10
      • 一、15. 三数之和
      • 二、53. 最大子数组和
      • 三、912. 排序数组
      • 四、21. 合并两个有序链表
      • 五、1. 两数之和

一、15. 三数之和

题目链接:https://leetcode.cn/problems/3sum/description/
思路:求三数之和,需要外层一个for,内层一个for,内层的还要双指针。另外就是要注意去重操作。

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> arrayList = new ArrayList<>();Arrays.sort(nums);for(int i = 0; i < nums.length-2; i++) {if(nums[i] > 0) break;if(i > 0 && nums[i] == nums[i-1]) continue;int j = i+1, k = nums.length-1;while(j < k) {int temp = nums[i] + nums[j] + nums[k];if(temp == 0) {List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);arrayList.add(list);while(j < k && nums[j] == nums[j+1]) j++;while(j < k && nums[k] == nums[k-1]) k--;j++;k--;}else if(temp < 0) {j++;}else{k--;}}}return arrayList;}
}

二、53. 最大子数组和

题目链接:https://leetcode.cn/problems/maximum-subarray/description/
思路:可以使用动态规划和贪心来做,动态规划就是状态与选择,贪心就是局部最优到全局最优。
动态规划,定义dp[i]表示在区间nums[0, i]中,以nums[i]为结尾的最大子数组的和,那么对于每一个dp[i]来说,它都可以选择把nums[i]是否追加到子数组的结尾,这个就是状态与选择,选择的条件是最大子数组的和,这一句话就把动态规划讲透了。
贪心:贪心更简单,只要子数组的和大于0我就一直加,只要小于0就离开开启一个新的子数组。

class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int max = nums[0];for(int i = 1; i < nums.length; i++) {dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);max = Math.max(max, dp[i]);}return max;}
}

三、912. 排序数组

题目链接:https://leetcode.cn/problems/sort-an-array/description/
思路:使用归并排序,时间复杂度为O(nlogn),空间复杂度为O(n)。

class Solution {int[] temp;public int[] sortArray(int[] nums) {temp = new int[nums.length];mergeSort(nums, 0, nums.length-1);return nums;}void mergeSort(int[] nums, int left, int right) {if(left >= right) return;int mid = left + (right - left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid+1, right);int i = left, j = mid + 1;int k = left;while(i <= mid && j <= right) {if(nums[i] <= nums[j]) {temp[k++] = nums[i++]; }else{temp[k++] = nums[j++];}}while(i <= mid) {temp[k++] = nums[i++]; }while(j <= right) {temp[k++] = nums[j++];}k = left;while(k <= right) {nums[k] = temp[k];k++;}}
}

四、21. 合并两个有序链表

题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/description/
思路:合并两个有序链表,类似于归并排序,比大小然后拼接,剩下的,直接拼接。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode root = new ListNode();ListNode p1 = list1, p2 = list2, p = root;while(p1 != null && p2 != null) {if(p1.val <= p2.val) {p.next = p1;p1 = p1.next;}else{p.next = p2;p2 = p2.next;}p = p.next;p.next = null;}if(p1 != null) {p.next = p1;}if(p2 != null) {p.next = p2;}return root.next;}
}

五、1. 两数之和

题目链接:https://leetcode.cn/problems/two-sum/description/
思路:两数之和,利用map,从map里找target - nums[i],找到了就找到了。

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i < nums.length; i++) {int t = target - nums[i];if(map.containsKey(t)) {return new int[] {i, map.get(t)};}else{map.put(nums[i], i);}}return new int[] {-1, -1};}
}

这篇关于力扣爆刷第104天之CodeTop100五连刷6-10的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/846745

相关文章

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

力扣接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 示例 2: 输入:height

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1

【代码随想录训练营第42期 续Day52打卡 - 图论Part3 - 卡码网 103. 水流问题 104. 建造最大岛屿

目录 一、做题心得 二、题目与题解 题目一:卡码网 103. 水流问题 题目链接 题解:DFS 题目二:卡码网 104. 建造最大岛屿 题目链接 题解:DFS  三、小结 一、做题心得 也是成功补上昨天的打卡了。 这里继续图论章节,还是选择使用 DFS 来解决这类搜索问题(单纯因为我更熟悉 DFS 一点),今天补卡的是水流问题和岛屿问题。个人感觉这一章节题对于刚

力扣 797. 所有可能路径【DFS】

1. 题目 2. 代码 DFS , 直接见代码 class Solution {public:vector<int> path;vector<vector<int>> res; // 结果集void dfs(vector<vector<int>>& graph, int cur, int n){// 找出所有从节点 0 到节点 n-1 的路径// 下标从 0 开始的if (

Java中等题-整数替换(力扣)

给定一个正整数 n ,你可以做如下操作: 如果 n 是偶数,则用 n / 2替换 n 。如果 n 是奇数,则可以用 n + 1或n - 1替换 n 。 返回 n 变为 1 所需的 最小替换次数 。 示例 1: 输入:n = 8输出:3解释:8 -> 4 -> 2 -> 1 示例 2: 输入:n = 7输出:4解释:7 -> 8 -> 4 -> 2 -> 1或 7 ->

力扣 | 递归 | 区间上的动态规划 | 486. 预测赢家

文章目录 一、递归二、区间动态规划 LeetCode:486. 预测赢家 一、递归 注意到本题数据范围为 1 < = n < = 20 1<=n<=20 1<=n<=20,因此可以使用递归枚举选择方式,时间复杂度为 2 20 = 1024 ∗ 1024 = 1048576 = 1.05 × 1 0 6 2^{20} = 1024*1024=1048576=1.05 × 10^