LeetCode 第25、27、28题

LeetCode 第25题：K个一组翻转链表

题目描述

给你链表的头节点head，每k个节点一组进行翻转，请你返回修改后的链表。

k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。

不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

难度：困难

题目链接：25. K 个一组翻转链表 - 力扣（LeetCode）

示例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]

提示：

• 链表中的节点数目为n
• 1<=k<=n<=5000
• 0<=Node.val<=1000

解题思路

方法一：迭代法： 使用迭代的方式，每次处理k个节点

• 创建虚拟头节点
• 计算链表长度
• 对于每组k个节点：

1. 判断剩余节点是否足够k个
2. 保存组的前驱和后继
3. 翻转k个节点
4. 连接翻转后的组

• 返回虚拟头节点的下一个节点
• 时间复杂度：O(n)，其中n是链表的长度
• 空间复杂度：O(1)

/**Definition for singly-linked list.public class ListNode{public int val;public ListNode next;public ListNode(int val=0,ListNode next=null){this.val = val;this.next = next;}}
**/
public class Solution{public ListNode ReverseKGroup(ListNode head,int k){if(head ==null || k==1)  return head;//创建虚拟头节点ListNode dummy = new ListNode(0);dummy.next = head;ListNode prev = dummy;ListNode curr = head;//计算链表长度int length = 0;while(head!=null){length++;head=head.next;}//处理每组k个节点for(int i=0;i<length/k;i++){//翻转k个节点for(int j=1;j<k;j++){ListNode next = curr.next;curr.next = next.next;next.next = prev.next;prev.next = next;}prev = curr;curr = curr.next;}return dummy.next;}
}

方法二：递归法（利用递归的特性，将问题分解为子问题）

递归思路：

• 基线条件：剩余节点不足k个
• 对于每组k个节点：

1. 翻转当前k个节点
2. 递归处理后续节点

• 返回新的头节点

public class Solution
{public ListNode ReverseKGroup(ListNode haed,int k){if(head==null || k==1)  return head;//检查剩余节点是否足够k个ListNode curr = head;int count = 0;while(curr!=null && count<k){curr = curr.next;count++;}//如果不足k个节点，返回原链表if(count<k) return head;//翻转k个节点curr=head;ListNode prev = null;ListNode next = null;for(int i=0;i<k;i++){next = curr.next;curr.next = prev;prev = curr;curr = next;}//递归处理后续节点head.next = ReverseKGroup(curr,k);return prev;}
}

 LeetCode 第27题：移除元素

题目描述

给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用O(1)额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

难度：简单

题目链接：27. 移除元素 - 力扣（LeetCode）

示例1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

• 0<=nums.length<=100
• 0<=nums[i]<=50
• 0<=val<=100

解题思路

方法一：双指针（快慢指针）

使用快慢指针的方法，慢指针指向当前可以放置元素的位置，快指针用于遍历数组。

• 初始化慢指针slow=0；
• 使用快指针fast遍历数组

1. 如果nums[fast]!=val，将元素复制到slow位置
2.  slow指针前进一位

• 返回slow（新数组的长度）
• 时间复杂度：O（n），其中n是数组的长度
• 空间复杂度：O(1)

public class Solution
{public int RemoveRlement(int[] nums,int val){int slow = 0;for(int fast = 0;fast<nums.Length;fast++){if(nums[fast]!=val){nums[slow] = nums[fast];slow++;}}return slow;}
}

方法二：双指针（首尾指针）使用首尾指针的方法，当遇到需要移除的元素时，用数组末尾的元素替换它

• 初始化左指针left=0，右指针right=nums.length-1
• 当left<=right时：

1. 如果nums[left]==val，用nums[right]替换，right--
2. 否则left++；

• 返回left（新数组长度）

public class Solution{public int RemoveElement(int[] nums,int val){int left = 0,right = nums.Length-1;while(left<right){if(nums[left]==val){nums[left]=nums[right];right--;}else{left++;}}return left;}
}

LeetCode 第28题 找出字符串中第一个匹配项的下标

 题目描述

给你两个字符串haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从0开始）。如果needle不是haystack的一部分，则返回-1。

难度：简单

题目链接：28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

示例1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

 示例2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示

• 1<=haystack.length，needle.length<=104
• haystack和needle仅由小写英文字符组成

解题思路：

方法一：暴力求解（不做解释）

方法二：KMP算法

• 构建模式串的next数组
• 利用next数组进行匹配

1. 主串指针i不回溯
2. 模式串指针j根据next数组移动

• 找到匹配或遍历完主串
• 时间复杂度：O（m+n）
• 空间复杂度：O(n)，用于存储next数组 

public class Solution
{public int StrStr(string haystack,string needle){if(string.IsNullOrEmpty(needle)) return 0;if(haystack.Length<needle.Length) return -1;//构建next数组int[] next = BuildNext(needle);//KMP匹配过程int i=0,j=0;while(i<haystack.Length && j<needle.Length){if(j==-1 || haystack[i]==needle[j]) i++,j++;else j=next[j];}return j = needle.Length ? i-j:-1;}private int[] BuildNext(string pattern){int[] next = new int[pattern.Length];next[0]=-1;int i=0,j=-1;while(i<pattern.Length-1){if(j==-1 || pattern[i]==pattern[j]) i++,j++,next[i]=j;else j= next[j];}return next;}
}