To Index
848 Shifting Letters
题目难度 Medium
有一个由小写字母组成的字符串 S，和一个整数数组 shifts。 我们将字母表中的下一个字母称为原字母的 移位（由于字母表是环绕的， ‘z’ 将会变成 ‘a’）。
例如·，shift('a') = 'b'， shift('t') = 'u',， 以及 shift('z') = 'a'。
对于每个 shifts[i] = x ， 我们会将 S 中的前 i+1 个字母移位 x 次。
返回将所有这些移位都应用到 S 后最终得到的字符串。
示例：
输入：S = "abc", shifts = [3,5,9]
输出："rpl"
解释：
我们以 "abc" 开始。
将 S 中的第 1 个字母移位 3 次后，我们得到 "dbc"。
再将 S 中的前 2 个字母移位 5 次后，我们得到 "igc"。
最后将 S 中的这 3 个字母移位 9 次后，我们得到答案 "rpl"。
提示：
1 <= S.length = shifts.length <= 20000
0 <= shifts[i] <= 10 ^ 9
方法：首先计算每个位置的字符要移动的距离，最后一个字母只需要移动数组中末位位移，倒数第二个则需要移动的位数是移位数组末尾两数之和，以此类推。
- 由于shifts每个元素大小最大为10^9，长度为
2*10^4，而int类型表达范围是-2^31～2^31,约为2147483648，无法表达shifts数组的各项元素之和，因此采用long int类型。 - 然后计算需要移位的位置，参照字母‘a’来计算，tmp表示最后相距a的距离。
- 使用一个空String保存所有移位后的字母。
class Solution {
public:
string shiftingLetters(string S, vector<int>& shifts) {
string result="";
size_t num=shifts.size();
vector<long int > move(shifts.size(),0);
move[num-1]=shifts[num-1];
for(int i=num-2;i>-1;i--)
{
move[i] = shifts[i]+ move[i+1];
}
for(int i=0;i<shifts.size();i++)
{
int tmp=S[i]-'a'+move[i]-move[i]/26*26;
result += 'a'+tmp%26 ;
// result += (tmp -'z' >0 ? tmp-((tmp-'z')/26)*26 : tmp);
}
return result;
}
};