LeetCode(1)

优美子数组

将输入的数组逐个取模，得到一个新的数组，计算其前缀和数组

子数组(i到j)中如果恰好有K个1，即和为K，那么这个数组就满足了题目要求，有K个奇数数字

转化: sum[i] - sum[j] == k 等价于 sum[j] == sum[i]-k

此时遍历每一个i，统计j的个数即可

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int len = nums.size();
        vector<int> sum(len+1);
        vector<int> count(len+1);

        for (int i=0;i<len;i++) {
            sum[i+1] = nums[i] % 2 + sum[i]; 
        }
        for (int i=0;i<len+1;i++) {
            count[sum[i]]++; 
        }

        int ans = 0;
        for (int i=0;i<len+1;i++) {
            if (sum[i] - k >= 0) {
                ans += count[sum[i]-k];
            }
        }
        return ans;
    }
};

多米诺和托米诺平铺

第i列后正方形未被瓷砖覆盖，则第i列的正方形有4种被覆盖的情况:

1. 一个正方形都未被覆盖，状态记为0

2. 只有上方正方形被覆盖，状态记为1

3. 只有下方正方形被覆盖，状态记为2

4. 上下两个正方形被覆盖，状态记为3

写出状态转移方程

const long long mod = 1e9 + 7;
class Solution {
public:
    int numTilings(int n) {
        vector<vector<long long>> dp(n+1,vector<long long>(4));
        dp[0][3] = 1;
        for (int i=1;i<=n;i++) {
            dp[i][0] = dp[i-1][3];
            dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % mod;
            dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % mod;
            dp[i][3] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]) % mod;
        }
        return dp[n][3];
    }
};

Determine if String Halves Are Alike

先将字符串分半，然后遍历两个字串，使用find_first_of可以判断是否含有元音字母，统计个数后进行比较

class Solution {
public:
    bool halvesAreAlike(string s) {
        string vowels = "aeiouAEIOU";
        string a = s.substr(0,s.size()/2);
        string b = s.substr(s.size()/2);

        int count1 = 0,count2 = 0;
        for (int i=0;i<a.size();i++) {
            if (vowels.find_first_of(a[i]) != string::npos) {
                count1++;
            }
        }
        for (int i=0;i<b.size();i++) {
            if (vowels.find_first_of(b[i]) != string::npos) {
                count2++;
            }
        }
        return count1 == count2;
    }
};