专栏首页营琪的小记录算法:HashTable、List、Map、Set-实战

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法:优先队列-实战

    这个arr数组要是比较小,可以直接用快速排序,再输出第K大的值。时间复杂度O(N*K*logk)

    营琪
  • 算法:递归和分治-实战

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    营琪
  • Java的基础程序设计结构(Java学习-1)

    注释就是方便自己或者别人阅读代码,绝大多数的程序语言都有注释这个功能,大部分的注释命令都是相同的或者想通的,

    营琪
  • LeetCode第六天

    第六天 30.(219) Contains Duplicate II ? JAVA class Solution { public boolean co...

    郭耀华
  • 2019 第十届蓝桥杯C/C++ 省赛B组题解

    又是一年一度的蓝桥杯,这次也应该是我大学最后一次学科竞赛了,今年的省赛题型和往届有些不同,代码填空没有了,只有结果填空和编程大题,不过坑还是一样的多,稍不注意就...

    指点
  • LintCode-373.奇偶分割数组

    悠扬前奏
  • Leetcode Golang 27. Remove Element.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88902476

    anakinsun
  • Leetcode Golang 162. Find Peak Element.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/arti...

    anakinsun
  • 每日算法系列【LeetCode 153】寻找旋转排序数组中的最小值

    (例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2])。

    godweiyang
  • Leetcode 80 Remove Duplicates from Sorted Array II

    Follow up for "Remove Duplicates": What if duplicates are allowed at most twic...

    triplebee

扫码关注云+社区

领取腾讯云代金券