力扣爆刷第84天之hot100五连刷6-10

2024-03-03 06:52

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

力扣爆刷第84天之hot100五连刷6-10

文章目录

      • 力扣爆刷第84天之hot100五连刷6-10
      • 一、15. 三数之和
      • 二、42. 接雨水
      • 三、3. 无重复字符的最长子串
      • 四、438. 找到字符串中所有字母异位词
      • 五、560. 和为 K 的子数组

一、15. 三数之和

题目链接:https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked
思路:三数之和和两数之和类似都是使用双指针进行操作,只不过nums数组内包含重复元素,需要考虑去重的操作,先排序,然后外层一个for内层双指针即可完成遍历,完成去重有两步。
一步: if (i > 0 && nums[i] == nums[i-1]) continue;杜绝相同的nums[i]。
二步:当nums[j]+nums[k]==nums[i]时,务必保证nums[j]和nums[k]不再重复。

while(j < k && nums[j] == nums[j+1]) j++;
while(j < k && nums[k] == nums[k-1]) k--;
j++;
k--;
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> array = new ArrayList<>();Arrays.sort(nums);int len = nums.length;for(int i = 0; i < len-2; i++) {if (nums[i] > 0) break;if (i > 0 && nums[i] == nums[i-1]) continue;int j = i+1, k = len-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]);array.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 array;}
}

二、42. 接雨水

题目链接:https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
思路:接雨水是典型的单调栈问题,只需要构造出来凹型即可,也就是栈内,自栈底到栈顶是递减的,当遇到大于栈顶的元素时,就弹出栈顶,此时栈顶即为凹槽,然后计算面积即可。

class Solution {public int trap(int[] height) {Deque<Integer> stack = new LinkedList<>();int sum = 0;for(int i = 0; i < height.length; i++) {while(!stack.isEmpty() && height[stack.peek()] < height[i]) {int mid = stack.pop();if(!stack.isEmpty()) {int h = Math.min(height[i], height[stack.peek()]) - height[mid];int w = i - stack.peek() - 1; sum += h * w;}}stack.push(i);}return sum;}
}

三、3. 无重复字符的最长子串

题目链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked
思路:如s = “abcabcbb” 长度为3,典型的滑动窗口,使用set维护不重复的子串,每次新加入元素后,更新最大长度,如果遇到重复元素,则开始缩小窗口,直到当前元素不重复,才继续开始扩大窗口。

class Solution {public int lengthOfLongestSubstring(String s) {int max = 0;Set<Character> set = new HashSet<>();int slow = 0;for(int i = 0; i < s.length(); i++) {while(set.contains(s.charAt(i))) {set.remove(s.charAt(slow));slow++;}set.add(s.charAt(i));max = Math.max(max, set.size());}return max;}
}

四、438. 找到字符串中所有字母异位词

题目链接:https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
思路:一看是异位词基本上就得使用set或map来处理,字符串的长度又巨长,10的4次方,常规遍历自然超时,需要使用双指针去掉一层循环,即使用滑动窗口,维护好字符串窗口,开始时扩大窗口,顺便记录标记值,当窗口达到p字符串长度时,进行判断,看看标记值是否符合,然后缩减窗口,这样一次循环结束。
滑动窗口模板:

/* 滑动窗口算法框架 */
void slidingWindow(String s) {// 用合适的数据结构记录窗口中的数据HashMap<Character, Integer> window = new HashMap<>();int left = 0, right = 0;while (right < s.length()) {// c 是将移入窗口的字符char c = s.charAt(right);window.put(c, window.getOrDefault(c, 0) + 1);// 增大窗口right++;// 进行窗口内数据的一系列更新.../*** debug 输出的位置 ***/// 注意在最终的解法代码中不要 print// 因为 IO 操作很耗时,可能导致超时System.out.printf("window: [%d, %d)\n", left, right);/********************/// 判断左侧窗口是否要收缩while (left < right && window needs shrink) {// d 是将移出窗口的字符char d = s.charAt(left);window.put(d, window.get(d) - 1);// 缩小窗口left++;// 进行窗口内数据的一系列更新...}}
}

题解:

class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> list = new ArrayList<>();int sLen = s.length(), pLen = p.length();if(pLen > sLen) return list;Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();for(char c : p.toCharArray()) {need.put(c, need.getOrDefault(c, 0)+1);}int left = 0, right = 0, valid = 0;while(right < sLen) {char rc = s.charAt(right);right++;if(need.containsKey(rc)) {window.put(rc, window.getOrDefault(rc, 0)+1);if(window.get(rc).equals(need.get(rc))) {valid++;}}if(right - left == pLen) {if(valid == need.size()) {list.add(left);}char lc = s.charAt(left);left++;if(need.containsKey(lc)) {if(window.get(lc).equals(need.get(lc))) {valid--;}window.put(lc, window.get(lc)-1);}}}return list;}
}

五、560. 和为 K 的子数组

题目链接:https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked
思路:求和为k的子数组,其实就是前缀和,和使用前缀和数组的题目有点像,但是为了少一层for,把原本要存入前缀和数组的值,都存进了hashmap,然后只需要用preSum - k 去map中寻找value即可。

class Solution {public int subarraySum(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>();map.put(0, 1);int count = 0, preSum = 0;for(int i = 0; i < nums.length; i++) {preSum += nums[i];if(map.containsKey(preSum - k)) {count += map.get(preSum - k);}map.put(preSum, map.getOrDefault(preSum, 0)+1);}return count;}
}

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



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

相关文章

两数之和--力扣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,那么它的

hot100刷题第1-9题,三个专题哈希,双指针,滑动窗口

求满足条件的子数组,一般是前缀和、滑动窗口,经常结合哈希表; 区间操作元素,一般是前缀和、差分数组 数组有序,更大概率会用到二分搜索 目前已经掌握一些基本套路,重零刷起leetcode hot 100, 套路题按套路来,非套路题适当参考gpt解法。 一、梦开始的地方, 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣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

力扣 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 (

【Hot100】LeetCode—394. 字符串解码

目录 1- 思路栈实现+四种情况处理 2- 实现⭐394. 字符串解码——题解思路 3- ACM 实现 原题链接:394. 字符串解码 1- 思路 栈实现+四种情况处理 ① 遇到数字,进行倍数相加 、②遇到左括号,压栈之前的元素、③遇到右括号弹出,栈进行拼接、④否则遇到字母,直接拼接在 res通过栈,实现先进后出的思想 对于输入 3[a2[c]] 的输入,在读到 3[得

【Hot100】LeetCode—347. 前 K 个高频元素

目录 1- 思路自定义Node结点 + 哈希表实现 2- 实现⭐347. 前 K 个高频元素——题解思路 3- ACM实现 原题连接:347. 前 K 个高频元素 1- 思路 自定义Node结点 + 哈希表实现 ① 自定义 Node 结点: 自定义 Node 结点中有 value 和 cnt 字段,其中 value 为具体的数字,cnt 为具体的值实现 ① getCn