刷Leecode笔记（三）哈希表篇

哈希表篇

字母异味，数组交集，数字，字符串

哈希表

字母异位

242.有效的字母异位

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            map.put(c, map.getOrDefault(c, 0) - 1);
            if (map.get(c) == 0) {
                map.remove(c);
            }
            // if (map.get(c) < 0) return false;

        }
        return map.size() == 0 ? true : false;
        // return true;
    }
}
//HashMap，put,remove,如果get(元素)<0,返回false

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }
}
/*字符串转数组再排序，判断是否相等
注意：要使用Arrays.equals(str1, str2)，而不是str1.equals(str2)
Arrays.equals(str1, str2) 是用于判断两个数组是否相等的正确表达式。str1.equals(str2) 用于比较字符串对象的内容是否相等，而不是数组，即是这里比较的是地址值，肯定不相等。
正确的数组比较应该使用 Arrays.equals 方法，该方法会逐个比较数组中的元素，确保数组内容相同。

383.赎金信

s字符串是否能由t构成，s中字符只能在t中使用1次

class Solution {
    public boolean canConstruct(String s, String t) {
        int lens = s.length();
        int lent = t.length();
        if (lens > lent) {
            return false;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < lent; i++) {
            char c = t.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for (int i = 0; i < lens; i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) - 1);
            if (map.get(c) < 0) {
                return false;
            }
        }
        return true;
    }
}
//正常HashMap的put插入覆盖更新，如果表内的value<0.说明s中的新字符或者超过1次的限制

49.字母异位词分组

//排序后将String作为key，list<String>作为value，寻找相同的string添加list<String>即可
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] array = s.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> value = map.getOrDefault(key, new ArrayList<String>());
            value.add(s);
            map.put(key, value);
        }
        return new ArrayList<>(map.values());
    }
}
/* 集合的集大成之作，key，value是集合，ArrayList + HashMap，差点绕晕过去了

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

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        int lens = s.length();
        int lenp = p.length();
        if (lens < lenp) {
            return list;
        }
        char[] arr = p.toCharArray();
        Arrays.sort(arr);
        p = new String(arr);
        for (int i = 0; i <= lens - lenp; i++) {
            String str = s.substring(i, i + lenp);
            if (isAnagram(str, p) == true) {
                list.add(i);
            }
        }
        return list;
    }

    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        // Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }
 
}
//核心判断是字符串排序后比较值是否相等来判断异位词
//遍历，查找长度一样的字串，substring()提取字串的方法s是小写，没啥说的

数组交集

349.两个数组的交集

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1.length == 0 || nums2.length == 0){
            return new int[0];
        }
        HashSet<Integer> set1 = new HashSet<>();
        HashSet<Integer> set2 = new HashSet<>();
        for(int i : nums1){
            set1.add(i);
        }
        for(int i : nums2){
            if(set1.contains(i)){
                set2.add(i);
            }
        }
        int [] ans = new int[set2.size()];
        int j = 0;
        for(int i : set2){
            ans[j++] = i;
        }
        return ans;
    }
}
// 思路是，使用set集合存入nums1，再遍历nums2，判断set中是否包含
// 最后将set转为数组
// 要定义两个set，因为包含的也会重复

350.两个数组的交集II

/*与I不同点在于，I的交集是用set记录去重的，直接用set记录交集就好
II要交集出现的次数，与出现的最小次数一致，正常用map记录nums1的词和次数，再扫描nums2，判断存在就次数--，加入到list中去，直到次数为0，为止，记录list，再转为数组
*/
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i : nums1) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        for (int i : nums2) {
            if (map.containsKey(i) && map.get(i) > 0) {
                list.add(i);
                map.put(i, map.get(i) - 1);
            }
        }
        int[] ans = new int[list.size()];
        int j = 0;
        for (int i : list) {
            ans[j++] = i;
        }
        return ans;
    }
}
/*
 * list和数组的转换，不能直接int[] ans = list.toArray()
 * 因为，不能把Object集合强转为int类型的，像我那样一个一个遍历又太麻烦了
 list.toArray()只能转换为，没啥用额包装类的类型Object[]，还要转换
 * 正确的写法是
 * Integer[] ans = list.toArray(new Integer[list.size()])
 * 不如一个一个遍历算啦
 */

