优选算法 - 4 （ 链表 哈希表 字符串 9000 字详解 ）

一：链表

1.1 链表常用技巧和操作总结

1.2 两数相加

题目链接：两数相加

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 先用 cur1 指向 l1 的头节点，用 cur2 指向 l2 的头节点 -- 链表的名字代表着链表头部节点的地址
        // 因为要记录节点的信息，比如说 val 和 next ，所以 cur1 和 cur2 都用 ListNode 节点类型
        ListNode cur1 = l1, cur2 = l2;
        // 接着创建一个虚拟节点 newHead，当两个链表相加后延长这个节点，并把值存储在对应的节点中
        ListNode newHead = new ListNode(0);
        // 用 prev 标记一下 newHead  延长后的尾节点
        ListNode prev = newHead;
        // 用 t 临时存储两个节点相加的结果
        int t = 0;
 
        // 当 cur1 或 cur2 不为空并且 t 没有剩余值时就一直循环，t 不为空是为了处理两个数相加进位后剩下的数字
        while(cur1 != null || cur2 != null || t != 0){
            if(cur1 != null){
                t += cur1.val;
                cur1 = cur1.next;
            }

            if(cur2 != null){
                t += cur2.val;
                cur2 = cur2.next;
            }

            // 当 t 累加上两个节点的值后，把 t 的个位放入 newHead 延长的节点中,接着让 prev 继续指向尾节点
            prev.next = new ListNode(t % 10);
            prev = prev.next;

            // 接着让 t 的十位继续加
            t /= 10;
        }

        // 返回结果链表的第一个有效节点，我们要跳过虚拟头节点
        return newHead.next;
    }
}

1.3 两两交换链表中的结点

题目链接：两两交换链表中的结点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // 先处理链表为空和链表元素为一的情况，这种情况链表无需交换
        if(head == null || head.next == null) return head;

        // 接着处理正常的情况,先创建一个虚拟头节点 newHead ，方便交换，不用处理太多的细节
        ListNode newHead = new ListNode(0);
        //接着把 newHead 当作 head 的头节点
        newHead.next = head;

        // 初始化四个指针：
        // `prev` 用于指向当前要交换的节点的前一个节点
        // `cur` 用于指向当前要交换的第一个节点
        // `next` 用于指向当前要交换的第二个节点
        // `nnext` 用于指向当前要交换的第二个节点后一个节点
        ListNode prev = newHead, cur = prev.next, next = cur.next, nnext = next.next;
        while(cur != null && next != null){
            prev.next = next;
            next.next = cur;
            cur.next = nnext;

            //交换完两个数字后更新四个指针，让接下来的节点继续交换
            prev = cur;
            cur = nnext;
            if (cur != null) next = cur.next; // `next` 移到下一对的第二个节点（如果存在）
            if (next != null) nnext = next.next; // `nnext` 移到下一对的第一个节点的后一个节点（如果存在）
        }

        //循环结束后返回 head ，当然，要去掉虚拟节点
        return newHead.next;
    }
}

1.4 重排链表

题目链接：重排链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        // 先处理链表为空和链表只有一个节点以及两个节点的情况，这些情况下，链表不需要重排
        if(head == null  || head.next == null || head.next.next == null) return;

        //接下来就处理正常情况了，首先先找到链表的中间节点，这里用快慢双指针的方法
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        //循环过后 slow 就是 head 的中间节点,接着我们把 head 分为两个部分 [0, slow],[slow.next, n]
        //我们用 head2 存储第二部分的链表,利用头插法对链表逆序
        ListNode head2 = new ListNode(0);
        //用 cur 标记第二部分链表的首元素
        ListNode cur = slow.next;
        // 接着以 slow 为界将链表前后部分分离
        slow.next = null;                 
        while(cur != null){
            // 因为我们头插 cur 时，cur 与原来的 cur.next 会断开，所以我们用 next 先记录一下这个节点，方便进行循环
            ListNode next = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = next;
        }

        // 接着我们就可以开始合并 head 和 head2 了
         // 用 ret 存储合并后的链表，并用 prev 标记 ret 的尾节点,用 cur1 标记 head 的头节点， cur2 标记 head2 的头节点
        ListNode ret = new ListNode(0);
        ListNode cur1 = head, cur2 = head2.next, prev = ret;

        // 因为 head 的长度一定是大于 head2 的，并且我们合并数组时是分别取出一个的，所以我们只需要判断 head 不为空
        while(cur1 != null){
            //先把 head 中的元素添加进 ret 中
            prev.next = cur1;
            prev = prev.next;
            cur1 = cur1.next;

            //因为 head2 的长度小于 head ，所以我们要判断一下 cur2 是否为空
            if(cur2 != null){
                prev.next = cur2;
                prev = prev.next;
                cur2 = cur2.next;
            }
        }
        
         // 链表重排完成，无需返回值，因为操作在原链表上完成
        
    }
}

