算法|有效的字母异位词、赎金信、找到字符串中所有字母异位词、字母

一、242. 有效的字母异位词

题目连接：https://leetcode.cn/problems/valid-anagram/
思路：使用hash思想，将字母key转化为数组的索引，value存的每个字母的数量，在t中减去数量，在遍历数组，不等于0的即是不存在或者的少于字母

class Solution {
    public boolean isAnagram(String s, String t) {
        int record[] = new int[26];
        for (int i = 0; i < s.length(); i++) {
            record[s.charAt(i) - 'a']++; 
        }

        for (int i = 0; i < t.length(); i++) {
            record[t.charAt(i) - 'a']--;
        }
        for (int i = 0; i < record.length; i++) {
            if (record[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

二、 383. 赎金信

题目连接：https://leetcode.cn/problems/ransom-note/
思路：先统计magszine里面的每个字符的的数量，在扫描ransomNote，在扫描的过程，数量--，如果每个字符的数量小于了0，则证明magazine里面的字符不够可以拼成ransomNote

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] hash = new int[26];
        for (int i = 0; i < magazine.length(); i++){
            hash[magazine.charAt(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++){
            hash[ransomNote.charAt(i) - 'a']--;
            if (hash[ransomNote.charAt(i) - 'a'] < 0) return false;
        }

        return true;
    }
}

三、438. 找到字符串中所有字母异位词

题目连接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/
1、暴力方法

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();

        int pLength = p.length();
        int sLength = s.length();
        for (int i = 0; i < sLength - pLength + 1; i++){
            int hash[] = new int[26];
            for (int k = 0; k < pLength; k++){
                hash[p.charAt(k) - 'a']++;
            }
            for (int j = i; j < i + pLength ; j++) {
                hash[s.charAt(j) - 'a']--;
            }
            boolean isHave = true;
            for (int g = 0; g < hash.length; g++){
                if (hash[g] != 0) {
                    isHave = false;
                    break;
                }
            }
            if (isHave) result.add(i);
        }
        return result;
    }
}

2、使用滑动窗口思想，不断修改窗口的起始位置统计数量，比较两个统计数量的集合是否相同

class Solution {
    private boolean isArraysEquals(int[] sHash, int[] pHash) {
        if (sHash == null || pHash == null) {
            return false;
        }
        if (sHash.length != pHash.length) return false;
        for (int i = 0; i < sHash.length; i++) {
            if (sHash[i] != pHash[i]) return false;
        } 
        return true;
    }
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int sLength = s.length();
        int pLength = p.length();
        if (sLength < pLength){
            return result;
        }
        int[] sHash = new int[26];
        int[] pHash = new int[26];
        for (int i = 0; i < pLength; i++){
            sHash[s.charAt(i) - 'a']++;
            pHash[p.charAt(i) - 'a']++;
        }
        if (isArraysEquals(sHash, pHash)) {
            result.add(0);
        }


        for (int i = pLength; i < sLength; i++){
            sHash[s.charAt(i - pLength) - 'a']--;
            sHash[s.charAt(i) - 'a']++;
            if (isArraysEquals(sHash, pHash)){
                result.add(i - pLength + 1);
            }
        }
        return result;
    }
}

四、349. 两个数组的交集

题目连接：https://leetcode.cn/problems/intersection-of-two-arrays/
思路：将nums1去重放入num1Set，遍历nums2,如果在num1Set,就放入结果集中
方法一、

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> num1Set = new HashSet<>();
        for (int i = 0; i < nums1.length; i++){
            num1Set.add(nums1[i]);
        }
        HashSet<Integer> resultHashSet = new HashSet<>();
        for (int i = 0; i < nums2.length; i++){
            if (num1Set.contains(nums2[i])) {
                resultHashSet.add(nums2[i]);
            }
        }
        int[] result = new int[resultHashSet.size()];
        int index = 0;
        Iterator<Integer> iterator = resultHashSet.iterator();
        while (iterator.hasNext()) {
            result[index++] = iterator.next();
        }

        return result;
        
    }
}

方法二、

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] hash = new int[1001];
        for (int i = 0; i < nums1.length; i++) {
            hash[nums1[i]] = 1;
        }
        HashSet<Integer> resultHashSet = new HashSet<>();
        for (int i = 0; i < nums2.length; i++){
            if (hash[nums2[i]] == 1) resultHashSet.add(nums2[i]);
        }
        
        int[] result = new int[resultHashSet.size()];
        Iterator<Integer> iterator = resultHashSet.iterator();
        int index = 0;
        while (iterator.hasNext()) {
            result[index++] = iterator.next();
        }
        return result;
    }
}

五、350. 两个数组的交集 II

题目连接：https://leetcode.cn/problems/intersection-of-two-arrays-ii/
方法一、

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        int[] hash = new int[1001];
        for (int i = 0; i < nums1.length; i++){
            hash[nums1[i]]++; 
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums2.length; i++){
            if (hash[nums2[i]] != 0) {
                list.add(nums2[i]);
                hash[nums2[i]]--;
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < result.length; i++){
            result[i] = list.get(i);
        }
        return result;
    }
}

方法二、

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums1.length; i++){
            hashMap.put(nums1[i], hashMap.getOrDefault(nums1[i], 0) + 1);
        }
        ArrayList<Integer> resultList = new ArrayList<>();
        for (int i = 0; i < nums2.length; i++){
            if (hashMap.getOrDefault(nums2[i], 0) != 0){
                resultList.add(nums2[i]);
                hashMap.put(nums2[i], hashMap.getOrDefault(nums2[i], 0) - 1);
            }
        }
        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++){
            result[i] = resultList.get(i);
        }
        return result;
        
    }
}

六、 49. 字母异位词分组

题目连接：https://leetcode.cn/problems/group-anagrams/
思路：使用hashmap key存排序后的str, value即异位词集合

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, ArrayList<String>> hashmap = new HashMap<>();
        for (int i = 0; i < strs.length; i++){
            String el = strs[i];
            char[] cs = el.toCharArray();
            Arrays.sort(cs);
            String elNew = String.valueOf(cs);
            if (!hashmap.containsKey(elNew)) {
                hashmap.put(elNew, new ArrayList<String>());
            }
            hashmap.get(elNew).add(el);
        }
        return new ArrayList(hashmap.values());
    }
}

七、 202. 快乐数

题目连接：https://leetcode.cn/problems/happy-number/
思路：使用hashSet 判断和是否出现过，出现就终止判断是否n==1

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
       HashMap<String, ArrayList<String>> hashMap = new HashMap<>();
       for (String str:strs){
           char[] cs = str.toCharArray();
           Arrays.sort(cs);
           String strSort = String.valueOf(cs);
           if (hashMap.get(strSort) == null) {
               hashMap.put(strSort, new ArrayList<String>());
           }
           hashMap.get(strSort).add(str);
       }
       return new ArrayList<>(hashMap.values());
    }
}

八、1. 两数之和

题目连接：https://leetcode.cn/problems/two-sum/
思路一、暴力法（复杂度不过）

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++) {
             System.out.println(nums[i] + " " + nums[j]);
             if (nums[i] + nums[j] == target) {
                 
                 return new int[]{i, j};
             }
         }
     }
     return new int[]{-1, -1};   
    }
}

思路二、看target和当前nums[i]差值是否在hashMap中存在，存在则说明找到结果，如果不存在则将该nums[i]放入hashmap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
            int temp = target - nums[i];
            if (hashMap.containsKey(temp)) {
                return new int[]{i, hashMap.get(temp)};
            }
            hashMap.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}