数字

202.快乐数

/*
 * 思路，用set记录和值n的值，不断调用方法，求解下一个n,来判断n是否出现在set集合内，若出现，则判断false
 * 若sum==1，判定为快乐数字
 */
class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        while (n != 1 && !set.contains(n)) {
            set.add(n);
            n = nextNumber(n);
        }
        return n == 1;
    }

    public int nextNumber(int n) {
        int sum = 0;
        while (n != 0) {
            sum += Math.pow(n % 10, 2);
            n /= 10;
        }
        return sum;
    }
}

1.两数之和

//没啥说的，记个时，五分钟内写出来
//用map记录数组元素，以及数组的下标，从i遍历数组，判断map是否存在target-i的值，返回即可
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[] { i, map.get(target - nums[i]) };
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

454.四数相加

/*
 * 思路：正常四层循环，count++肯定超时,考虑空间换时间
 * 考虑将四层循环减为两层
 * 定义一个map，用于存放两数的和sum，以及和出现的次数
 * 寻找，在3,4表中两层for，寻找-sum出现的次数
 */
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i : nums1) {
            for (int j : nums2) {
                map.put(i + j, map.getOrDefault(i + j, 0) + 1);
            }
        }
        int count = 0;
        for (int i : nums3) {
            for (int j : nums4) {
                count += map.getOrDefault(-i - j, 0);
                // if (map.containsKey(-i - j)) {
                // count += map.get(-i - j);
                // 获取默认值＋0，效率高于查找key再获取值
                // }
            }
        }
        return count;
    }
}

383.赎金信

//判断第一个字符串能不能由第二个字符串组成
//思路：map存储第一个字符串以及出现的次数，遍历第二个字符串，将map对应的值-1，再判断当前元素对应的value值，如果<0，即为false
//已经做过了，就写个思路吧

15.三数之和

//思路：两层for循环确定i,j的值。再判断hashmap中是否存在(-i-j)的值,存在放入list<Integer>集合中，
//题目说不能重复的三元组，所以对list集合要去重，可以再定义一个set集合去重，试试
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        // 这样定义ArrayList的每一个对象都是List<Integer>类型的
        if (nums == null || n < 3) {
            return ans;
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        Arrays.sort(nums);
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
                // 当前i与前一个重复的时候，直接跳过
            }
            for (int j = i + 1; j < n - 1; j++) {
                int target = -nums[i] - nums[j];
                if (map.containsKey(target)) {
                    if (target == nums[i] || target == nums[j]) {
                        if (map.get(target) < 2) {
                            continue;
                            // 只有一个重复的话
                            // map中的个数要>=2才能确保不是自己
                            // 所以<2的时候，直接跳出循环
                        }
                    }
                    if (target == nums[i] && target == nums[j]) {
                        if (map.get(target) < 3) {
                            continue;
                            // 同理针对都是0的情况，个数要大于3次
                            // 小于3次直接跳出循环
                        }
                    }
                    List<Integer> list = new ArrayList<>();
                    list = Arrays.asList(nums[i], nums[j], target);
                    Collections.sort(list);// 排序后加到集合中，方便set去重
                    ans.add(list);
                }
            }
        }
        // 将ArrayList集合转为set集合，直接定义将结果扔进去就行
        Set<List<Integer>> set = new HashSet<>(ans);
        // 再转为AerrayList集合
        return new ArrayList<>(set);
    }
}
//思路好理解，去重浪费太多时间了
//我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的！
//所以这里是有两个重复的维度
//熟悉定理复杂list集合，以及ArrayList和Set集合之间的转换

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.length; i++) {
            // 排序之后如果第一个元素已经大于零，
            // 那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }
            if (i > 0 && nums[i] == nums[i - 1]) { // 去重a
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    while (right > left && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}
//双指针的去重逻辑比map简单多了，不用考虑那么多情况，也不用map，set，ArrayList一起用又排序，又去重，还有两个重复的维度，太慢了，再也不头铁了

18.四数之和

/*思路：使用双指针法的话，要O^3，
使用map记录两种和出现的次数，查找另外两个，O^2
先试试map吧，都试试。完全没思路了，去重因为是数组
*/
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length < 4) {
            return ans;
        }
        Arrays.sort(nums);
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        List<Integer> list = new ArrayList<>();
                        list = Arrays.asList(nums[i], nums[j], nums[left], nums[right]);
                        // Collections.sort(list);
                        ans.add(list);
                        while (right > left && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        while (right > left && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        right--;
                        left++;
                    }
                }
            }
        }
        // Set<List<Integer>> set = new HashSet<>(ans);
        // return new ArrayList<>(set);
        return ans;
    }
}

