(贪心)leetcode 392. Is Subsequence, 771. Jewels and Stones, 463. Island Perimeter

题意：判断s是否为t的子序列。

思路：分别从s和t的开头开始遍历，若相等则索引同时加1，否则t的索引加1。

终止条件：若s已经遍历完，则说明在t中找到了s，返回true; 否则t已经遍历完了，返回false。

特殊情况：s为空，返回true。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if(s.empty())
            return true;
        int n = s.size(), m = t.size();
        int j=0, i=0;
        while(i<n && j<m){
            if(s[i] == t[j])
                i++;
            j++;
        }
        return i == n;
    }
};

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if(s.size() == 0) return true;
        int s_f = 0, t_f = 0;
        while(t_f<t.size()){
            if(s[s_f] == t[t_f]){
                if(s_f == s.size()-1)
                    return true;
                s_f ++;
                t_f ++;
            }
            else{
                t_f++;
            }
    
        }
        return false;
    }
};

与392是同样的思路。

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int cnt = 0;
        for(int j=0; j<J.size();j++){
            for(int i=0; i<S.size();i++){
                if(J[j] == S[i])
                    cnt++;
            }
        }
        return cnt;
    }
};

题意：求岛屿（矩阵中值为1）的周长。

思路：矩阵中若值为1则周长+4；若这个1的左边或上面也是1，则周长-2.

易错：i>0 && grid[i-1][j]==1 中判断 i>0 需要放在前面，否则会报栈溢出的错。

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        if(grid.empty() || grid[0].empty()) return 0;
        int cnt = 0;
        for(int i=0; i<grid.size();i++){
            for(int j =0; j<grid[0].size(); j++){
                if(grid[i][j] == 1){
                    cnt +=4;
                    if(i>0 && grid[i-1][j]==1)
                        cnt -= 2;
                    if(j>0 && grid[i][j-1] == 1)
                    //若1的左边或上面都是1，则-2
                        cnt -=2;
                }
            }
        }
        return cnt;
    }
};