周赛玩了吗？
一起刷题
优秀
太菜了 不敢玩 
刷个200题就可以去玩了，实战更锻炼人
再刷一个月去试试
怎么不每天发个话题
话题是啥
就是新开个帖子，而不是回复
嗷嗷 我看回复也会把帖子顶上去 就没新开 
节省资源
1 个赞
题解
本题是一道简单题, 要求判定s和t是不是同构的, 即类似常说的ABB型这种结构. 本题使用一个哈希表记录字符与字符的映射即可, 如果出现了不同的映射则是不同构的.
代码
func isIsomorphic(s string, t string) bool {
table1 := map[rune]byte{}
table2 := map[byte]rune{}
for index, value := range s{
mapping1, exist := table1[value]
mapping2, exist2 := table2[t[index]]
if !exist{
table1[value] = t[index]
}else{
if !(mapping1 == t[index]){
return false
}
}
if !exist2{
table2[t[index]] = value
}else{
if mapping2 == value{
continue
}else{
return false
}
}
}
return true
}
总结
查看前面的题解, 发现了果然0ms用时的思路还是不同凡响, 用字符本身作为下标维护两个数组, 在遍历两个字符串的时候将两个字符串当前的字符作为下标, 将当前遍历的字符串的下标作为值放入两个数组中, 这样就记录了同时出现的两个字符最后的出现的下标, 如果这两个字符一直同时出现则二者下标一直是相同的, 若没有同时出现说明字符映射改变了, 没有继续之前的映射. 则两个字符串就是不同构的. 字符的本质是数, 那么字符可以表示更多的信息, 而不是字符本身, 将其作为数组下标就既使用了字符本身这个信息, 还使用了数组对应位置的元素这个信息, 能使用更多的信息就意味着更高的效率.
func isIsomorphic(s string, t string) bool {
s2t := [128]byte{}
t2s := [128]byte{}
for i, end := 0, len(s); i < end; i++ {
if s2t[s[i]] != t2s[t[i]] {
return false
}
s2t[s[i]], t2s[t[i]] = byte(i+1), byte(i+1)
}
return true
}
之后偶尔可能也会放几道CTF的题目 不会太难 就当玩一玩 放松一下了 
题解
本题可使用递归求解, 设置一个标记数组和board大小相同, 来标记已经访问过的元素, 遍历board数组, 找到目标字符串的起始字符, 对其调用explore函数求解, 若为true则直接返回true. 最后全部遍历完则返回false.
explore函数中, 传入了当前字符的行下标和列下标, 先判断可行的探索方向, 再在可行的探索方向上逐个判断其是否为目标字符串中的下一个字符以及是否已经被访问过, 若可以访问且为目标字符, 则对这个可行方向的字符调用explore函数继续后面的探索, 知道探索到目标字符串结尾则直接返回true. 若调用explore函数返回为true说明后面的字符串符合目标字符串且有可行路径, 则返回true. 若没有可探索方向或者所有可探索方向都不满足条件, 返回false.
使用递归要考虑的是在当前递归状态中应该完成什么任务以及递归的结束条件, 递归本质上是一种将全局问题化解为小的局部问题, 通过求解每个小的局部问题最终解决全局问题的解决问题的思路.
代码
func exist(board [][]byte, word string) bool {
for index, value := range board{
for index1, value2 := range value{
if value2 == byte(word[0]){
var flag [][]int
for _,_ = range board{
a := make([]int, len(board[0]))
flag = append(flag, a)
}
if (explore(board, index, index1, 0, flag, word)){
return true
}
}
}
}
return false
}
func explore(board [][]byte, row int, column int, target int, flag [][]int, word string)bool{
if target == len(word)-1 && byte(word[target]) == board[row][column]{
return true
}
up, down, left, right := !(row == 0),!(row == len(board)-1),!(column == 0), !(column == len(board[0])-1)
ok := false
if up && board[row-1][column] == byte(word[target+1])&&(flag[row-1][column] == 0){
if target+1 == len(word) - 1{
return true
}
flag[row][column] = 1
ok = ok || explore(board, row-1, column, target+1, flag,word)
flag[row][column] = 0
}
if down && board[row+1][column] == byte(word[target+1]) &&(flag[row+1][column] == 0){
if target+1 == len(word) - 1{
return true
}
flag[row][column] = 1
ok =ok || explore(board, row+1, column, target+1, flag, word)
flag[row][column] = 0
}
if left && board[row][column-1] == byte(word[target+1]) &&(flag[row][column-1] == 0){
if target+1 == len(word) - 1{
return true
}
flag[row][column] = 1
ok =ok || explore(board, row, column-1, target+1, flag, word)
flag[row][column] = 0
}
if right && board[row][column+1] == byte(word[target+1]) &&(flag[row][column+1] == 0){
if target+1 == len(word) - 1{
return true
}
flag[row][column] = 1
ok = ok || explore(board, row, column+1, target+1, flag, word)
flag[row][column] = 0
}
return ok
}
2 个赞
题解
本题是简单题, 因为题目说明了给定的括号一定是匹配的, 因此不用考虑括号匹配的问题. 只需设计一个值来保存当前还未匹配的左括号的个数, 这也是到当前这个字符的括号深度, 因此若出现了新的左括号, 就更新最大深度为当前的左括号个数和之前的最大深度中的较大值, 出现右括号则将未匹配的左括号个数减一, 最后返回最大深度即可.
代码
func maxDepth(s string) int {
depth := 0
left := 0
for _,value := range s{
if value == '('{
left++
depth = max(depth, left)
}
if value == ')'{
left--
}
}
return depth
}
1 个赞
题解
本题可以使用类似简单回溯的方法, 遍历字符串并判断当前字符和下一个字符是否互为大小写, 若是则删掉两个字符同时将循环下标回退到当前字符的前一个, 继续遍历字符串, 如此反复直到到达字符串结尾即可, 注意处理字符位于字符串结尾和开始的边界情况.
代码
func makeGood(s string) string {
index := 0
length := len(s)
for index=0;index<length-1;index++{
if s[index]!=s[index+1]&&(s[index] == s[index+1]+32 || s[index] == s[index+1]-32){
if index == length-2{
s = s[0:index]
length = len(s)
break
}else{
s = s[0:index]+s[index+2:]
length = len(s)
}
if index == 0{
index--
continue
}else{
index = index - 2
}
}
}
return s
}
总结
看到题解中有人使用栈, 通过额外的空间获得了更快的速度, 将前面的字符都入栈, 将栈顶和当前字符比较, 互为大小写则将栈顶出栈, 继续向下遍历并比较, 不互为大小写则将当前字符入栈. 这样不用回退下标, 可以充分利用go 中对for range循环优化带来的效率.
func makeGood(s string) string {
sb := []rune(s)
stack := make([]byte, 0)
if len(sb) > 1 {
for i, _ := range s {
n := len(stack)
if n > 0 && ((s[i]-stack[n-1] == 32) || (stack[n-1]-s[i] == 32)) {
stack = stack[:n-1]
} else {
stack = append(stack, s[i])
}
}
return string(stack)
} else {
return s
}
}
2 个赞
一起刷牙
题解
本题实际上还是一个括号匹配的问题, 使用一个栈就可以解决问题, 与前一天题不同的是, 本题中的左括号不一定能完全被匹配, 所以栈中可以保存左括号的下标, 遍历到字符串末尾后, 将栈中仍然存在的未匹配的左括号全部删去即可.
代码
func minRemoveToMakeValid(s string) string {
stack := []int{}
number := 0
index := 0
for index < len(s){
if s[index] == ')' {
if number == 0{
if index == len(s) - 1{
s = s[0:index]
return s
}else{
s = s[0:index] + s[index+1:]
}
}else{
number--
stack = stack[0:len(stack)-1]
index++
}
}else if s[index] == '('{
number++
stack = append(stack, index)
index++
}else{
index++
}
}
if len(stack) != 0{
for index,value := range stack{
if value - index != len(s) - 1{
s = s[0:value-index]+s[value+1-index:]
}else{
s = s[0:value-index]
return s
}
}
}
return s
}
1 个赞
题解
本题仍然是括号匹配问题, 只是这次加了一个万能字符’*‘,相当于赖子,既可以当’(‘用也可以当’)‘用. 作为一个判定问题, 只需要判断字符串是否匹配即可. 因此使用一个变量记录当前未匹配的左括号个数和可以被匹配的星号个数, 当遇到未匹配的右括号时如果没有未匹配的左括号则使用星号匹配. 若遍历结束左括号没有剩余则匹配成功. 若星号个数比左括号少则直接匹配失败. 若左括号和星号仍有剩余, 且星号个数大于左括号时, 说明剩余的星号可能能完全匹配左括号,这时反向遍历,把’)‘作为之前的左括号看待,用同样的方法尝试匹配所有’(‘. 最后只要’(‘能匹配成功即成功. p.s: 这里考虑的是正向遍历时若’)‘都匹配成功了, 那么只需要测试’(‘能否匹配就够了, 因为剩余的’)‘在正向遍历时已经确认可以通过多余的’*‘来完全匹配, 因此不用再考虑’)'的匹配问题.
代码
func checkValidString(s string) bool {
leftstack := 0
star := 0
for _, value := range s {
if value == '*'{
star++
}else if value == '('{
leftstack++
}else{
if leftstack > 0{
leftstack--
}else if star > 0{
star--
}else{
return false
}
}
}
if leftstack == 0{
return true
}else if star < leftstack{
return false
}else{
leftstack = 0
star = 0
for index:= len(s)-1;index>=0;index--{
if s[index] == ')'{
leftstack++
}else if s[index] == '*'{
star++
}else{
if leftstack > 0{
leftstack--
}else if star > 0{
star--
}else{
return false
}
}
}
}
return true
}
2 个赞
题解
本题是一道简单题, 题干看似很长, 分析下来会发现题目本身并不难, 若当前栈顶的三明治当前学生不喜欢, 就会向下轮换, 直到轮换到喜欢的学生, 因此栈顶三明治是否会被拿走取决于队伍中是否还有喜欢这种三明治的学生, 只要有这个学生总会被轮换到队伍的最前面. 则遍历学生数组, 统计两种三明治的喜欢的学生的数量. 遍历三明治数组, 遍历过程中减掉被拿走的三明治的类型喜欢的学生的数量, 直到三明治数组的当前元素没有学生喜欢, 则剩余的三明治就无法被拿到, 也就是无法吃到三明治的学生个数.
代码
func countStudents(students []int, sandwiches []int) int {
love1 := 0
love0 := 0
length := len(sandwiches)
for _,value := range students{
if value == 1{
love1++
}else{
love0++
}
}
for index,value := range sandwiches{
if value == 1{
if love1 <= 0{
return length - index
}
love1--
}else{
if love0 <= 0{
return length - index
}
love0--
}
}
return 0
}
1 个赞
题解
本题是一道简单题,并不需要去考虑模拟队列一轮一轮买票的过程, 而考虑队伍中的每个人在目标k买完票之前买了多少次票并将每个人中买的次数加和即可. 这里要将k之前和k之后的分开考虑, k之前的如果比k的需求大则在k买完之前都要买k需求的票的数量, 比k小则将自己的需求数量买完即可. 在k之后不同在于需求数大于等于k的人只会买k-1张票, 在k买完自己需要的票的时候这些人还在k的后面故当k买完时这些人最多买了k-1张. 遍历一遍数组按照这个规则将每个人的买票数加和即可得到最终结果.
代码
func timeRequiredToBuy(tickets []int, k int) int {
target := tickets[k]
time := 0
for _,value := range tickets[0:k]{
if value >= target{
time += target
}else{
time += value
}
}
for _,value := range tickets[k:]{
if value >= target - 1{
time += target - 1
}else{
time += value
}
}
// add itself once
time++
return time
}
1 个赞