1.5 合并 K 个升序链表

题目链接：合并 K 个升序链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 创建一个小根堆（优先队列），根据节点值进行排序
        // lambda 表达式：(v1, v2) -> v1.val - v2.val 用于实现按节点值升序排列
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);

        // 接着将所有链表的头结点加入到小根堆中，注意！并不是取的链表所有的节点
        for(ListNode Li : lists)
            if(Li != null) heap.offer(Li);
        
        // 接着创建一个 ret 存储合并后的升序链表，用 prev 指向 ret 的尾节点
        ListNode ret = new ListNode(0);
        ListNode prev = ret;

        // 接着就把小堆里的元素依次放入 ret 中
        while(heap.isEmpty() == false){
            //尾插到 prev 后面，并更新 prev 的指向
            ListNode t = heap.poll();
            prev.next = t;
            prev = t;

            // 如果堆顶节点 t 有下一个节点，将其加入堆
            if (t.next != null) {
                heap.offer(t.next); // 把 t 的下一个节点加入堆中
            }
        }

        // 返回合并后的链表的头节点（去掉虚拟头节点 ret）
        return ret.next;
    }
}

1.6 K 个一组翻转链表

题目链接：K 个一组翻转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 先获取链表需要反转的次数 n 
        int n = 0;
        ListNode cur = head; // 指针初始化为链表头节点
        while(cur != null){
            cur = cur.next;
            n++;
        }
        n /= k; // 此时 n 就存储了数组要反转的次数了

        // 接着创建一个虚拟节点 newHead ，用于存储翻转后的链表
        ListNode newHead = new ListNode(0);
        // 接着用 prev 标记要插入位置的前一个节点
        ListNode prev = newHead;
        cur = head; // 重置一下 cur ，因为前面遍历链表时修改了 cur

        // 先处理 n 次需要翻转 k 个元素的情况
        for(int i = 0; i < n; i++){
            ListNode tmp = cur; // 先用 tmp 临时存储一下第一个插入的节点
            for(int j = 0; j < k; j++){
                ListNode next = cur.next; // 先用 next 存储一下插入节点的下一个节点
                cur.next = prev.next;
                prev.next = cur;
                cur = next;
            }
            // 当一组结束完后要重新更新一下 prev ,让下一轮循环以 prev 为基准进行头插
            prev = tmp;
        }

        // 接着处理一下剩余的元素
        prev.next = cur;

        // 最后返回 newHead ，要跳过虚拟节点
        return newHead.next;
    }
}

二：哈希表

2.1 两数之和

题目链接：两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 键：数组元素的值，值：该元素在数组中的索引
        Map<Integer, Integer> hash = new HashMap<>(); // <nums[i], i>
        
        // 接着开始遍历数组
        for(int i = 0; i < nums.length; i++){
            int x = target - nums[i];
            if(hash.containsKey(x)) return new int[]{i, hash.get(x)};
            else hash.put(nums[i], i);
        }

        // 如果找不到返回 -1 和 -1 
        return new int[]{-1, -1};
    }
}

2.2 判断是否互为字符重排

