计算机 leetcode

leetcode

Posted by jabin on December 28, 2019

一、字符串

  1. 基本上都需要循环遍历，来解决
  2. 思路想清楚，再动手

1.1 最长公共前缀

// 查找最短的字符串
func getShortestStr(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    
    shortestStr := strs[0]
    
    // 遍历、替换
    for _, v:= range strs {
        if len(v) < len(shortestStr) {
            shortestStr = v
        }
    }
    
    return shortestStr
}

func longestCommonPrefix(strs []string) string {
    // 1. 查找最短字符串
    shortestStr := getShortestStr(strs)
    // 2. 遍历最短字符串
    for i, v := range shortestStr {
        
        // 3. 遍历字符串数组
        for _, str := range strs {
            // 4. 第一次出现字符不一致， 直接返回
            if str[i] != byte(v) {
                return shortestStr[0:i]
            }
        }
        
        
    }
    
    // 5. 返回最短字符串
    return shortestStr
}

1.2 罗马数字转整数

func romanToInt(s string) int {
    // 1. 定义罗马单字和数字映射map
    valueMap := map[byte]int {
        'I':1,
        'V':5,
        'X':10,
        'L':50,
        'C':100,
        'D':500,
        'M':1000,
    }
    
    num := 0  // 统计计数和
    // 2. 遍历罗马数字
    for i, v := range s {
        curNum := valueMap[byte(v)]
        // 3. 若当前数字>=下个数字或是最后一个了，加， 否则减
        if  i==len(s)-1 || curNum >= valueMap[s[i+1]] {
            num += curNum 
        } else {
            num -= curNum 
        }
                
    }
    
    return num
}

1.3 外观数列

func countAndSay(n int) string {
    // 1. 循环每一行
    // 2. 通过循环上一行，进行计数，得到下一行
    str := "1"
    for i:=1; i<n; i++ {
        tmp := ""
        lenStr := len(str)
        for j:=0; j<lenStr; j++ {
            count := 1
            for ; j+1<lenStr && str[j] == str[j+1]; {
                count++
                j++
            }

            
            tmp = tmp + strconv.Itoa(count) + string(str[j])
            //tmp = append(tmp, str[j])
        }

        str = tmp
    }

    return str
}

1.4 字符串中第一个唯一字符

func firstUniqChar(s string) int {
 	var charCntMap = make(map[rune]int, 0)
 	// 1. 对所有的字符进行计数，存进map
 	for _, v := range s {
 		if _, ok := charCntMap[v]; ok { // 若存在，则计数加1
 			charCntMap[v]++
        } else {  // 若不在， 则置为1
            charCntMap[v] = 1
        }
 	}
    
    
 	// 2. 遍历字符串， 找第一个计数为1
 	for i, v := range s {
        if charCntMap[v] == 1 {
            return i
        }
 	}

 	return -1
}

1.5 翻转字符串

func reverseString(s []byte)  {
	// 一个循环， 两个方向向中间移动，进行两两交换
	for i, j := 0, len(s)-1; i<j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	} 
}

1.6 验证回文串

func isPalindrome(s string) bool {
	// 1. 字符串预处理
	// 转成小写
	s = strings.ToLower(s)
	// 去除非数字Or字母的
	resStr := ""
	for _, v := range s {
		if (rune(v) >= 'a' && rune(v) <= 'z') || (rune(v) >= '0' && rune(v) <= '9') {
			resStr += string(v)
		}
	}
	// 2. 两边往中间遍历, 判断是否都相等
	for i, j:=0, len(resStr)-1; i<j; i,j = i+1, j-1 {
		if (resStr[i] != resStr[j]) {
			return false
		}
	}

	return true
}

1.7 有效的括号

// 配对，利用栈的先进后出
func isValid(s string) bool {
    // 栈，左括号进栈，右括号出栈，并且是否相匹配，最后判断是否空栈
    // 1. 定义左右括号的映射 和 栈
    bracketMap := map[rune]rune {
    	'}':'{',
    	']':'[',
    	')':'(',
    }
    
    stack := make([]rune, 0)

    // 2. 循环字符串
    for _, v := range s {
    	switch rune(v) {
            case '{', '(', '[':
                // 左括号都入栈
                stack = append(stack, rune(v))
            case '}', ')', ']':
                // 右括号判断是否是空栈， 或者是否和栈顶字符相等
                if len(stack) == 0 || bracketMap[rune(v)] != stack[len(stack)-1] {
                    return false
                }
                stack = stack[:len(stack)-1]
            default:
                return false
        }
    }

    // 3. 若栈不为空， 说明还有未匹配的， 返回false
    if (len(stack)>0) {
    	return false
    }

    return true

}

