面试经典 150 题:205,55

205. 同构字符串

【解题思路】 

来自大佬@Krahets

【参考代码】

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char, char> Smap, Tmap;
        for(int i=0; i<s.size(); i++){
            char a = s[i], b = t[i];
            //map容器存在该字符，且不等于之前映射的字符
            if((Smap.find(a) != Smap.end() && Smap[a] != b) || 
                (Tmap.find(b) != Tmap.end() && Tmap[b] != a))
                return false;
            //添加映射
            Smap[a] = b,  Tmap[b] = a;
        }
        return true;
    }
};

55. 跳跃游戏

【参考代码】

贪心，可以用动态规划

class Solution {
public:
    bool canJump(vector<int>& nums) { //贪心
        int size = nums.size();
        int maxstep = 0;
        for(int i=0; i<size; i++){
            if(i <= maxstep){ //在最远可以到达的位置的范围内
                maxstep = max(maxstep, i + nums[i]); //实时维护最远可以到达的位置
                if(maxstep >= size-1){
                    return true;
                }
            }  
        }
        return false;
    }
};