409.最长回文子串
代码:
func longestPalindrome(s string) int {
var pair := make(map[byte]int)
for i:=0;i<len(s);i++{
pair[s[i]]++
}
var sum int
flag := false
for _,v := range(pair){
if v % 2 != 0{
flag = true
v = v - 1
}
sum += v
}
if flag {
sum ++
}
return sum
}
思路:
- 只需返回回文串长度,只要是字符出现的次数为偶数就直接相加,如果有为奇数的,则减1相加,并把标志位置true,最后总的sum加一
- 没用到双指针,也没看到题解用双指针,不知道双指针是怎么实现的
125.验证回文串
代码:
func isPalindrome(s string) bool {
var a string
for i:=0;i<len(s);i++{
if isANum(s[i]){
a += string(s[i])
}
}
a = strings.ToUpper(a)
for i,j:=0,len(a)-1;i<j;i++{
if a[i] != a[j]{
return false
}
j--
}
return true
}
func isANum(s byte)bool{
return (s >='0' && s <= '9') || (s >= 'A' && s <= 'Z') || (s >='a' && s <='z')
}
思路:
- 在原字符串上一边遍历一边改变长度不是个好办法,情愿新申请一个变量
- 预处理字符串后,使用双指针头尾结合判断
- A的ASCII码为65,Z的ASCII码为90,a的ASCII码为97,z的ASCII码为122
5.最长回文子串
代码:
func longestPalindrome(s string) string {
maxLen := ""
for i:=0;i<len(s);i++{
temLen := ""
for left,right:=i,i;left >=0 && right <len(s);left--{
if s[left] != s[right]{
break
}
temLen = s[left:right+1]
if len(temLen) > len(maxLen){
maxLen = temLen
}
right++
}
temLen = ""
for left,right:=i,i+1;left >=0 && right <len(s);left--{
if s[left] != s[right]{
break
}
temLen = s[left:right+1]
if len(temLen) > len(maxLen){
maxLen = temLen
}
right++
}
}
return maxLen
}
思路:
- 中心扩散法,从第一个位置开始,两个指针分别向两边扩散,判断是否相等,保存最长的字符串
- 有两种情况,一种为偶偶,另种为偶奇偶。扩散的方式不同,需要两种情况
1.两数之和
代码:
func twoSum(nums []int, target int) []int {
pair := make(map[int]int)
for k,v := range(nums){
if ret,ok := pair[target-v];ok{
return []int{ret,k}
}
pair[v] = k
}
return []int{}
}
思路:
- 使用target—v来作为查找判断,这个key是否在map里。
- index作为map的value,这样直接定位到在数组中的序号
15.三数之和
代码:
import "sort"
func threeSum(nums []int) [][]int {
ret := [][]int{}
sort.Ints(nums)
for i:=0;i<len(nums);i++{
if i > 0 && nums[i] == nums[i-1]{
continue
}
k := len(nums)-1
target := -1 * nums[i]
for j:=i+1;j<len(nums);j++{
if j > i+1 && nums[j] == nums[j-1]{
continue
}
for j < k && nums[k] + nums[j] > target{
k--
}
if k == j{
break
}
if nums[k] + nums[j] == target{
ret = append(ret,[]int{nums[i],nums[j],nums[k]})
}
}
}
return ret
}
思路:
- 先排序,排完一切好说
- 如果两个数是一样的,就跳过
- 利用递增的特性,第三圈的时候,把指针移到小于的情况
- 直接判断是的话就append
- 当j递增的时候,k在回到第三步