字符串

344.反转字符串

class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        int i = 0, j = n - 1;
        while (i < j) {
            char t = s[i];
            s[i] = s[j];
            s[j] = t;
            i++;
            j--;
        }
    }
}
//没啥说的，或者调用StringBuilder，调用里面的reverse方法

541.反转字符串II

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        int i = 0;
        char[] arr = s.toCharArray();
        while (i < n) {
            int r = Math.min(i + k - 1, n - 1);
            arr = subReverse(arr, i, r);
            i = i + 2 * k;
        }
        return new String(arr);
    }

    public char[] subReverse(char[] arr, int i, int j) {
        while (i < j) {
            char t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
            i++;
            j--;
        }
        return arr;
    }
}
//就是判断尾指针的长度，是不能超过数组的长度
//还有就是。是，charAt()只能取值，不能赋值给另一个charAt，涉及到数组字符串交换的，要转为数组处理

替换数字

将字符串中的数字替换为字符

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                sb.append("number");
            } else {
                sb.append(s.charAt(i));
            }
        }
        System.out.println(sb);
    }
}
// 不熟悉ACM格式，用StringBuilder秒了，不用扩长度

151.反转字符串中的单词

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        int n = s.length();
        int i = n - 1, j = n - 1;
        StringBuilder ans = new StringBuilder();
        while (i >= 0) {
            while (i >= 0 && s.charAt(i) != ' ') {
                i--;// 搜索首个空格出现的位置
            }
            String sub = s.substring(i + 1, j + 1) + " ";
            ans.append(sub);
            while (i >= 0 && s.charAt(i) == ' ') {
                i--;
            }
            j = i;
        }
        return ans.toString().trim();
    }
}
//想了半天不知道字符串中间的单词空格怎么处理，直接+""到后面再trim()处理，真的妙啊

右旋字符串

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int k = scan.nextInt();
        String s = scan.next();
        char arr[] = s.toCharArray();
        int n = arr.length;
        char[] ans = new char[n];
        int j = 0;
        for (int i = n - k; i < n; i++) {
            ans[j++] = arr[i];
        }
        for (int i = 0; i < n - k; i++) {
            ans[j++] = arr[i];
        }
        System.out.println(ans);
    }
}
//ACM模式，开辟了额外空间
//如果O(1),就先倒序，再倒序字串，就行

28.找出字符串中第一个匹配的下标

class Solution {
    public int strStr(String h, String n) {
        int lenh = h.length();
        int lenn = n.length();
        for (int i = 0; i <= lenh - lenn; i++) {
            int a = i, b = 0;// 分别指向两个字符串的指针
            while (b < lenn && h.charAt(a) == n.charAt(b)) {
                a++;
                b++;
            }
            if (b == lenn) {
                return i;
            }
        }
        return -1;
    }
}
//模拟法。分别指向两个字符串的指针，a是发起点，每循环一次，长的字符串都要有不同的发起点去匹配。y也就是暴力算法，时间复杂度O(m*n)
//KMP算法，

459.重复的字串

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i <= n / 2; i++) {
            if (n % i == 0) {
                String sub = s.substring(0, i);
                StringBuilder sb = new StringBuilder();
                for (int j = 1; j <= n / i; j++) {
                    sb.append(sub);
                }
                if (sb.toString().equals(s)) {
                    return true;
                }
            }
        }
        return false;
    }
}
//暴力模拟，找出字串，重复n次，判断是否与原有的串相等
//KMP算法，太复杂了不想弄了，就暴力吧