每日一题(6) | 顾澜的技术小站

2024-06-17

题解和思路

不需要枚举每个字符串的所有子序列，如果短的子序列是「独有子序列」，那么更长的子序列也会是「独有子序列」。或者说，子序列越长，约不可能是其它字符串的子序列。

把 $strs$ 从大到小排序，一旦枚举到到符合要求的字符串，立即返回长度即可。没有符合要求的返回 $-1$

// 判断 s 是否为 t 的子序列  
func isSubseq(s, t string) bool {  
    i := 0  
    for _, c := range t {  
        if s[i] == byte(c) {  
            i++  
            if i == len(s) { // 所有字符匹配完毕  
                return true // s 是 t 的子序列  
            }  
        }  
    }  
    return false  
}  
  
func findLUSlength(strs []string) int {  
    ans := -1  
    sort.Slice(strs, func(i, j int) bool {  
        return len(strs[i]) > len(strs[j])  
    })  
next:  
    for i, s := range strs {  
        for j, t := range strs {  
            if j != i && isSubseq(s, t) {  
                continue next  
            }  
        }  
        return len(strs[i])  
    }  
    return ans  
}

2024-06-18

题目: 2288. 价格减免

题解和思路

空格分隔成 $n$ 个字符串数组，找到为 $\$$ 开头的字符串，并计算减免价格，最后把数组转回字符串即可。

func discountPrices(sentence string, discount int) string {
    strs := strings.Split(sentence, " ")
    d := 1 - float64(discount)/100
    for i, s := range strs {
        if len(s) > 1 && s[0] == '$' {
            price, err := strconv.Atoi(s[1:]) // 出错表示不是全数字
            if err == nil {
                strs[i] = fmt.Sprintf("$%.2f", float64(price)*d)
            }
        }
    }
    return strings.Join(strs, " ")
}

2024-06-19

题目: 2713. 矩阵中严格递增的单元格数

题解和思路

根据题目描述，我们顺序移动的单元格的值必须严格递增，因此，我们不妨用一个哈希表 $g$ 来记录每个值对应的所有单元格的位置，然后按照值的大小从小到大遍历。

在这个过程中，我们可以维护两个数组 $rowMax$ 和 $colMax$ ，分别记录每一行和每一列的最大递增长度。初始时，这两个数组的所有元素都为 $0$ 。

对于每个值对应的所有单元格位置，我们按照位置顺序遍历，对于每个位置 $(i,j)$ ，我们可以计算出以该位置为终点的最大递增长度为 $1+max⁡(rowMax[i],colMax[j])1$ ，更新答案，然后更新$ rowMax[i]$ 和 $colMax[j]$

func maxIncreasingCells(mat [][]int) int {  
    g := make(map[int][][2]int)  
    for i, row := range mat {  
        for j, x := range row {  
            g[x] = append(g[x], [2]int{i, j})  
        }  
    }  
      
    keys := make([]int, 0, len(g))  
    for k := range g {  
        keys = append(keys, k)  
    }  
    sort.Ints(keys)  
      
    rowMax := make([]int, len(mat))  
    colMax := make([]int, len(mat[0]))  
      
    var ans int  
    for _, k := range keys {  
        pos := g[k]  
        fs := make([]int, len(pos))  
        for i, p := range pos {  
            fs[i] = max(rowMax[p[0]], colMax[p[1]]) + 1  
            ans = max(ans, fs[i])  
        }  
          
        for i, p := range pos {  
            rowMax[p[0]] = max(rowMax[p[0]], fs[i])  
            colMax[p[1]] = max(colMax[p[1]], fs[i])  
        }  
    }  
    return ans  
}

2024-06-20

题目: 2748. 美丽下标对的数目

题解和思路

暴力：

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func countBeautifulPairs(nums []int) int {
    ans := 0
    n := len(nums)
    
    for i := 0; i < n; i++ {
        for nums[i] >= 10 {
            nums[i] /= 10
        }
        for j := i + 1; j < n; j++ {
            if gcd(nums[i], nums[j]%10) == 1 {
                ans++
            }
        }
    }
    return ans
}

哈希表

由于 $nums[i]$ 的最高位在 $[1,9]$ 中，我们可以在遍历数组的同时，统计最高位出现的次数，这样就只需枚举 $[1,9]$ 中的与 $x\mod 10$ 互质的数，把对应的次数加到答案中。

