算法：HashTable、List、Map、Set-实战
版权声明：本文为博主原创文章，遵循 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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-07-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录