算法：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; }