1.7 实现strStr

func strStr(haystack string, needle string) int {
	if len(needle) == 0 {
		return 0
	}
	// 1. 循环haystack， 若和needle的第一个字符一样，则遍历needle， 若不一样，则break，若都一样， 则返回i
	for i, v := range haystack {
		if v == rune(needle[0]) {
			j := i
			for _, v2 := range needle {
				if j> len(haystack)-1 || v2 != rune(haystack[j]) {
					break
				}
				j++
			}

			//2. 若遍历完了needle， 则找到了
			if len(needle) == j-i {
				return i
			}
		}
	}

	return -1   
}

1.8 最长回文子串 5

func isPalindrome(s string) bool {
	for i, j:=0, len(s)-1; i<j; i,j = i+1, j-1 {
		if (s[i] != s[j]) {
			return false
		}
	}

	return true
}

func longestPalindrome(s string) string {
    // 1. 从s的最大长度开始遍历，寻找满足的子回文串
    lenStatic := len(s)
    lenS := len(s)
    for lenS > 0 {
    	for i:=0; i<=lenStatic-lenS;i++ {
    		if isPalindrome(s[i:i+lenS]) {
    			return s[i:i+lenS]
    		}
    	}

    	lenS--
    }

    return ""
}


// 法二，中心位置扩展
func palindrome(s string, l int, r int) string {
    for l>=0 && r<len(s) && s[l]==s[r] {
        l--
        r++
    }
    
    return s[l+1:r]
}


func longestPalindrome(s string) string {
    if len(s) == 0 || len(s) == 1 {
        return s
    }
    maxSubStr := ""
    for i:=0; i<len(s)-1; i++ {
        
        oddSubStr := palindrome(s, i, i)
        evenSubStr := palindrome(s, i, i+1)
        tmpSubStr := ""
        if len(oddSubStr) > len(evenSubStr) {
            tmpSubStr = oddSubStr
        } else {
            tmpSubStr = evenSubStr
        }
   
        if len(tmpSubStr) > len(maxSubStr) {
            maxSubStr = tmpSubStr
        }
        
    }
    
    return maxSubStr    
}

1.9 无重复字符串的最长子串 – 滑动窗口 3

// 解1
func lengthOfLongestSubstring(s string) int {
    // 滑动窗口， 不定长问题
    // 1. 定义窗口的起始和长度
    start, window := 0, 0
    //fmt.Println(len([]rune(s)))
    // 2. 遍历
    for i:=0; i<len(s); i++ {
        // s[start:i], s[i](
        // 3. 找窗口起始到当前位置范围内是否有相同的字符
        pos := strings.Index(string(s[start:i]), string(s[i]))
        
        // 无， 则更新窗口长度
        if pos == -1 {
            if (i-start+1) > window {
                window = i-start+1
            }
        } else {  // 有，则更新窗口起始位置
            start = start + pos + 1
        }

    }

    return window
}

// 解2 标准滑动窗口
func Max(a int, b int) int {
    if a>b {
        return a
    }
    return b
}

func lengthOfLongestSubstring(s string) int {
    cntMap := make(map[byte]int, 0)
    
    left, right, max := 0, 0, 0
    for right < len(s) {
        // 无重复的， 窗口的右端位置为重复的
        if _, ok := cntMap[s[right]]; !ok {
            cntMap[s[right]]++
            right++
        } else {  
            for left < right { // 发现重复的元素，窗口左端右移
                if s[left] == s[right] {
                    delete(cntMap, s[left])
                    left++
                    break
                }
                delete(cntMap, s[left])
                left++
            }
        }
        max = Max(max, right-left)
    }
    
    return max
}

二、数组

2.1 买卖股票最佳时机

