「日更刷题」第一周,链表和哈希表(二)

简介: 「日更刷题」第一周,链表和哈希表

383.赎金信

题目描述

网络异常,图片无法展示
|

解题思路

  • 遍历出所有的值
  • 找出重复的值
  • 很明显使用set去做
  • 第一个set存 num1的值
  • 遍历 num2的时候判断这个值在 set1中是否存在,若存在则表示重复
  • 最后使用 stream的方式提取出 int数组

代码展示

public static int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set1 = new HashSet<>();
    Set<Integer> set2 = new HashSet<>();
    for (int i : nums1) {
        set1.add(i);
    }
    for (int i : nums2) {
        if (set1.contains(i)) {
            set2.add(i);
        }
    }
    int[] ints = set2.stream().mapToInt(s -> s).toArray();
    return ints;
}
复制代码

提交结果

网络异常,图片无法展示
|

2022/8/31

350. 两个数组的交集 II

题目描述

网络异常,图片无法展示
|

解题思路

  • 两个数组的交集,就是找出这两个数组中相同的元素
  • 先将两个数组进行排序操作
  • 创建 int x,使用三元运算获取到两个数组的最小长度
  • 两个数组最大的交集长度 == x
  • 创建数组 result,长度为 x,用来接收两个数组的交集
  • 遍历两个数组
  • 因为之前我们给两个数组进行过排序了,所以直接判断然后下标 ++就可以了
  • 具体实现和双指针一样

代码展示

public static int[] intersect(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int i = 0,j = 0, z = 0;
    int x = nums1.length < nums2.length ? nums1.length: nums2.length;
    int[] result = new int[x];
    while(j < nums2.length && i < nums1.length){
        if (nums1[i] == nums2[j]){
            result[z] = nums1[i];
            i++;
            j++;
            z++;
        } else if (nums1[i] < nums2[j]) {
            i++;
        }else{
            j++;
        }
    }
    int[] ints = Arrays.copyOf(result, z);
    return ints;
}
复制代码

提交结果

网络异常,图片无法展示
|

202 快乐数

题目描述

网络异常,图片无法展示
|

解题思路

  • 读题可知,就是一个数字的各个位的平方相加
  • 题中有说,可能会陷入死循环,结果永远不唯一
  • 所以我们要采用 Set对每次获取到的结果进行判断是不是出现过
  • 出现过代表陷入了死循环中

代码展示

public static boolean isHappy(int n) {
    Set<Integer> set = new HashSet<>();
    while(n != 1 && !set.contains(n)){
        set.add(n);
        n = test(n);
    }
    return n == 1;
}
private static Integer test(int n){
    int result = 0;
    while(n > 0){
        int temp = n % 10;
        result += temp * temp;
        n = n / 10;
    }
    return result;
}
复制代码

提交结果

网络异常,图片无法展示
|

1. 两数之和 (之前做过, 不算)

题目描述

网络异常,图片无法展示
|

解题思路

  • 这道题我就通过了一种很简单的做法
  • 遍历当前值
  • 目标值减去 当前值 == 需要值
  • 如果需要值在 map中则直接返回
  • 若不在则存储到 map中

代码展示

public static  int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int temp = target - nums[i];
        if (map.containsKey(temp)) {
            return new int[]{i, map.get(temp)};
        }else{
            map.put(nums[i], i);
        }
    }
    return null;
}
复制代码

提交结果

网络异常,图片无法展示
|

454. 四数相加 II

题目描述

网络异常,图片无法展示
|

解题思路

  • 和上面两数之和一样的
  • 两两个数组遍历相加存到map
  • 获取需要值然后去map中取
  • 和上一题不一样的是,这次是找到个数

代码展示

public static int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    Map<Integer, Integer> map = new HashMap<>();
    int num = 0;
    for (int i = 0; i < nums1.length; i++) {
        for (int j = 0; j < nums2.length; j++) {
            num = nums1[i] + nums2[j];
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
    }
    int result = 0;
    for (int i = 0; i < nums3.length; i++) {
        for (int j = 0; j < nums4.length; j++) {
            num = 0 - (nums3[i] + nums4[j]);
            int count = map.getOrDefault(num, 0);
            result += count;
        }
    }
    return result;
}
复制代码

提交结果

网络异常,图片无法展示
|

2022/9/1

15. 三数之和

题目描述

