leetcode困难题

找到矩阵中的好子集

解：
答案至多选取两行矩阵。
分析：
选取一行矩阵时，floor(c/2)=0，那么必须全为0才能满足。
选取两行矩阵时，floor(c/2)=1，同一列元素不能都是1，也就是相&为0
选取三行矩阵时，floor(c/2)=1，去掉一列后，等同于两行的情况
选取四行时，floor(c/2)=2，假如上述都没有答案：
选取四行中1最少的一行来分析：
1.这一行为10……0，因为上述<4行时都不成立，所以2行时任意两行都不能相&为0，所以其他行第一列必须是1，第一列相加为4，不满足要求
2.这一行为11……0，第二行为10……，第三行为01……为了让第二行与第三行相&不为0，必须在后边的一列都为1，第四行为了与第二行和第三行相&不为0，必须拿出一列使得其与第一行、第二行和第三行都为1，这样算起来就需要6列数据，而题目所说列数小于等于5，所以不满足条件
选取超过四行时，类似方法证明答案不存在

func goodSubsetofBinaryMatrix(grid [][]int) []int {
	n := len(grid)
	if n == 0 {
		return nil
	}
	num := make(map[int]int, n)
	for i, row := range grid {
		mask := 0
		for j, v := range row {
			mask |= v << j
		}
		num[mask] = i
	}
	if v, ok := num[0]; ok {
		return []int{v}
	}
	for i, v := range num {
		for j, v2 := range num {
			if i&j == 0 {
				if v < v2 {
					return []int{v, v2}
				}
				return []int{v2, v}
			}
		}
	}
	return nil
}

最长合法子字符串的长度

func longestValidSubstring(word string, forbidden []string) int {
	n := len(word)
	if n == 0 {
		return -1
	}
	vis := make(map[string]struct{}, len(forbidden))
	for _, v := range forbidden {
		vis[v] = struct{}{}
	}
	l := 0
	ans := 0
	for i := 0; i < n; i++ {
		for j := i; j >= l && j >= i-10; j-- {
			if _, ok := vis[word[j:i+1]]; ok {
				l = j + 1
				break
			}
		}
		if i-l+1 > ans {
			ans = i - l + 1
		}
	}
	return ans
}

情侣牵手

var f []int

func fin(x int) int {
	if x != f[x] {
		f[x] = fin(f[x])
	}
	return f[x]
}

func union(x, y int) {
	fx, fy := fin(x), fin(y)
	if fx < fy {
		f[fy] = fx
	} else {
		f[fy] = fx
	}
}

func minSwapsCouples(row []int) int {
	n := len(row)
	f = make([]int, n/2)
	for i := 0; i < n/2; i++ {
		f[i] = i
	}
	for i := 0; i < n; i += 2 {
		union(row[i]/2, row[i+1]/2)
	}
	cnt := 0
	for i := 0; i < n/2; i++ {
		if f[i] == i {
			cnt++
		}
	}
	return n/2 - cnt
}

我们将 N 对情侣看做图中的 N 个节点；对于每对相邻的位置，如果是第 i 对与第 j 对坐在了一起，则在 i号节点与 j 号节点之间连接一条边，代表需要交换这两对情侣的位置。如果图中形成了一个大小为 k 的环：i→j→k→…→l→i 则我们沿着环的方向，先交换i，j 的位置，再交换 j，k 的位置，以此类推。在进行了 k−1 次交换后，这 k 对情侣就都能够彼此牵手了。

故我们只需要利用并查集求出图中的每个连通分量；对于每个连通分量而言，其大小减 111 就是需要交换的次数。

三个无重叠子数组的最大和

func maxSumOfThreeSubarrays(nums []int, k int) []int {
	sum1, sum2, sum3 := 0, 0, 0
	maxSum1, maxSum2, maxSum3 := 0, 0, 0
	m1_id := 0
	m2_id1, m2_id2 := 0, 0
	m3_id1, m3_id2, m3_id3 := 0, 0, 0
	for i := 2 * k; i < len(nums); i++ {
		sum1 += nums[i-2*k]
		sum2 += nums[i-k]
		sum3 += nums[i]
		if i >= 3*k-1 {
			if sum1 > maxSum1 {
				maxSum1 = sum1
				m1_id = i - 3*k + 1
			}
			if sum2+maxSum1 > maxSum2 {
				maxSum2 = sum2 + maxSum1
				m2_id1, m2_id2 = m1_id, i-2*k+1
			}
			if sum3+maxSum2 > maxSum3 {
				maxSum3 = sum3 + maxSum2
				m3_id1, m3_id2, m3_id3 = m2_id1, m2_id2, i-k+1
			}
			sum1 -= nums[i-3*k+1]
			sum2 -= nums[i-2*k+1]
			sum3 -= nums[i-k+1]
		}
	}
	return []int{m3_id1, m3_id2, m3_id3}
}

