leetcode-cn 2021年1月 2021年2月每日一题

DDY1024 · 2021 年2 月 24 日 01:28

// 2021.02.24

func flipAndInvertImage(A [][]int) [][]int {
    n, m := len(A), len(A[0])
    var reverse = func(arr []int) {
        l := len(arr)
        i, j := 0, l-1
        for i < j {
            arr[i], arr[j] = arr[j], arr[i]
            i++
            j--
        }
    }

    for i := 0; i < n; i++ {
        reverse(A[i])
        for j := 0; j < m; j++ {
            A[i][j] ^= 1
        }
    } 
    return A
}

LightningBilly · 2021 年2 月 24 日 14:41

488. 祖玛游戏


/*
基本思路：
模拟选择+bfs，每次选择一个字母往串里放，然后模拟消除，把结果放入到队列中。
这里需要定义状态，当前串和手中球
如果直接使用字符串来表示，空间不够用，需要状态压缩。
由于串是由5个字母组成的，长度最多是16，可以用6进制来表示，0表示无的意思。
最多用6^16 大概是10^14次方，再加上手中球5位，可以用uint64来表示一个状态。
 */

// 节点数据
type SingleObject interface{}

// 单链表节点
type SingleNode struct {
	Data SingleObject
	Next *SingleNode
}

// 单链表
type SingleList struct {
	mutex *sync.RWMutex
	Head  *SingleNode
	Tail  *SingleNode
	Size  uint
}

// 初始化
func (list *SingleList) Init() {
	list.Size = 0
	list.Head = nil
	list.Tail = nil
	list.mutex = new(sync.RWMutex)
}

// 添加节点到链表尾部
func (list *SingleList) Append(node *SingleNode) bool {
	if node == nil {
		return false
	}
	list.mutex.Lock()
	defer list.mutex.Unlock()
	if list.Size == 0 {
		list.Head = node
		list.Tail = node
		list.Size = 1
		return true
	}

	tail := list.Tail
	tail.Next = node
	list.Tail = node
	list.Size += 1
	return true
}

// 插入节点到指定位置
func (list *SingleList) Insert(index uint, node *SingleNode) bool {
	if node == nil {
		return false
	}

	if index > list.Size {
		return false
	}

	list.mutex.Lock()
	defer list.mutex.Unlock()

	if index == 0 {
		node.Next = list.Head
		list.Head = node
		list.Size += 1
		return true
	}
	var i uint
	ptr := list.Head
	for i = 1; i < index; i++ {
		ptr = ptr.Next
	}
	next := ptr.Next
	ptr.Next = node
	node.Next = next
	list.Size += 1
	return true
}

// 删除指定位置的节点
func (list *SingleList) Delete(index uint) bool {
	if list == nil || list.Size == 0 || index > list.Size-1 {
		return false
	}

	list.mutex.Lock()
	defer list.mutex.Unlock()

	if index == 0 {
		head := list.Head.Next
		list.Head = head
		if list.Size == 1 {
			list.Tail = nil
		}
		list.Size -= 1
		return true
	}

	ptr := list.Head
	var i uint
	for i = 1; i < index; i++ {
		ptr = ptr.Next
	}
	next := ptr.Next

	ptr.Next = next.Next
	if index == list.Size-1 {
		list.Tail = ptr
	}
	list.Size -= 1
	return true
}

// 获取指定位置的节点，不存在则返回nil
func (list *SingleList) Get(index uint) *SingleNode {
	if list == nil || list.Size == 0 || index > list.Size-1 {
		return nil
	}

	list.mutex.RLock()
	defer list.mutex.RUnlock()

	if index == 0 {
		return list.Head
	}
	node := list.Head
	var i uint
	for i = 0; i < index; i++ {
		node = node.Next
	}
	return node
}

// 输出链表
func (list *SingleList) Display() {
	if list == nil || list.Size == 0 {
		fmt.Println("this single list is nil")
		return
	}
	list.mutex.RLock()
	defer list.mutex.RUnlock()
	fmt.Printf("this single list size is %d \n", list.Size)
	ptr := list.Head
	var i uint
	for i = 0; i < list.Size; i++ {
		fmt.Printf("No%3d data is %v\n", i+1, ptr.Data)
		ptr = ptr.Next
	}
}

