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

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

一、前言

由于单纯地算法题是真的不给推荐, 也有可能是太简单了。。

所以接下来采取多天发一次的方式,记录一下算法小白的历练之路

注:刷题语言均为java,每天保证做三道以前没有做过的题目,刷遍LeetCode从今天开始

2022/8/29

从今天第二道题开始就是哈希表相关的题了

142. 环形链表 II

题目描述

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例

示例1

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

输入: head = [3,2,0,-4], pos = 1
输出: 返回索引为 1 的链表节点
解释: 链表中有一个环,其尾部连接到第二个节点。
复制代码

示例2

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

输入: head = [1,2], pos = 0
输出: 返回索引为 0 的链表节点
解释: 链表中有一个环,其尾部连接到第一个节点。
复制代码

示例3

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

输入: head = [1], pos = -1
输出: 返回 null
解释: 链表中没有环。
复制代码

提示

  • 链表中节点的数目范围在范围 [0, 104]
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

解题思路

  • 首先,我们要去判断当前链表 head是不是环形链表
  • 新建两个链表 nodeA和 nodeB,去接收原链表 head
  • 循环遍历,nodeA每次前进一步,nodeB每次前进两步
  • 当链表相遇时,证明链表 head是环形链表
  • 如果不是环形链表,则直接返回 null
  • 如果是环形链表,那么 nodeA肯定会与 nodeB相遇
  • 因为 nodeA每次前进一步,nodeB每次前进两步,所以 nodeA绕环形链表部分走一圈时,nodeB会绕环形链表走两圈,这期间不论环形链表部分是单数链表还是双数链表,肯定会相遇最少一次
  • 现在我们确定了链表 head是环形链表之后,该去判断环形链表部分的初始节点位置,下面简称为入环点
  • 假设链表 head的头结点到入环点的距离为 x,入环点到相遇点为 y,相遇点到入环点为 z
  • 那么 nodeA走到相遇点的距离为 x + y
  • nodeB走到相遇点的距离为 n(y + z) + x + y
  • 又因为 nodeA走一步,nodeB走两步,所以: (x + y)* 2 = n(y + z) + x + y
  • 解得: x = n(y + z) -y
  • 整理可得: x = (n - 1)(y + z) + z
  • 因为 nodeA跑一步 nodeB跑两步,所以 n是肯定大于 1的
  • 又因为环形链表部分的长度等于 y + z
  • 所以 x = z + nodeA绕环形链表圈数
  • 那么我们现在要做的,就是让 nodeA跑 x距离,让 nodeB跑 (z + n圈)
  • 所以我们让 nodeA = head,让 nodeA从头开始跑
  • nodeB不变,因为当前 nodeB距离入环点就是 z的距离
  • 同时让 nodeA和 nodeB每次循环前进一位,保证两个节点肯定会在入环点相遇
  • 具体代码如下所示

代码展示

public static ListNode detectCycle(ListNode head) {
    // 搞两个链表,接收 head
    // A是慢链表,B是快链表
    ListNode nodeA = head;
    ListNode nodeB = head;
    // 判断该链表是否为环形链表
    boolean flag = false;
    while(nodeB != null && nodeB.next != null){
        nodeA = nodeA.next;
        nodeB = nodeB.next.next;
        if (nodeA == nodeB){
            flag = true;
            break;
        }
    }
    // 如果为环形链表,判断入口位置
    if (flag){
        nodeA = head;
        while(nodeA != nodeB){
            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }
        return nodeA;
    }
    return null;
}
复制代码

提交结果

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

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
  • st 仅包含小写字母

解题思路

  • 将字符串转化为 char数组,数组长度为 26
  • 根据 ASCII可以计算出字幕在数组中的下标
  • 遍历字符串s,在数组相应的位置上进行 +1操作
  • 遍历字符串t,在数组相应的位置上进行 -1操作
  • 最后遍历我们的 char数组
  • 如果数组中有元素不为 0,则字符串s 和字符串t 不是字母异位词

代码展示

public static boolean isAnagram(String s, String t) {
    int[] array = new int[26];
    char[] charsS = s.toCharArray();
    char[] charsT = t.toCharArray();
    for (int i = 0; i < charsS.length; i++) {
        array[charsS[i] - 'a'] ++;
    }
    for (int i = 0; i < charsT.length; i++) {
        array[charsT[i] - 'a'] --;
    }
    for (int i = 0; i < array.length; i++) {
        if (array[i] != 0){
            return false;
        }
    }
    return true;
}
复制代码

提交结果

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

383.赎金信

题目描述

给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以,返回 true ;否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例

示例1

输入: ransomNote = "a", magazine = "b"
输出: false
复制代码

示例2

输入: ransomNote = "aa", magazine = "ab"
输出: false
复制代码

示例3

