【TalkGo算法之美】第 1 次在线比赛

算法之美线上比赛开启报名

目的

希望志同道合的刷题人可以有一个一起比赛、探讨的平台,也希望大神们可以来这里秀出你的最优解。

报名形式

直接回贴:报名参加 即可。

报名截止时间

2021.01.22 23:59:59

活动方式

参加 LeetCode 在 2021.01.24 早上的周赛。

比赛结束后,请将个人比赛的题解以及你所取得的成绩排名截图一并回复到你报名的帖子里。

我们将会按照报名成功的候选人中选出一名优胜者(以比赛最终排名为准)。

活动奖励

任意一本图书(如果你可以你给出选择理由以及看过之后的推荐语,那就更好了)

备注:想更更多真正积极活跃的人一起讨论,可以微信私信 night_reading_go,最好将你的“算法”相关情况进行备注说明。

1赞

报名参加

报名参加

只做出两道
第一题

func maximumTime(time string) string {
    temp := []byte(time)
    
    if temp[0] == '?' {
        if temp[1] == '?' || temp[1] == '1' || temp[1] == '2' || temp[1] == '3' || temp[1] == '0' {
            temp[0] = '2'
        } else {
            temp[0] = '1'
        }

    }
    if temp[1] == '?' {
        if temp[0] == '2' {
            temp[1] = '3'
        } else {
            temp[1] = '9'
        }
    }
    if temp[3] == '?' {
        temp[3] = '5'
    }
    if temp[4] == '?' {
        temp[4] = '9'
    }
    return string(temp)
}

第三题

func kthLargestValue(matrix [][]int, k int) int {
	m, n := len(matrix), len(matrix[0])
	arr := make([]int, 0, m*n)

	arr = append(arr, matrix[0][0])
	for j:=1; j<n; j++ {
		matrix[0][j] ^= matrix[0][j-1]
		arr = append(arr, matrix[0][j])
	}
	for i:=1; i<m; i++ {
		temp := matrix[i][0]
		matrix[i][0] ^=  matrix[i-1][0]
		arr = append(arr, matrix[i][0])
		for j:=1; j<n; j++ {
            temp ^= matrix[i][j]
			matrix[i][j] =  temp  ^  matrix[i-1][j]
			arr = append(arr, matrix[i][j])
		}
	}


	sort.Ints(arr)
	// fmt.Println(arr)
	return arr[len(arr)-k]
}

报名参加

报名参加

报名参加

报名参加

报名参加

报名参加

报名参加


本次比赛代码都不是最佳解法,请勿模仿。

第一题

简单题 ,wa了两次。。:hot_pepper::chicken:

func maximumTime(time string) string {
	var ans = strings.Builder{}
	for i := 0; i < len(time); i++ {
		if time[i]=='?'{
			switch i {
			case 0:
				if time[1]!='?' && time[1] >'3'{
					ans.WriteByte('1')
				}else {
					ans.WriteByte('2')
				}
				
			case 1:
				if ans.String()[0]<'2'{
					ans.WriteByte('9')
				}else {
					ans.WriteByte('3')
				}

			case 3:
				ans.WriteByte('5')
			case 4:
				ans.WriteByte('9')
			}
		}else {
			ans.WriteByte(time[i])
		}
	}
	return ans.String()
}

第二题

‘a~'z’都模拟一遍 ,就这题。。wa了三次,太:hot_pepper::chicken:了。

func min(a, b int) int {
	if a<b{
		return a
	}
	return b
}
func minCharacters(a string, b string) int {
	ab,bb := make([]int, 26),make([]int, 26)
	for i := 0; i < len(a); i++ {
	    ab[a[i]-'a']++
	}
	for i := 0; i < len(b); i++ {
		bb[b[i]-'a']++
	}
	ans := min(operator(ab,bb), operator(bb,ab))
	max:=0
	for i := 0; i < 26; i++ {
		ab[i]+=bb[i]
	}
	for i := 0; i < 26; i++ {
		if max < ab[i]{
			max = ab[i]
		}
	}
    // fmt.Println(max)
	return min(ans, len(a)+len(b)-max)
}

func operator(a, b []int) int {
	ans :=math.MaxInt32
	for i := 1; i < 26; i++ {
		temp :=0
		for j := 0; j < i; j++ {
			temp +=a[j]
		}
		for j := i; j < 26; j++ {
			temp +=b[j]
		}
		if temp < ans{
			ans = temp
		}
	}
	return ans
}

第三题

类似前缀和的思想求出矩阵前缀异或,再排序取第k个(这边可以用快排的partition优化复杂度,比赛就没想那么多了)

