Week 42 @ 2024 算法周记【双指针数组】
- Bryan
Owned by Bryan
LC 26. Remove Duplicates from Sorted Array 删除有序数组中的重复项
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
func removeDuplicates(nums []int) int {
i := 0
j := 1
for ; j < len(nums); j++ {
if nums[j] == nums[j-1] {
// duplicate
continue
}
nums[i+1] = nums[j]
i++
}
return i+1
}另一种解法：思路类似，只是代码组织形式不同
func removeDuplicates(nums []int) int {
slow, fast := 0, 0
for fast < len(nums) {
if nums[fast] != nums[slow] {
slow++
nums[slow] = nums[fast]
}
fast++
}
return slow+1
}LC 83. Remove Duplicates from Sorted List 删除排序链表中的重复元素
https://leetcode.com/problems/remove-duplicates-from-sorted-list/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return nil
}
slow, fast := head, head
for fast != nil {
if slow.Val != fast.Val {
slow.Next = fast
slow = slow.Next
}
fast = fast.Next
}
slow.Next = nil
return head
}注意：数组版本保证至少有一个元素，而链表版本并没有保证，所以链表版本的代码需要判断是否为空（否则会空指针异常）
LC 27. Remove Element 移除元素
https://leetcode.com/problems/remove-element/
LC 283. Move Zeroes 移动零
https://leetcode.com/problems/move-zeroes/
其实和上面的「移除元素」一样，只不过不是返回 slow 而是把 nums[slow..] 赋值为 0
LC 167. Two Sum II - Input Array Is Sorted 两数之和 II - 输入有序数组
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
注意返回的 index 是 1-based
LC 344. Reverse String 反转字符串
https://leetcode.com/problems/reverse-string/
LC 5. Longest Palindromic Substring 最长回文子串
https://leetcode.com/problems/longest-palindromic-substring/
精简、合并一些代码
进阶解法：Manacher 算法