【优选算法】（第二十八篇）

K个⼀组翻转链表（hard）

题目解析

讲解算法原理

编写代码

两数之和（easy）

题目解析

讲解算法原理

编写代码

K个⼀组翻转链表（hard）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你链表的头节点head，每k个节点⼀组进⾏翻转，请你返回修改后的链表。k是⼀个正整数，它的值⼩于或等于链表的⻓度。如果节点总数不是k的整数倍，那么请将最后剩余
的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，⽽是需要实际进⾏节点交换。
⽰例1：

输⼊：head=[1,2,3,4,5],k=2输出：[2,1,4,3,5]
⽰例2：

输⼊：head=[1,2,3,4,5],k=3输出：[3,2,1,4,5]

提⽰：链表中的节点数⽬为n1<=k<=n<=5000
0<=Node.val<=1000

进阶：你可以设计⼀个只⽤O(1)额外内存空间的算法解决此问题吗？

讲解算法原理

解法（模拟）：算法思路：
本题的⽬标⾮常清晰易懂，不涉及复杂的算法，只是实现过程中需要考虑的细节⽐较多。我们可以把链表按 K 个为⼀组进⾏分组，组内进⾏反转，并且记录反转后的头尾结点，使其可以和
前、后连接起来。思路⽐较简单，但是实现起来是⽐较复杂的。
我们可以先求出⼀共需要逆序多少组（假设逆序 n 组），然后重复 n 次⻓度为 k 的链表的逆序即可。

编写代码

c++算法代码：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution
{
public:ListNode* reverseKGroup(ListNode* head, int k) {// 1. 先求出需要逆序多少组int n = 0;ListNode* cur = head;while(cur){cur = cur->next;n++;}n /= k;// 2. 重复 n 次：⻓度为 k 的链表的逆序即可ListNode* newHead = new ListNode(0);ListNode* prev = newHead;cur = head;for(int i = 0; i < n; i++){ListNode* tmp = cur;for(int j = 0; j < k; j++){ListNode* next = cur->next;cur->next = prev->next;prev->next = cur;cur = next;}prev = tmp;}// 把不需要翻转的接上prev->next = cur;cur = newHead->next;delete newHead;return cur;}
};

java 算法代码：

/*** 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) {// 1. 先求出需要逆序多少组int n = 0;ListNode cur = head;while(cur != null){cur = cur.next;n++;}n /= k;// 2. 重复 n 次：⻓度为 k 的链表的逆序 ListNode newHead = new ListNode(0); ListNode prev = newHead;cur = head;for(int i = 0; i < n; i++){ListNode tmp = cur;for(int j = 0; j < k; j++){// 头插的逻辑ListNode next = cur.next;cur.next = prev.next;prev.next = cur;cur = next;}prev = tmp;}// 把后⾯不需要逆序的部分连接上prev.next = cur;return newHead.next;}
}

两数之和（easy）

题目解析

1.题目链接：. - 力扣（LeetCode）

有⼈相爱，有⼈夜⾥开⻋看海，有⼈leetcode第⼀题都做不出来。

2.题目描述

给定⼀个整数数组nums和⼀个整数⽬标值target，请你在该数组中找出和为⽬标值target的那两个整数，并返回它们的数组下标。
你可以假设每种输⼊只会对应⼀个答案。但是，数组中同⼀个元素在答案⾥不能重复出现。你可以按任意顺序返回答案。
⽰例1：
输⼊：nums=[2,7,11,15],target=9
输出：[0,1]
解释：因为nums[0]+nums[1]==9，返回[0,1]。
⽰例3：
输⼊：nums=[3,3],target=6
输出：[0,1]

讲解算法原理

解法（哈希表）：
算法思路：
• 如果我们可以事先将「数组内的元素」和「下标」绑定在⼀起存⼊「哈希表」中，然后直接在哈希
表中查找每⼀个元素的 target - nums[i] ，就能快速的找到「⽬标和的下标」。• 这⾥有⼀个⼩技巧，我们可以不⽤将元素全部放⼊到哈希表之后，再来⼆次遍历（因为要处理元素
相同的情况）。⽽是在将元素放⼊到哈希表中的「同时」，直接来检查表中是否已经存在当前元素所对应的⽬标元素（即 target - nums[i] ）。如果它存在，那我们已经找到了对应解，并⽴即将其返回。⽆需将元素全部放⼊哈希表中，提⾼效率。
• 因为哈希表中查找元素的时间复杂度是 O(1) ，遍历⼀遍数组的时间复杂度为 O(N) ，因此可以
将时间复杂度降到 O(N) 。
这是⼀个典型的「⽤空间交换时间」的⽅式。

编写代码

c++算法代码：

class Solution
{
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash; // <nums[i], i>for(int i = 0; i < nums.size(); i++){int x = target - nums[i];if(hash.count(x)) return {hash[x], i};hash[nums[i]] = i;}// 照顾编译器return {-1, -1};}
};

java 算法代码：

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)};}hash.put(nums[i], i);}// 照顾编译器return new int[]{-1, -1};}
}