双指针链表
LC 234. Palindrome Linked List 回文链表
https://leetcode.com/problems/palindrome-linked-list/description/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
mid := getMid(head)
prev, h := mid, mid.Next
for h != nil {
next := h.Next
h.Next = prev
prev = h
h = next
}
mid.Next = nil
l, r := head, prev
// printList(l)
// printList(r)
for l != r && l != nil && r != nil {
// fmt.Println("compare", l.Val, r.Val)
if l.Val != r.Val {
return false
}
l = l.Next
r = r.Next
}
return true
}
// func printList(head *ListNode) {
// for head != nil {
// fmt.Print(head.Val, " -> ")
// head = head.Next
// }
// fmt.Println("END")
// }
func getMid(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
整理下代码
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
mid := getMid(head)
l, r := head, reverse(mid)
for l != nil && r != nil {
if l.Val != r.Val {
return false
}
l = l.Next
r = r.Next
}
return true
}
func getMid(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
func reverse(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
next := head.Next
head.Next = prev
prev = head
head = next
}
return prev
}
双指针数组
LC 26. Remove Duplicates from Sorted Array 删除有序数组中的重复项
https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/
判断当前元素是否重复
func removeDuplicates(nums []int) int {
slow, fast := 1, 1
for fast < len(nums) {
if nums[fast] == nums[fast-1] {
fast++
continue
}
nums[slow] = nums[fast]
slow++
fast++
}
return slow
}
判断当前元素是否已存在
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 27. Remove Element 移除元素
https://leetcode.com/problems/remove-element/description/
func removeElement(nums []int, val int) int {
slow, fast := 0, 0
for fast < len(nums) {
if nums[fast] != val {
nums[slow] = nums[fast]
slow++
}
fast++
}
return slow
}
LC 167. Two Sum II - Input Array Is Sorted 两数之和 II - 输入有序数组
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
func twoSum(nums []int, target int) []int {
l, r := 0, len(nums)-1
for l < r {
v := nums[l] + nums[r]
switch {
case v == target:
return []int{l+1, r+1}
case v < target:
l++
default:
r--
}
}
panic("impossible")
}
LC 344. Reverse String 反转字符串
https://leetcode.com/problems/reverse-string/description/
func reverseString(s []byte) {
i, j := 0, len(s)-1
for i < j {
s[i], s[j] = s[j], s[i]
i++
j--
}
}
LC 5. Longest Palindromic Substring 最长回文子串
https://leetcode.com/problems/longest-palindromic-substring/
func longestPalindrome(s string) string {
lp := ""
for i := range s {
ss := palindrome(s, i, i)
if len(ss) > len(lp) {
lp = ss
}
if i > 0 {
ss := palindrome(s, i-1, i)
if len(ss) > len(lp) {
lp = ss
}
}
}
return lp
}
func palindrome(s string, i, j int) string {
l, r := i, j
for l >= 0 && r < len(s) && s[l] == s[r] {
l--
r++
}
return s[l+1:r]
}
LC 80 删除有序数组中的重复项 II
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/
func removeDuplicates(nums []int) int {
slow, fast := 0, 0
for fast < len(nums) {
// fmt.Printf("slow = %d, fast = %d | %v | %v\n",
// slow, fast, nums[:slow], nums,
// )
if slow-2 < 0 || nums[fast] != nums[slow-1] || nums[fast] != nums[slow-2] {
// new element
nums[slow] = nums[fast]
slow++
}
fast++
}
return slow
}