当前位置: 首页 > biancheng >正文

len的魔力(中文网)+使括号有效的最少添加(leetcode)——20221004

中文网今日题目:len

package main

const s = "Go101.org"

// len(s) == 9
// 1 << 9 == 512
// 512 / 128 == 4

var a byte = 1 << len(s) / 128
var b byte = 1 << len(s[:]) / 128

func main() {
	println(a, b)
}
-----------------------------------
>>> 4 0

评论区大佬解答

  1. len(s)若s为字符串常量或者简单的数组表达式,则len返回的为int型的常量,若s为不为上述情况(有函数计算、通道等),则len返回的为int型的变量

  2. 关于位移操作,如果常量位移表达式的左侧操作数是一个无类型常量,那么其结果是一个整数常量,否则就是和左侧操作数同一类型的常量(必须是整数类型 );如果一个非常量位移表达式的左侧的操作数是一个无类型常量,那么它会先被隐式地转换为假如位移表达式被其左侧操作数单独替换后的类型。

  3. “先被隐式地转换为假如位移表达式被其左侧操作数单独替换后的类型" :对于var b byte = 1 << len(s[:]),1 << len(s[:])会被隐式的转换为var b byte = 1(表达式被1单独替换)的类型,1为无类型常量,因为b为byte,所以1会被隐式转换为byte,所以1 << len(s[:])为byte类型。

  4. s为常量表达式。对于var a byte = 1 << len(s) / 128,len(s)返回整型常量,所以1 << len(s)为常量表达式,且1为无类型常量,符合位移操作的第一种情况,所以为表达式结果为整型常量,故最后计算为4;

  5. 对于var b byte = 1 << len(s[:]) / 128,s[:]为函数计算,所以len(s[:])返回的为整型变量,所以1 << len(s[:]) / 128为非常量表达式,且1为无类型常量,符合位移操作的第二种情况,所以为表达式结果为byte,1<<9为512,转为byte类型,结果溢出,为0。

答案详解

  1. len 是一个内置函数,在官方标准库文档关于 len 函数 有这么一句:

    For some arguments, such as a string literal or a simple array expression, the result can be a constant. See the Go language specification’s “Length and capacity” section for details.(当参数是字符串字面量和简单 array 表达式,len 函数返回值是常量)

  2. 内置函数 len 和 cap 获取各种类型的实参并返回一个 int 类型结果。实现会保证结果总是一个 int 值。如果 s 是一个字符串常量,那么 len(s) 是一个常量 。如果 s 类型是一个数组或到数组的指针且表达式 s 不包含信道接收或(非常量的) 函数调用的话, 那么表达式 len(s) 和 cap(s) 是常量,这种情况下, s 是不求值的。否则的话, len 和 cap 的调用结果不是常量且 s 会被求值

  3. 第一句的 len(s) 是常量(因为 s 是字符串常量);而第二句的 len(s[:]) 不是常量。这是这两条语句的唯一区别:两个 len 的返回结果数值并无差异,都是 9,但一个是常量一个不是。

    var a byte = 1 << len(s) / 128
    var b byte = 1 << len(s[:]) / 128
    
  4. 关于位移操作,在位移表达式的右侧的操作数必须为整数类型,或者可以被 uint 类型的值所表示的无类型的常量。如果一个非常量位移表达式的左侧的操作数是一个无类型常量,那么它会先被隐式地转换为假如位移表达式被其左侧操作数单独替换后的类型。
    这里的关键在于常量位移表达式。根据上文的分析,1 << len(s) 是常量位移表达式,而 1 << len(s[:]) 不是。

  5. 如果常量位移表达式的左侧操作数是一个无类型常量,那么其结果是一个整数常量;否则就是和左侧操作数同一类型的常量(必须是整数类型 )

    因此对于 var a byte = 1 << len(s) / 128,因为 1 << len(s) 是一个常量位移表达式,因此它的结果也是一个整数常量,所以是 512,最后除以 128,最终结果就是 4。

    而对于 var b byte = 1 << len(s[:]) / 128,因为 1 << len(s[:]) 不是一个常量位移表达式,而做操作数是 1,一个无类型常量,根据规范定义它是 byte 类型(根据:如果一个非常量位移表达式的左侧的操作数是一个无类型常量,那么它会先被隐式地转换为假如位移表达式被其左侧操作数单独替换后的类型)。

    所以 var b byte = 1 << len(s[:]) / 128 中,根据规范定义,1 会隐式转换为 byte 类型,因此 1 << len(s[:]) 的结果也是 byte 类型,而 byte 类型最大只能表示 255,很显然 512 溢出了,结果为 0,因此最后 b 的结果也是 0。

