# 前言

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.
* @return 	 	      true if current version is bad
*			          false if current version is good
*/
start,end := 1,n
for start <= end {
mid := start + (end-start)/2
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
}

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 {
for i:=0;i<n;i++ {
right = right.Next
}
for ;right!=nil;left=left.Next {
right = right.Next
}
left.Next = left.Next.Next
}

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

## 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
}
//迭代
var prev *ListNode
for curr!=nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}

//迭代
}
var mid,right *ListNode
right = mid.Next
for right!=nil{
mid = right
right = right.Next
}
return mid
}*/

//递归
}
//很重要，为了防止链表循环，在处理第一个节点的时候 防止循环
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
}

THE END