网络异常,图片无法展示
|

解题思路

  • 因为题中只要求返回 0且不重复的数组,而没有要求顺序
  • 所以我们可以使用双指针来做这道题
  • 先对数组进行排序
  • 设置三个指针
  • 指针 i从 0开始,从左向右前进
  • 指针 left从 1开始,从左向右前进
  • 指针 right从 lenght-1 开始,从右向左前进
  • 题中要求不重复数组,那么采用三指针的情况肯定就不会有重复的数值了,因为我们的数组是排序过的
  • 因为 left肯定比 i大,且是从左向右前进,right是从右向左前进,那么循环终止条件为 left >= right
  • 计算当前三指针元素之和是否等于目标值 target
  • 小了就 left++
  • 大了就 right--
  • 注意,这里需要判断当前 i下标元素是否和 i-1下标元素相同,相同则跳出循环,因为要求数组是不重复的

代码展示

public static List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            return result;
        }
        if (i > 0 && nums[i] == nums[i - 1]){
            continue;
        }
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right){
            int sum = nums[i] + nums[left] + nums[right];
            if (sum < 0){
                left++;
            }else if (sum > 0){
                right--;
            }else{
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while(right > left && nums[right] == nums[right - 1]) right--;
                while(right > left && nums[left] == nums[left + 1]) left++;
                right--;
                left++;
            }
        }
    }
    return result;
}
复制代码

提交结果

网络异常,图片无法展示
|

18. 四数之和

题目描述

网络异常,图片无法展示
|

解题思路

这道题和三数之和的思路是一样的,区别就是多加了一层循环,这层循环是从 lenght-1开始的

建议大家看懂了上一题三数之和之后自己尝试着做一下

代码展示

public static List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > target && (nums[i] > 0 || target > 0)){
            return list;
        }
        if (i > 0 && nums[i] == nums[i - 1]){
            continue;
        }
        for (int j = nums.length - 1; j > i; j--) {
            if (j < nums.length - 1 && nums[j] == nums[j + 1]){
                continue;
            }
            int left = i + 1;
            int right = j - 1;
            while (left < right){
                long num = (long) nums[i] + nums[left] + nums[right] + nums[j];
                if (num < target){
                    left++;
                }else if (num > target){
                    right--;
                }else{
                    list.add(Arrays.asList(nums[i],nums[left],nums[right],nums[j]));
                    while(left < right && nums[right] == nums[right - 1]) right--;
                    while(left < right && nums[left] == nums[left + 1]) left++;
                    left++;
                    right--;
                }
            }
        }
    }
    return list;
}
复制代码

提交结果

网络异常,图片无法展示
|

本题小结

  • 注意 nums[i] 的范围, 需要用 long接收

344. 反转字符串

题目描述

网络异常,图片无法展示
|

解题思路

直接暴力破解。。

代码展示

public static void reverseString(char[] s) {
    for (int i = 0; i < s.length / 2; i++) {
        char temp = s[i];
        s[i] = s[s.length - 1 - i];
        s[s.length - 1 - i] = temp;
    }
}
复制代码

提交结果

网络异常,图片无法展示
|

题目小结

该题于去年做过,不算今日完成

541. 反转字符串 II

题目描述

网络异常,图片无法展示
|

解题思路

  • 这道题的我感觉比上道题烦很多
  • 做字符串相关的题我比较喜欢将其转为 char数组做,大家可以根据自己的喜好来
  • 初始化每次反转的字符长度以及下标 left和 right
  • 循环遍历来反转字符串
  • 循环中止条件是 right >= s.lenght
  • 求出每次反转的最后一个字符的下标, stop
  • 循环反转字符串
  • 反转完毕之后 left=right 同时 right+= 2*k
  • 题中根据剩余字符的不同来做了不同的操作
  • 我们判断出最后一次循环的终止位置 right
  • 循环反转字符串

代码展示

public static String reverseStr(String s, int k) {
    char[] chars = s.toCharArray();
    int left = 0;
    int right = left + 2 * k;
    while (right < s.length()){
        int stop = left + k - 1;
        while(left < stop){
            char temp = chars[left];
            chars[left] = chars[stop];
            chars[stop] = temp;
            left++;
            stop--;
        }
        left = right;
        right += 2 * k;
    }
    right = s.length() - left < k ? s.length() - 1 : left + k -1 ;
    while (left < right){
        char temp = chars[left];
        chars[left] = chars[right];
        chars[right] = temp;
        left++;
        right--;
    }
    return String.valueOf(chars);
}
复制代码

