前言

Leetcode里面的20天算法刷题计划中的算法入门部分的31道题，使用Go语言。

704. 二分查找

package question704

func Search(nums []int, target int) int {
	start,end := 0,len(nums)-1
	for start <= end {
		mid := (start+end)/2
		if nums[mid] == target {
			return mid
		}else if nums[mid] < target {
			start = mid+1
		}else {
			end = mid-1
		}
	}
	return -1
}

278. 第一个错误的版本

package question278

/**
 * Forward declaration of isBadVersion API.
 * @param   version   your guess about first bad version
 * @return 	 	      true if current version is bad
 *			          false if current version is good
 * func isBadVersion(version int) bool;
 */
func firstBadVersion(n int) int {
	start,end := 1,n
	for start <= end {
		mid := start + (end-start)/2
		if isBadVersion(mid) {
			end = mid-1
		}else {
			start = mid + 1
		}
	}
	return start
}

35. 搜索插入位置

package question35


func searchInsert(nums []int, target int) int {
	start,end := 0,len(nums)-1
	for start <= end {
		mid := (start+end)/2
		if nums[mid] == target {
			return mid
		}else if nums[mid] < target {
			start = mid+1
		}else {
			end = mid-1
		}
	}
	return -1
}

977. 有序数组的平方

package question977

func sortedSquares(nums []int) []int {
	var index int = len(nums)-1
	res := make([]int,len(nums))
	left,right := 0,len(nums)-1
	for left<=right {
		if nums[left]*nums[left] >= nums[right]*nums[right] {
			res[index] = nums[left]*nums[left]
			left++
		}else{
			res[index] = nums[right]*nums[right]
			right--
		}
		index--
	}
	return res
}

189. 轮转数组

package question189


func rotate(nums []int, k int)  {
	n := len(nums)
	k = k%n
	reverse(nums)
	reverse(nums[:k])
	reverse(nums[k:])
}

func reverse(nums []int){
	n := len(nums)
	for i:=0;i<n/2;i++{
		temp := nums[i]
		nums[i]=nums[n-i-1]
		nums[n-i-1] = temp
	}
}

283. 移动零

package question283

func moveZeroes(nums []int)  {
	left,right,n := 0,0,len(nums)
	for right < n {
		if nums[right] != 0 {
			nums[left],nums[right] = nums[right],nums[left]
			left++
		}
		right++
	}
}

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

package question167

func twoSum(numbers []int, target int) []int {
	n := len(numbers)
	left,right := 0,n-1

	for left<right {
		sum := numbers[left]+numbers[right]
		if sum==target {
			return []int{left+1,right+1}
		}else if sum<target {
			left++
		}else {
			right--
		}
	}
	return []int{}
}

344. 反转字符串

package question344

func reverseString(s []byte)  {
	n := len(s)
	for i:=0;i<(n>>1);i++{
		s[i],s[n-i-1] = s[n-i-1],s[i]
	}
}

557. 反转字符串中的单词 III

package question557

import "strings"

func reverseString(s []byte)  string{
	n := len(s)
	for i:=0;i<(n>>1);i++{
		s[i],s[n-i-1] = s[n-i-1],s[i]
	}
	return string(s)
}
func reverseWords(s string) string {
	ss := strings.Split(s," ")
	for i:=0;i<len(ss);i++ {
		ss[i] = reverseString([]byte(ss[i]))
	}
	return strings.Join(ss," ")
}

876. 链表的中间结点

package question876

type ListNode struct {
	Val  int
	Next *ListNode
}

func middleNode(head *ListNode) *ListNode {
	var leftNode,rightNode *ListNode = head,head
	for  {
		if rightNode.Next==nil {
			return leftNode
		}else{
			rightNode = rightNode.Next.Next
			leftNode = leftNode.Next
		}
		if rightNode==nil {
			return leftNode
		}
	}
}

19. 删除链表的倒数第 N 个结点

package question19

