数据结构与算法-刷题-Leetcode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func myAtoi(s string) int {
    s=strings.TrimSpace(s)
    if s==""{return 0}
    nagative:=false
    if s[0]=='-'||s[0]=='+'{
        if s[0]=='-'{nagative=true}
        s=s[1:]
    }
    ans:=0
    for _,v:=range s{
        if !unicode.IsDigit(v){break}
        ans=ans*10+int(v-'0')
        if ans>math.MaxInt32{break}
    }
    if nagative{ans=-ans}
    if ans>math.MaxInt32{ans=math.MaxInt32}
    if ans<math.MinInt32{ans=math.MinInt32}
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

func solveNQueens(n int) [][]string {
    colbool:=make([]bool,n)
    leftup:=make([]bool,2*n-1)
    rightup:=make([]bool,2*n-1)
    ans:=make([][]string,0)
    sb:=strings.Builder{}
    
    queue:=make([]int,n)
    var backtrack func(row int)
    backtrack=func(row int){
        //fmt.Println(colbool,leftup,rightup,queue)
        if row==n{
            anstmp:=make([]string,0)
            for _,v:=range queue{
                sb.Reset()
                for i:=0;i<n;i++{
                    if i!=v{
                        sb.WriteByte('.')
                    }else{sb.WriteByte('Q')}
                }
                anstmp=append(anstmp,sb.String())
            }
            ans=append(ans,anstmp)
            return
        }
        for col:=0;col<n;col++{
            lu,ru:=row-col+n-1,row+col
            if !(colbool[col]||leftup[lu]||rightup[ru]){
                colbool[col],leftup[lu],rightup[ru]=true,true,true
                queue[row]=col
                backtrack(row+1)
                colbool[col],leftup[lu],rightup[ru]=false,false,false
            }
        }
    }

    backtrack(0)

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func totalNQueens(n int) int {
    colbool:=make([]bool,n)
    leftup:=make([]bool,2*n-1)
    rightup:=make([]bool,2*n-1)
    ans:=0

    var backtrack func(row int)
    backtrack=func(row int){
        //fmt.Println(colbool,leftup,rightup)
        if row==n{
            ans++
            return
        }
        for col:=0;col<n;col++{
            lu,ru:=row-col+n-1,row+col
            if !(colbool[col]||leftup[lu]||rightup[ru]){
                colbool[col],leftup[lu],rightup[ru]=true,true,true
                backtrack(row+1)
                colbool[col],leftup[lu],rightup[ru]=false,false,false
            }
        }
    }

    backtrack(0)

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func lengthOfLastWord(s string) int {
    s=strings.TrimSpace(s)
    ans:=0
    for i:=len(s)-1;i>=0;i--{
        if unicode.IsLetter(rune(s[i])){
            ans++
        }else{break}
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func getPermutation(n int, k int) string {
    onpath:=make([]bool,n+1)
    ans:=make([]int,n)
    sep:=make([]int,n)
    tmp:=1
    for i,j:=n-1,1;i>=0;{
        tmp*=j
        sep[i]=tmp
        i--
        j++
    }
    //统一结果，-1过后k/v正好就是从左往右第i位取的第ans[i]个未使用数字
    k--
    for i,v:=range sep[1:]{
        ans[i]=k/v
        k-=ans[i]*v
    }
    //fmt.Println("sep",sep)
    sb:=strings.Builder{}
    for _,v:=range ans{
        tmp:=1
        for onpath[tmp]{tmp++}
        for v>0{
            tmp++
            for onpath[tmp]{tmp++}
            v--
        }
        onpath[tmp]=true
        sb.WriteString(strconv.Itoa(tmp))
    }

    //fmt.Println("ans",ans)

    return sb.String()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

visited:=make([]bool,n)

var dfs func(int)int
dfs=func(i int)(int,int){
  visited[i]=true
  //maxLen记录i作为根节点的最大深度,node记录最深的叶子节点
  maxLen,node:=0,i
  for _,j:=range graph[i]{
    if !visited[j]{
      tmp,tmpnode:=dfs(j)+1
      if maxLen<tmp{
        maxLen=tmp
        node=tmpnode
      }
    }
  }
  return maxLen,node
}

_,n1:=dfs(0)
diameter,n2:=dfs(n1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

visited:=make([]bool,n)
diameter:=0

var dfs func(int) int
dfs = func(i int) (int) {
  visited[i]=true
  maxLen=0
  for _, j := range graph[i] {
    if !visited[j] {
      tmp := dfs(j)+1
      //max即上面的工具函数，maxLen记录最深子树分支的深度，当前分支的深度，看加起来是否大于当前记录diameter
      diameter = max(diameter, maxLen+tmp)
      //更新maxLen记录
      maxLen = max(maxLen, tmp)
    }
  }
  return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func removeElement(nums []int, val int) int {
    right:=len(nums)-1
    for i,v:=range nums{
        if v==val{
            for right>=0&&nums[right]==val{right--}
            if i>right{break}
            nums[i],nums[right]=nums[right],v
        }
    }
    return right+1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func firstMissingPositive(nums []int) int {
    l:=len(nums)
    swap:=func(i,j int){nums[i],nums[j]=nums[j],nums[i]}
    for i,_:=range nums{
        for nums[i]>0&&nums[i]<=l&&
        nums[i]!=i+1&&nums[nums[i]-1]!=nums[i]{
            swap(i,nums[i]-1)
        }
    }

    for i,v:=range nums{
        if v!=i+1{return i+1}
    }
    return l+1
}

1
2

dp[i][0]=min(dp[i-1][0]* num[i], dp[i-1][1] *num[i], num[i])
dp[i][1]=max(dp[i-1][0]* num[i], dp[i-1][1] *num[i], num[i])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

func maxProduct(nums []int) int {
    l:=len(nums)
    memo:=make([][]int,l)
    for i,_ := range memo{
        memo[i]=make([]int,2)
        for j,_:=range memo[i]{
            memo[i][j]=math.MaxInt
        }
    }
    memo[0][0]=nums[0]
    memo[0][1]=nums[0]

    ans:=nums[0]
    var dp func(i,j int)int
    dp=func(i,j int)int{
        if memo[i][j]!=math.MaxInt{return memo[i][j]}
        a,b:=dp(i-1,0)*nums[i],dp(i-1,1)*nums[i]
        //fmt.Println(a,b,nums[i],ans)
        ans=max(a,b,nums[i],ans)
        memo[i][0]=min(a,b,nums[i])
        memo[i][1]=max(a,b,nums[i])
        return memo[i][j]
    }

    dp(l-1,1)
    //fmt.Println(memo)
    return ans
}

func max(s ...int)int{
    tmp:=math.MinInt
    for _,v:=range s{
        if tmp<v{tmp=v}
    }
    return tmp
}

func min(s ...int)int{
    tmp:=math.MaxInt
    for _,v:=range s{
        if tmp>v{tmp=v}
    }
    return tmp
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

type LRUCache struct {
    h int
    l *list.List
    m map[int]*list.Element
}

type Kv struct{
    k,v int
}


func Constructor(capacity int) LRUCache {
    return LRUCache{
        h:capacity,
        l:list.New(),
        m:map[int]*list.Element{},
    }
}


func (this *LRUCache) Get(key int) int {
    ans:=-1
    if e,has:=this.m[key];has{
        ans=e.Value.(*Kv).v
        this.l.MoveToFront(e)
    }
    return ans
}


func (this *LRUCache) Put(key int, value int)  {
    e,has:=this.m[key]
    if has{
        kv:=e.Value.(*Kv)
        this.l.MoveToFront(e)
        kv.v=value
    }else{
        t:=this.l.PushFront(&Kv{key,value})
        this.m[key]=t
        for this.l.Len()>this.h{
            r:=this.l.Back()
            rkv:=r.Value.(*Kv)
            delete(this.m,rkv.k)
            this.l.Remove(r)
        }
    }
    //this.show()
}

func (this *LRUCache) show(){
    fmt.Println(this.l.Len())
    for tmp:=this.l.Front();tmp!=nil;tmp=tmp.Next(){
        fmt.Print(tmp.Value.(*Kv)," ")
    }
    fmt.Println()
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func nextGreaterElements(nums []int) []int {
    l:=len(nums)
    tmp:=make([]int,l+l)
    copy(tmp,nums)
    copy(tmp[l:],nums)
    //fmt.Println(tmp)
    stack:=make([]int,0,l+l)
    ans:=make([]int,l+l)
    for i,v:=range tmp{
        for {
            ls:=len(stack)
            if ls==0{break}
            top:=stack[ls-1]
            if tmp[top]>=v{break}
            ans[top]=v
            stack=stack[:ls-1]
        }
        stack=append(stack,i)
    }
    for _,v:=range stack{
        ans[v]=-1
    }
    return ans[:l]
}

1
2

dp[i][j]=dp[i-1][j-1]+dp[i-1][j],s[i]==t[j]
         dp[i-1][j],s[i]!=s[j]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func numDistinct(s string, t string) int {
    ls,lt:=len(s),len(t)
    dp:=make([][]int,ls+1)
    for i,_:=range dp{
        dp[i]=make([]int,lt+1)
        dp[i][0]=1
    }
    for i,si:=range s{
        i=i+1
        for j,sj:=range t{
            j=j+1
            if si==sj{
                dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
            }else{
                dp[i][j]=dp[i-1][j]
            }
        }
    }
    return dp[ls][lt]
}

1
2
3
4
5

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max( 今天选择 rest,        今天选择 sell       )

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max( 今天选择 rest,         今天选择 buy         )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

func maxProfit(max_k int, prices []int) int {
    n := len(prices)
    if n <= 0 {
        return 0
    }

    // base case：
    // dp[-1][...][0] = dp[...][0][0] = 0
    // dp[-1][...][1] = dp[...][0][1] = -infinity
    dp := make([][][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([][]int, max_k+1)
        for k := 0; k <= max_k; k++ {
            dp[i][k] = make([]int, 2)
        }
    }

    // k = 0 时的 base case
    for i := 0; i < n; i++ {
        dp[i][0][1] = -1 << 31
        dp[i][0][0] = 0
    }

    for i := 0; i < n; i++ {
        for k := max_k; k >= 1; k-- {
            if i-1 == -1 {
                // 处理 i = -1 时的 base case
                dp[i][k][0] = 0
                dp[i][k][1] = -prices[i]
                continue
            }
            // 状态转移方程
            dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
            dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
        }
    }
    return dp[n-1][max_k][0]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    reverseK:=func (current *ListNode) (Start,Last *ListNode){
        Last=current
        var prev,next *ListNode=nil,nil
        for i:=0;i<k;i++{
            next=current.Next
            current.Next=prev
            prev=current
            current=next
        }
        Start=prev
        return
    }
    dummy:=&ListNode{Next:head}
    cur,prev:=head,dummy
    for cur!=nil{
        i:=0
        for ;i<k&&cur!=nil;i++{
            cur=cur.Next
        }
        if i==k{
            Start,Last:=reverseK(prev.Next)
            prev.Next=Start
            Last.Next=cur
            prev=Last
        }else{break}
    }
    return dummy.Next
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func countDigitOne(n int) int {
    s := strconv.Itoa(n)
    l := len(s)
    ans:=0
    for i,v:=range s{
        front,_:=strconv.Atoi(s[:i])
        back,_:=strconv.Atoi(s[i+1:])
        k:=l-i-1
        t:=1
        for i:=0;i<k;i++{
            t*=10
        }
        //fmt.Println(front,back,i,k,t)
        t1:=front*t
        t2:=0
        if v>'1'{
            t2=t
        }else if v=='1'{
            t2=back+1
        }
        ans+=t1+t2
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func removeDuplicates(nums []int) int {
    l,r:=0,0
    n:=len(nums)
    var tmp int
    tmpc:=0
    for r<n{
        if nums[r]!=tmp{
            tmp=nums[r]
            tmpc=0
        }
        if tmpc<2{
            nums[l]=nums[r]
            l++
        }
        tmpc++
        r++
    }
    return l
}

1
2
3
4
5
6
7

func rotate(nums []int, k int)  {
    f:=func(i,j int)bool{return i>j}
    n:=len(nums)
    sort.SliceStable(nums,f)
    sort.SliceStable(nums[:k%n],f)
    sort.SliceStable(nums[k%n:],f)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func jump(nums []int) int {
    n:=len(nums)
    memo:=make([]int,n)
    for i:=1;i<n;i++{
        memo[i]=math.MaxInt
    }
    //fmt.Println(dp)
    for i,v:=range nums{
        for j:=1;j<=v;j++{
            if i+j<n{
                //fmt.Println(i,j,dp[i+j],dp[i]+1)
                memo[i+j]=Min(memo[i+j],memo[i]+1)
            }
        }
    }
    return memo[n-1]
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func jump(nums []int) int {
    n:=len(nums)
    if n==1{return 0}
    step:=0
    max:=0
    cur:=0
    for i,v:=range nums{
        if i+v>max{
            max=i+v
        }
        if max>=n-1{
            step++
            break
        }
        if i==cur{
            cur=max
            step++
        }
    }
    return step
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func merge(nums1 []int, m int, nums2 []int, n int)  {
    nums1=nums1[:cap(nums1)]
    cur:=m+n-1
    c1,c2:=m-1,n-1
    for c1>=0&&c2>=0{
        if nums1[c1]>nums2[c2]{
            nums1[cur]=nums1[c1]
            c1--
        }else{
            nums1[cur]=nums2[c2]
            c2--
        }
        cur--
    }
    if c2>=0{copy(nums1,nums2[:c2+1])}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func smallestRepunitDivByK(k int) int {
    resid:=1%k
    l:=1
    m:=map[int]bool{}
    for resid!=0{
        m[resid]=true
        l++
        resid=(resid*10+1)%k
        if m[resid]{return -1}
    }
    return l
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func smallestRepunitDivByK(k int) int {
    if k%2 == 0 || k%5 == 0 {
        return -1
    }
    x := 1 % k
    for i := 1; ; i++ { // 一定有解
        if x == 0 {
            return i
        }
        x = (x*10 + 1) % k
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func queryString(s string, n int) bool {
    m:=map[string]bool{}
    l:=len(s)
    st:=strconv.FormatInt(int64(n),2)
    stl:=len(st)
    low:=1<<(stl-1)
    for i:=0;i<=l-stl;i++{
        m[s[i:i+stl]]=true
    }
    //fmt.Println(m)
    for i:=low;i<=n;i++{
        if !m[strconv.FormatInt(int64(i),2)]{return false}
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    n:=len(nums)
    absans:=math.MaxInt
    var ans int
    for i,v:=range nums{
        l,r:=i+1,n-1
        t:=target-v
        for l<r{
            tmp:=nums[l]+nums[r]
            cur:=tmp-t
            abscur:=abs(cur)
            if absans>abscur{
                absans=abscur
                ans=tmp+v
            }
            if cur>0{
                r--
            }else if cur<0{
                l++
            }else{return target}
        }
    }
    return ans
}

func abs(i int)int{
    if i<0{return -i}
    return i
}

1

dp[i]=max(i-j),i-1-j<dp[i-1],k∈[j+1,i-1],nums[k]&nums[i]==0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func longestNiceSubarray(nums []int) int {
    ans:=1
    n:=len(nums)
    dp:=make([]int,n)
    dp[0]=1
    for i:=1;i<n;i++{
        j:=i-1
        for ;i-1-j<dp[i-1];j--{
            if nums[i]&nums[j]!=0{break}
        }
        dp[i]=i-j
        if dp[i]>ans{
            ans=dp[i]
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func longestNiceSubarray(nums []int) int {
    n:=len(nums)
    l,r:=0,0
    cur:=0
    ans:=1
    for r<n{
        for l<r&&cur&nums[r]!=0{
            cur^=nums[l]
            l++
        }
        cur|=nums[r]
        r++
        count:=r-l
        if ans<count{ans=count}
    }
    return ans
}

1
2
3
4

dp[i]=dp[i-1]+2,word[i]<=word[i-1]
      插入2个字母
      dp[i-1]-1,word[i]>word[i-1]
      作为插入字母

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func addMinimum(word string) int {
    n:=len(word)
    dp:=make([]int,n)
    dp[0]=2
    for i:=1;i<n;i++{
        if word[i]<=word[i-1]{
            dp[i]=dp[i-1]+2
        }else{
            dp[i]=dp[i-1]-1
        }
    }
    return dp[n-1]
}

1
2
3
4
5
6
7
8

func addMinimum(word string) int {
    n:=len(word)
    tmp:=1
    for i:=1;i<n;i++{
        if word[i]<=word[i-1]{tmp++}
    }
    return 3*tmp-n
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func findLongestSubarray(array []string) []string {
    l:=len(array)
    presum:=make([]int,l+1)
    sum:=0
    for i,v:=range array{
        if unicode.IsDigit(rune(v[0])){
            sum++
        }else{sum--}
        presum[i+1]=sum
    }

    //fmt.Println(presum)
    
    ans:=math.MinInt
    var ansi,ansj int
    m:=make(map[int]int)
    for j,v:=range presum{
        if i,has:=m[v];has{
            if ans<j-i{
                ans=j-i
                ansi=i
                ansj=j
            }
        }else{m[v]=j}
    }

    //fmt.Println(ans,ansi,ansj)

    if ans==math.MinInt{return nil} 
    return array[ansi:ansj]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

func countSubgraphsForEachDiameter(n int, edges [][]int) []int {
    graph:=make([][]int,n)
    for i,_:=range graph{graph[i]=[]int{}}
    for _,e :=range edges{
        graph[e[0]-1]=append(graph[e[0]-1],e[1]-1)
        graph[e[1]-1]=append(graph[e[1]-1],e[0]-1)
    }
    ans:=make([]int,n)

    //fmt.Println(graph)

    for mask:=3;mask<(1<<n);mask++{
        //fmt.Println("mask:",mask)
        //至少得有2个节点
        if mask&(mask-1)==0{continue}
        diameter,onpath:=0,0
        var dfs func(int)int
        dfs=func(i int)int{
            //fmt.Println("dfs:",i)
            onpath|=1<<i
            ml:=0
            for _,j:=range graph[i]{
                if (onpath>>j)&1!=1&&(mask>>j)&1==1{
                    tmp:=dfs(j)+1
                    if diameter<tmp+ml{diameter=tmp+ml}
                    if ml<tmp{ml=tmp}
                }
            }
            return ml
        }

        start:=0
        //fmt.Println(onpath,mask)
        for mask&(1<<start)==0{start++}
        dfs(start) 
        //fmt.Println(mask,onpath)
        if onpath==mask{
            //fmt.Println(mask)
            ans[diameter]++
        }
    }

    return ans[1:]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func minNumberOfHours(initialEnergy int, initialExperience int, energy []int, experience []int) int {
    ans,tmp:=0,0
    for i,exp:=range experience{
        ene:=energy[i]
        //fmt.Println(initialExperience,initialEnergy,exp,ene)
        tmp=exp+1-initialExperience
        if tmp>0{
            ans+=tmp
            initialExperience+=tmp
        }
        tmp=ene+1-initialEnergy
        if tmp>0{
            ans+=tmp
            initialEnergy+=tmp
        }
        initialExperience+=exp
        initialEnergy-=ene
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func restoreMatrix(rowSum []int, colSum []int) [][]int {
    r,c:=len(rowSum),len(colSum)
    ans:=make([][]int,r)
    for i,_:=range ans{
        ans[i]=make([]int,c)
    }
    
    for row,rowslice :=range ans{
        for col,_:=range rowslice{
            ans[row][col]=Min(rowSum[row],colSum[col])
            rowSum[row]-=ans[row][col]
            colSum[col]-=ans[row][col]
        }
    }
    return ans
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

func maximalNetworkRank(n int, roads [][]int) int {
    degree:=make([]int,n)
    graph:=make([][]int,n)
    for i,_:=range graph{graph[i]=[]int{}}
    for _,e:=range roads{
        a,b:=e[0],e[1]
        graph[a]=append(graph[a],b)
        graph[b]=append(graph[b],a)
        degree[a]++
        degree[b]++
    }
    //fmt.Println(degree)
    maxdegree:=0
    for _,v:=range degree{
        if v>maxdegree{
            maxdegree=v
        }
    }
    maxdegree2:=0
    for i,v:=range degree{
        if v==maxdegree{
            tmp:=make([]int,n)
            copy(tmp,degree)
            for _,to:=range graph[i]{
                tmp[to]--
            }
            tmp[i]=0
            for _,vv:=range tmp{
                if maxdegree2<vv{
                    maxdegree2=vv
                }
            }
        }
    }
    return maxdegree+maxdegree2
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

func countSubarrays(nums []int, k int) int {
    l:=len(nums)
    
    var t int
    for i,v:=range nums{
        if v==k{
            t=i
            break
        }
    }
    
    ans:=1
    
    memo:=make([]int,t+1)
    memo[t]=0
    m:=make(map[int][]int,l)
    m[0]=[]int{t}
    for i:=t-1;i>=0;i--{
        if nums[i]>k{
            memo[i]=memo[i+1]+1
        }else{memo[i]=memo[i+1]-1}
        m[memo[i]]=append(m[memo[i]],i)
        if memo[i]==0||memo[i]==1{
            ans++
            //fmt.Println(i,t)
        }
    }
    //fmt.Println(memo)
    //fmt.Println(m)
    tmp:=0
    for j:=t+1;j<l;j++{
        if nums[j]>k{
            tmp++
        }else{tmp--}
        ans+=len(m[0-tmp])+len(m[1-tmp])
        //fmt.Println(tmp)
    }
    
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func countSubarrays(nums []int, k int) int {
    l:=len(nums)
    
    preSum:=make([]int,l)
    m:=make(map[int]int,l)
    flag:=false
    ans:=0
    
    tmp:=0
    for i,v:=range nums{
        if v>k{tmp++}else if v<k{tmp--}
        preSum[i]=tmp
        if v==k{flag=true}
        if flag{
            if tmp==0||tmp==1{ans++}
            //tmp-target=1||tmp-target=0
            ans+=m[tmp-1]+m[tmp]
        }else{m[tmp]++}
    }

    //fmt.Println(preSum)
    //fmt.Println(m)
    
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func answerQueries(nums []int, queries []int) []int {
    sort.Ints(nums)
    lq,ln:=len(queries),len(nums)
    preSum:=make([]int,ln)
    ans:=make([]int,lq)
    
    tmp:=0
    for i,v:=range nums{
        tmp+=v
        preSum[i]=tmp
    }
    
    bs:=func(t int)int{
        l,r,m:=0,ln-1,0
        for l<=r{
            m=l+(r-l)/2
            if preSum[m]>t{
                r=m-1
            }else if preSum[m]<t{
                l=m+1
            }else {r=m-1}
        }
        if l<ln&&preSum[l]==t{l++}
        return l
    }
    
    for i,v:=range queries{
        ans[i]=bs(v)
    }
    //fmt.Println(preSum)
    //fmt.Println(queries)
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func answerQueries(nums []int, queries []int) []int {
    sort.Ints(nums)
    n := len(nums)
    f := make([]int, n)
    f[0] = nums[0]
    for i := 1; i < n; i++ {
        f[i] = f[i-1] + nums[i]
    }
    ans := []int{}
    for _, q := range queries {
        idx := sort.SearchInts(f, q+1)
        ans = append(ans, idx)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func checkPalindromeFormation(a string, b string) bool {
    check:=func(s string,l,r int)bool{
        for l<r{
            if s[l]!=s[r]{
                return false
            }else{
                l++
                r--
            }
        }
        return true
    }
    
    findSplit:=func(a,b string)bool{
        l,r:=0,len(a)-1
        for l<r&&a[l]==b[r]{
            l++
            r--
        }
        //fmt.Println(a,l,r)
        return check(a,l,r)||check(b,l,r)
    }
    return findSplit(a,b)||findSplit(b,a)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

func findLexSmallestString(s string, a int, b int) string {
    m:=make(map[string]bool,0)
    ans:=[]byte(s)
    
    cmp:=func(a,b []byte)int{
        for i,_:=range a{
            if a[i]<b[i]{
                return 1
            }else if a[i]>b[i]{
                return -1
            }
        }
        return 0
    }
    
    adda:=func(bs []byte)([]byte){
        ret:=make([]byte,len(bs))
        for i,v:=range bs{
            ret[i]=v
            if i&1==1{
                ret[i]+=byte(a)
                if ret[i]>'9'{
                    ret[i]-='0'
                    ret[i]%=10
                    ret[i]+='0'
                }
            }
        }
        return ret
    }
    
    shift:=func(bs []byte)([]byte){
        ret:=make([]byte,0,len(bs))
        for _,v:=range bs[b:]{
            ret=append(ret,v)
        }
        for _,v:=range bs[:b]{
            ret=append(ret,v)
        }
        return ret
    }
    
    
    var dfs func([]byte)
    dfs=func(bs []byte){
        if m[string(bs)]{return}
        if cmp(ans,bs)==-1{
            ans=bs
        }
        m[string(bs)]=true
        dfs(adda(bs))
        dfs(shift(bs))
    }
    
    dfs([]byte(s))
    
    return string(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

func numDupDigitsAtMostN(n int) (ans int) {
	s := strconv.Itoa(n)
	m := len(s)
	dp := make([][1 << 10]int, m)
	for i := range dp {
		for j := range dp[i] {
			dp[i][j] = -1 // -1 表示没有计算过
		}
	}
	var f func(int, int, bool, bool) int
	f = func(i, mask int, isLimit, isNum bool) (res int) {
		if i == m {
			if isNum {
				return 1 // 得到了一个合法数字
			}
			return
		}
		if !isLimit && isNum {
			dv := &dp[i][mask]
			if *dv >= 0 {
				return *dv
			}
			defer func() { *dv = res }()
		}
		if !isNum { // 可以跳过当前数位
			res += f(i+1, mask, false, false)
		}
		d := 0
		if !isNum {
			d = 1 // 如果前面没有填数字，必须从 1 开始（因为不能有前导零）
		}
		up := 9
		if isLimit {
			up = int(s[i] - '0') // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
		}
		for ; d <= up; d++ { // 枚举要填入的数字 d
			if mask>>d&1 == 0 { // d 不在 mask 中
				res += f(i+1, mask|1<<d, isLimit && d == up, true)
			}
		}
		return
	}
	return n - f(0, 0, true, false)
}

1
2
3

func convertTemperature(celsius float64) []float64 {
    return []float64{celsius+273.15,celsius*1.8+32}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func bestTeamScore(scores []int, ages []int) int {
    type pair struct{age,score int}
    l:=len(scores)
    s:=make([]pair,0,l)
    for i,v:=range scores{
        s=append(s,pair{ages[i],v})
    }
    sort.Slice(s,func (i,j int)bool{
        if s[i].age<s[j].age{
            return true
        }else if s[i].age==s[j].age{
            if s[i].score<s[j].score{
                return true
            }
        }
        return false
    })
    //fmt.Println(s)

    ans:=0
    memo:=make([]int,l)
    for i,vi:=range s{
        tmp:=0
        for j,vj:=range s[:i]{
            if vi.score>=vj.score&&tmp<=memo[j]{tmp=memo[j]}
        }
        memo[i]=tmp+vi.score
        if ans<memo[i]{ans=memo[i]}
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func checkArithmeticSubarrays(nums []int, l []int, r []int) []bool {
    ans:=make([]bool,len(l))
    
    check:=func(nums []int)bool{
        l:=len(nums)
        max:=math.MinInt
        min:=math.MaxInt
        m:=map[int]bool{}
        for _,v:=range nums{
            if min>v{min=v}
            if max<v{max=v}
            m[v]=true
        }
        sep:=(max-min)/(l-1)
        if min+sep*(l-1)!=max{return false}
        for tmp:=min+sep;tmp<max;tmp+=sep{
            if _,has:=m[tmp];!has{return false}
        }
        return true
    }
    for i,_:=range l{
        ans[i]=check(nums[l[i]:r[i]+1])
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

type m map[byte]*m

type StreamChecker struct {
    s []byte
    trie *m
}


func Constructor(words []string) StreamChecker {
    ret:=StreamChecker{}
    ret.trie=&m{}
    for _,s:=range words{
        tmp:=ret.trie
        for i:=len(s)-1;i>=0;i--{
            v:=s[i]
            if _,has:=(*tmp)[v];!has{
                (*tmp)[v]=&m{}
            }
            tmp=(*tmp)[v]
        }
        (*tmp)['0']=&m{}
    }
    return ret
}


func (this *StreamChecker) Query(letter byte) bool {
    this.s=append(this.s,letter)
    tmp:=this.trie
    for i:=len(this.s)-1;i>=0;i--{
        v:=this.s[i]
        if next,has:=(*tmp)[v];has{
            tmp=next
            if (*tmp)['0']!=nil{
                return true
            }
        }else{return false}
    }
    return false
}


/**
 * Your StreamChecker object will be instantiated and called as such:
 * obj := Constructor(words);
 * param_1 := obj.Query(letter);
 */

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func findLengthOfShortestSubarray(arr []int) int {
    l:=len(arr)
    i,j:=1,l-2
    for i<l{
        if arr[i]<arr[i-1]{break}
        i++
    }
    if i==l{return 0}
    for j>0{
        if arr[j]>arr[j+1]{break}
        j--
    }
    left,right:=-1,j+1
    //fmt.Println(left,right)
    ans:=math.MaxInt
    for left<i{
        for right<l&&left>=0&&arr[left]>arr[right]{
            right++
        }
        if ans>right-left-1{ans=right-left-1}
        left++
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func findSubarrays(nums []int) bool {
    l:=len(nums)
    presum:=make([]int,l+1)
    tmp:=0
    for i,_:=range presum[1:]{
        tmp+=nums[i]
        presum[i+1]=tmp
    }

    //fmt.Println(presum)

    m:=map[int]bool{}
    for i,vl:=range presum[:l-1]{
        vr:=presum[i+2]
        if m[vr-vl]{return true}
        m[vr-vl]=true
    }
    return false
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func countSubstrings(s string, t string) int {
    ls,lt:=len(s),len(t)
    ans:=0
    for i:=0;i<ls;i++{
        for j:=0;j<lt;j++{
            flag:=false
            for k:=0;i+k<ls&&j+k<lt;k++{
                if s[i+k]!=t[j+k]{
                    if flag{break}
                    flag=true
                }
                if flag{ans++}
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

func shortestCommonSupersequence(str1 string, str2 string) string {
    //预处理，设置memo数组和memopre数组
    l1,l2:=len(str1),len(str2)
    memo:=make([][]int,l1)
    for i,_:=range memo{
        memo[i]=make([]int,l2)
        for j,_:=range memo[i]{
            memo[i][j]=-1
        }
    }
    memopre:=make([][][]int,l1)
    for i,_:=range memopre{
        memopre[i]=make([][]int,l2)
    }
    
    //basecase
    if str1[0]==str2[0]{
        memo[0][0]=1
        memopre[0][0]=[]int{-1,-1}
    }else{
        memo[0][0]=0
        memopre[0][0]=[]int{-1,0}
    }
    
    //dp函数遍历
    var dp func(i,j int)int
    dp=func(i,j int)int{
        if i<0||j<0{return 0}
        if memo[i][j]!=-1{
            return memo[i][j]
        }
        
        if str1[i]==str2[j]{
            memo[i][j]=dp(i-1,j-1)+1
            memopre[i][j]=[]int{i-1,j-1}
        }else{
            i1j:=dp(i-1,j)
            ij1:=dp(i,j-1)
            max,maxi,maxj:=i1j,i-1,j
            if i1j<ij1{
                max,maxi,maxj=ij1,i,j-1
            }
            memo[i][j]=max
            memopre[i][j]=[]int{maxi,maxj}
        }
        return memo[i][j]
    }
    
    //求解
    dp(l1-1,l2-1)
    
    //fmt.Println(memo)
    //fmt.Println(memopre)
    
    //构造答案
    b:=strings.Builder{}
    i,j:=l1-1,l2-1
    for i>=0&&j>=0{
        if memopre[i][j][0]==i{
            b.WriteByte(str2[j])
        }else{
            b.WriteByte(str1[i])
        }
        i,j=memopre[i][j][0],memopre[i][j][1]
    }
    for i>=0{
        b.WriteByte(str1[i])
        i--
    }
    for j>=0{
        b.WriteByte(str2[j])
        j--
    }
    ansr:=b.String()
    b.Reset()
    for i=len(ansr)-1;i>=0;i--{
        b.WriteByte(ansr[i])
    }
    return b.String()
}

1

dp[i][j]=sum(dp[i-1][k-1]),i>1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func countVowelStrings(n int) int {
    dp:=make([][]int,n+1)
    for i,_:=range dp{
        dp[i]=make([]int,5)
    }
    for j,_:=range dp[1]{dp[1][j]=1}
    for i:=2;i<=n;i++{
        tmp:=0
        for j,_:=range dp[i]{
            tmp+=dp[i-1][j]
            dp[i][j]=tmp
        }
    }
    
    ans:=0
    for _,v:=range dp[n]{ans+=v}
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func maxWidthOfVerticalArea(points [][]int) int {
    s:=make([]int,0)
    for _,v :=range points{
        s=append(s,v[0])
    }
    sort.Ints(s)
    ans:=0
    for i:=1;i<len(s);i++{
        ans=max(ans,s[i]-s[i-1])
    }
    return ans
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func arithmeticTriplets(nums []int, diff int) int {
    l:=len(nums)
    ans:=0
    m:=make(map[int]int,l)
    for _,v:=range nums{
        m[v]++
    }
    for j:=1;j<l-1;j++{
        v:=nums[j]
        ans+=m[v-diff]*m[v+diff]
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

func maskPII(s string) string {
    ans:=strings.Builder{}
    email,_:=regexp.Compile(`^(\w+)((?i)@\w+\.\w+)$`)
    ss:=email.FindStringSubmatch(s)
    //fmt.Println(ss)
    if len(ss)>0{
        ans.WriteRune(unicode.ToLower(rune(ss[1][0])))
        ans.WriteString("*****")
        ans.WriteRune(unicode.ToLower(rune(ss[1][len(ss[1])-1])))
        ans.WriteString(strings.ToLower(ss[2]))
    }else{
        tmp:=strings.Builder{}
        for _,v:=range s{
            if unicode.IsDigit(v){
                tmp.WriteRune(v)
            }
        }
        t:=tmp.String()
        n:=len(t)
        if n>10{
            ans.WriteRune('+')
            for n>10{
                ans.WriteRune('*')
                n--
            }
            ans.WriteRune('-')
        }
        ans.WriteString("***-***-")
        ans.WriteString(t[len(t)-4:])
    }
    return ans.String()
}

1
2

dp[i][j]=min(dp[i][k]+dp[k][j])+values[i] * values[k] * values[j],k属于(i,j)
         0,j-i<=1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func minScoreTriangulation(values []int) int {
    l:=len(values)
    if l<3{return 0}
    memo :=make([][]int,l)
    for i,_:=range memo{
        memo[i]=make([]int,l)
    }
    
    var dp func(i,j int)int
    dp=func(i,j int)int{
        if memo[i][j]!=0{
            return memo[i][j]
        }
        min:=math.MaxInt
        for k:=i+1;k<j;k++{
            part1,part3:=0,0
            part2:=values[i]*values[j]*
                 values[k]
            if k-i>1{part1=dp(i,k)}
            if j-k>1{part3=dp(k,j)}
            tmp:=part1+part2+part3
            if min>tmp{min=tmp}
        }
        memo[i][j]=min
        return memo[i][j]
    }
    return dp(0,l-1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func prevPermOpt1(arr []int) []int {
    l:=len(arr)
    var i,j int
    flag:=false
    for i=l-2;i>=0;i--{
        if arr[i]>arr[i+1]{
            flag=true
            for j=i+1;j<l;j++{
                if arr[j]>=arr[i]{
                    break
                }
            }
            j--
            // 找最左元素
            for arr[j]==arr[j-1]{j--}
            break
        }
    }
    if flag{
        arr[i],arr[j]=arr[j],arr[i]
    }
    return arr
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

func mergeStones(stones []int, k int) int {
    n := len(stones)
    if (n-1)%(k-1) != 0 {
        return -1
    }

    d := make([][][]int, n)
    for i := range d {
        d[i] = make([][]int, n)
        for j := range d[i] {
            d[i][j] = make([]int, k+1)
            for k := range d[i][j] {
                d[i][j][k] = 1e9
            }
        }
    }
    sum := make([]int, n+1)
    for i, s := 0, 0; i < n; i++ {
        d[i][i][1] = 0
        s += stones[i]
        sum[i+1] = s
    }

    for len := 2; len <= n; len++ {
        for l := 0; l < n && l+len-1 < n; l++ {
            r := l + len - 1
            for t := 2; t <= k; t++ {
                for p := l; p < r; p += k - 1 {
                    d[l][r][t] = min(d[l][r][t], d[l][p][1]+d[p+1][r][t-1])
                }
            }
            d[l][r][1] = min(d[l][r][1], d[l][r][k]+sum[r+1]-sum[l])
        }
    }
    return d[0][n-1][1]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func mergeStones(stones []int, k int) int {
    l:=len(stones)
    memo:=make([][][]int,l)
    for i,_ :=range memo{
        memo[i]=make([][]int,l)
        for j,_:=range memo[i]{
            memo[i][j]=make([]int,k+1)
            memo[i][i][1]=stones[i]
        }
    }
    presum:=make([]int,l+1)
    tmp:=0
    for i,v:=range stones{
        tmp+=v
        presum[i+1]=tmp
    }

    var dp func(i,j,k int)int
    dp=func(i,j,k int)int{
        if memo[i][j][k]!=0{return memo[i][j][k]}
        if j-i+1<k{return math.MaxInt}
        cost:=presum[j+1]-presum[i]
        min:=math.MaxInt
        for t:=i;t<=j-k;t++{
            tmp:=dp(i,t,1)
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func commonFactors(a int, b int) int {
    g:=gcd(a,b)
    ans:=0
    for i:=1;i<=g;i++{
        if a%i==0&&b%i==0{ans++}
    }
    return ans
}

func gcd(a,b int)int{
    for a!=0{
        a,b=b%a,a
    }
    return b
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

func numMovesStonesII(stones []int) []int {
    sort.Ints(stones)
    l:=len(stones)
    max:=Max(stones[l-1]-stones[1],stones[l-2]-stones[0])-(l-2)
    if stones[l-1]-stones[0]==l-1{return []int{0,0}}
    min,curcount:=math.MaxInt,0
    left,right:=0,0
    fmt.Println(stones)
    for right<l{
        curcount++
        right++
        for left<right&&stones[left]<=stones[right-1]-l{
            curcount--
            left++ 
        }
        tmp:=l-curcount
        if curcount==l-1&&
            stones[right-1]-stones[left]==curcount-1{tmp++}
        //fmt.Println(left,right,tmp,min)
        min=Min(tmp,min)
    }
    return []int{min,max}
}

func Max(s ...int)int{
    tmp:=math.MinInt
    for _,v:=range s{
        if tmp<v{tmp=v}
    }
    return tmp
}

func Min(s ...int)int{
    tmp:=math.MaxInt
    for _,v:=range s{
        if tmp>v{tmp=v}
    }
    return tmp
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxAncestorDiff(root *TreeNode) int {
    ans:=math.MinInt
    var dfs func(root *TreeNode)(min,max int)
    dfs=func(root *TreeNode)(min,max int){
        if root==nil{return math.MaxInt,math.MinInt}
        lmin,lmax:=dfs(root.Left)
        if lmin==math.MaxInt{
            lmin=root.Val
            lmax=root.Val
        }
        rmin,rmax:=dfs(root.Right)
        if rmin==math.MaxInt{
            rmin=root.Val
            rmax=root.Val
        }
        min=Min(lmin,rmin,root.Val)
        max=Max(lmax,rmax,root.Val)
        ans=Max(abs(root.Val-min),abs(root.Val-max),ans)
        return
    }
    
    dfs(root)
    return ans
}

func abs(i int)int{
  if i<0{i=-i}
  return i
}

func Max(s ...int)int{
    tmp:=math.MinInt
    for _,v:=range s{
        if tmp<v{tmp=v}
    }
    return tmp
}

func Min(s ...int)int{
    tmp:=math.MaxInt
    for _,v:=range s{
        if tmp>v{tmp=v}
    }
    return tmp
}