func maxProfit(prices []int) int {
	// 遍历每天的股票价格，统计收益，若收益小于0重置，否则判断当前迭代的收益是否大于当前最大收益，大则更新最大收益
	maxProfit := 0
	tmpProfit := 0

	// 1. 若只有一天的价格， 则返回0
	if len(prices) < 2 {
		return 0
	}

	// 2. 遍历股票价格
	for i:=1; i<len(prices); i++ {
		// 每天的收益
		dayProfit := prices[i] - prices[i-1]
		// 更新tmpProfit
		tmpProfit = tmpProfit + dayProfit

		// 3. 若tmpProfit<0了， 则重置为0， 不操作
		if tmpProfit < 0 {
			tmpProfit = 0
		}

		// 4. 若tmpProfit 大于max了， 则更新
		if tmpProfit > maxProfit {
			maxProfit = tmpProfit
		}
	}


	return maxProfit  
}

2.2 最长子序和

func maxSubArray(nums []int) int {
	// 遍历数组，贪婪算法
	maxSum := nums[0]
	tmpSum := 0
	// 1. 遍历数组
	for _, num range nums {
		// 2. 不管啥，直接要, 要完判断是否更新max
		tmpSum += num
		if tmpSum > maxSum {
			maxSum = tmpSum
		}

		// 3. 本来有0， 加了还少了。。重新来
		if tmpSum < 0 {
			tmpSum = 0
		}
	}

    return maxSum
}

2.3 两数之和

func twoSum(nums []int, target int) []int {
	// 一个循环， map记录当前值对应的下标，判断target减去当前遍历的下标的下标是否为空
	idxMap := make(map[int]int, 0)

	for i, v := range nums {
		if _, ok := idxMap[target-v]; ok {
   			return []int{i, idxMap[target-v]}
   		}
   		idxMap[v] = i
	}
   
  	return nil
}

2.4 合并两个有序数组

func merge(nums1 []int, m int, nums2 []int, n int)  {
    // 1、直接从最大的开始赋值
    i := m-1
    j := n-1
    k := m+n-1
    for i>=0 && j>=0 {
    	if nums1[i] > nums2[j] {
    		nums1[k] = nums1[i]
    		i--
    	} else {
    		nums1[k] = nums2[j]
    		j--
    	}

    	k--
    }

    // 2. 若nums2还有，则直接给num1最前面
    for j >= 0 {
    	nums1[k] = nums2[j]
    	j--
    	k--
    }
}

2.5 盛最多水的容器

func maxArea(height []int) int {
    max := 0
    tmp := 0

    i:=0
    j:= len(height)-1
    for i < j {
        if height[i] < height[j] {
            tmp = height[i] * (j-i)
            i++
        } else {
            tmp = height[j] * (j-i)
            j--
        }
        if tmp > max {
            max = tmp
        }
    }
    return max
}

2.6 三数之和

func threeSum(nums []int) [][]int {
    var result [][]int
    
    // 1. 排序、遍历数组， 三数去重
    // 2. 双指针计算两数之和， 两数去重
    sort.Ints(nums)
    for i:=0; i<len(nums); i++ {
    	// 三数去重
    	if i>0 && nums[i] == nums[i-1] {
    		continue
    	}

    	// 双指针
    	begin := i+1
    	end := len(nums)-1
    	target := -nums[i]

    	// 循环后续， 寻找两数之和
    	for begin < end {
    		// 找到了
    		if nums[begin] + nums[end] == target {
    			result = append(result, []int{nums[i], nums[begin], nums[end]})
    			begin++
    			end--

    			// 两数去重
    			for begin < end && nums[begin] == nums[begin-1] {
    				begin++
    			}

    			for begin < end && nums[end] == nums[end+1] {
    				end--
    			}

    		} else if nums[begin] + nums[end] < target {// 太小了，begin后移
    			begin++
    		} else {  // 太大， end 前移
    			end--
    		}

    	}

    }
    return result
}

2.7 1 比特与 2 比特字符

func isOneBitCharacter(bits []int) bool {
    i := 0
    //线性遍历
    for i<len(bits)-1 {
        if bits[i] == 1 {
            i += 2
        } else {
            i += 1
        }
    }
 
    // 若刚好遍历完，则最后一个是Onebit，否则不是
    if i == len(bits)-1 {
        return true
    } else {
        return false
    }  
}

2.8 数组形式的整数加法 989

