演算法：HashTable、List、Map、Set-實戰
- 2019 年 11 月 4 日
- 筆記
版權聲明：本文為部落客原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。
本文鏈接：https://blog.csdn.net/weixin_43126117/article/details/97632634
實戰的題目都是leetcode的題目。
leetcode:242有效字母異位詞
第一種解法：排序
思路：通過對字元串排序，再比較是否相同，如 s=213，t=321 排序後 s=123,t=123，比較是否相同。時間複雜度O(NlogN)。
class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } byte[] ss = t.getBytes(); byte[] tt = s.getBytes(); Arrays.sort(ss); //排序 Arrays.sort(tt); for (int i = 0 ; i < ss.length ; i++){ if (ss[i] != tt[i]) { //比較是否相等 return false; } } return true; } }
第二種方法：利用Map記數
思路：先把字元串轉變為字元數組，遍歷字元數組，把每個字元存入Map中，並判斷Map中是否存在此字元，存在則計數加一。
class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; final Map<Character, Integer> map = new HashMap<>(); for (int i = 0 ; i < s.length() ;i++) { //根據元素計數 Character c = s.charAt(i); Integer num = map.get(c); if (num != null) { map.put(c, num + 1); } else { map.put(c, 1); } } for (int i = 0 ; i < s.length() ;i++) { //根據元素 反計數 Character c = t.charAt(i); Integer num = map.get(c); if (num != null) { map.put(c, num-1); } else { return false; } } for (Map.Entry<Character,Integer> entry:map.entrySet()){ if (entry.getValue() != 0) { return false; } } return true; } }
第三種方法:特殊哈希表法
思路：因為這道題比較特殊，傳遞的值只有小寫字母，這樣我們可以創建一個26個空間的數組充當 哈希表， 哈希值由字元的ASCII代替
public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; int[] counter = new int[26]; for (int i = 0; i < s.length(); i++) { counter[s.charAt(i) - 'a']++; //這相當於哈希表 if (--counter[t.charAt(i) - 'a'] < 0) return false; } for (int count : counter) { if (count != 0) return false; } return true; }
leetcode:1兩數之和
方法一、暴力法
思路:兩次循環就行了，判斷倆個數相加是否等於target，等於則返回數組下標。時間複雜度O(N^2)，是特別慢的。
class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i+ 1; j <nums.length; j++) { if (i == j) continue; if (nums[i] + nums[j] == target) return new int[]{i,j}; } } return null; } }
方法二、利用Map存取下標和值
思路：主要就是把數組下標和值存取到Map中，再在Map中查詢對應的值，有則返回下標。
public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0 ; i < nums.length ; i++) { int result = target - nums[i]; if (map.containsKey(result)) return new int[]{i,map.get(result)}; map.put(nums[i],i); } return null; }
leetcode:15三數之和
方法一、暴力法
思路：三次循環找出相加等於零即可，判斷三元組是否重複
public List<List<Integer>> threeSum2(int[] nums) { List list = new ArrayList<List<Integer>>(); Set set = new HashSet(); for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { for (int t = j + 1; t < nums.length; t++) { if (nums[i] + nums[j] + nums[t] == 0){ int[] arr = {nums[i] , nums[j] , nums[t]}; Arrays.sort(arr); if (set.contains(arr[0]+""+ arr[1]+""+ arr[2])) break; set.add(arr[0]+""+ arr[1]+""+ arr[2]); List stor = new ArrayList<Integer>(); stor.add(nums[i]); stor.add(nums[j]); stor.add(nums[t]); list.add(stor); break; } } } } return list; } //或者不用SET 去重 public List<List<Integer>> threeSum2(int[] nums) { final ArrayList<List<Integer>> lists = new ArrayList<>(); Arrays.sort(nums); // long count = 0; for (int i = 0; i < nums.length - 2; i++) { if (nums[i] > 0) { break; } if (i > 0 && nums[i] == nums[i - 1]) { continue; } int maxIndex = nums.length - 1; for (int j = i + 1; j < maxIndex; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } for (int k = maxIndex; k > j; k--) { // count++; final int sum = nums[i] + nums[j] + nums[k]; if (sum == 0) { final ArrayList<Integer> integers = new ArrayList<>(); integers.add(nums[i]); integers.add(nums[j]); integers.add(nums[k]); lists.add(integers); maxIndex = k; break; } else if (sum < 0) { break; } } } } return lists; }
方法二、快排後往中間夾
public static List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ans = new ArrayList(); Arrays.sort(nums); // 排序 int len = nums.length; if(nums == null || len < 3) return ans; for (int i = 0; i < len ; i++) { if(nums[i] > 0) break; // 如果當前數字大於0，則三數之和一定大於0，所以結束循環 if(i > 0 && nums[i] == nums[i-1]) continue; // 去重 int L = i+1; int R = len-1; while(L < R){ int sum = nums[i] + nums[L] + nums[R]; if(sum == 0){ ans.add(Arrays.asList(nums[i],nums[L],nums[R])); while (L<R && nums[L] == nums[L+1]) L++; // 去重 while (L<R && nums[R] == nums[R-1]) R--; // 去重 L++; R--; } else if (sum < 0) L++; else if (sum > 0) R--; } } return ans; }
