【LeetCode】2381、字母移位 II

【LeetCode】2381、字母移位 II

一、数据结构-差分-一维差分

1.1 数据结构-差分-一维差分

题目复述: 字符串s, 和shifts[]数组, 遍历每个shifts[i]来操作s, 操作如下:
每个shifts[i] 为 [starti, endi, directioni] 的三元组
把 s 中下标为 [starti, endi] 左比右闭区间的字母, 向前或向后偏移一个字符.
其中 若 directioni == 0 则向前偏移, 若 directioni == 1 则向后偏移

子区间的整体改变, 可联想到差分, 即差分数组两端的改变.

// go
func shiftingLetters(s string, shifts [][]int) string {
    n := len(s)
    diff := make([]int, n+1) // 差分数组, 注意大小为n+1
    for _, p := range shifts {
        start, end, dir := p[0], p[1], 2*p[2]-1 // 2*direction-1 使值域 [0,1] 变为 [-1,1]
        diff[start]+=dir // 意为 s[start...end] += dir
        diff[end+1]-=dir // 同上
    }

    // 对差分数组, 求累加, 还原出原数组
    t := []byte(s)
    shift := 0 // s中下标为 i 的值, 累加为 shift
    for i := range t {
        shift += diff[i] // 位置i, 累加得到的偏移, 可正可负可零
        c := int(t[i]-'a') // 字符c对应的数字(值域0到26), 注意要强转为int
        gap := (c + shift%26 + 26) % 26 // 位置i, 最终字符, 的非负数数字表示. +26是为了使余数为非负数. shift%26是为了防止数字太大而溢出
        t[i] = byte('a' + gap) // 注意要强转为byte
    }
    return string(t)
}

灵神视频
灵神题解

二、多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp

// go 同上

# python

// rust

// js

// ts