func kthLargestValue(matrix [][]int, k int) int {
	var xor = make([][]int, len(matrix))
	for i := 0; i < len(matrix); i++ {
		xor[i] = make([]int, len(matrix[0]))
	}
	temp := 0
	for i := 0; i < len(matrix[0]); i++ {
		temp ^= matrix[0][i]
		xor[0][i] = temp
	}
	for i := 1; i < len(matrix); i++ {
		for j := 0; j < len(matrix[0]); j++ {
			if j==0 {
				xor[i][0]=xor[i-1][0]^matrix[i][0]
			}else {
				xor[i][j] = xor[i-1][j]^xor[i][j-1]^xor[i-1][j-1]^matrix[i][j]
			}
		}
	}
	var ans = make([]int, len(matrix)*len(matrix[0]))
	index :=0
	for i := 0; i < len(xor); i++ {
		for j := 0; j < len(xor[i]); j++ {
			ans[index] = xor[i][j]
         index++

		}
	}
	sort.Ints(ans)
	return ans[len(ans)-k]
}

第四题

脑筋急转弯,观察得知(比较难解释,就类似1+2+3。。。+n,不够的话再把最右边看成墙壁,再计算需要补多少个底座)

func minimumBoxes(n int) int {
	i := 1
	total := 1
	for total+(i+1)*(i+2)/2 < n {
		i++
		total += (i + 1) * (i) / 2
	}
	n = n-total
   
	temp :=int(math.Sqrt(float64(n*2)))
	if temp*(temp+1)/2 >= n{
		return (i+1)*i/2+temp 
	}else {
		return (i+1)*i/2+temp+1
	}
}

最后排名:

2赞

看来我要去补补数学了

第一题: 替换隐藏数字得到的最晚时间

 func maximumTime(time string) string {
	arr := strings.Split(time, ":")
	hour := []byte(arr[0])
	minite := []byte(arr[1])

	if hour[0] == '?' {
		if hour[1] == '?' || hour[1] - '0' < 4 {
			hour[0] = '2'
		}else {
			hour[0] = '1'
		}
	}

	if hour[1] == '?' {
		switch hour[0] {
		case '0','1':
			hour[1] = '9'
		case '2':
			hour[1] = '3'
		default:
		}
	}
	if minite[0] == '?' {
		minite[0] = '5'
	}
	if minite[1] == '?' {
		minite[1] = '9'
	}

	return string(hour) + ":" + string(minite)
}

第二题: 满足三条件之一需改变的最少字符数

/*
满足条件一的方案:a中的所有字符都小于b中的所有字符-》a中的所有字符小于b中最小的字符
这时可以枚举最小字符a~z, 假设如果最小字符是d, 那么最小的操作数应该为: b中小于字符d的字符数 + a中大于等于字符d的字符数
*/

func LessThanMinCharacters(a string, b string) int {
	aCharNums := [26]int{}
	bCharNums := [26]int{}

	for _, ch := range a {
		aCharNums[ch - 'a']++
	}
	for _, ch := range b {
		bCharNums[ch - 'a']++
	}
	min := math.MaxInt32

	for i := 0; i < 26; i++ {
		tmpt := 0
		if i == 0 {
			continue
		}
		for j := i; j < 26; j++ {
			tmpt += aCharNums[j]
		}

		for j := 0; j < i; j++ {
			tmpt += bCharNums[j]
		}

		if tmpt < min {
			min = tmpt
		}
	}

	return min
}

func SameCharacters(a string, b string) int {
	charNums := [26]int{}
	for _, ch := range a {
		charNums[ch-'a']++
	}
	for _, ch := range b {
		charNums[ch-'a']++
	}

	max := 0
	for i := 0; i < 26; i++ {
		if max < charNums[i] {
			max = charNums[i]
		}
	}

	return len(a) + len(b) - max

}
func minCharacters(a string, b string) int {
	min1, min2, min3 := LessThanMinCharacters(a, b), LessThanMinCharacters(b, a), SameCharacters(a, b)
	min := min1
	if min > min2 {
		min = min2
	}
	if min > min3 {
		min = min3
	}
	return min
}

第三题 找出第 K 大的异或坐标值

/*
1:运用异或的性质: 满足结合律和交换律, 并且a^0=a
2:前缀和的思想, 充分运用以前计算过的结果进行计算异或值
3:将二维数据转换为一维度数据进行计算, 为了使用排序算法
*/

func kthLargestValue(matrix [][]int, k int) int {
	if len(matrix) == 0 {
		return 0
	}

	m, n := len(matrix), len(matrix[0])
	xorMatrix := make([]int, m * n)

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if i > 0 {
				xorMatrix[i * n + j] ^= xorMatrix[(i-1) * n + j]
			}
			if j > 0 {
				xorMatrix[i * n + j] ^= xorMatrix[i * n + j-1]
			}
			if i > 0 && j > 0 {
				xorMatrix[i * n + j] ^= xorMatrix[(i-1) * n + j-1]
			}
			xorMatrix[i * n + j] ^=  matrix[i][j]
		}
	}

	sort.Ints(xorMatrix)
	return xorMatrix[m*n-k]
}