type ListNode struct {
	Val  int
	Next *ListNode
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	hhead := &ListNode{0,head}
	left,right := hhead,head
	for i:=0;i<n;i++ {
		right = right.Next
	}
	for ;right!=nil;left=left.Next {
		right = right.Next
	}
	left.Next = left.Next.Next
	return hhead.Next
}

/*func removeNthFromEnd(head *ListNode, n int) *ListNode {
	left,right := head,head
	for i:=0;i<n;i++ {
		right = right.Next
	}
	if right==nil {
		return head.Next
	}
	for ;right.Next!=nil;left=left.Next {
		right = right.Next
	}
	left.Next = left.Next.Next
	return head
}*/

3. 无重复字符的最长子串

package question3

func max(x,y int) int{
	if x>y{
		return x
	}else{
		return y
	}
}
/*func lengthOfLongestSubstring(s string) int {
	n := len(s)
	mmax := max(n,128)
	maxLength := 0
	left,right := 0,0
	for ;left<n;left++ {
		myMap := make(map[byte]int)
		for right=left;right<n&&right-left<mmax;right++ {
			if myMap[s[right]]>0 {
				break
			}
			myMap[s[right]]++
		}
		maxLength = max(maxLength,right-left)
		if right==n {
			return maxLength
		}
		left += strings.Index(string([]byte(s)[left:right]), string(s[right]))
		fmt.Println(left)
	}
	return maxLength
}*/
func lengthOfLongestSubstring(s string) int {
	n := len(s)
	mmax := max(n,128)
	maxLength := 0
	myMap := make(map[byte]int)
	left,right := 0,0
	for ;left<n;left++ {
		if left != 0 {
			myMap[s[left-1]]--
		}
		for ;right<n&&right-left<mmax;right++ {
			if myMap[s[right]]>0 {
				break
			}
			myMap[s[right]]++
		}
		maxLength = max(maxLength,right-left)
	}
	return maxLength
}

567. 字符串的排列

package question567

import "fmt"

func checkInclusion(s1 string, s2 string) bool {
	n1, n2 := len(s1), len(s2)
	if n1>n2 {
		return false
	}
	myMap := make(map[byte]int)
	for i := 0; i < n1; i++ {
		myMap[s1[i]]++
		myMap[s2[i]]--
	}
	var diff int = 0
	for _,k :=range myMap{
		if k!=0 {
			diff++
		}
	}
	if diff==0 {
		return true
	}

	for i := n1; i < n2; i++ {
		if myMap[s2[i-n1]]==0 {
			diff++
		}
		myMap[s2[i-n1]]++
		if myMap[s2[i-n1]]==0 {
			diff--
		}
		if myMap[s2[i]]==0 {
			diff++
		}
		myMap[s2[i]]--
		if myMap[s2[i]]==0 {
			diff--
		}
		fmt.Println(diff)
		if diff == 0 {
			return true
		}
	}
	return false

}
/*func checkInclusion(s1 string, s2 string) bool {
	n1, n2 := len(s1), len(s2)
    if n1>n2 {
        return false
    }
	map1 := make(map[byte]int)
	map2 := make(map[byte]int)
	for i := 0; i < n1; i++ {
		map1[s1[i]]++
		map2[s2[i]]++
	}
	var fflag bool = true
	for k, v := range map1 {
		if map2[k]!=v {
			fflag = false
		}
	}
	if fflag==true {
		return true
	}
    fmt.Println(map1)
	for i := 1; i < n2-n1+1; i++ {
		map2[s2[i-1]]--
		map2[s2[i+n1-1]]++
        fmt.Println(map1)
		var flag bool = true
		for k, v := range map1 {
			if map2[k]!=v {
				flag = false
			}
		}
		if flag==true {
			return true
		}
	}
	return false

}
*/

733. 图像渲染

package question733