func addToArrayForm(A []int, K int) []int {
    // 1. 倒序遍历数组，每个元素与K相加
    // 2. 取个位，append到结果数组; K更新为去个位的K
    // 3. 若数组遍历完，k还没，则需要继续遍历K
    // 4. 反转数组
    ret := make([]int, 0)
    i := len(A) - 1
    for i>=0 {
        tmp := K+A[i]
        ret = append(ret, tmp%10)

        K = tmp/10

        i--
    }

    for K>0 {
        ret = append(ret, K%10)
        K=K/10
    }

    result := make([]int, 0)
	for i:=len(ret)-1; i>=0; i--{
		result = append(result, ret[i])
	}

    return result
}

2.9 数组拆分1 561

// 一个2n长度数组，两两配对，得到n对， 每对取最小值，进行求和，求和结果最大值是多少？
import "sort"
func arrayPairSum(nums []int) int {
    // 差值最小， 则损失的值最小， 这样最后和最大
    sort.Ints(nums);  //快排
    sum := 0;
    for i := 0; i< len(nums); i+=2 {
        sum += nums[i];
    }

    return sum;
}

2.10 买卖股票的最佳时机 II 122

// 概述：一个数组代表第i天的股票市值arr[i], 允许多次交易，但必须一买一卖，求最后的最大收益
func maxProfit(prices []int) int {
    // 断线操作， 赚到每次的小波段， 一次循环
    max := 0
    for i:=1; i<len(prices); i++ {
        if prices[i]>prices[i-1] {
            max += prices[i] - prices[i-1]
        }
    }

    return max
}

2.11 存在重复元素 217

//要么两层循环，内存少点，cpu多点，要么一层循环，记录下遍历的过程
func containsDuplicate(nums []int) bool {
    cntMap := make(map[int]int, 0)

    for _, v := range nums {
        if cntMap[v] == 1 {
            return true
        } else {
            cntMap[v] = 1
        }
    }

    return false
}

2.12 存在重复元素II 219


func containsNearbyDuplicate(nums []int, k int) bool {
    posMap := make(map[int]int, 0)

    for i, v := range nums {
        if _,ok := posMap[v]; ok {
            if i-posMap[v] <= k {
                return true
            }
            // 存储当前遍历的位置
            posMap[v] = i
        } else {
            // 存储当前遍历的位置
            posMap[v] = i
        }
    }

    return false
}

2.13 存在重复元素III 220

func absVal(num int) int {
    if num < 0 {
        return -num
    }

    return num
}
func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
    for i:=0; i<len(nums)-1; i++ {
        for j:=i+1; j<len(nums); j++ {
            if absVal(nums[i]-nums[j])<=t && j-i<=k {
                return true
            }
        }
    }

    return false 
}

2.14 数组的度 697

import "fmt"

func findShortestSubArray(nums []int) int {
    // 1. 统计每个元素的出现的频数
    // 2. 存储每个元素出现的左右下标，用于计算子数组的长度
    // 3. 计算度
    // 4. 遍历每个元素出现的频数，找到和度相同的元素频数，对应的长度， 并返回最小值
    eleCnt := make(map[int]int, 0)
    leftIdx := make(map[int]int, 0)
    rightIdx := make(map[int]int, 0)

    for i, v := range nums {
        if _, ok := leftIdx[v]; ok {
            rightIdx[v] = i
        } else {
            leftIdx[v] = i
        }

        eleCnt[v]++
    }


    // for i, v := range eleCnt {
    //     fmt.Printf("%d, %d\n", i, v)
    // }
    degree := 0
    shortestLen := len(nums)
    for _, v := range eleCnt {
        if v>degree {
            degree = v
        }        
    }

    // fmt.Println(degree)

    for i, v := range eleCnt {
        if v == degree {
            curLen := 1
            if rightIdx[i] != 0 {
                curLen = rightIdx[i]-leftIdx[i]+1
            }
            
            // fmt.Println(curLen)
            if curLen < shortestLen {
                shortestLen = curLen
            } 
        }
    }
    

    return shortestLen
}

2.15 排序数组中查找元素的第一和最后一个位置

// 时间复杂度要求O(logn)  二分查找
func leftRange(nums []int, target int) int {
    left := 0
    right := len(nums) - 1 
    for left <= right {
        mid := (left + right)/2
        if nums[mid] > target {
            right = mid - 1    
        } else if nums[mid] < target {
            left = mid
        } else if nums[mid] == target { // 左边界，右往左缩，可举实例理解
            right = mid - 1
        }
    }

    if left > len(nums)-1 || nums[left] != target {
        return -1
    }
    return left
}

