2024-03-11 代码随想录

代码随想录算法训练营day6 | 题目242、题目349、题目202、题目1

题目一描述

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:
输入: s = "rat", t = "car"
输出: false

提示:
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

解题思路

方法一：两个字符串打乱后排序，然后对比这两个数组是否相等即可。
方法二：所有的字母及其出现次数存入一个哈希表，再遍历第二遍取出，最后算一下map的values是否都为0
方法三：由于只有小写字母，可以按照字母存入长度为26的一位数组里。

代码实现

方法一：

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] sca = s.toCharArray();
        char[] tca = t.toCharArray();
        Arrays.sort(sca); // 注意这个操作返回的是空值
        Arrays.sort(tca);

      //  return String.valueOf(sca).equals(String.valueOf(tca));
        return Arrays.equals(sca, tca);
    }
}

方法二：

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) { // 带括号
            return false;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (char ss : s.toCharArray()) {
            if (map.containsKey(ss)) {
                map.put(ss, map.get(ss) + 1);
            } else {
                map.put(ss, 1); // 初始化次数数字是1
            }
        }
        for (char tt : t.toCharArray()) {
            if (map.containsKey(tt)) {
                map.put(tt, map.get(tt) - 1);
                if (map.get(tt) < 0) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
}

方法三：

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) { // 带括号
            return false;
        }
        int[] map = new int[26];
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i) - 'a']++;
            map[t.charAt(i) - 'a']--;
        }
        for (int i : map) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }
}

技巧总结

s.toCharArray()字符串转数组
Arrays.sort()返回的是空值，而且只能传入数组。
Arrays.equals()可以直接比较数组。

字符串长度要加括号：s.length()
map[s.charAt(i) - 'a']++; 使用这个技巧来存储英文字母

题目二描述

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

解题思路

本质就是在找两个数组中都存在的那些数，返回一个去重的结果。
可以用set来辅助去重并且快速查找，即方法一。
也可以排序后使用双指针，两个指针分别指向每个数组的开头，向后找到相同的元素并去重操作。

代码实现

方法一：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> ress = new HashSet<>();

        for(int n1: nums1){
            set1.add(n1);
        }
        for(int n2: nums2){
            if(set1.contains(n2)){
                ress.add(n2);
            }
        }
        // 把Set转为数组，只能先创建数组然后遍历放入
        int[] res = new int[ress.size()];
        int index = 0;
        for (int num : ress) {
            res[index++] = num;
        }

        return res;
    }
}

方法二：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int index1 = 0;
        int index2 = 0;
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int[] res = new int[nums1.length];
        int index = 0;
        while (index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] == nums2[index2]) {
                res[index] = nums1[index1];
                if (index > 0 && res[index - 1] == res[index]) {
                    index--;
                }
                index++;
                index1++;
                index2++;
            } else {
                if (nums1[index1] > nums2[index2]) {
                    index2++;
                } else {
                    index1++;
                }
            }
        }
        return Arrays.copyOf(res, index);
    }
}

技巧总结

学会set转数组的方式。
学会Arrays.copyOf()来得到一个数组的前几项。

题目2.1描述

350. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

解题思路

无需去重的类似题，双指针更好用

代码实现

方法一：

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map1 = new HashMap<>();
        Map<Integer, Integer> map2 = new HashMap<>();
        int[] res = new int[nums1.length];

        for (int n1 : nums1) {
            map1.put(n1, map1.getOrDefault(n1, 0) + 1);
        }
        for (int n2 : nums2) {
            map2.put(n2, map2.getOrDefault(n2, 0) + 1);
        }
        int index = 0;
        for (int n1 : map1.keySet()) {
            if (map2.containsKey(n1)) {
                int n = Math.min(map1.get(n1), map2.get(n1));
                for (int i = 0; i < n; i++) {
                    res[index++] = n1;
                }
            }
        }
        return Arrays.copyOf(res, index);
    }
}

技巧总结

使用map.put(key, map.getOrDefault(key, 0) + 1);来为map的key赋值加一

题目三描述

202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：
输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
示例 2：
输入：n = 2
输出：false

提示：
1 <= n <= 231 ^ -1

解题思路

如果sum出现重复，就说明一定不是快乐数，所以用Set存储所有出现过的sum。
难点在于对数字的得到每一位的操作，只有两种方法，记住第一种方法。

代码实现

方法一：

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();

        while (true) {
            int sum = getSum(n);
            if (sum == 1) {
                return true;
            }
            if (set.contains(sum)) {
                return false;
            }
            set.add(sum);
            n = sum;
        }
    }

    public int getSum(int n) {
        int sum = 0;
        while (n > 0) {
            int lower = n % 10;
            sum += lower * lower;
            n = n / 10;
        }
        return sum;
    }
}

方法二（getSum的另一种写法）：

class Solution {
    public int getSum(int n) {
        int sum = 0;
        String number = String.valueOf(n);
        for (char c : number.toCharArray()) {
            sum += Character.getNumericValue(c) * Character.getNumericValue(c);
        }
        return sum;
    }
}

技巧总结

记住如何对数字的每一位进行遍历

题目四描述

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

解题思路

注意不能先把所有数全部放入map中，不然会有查找到自身而重复的情况。

代码实现

方法一：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        // for(int i = 0; i< nums.length; i++){
        //     map.put(nums[i], i);
        // }
        for(int i = 0; i<nums.length; i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{i, map.get(target - nums[i])};
            }else{
                map.put(nums[i], i);
            }
        }
        return new int[2];
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。