Week 42 @ 2024 算法周记【双指针数组】

1 LC 26. Remove Duplicates from Sorted Array 删除有序数组中的重复项
- 1.1 LC 83. Remove Duplicates from Sorted List 删除排序链表中的重复元素
2 LC 27. Remove Element 移除元素
- 2.1 LC 283. Move Zeroes 移动零
3 LC 167. Two Sum II - Input Array Is Sorted 两数之和 II - 输入有序数组
4 LC 344. Reverse String 反转字符串
5 LC 5. Longest Palindromic Substring 最长回文子串

LC 26. Remove Duplicates from Sorted Array 删除有序数组中的重复项

Remove Duplicates from Sorted Array - LeetCode

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 删除排序链表中的重复元素

Remove Duplicates from Sorted List - LeetCode

/**
 * 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 移除元素

Remove Element - LeetCode

LC 283. Move Zeroes 移动零

Move Zeroes - LeetCode

其实和上面的「移除元素」一样，只不过不是返回 slow 而是把 nums[slow..] 赋值为 0

LC 167. Two Sum II - Input Array Is Sorted 两数之和 II - 输入有序数组

Two Sum II - Input Array Is Sorted - LeetCode

注意返回的 index 是 1-based

LC 344. Reverse String 反转字符串

Reverse String - LeetCode

LC 5. Longest Palindromic Substring 最长回文子串

Longest Palindromic Substring - LeetCode

精简、合并一些代码

进阶解法：Manacher 算法