力扣爆刷第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;}
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/715175.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/715175.shtml
英文地址,請注明出處:http://en.pswp.cn/news/715175.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

JAVA學習筆記13(位運算)

1.位運算 1.1 原碼、反碼、補碼 ? *規則&#xff1a; ? 1.二進制的最高位是符號位&#xff1a;0表示正數&#xff0c;1表示負數 ? 2.正數的原碼&#xff0c;反碼&#xff0c;補碼都一樣&#xff08;三碼合一&#xff09; ? 3.負數的反碼 他的原碼符號位不變&#xff…

從metashape導出深度圖,從深度圖恢復密集點云

從metashape導出深度圖&#xff0c;從深度圖恢復密集點云 1.從metashape導出深度圖 參考&#xff1a;https://blog.csdn.net/WHU_StudentZhong/article/details/123107072?spm1001.2014.3001.5502 2.從深度圖建立密集點云 首先從metashape導出blockExchange格式的xml文件&…

OpenHarmony、HarmonyOS打開編輯 PDF 等操作的三方組件使用教程

項目場景: 隨著數字化時代的發展,PDF 文檔成為廣泛應用于各行業的重要文件格式。為了提高OpenHarmony/HarmonyOS生態系統的功能性和用戶體驗,我們需要一款支持打開、編輯PDF文件的應用程序。 使用戶能夠輕松打開、瀏覽和編輯PDF文件。該應用將充分利用OpenHarmony/HarmonyO…

【NTN 衛星通信】衛星和無人機配合的應用場景

1 場景概述 衛星接入網是一種有潛力的技術&#xff0c;可以為地面覆蓋差地區的用戶提供無處不在的網絡服務。然而&#xff0c;衛星覆蓋范圍對于位于考古或采礦地點內部/被茂密森林覆蓋的村莊/山谷/靠近山丘或大型建筑物的用戶可能很稀疏。因此&#xff0c;涉及衛星接入和無人駕…

HarmonyOS Full SDK的安裝

OpenHarmony的應用開發工具HUAWEI DevEco Studio現在隨著OpenHarmony版本發布而發布,只能在版本發布說明中下載,例如最新版本的OpenHarmony 4.0 Release。對應的需要下載DevEco Studio 4.0 Release,如下圖。 圖片 下載Full SDK主要有兩種方式,一種是通過DevEco Studio下載…

教你用Fiddler捕獲HTTPS請求

安裝Fiddler 這里不特別說明了&#xff0c;網上搜索一大把&#xff0c;根據安裝引導一步步安裝即可。&#xff08;這里采用的是fiddler v4.6&#xff09; 配置Fiddler 1、打開fiddler配置Tools –>Telerik Fiddler Options。 2、打開HTTPS配置項&#xff0c;勾選“Captur…

【程序員養生延壽系列-萬人關注的養生指南 4 】

1.早起一杯溫水&#xff0c;疏通腸胃&#xff0c;補充水分。 2.早十點和下午三點左右活動活動身體&#xff08;運動or健身&#xff09;&#xff0c;放松緊張疲憊的身體&#xff0c;幫助消化&#xff0c;給身體透個氣。 3.每天散步&#xff0c;好處多多&#xff08;減肥健身&a…

ctf_show筆記篇(web入門---爆破)

爆破 21&#xff1a;直接bp抓包跑字典&#xff0c;需base64加密 22&#xff1a;可用工具跑也可用瀏覽器找還可以用網上做好的域名查找去找 23&#xff1a;此題需跑腳本已經附上自寫腳本 最后跑出來六個答案一個一個嘗試得到答案為3j import hashlibm "0123456789qwert…

C++_AVL樹

目錄 1、AVL的概念 2、平衡因子的調整概念 3、AVL樹的插入 3.1 調整平衡因子代碼實現 3.2 右旋操作 3.2 左旋操作 3.3 雙旋-先右旋再左旋 3.4 雙旋-先左旋再右旋 3.5 旋轉操作的小結 4、AVL的驗證與實現 結語 前言&#xff1a; 在C中&#xff0c;AVL樹是在二叉搜索…

2024中國眼博會,山東省眼科醫學技術交流大會

以展帶會&#xff0c;以會促展&#xff0c;展與會有機結合&#xff0c;立足山東打造具全國影響力的眼康產業發展盛會&#xff1b; ——隨著時代的高速發展&#xff0c;科技的進步&#xff0c;現代生活節奏的加快&#xff0c;青少年近視問題日益嚴重&#xff0c;對兒童青少年的…