提交结果

网络异常,图片无法展示
|

题目小结

  • 一定一定要计算好边界,不然很容易出错

2022/9/2

剑指 Offer 05. 替换空格

题目描述

网络异常,图片无法展示
|

解题思路

  • 依旧是字符串转为 char数组
  • 因为是把空格转为 %20,所以我们新的字符串长度有所变化
  • 遍历字符串求出新数组长度
  • 创建新数组
  • 倒序遍历字符串
  • 如果当前 i == lenght 那么说明剩余的字符串内没有空格,直接返回就可以了
  • 如果当前字符为空格,则在数组中倒序加入 02%

代码展示

public static String replaceSpace(String s) {
    char[] chars = s.toCharArray();
    int length = s.length();
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] == ' '){
            length += 2;
        }
    }
    char[] ints = new char[length];
    for (int i = chars.length - 1; i >= 0; i--) {
        if (i == length){
            return String.valueOf(ints);
        }
        if (chars[i] == ' '){
            ints[--length] = '0';
            ints[--length] = '2';
            ints[--length] = '%';
        }else{
            ints[--length] = chars[i];
        }
        System.out.println(Arrays.toString(ints));
    }
    return String.valueOf(ints);
}
复制代码

提交结果

网络异常,图片无法展示
|

151. 反转字符串中的单词

题目描述

网络异常,图片无法展示
|

解题思路

  • 和上一题一样的
  • 创建List
  • 转为char数组
  • 遍历字符串
  • 新建StringBuilder对象 str
  • 如果有空格且 str不为空则把 str加入到 list中
  • 最后倒序遍历相加到一起

代码展示

public static String reverseWords(String s) {
    List<String> list = new ArrayList<>();
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        StringBuilder str = new StringBuilder();
        while(i < chars.length && chars[i] != ' '){
            str.append(chars[i]);
            i++;
        }
        if (str != null){
            list.add(str.toString());
        }
    }
    StringBuilder str = new StringBuilder();
    for (int i = list.size() - 1; i >= 0; i--) {
        str.append(list.get(i));
        str.append(" ");
    }
    str.deleteCharAt(str.length() - 1);
    return str.toString();
}
复制代码

提交结果##

网络异常,图片无法展示
|

小题总结

  • 两次判断当前char是否为 ‘ ’, 一次在循环开始,一次在获取单词
目录
相关文章
|
2月前
|
存储 缓存
【每日一题Day336】LC146最近最少使用缓存 | 哈希表+链表
【每日一题Day336】LC146最近最少使用缓存 | 哈希表+链表
22 0
|
2月前
|
索引
【每日一题Day281】LC142链表 Ⅱ| 快慢指针 哈希表
【每日一题Day281】LC142链表 Ⅱ| 快慢指针 哈希表
10 0
|
2月前
|
存储 索引
【每日一题Day280】LC141环形链表 | 快慢指针 哈希表
【每日一题Day280】LC141环形链表 | 快慢指针 哈希表
14 0
|
2月前
【每日一题Day234】LC1171从链表中删去总和值为零的连续节点 | 链表模拟 哈希表+前缀和
【每日一题Day234】LC1171从链表中删去总和值为零的连续节点 | 链表模拟 哈希表+前缀和
14 0
|
3月前
|
存储 算法 Python
python算法(二)—栈、队列、链表、哈希
python算法(二)—栈、队列、链表、哈希
41 0
|
7月前
|
机器学习/深度学习 存储 Cloud Native
817. 链表组件:哈希表+flag
这是 力扣上的 817. 链表组件,难度为 中等。
|
9月前
LeetCode剑指 Offer 35—复杂链表的复制(哈希表/递归)
LeetCode剑指 Offer 35—复杂链表的复制(哈希表/递归)
复杂链表的复制(剑指offer35 力扣138)java哈希表/原地拼接
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
|
索引
力扣142 - 环形链表||【二重双指针+哈希表】
灵活运用双指针,带您一探环形链表的奥秘
72 0
力扣142 - 环形链表||【二重双指针+哈希表】
|
存储 算法 Java
「日更刷题」第一周,链表和哈希表(三)
「日更刷题」第一周,链表和哈希表
49 0