func rightRange(nums []int, target int) int {
    left := 0
    right := len(nums) - 1
    for left <= right {
        mid := (left + right)/2
        if nums[mid] > target {
            right = mid  
        } else if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] == target { //右边界，左往后缩
            left = mid + 1
        }
    }
    
    if right < 0 || nums[right] != target {
        return -1
    }

    return right
}

func searchRange(nums []int, target int) []int {
    // 1. 查找左边界
    left := leftRange(nums, target)
    
    // 2. 查找右边界
    right := rightRange(nums, target)
    
    return []int{left, right}
}

三、链表

3.1 反转链表 206

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    var cur *ListNode
    var tmp *ListNode

    cur = head


    for cur != nil {

    	tmp = cur.Next

    	cur.Next = pre
    	pre = cur
    	

    	cur = tmp
    }


    return pre
}

//递归解法：
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head.Next == nil {
        return head
    }
    last := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    
    return last
}

3.2 合并两个有序链表 21

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    } 

    if l2 == nil {
        return l1
    }

    var head *ListNode
    var tmpNode *ListNode
    // 开始
    if l1.Val <= l2.Val {
    	tmpNode = l1
    	l1 = l1.Next
    } else {
    	tmpNode = l2
    	l2 = l2.Next
    }

    head = tmpNode 

    // 循环两个链表， 比较， 加入tmpNode, 各自有自己的计数器
    for l1 != nil && l2 != nil {
    	if l1.Val <= l2.Val {
    		tmpNode.Next = l1
    		l1 = l1.Next
    	} else {
    		tmpNode.Next = l2
    		l2 = l2.Next
    	}

    	tmpNode = tmpNode.Next
    }

    // 还有剩下的，直接到后面
    if l1 != nil {
    	tmpNode.Next = l1
    }

    if l2 != nil {
    	tmpNode.Next = l2
    }

    return head

}

3.3 两数相加

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode{Val:0}

    tmp := head

    flag := false
    // 1. 遍历 l1, l2, 直到有一个穷尽了
    for l1 != nil && l2 != nil {
    	var sum int
    	if flag {
    		sum = l1.Val + l2.Val + 1
    	} else {
    		sum = l1.Val + l2.Val
    	
    	}

    	// 若大于10 ， 则置flag为true
    	if sum >= 10 {
    		flag = true
    		sum = sum - 10
    	} else {
    		flag = false
    	}
    	tmpNode := &ListNode {
    		Val : sum,
    	}
    	
    	tmp.Next = tmpNode

    	tmp = tmp.Next


    	// 迭代
        l1 = l1.Next
        l2 = l2.Next
    }

    // 2. 处理剩下的
    if l1 != nil {
    	tmp.Next = l1
    }

    if l2 != nil {
    	tmp.Next = l2
    }

    if l1 == nil && l2 == nil {
    	if flag {
    		tmp.Next = &ListNode {
    			Val:1,
    		}
    	}
    }

    return head.Next
}

3.4 反转链表的一部分 92

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

var nextNode *ListNode
func reverseN(head *ListNode, n int) *ListNode {
    if n==1 {
        nextNode = head.Next
        return head
    }
    last := reverseN(head.Next, n-1)
    head.Next.Next = head
    head.Next = nextNode
    return last
}


func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if m==1 {
        return reverseN(head, n)
    }
    
    head.Next = reverseBetween(head.Next, m-1, n-1)
    return head
}

3.5 环形链表II 142

// 已知链表有环，求环的起始位置
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    slow := head
    fast := head
    // 判断都已快指针来判断
    for fast!=nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if (slow == fast) {
            break
        }
    }
    
    // 判断都已快指针来判断
    if fast == nil || fast.Next == nil {
        return nil
    }
    
    slow = head
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }
    
    return slow
}

四、动态规划

4.1 零钱兑换问题 322

func coinChange(coins []int, amount int) int {
	//状态转移方程 dp[i] = mini{dp[i-coins[j]]+1| coins[j]属于coins}

	dp := make([]int, amount+1)
	dp[0] = 0

	for i:=1; i<=amount; i++ {
		dp[i] = amount+1
		for j:= 0; j<len(coins); j++ {
			if i<coins[j] {
				continue
			}
			if dp[i] > dp[i-coins[j]]+1 {
				dp[i] = dp[i-coins[j]]+1
			}
		}
	}

	if dp[amount] == amount+1 {
		return -1
	}

	return dp[amount]
}