leetcode今日题目:使括号有效的最少添加

使括号有效的最少添加:

只有满足下面几点之一,括号字符串才是有效的:

  • 它是一个空字符串,或者
  • 它可以被写成 AB (A 与 B 连接), 其中 A 和 B 都是有效字符串,或者
  • 它可以被写作 (A),其中 A 是有效字符串。

给定一个括号字符串 s ,移动N次,你就可以在字符串的任何位置插入一个括号。

  • 例如,如果 s = “()))” ,你可以插入一个开始括号为 “(()))” 或结束括号为 “())))” 。

返回 为使结果字符串 s 有效而必须添加的最少括号数。

示例 1:

输入:s = "())"
输出:1

示例 2:

输入:s = "((("
输出:3

tmd,力扣不说人话,我日****
翻译:括号匹配,()为有效,需要去掉,返回将剩下的变为有效的次数。

解决方法

对于括号匹配的题目,常用的做法是使用栈进行匹配,栈具有后进先出的特点,因此可以保证右括号和最近的左括号进行匹配。

  1. 从左到右遍历字符串,在遍历过程中维护左括号的个数以及添加次数。

  2. 如果遇到左括号,则将左括号的个数加 1。

  3. 如果遇到右括号,则需要和前面的左括号进行匹配,具体做法如下:

  4. 如果左括号的个数大于 0,则前面有左括号可以匹配,因此将左括号的个数减 1,表示有一个左括号和当前右括号匹配;

  5. 如果左括号的个数等于 0,则前面没有左括号可以匹配,需要添加一个左括号才能匹配,因此将添加次数加 1。

  6. 遍历结束后,需要检查左括号的个数是否为 0。如果不为 0,则说明还有剩下的左括号没有匹配,对于每个剩下的左括号都需要添加一个右括号才能匹配,此时需要添加的右括号个数为剩下的左括号个数,将需要添加的右括号个数加到添加次数。

func minAddToMakeValid(s string) int {
	// 左括号数量
	left:=0
	bucket:=make([]byte,0,len(s))

	for charIndex:=range s{
		if s[charIndex]=='('{
			bucket=append(bucket,s[charIndex])
			left++
		}else{
			if left!=0{
				bucket=append(bucket[:len(bucket)-1],bucket[len(bucket):]...)
				left--
			}else{
				bucket = append(bucket, s[charIndex])
			}
		}
	}
	return len(bucket)
}

在这里插入图片描述

优化

使用计数代替栈。

func minAddToMakeValid(s string) (ans int) {
    cnt := 0
    for _, c := range s {
        if c == '(' {
            cnt++
        } else if cnt > 0 {
            cnt--
        } else {
            ans++
        }
    }
    return ans + cnt
}

在这里插入图片描述

相关文章:

  • 牛客练习赛#84 F 莫比乌斯反演+杜教筛+技巧+斐波那契数列和gcd的结论+矩阵快速幂
  • ZZNUOJ_用C语言编写程序实现1342:支配值数目(附完整源码)
  • java毕业设计后勤管理系统餐饮评价监督系统(附源码、数据库)
  • 前端基础学习笔记
  • 【TS】联合类型--类型断言--类型推断
  • 谈笑风声的秘密
  • QT影城网上售票系统
  • NetCDF数据在ArcMap中的使用
  • 打怪升级(考验思路)
  • 持续精进,改变自己