2020-06-16

LeetCode哈希表

面试10.02 变位词组(HashMap)

题目

分析

统计26个字母各自出现的次数，得到一个大小为26的int数组。
关键在于如何将这个int数组转换为独一无二的key。
我的方法是将它转为String。

代码

public class BianWeiArr {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String[] a={"eat","tea","tan","ate","nat","bat"};
        System.out.println(groupAnagrams(a));
    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        int len=strs.length;  //获取字符串的长度
        HashMap<String,List<String>> map=new HashMap<>(len); //生成一个map获取
        for(String str:strs){
            int[] count=new int[26];  //新建count数组存放每个字符出现次数
            for(int i=0;i<str.length();i++){
                count[str.charAt(i)-'a']++;  //通过ascii码判断
            }
            StringBuilder sb=new StringBuilder(100);
            for(int num:count){
                sb.append(num+".");  //26位每一位粘贴过来
            }
            map.computeIfAbsent(sb.toString(),unused -> new LinkedList<>()).add(str);
        }
        return new ArrayList<>(map.values());  //返回新的集合
    }

}

结果

面试16.02 单词频率(HashMap)

题目

分析

第一个函数通过hashmap存放次数
第二个函数判断是不是有这个单词 返回这个单词次数

代码


class WordsFrequency {
    Map<String,Integer> recMap = new HashMap<>();
    public WordsFrequency(String[] book) {
        for(int i=0;i<book.length;i++) {
            if(!recMap.containsKey(book[i])) {
                recMap.put(book[i],1);
            }else {
                recMap.put(book[i], recMap.get(book[i])+1);
            }
        }
    }

    public int get(String word) {
        if(recMap.containsKey(word)) {
            return recMap.get(word);
        }
        return 0;
    }
}

/**
 * Your WordsFrequency object will be instantiated and called as such:
 * WordsFrequency obj = new WordsFrequency(book);
 * int param_1 = obj.get(word);
 */

结果

剑指offer50 第一次只出现一次的字符(count[s.charAt(i)-97]==1)

题目

分析

1. 主要是通过count数组统计每次出现次数
2. for循环让每一位的值对应的count数组查看是否为1 有就退出因为找第一个(count[s.charAt(i)-97]==1）

代码


public class OnlyOne {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String s=input.next();
        System.out.println(firstUniqChar(s));
    }

    public static char firstUniqChar(String s) {
        int[] count=new int[26];
        char c=' ';
        for(int i=0;i<s.length();i++){
            count[s.charAt(i)-97]++;
        }
        for(int i=0;i<s.length();i++){
            if(count[s.charAt(i)-97]==1){
                c=s.charAt(i);
                break;
            }
        }
        return c;
    }

}

结果

面试16.24 数对和(双指针+list集合)

题目

分析

1. 先试用双指针进行控制得到结果的end和start两端，
2. 每次找到就新建一个list添加进去两个值之后添加到最终的ans里面

代码

public class ShuDuiHe {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<a.length;i++){
            a[i]=input.nextInt();
        }
        int target=input.nextInt();
        System.out.println(pairSums(a,target));
    }

    public static List<List<Integer>> pairSums(int[] nums, int target) {
        List<List<Integer>> ans=new LinkedList<>();
        Arrays.sort(nums); //对数组进行排序
        int start=0;
        int end=nums.length-1;
        for(;start<end;){
            int sum = nums[start] + nums[end];
            if (sum < target) {  //要变大一些
                start++;
            } else if (sum > target){  //要变小一些
                end--;
            } else {   //刚好符合
                List<Integer> list = new LinkedList<>(); //新成立list集合
                list.add(nums[start]); //存进去start和end位置的值
                list.add(nums[end]);
                ans.add(list);  //最终结果添加list集合
                start++; //缩小范围
                end--;
            }
        }
        return ans;
    }

}