// Queue 队列信息
type Queue struct {
	list *SingleList
}

// Init 队列初始化
func (q *Queue) Init() {
	q.list = new(SingleList)
	q.list.Init()
}

// Size 获取队列长度
func (q *Queue) Size() uint {
	return q.list.Size
}

// Enqueue 进入队列
func (q *Queue) Enqueue(data interface{}) bool {
	return q.list.Append(&SingleNode{Data: data})
}

// Dequeue 出列
func (q *Queue) Dequeue() interface{} {
	node := q.list.Get(0)
	if node == nil {
		return nil
	}
	q.list.Delete(0)
	return node.Data
}

// Peek 查看队头信息
func (q *Queue) Peek() interface{} {
	node := q.list.Get(0)
	if node == nil {
		return nil
	}
	return node.Data
}

type Node struct {
	Val      int
	Children []*Node
}

var A2Num = map[rune]int{'R':1,'Y':2, 'B':3, 'G':4, 'W':5}
var Base uint64 = 6
var Hand uint64 = 10000

// 使用6进制转化。
func getHash(arr []int) uint64 {
	var sum uint64 = 0
	for _, value := range arr {
		sum *=Base
		sum+=uint64(value)
	}

	return sum
}

// 6进制反序列化。
func getArrFromHash(h uint64 ) []int{
	if h==0 {return nil}
	arr := make([]int, 0)

	for ;h>0;h/=Base {
		arr = append(arr, int(h%Base))
	}

	return arr
}

// 将串和手中球进行编码成一个状态。
func encode(board , hand []int) uint64 {
	sort.Ints(hand)
	boardHash, handHash := getHash(board), getHash(hand)
	return boardHash*Hand+handHash
}

// 解码状态。
func decode(code uint64) (board ,hand[]int) {
	boardHash, handHash := code/Hand , code%Hand
	return getArrFromHash(boardHash), getArrFromHash(handHash)
}

// 模拟添加一个球后的串，要考虑消除。
func insert(arr []int, position, ball int) []int {
	curball := ball
	cnt,i,j:=1, position-1,position
	for ;; { // 从插入的位置开始消除，其他位置一开始肯定不满足消除的情况。
		ii,jj:=i,j
		for ;ii>=0 && arr[ii]==curball ;ii-- {
			cnt++
		}
		for ;jj<len(arr) && arr[jj]==curball ;jj++ {
			cnt++
		}

		if cnt>=3 { // 需要消除
			i,j = ii,jj
			curball = -1
			cnt=0
			if i>=0 {
				curball = arr[i]
			}else if j<len(arr){
				curball = arr[j]
			}
		} else { // 不消除了直接退出
			break
		}
	}

	newArr := []int{}
	if i>=0 {
		newArr = append(newArr, arr[:i+1]...)
	}
	if j==position{ // 说明一次也没有消除过手中球需要添加
		newArr = append(newArr, ball)
	}
	if j<len(arr){
		newArr = append(newArr, arr[j:]...)
	}

	return newArr
}

func getArr(s string) []int {
	if len(s)==0 {return nil}
	arr := make([]int, len(s))
	for i, value := range s {
		arr[i]=A2Num[value]
	}

	return arr
}

func makeStartCode(board , hand string) uint64{
	boardArr := getArr(board)
	handArr := getArr(hand)

	return encode(boardArr, handArr)
}

/*
基本思路：
模拟选择+bfs，每次选择一个字母往串里放，然后模拟消除，把结果放入到队列中。
这里需要定义状态，当前串和手中球
如果直接使用字符串来表示，空间不够用，需要状态压缩。
由于串是由5个字母组成的，长度最多是16，可以用6进制来表示，0表示无的意思。
最多用6^16 大概是10^14次方，再加上手中球5位，可以用uint64来表示一个状态。
 */


