简单 #
旅行终点站 #
给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市*。*
题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。
输入：paths = [["B","C"],["D","B"],["C","A"]]
输出："A"
解释：所有可能的线路是：
"D" -> "B" -> "C" -> "A".
"B" -> "C" -> "A".
"C" -> "A".
"A".
显然，旅行终点站是 "A" 。
func destCity(paths [][]string) string { //合并区间
for i, j := 0, 1; j < len(paths); {
if len(paths) == 1 {
break
}
if paths[i][1] == paths[j][0] {
paths[i][1] = paths[j][1]
paths = append(paths[:j], paths[j+1:]...)
j = 1
continue
}
if paths[i][0] == paths[j][1] {
paths[j][1] = paths[i][1]
paths = append(paths[:i], paths[i+1:]...)
j = 1
continue
}
j++
}
return paths[0][1]
}
官方：
func destCity(paths [][]string) string {
citiesA := map[string]bool{}
for _, path := range paths { //每个开始都给true
citiesA[path[0]] = true
}
for _, path := range paths {
if !citiesA[path[1]] { //如果没有则证明是最后一个
return path[1]
}
}
return ""
}
求出出现两次数字的XOR值 #
给你一个数组 nums ，数组中的数字 要么 出现一次，要么 出现两次。
请你返回数组中所有出现两次数字的按位 XOR 值，如果没有数字出现过两次，返回 0 。
示例 1：
**输入：**nums = [1,2,1,3]
**输出：**1
解释：
nums 中唯一出现过两次的数字是 1 。
示例 2：
**输入：**nums = [1,2,3]
**输出：**0
解释：
nums 中没有数字出现两次。
示例 3：
**输入：**nums = [1,2,2,1]
**输出：**3
解释：
数字 1 和 2 出现过两次。1 XOR 2 == 3 。
func duplicateNumbersXOR(nums []int) int {
cMap:=make(map[int]struct{},0)
number:=0
for _,num:=range nums{
if _,ok:=cMap[num];ok{
number=number^num
}else{
cMap[num]=struct{}{}
}
}
return number
}
官方：
func duplicateNumbersXOR(nums []int) int {
cnt := make(map[int]bool)
res := 0
for _, num := range nums {
if _, found := cnt[num]; found {
res ^= num
} else {
cnt[num] = true
}
}
return res
}
字母在字符串中的百分比 #
给你一个字符串 s 和一个字符 letter ，返回在 s 中等于 letter 字符所占的 百分比 ，向下取整到最接近的百分比。
示例 1：
输入：s = "foobar", letter = "o"
输出：33
解释：
等于字母 'o' 的字符在 s 中占到的百分比是 2 / 6 * 100% = 33% ，向下取整，所以返回 33 。
func percentageLetter(s string, letter byte) int {
count:=0
for _,v:=range []byte(s){
if v==letter{
count++
}
}
return int(float64(count) / float64(len(s))* 100)
}
遇到的坑 #
-
float32(59) / float32(100)的精确数学结果是0.59。 -
但
float32是 32位单精度浮点数，其有效位数约为 7位十进制数字，无法精确表示0.59。 -
实际存储的值可能是近似值，例如
0.58999997（因二进制浮点数无法精确表示某些十进制小数）。 -
继续计算
0.58999997 * 100，结果是58.999997（而非精确的59.0）。 -
Go 的
int(...)会直接 截断小数部分（不是四舍五入）。 -
int(58.999997) → 58。
奇偶频次间的最大差值 I #
给你一个由小写英文字母组成的字符串 s 。
请你找出字符串中两个字符 a1 和 a2 的出现频次之间的 最大 差值 diff = a1 - a2，这两个字符需要满足：
a1在字符串中出现 奇数次 。a2在字符串中出现 偶数次 。
返回 最大 差值。
示例 1：
**输入：**s = “aaaaabbc”
**输出：**3
解释：
- 字符
'a'出现 奇数次 ，次数为5；字符'b'出现 偶数次 ，次数为2。 - 最大差值为
5 - 2 = 3。
示例 2：
**输入：**s = “abcabcab”
**输出：**1
解释：
- 字符
'a'出现 奇数次 ，次数为3；字符'c'出现 偶数次 ，次数为 2 。 - 最大差值为
3 - 2 = 1。
func maxDifference(s string) int {
cnt:=make(map[rune]int)
for _,v:=range s{
if value,ok:=cnt[v];ok{
value++
cnt[v]=value
}else{
cnt[v]=1
}
}
maxOdd,minEven:=1,len(s)
for _,v:=range cnt{
if v%2==1{
maxOdd=max(maxOdd,v)
}else{
minEven=min(minEven,v)
}
}
return maxOdd-minEven
}
中等 #
优质数对的总数2 #
给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。
如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。
返回 优质数对 的总数。
示例 1：
**输入：**nums1 = [1,3,4], nums2 = [1,3,4], k = 1
**输出：**5
解释：
5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。
示例 2：
**输入：**nums1 = [1,2,4,12], nums2 = [2,4], k = 3
**输出：**2
解释：
2个优质数对分别是 (3, 0) 和 (3, 1)。
超出时间限制：
func numberOfPairs(nums1 []int, nums2 []int, k int) int64 {
nums1Data:=make(map[int]int,len(nums1))
nums1MaxNumber:=0
for _,nums:=range nums1{
nums1Data[nums]++
if nums>nums1MaxNumber{
nums1MaxNumber=nums
}
}
var number int64
for _,num2:=range nums2{
for i:=num2*k;i<=nums1MaxNumber;i+=num2*k{
if a,ok:=nums1Data[i];ok{
number+=int64(a)
}
}
}
return number
}
官方：
func numberOfPairs(nums1 []int, nums2 []int, k int) int64 {
count := make(map[int]int)
count2 := make(map[int]int)
max1 := 0
for _, num := range nums1 {
count[num]++
if num > max1 {
max1 = num
}
}
for _, num := range nums2 {
count2[num]++
}
var res int64
for a, cnt := range count2 {
for b := a * k; b <= max1; b += a * k {
if _, ok := count[b]; ok {
res += int64(count[b] * cnt)
}
}
}
return res
}
向字符串添加空格 #
给你一个下标从 0 开始的字符串 s ，以及一个下标从 0 开始的整数数组 spaces 。
数组 spaces 描述原字符串中需要添加空格的下标。每个空格都应该插入到给定索引处的字符值 之前 。
- 例如，
s = "EnjoyYourCoffee"且spaces = [5, 9]，那么我们需要在'Y'和'C'之前添加空格，这两个字符分别位于下标5和下标9。因此，最终得到"Enjoy ***Y***our ***C***offee"。
请你添加空格，并返回修改后的字符串*。*
示例 1：
输入：s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]
输出："Leetcode Helps Me Learn"
解释：
下标 8、13 和 15 对应 "LeetcodeHelpsMeLearn" 中加粗斜体字符。
接着在这些字符前添加空格。
//超出时间限制
func addSpaces(s string, spaces []int) string {
sLen := len(s)
result := ""
for i, v := range spaces {
if v < sLen {
if i == 0 {
result = s[:v]
continue
}
result = result + " " + string(s[spaces[i-1]:spaces[i]])
}
}
result = result + " " + string(s[spaces[len(spaces)-1]:])
return result
}
//超出时间限制
func addSpaces(s string, spaces []int) string {
spacesLen := len(spaces)
j:=0
result := ""
for i, v := range s {
if j<spacesLen&&i==spaces[j]{
result=result+" "+string(v)
j++
}else{
result=result+string(v)
}
}
return result
}
//通过
func addSpaces(s string, spaces []int) string {
var res strings.Builder
ptr := 0
for i ,v:=range s{
if ptr < len(spaces) && i == spaces[ptr] {
res.WriteByte(' ')
ptr++
}
res.WriteRune(v)
}
return res.String()
}
在 Go 中，字符串是不可变的，每次使用 + 拼接字符串都会创建一个新的字符串并复制所有内容。当字符串较大或循环次数较多时，这种操作会带来严重的性能问题。
Go 的 strings.Builder 是专门为高效构建字符串设计的工具，它通过预分配内存和缓冲区复用，避免了频繁的内存分配和复制。
从盒子中找出字典序最大的字符串 I #
给你一个字符串 word 和一个整数 numFriends。
Alice 正在为她的 numFriends 位朋友组织一个游戏。游戏分为多个回合，在每一回合中：
word被分割成numFriends个 非空 字符串，且该分割方式与之前的任意回合所采用的都 不完全相同 。- 所有分割出的字符串都会被放入一个盒子中。
在所有回合结束后，找出盒子中 字典序最大的 字符串。
示例 1：
输入: word = “dbca”, numFriends = 2
输出: “dbc”
解释:
所有可能的分割方式为：
"d"和"bca"。"db"和"ca"。"dbc"和"a"。
你只需要知道计算字符串字典序用 max(a,b)函数
abcdefg 3 7-3+1=5 abcde 从零开始 “”和word[0:5] word[1:6] word[2:7] word[3:7] word[4:7] ... 所以min(i+n-numFriends+1,n)
func answerString(word string, numFriends int) string {
if numFriends==1{
return word
}
n:=len(word)
res:=""
for i:=0;i<n;i++{
res=max(res,word[i:min(i+n-numFriends+1,n)])
}
return res
}
按字典序排列最小的等效字符串 #
给出长度相同的两个字符串s1 和 s2 ，还有一个字符串 baseStr 。
其中 s1[i] 和 s2[i] 是一组等价字符。
- 举个例子，如果
s1 = "abc"且s2 = "cde"，那么就有'a' == 'c', 'b' == 'd', 'c' == 'e'。
等价字符遵循任何等价关系的一般规则：
- 自反性 ：
'a' == 'a' - 对称性 ：
'a' == 'b'则必定有'b' == 'a' - 传递性 ：
'a' == 'b'且'b' == 'c'就表明'a' == 'c'
例如， s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样，那么 baseStr = "eed" , "acd" 或 "aab"，这三个字符串都是等价的，而 "aab" 是 baseStr 的按字典序最小的等价字符串
利用 s1 和 s2 的等价信息，找出并返回 baseStr 的按字典序排列最小的等价字符串。
示例 1：
输入：s1 = "parker", s2 = "morris", baseStr = "parser"
输出："makkek"
解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [m,p], [a,o], [k,r,s], [e,i] 共 4 组。每组中的字符都是等价的，并按字典序排列。所以答案是 "makkek"。
func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
uf := NewUnionFind(26) //注意这里是26个字母
for i := 0; i < len(s1); i++ {
x := s1[i] - 'a'
y := s2[i] - 'a'
uf.union(int(x), int(y))
}
s := []byte(baseStr)
for i := 0; i < len(baseStr); i++ {
s[i] = byte(uf.find(int(s[i]-'a') )+ 'a') //注意别+错了
}
return string(s)
}
type UnionFind struct {
parent []int
}
func NewUnionFind(n int) *UnionFind {
uf := new(UnionFind)
uf.parent = make([]int, n)
for i := 0; i < n; i++ {
uf.parent[i] = i
}
return uf
}
func (uf *UnionFind) find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.find(uf.parent[x])
}
return uf.parent[x]
}
func (uf *UnionFind) union(x, y int) {
x, y = uf.find(x), uf.find(y) //查找根节点
if x == y { //同一棵树
return
}
if x > y { //// 总是让字典序更小的作为集合代表字符 根据情况，也可以换成最大的或者不换
x, y = y, x
}
uf.parent[y] = x
}
删除星号以后字典序最小的字符串 #
给你一个字符串 s 。它可能包含任意数量的 '*' 字符。你的任务是删除所有的 '*' 字符。
当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：
- 删除最左边的
'*'字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。
请你返回删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串。
示例 1：
**输入：*s = “aaba”
输出：“aab”
解释：
删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ，s 字典序最小。
示例 2：
**输入：**s = “abc”
输出：“abc”
**解释：**字符串中没有 '*' 字符。
根据题意可知，每遇到一个 ‘∗’ 时，则需要去除左侧字典序最小的字符，由于每次要要去掉字典序最小的字母，为了让字典序尽量小，根据贪心原则，相比去掉前面的字符，去掉后面的字符更优，这样才能保证最小的字符尽可能的靠前，使得字符串整体的字典序最小。
我们从左到右遍历字符串 s，由于字符串只包含小写字母，用 26 个栈来保存当前已遍历过的每种字符的索引，第 k 个栈维护第 k 个小写字母的索引。
当遇到字符 ‘∗’ 时，找到非空且字典序最小的栈，在字符串 s 种标记栈顶元素对应的字符为 ‘∗’，并移除栈顶元素；
当遇到非字符 ‘∗’ 时，则将当前索引 i 压入到对应的栈。
最后从左到右选取字符串 s 中不为 ‘∗’ 的字符构成的字符串即为答案。
func clearStars(s string) string {
size := len(s)
cnt := make([][]int, 26)
for i := 0; i < 26; i++ { //建立26个栈，保存当前已遍历过的每种字符的索引
cnt[i] = make([]int, 0)
}
ss := []rune(s)
for i, v := range s {
if v != '*' {
cnt[v-'a'] = append(cnt[v-'a'], i)
} else {
for i := 0; i < 26; i++ {
if len(cnt[i]) > 0 {
n := cnt[i][len(cnt[i])-1] //最小值的最后一个索引
cnt[i]=cnt[i][:len(cnt[i])-1] //栈出一个
ss[n]='*' //删除的空位填充
break
}
}
}
}
sss:=make([]rune, 0)
for i:=0;i<size;i++ { //遍历一遍 去掉*
if ss[i] != '*' {
sss = append(sss, ss[i])
}
}
return string(sss)
}
使用机器人打印字典序最小的字符串 #
给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：
- 删除字符串
s的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到t的尾部。 - 删除字符串
t的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。
请你返回纸上能写出的字典序最小的字符串。
示例 1：
输入：s = "zza"
输出："azz"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="zza" ，t="" 。
执行第一个操作三次，得到 p="" ，s="" ，t="zza" 。
执行第二个操作三次，得到 p="azz" ，s="" ，t="" 。
示例 2：
输入：s = "bac"
输出："abc"
解释：用 p 表示写出来的字符串。
执行第一个操作两次，得到 p="" ，s="c" ，t="ba" 。
执行第二个操作两次，得到 p="ab" ，s="c" ，t="" 。
执行第一个操作，得到 p="ab" ，s="" ，t="c" 。
执行第二个操作，得到 p="abc" ，s="" ，t="" 。
示例 3：
输入：s = "bdda"
输出："addb"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="bdda" ，t="" 。
执行第一个操作四次，得到 p="" ，s="" ，t="bdda" 。
执行第二个操作四次，得到 p="addb" ，s="" ，t="" 。
提示：
1 <= s.length <= 105s只包含小写英文字母。
方法一：贪心 + 栈
思路
这题其实是给了一个栈的入栈序列，要求出栈序列字典序最小。考虑栈顶元素 c 和字符串 s 中剩余字符中最小的字符 minCharacter：
如果 c<minCharacter，那么要将栈顶元素出栈，才能保证出栈序列最小。 如果 c>minCharacter，那么要将栈顶元素保留，并不停入栈，直到 minCharacter 才能保证出栈序列最小。 如果 c=minCharacter，那么也要将栈顶元素出栈，才能保证出栈序列最小。因为这样做的话，我们可以先将 c 出栈，然后再不停入栈后将 minCharacter 出栈，出栈序列中有两个连续的最小字符。否则如果先不停入栈后将 minCharacter 出栈，我们只能得到一个最小字符，后续的字符只会大于等于该最小字符。 有了这个贪心的思路，我们可以每次将一个字符入栈，然后更新字符串 s 中剩余字符中最小的字符 minCharacter，并不停比较栈顶元素和 minCharacter 的大小，如果符合条件则出栈，否则就进入下一次循环。最后返回结果。
func robotWithString2(s string) string {
cnt := make([]int, 26)
for i := 0; i < len(s); i++ {
cnt[s[i]-'a']++ //先记录所有的字母
}
//创建一个栈
stack := make([]byte, 0)
res := make([]byte, 0)
minCharacter := 0 //比栈顶
for _, v := range s {
stack = append(stack, byte(v)) //先入栈
cnt[v-'a']--
//找出下一个最小字符 用来判断要不要出栈
for j := 0; j < 26; j++ {
if cnt[j] > 0 {
minCharacter = j + 'a'
break
}
}
//出栈 出多少次停止？ 栈>0,栈顶元素<=最小字符 一直出到栈顶大于最小字符串
for len(stack) > 0 && stack[len(stack)-1] <= byte(minCharacter) {
//不是出完为止，是出栈顶元素
res = append(res, stack[len(stack)-1])
stack = stack[:len(stack)-1]
}
}
for len(stack) > 0 { //记得最后出栈，出完为止，
res = append(res, stack[len(stack)-1])
stack = stack[:len(stack)-1]
}
return string(res)
}
字典序排数 #
给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
示例 1：
输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
示例 2：
输入：n = 2
输出：[1,2]
输入：n = 32
输出：[1,10,11,12,13,14,15,16,17,18,19,2,20,21,22,23,24,25,26,27,28,29,3,30,31,32,4,5,6,7,8,9]
题目要求设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法，因此我们不能使用直接排序的方法。
那么对于一个整数 number，它的下一个字典序整数对应下面的规则：
尝试在 number 后面附加一个零，即 number×10，如果 number×10≤n，那么说明 number×10 是下一个字典序整数；
如果 numbermod10=9 或 number+1>n，那么说明末尾的数位已经搜索完成，退回上一位，即 number=⌊ 10 number ⌋，然后继续判断直到 numbermod10 \ =9 且 number+1≤n 为止，那么 number+1 是下一个字典序整数。
字典序最小的整数为 number=1，我们从它开始，然后依次获取下一个字典序整数，加入结果中，结束条件为已经获取到 n 个整数。
func lexicalOrder(n int) []int {
res:=make([]int,n )
num:=1
for i:=range n{
res[i]=num //第一个传1 注意它在这里
if num*10<=n{
num=num*10 //到10
}else{ //从10 一直到19
for num%10==9|| num+1>n{ //到9了，或者下一个要超了
num=num/10
}
num++
}
}
return res
}
困难 #
公司命名 #
给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：
- 从
ideas中选择 2 个 不同 名字，称为ideaA和ideaB。 - 交换
ideaA和ideaB的首字母。 - 如果得到的两个新名字 都 不在
ideas中，那么ideaA ideaB（串联ideaA和ideaB，中间用一个空格分隔）是一个有效的公司名字。 - 否则，不是一个有效的名字。
返回 不同 且有效的公司名字的数目。
示例 1：
输入：ideas = ["coffee","donuts","time","toffee"]
输出：6
解释：下面列出一些有效的选择方案：
- ("coffee", "donuts")：对应的公司名字是 "doffee conuts" 。
- ("donuts", "coffee")：对应的公司名字是 "conuts doffee" 。
- ("donuts", "time")：对应的公司名字是 "tonuts dime" 。
- ("donuts", "toffee")：对应的公司名字是 "tonuts doffee" 。
- ("time", "donuts")：对应的公司名字是 "dime tonuts" 。
- ("toffee", "donuts")：对应的公司名字是 "doffee tonuts" 。
因此，总共有 6 个不同的公司名字。
下面列出一些无效的选择方案：
- ("coffee", "time")：在原数组中存在交换后形成的名字 "toffee" 。
- ("time", "toffee")：在原数组中存在交换后形成的两个名字。
- ("coffee", "toffee")：在原数组中存在交换后形成的两个名字。
示例 2：
输入：ideas = ["lack","back"]
输出：0
解释：不存在有效的选择方案。因此，返回 0 。
提示：
2 <= ideas.length <= 5 * 1041 <= ideas[i].length <= 10ideas[i]由小写英文字母组成ideas中的所有字符串 互不相同
超时结果：
func distinctNames(ideas []string) int64 {
list := make(map[string]struct{}, 0)
for _, idea := range ideas {
list[idea] = struct{}{}
}
var number int64 = 0
for i := 0; i < len(ideas); i++ {
for j := i + 1; j < len(ideas); j++ {
i_idea, j_idea := []byte(ideas[i]), []byte(ideas[j])
if i_idea[0] == j_idea[0] {
continue
} else {
a := i_idea[0]
i_idea[0] = j_idea[0]
j_idea[0] = a
if _, ok := list[string(i_idea)]; ok {
continue
}
if _, ok := list[string(j_idea)]; ok {
continue
}
number += 2
}
}
}
return number
}
字典序的第K小数字 #
给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。
示例 1:
输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
示例 2:
输入: n = 1, k = 1
输出: 1
//超时结果：
func findKthNumber(n int, k int) int {
v:=1
j:=0
for i:=0;i<n;i++{
j++
if j==k{
break
}
if v*10<=n{
v=v*10
}else{
for v+1>n||v%10==9{
v=v/10
}
v++
}
}
return v
}