4.2 接雨水 42

// 暴力解法
func Max(a int, b int) int {
    if a>b {
        return a
    }
    return b
}

func Min(a int, b int) int {
    if a<b {
        return a
    }
    return b
}

func trap(height []int) int {
    total := 0
    
    for i:=1; i<len(height)-1; i++ {
        l_max := 0
        for j:=0; j<=i; j++ {
            l_max = Max(l_max, height[j])
        }

        r_max := 0
        for k:=i; k<len(height); k++ {
        	r_max = Max(r_max, height[k])
        }
        

        total += Min(r_max, l_max)-height[i]
    }

    return total
}

// 备忘录
func Max(a int, b int) int {
    if a>b {
        return a
    }
    return b
}

func Min(a int, b int) int {
    if a<b {
        return a
    }
    return b
}

func trap(height []int) int {
    
    if len(height) == 0 {
        return 0
    }
    
    total := 0

    l_max := make(map[int]int, 0)
    r_max := make(map[int]int, 0)

    l_max[0] = height[0]
    r_max[len(height)-1] = height[len(height)-1]
    
    for i:=1; i<len(height); i++ {
    	l_max[i] = Max(l_max[i-1], height[i])
    }

    for i:=len(height)-2; i>=0; i-- {
    	r_max[i] = Max(r_max[i+1], height[i])
    }
    
    for i:=1; i<len(height)-1; i++ {
        total += Min(r_max[i], l_max[i])-height[i]
    }

    return total
}

五、树

5.1 二叉树的最近公共祖先

/**
 * Definition for TreeNode.
 * type TreeNode struct {
 *     Val int
 *     Left *ListNode
 *     Right *ListNode
 * }
 */
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// base case
    if root == nil {
        return nil
    }
    if root==p || root==q {
        return root
    }
    
    // 递归求左右子树 
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    // p和q分别找到了，则肯定是root
    if left!=nil && right!=nil {
        return root
    }
    
    // 都没有
    if left==nil && right==nil {
        return nil;
    }

    // 左子树找到了
    if left != nil {
        return left
    }
    
    if right != nil {
        return right
    }
    
    return nil
}

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

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */


func connectTwoNode(node1 *Node, node2 *Node) {
    if node1 == nil || node2 == nil {
        return 
    }
    
    node1.Next = node2
    
    connectTwoNode(node1.Left, node1.Right)
    connectTwoNode(node2.Left, node2.Right)
    
    connectTwoNode(node1.Right, node2.Left)
}

func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    
    connectTwoNode(root.Left, root.Right)
    
    return root
}

5.3 二叉树展开为链表 114

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode)  {
    // base case 
    if root == nil {
        return
    }
    
    flatten(root.Left)
    flatten(root.Right)
    
    right := root.Right
    left := root.Left
    
    root.Right = left
    root.Left = nil
    
    tmpNode := root
    for tmpNode.Right != nil {
        tmpNode = tmpNode.Right 
    }
    
    tmpNode.Right = right
}

5.4 构造最大二叉树 654

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    
    maxIdx := 0
    for i:=0; i<len(nums); i++ {
        if nums[i] > nums[maxIdx] {
            maxIdx = i
        }
    }
    
    root := &TreeNode {
        Val:nums[maxIdx],
    }
    root.Left = constructMaximumBinaryTree(nums[0:maxIdx])
    root.Right = constructMaximumBinaryTree(nums[maxIdx+1:len(nums)])
    
    return root
}

5.5 从前序与中序遍历序列中构造二叉树 105

// 此题还可变形为 从后序与中序遍历序列中构造二叉树  106  
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 || len(inorder) == 0 {
        return nil
    }
    
    
    root := &TreeNode {
        Val:preorder[0],
    }
    
    if len(preorder) == 1 || len(inorder) == 1 {
        return root
    }
    
    rootInorderIdx := 0
    for i:=0; i<len(inorder); i++ {
        if inorder[i] == root.Val {
            rootInorderIdx = i
            break
        }
    }
    
    println(rootInorderIdx)
    
    root.Left = buildTree(preorder[1:rootInorderIdx+1], inorder[0:rootInorderIdx])
    root.Right = buildTree(preorder[rootInorderIdx+1:], inorder[rootInorderIdx+1:])
    
    return root
}