func findMinStep(board , hand string) int {
	step := 0
	q := &Queue{}
	q.Init()
	start := makeStartCode(board, hand)
	q.Enqueue(start)
	vis := make(map[uint64]bool) // 标记是否已经搜索过
	for q.Size()>0 {
		for l:=q.Size();l>0;l-- {
			front, ok := q.Dequeue().(uint64)
			if !ok {continue}
			chain, handBall := decode(front)
			if len(chain)==0 { // 已经消除完毕
				return step
			}

			for i, _ := range chain {
				for j, ballColor := range handBall {
					if ballColor==0{continue} // 已经被选择了
					if j>0 && handBall[j-1]==ballColor {continue} // 跟之前做了同样的选择，没有意义
					if i>0 && chain[i-1]==ballColor {continue} // 填在右边不需要做
					/*
                    "RRWWRRBBRR"
"WB" 这个用例证明下面的判断逻辑是不对的

*/
					//if color!=ballColor {continue} //希望放在当前的左边，但颜色不一样，放了也没用。（该逻辑不正确）

					// 在当前位置左边放一个
					newChain := insert(chain, i, ballColor)
					copyHandBall := make([]int, len(handBall))

					copy(copyHandBall, handBall)
					copyHandBall[j]=0 //置为已选择

					newState := encode(newChain, copyHandBall)
					if !vis[newState] { //未搜索过
						vis[newState] = true
						q.Enqueue(newState) // 加入队列
					}

				}
			}
		}

		step++
	}

	return -1
}

kingeasternsun · 2021 年2 月 25 日 01:12

867. 转置矩阵

难度简单152收藏分享切换为英文接收动态反馈

给你一个二维整数数组 matrix，返回 matrix 的 转置矩阵 。

矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。

/*
 * @Description: 867
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-02-25 08:57:04
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-02-25 09:11:18
 * @FilePath: \867transpose\867.go
 */

package leetcode

func transpose(matrix [][]int) [][]int {

	rows := len(matrix)
	if rows == 0 {
		return matrix
	}
	cols := len(matrix[0])
	if cols == 0 {
		return matrix
	}

	if rows == cols {
		return inplace(matrix, rows, cols)
	}

	res := make([][]int, cols)
	for i := 0; i < cols; i++ {
		res[i] = make([]int, rows)
	}

	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			res[j][i] = matrix[i][j]
		}
	}

	return res
}

func inplace(matrix [][]int, rows, cols int) [][]int {
	for i := 0; i < rows; i++ {
		for j := i + 1; j < cols; j++ {
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}

	return matrix
}

DDY1024 · 2021 年2 月 25 日 02:18

// 2021.02.25

func transpose(matrix [][]int) [][]int {
    n, m := len(matrix), len(matrix[0])
    rmat := make([][]int, m)
    for i := 0; i < m; i++ {
        rmat[i] = make([]int, n)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            rmat[j][i] = matrix[i][j]
        }
    }
    return rmat
}

DDY1024 · 2021 年2 月 26 日 02:42

//2021.02.26

func findNumOfValidWords(words []string, puzzles []string) []int {
	n, m := len(words), len(puzzles)
	ans := make([]int, m)
	// 注意: puzzles 长度为固定值 7，puzzles 数组总的长度为 10^4
	includeCnt := make(map[int]int)
	for i := 0; i < n; i++ {
		mask := 0
		for j := 0; j < len(words[i]); j++ {
			mask |= 1 << uint(words[i][j]-'a')
		}
		includeCnt[mask]++
	}

	var lowBit = func(x int) int {
		return x & (-x)
	}
	bits := map[int]int{
		1:  0,
		2:  1,
		4:  2,
		8:  3,
		16: 4,
		32: 5,
		64: 6,
	}

	maskArr := make([]int, 128)
	for i := 0; i < m; i++ {
		for j := 1; j < 128; j++ {
			maskArr[j] = maskArr[j&(j-1)] | (1 << uint(puzzles[i][bits[lowBit(j)]]-'a'))
			if maskArr[j]&(1<<uint(puzzles[i][0]-'a')) > 0 {
				ans[i] += includeCnt[maskArr[j]]
			}
		}
	}
	return ans
}