输入: ransomNote = "aa", magazine = "aab"
输出: true
复制代码

提示

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNotemagazine 由小写英文字母组成

解题思路

  • 本题是上一题的相关类型题,解题思路也差不多
  • 字符串 ransomNote的长度是永远小于等于字符串 magazine的
  • 所以还是创建一个长度为 26的数组
  • 遍历 ransomNote每个元素减去 ‘a’的 ASCII码, 获取到数组的下标进行 ++ 操作
  • 遍历 magazine每个元素减去 ‘a’的 ASCII码, 获取到数组的下标进行 -- 操作
  • 遍历数组,看是否有元素是大于0的,有则false

代码展示

public static boolean canConstruct(String ransomNote, String magazine) {
    int[] array = new int[26];
    for (char c : ransomNote.toCharArray()) {
        array[c - 'a']++;
    }
    for (char c : magazine.toCharArray()) {
        array[c - 'a']--;
    }
    for (int i : array) {
        if (i > 0){
            return false;
        }
    }
    return true;
}
复制代码

提交结果

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

2022/8/30

49. 字母异位词分组

题目描述

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。

示例

示例1

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
复制代码

示例2

输入: strs = [""]
输出: [[""]]
复制代码

示例3

输入: strs = ["a"]
输出: [["a"]]
复制代码

提示

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母

解题思路

  • 设置int[26]数组,存放 a-z的个数
  • 使用 ASCII 字母 - ‘a’ 获取到对应的数组下标
  • 字符串 p永远比字符串 s短
  • 所以获取字符串 p对应的字母下标数组
  • 遍历字符串 s,长度为 p的长度
  • 这里注意终止条件为 s.lenght - p.lenght + 1
  • 判断当前长度的字符串与 p是否为异步词
  • 如果是异步词则加入返回 list中

注意:判断两个数组是否相等可以使用 Arrays.equlas(int[] int1, int[] int2) 遍历字符串s 时的中止条件应该是 s.lenght - p.lenght + 1

代码展示

public static List<Integer> findAnagrams(String s, String p) {
    List<Integer> list = new ArrayList<>();
    // 求出 p的长度
    int lengthP = p.length();
    // 字符串 s转换成 char数组
    char[] chars = s.toCharArray();
    // 获取 p的哈希表
    int[] array = new int[26];
    for (char c : p.toCharArray()) {
        array[c -'a'] ++;
    }
    // 循环遍历
    for (int i = 0; i < chars.length - lengthP + 1; i++) {
        int[] array1 = new int[26];
        for (int j = 0; j < lengthP ; j++) {
            array1[chars[i + j] - 'a']++;
        }
        // 判断当前长度的字符串是否和p是异步词
        if (Arrays.equals(array, array1)){
            list.add(i);
        }
    }
    return list;
}
复制代码

提交结果

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

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

题目描述

给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

示例

示例1

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
复制代码

示例2

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
复制代码

提示

  • 1 <= s.length, p.length <= 3 * 104
  • sp 仅包含小写字母

解题思路

  • 这个代码改的难受的一批,可以简写很多,感兴趣的自己敲一下
  • 先定义了返回的集合
  • 使用map去判断是不是字母异味词
  • 开始遍历
  • 使用老办法 array数组存储单词字母的个数
  • 加入map, 这里注意,array.toString记录的是数组的内存地址,而不是值,所以map的 key不能直接记录
  • String.valueOf方法去记录还是获取的元素的 toString方法,所以这里需要用 Arrays.toString获取真正的数组元素信息
  • 剩下的就是map判断,然后遍历出map里的 value信息了

注意:数组的toString方法返回值是内存地址 效率很低,一个是因为自己代码的问题,例如最后的遍历map可以使用 stream 流来做 还有一部分原因是,我看大佬们的解题是在获取到单词的字母的时候,也是做了一个str.toCharArray()操作,但是在这里是使用了 排序,保持字母顺序的一个固定key, 存到map中了

代码展示

public static List<List<String>> groupAnagrams(String[] strs) {
    // 定义返回值
    List<List<String>> result = new ArrayList<>();
    // 存储相同字母的单词
    Map<String, List<String>> map = new HashMap<>();
    // 遍历 strs
    int[] array = new int[26];
    String s, t;
    for (String str : strs) {
        for (char c : str.toCharArray()) {
            array[c - 'a']++;
        }
        List<String> strings;
        s = String.valueOf(Arrays.toString(array));
        if (map.containsKey(s)) {
            strings = map.get(s);
        }else{
            strings = new ArrayList<>();
        }
        strings.add(str);
        map.put(s, strings);
        array = new int[26];
    }
    for (Map.Entry<String, List<String>> listEntry : map.entrySet()) {
        result.add(listEntry.getValue());
    }
    return result;
}
复制代码

提交结果

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

目录
相关文章
|
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