概念学习

罗马数字转整数

I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000

罗马数字，如果大数在左小数在右侧，那么可以将字符视为单独数值，做相加处理

class Solution:
    def romanToInt(self, s: str) -> int:
        Im = {'I': 1,'V': 5,'X': 10,'L': 50,'C': 100,'D': 500,'M': 1000,}
        total = 0
        for char in s:
            if char in Im:
                total += Im[char]
        return total

但如果左侧为小数，则要做减法XIV = 10−1+5=14

if i > 0 and Im[s[i]] > Im[s[i-1]]
	total += Im[s[i]] -  2 * Im[s[i-1]]

减法的关键在于*2 假设输入为“IV”（4）在便利“I”时total已经加上了一个1使得如果直接将两数相减5-1=4 4+1=5会出现错误，所以需要乘2来抵消之前的错误相加


class Solution:
    def romanToInt(self, s: str) -> int:
        Im = {'I': 1,'V': 5,'X': 10,'L': 50,'C': 100,'D': 500,'M': 1000,}
        total = 0
        for i in range(len(s)):
            if i > 0 and Im[s[i]] > Im[s[i-1]]:
                total += Im[s[i]] - 2 * Im[s[i-1]]
            else:
                total += Im[s[i]]
        return total

最长公共前缀

  1. 纵向扫描

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        base = strs[0]

        for i in range(len(base)):
            # 固定字符串i 检查字符串的第i个字符师傅匹配
            for s in strs[1:]:
                if i >= len(s) or s[i] != base[i]:
                # 检测是否越界 是否相等 如果不相等则按照i切片输出
                    return base[:i]
        return base

使用第一个字符串 遍历每一个字符 逐个字符与其他字符串比较 错误暂停 结果即为答案

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        stack = []
        pairs = {'(':')','[':']','{':'}'}

        for char in s:
            if char in pairs:
                stack.append(char)
            else:
                if not stack or pairs[stack.pop()] != char:
                    return False
                    
        return not stack

建立一个字典，左括号为key，遍历字符串，判断是否为左括号如果是则推入栈，如果不是则使用顶栈作为key判断出对应右括号是否相等，如不等则返回False，否则继续判断，全部判断完成后检查栈是否为空（通过pop弹栈操作会将输出的栈删除）如果为空 返回true，如果不是则返回false代表栈中还有左括号，没有完成匹配

3330. 找到初始输入字符串 I

Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙，她 可能 在一个按键上按太久，导致一个字符被输入 多次 。

尽管 Alice 尽可能集中注意力，她仍然可能会犯错 至多 一次。

给你一个字符串 word ，它表示 最终 显示在 Alice 显示屏上的结果。

请你返回 Alice 一开始可能想要输入字符串的总方案数。

class Solution:
    def possibleStringCount(self, word: str) -> int:
        n,l =len(word),1
        for i in range(1,n):
            if word[i-1] == word[i]:
                l += 1
        return l

1768. 交替合并字符串

给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。

返回 合并后的字符串 。

func mergeAlternately(word1 string, word2 string) string {
    
    return u(word1,word2)
}

func u(x string, y string) string{
    s1 := []rune(x)
	s2 := []rune(y)
	miniLen := len(s1)
	if len(s2) < miniLen {
		miniLen = len(s2)
	}
	var builder strings.Builder
	for i := 0; i < miniLen; i++ {
		builder.WriteRune(s1[i])
		builder.WriteRune(s2[i])
	}

    if len(s1) > miniLen {
		builder.WriteString(string(s1[miniLen:]))
	} else if len(s2) > miniLen {
		builder.WriteString(string(s2[miniLen:]))
	}
	return builder.String()
}

偷懒了 直接用strings.Builder解决 长度最小的字符串做穿插 而后用找出最常的截出多余的字符拼接

389. 找不同

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

func findTheDifference(s string, t string) byte {
    return u(s,t)[0]
}

func u(s string, t string) string {
	s1 := s
	s2 := t
	x := 0
	x2 := 0
	for _, v := range s1 {
		x = x + int(v)
	}
	for _, v := range s2 {
		x2 = x2 + int(v)
	}

	if x2 > x {
		y := x2 - x
		return string(y)
	} else {
		y := x - x2
		return string(y)
	}

}

一个很巧的方法，计算两个字符串ascii之和相减，差转为字符就是多余字符