26. 删除有序数组中的重复项

image-20220913081623626

解题思路：

因为数组是有序的，所以直接往后遍历即可

定义快慢指针，快指针fast在前方探路，slow跟着后面，当fast发现一个新元素时，slow前进一步并赋值

当fast走到末尾时，nums[:slow]就是一个完全去重的数组

1

示例代码：

1
2
3
4
5
6
7
8
9
10
func removeDuplicates(nums []int) int {
    slow := 0
    for fast := 0; fast < len(nums); fast++ {
      	if nums[slow] != nums[fast] {
         	slow++
         	nums[slow] = nums[fast]
      	}
   	}
   	return slow + 1
}

27. 移除元素

image-20220913082134931

解题思路：

思路与前一题类似，依旧是定义快慢指针，不同的地方在于，前一题是fast遇到不同的元素，则slow前进并赋值，此题是fast遇到值不为val元素时，slow赋值并前进

示例代码：

1
2
3
4
5
6
7
8
9
10
11
func removeElement(nums []int, val int) int {
   	slow := 0
   	for fast := 0; fast < len(nums); fast++ {
      	if nums[fast] != val {
         	nums[slow] = nums[fast]
         	slow++
      	}
   	}
   	// 因为先复制后前进,所以返回值不+1
   	return slow
}

283. 移动零

image-20220913082948040

解题思路：

快指针fast向前遍历，遇到非0值就与慢指针slow所在值进行交换，fast遍历结束，所有的0都处于数组后半段

此题与26和27的思路类似，可以看做是27题的移除元素0的升级版，把移除变成了交换位置

示例代码：

1
2
3
4
5
6
7
8
9
func moveZeroes(nums []int) {
	slow := 0
	for fast := 0; fast < len(nums); fast++ {
		if nums[fast] != 0 {
			nums[fast], nums[slow] = nums[slow], nums[fast]
			slow++
		}
	}
}

167. 两数之和 II - 输入有序数组

image-20220913083308448

解题思路：

根据题意，数组是有序的，定义左右指针left和right分别指向数组头和尾，通过调节left和right来调整和的大小与target进行对比，即：

比target大时，right--，和变小
比target小时，left++，和变大

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
func twoSum(numbers []int, target int) []int {
	for i, j := 0, len(numbers)-1; i < j; {
		if numbers[i]+numbers[j] < target {
			i++
		} else if numbers[i]+numbers[j] > target {
			j--
		} else {
			return []int{i + 1, j + 1}
		}
	}
	return nil
}

344. 反转字符串

image-20220913083804229

解题思路：

定义左右指针，相向而行，交换值

示例代码：

1
2
3
4
5
6
7
8
func reverseString(s []byte) {
	i, j := 0, len(s)-1
	for i < j {
		s[i], s[j] = s[j], s[i]
		i++
		j--
	}
}

5. 最长回文子串

image-20220913083951766

解题思路：

采用中心拓展的方式可以判断出一个字符串是否为回文串

回文串根据长度区分，可分为奇数与偶数两种，如果回文串的长度为奇数，则它有一个中心字符；如果回文串的长度为偶数，则可以认为它有两个中心字符

之后我们遍历输入的字符串，求每(两)个字符串的回文串，最终返回最长的那一个即可满足条件

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 中心拓展获取回文串，当i与j相同时则取出的是奇数回文串，i与j相邻时取出的是偶数回文串
func getPalindrome(s string, i, j int) string {
	for i >= 0 && j < len(s) && s[i] == s[j] {
		i--
		j++
	}

	return s[i+1 : j]
}

func longestPalindrome(s string) string {
	var str string
	for i := 0; i < len(s); i++ {
		res := getPalindrome(s, i, i)
		if len(res) > len(str) {
			str = res
		}
		res = getPalindrome(s, i, i+1)
		if len(res) > len(str) {
			str = res
		}
	}
	return str
}

参考链接：