二分法
基本思路是利用查找中间值,将中间值和target比较,判断,target在左区间还是右区间, 如果nums[mid] > target ,则说明target在左区间
right赋值为mid – 1, 如果nums[mid] > target, 则说明target在右区间,更新left = mid + 1
func search(nums []int, target int) int {
high := len(nums) - 1
low := 0
for low <= high {
mid := low + (high-low)/2
if nums[mid] == target {
return mid
} else if nums[mid] > target {
high = mid - 1
} else {
low = mid + 1
}
}
return -1
}
双指针法
定义两个指针,快指针可以在for
循环 里,不用额外定义。慢指针要定义,两个都从0开始,如果快指针与目标值不相等则每一次慢指针递增一,如果相等,则慢指针停下,快指针在for循环递增,数组当前元素=数组当前索引对应的下一个元素。
func removeElement(nums []int, val int) int {
l := len(nums)
//fast := 0
slow := 0
for fast :=0; fast<l; fast ++{
if val != nums[fast]{
nums[slow] = nums[fast]
slow ++
}
}
return slow
}
leetcode 26
自己想的比较低效的一种写法
func removeDuplicates(nums []int) int {
slow := 0
l := len(nums)
ln := len(nums)
if ln == 0{
return 0
}
if ln<2{
return 1
}
for fast :=slow+1; fast<l; fast++{
if nums[fast]== nums[slow]{
for i:=slow; i<l-1;i++{
nums[i] = nums[i+1]
}
fmt.Println("---")
fmt.Println("l:", l)
if nums[fast]==nums[slow]{
fast--
slow--
}
l --
}
slow ++
}
fmt.Println(nums)
return l
}
借鉴了评论里一个大佬方案
func removeDuplicates(nums []int) int {
slow := 0
fast := 1
l := len(nums)
if l<2{
return l
}
for fast<l{
if nums[slow]!=nums[fast]{
nums[slow+1]=nums[fast]
slow ++
}
fast++
//l--
}
return slow+1
}
对比了一下,我是对比如果相等的情况,而他的是对比不相等的情况,如果不相等那么把当前指针后一个索引的数字赋值为fast指向的数字,然后slow向后移一位,其他情况那么fast继续向后走。
leetcode844
堆栈
func backspaceCompare(s string, t string) bool {
// 堆栈
return build(s)==build(t)
}
func build(str string)string{
s := []byte{}
for i,v := range str{
if v != 35{
s = append(s, str[i])
}else if len(s)>0{
// fmt.Println("pop before:", string(s))
s = append(s[:0], s[:len(s)-1]...)
// fmt.Println("pop after:", string(s))
}
}
return string(s)
}
双指针法
func backspaceCompare(s string, t string) bool {
flagS, flagT := 0, 0
i , j := len(s)-1, len(t)-1
for i>=0||j>=0 {
for i >= 0{
if s[i] == 35 {
flagS++
i--
} else if flagS > 0 {
flagS--
i--
}else {
// 这个时候说明遇到正常字符,不用去掉的那种,这个时候需要停下,让另一个循环执行, 如果两个字符相等那么继续,不相等直接返回false
break
}
}
for j >= 0{
if t[j] == 35 {
flagT++
j--
} else if flagT > 0 {
flagT--
j--
}else{
break
}
}
if i>=0&&j>=0{
if s[i]!= t[j]{
return false
}
}else if i>=0||j>=0{
return false
}
// 能坚持到这,说明都是被break了, 没有--
i--
j--
}
return true
}