时间复杂度：O(n)
空间复杂度：O(n)

思想：滑动数组+贪心

数字1的个数

func digitOneInNumber(num int) int {
    ans:=0
    bitCount:=1
    low,cur,heigh:=0,num%10,num/10
    for cur>0||heigh>0{
        if cur==0{
            ans+=heigh*bitCount
        }else if cur==1{
            ans+=heigh*bitCount+low+1
        }else{
            ans+=(heigh+1)*bitCount
        }
        low+=cur*bitCount
        bitCount*=10
        cur=heigh%10
        heigh=heigh/10
    }
    return ans
}

将数字按照位分为前半段、当前位和后半段，然后分别讨论

滑动窗口的最大值

func maxInWindows( num []int ,  size int ) []int {
    // write code here
    if size==0{
        return nil
    }
    stack:=[]int{}
    ans:=[]int{}
    for i:=0;i<len(num);i++{
        for len(stack)>0&&num[stack[len(stack)-1]]<num[i]{
            stack=stack[:len(stack)-1]
        }
        stack = append(stack, i)
        for len(stack)>=0&&stack[0]+size-1<i{
            stack=stack[1:]
        }
        if i>=size-1{
        ans=append(ans, num[stack[0]])
        }
    }
    return ans
}

维护双端单调递减的队列。当前的num比队列后面的值大时，后面的值就没有存在的价值，因为现在的值比它大，也比它晚在滑动窗口中淘汰。依次从后往前淘汰掉值，然后再从头往前淘汰掉应该从滑动窗口中删除的值。最后头部的一定是最大值。如果当前的num比队列中的小，则直接放入到队列中，因为虽然它小，但是它新，可能会比大的晚淘汰。

简易计算器

func calculate(s string) int {
    stack:=[]int{1}
    ans:=0
    opt:=1
    var cur int
    for cur<len(s){
        switch s[cur]{
            case ' ':
                cur++
            case '+':
                opt=stack[len(stack)-1]
                cur++
            case '-':
                opt=-stack[len(stack)-1]
                cur++
            case '(':
                stack=append(stack,opt)
                cur++
            case ')':
                stack=stack[:len(stack)-1]
                cur++
            default:
                tmp:=0
                for cur<len(s)&&s[cur]>='0'&&s[cur]<='9'{
                    tmp=tmp*10+int(s[cur]-'0')
                    cur++
                }
                ans+=opt*tmp
        }
    }
    return ans
}

时间复杂度：O(n)
空间复杂度：O(n)

记录数字前面的符号，+就是1，-就是-1，然后数字乘以前面的符号就是它所贡献的值。
对于遇到（），我们把（之前的那个符号压栈，括号里面的符号要根据栈中最后一个符号来决定，-就是取当前符号数的相反数，+就是取当前符号数。

单词搜索

type Tire struct{
    end string
    next [26]*Tire
}

func (t *Tire)Insert(s string){
    cur:=t
    for _,v:=range s{
        if cur.next[v-'a']==nil{
            cur.next[v-'a']=&Tire{}
        }
        cur=cur.next[v-'a']
    }
    cur.end=s
}

func findWords(board [][]byte, words []string) []string {
    m:=len(board)
    if m==0{
        return nil
    }
    n:=len(board[0])
    if n==0{
        return nil
    }
    t:=&Tire{}
    for _,v:=range words{
        t.Insert(v)
    }
    ans:=[]string{}
    pos:=[4][2]int{{-1,0},{0,-1},{0,1},{1,0}}
    vis:=make([][]bool,m)
    for i:=0;i<m;i++{
        vis[i]=make([]bool,n)
    }
    var dfs func(x,y int,cur *Tire)
    dfs=func(x,y int,cur *Tire){
        if cur==nil{
            return
        }
        if len(cur.end)!=0{
            ans=append(ans,cur.end)
            cur.end=""
        }
        vis[x][y]=true
        for i:=0;i<4;i++{
            xx,yy:=x+pos[i][0],y+pos[i][1]
            if xx>=m||yy>=n||xx<0||yy<0{
                continue
            }
            if vis[xx][yy]{
                continue
            }
            dfs(xx,yy,cur.next[board[xx][yy]-'a'])
        }
        vis[x][y]=false
        return 
    }
    for i:=0;i<m;i++{
        for j:=0;j<n;j++{
            if t.next[board[i][j]-'a']!=nil{
             dfs(i,j,t.next[board[i][j]-'a'])
            }
        }
    }
    return ans
}

时间复杂度：O(m*n)
空间复杂度：O(26len(n))

对于要在矩阵中搜索的单词建立tire树，然后深度搜索矩阵中每一个位置开始，然后往四个方向走，如果走到的地方能够匹配上tire树，则tire树往下指