算法实践(双指针)

算法

Posted by XuHAo on January 6, 2019

算法实践之双指针-go语言


有序数组的 Two Sum

有序数组的 Two Sum

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2

说明:

  • 返回的下标值(index1 和 index2)不是从零开始的。
  • 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
func twoSum(numbers []int, target int) []int {
	//双指针思想
	minP:=0
	maxP:=len(numbers)-1
	sum:=numbers[minP]+numbers[maxP]
	for sum!=target{
		//保持maxP>minP
		if maxP-minP<=1{
			break
		}
		//指针移动
		if sum>target{
			maxP=maxP-1
		}else{
			minP=minP+1
		}
		//重新求和
		sum=numbers[minP]+numbers[maxP]
	}
	return []int{minP,maxP}
}

两数平方和

两数平方和

给定一个非负整数 c ,你要判断是否存在两个整数 ab,使得 a2 + b2 = c。

示例1:

输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5

示例2:

输入: 3
输出: False
func judgeSquareSum(c int) bool {
	intoNum:=c
	minNum:=0
	maxNum:=int(math.Sqrt(float64(c)))
	sum:=minNum*minNum+maxNum*maxNum
	isFind:=true

	if maxNum*maxNum>intoNum{
		maxNum--
	}
	sum=minNum*minNum+maxNum*maxNum
	for sum!=intoNum{
		if minNum>maxNum{
			isFind=false
			break
		}
		if sum>intoNum{
			maxNum=maxNum-1
		}else{
			minNum=minNum+1
		}
		sum=minNum*minNum+maxNum*maxNum
	}
	return isFind
}

反转字符串中的元音字符

反转字符串中的元音字符

编写一个函数,以字符串作为输入,反转该字符串中的元音字母。

示例 1:

输入: "hello"
输出: "holle"

示例 2:

输入: "leetcode"
输出: "leotcede"

说明: 元音字母不包含字母”y”。

func reverseVowels(s string) string {
	//双指针

	//初始化元音集合
	vowelsTemp := []string{"a", "e", "i", "o", "u", "A", "E", "I", "O", "U"}
	vowels := make(map[string]bool)
	for _, v := range vowelsTemp {
		vowels[v] = true
	}

	str:=[]rune(s)

	rP:=0
	lP:=len(str)-1

	for rP<=lP{
		cR:=string(str[rP])
		cL:=string(str[lP])
		if _,isFind:=vowels[cR];!isFind{
			rP++
		}else if _,isFind:=vowels[cL];!isFind {
			lP--
		}else {
			//交换
			tempStr:=str[rP]
			str[rP]=str[lP]
			str[lP]=tempStr
			rP++
			lP--
		}
	}

	strReturn:=string(str)
	return strReturn
}

回文字符串

回文字符串

给定一个非空字符串 s最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: "aba"
输出: True

示例 2:

输入: "abca"
输出: True
解释: 你可以删除c字符。

注意:

  1. 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
func validPalindrome(s string) bool {
	//双指针
	str:=[]rune(s)
	headPoint:=0
	tailPoint:=len(str)-1

	//双指针循环
	for(headPoint<tailPoint){

		headChar:=string(str[headPoint])
		tailChar:=string(str[tailPoint])

		if headChar!=tailChar{
			return  isPalindrome(str,headPoint+1,tailPoint)||isPalindrome(str,headPoint,tailPoint-1)
		}
		headPoint++
		tailPoint--
	}
	return true
}
func isPalindrome(str []rune,headP,tailP int) bool{
	for(headP<tailP){
		if str[headP]!=str[tailP]{
			return false
		}
		headP++
		tailP--
	}
	return true
}


归并两个有序数组

归并两个有序数组

给定两个有序整数数组 nums1nums2,将 nums2 合并到 nums1使得 num1 成为一个有序数组。

说明:

  • 初始化 nums1nums2 的元素数量分别为 mn
  • 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]
func merge(nums1 []int, m int, nums2 []int, n int)  {
	//初始化索引,由尾开始
	indexA:=m-1
	indexB:=n-1
	index:=m+n-1
	for indexA>=0||indexB>=0{
		if indexA<0{ //nums1 中数取完
			nums1[index]=nums2[indexB]
			index--
			indexB--
		}else if indexB<0{  //nums2中数取完
			nums1[index]=nums1[indexA]
			index--
			indexA--
		}else if nums1[indexA]>nums2[indexB]{
			nums1[index]=nums1[indexA]
			index--
			indexA--
		}else{
			nums1[index]=nums2[indexB]
			index--
			indexB--
		}
	}
}

最长子序列

最长子序列

给定一个字符串和一个字符串字典,找到字典里面最长的字符串,该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个,返回长度最长且字典顺序最小的字符串。如果答案不存在,则返回空字符串。

示例 1:

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

输出: 
"apple"

示例 2:

输入:
s = "abpcplea", d = ["a","b","c"]

输出: 
"a"

说明:

  1. 所有输入的字符串只包含小写字母。
  2. 字典的大小不会超过 1000。
  3. 所有输入的字符串长度不会超过 1000。
func findLongestWord(s string, d []string) string {
	maxLong := ""
	for _, st := range d {
		str := string(st)
		//比较maxLong与str长度
		if len(maxLong) > len(str) {
			continue
		}
		//比较同长度字符
		if len(maxLong) == len(str) {
			if dictCount(maxLong, str) {
				continue
			}
		}
		if isVaild(s, str) {
			maxLong = str
		}
	}
	return maxLong
}

func isVaild(s, str string) bool {
	i, j := 0, 0
	for i < len(s) && j < len(str) {
		if s[i] == str[j] {
			j++
		}
		i++
	}
	return j == len(str)
}

//maxLong 小于 str 返回 true
func dictCount(maxLong, str string) bool {
	for i := 0; i < len(str); i++ {
		if maxLong[i]<str[i]{
			return true
		}else if maxLong[i]==str[i]{
			continue
		}
		return false
	}
	return false
}