//BFS
func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
	target := image[sr][sc]
	if target == newColor {
		return image
	}
	image[sr][sc] = newColor
	queue := [][]int{}
	xx := []int{-1, 0, 0, 1}
	yy := []int{0, -1, 1, 0}
	queue = append(queue, []int{sr, sc})
	for i := 0; i < len(queue); i++ {
		nowEle := queue[i]
		for j := 0; j < 4; j++ {
			mx, my := nowEle[0]+xx[j], nowEle[1]+yy[j]
			if mx >= 0 && my >= 0 && mx < len(image) && my < len(image[0]) && image[mx][my] == target {
				image[mx][my] = newColor
				queue = append(queue, []int{mx, my})
			}
		}
	}
	return image
}

695. 岛屿的最大面积

package question695

func maxAreaOfIsland(grid [][]int) int {
	res := 0
	xx := []int{-1, 0, 0, 1}
	yy := []int{0, -1, 1, 0}
	for i := 0;i<len(grid);i++ {
		for j := 0;j<len(grid[i]);j++ {
			if grid[i][j]==0 {
				continue
			}
			nowArea := 1
			queue := [][]int{}
			queue = append(queue,[]int{i,j})
			grid[i][j] = 0
			for k := 0; k < len(queue);k++ {
				nowEle := queue[k]
				for p := 0; p < 4; p++ {
					mx, my := nowEle[0]+xx[p], nowEle[1]+yy[p]
					if mx >= 0 && my >= 0 && mx < len(grid) && my < len(grid[0]) && grid[mx][my] != 0 {
						grid[mx][my] = 0
						nowArea++
						queue = append(queue, []int{mx, my})
					}
				}
			}
			if nowArea>res {
				res = nowArea
			}
		}
	}
	return res
}

617. 合并二叉树

package question617

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
//深度优先搜索
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	if root1==nil {
		return root2
	}else if root2==nil {
		return root1
	}
	root1.Val = root1.Val+root2.Val
	root1.Left = mergeTrees(root1.Left,root2.Left)
	root1.Right = mergeTrees(root1.Right,root2.Right)
	return root1
}

116. 填充每个节点的下一个右侧节点指针

package question116

type Node struct {
	Val   int
	Left  *Node
	Right *Node
	Next  *Node
}

func connect(root *Node) *Node {
	if root == nil {
		return root
	}
	if root.Left != nil {
		root.Left.Next = root
		root.Right.Next = root
	}
	if root.Next != nil {
		if root.Next.Right != root {
			root.Next = root.Next.Right
		} else if root.Next.Next == nil {
			root.Next = nil
		} else {
			root.Next = root.Next.Next.Left
		}
	}
	connect(root.Left)
	connect(root.Right)
	return root
}

542. 01 矩阵

package question542


func updateMatrix(mat [][]int) [][]int {

	n,m := len(mat),len(mat[0])
	queue := [][]int{}
	hasDeal := make([][]int,n)
	for k,_ := range hasDeal{
		hasDeal[k] = make([]int,m)
	}
	for i:=0;i<n;i++ {
		for j:=0;j<m;j++ {
			if mat[i][j]==0 {
				queue = append(queue, []int{i,j})
				hasDeal[i][j] = 1
			}
		}
	}
	xx := []int{-1,1,0,0}
	yy := []int{0,0,-1,1}
	for i:=0;i<len(queue);i++ {
		nowElem := queue[i]
		for j:=0;j<4;j++ {
			mx,my := nowElem[0]+xx[j],nowElem[1]+yy[j]
			if mx>=0&&my>=0&&mx<n&&my<m&&hasDeal[mx][my]==0 {
				hasDeal[mx][my] = hasDeal[nowElem[0]][nowElem[1]]+1
				mat[mx][my] = hasDeal[mx][my]-1
				queue = append(queue, []int{mx,my})
			}
		}
	}
	return mat
}

994. 腐烂的橘子

package question994