func countBeautifulPairs(nums []int) int {  
    ans := 0  
    cnt := [10]int{}  
      
    for _, num := range nums {  
        for i := 1; i < 10; i++ {  
            if cnt[i] > 0 && gcd(i, num%10) == 1 {  
                ans += cnt[i]  
            }  
        }  
        for num >= 10 {  
            num /= 10  
        }  
        cnt[num]++ // 统计最高位的出现次数  
    }  
    return ans  
}

2024-06-21

题目: LCP 61. 气温变化趋势

题解和思路

设两地气温变化趋势相同时为 $T$ ，否则为 $F$ ，求相同趋势的问题就变成了求最长 $T$ 的长度。

示例 1 可转换为 $TFTT$ ，最长 $T$ 长度为 2。

func temperatureTrend(temperatureA []int, temperatureB []int) int {  
    sum := 0  
    ans := 0  
    for i := 1; i < len(temperatureA); i++ {  
        if isCompare(temperatureA[i], temperatureA[i-1]) == isCompare(temperatureB[i], temperatureB[i-1]) {  
            sum++  
            ans = max(ans, sum)  
        } else {  
            sum = 0  
        }  
    }  
    return ans  
}  
  
func isCompare(a, b int) int {  
    if a > b {  
        return 1  
    } else if a == b {  
        return 0  
    }  
    return -1  
}

2024-06-22

题目: 2663. 字典序最小的美丽字符串

题解和思路

「不包含任何长度为 $2$ 或更长的回文串」，如果一个字符串是回文串，那么去掉首尾它依旧是回文串，直到最后回文串的最终长度为 $2$ 或者 $3$ ，此时等价于「不包含长度为 $2$ 或者 $3$ 」d 的回文串。也即是说，不能出现 $s[i] == s[i-1]$ 以及 $s[i] == s[i-2]$ 。

根据此性质，只需要判断 $s[i]$ 左侧的两个字母即可。 $s[i]$ 极其右侧的字母交给它右侧的字母来判断

要求字典序最小，修改最右侧就可以满足。

例如： $s=bcaz,k=26$ ，答案需要比 $s$ 大，先将 $s[3]=z$ 加一，因为 $z+1>k$ ，所以需要进位得到 $bcba$ 。但是这样前三个字母 $bcb$ 形成了回文串，接着处理 $bcb$ ，把 $s[2]=b$ 加一，得到 $bcca$ ，此时中间两个字符串形成了回文串 $cc$ ，将 $s[2]=c$ 加一，得到 $bcda$ ，此时已经没有回文串了。

题目保证了输入的 $s$ 是美丽字符串（不包含回文串），所以一旦发现此字符左侧不存在回文串时我们往右寻找，也不存在就可以返回答案。当 $s[0]$ 加一后不在前 $k$ 个字母中的情况，说明答案为空，返回空字符串。

func smallestBeautifulString(s string, k int) string {  
    maxS := 'a' + byte(k) // 最大字符  
    n := len(s)  
    i := n - 1 // 从最后一个字符往前处理  
    b := []byte(s)  
      
    b[i]++  
    for i < n {  
        if b[i] == maxS { // 需要进位  
            if i == 0 { // 遍历到第一个字符,没有结果  
                return ""  
            }  
              
            b[i] = 'a'  
            i--  
            b[i]++ // 进位  
        } else if i > 0 && b[i] == b[i-1] || i > 1 && b[i] == b[i-2] { // 左侧存在回文串  
            b[i]++  
        } else { // 左侧不存在回文串,往右寻找  
            i++  
        }  
    }  
    return string(b)  
}

2024-06-23

题目: 520. 检测大写字母

题解和思路

遍历所有字符，统计大写字母数量 $count$ ，以下三种情况均为 $true$ ：

$count=0$ $co u n t = 0$ ，全是小写字母
- $count = len(word)$ ，全部为大写字母
- $count=1$ 且 $word[0]$ 即首字母是大写

unicode.IsUpper(s) 可以判断 s 是否为大写字母

func detectCapitalUse(word string) bool {
    count := 0
    for _, s := range word {
        if unicode.IsUpper(s) {
            count++
        }
    }
    
    return count == 0 || count == len(word) || count == 1 && unicode.IsUpper(rune(word[0]))
}