leetCode(GO)

twoSum

package main

func twoSum(nums []int, target int) []int {
	//	返回值为一个int数组
	m := make(map[int]int)
	//这里是初始化一个字典map
	for k, v := range nums {
		//循环遍历每一个num 其中k为下标 v为值
		if idx, ok := m[target-v]; ok {
			//这里将是将数组值存储为字典的键 取出来的idx就是 而这里的ok如果取出来有就是ture
			return []int{idx, k}
			//得到就返回回去而这里的idx其实就是数组下标 而k是值
		}
		m[v] = k
		//如果没有取到就放入map中
	}
	return nil
}
func main() {
	nums := []int{2, 3, 11, 7}
	twoSum(nums, 9)
}

addTwoNumbers

package main

type ListNode struct {
   //定义一个ListNode的结构体
   Val int
   //定义本节点的值
   Next *ListNode
   // 定义下一个节点的指针变量
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
   //
   head := &ListNode{Val: 0}

   //head 用来存储ListNode的地址
   n1, n2, carry, current := 0, 0, 0, head

   //n1 用来存放l1中的val的值 n2 ... carry用来标识进位 current 用来标识当前是那个节点
   for l1 != nil || l2 != nil || carry != 0 {

      //当三个不同时为零的时候就继续循环
      if l1 == nil {
         n1 = 0
      } else {
         n1 = l1.Val
         l1 = l1.Next
      }
      //主要是赋值操作
      if l2 == nil {
         n2 = 0
      } else {
         n2 = l2.Val
         l2 = l2.Next
      }
      current.Next = &ListNode{Val: (n1 + n2 + carry) % 10}
      //这步目的是存放下一个ListNode的值
      current = current.Next
      //当前指向的节点进行更改
      carry = (n1 + n2 + carry) / 10
      //对进位进行处理
   }
   return head.Next
   // 这步返回的不是第一个节点而是第二个节点.因为第一个节点我们并没有使用
}

lengthOfLongestSubstring

package main

func lengthOfLongestSubstring(s string) int {
	if len(s) == 0 {
		return 0
	}
	var bitSet [256]bool
	//简单来说就是打布尔标记
	result, left, right := 0, 0, 0

	for left < len(s) {
		//每一个字符都要循环
		if bitSet[s[right]] {
			//但前面已经有一个出现了的时候 也就是true的时候
			bitSet[s[left]] = false
			//就打回false
			left++
			//左边向前移动一位
		} else {
			//因为a的ascii是97 所以当到达这里时第97就会被打成true
			bitSet[s[right]] = true
			right++
		}
		if result < right-left {
			//判断当前是不是最长的如果是就改变最长的值
			result = right - left
		}
		if left+result > len(s) || right >= len(s) {
			//判断有没有越界问题
			break
		}
	}

	return result

}
func lengthOfLongestSubstring1(s string) int {
	if len(s) == 0 {
		return 0
	}
	var freq [127]int
	result, left, right := 0, 0, -1
	for left < len(s) {
		if right+1 < len(s) && freq[s[right+1]] == 0 {
			freq[s[right+1]]++
			right++
		} else {
			freq[s[left]]--
			left++
		}
		result = max(result, right-left+1)
	}
	return result

}
func lengthOfLongestSubstring2(s string) int {
	right, left, res := 0, 0, 0
	indexs := make(map[byte]int, len(s))
	for left < len(s) {
		if indx, ok := indexs[s[left]]; ok && indx >= right {
			right = indx + 1
		}
		indexs[s[left]] = left
		left++
		res = max(res, left-right)

	}
	return res

}
func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}
func main() {
	lengthOfLongestSubstring2("abcabcbb")
}

longestPalindrome

package main

func longestPalindrome(s string) string {
	if len(s) < 2 {
		return s
	}
	newS := make([]rune, 0)
	//rune为utf8类型主要用于汉字等
	newS = append(newS, '#')
	for _, c := range s {
		newS = append(newS, c)
		newS = append(newS, '#')
	}
	//	dp[i] 以预处理字符串下标i为中心的回文半径(奇数长度是不包括中心)
	//maxRight 通过中心扩散的方式能够扩散的最右边的下标
	//center 与maxRight对应的中心字符的下标
	//maxLen 记录最长回文串的半径
	//begin 记录最长回文串在起始串s中的起始下标
	dp, maxRight, center, maxlen, begin := make([]int, len(s)), 0, 0, 1, 0
	for i := 0; i < len(newS); i++ {
		if i < maxRight {
			dp[i] = min(maxRight-i, dp[2*center-i])
		}
		left, right := i-(1+dp[i]), i+(1+dp[i])
		for left >= 0 && right < len(newS) && newS[left] == newS[right] {
			dp[i]++
			left--
			right++

		}
		if i+dp[i] > maxRight {
			maxRight = i + dp[i]
			center = i
		}
		if dp[i] > maxRight {
			maxRight = i + dp[i]
			center = i
		}

		if dp[i] > maxlen {
			maxlen = dp[i]
			begin = (i - maxlen) / 2
		}
	}
	return s[begin : begin+maxlen]

}
func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}
func main() {
	longestPalindrome("babad")
}

func longestPalindrome2(s string) string {
	res := ""
	for i := 0; i < len(s); i++ {
		res = maxPalindrome(s, i, i, res)
		res = maxPalindrome(s, i, i+1, res)

	}
	return res

}
func maxPalindrome(s string, i, j int, res string) string {
	sub := ""
	for i >= 0 && j < len(s) && s[i] == s[j] {
		sub = s[i : j+1]
		i--
		j++

	}
	if len(res) < len(sub) {
		return sub
	}
	return res
}