LC 26. Remove Duplicates from Sorted Array 删除有序数组中的重复项
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
| Code Block |
|---|
|
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
} |
另一种解法：思路类似，只是代码组织形式不同
| Code Block |
|---|
|
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/
| Code Block |
|---|
|
/**
* 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/
| Code Block |
|---|
|
func removeElement(nums []int, val int) int {
slow, fast := 0, 0
for ; fast < len(nums); fast++ {
if nums[fast] != val {
nums[slow] = nums[fast]
slow++
}
}
return slow
} |
LC 283. Move Zeroes 移动零
https://leetcode.com/problems/move-zeroes/
| Code Block |
|---|
|
func moveZeroes(nums []int) {
slow, fast := 0, 0
for ; fast < len(nums); fast++ {
if nums[fast] != 0 {
nums[slow] = nums[fast]
slow++
}
}
for i := slow; i < len(nums); i++ {
nums[i] = 0
}
} |
其实和上面的「移除元素」一样，只不过不是返回 slow 而是把 nums[slow..] 赋值为 0
| Code Block |
|---|
|
func moveZeroes(nums []int) {
x := removeElement(nums, 0)
for i := x; i < len(nums); i++ {
nums[i] = 0
}
}
func removeElement(nums []int, val int) int {
slow, fast := 0, 0
for ; fast < len(nums); fast++ {
if nums[fast] != val {
nums[slow] = nums[fast]
slow++
}
}
return slow
} |
LC 167. Two Sum II - Input Array Is Sorted 两数之和 II - 输入有序数组
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
| Code Block |
|---|
|
func twoSum(nums []int, target int) []int {
i, j := 0, len(nums) - 1
for i < j {
if nums[i] + nums[j] == target {
return []int{i + 1, j + 1}
} else if nums[i] + nums[j] < target {
i++
} else {
j--
}
}
return nil // impossible
} |
注意返回的 index 是 1-based
LC 344. Reverse String 反转字符串
https://leetcode.com/problems/reverse-string/
| Code Block |
|---|
|
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/
| Code Block |
|---|
|
func longestPalindrome(s string) string {
result := ""
for i := 0; i < len(s); i++ {
ps := longestPalindrome1(s, i)
if len(ps) > len(result) {
result = ps
}
}
for i := 0; i < len(s)-1; i++ {
ps := longestPalindrome2(s, i, i+1)
if len(ps) > len(result) {
result = ps
}
}
return result
}
func longestPalindrome1(s string, center int) string {
i, j := center, center
for i >= 0 && j < len(s) && s[i] == s[j] {
i--
j++
}
return s[i+1:j]
}
func longestPalindrome2(s string, centerL, centerR int) string {
i, j := centerL, centerR
for i >= 0 && j < len(s) && s[i] == s[j] {
i--
j++
}
return s[i+1:j]
} |
精简、合并一些代码
| Code Block |
|---|
|
func longestPalindrome(s string) string {
result := ""
for i := 0; i < len(s); i++ {
ps := palindrome(s, i, i)
if len(ps) > len(result) {
result = ps
}
ps = palindrome(s, i, i+1)
if len(ps) > len(result) {
result = ps
}
}
return result
}
// 在 s 中寻找以 s[centerL] 和 s[centerR] 为中心的最长回文串
func palindrome(s string, centerL, centerR int) string {
i, j := centerL, centerR
for i >= 0 && j < len(s) && s[i] == s[j] {
i--
j++
}
return s[i+1:j]
} |
进阶解法：Manacher 算法