func orangesRotting(grid [][]int) int {
	n,m := len(grid),len(grid[0])

	queue := [][]int{}
	hasDeal := make([][]int,n)
	for k,_ := range hasDeal{
		hasDeal[k] = make([]int,m)
	}
	freshNum := 0
	for i:=0;i<n;i++ {
		for j:=0;j<m;j++ {
			if grid[i][j]==2 {
				queue = append(queue, []int{i,j})
				hasDeal[i][j] = 1
			}else if grid[i][j]==1 {
				freshNum++
			}
		}
	}
	if freshNum==0 {
		return 0
	}

	xx := []int{-1,1,0,0}
	yy := []int{0,0,-1,1}
	var res int
	for i:=0;i<len(queue);i++ {
		nowElem := queue[i]
		for j:=0;j<4;j++ {
			mx,my := nowElem[0]+xx[j],nowElem[1]+yy[j]
			if mx>=0&&my>=0&&mx<n&&my<m&&hasDeal[mx][my]==0&&grid[mx][my]==1 {
				hasDeal[mx][my] = hasDeal[nowElem[0]][nowElem[1]]+1
				res = hasDeal[mx][my]-1
				grid[mx][my] = 2
				freshNum--
				queue = append(queue, []int{mx,my})
			}
		}
	}
	if freshNum!=0 {
		return -1
	}
	return res

}

21. 合并两个有序链表

package question21

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1==nil {
		return list2
	}else if list2==nil {
		return list1
	}
	if list1.Val<list2.Val {
		list1.Next = mergeTwoLists(list1.Next,list2)
		return list1
	}else{
		list2.Next = mergeTwoLists(list1,list2.Next)
		return list2
	}

}

206. 反转链表

package question206

type ListNode struct {
	Val  int
	Next *ListNode
}
//迭代
func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	curr := head
	for curr!=nil {
		next := curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}
	return prev
}


//迭代
/*func reverseList(head *ListNode) *ListNode {
	if head==nil||head.Next==nil {
		return head
	}
	var mid,right *ListNode
	mid = head.Next
	right = mid.Next
	head.Next = nil
	for right!=nil{
		mid.Next = head
		head = mid
		mid = right
		right = right.Next
	}
	mid.Next = head
	return mid
}*/

//递归
/*func reverseList(head *ListNode) *ListNode {
	if head==nil||head.Next==nil {
		return head
	}
	res := reverseList(head.Next)
	head.Next.Next = head
	//很重要，为了防止链表循环，在处理第一个节点的时候 防止循环
	head.Next = nil
	return res
}*/

77. 组合

package question77

var res [][]int

func combine(n int, k int) [][]int {
	var path []int
	res = [][]int{}
	backtrace(path, n, k, 1)
	return res
}
func backtrace(path []int, n int, k int, start int) {
	if len(path) == k {
		//后续修改path，会影响到res中的内容。
		temp := make([]int, k)
		copy(temp, path)
		res = append(res, temp)
		return
	}
	for i := start; i <= n; i++ {
		//剪枝
		if i<=1+n-k+len(path) {
			path = append(path, i)
			backtrace(path, n, k, i+1)
			path = path[:len(path)-1]
		}
	}
}

46. 全排列

package question46

import "fmt"

var res [][]int
func permute(nums []int) [][]int {
	path := []int{}
	res = [][]int{}
	backtrace(path,nums)
	return res
}
func isInSlice(path []int,value int) bool{
	for _,v:=range path{
		if v == value {
			return true
		}
	}
	return false
}
func backtrace(path []int,nums []int) {
	if len(path) == len(nums) {
		fmt.Println(len(nums))
		//后续修改path，会影响到res中的内容。
		temp := make([]int, len(nums))
		copy(temp, path)
		res = append(res, temp)
		return
	}
	for i := 0; i <len(nums); i++ {
		if !isInSlice(path,nums[i]) {
			fmt.Println(nums[i])
			path = append(path, nums[i])
			backtrace(path,nums)
			path = path[:len(path)-1]
		}
	}
}

784. 字母大小写全排列

package question784

import "strings"

var res []string

func letterCasePermutation(s string) []string {
	res = []string{}
	path := ""
	backtrace(path, s, 0)
	return res
}

