优选算法 - 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) {// 先处理特殊情况，当两个字符串的长度不相同时，一定不是重排字符串2if(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']--;// 此时如果有某一位出现负数了。那么直接返回 falseif(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 和 lenif(right - left - 1 > len){begin = left + 1; // 因为 left 和 right 都越过了回文子串的范围，他们是用完后再加加的len  = right - left - 1;} // 接着处理偶数的情况2left = 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 / 10ret.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();}
}