kingeasternsun · 2021 年2 月 26 日 08:06

1178. 猜字谜

难度困难130收藏分享切换为英文接收动态反馈

外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。

字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：

单词 word 中包含谜面 puzzle 的第一个字母。
单词 word 中的每一个字母都可以在谜面 puzzle 中找到。
例如，如果字谜的谜面是 “abcdefg”，那么可以作为谜底的单词有 “faced”, “cabbage”, 和 “baggage”；而 “beefed”（不含字母 “a”）以及 “based”（其中的 “s” 没有出现在谜面中）。

返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。

/*
 * @Description: https://github.com/kingeasternsun/leetcode-cn
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-02-26 14:56:32
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-02-26 16:03:54
 * @FilePath: \1178findNumOfValidWords\1178.go
 */
package leetcode

/*
	匹配跟单词中的字母顺序，字母个数都无关，可以用bitmap压缩
	1. 记录word中 利用map记录各种bit标示的个数
	2. puzzles 中各个字母都不相同! 记录bitmap，然后搜索子空间中各种bit标识的个数的和
		因为puzzles长度最长是7，所以搜索空间 2^7
*/
func findNumOfValidWords(words []string, puzzles []string) []int {

	wordBitStatusMap := make(map[uint32]int, 0)
	for _, w := range words {
		wordBitStatusMap[toBitMap([]byte(w))]++
	}
	var res []int
	for _, p := range puzzles {
		var bitMap uint32
		var totalNum int
		bitMap |= (1 << (p[0] - 'a')) //work中要包含 p 的第一个字母 所以这个bit位上必须是1
		findNum([]byte(p)[1:], bitMap, &totalNum, wordBitStatusMap)
		res = append(res, totalNum)
	}

	return res
}

func toBitMap(word []byte) uint32 {
	var res uint32
	for _, b := range word {
		res |= (1 << (b - 'a'))
	}
	return res
}

//利用dfs 搜索 pussles的子空间
func findNum(puzzles []byte, bitMap uint32, totalNum *int, m map[uint32]int) {
	if len(puzzles) == 0 {
		*totalNum = *totalNum + m[bitMap]
		return
	}

	//puzzles[0]对应bit是0
	findNum(puzzles[1:], bitMap, totalNum, m)

	//puzzles[0]对应bit是0
	bitMap |= (1 << (puzzles[0] - 'a'))
	findNum(puzzles[1:], bitMap, totalNum, m)
	bitMap ^= (1 << (puzzles[0] - 'a')) //异或 清零

	return
}

DDY1024 · 2021 年2 月 28 日 01:40

// 2021.02.28

func isMonotonic(A []int) bool {
    n := len(A)
    sign1, sign2 := true, true 
    for i := 1; i < n; i++ {
        if A[i-1] < A[i] {
            sign1 = false
        }
        if A[i-1] > A[i] {
            sign2 = false
        }
    }
    return sign1 || sign2
}

DDY1024 · 2021 年3 月 1 日 05:07

//2021.3.1

type NumArray struct {
    prefixSum []int
    size int
}

func Constructor(nums []int) NumArray {
    n := len(nums)
    if n == 0 {
        return NumArray{}
    }

    prefixSum := make([]int, n)
    prefixSum[0] = nums[0]
    for i := 1; i < n; i++ {
        prefixSum[i] = nums[i] + prefixSum[i-1]
    }
    return NumArray{
        prefixSum,
        n,
    }
}

func (this *NumArray) SumRange(i int, j int) int {
    ans := this.prefixSum[j]
    if i > 0 {
        ans -= this.prefixSum[i-1]
    }
    return ans
}

/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.SumRange(i,j);
 */

leetcode-cn 2021年1月 2021年2月 每日一题

488. 祖玛游戏

867. 转置矩阵

1178. 猜字谜

leetcode-cn 2021年1月 2021年2月每日一题