5.6 二叉搜索树中第K小的元素 230

/**
* Definition for a binary tree node.
* type TreeNode struct {
	*     Val int
	*     Left *TreeNode
	*     Right *TreeNode
	* }
	*/

var rank int 
var	res int

func traverse(root *TreeNode, k int) {
	if root == nil {
		return 
	}
    // 二叉搜索树的特点， 进行中序遍历， 递增的
	traverse(root.Left, k)
	rank++
	if rank == k {
		res = root.Val
		return
	}

	traverse(root.Right, k)
}

func kthSmallest(root *TreeNode, k int) int {
    // 初始化！
	rank = 0
	res = 0

	traverse(root, k)

	return res
}

5.7 验证二叉搜索树 98

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func validBST(root *TreeNode, max *TreeNode, mini *TreeNode) bool {
	if root == nil {
		return true
	}

	if max!=nil && root.Val >= max.Val {
		return false
	}

	if mini!=nil && root.Val <= mini.Val {
		return false
	}

	return validBST(root.Left, root, mini) && validBST(root.Right, max, root)

}

func isValidBST(root *TreeNode) bool {
    return validBST(root, nil, nil)
}

5.8 删除二叉树中的节点 450

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func getMax(root *TreeNode)  *TreeNode {
	for root.Right != nil {
		root = root.Right
	}

	return root
}

func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}

	if root.Val==key {
		if root.Left == nil {
			return root.Right
		}
		if root.Right == nil {
			return root.Left
		}

		max := getMax(root.Left)
		root.Val = max.Val
		root.Left = deleteNode(root.Left, max.Val)

	}else if root.Val > key {
		root.Left = deleteNode(root.Left, key)
	} else if root.Val < key {
		root.Right = deleteNode(root.Right, key)   
	}

	return root
}

六、深度/广度优先（回溯/BFS）

//1. 回溯算法解题框架
for choice in choices
    remove choice in choices
    traces.add(choice)
    backtrace(choices, traces)
    traces.remove(choice)

//2. BFS 算法解题框架
func bfs(start Node, target Node) int {
    // 一些初始化， q核心数据结构， visisted访问过的节点， step遍历的步数
    var q []*Node{}
    var visited []*Node{}  // 走过的
    q = append(q, start)  //起点加入队列
    visited = append(visited, start)  
    int step = 0   // 起点到目标点的步数
    
    // 2， 循环一层层往下遍历
    while(len(q) != 0) {
        sz := len(q)
        for i:=0; i<sz; i++ {
            curNode := q[i]
            if curNode == target {  // 若找到了目标节点则返回
                return step
            }
            
            for x in curNode.arroundNodes {  // 把cur的所有相邻节点加入q
                if x not in visted {
                    q = append(q, x)
                    visited = append(visited, x)
                }
            }
        }
        q = q[sz:]  // 取下一层
        step++
    }
}

6.1 全排列问题（DFS） 46

var result [][]int

func in_array(val int, array []int) (exists bool, index int) {
	exists = false
	index = -1;

	for i, v := range array {
		if val == v {
			index = i
			exists = true
			return
		}
	}

	return
}

func backtrack(nums []int, tracks []int) {
    if len(tracks) == len(nums) {
            result = append(result, tracks)
            return
    }
    for _, num := range nums {
        if isExist, _ := in_array(num, tracks); isExist {
            continue
        }
        
        pre := tracks
        
        tracks = append(tracks, num)
        backtrack(nums, tracks)
        tracks = pre
    } 
}

func permute(nums []int) [][]int {
    result = make([][]int, 0)
    tracks := make([]int, 0)
    
    backtrack(nums, tracks)
    return result 
}

6.2 二叉树最小高度（BFS）

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    var q []*TreeNode
    q = append(q, root)
    step := 1
    
    for len(q) != 0 {
        sz := len(q)
        for i:=0; i<sz; i++ {
            currNode := q[i]
            
            if currNode == nil {
                continue
            }
            // 目标节点
            if currNode.Left == nil && currNode.Right == nil {
                return step
            }
            // cur相邻的节点都遍历
            q = append(q, currNode.Left)
            q = append(q, currNode.Right)
        }
        //取新增的
        q = q[sz:]
        step++
    }
    
    return step
}