题目链接：判断是否互为字符重排

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        // 先处理特殊情况，当两个字符串的长度不相同时，一定不是重排字符串2
        if(s1.length() != s2.length()) return false;

        // 接下来处理正常的情况，我们用大小为 26 的数组模拟哈尼表，用于存储 'a' - 'z' 字符
        int[] hash = new int[26];
        // 先遍历第一个字符串 s1 ，遇到一个字符让对应的下标加加
        for(int i = 0; i < s1.length(); i++){
            hash[s1.charAt(i) - 'a']++;
        }
        // 接着处理第二个字符串 s2 ，当遇到相同的字符时，让对应下标减减
        for(int i = 0; i < s2.length(); i++){
            hash[s2.charAt(i) - 'a']--;
            // 此时如果有某一位出现负数了。那么直接返回 false
            if(hash[s2.charAt(i) - 'a'] < 0) return false;
        }

        return true;
    }
}

2.3 存在重复元素

题目链接：存在重复元素

class Solution {
    public boolean containsDuplicate(int[] nums) {
        // 此处我们用 set 存储数组中的元素
        Set<Integer> hash = new HashSet<>();

        // 接着开始遍历数组
        for(int x : nums){
            if(hash.contains(x)) return true;
            else hash.add(x);
        }

        return false;
    }
}

2.4 存在重复元素 II

题目链接：存在重复元素 II

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // 创建一个哈希表，用于记录数组中的每个元素及其对应的索引
        // 键：数组中的元素值，值：该元素的最新索引
        Map<Integer, Integer> hash = new HashMap<>();

        // 接着开始遍历数组
        for(int i = 0; i < nums.length; i++){
            // 先判断一下这个数之前是否存在有相同的元素
            if(hash.containsKey(nums[i])){
                if(i - hash.get(nums[i]) <= k) return true;
            }

            hash.put(nums[i], i);
        }

        return false;
    }
}

2.5 字母异位词分组

题目链接：字母异位词分组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 创建一个哈希表，用于将字母异位词分组
        // 键：经过排序的字符串（字母异位词的特征值）
        // 值：与该特征值对应的所有字母异位词的列表
        Map<String, List<String>> hash = new HashMap<>();

        // 1. 遍历字符串数组，将字母异位词分组
        for (String s : strs) {
            // 将当前字符串转换为字符数组
            char[] tmp = s.toCharArray();
            // 对字符数组进行排序，使异位词具有相同的排序结果
            Arrays.sort(tmp);
            // 将排序后的字符数组转换为字符串，作为分组的键
            String key = new String(tmp);

            // 如果哈希表中不存在该键，初始化一个新的列表作为值
            if (!hash.containsKey(key)) hash.put(key, new ArrayList<>());
            

            // 将当前字符串添加到对应键的列表中
            hash.get(key).add(s);
        }

        // 2. 提取结果
        // 将哈希表中所有的值（分组列表）转换为一个列表返回
        return new ArrayList<>(hash.values());
    }
}

三：字符串

3.1 最长公共前缀

题目链接：最长公共前缀

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 先处理一下特殊的情况,当字符串为 null 以及 strs 中的字符串个数为 0 ，这种情况下我们直接返回空字符串
        if(strs == null || strs.length == 0) return "";

        // 如果不是的话就处理正常的情况，我们以 strs 中的第一个字符串为基准，当前缀的长度大于等于 strs 中第一个字符串的长度时，循环停止
        int index = 0; // 用 index 记录最后第一个字符串的最长公共前缀的索引
        while(true){
            if(index >= strs[0].length()) break;

            char currentChar = strs[0].charAt(index); // 先获取第一个字符串的当前位置的字符
            // 接着开始遍历第二个及以下的字符串
            for(int i = 1; i < strs.length; i++){
                // 同样的，index 的长度也不能超过其他字符串的长度
                if(index >= strs[i].length() || strs[i].charAt(index) != currentChar) return strs[0].substring(0,index);
            }

            // 如果 index 没有超过长度并且字符相同的话，让 index 继续加加，继续比较下一个字符
            index++;
        }

        return strs[0].substring(0, index);
    }
}

3.2 最长回文子串