func backtrace(path string, s string, start int) {
	if len(path) == len(s) {
		res = append(res, path)
		return
	}
	ch := s[start]
	if ch >= 'a' && ch <= 'z' ||ch>='A'&&ch<='Z'{
		path += strings.ToUpper(string(ch))
		backtrace(path, s, start+1)
		path = path[:len(path)-1]
		path += strings.ToLower(string(ch))
		backtrace(path, s, start+1)
		path = path[:len(path)-1]
	} else {
		path += string(ch)
		backtrace(path, s, start+1)
	}
}

70. 爬楼梯

package question70


/*var cache []int = make([]int,100)
func climbStairs(n int) int {
	if cache[n-1]!=0 {
		return cache[n-1]
	}
	if n==1||n==2 {
		cache[n-1] = n
		return n
	}
	cache[n-1] = climbStairs(n-1)+climbStairs(n-2)
	return cache[n-1]
}*/

func climbStairs(n int) int {
	x,y,z :=0,0,1
	for i:=1;i<=n;i++ {
		x = y
		y = z
		z = x+y
	}
	return z
}

198. 打家劫舍

package question198

func max(x,y int) int {
	if x>y {
		return x
	}
	return y
}
func rob(nums []int) int {
	n := len(nums)
	if n==1 {
		return nums[0]
	}
	first,second := nums[0],max(nums[0],nums[1])

	for i:=3;i<=n;i++ {
		first,second = second,max(second,nums[i-1]+first)
	}
	return second
}

/*func rob(nums []int) int {
	n := len(nums)
	res := make([]int,n)
	for i:=1;i<=n;i++ {
		if i==1 {
			res[i-1] = nums[i-1]
		}else if i==2 {
			res[i-1] = max(nums[i-1],nums[i-2])
		}else{
			res[i-1] = max(res[i-2],res[i-3]+nums[i-1])
		}
	}
	return res[n-1]
}
*/

120. 三角形最小路径和

package question120

func min(x,y int)int  {
	if x>y {
		return y
	}
	return x
}
func minimumTotal(triangle [][]int) int {
	n := len(triangle)
	res := make([][]int, n)
	for i := 0; i < n; i++ {
		res[i] = make([]int, i+1)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < i+1; j++ {
			if i==0 {
				res[i][j] = triangle[i][j]
			}else if j==0 {
				res[i][j] = res[i-1][j]+triangle[i][j]
			}else if j==i{
				res[i][j] = res[i-1][j-1]+triangle[i][j]
			}else{
				res[i][j] = min(res[i-1][j],res[i-1][j-1])+triangle[i][j]
			}
		}
	}
	minElem := res[n-1][0]
	for i := 1; i <n ; i++ {
		if res[n-1][i]<minElem {
			minElem = res[n-1][i]
		}
	}
	return minElem
}

231. 2 的幂

package question231


func isPowerOfTwo(n int) bool {
	return (n>0)&&(n&(n-1)==0)
}
/*func isPowerOfTwo(n int) bool {
	if n==1 {
		return true
	}
	num := 1
	for num<=n {
		num = num<<1
	}
	if num==n {
		return true
	}
	return false
}*/

191. 位1的个数

package question191

func hammingWeight(num uint32) int {
	res := 0
	for ;num>0;num&=num-1 {
		res++
	}
	return res
}

/*func hammingWeight(num uint32) int {
	return strings.Count(strconv.FormatInt(int64(num),2),"1")
}*/

190. 颠倒二进制位

package question190


func reverseBits(n uint32) uint32 {
	n = (n>>16)|(n<<16)
	n = ((n&0xff00ff00)>>8)|((n&0x00ff00ff)<<8)
	n = ((n&0xf0f0f0f0)>>4)|((n&0x0f0f0f0f)<<4)
	n = ((n&0xcccccccc)>>2)|((n&0x33333333)<<2)
	n = ((n&0xaaaaaaaa)>>1)|((n&0x55555555)<<1)
	return n
}
/*func reverseBits(num uint32) uint32 {
	var res uint32 = 0
	for i:=0;i<32;i++ {
		res = res<<1|num&1
		num=num>>1
	}
	return res
}*/

136. 只出现一次的数字

package question136

func singleNumber(nums []int) int {
	var res int
	for _,v := range nums{
		res^=v
	}
	return res
}