七、设计题

7.1 LRU缓存机制

扩展：LFU 根据访问的频次进行淘汰

// 1. 操作： Get， set
// 2. 双向链表, 忽略首尾节点

// 定义双向链表的节点
type ListNode struct {
	Val int
	Key int
	Pre *ListNode
	Next *ListNode
}

type LRUCache struct {
	Cap int
	Len int 
	Map map[int]*ListNode  // 做一个映射， O(1)复杂度get
	Head *ListNode
	Tail *ListNode
}


func Constructor(capacity int) LRUCache {
	cache := LRUCache {
		Cap : capacity, 
		Len : 0,
		Map : make(map[int]*ListNode, capacity), 
		Head : &ListNode{}, 
		Tail : &ListNode{}, 
	}

	cache.Head.Next = cache.Tail
	cache.Tail.Pre = cache.Head

	return cache
}

// 指定的node, 加到队首
func (this *LRUCache) addToHead(listNode *ListNode) {
	listNode.Next = this.Head.Next
	this.Head.Next.Pre = listNode
	this.Head.Next = listNode
	listNode.Pre = this.Head

	this.Len++
}

// 删除
func (this *LRUCache) removeNode(listNode *ListNode) {
	listNode.Pre.Next = listNode.Next
	listNode.Next.Pre = listNode.Pre
	this.Len--
}

// 把指定的Key 移到队首, 
func (this *LRUCache) moveToHead(listNode *ListNode) {
	this.removeNode(listNode)
	this.addToHead(listNode)
}


func (this *LRUCache) Get(key int) int {
	// 1. 不存在， 返回-1
	// 2. key存在，返回，并放到队首
	if _, ok := this.Map[key]; !ok {
		return -1
	}

	this.moveToHead(this.Map[key])
	return this.Map[key].Val

}

func (this *LRUCache) Put(key int, value int)  {
	// 1. 存在， 移到队首
	// 2. 不存在容量够， 则加到队首
	// 2. 不存在容量不够， 则删除队尾的Key, 再加到队首
	if _, ok := this.Map[key]; ok {
		this.Map[key].Val = value
		this.moveToHead(this.Map[key])
		return 
	}

	node := &ListNode{Val:value, Key: key}

	if this.Len >= this.Cap {
		delete(this.Map, this.Tail.Pre.Key)
		this.removeNode(this.Tail.Pre)
	}
	// 加到Map
	this.Map[key] = node
	this.addToHead(node)
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

7.2 朋友圈时间线设计 355

// User类{id, followed, head(twitt时间线链表)}
// Twitt类{id, time, Next指针}

type Twitter struct {

}


/** Initialize your data structure here. */
func Constructor() Twitter {

}


/** Compose a new tweet. */
func (this *Twitter) PostTweet(userId int, tweetId int)  {

}


/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
func (this *Twitter) GetNewsFeed(userId int) []int {

}


/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
func (this *Twitter) Follow(followerId int, followeeId int)  {

}


/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
func (this *Twitter) Unfollow(followerId int, followeeId int)  {

}


/**
 * Your Twitter object will be instantiated and called as such:
 * obj := Constructor();
 * obj.PostTweet(userId,tweetId);
 * param_2 := obj.GetNewsFeed(userId);
 * obj.Follow(followerId,followeeId);
 * obj.Unfollow(followerId,followeeId);
 */

八、数学类型题

8.1 整数反转

func reverse(x int) int {
    result := 0
    // 循环移位, 由低位往高位构造整数
    for x != 0 {
    	result = result * 10 + x%10

    	x /= 10
    }

    if result<math.MaxInt32 && result>math.MinInt32 {
    	return result
    }

    return 0
}

8.2 回文数

// 法一， 转化成字符串，判断是否回文串
// 法二， 整数反转， 判断是否相等
func isPalindrome(x int) bool {
	// 1. 负数肯定不是
	// 2. 正数转化成字符
	if x<0 {
		return false
	}

	reversNum := reverse(x)

	if reversNum != x {
		return false
	}

	return true

}
CATALOG
    FEATURED TAGS
    计算机 git 分布式 一致性 go golang 微服务 docker c++ 投资理财 k8s 架构 ServiceMesh Istio knative istio infra eBPF 网络监控 Go 技术规范