舊的Spring Security OAuth已停止維護,全面擁抱新解決方案Spring SAS

Spring Authorization Server 替換 Shiro 指引 背景 Spring 團隊正式宣布 Spring Security OAuth 停止維護&#xff0c;該項目將不會再進行任何的迭代 目前 Spring 生態中的 OAuth2 授權服務器是 Spring Authorization Server 已經可以正式生產使用作為 SpringBoot 3.0 的最新…

如何使用naive 做一個模態框的方式

1.我的問題使用了一個table 表格&#xff0c;在表格中設置倆個按鈕 最后做出來的效果 <template><div><h1>測試文件</h1><!-- 表格 --><n-data-table :columns"columns" :data"data" :pagination"pagination" …

Linux內核隊列queue.h

文章目錄 一、簡介二、SLIST單向無尾鏈表2.1 介紹2.2 操作2.3 例子 三、STAILQ單向有尾鏈表四、LIST雙向無尾鏈表五、TAILQ雙向有尾鏈表六、CIRCLEQ循環鏈表七、queue源碼參考 一、簡介 queue.h是一個非常經典的文件&#xff0c;定義了一系列宏的操作&#xff0c;它定義了一系…

筆記72:關于IMU(慣性測量單元)傳感器的作用【不涉及公式推導】

一、IMU傳感器是什么&#xff1a; 慣性測量單元IMU&#xff08;Inertial Measurement Unit&#xff09;是一種使用【加速度計】和【陀螺儀】來測量【物體三軸姿態角&#xff08;空間姿態&#xff09;】的裝置&#xff1b;IMU在坐標系的每個坐標軸上&#xff0c;均安裝有1個陀螺…

90-子集2(回溯算法)

題目 給你一個整數數組 nums &#xff0c;其中可能包含重復元素&#xff0c;請你返回該數組所有可能的子集&#xff08;冪集&#xff09;。 解集 不能 包含重復的子集。返回的解集中&#xff0c;子集可以按 任意順序 排列。 示例 1&#xff1a; 輸入&#xff1a;nums [1,2,2] …

深入理解CSS常見選擇器

標題&#xff1a;深入理解CSS常見選擇器 在CSS中&#xff0c;選擇器是一種強大的工具&#xff0c;用于定位和樣式化HTML文檔中的元素。通過選擇器的靈活運用&#xff0c;我們能夠精準地選擇需要操作的元素&#xff0c;從而實現豐富多彩的頁面布局和設計。本文將重點介紹常見的…

Vue2:用node+express部署Vue項目

一、編譯項目 命令 npm run build執行命令后&#xff0c;我們會在項目文件夾中看到如下生成的文件 二、部署Vue項目 接上一篇&#xff0c;nodeexpress編寫輕量級服務 1、在demo中創建static文件夾 2、將dist目錄中的文件放入static中 3、修改server.js文件 關鍵配置&…

全量知識系統問題及SmartChat給出的答復 之13 解析器+DDD+文法型

Q32. DDD的領域概念和知識系統中設計的解析器之間的關系。 那下面&#xff0c;我們回到前面的問題上來。 前面說到了三種語法解析器&#xff0c;分別是 形式語言的&#xff08;機器或計算機語言&#xff09;、人工語言的和自然語言的。再前面&#xff0c;我們聊到了DDD設計思…

基于java的學生派遣信息管理系統設計開題報告

歡迎添加微信互相交流學習哦&#xff01; 項目源碼&#xff1a;biye2: 畢業設計源碼 一、項目名稱 Java基于學生派遣信息管理系統設計 二、項目背景 隨著科技的發展&#xff0c;互聯網在我國的應用越來越廣泛&#xff0c;尤其是在教育領域。為了能更好地管理學生派遣信息&am…

DayDreamInGIS 之 ArcGIS Pro二次開發 圖層屬性中換行符等特殊字符替換

具體參考ArcMap中類似的問題&#xff0c;本帖開發一個ArcGISPro版的工具 1.基礎庫部分 插件開發&#xff0c;經常需要處理圖層與界面的交互。基礎庫把常用的交互部分做了封裝&#xff0c;方便之后的重復使用。 &#xff08;1&#xff09;下述類定義了數據存儲結構&#xff0…