【优选算法】（第二十八篇）
目录
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};
}
}原文地址：https://blog.csdn.net/weixin_73861555/article/details/142757076
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！