資訊專欄INFORMATION COLUMN
摘要：示例輸入輸出示例輸入輸出說明輸出結果中的每個元素一定是唯一的。示例輸入輸出示例輸入輸出說明輸出結果中每個元素出現的次數，應與元素在兩個數組中出現次數的最小值一致。在完成所有重復項刪除操作后返回最終的字符串。
給定兩個字符串 s 和 t ，編寫一個函數來判斷 t 是否是 s 的字母異位詞。
注意：若 s 和 t 中每個字符出現的次數都相同，則稱 s 和 t 互為字母異位詞。
示例 1:
輸入: s = "anagram", t = "nagaram"輸出: true示例 2:
輸入: s = "rat", t = "car"輸出: false提示:
1 <= s.length, t.length <= 5 * 104s 和 t 僅包含小寫字母數組是一種最簡單的哈希表，因為兩個字符串只包含小寫字母所以我們可以設置一個長度為26的數組，0-25分別對應a-z出現的次數，最后再遍歷一次數組如果出現了不為1的元素就表明兩個字符串不是有效的字母異位詞
class Solution { public boolean isAnagram(String s, String t) { int[] result = new int[26]; for(int i = 0; i < s.length(); i++) { result[s.charAt(i) - "a"]++; } for(int j = 0; j < t.length(); j++) { result[t.charAt(j) - "a"]--; } for(int k = 0; k < 26; k++) { if(result[k] != 0) { return false; } } return true; }}O(n)
O(1)
給定兩個數組，編寫一個函數來計算它們的交集。
示例 1：
輸入：nums1 = [1,2,2,1], nums2 = [2,2]輸出：[2]示例 2：
輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]輸出：[9,4]說明：
這道題是虛假的求交集，即只是求出元素并不要求元素的個數所以我們可以聲明兩個set集合，然后將兩個set集合中包含的元素加入到結果數組中
也可以使用排序雙指針求解這里就不做演示了
class Solution { public int[] intersection(int[] nums1, int[] nums2) { HashSet<Integer> set = new HashSet<>(); HashSet<Integer> set0 = new HashSet<>(); int i = 0; for(int item : nums1) { set.add(item); } for(int item : nums2) { if(set.contains(item)) set0.add(item); } int[] result = new int[set0.size()]; for(int item : set0) { result[i] = item; i++; } return result; }}O(n)
O(n)
給定兩個數組，編寫一個函數來計算它們的交集。
示例 1：
輸入：nums1 = [1,2,2,1], nums2 = [2,2]輸出：[2,2]示例 2:
輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]輸出：[4,9]說明：
真正的求交集，和上一題一樣也是兩種思路，排序雙指針的會簡單一些
排序雙指針
class Solution { public int[] intersect(int[] nums1, int[] nums2) { //將數組排序 Arrays.sort(nums1); Arrays.sort(nums2); //定義雙指針分別指向兩個數組的頭部 int a = 0, b = 0; //定義結果集 int[] result = new int[Math.min(nums1.length,nums2.length)]; //定義遍歷結果集指針 int k = 0; while(a < nums1.length && b < nums2.length) { if(nums1[a] == nums2[b]) { //第一種情況：如果兩數相等就將數字加入到結果集中并讓兩個指針同時移動 result[k++] = nums1[a]; a++; b++; } else if(nums1[a] > nums2[b]) { //第二種情況：如果第一個數組的值大于第二個數組那么就讓值小的數組的指針前移 b++; } else { //第三種情況：如果第二個數組的值大于第一個數組那么就讓值小的數組的指針前移 a++; } } return Arrays.copyOfRange(result, 0, k); }}時間復雜度
O(n)
空間復雜度
O(n)
兩個map模擬并集
class Solution { public int[] intersect(int[] nums1, int[] nums2) { //存儲第一數組的元素和個數的key和value HashMap map0 = new HashMap<>(); //存儲第二個數組的元素和個數的key和value HashMap map1 = new HashMap<>(); //存儲并集 HashMap temp = new HashMap<>(); //將第一數組的元素和對應的元素存儲到map中 for(int i = 0; i < nums1.length; i++) { if(map0.containsKey(nums1[i])) { map0.replace(nums1[i], map0.get(nums1[i]) + 1); } else { map0.put(nums1[i], 1); } } //將第二數組的元素和對應的元素存儲到map中 for(int j = 0; j < nums2.length; j++) { if(map1.containsKey(nums2[j])) { map1.replace(nums2[j], map1.get(nums2[j]) + 1); } else { map1.put(nums2[j], 1); } } //模擬并集的過程，將兩個數組的相同元素作為key并將元素個數的最小值作為value存儲到result結集合中 for(int index : map0.keySet()) { if(map1.containsKey(index)) { temp.put(index,Math.min(map0.get(index), map1.get(index))); } } //定義數組長度 int length = 0; //將并集的長度求出來 //具體做法為將result集合中所有的value求和 for(int index : temp.values()) { length += index; } //定義返回數組 int[] result = new int[length]; /** * k 用來遍歷數組 * e 限制每個key的value循環 */ int k = 0, e = 0; for(int index : temp.keySet()) { e = 0; while(e < temp.get(index)) { result[k++] = index; e++; } } return result; }} 時間復雜度
O(n)
空間復雜度
O(n)
編寫一個算法來判斷一個數 n 是不是快樂數。
「快樂數」定義為：
如果 n 是快樂數就返回 true ；不是，則返回 false 。
示例 1：
輸入：n = 19輸出：true解釋：12 + 92 = 8282 + 22 = 6862 + 82 = 10012 + 02 + 02 = 1示例 2：
輸入：n = 2輸出：false提示：
1 <= n <= 231 - 1將數通過%10分離個位數再通過/10移除個位數并讓其他位數順位減一，將分離完的個位數依次平方求和然后儲存到set集合中，循環這個過程，如果平方和和set中的元素重復那么這個數就不是快樂數
class Solution { public boolean isHappy(int n) { //定義哈希set存儲每次sum的值如果添加sum的時候sum重復了那就返回false HashSet set = new HashSet<>(); int sum = n; //如果sum不為1 while(sum != 1) { if(set.contains(sum)){ return false; }else{ set.add(sum); } sum = 0; while(n != 0) { sum += Math.pow(n % 10, 2); n /= 10; } n = sum; } return true; }} O(logn)
O(logn)
給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 target 的那 兩個 整數，并返回它們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重復出現。
你可以按任意順序返回答案。
示例 1：
輸入：nums = [2,7,11,15], target = 9輸出：[0,1]解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：
輸入：nums = [3,2,4], target = 6輸出：[1,2]示例 3：
輸入：nums = [3,3], target = 6輸出：[0,1]提示：
這道題求解思路很多，暴力硬A的，二分查找，也可以使用哈希表來求得
使用目標數字減去數組的值如果map中存在那么就返回這兩個值如果map中不存在那么就將這個數組元素和數組下標存入map中
class Solution { public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; if(nums == null || nums.length == 0) { return result; } HashMap<Integer,Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++) { int temp = target - nums[i]; if(map.containsKey(temp)) { result[0] = i; result[1] = map.get(temp); return result; } map.put(nums[i], i); } return result; }}O(n)
O(n)
給你四個整數數組 nums1、nums2、nums3 和 nums4 ，數組長度都是 n ，請你計算有多少個元組 (i, j, k, l) 能滿足：
示例 1：
輸入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]輸出：2解釋：兩個元組如下：1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 02. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0示例 2：
輸入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]輸出：1提示：
因為題解的最后是需要得到能夠構成0的個數，所以我們可以將前兩個數組的元素之和求出同時統計出現的次數記錄到map中，然后再統計剩余元素的和，在map中尋找后兩個元素相加求和的相反數如果能找到就記錄出現的次數
class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map<Integer, Integer> map = new HashMap<>(); int temp; int res = 0; //統計兩個數組中的元素之和，同時統計出現的次數，放入map for (int i : nums1) { for (int j : nums2) { temp = i + j; if (map.containsKey(temp)) { map.put(temp, map.get(temp) + 1); } else { map.put(temp, 1); } } } //統計剩余的兩個元素的和，在map中找是否存在相加為0的情況，同時記錄次數 for (int i : nums3) { for (int j : nums4) { temp = i + j; if (map.containsKey(0 - temp)) { res += map.get(0 - temp); } } } return res; }}O(n^2)
O(n)
為了不在贖金信中暴露字跡，從雜志上搜索各個需要的字母，組成單詞來表達意思。
給你一個贖金信 (ransomNote) 字符串和一個雜志(magazine)字符串，判斷 ransomNote 能不能由 magazines 里面的字符構成。
如果可以構成，返回 true ；否則返回 false 。
magazine 中的每個字符只能在 ransomNote 中使用一次。
示例 1：
輸入：ransomNote = "a", magazine = "b"輸出：false示例 2：
輸入：ransomNote = "aa", magazine = "ab"輸出：false示例 3：
輸入：ransomNote = "aa", magazine = "aab"輸出：true提示：
因為只需要magazine中的字符在ransomNote中出現的次數一致就可以了，所以我們用數組來記錄贖金信中的字母及其個數，然后將雜志中的元素進行比對
class Solution { public boolean canConstruct(String ransomNote, String magazine) { int[] result = new int[26]; for(int i = 0; i < ransomNote.length(); i++) { // 遍歷贖金信并記錄次數 result[ransomNote.charAt(i) - "a"]++; } for(int j = 0; j < magazine.length(); j++) { // 將雜志中的字符串和贖金信中的做比對 if(result[magazine.charAt(j) - "a"] != 0) result[magazine.charAt(j) - "a"]--; } for(int i = 0; i < 26; i++) { if(result[i] != 0) return false; } return true; }}O(n + m)
O(1)
給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為 0 且不重復的三元組。
注意：答案中不可以包含重復的三元組。
示例 1：
輸入：nums = [-1,0,1,2,-1,-4]輸出：[[-1,-1,2],[-1,0,1]]示例 2：
輸入：nums = []輸出：[]示例 3：
輸入：nums = [0]輸出：[]排序雙指針，首先確認第一個元素，如果第一個元素大于0就沒有后續的必要了，因為不可以包含重復的三元組所以還涉及到了去重的操作，再確認好第一個元素之后，剩下兩個元素的值也很好確認可以使用雙指針來分別指向末尾和第一個元素后一位的元素
class Solution { public List<List<Integer>> threeSum(int[] nums) { //定義結果集LinkedList相比于ArrayList添加和刪除效率比較高 List> result = new LinkedList>(); //如果數組長度小于3就不需要進行后續操作了直接返回空的結果集即可 if(nums.length < 3) { return result; } //我們采用排序雙指針的方法方便去重的操作 Arrays.sort(nums); for(int i = 0; i < nums.length; i++) { //因為數組已經排過序了如果第一個值是正數后面就沒必要比較了 if(nums[i] > 0) break; //如果從數組第二個值開始，當前元素和前一個元素相同那么直接跳過本次循環 if(i > 0 && nums[i - 1] == nums[i]) continue; //a > b > c 由于第一個元素的確認我們把他看作常數對待那么 滿足函數 a(常數) + b(未知量) = -c(未知量) 形狀有點像 y = -x int left = i + 1; int right = nums.length - 1; while(left < right) { // temp = a + b + c if(nums[left] + nums[right] == -nums[i]) { result.add(new LinkedList(Arrays.asList(nums[i], nums[left], nums[right]))); left++; right--; //去重操作 while(left < right && nums[left] == nums[left - 1]) left++; while(left < right && nums[right] == nums[right + 1]) right--; } else if(nums[left] + nums[right] > -nums[i]) { right--; } else if(nums[left] + nums[right] < -nums[i]) { left++; } } } return result; }} O(n^2)
O(n)
這道題和15題核心思路基本一致
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { //創建結果集 List> result = new LinkedList>(); if(nums.length < 4) { return result; } //排序雙指針 Arrays.sort(nums); for(int i = 0; i < nums.length - 3; i++) { //去重 if(i > 0 && nums[i - 1] == nums[i]) { continue; } for(int j = i + 1; j < nums.length - 2; j++) { //去重 if(j > i + 1 && nums[j - 1] == nums[j]) { continue; } int left = j + 1; int right = nums.length - 1; int temp = target - nums[i] - nums[j]; while(left < right) { int sum = nums[left] + nums[right]; if(sum == temp) { result.add(new LinkedList(Arrays.asList(nums[i], nums[j], nums[left], nums[right]))); left++; right--; //去重 while(left < right && nums[left] == nums[left - 1]) left++; while(left < right && nums[right] == nums[right + 1]) right--; } else if(sum < temp) { left++; } else { right--; } } } } return result; }} 請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）：
實現 MyQueue 類：
模擬題仔細就可以了
class MyQueue { //定義兩個棧 Stack stack0 = null; Stack stack1 = null; //初始化兩個棧 public MyQueue() { stack0 = new Stack<>(); stack1 = new Stack<>(); } //如果棧1不為空那就先將棧1的元素全部出棧添加到棧0然后向棧0中添加新元素 public void push(int x) { if(stack1.size() != 0) { while(stack1.size() != 0) { stack0.push(stack1.pop()); } } stack0.push(x); } //如果棧0中包含元素那么就將所有元素出棧并添加到棧1中移除并返回棧1的棧頂元素 public int pop() { if(stack0.size() != 0) { while(stack0.size() != 0) { stack1.push(stack0.pop()); } } return stack1.pop(); } //如果棧0中包含元素那么就將所有元素出棧并添加到棧1中返回棧1的棧頂元素 public int peek() { if(stack0.size() != 0) { while(stack0.size() != 0) { stack1.push(stack0.pop()); } } return stack1.peek(); } //查看棧0和棧1中是否含有元素 public boolean empty() { return stack1.isEmpty() && stack0.isEmpty(); }} 模擬題我是使用一個隊列實現的
class MyStack { List<Integer> list0 = null; //初始化隊列 public MyStack() { list0 = new LinkedList(); } public void push(int x) { list0.add(x); } public int pop() { return list0.remove(list0.size() - 1); } public int top() { return list0.get(list0.size() - 1); } public boolean empty() { return list0.isEmpty(); }} 棧很適合用來做匹配消除，遍歷整個字符串，如果棧中元素不為空并且棧頂元素和對應的右括號匹配就彈出棧
class Solution { public boolean isValid(String s) { //定義一個棧 Stack stack = new Stack<>(); for(int i = 0; i < s.length(); i++) { if(!stack.isEmpty() && stack.peek() == isType(s.charAt(i))) { stack.pop(); continue; } stack.push(s.charAt(i)); } return stack.isEmpty(); } public char isType(char c) { char flag = "/0"; if(c == ")") { flag = "("; }else if(c == "]") { flag = "["; }else if(c == "}") { flag = "{"; } return flag; }} O(n)
O(n)
給出由小寫字母組成的字符串 S，重復項刪除操作會選擇兩個相鄰且相同的字母，并刪除它們。
在 S 上反復執行重復項刪除操作，直到無法繼續刪除。
在完成所有重復項刪除操作后返回最終的字符串。答案保證唯一。
輸入："abbaca"輸出："ca"解釋：例如，在 "abbaca" 中，我們可以刪除 "bb" 由于兩字母相鄰且相同，這是此時唯一可以執行刪除操作的重復項。之后我們得到字符串 "aaca"，其中又只有 "aa" 可以執行重復項刪除操作，所以最后的字符串為 "ca"。/** * 第一種思路，用棧來實現 * 依次將字符串的字符入棧如果兩兩相當，那么就消除 */class Solution { public String removeDuplicates(String s) { LinkedList<Character> queue = new LinkedList<>(); char temp; for(int i = 0; i < s.length(); i++) { temp = s.charAt(i); // 如果棧為空或者棧頂元素不等于temp就入棧，否則就出棧 if(queue.isEmpty() || queue.peek() != temp) { queue.push(temp); } else { queue.pop(); } } // 剩余的元素就是最終字符串,但是由于棧的結構所以得出來的字符串是反的需要換一下 String result = ""; while(!queue.isEmpty()) { result += queue.pop(); } result = new StringBuffer(result).reverse().toString(); return result; }}/** * 第二種思路，字符串模擬棧 */class Solution { public String removeDuplicates(String s) { StringBuffer buffer = new StringBuffer(); char temp; // 記錄buffer的長度，為什么是-1？ // 之所以是-1是因為第一個元素是默認添加的，它的索引值為0，此時為了能夠判斷第二次循環條件， // l模仿指向棧頂 int l = -1; for(int i = 0; i < s.length(); i++) { temp = s.charAt(i); // 如果此時字符串的尾部元素和temp相同那么就把字符串尾部刪除,為了添加第一個元素所以需要設置temp >= 0 if(l >= 0 && temp == buffer.charAt(l)) { buffer.deleteCharAt(l); l--; } else { buffer.append(temp); l++; } } return buffer.toString(); }}/** * 第三種思路，雙指針法,直接使用現有字符串使用雙指針覆蓋重復的元素 */class Solution { public String removeDuplicates(String s) { char[] c = s.toCharArray(); int slow = 0; for(int fast = 0; fast < s.length(); fast++) { c[slow] = c[fast]; // 如果slow指向的元素和slow-1所指向的元素相等那么就讓slow指針后移，下次循環直接就覆蓋掉了 if(slow > 0 && c[slow] == c[slow - 1]) { slow--; } else { slow++; } } return new String(c,0,slow); }}根據 逆波蘭表示法，求表達式的值。
有效的算符包括 +、-、*、/ 。每個運算對象可以是整數，也可以是另一個逆波蘭表達式。
說明：
示例 1：
輸入：tokens = ["2","1","+","3","*"]輸出：9解釋：該算式轉化為常見的中綴算術表達式為：((2 + 1) * 3) = 9示例 2：
輸入：tokens = ["4","13","5","/","+"]輸出：6解釋：該算式轉化為常見的中綴算術表達式為：(4 + (13 / 5)) = 6求解逆波蘭表達式，如果是數字直接入棧，如果是操作符，從棧中取出兩個元素進行操作后再壓入棧
class Solution { public int evalRPN(String[] tokens) { //定義一個棧便于存儲運算數字 Stack<Integer> stack = new Stack<Integer>(); //因為遍歷到+ - * /需要出棧兩個字符計算后入棧所以設置兩個變量 int a = 0; int b = 0; for(int i = 0; i < tokens.length; i++) { if ("+".equals(tokens[i])) { a = stack.pop(); b = stack.pop(); stack.push(b + a); } else if ("-".equals(tokens[i])) { a = stack.pop(); b = stack.pop(); stack.push(b - a); } else if ("*".equals(tokens[i]))
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/124497.html
摘要：此專欄文章是對力扣上算法題目各種方法的總結和歸納整理出最重要的思路和知識重點并以思維導圖形式呈現當然也會加上我對導圖的詳解目的是為了更方便快捷的記憶和回憶算法重點不用每次都重復看題解畢竟算法不是做了一遍就能完全記住的所 ...
摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖，寫出一個函數找到所有的最小高度樹并返回他們的根節點。因此使用一個數組代表每個節點的入度，若入度為就是葉子節點。 題目地址：https://leetcode-cn.com/probl...題目描述： 對于一個具有樹特征的無向圖，我們可選擇任何一個節點作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
閱讀 1107·2021-11-23 09:51
閱讀 1073·2021-10-18 13:31
閱讀 2965·2021-09-22 16:06
閱讀 4255·2021-09-10 11:19
閱讀 2195·2019-08-29 17:04
閱讀 424·2019-08-29 10:55
閱讀 2471·2019-08-26 16:37
閱讀 3368·2019-08-26 13:29