题目链接：最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        // 用 begin 记录最长回文子串的起始位置，len 记录最长回文子串的长度,n 存储字符串 s 的长度
        int begin = 0, len = 0, n = s.length();
        
        // 接着遍历字符串中的每一个元素
        for(int i = 0; i < n; i++){
            // 先处理奇数的情况
            int left = i, right = i;
            while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){left--; right++;}
            // 扩展结束后看一下要不要更新 begin 和 len
            if(right - left - 1 > len){
                begin = left + 1; // 因为 left 和 right 都越过了回文子串的范围，他们是用完后再加加的
                len  = right - left - 1;
            } 

            // 接着处理偶数的情况2
            left = i; right = i + 1;
            while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){left--; right++;}
            if(right - left - 1 > len){
                begin = left + 1; // 因为 left 和 right 都越过了回文子串的范围，他们是用完后再加加的
                len  = right - left - 1;
            } 
        }

        // 循环结束后根据 len 和 begin 来截取字符串
        return s.substring(begin, begin + len);
    }
}

3.3 二进制求和

题目链接：二进制求和

class Solution {
    public String addBinary(String a, String b) {
        // 因为要频繁的对字符串进行操作，因此我们使用 StringBuffer 来存储结果字符串
        StringBuffer ret = new StringBuffer();
        // 接着用 cur1 指向字符串 a 的末尾， cur2 指向字符串 b 的末尾,t 用来累加结果
        int cur1 = a.length() - 1, cur2 = b.length() - 1, t = 0;
        // 接着就可以开始从低位相加了
        while(cur1 >= 0 || cur2 >= 0 || t != 0){
            // 因为循环的条件是或，因此我们还要再循环内再判断一次，防止 cur1 和 cur2 越界,- '0' 是为了把字符转换为数字
            if(cur1 >= 0) t += a.charAt(cur1--) - '0';
            if(cur2 >= 0) t += b.charAt(cur2--) - '0';

            // 接着取出 t 的当前位，进位保留, + '0' 是把数字转换成字符
            ret.append((char)('0' + (t % 2)));
            t /= 2;
        }

        // 循环结束后 ret 就存储着求和的值，但注意，这个值的逆序的
        ret.reverse();

        // 最后把 ret 转换为 String 返回
        return ret.toString();
    }
}

3.4 字符串相乘

题目链接：字符串相乘

class Solution
{
    public String multiply(String num1, String num2)
    {
        // 获取两个数字的长度
        int m = num1.length(), n = num2.length();
        
        // 将数字字符串反转并转换为字符数组，方便逐位计算
        char[] n1 = new StringBuffer(num1).reverse().toString().toCharArray();
        char[] n2 = new StringBuffer(num2).reverse().toString().toCharArray();
        
        // 创建一个临时数组，用于存储无进位的乘积结果
        int[] tmp = new int[m + n - 1]; // 长度为m+n-1，因为每一位乘积最多扩展到m+n-1位
        
        // 1. ⽆进位相乘后累加
        for(int i = 0; i < m; i++) { // 遍历num1的每一位
            for(int j = 0; j < n; j++) { // 遍历num2的每一位
                // 把两位数字的乘积加到对应位置（i+j）
                tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
            }
        }
        
        // 2. 处理进位
        int cur = 0; // 当前处理的位置
        int t = 0; // 进位值
        StringBuffer ret = new StringBuffer(); // 用于存储最终的结果

        // 遍历tmp数组，将无进位的结果转化为正确的数字
        while(cur < m + n - 1 || t != 0) // 遍历到tmp的末尾或者有进位需要处理
        {
            if(cur < m + n - 1) // 如果当前位还在tmp数组范围内
                t += tmp[cur++]; // 加上当前位的值，并移动到下一位
            
            // 当前位的数字是t % 10，进位是t / 10
            ret.append((char)(t % 10 + '0')); // 保存当前位的数字（转换为字符后添加到结果中）
            t /= 10; // 更新进位值
        }

        // 3. 去除结果中的多余前导零
        while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0') {
            ret.deleteCharAt((ret.length() - 1)); // 删除结果最后的0，直到结果长度大于1
        }

        // 结果需要再反转一次，变为正序返回
        return ret.reverse().toString();
    }
}