[Day 3] Leetcode 848. Shifting Letters (C++)

前言

今天的题目在这里： 848. Shifting Letters，被归类为medium，乍看之下想说应该是easy颇简单，结果还是不小心踩了几个坑QQ 是关於char的数值范围与int的数值范围，还是有些知识不足的地方，一起来看看吧！

想法

看到题目，第一眼想说只想遍历一次的话，就要倒着来了，因为它字串的第一个字母会随着後面的每次shift都跟着shift；然後肯定是要先记录一个shift的总和，才知道最後总共要移多少；另外呢，要把int转成字母/英文字母转成int是很简单的，你可以直接打开这个线上编译器试试看：

// Example program
#include <iostream>
#include <string>
using namespace std;
int main()
{
    int a = 'a', z = 'z';
    cout << "'a' to int: " << a << endl;
    cout << "'z' to int: " << z << endl;
    char ca = 97, cz = 122;
    cout << "97 to char: " << ca << endl;
    cout << "122 to char: " << cz << endl;
}

输出如下：

'a' to int: 97
'z' to int: 122
97 to char: a
122 to char: z

可以看到它可以动态直接转型~ 小写英文字母'a'~'z'的数值范围在97~122之间。
但这里有个陷阱，就是你如果给char x = 某数字;，然後某数字<0 或 >255的话，就会overflow！(在unsigned char的情形中)
这是因为char是由1byte来储存的，容纳的数值范围只有2^8=256，char在不同编译器中可能是signed char或 unsigned char，分别可接受的数值范围是-128~127/ 0~255，可以看这边。
顺带一提，int则是4byte来储存的，容纳的数值范围是2^32，从-2,147,483,648~2,147,483,647

所以来看看我一开始的写法XD

class Solution {
public:
    string shiftingLetters(string s, vector<int>& shifts) {
        // iterate from the end, so we can record the nums we need to add for each char
        char tmp;
        int sum=0;
        string ans=s;
        for(int i=s.length()-1;i>=0;--i){
            tmp = s[i];
            sum+= shifts[i];
            tmp+=sum;
            if(tmp>'z'){
                tmp = (tmp-'a')%26+'a';
            }
            ans[i] = tmp;
        }
        return ans;
    }
};

里面会有两个爆点XDD

• 第一个是 tmp+=sum会在tmp+上去>255的时候就错误，
• 第二个是sum+= shifts[i];>2,147,483,647会溢位

数值小的时候没问题，比较大的test case就坏了
那要怎麽解决呢？就擅用提早%26取余数来避免最後加总才太大了！
以下是修改後的版本，顺便直接拿题目的s直接修改了XD

class Solution {
public:
    string shiftingLetters(string s, vector<int>& shifts) {
        // record the total shift distance
        int sum=0;
        // iterate from the end
        for(int i = shifts.size() - 1; i >= 0; --i) {
            // mod in every round to ensure the range
            sum = (shifts[i] + sum) % 26;
            s[i] = (s[i]-'a'+sum)%26+'a';
        } 
        return s;
    }
};

结语

本来想说题目蛮简单，没想到还是可以复习到一些特别的地方~
最近在看C++ Primer这本书，可能可以顺便在这边提一些书中提到的东西。