leetcode404周赛（1，2，3）

1.三角形的最大高度

题意：给你两个整数red和blue，需要用这些求组成一个三角形，相邻行颜色必须不同，求最大高度

思路：第一行放一个，第二行放两个第三行放三个，我们可以按奇数偶数行来计算总和，此时有两种情况，先蓝后红，先红后蓝，此时针对于第i行来说，如果

先蓝后红 此时对应奇偶行的蓝的数量不够或者红的数量不够，同时在先红后蓝这种情况下，红的数量或者蓝的数量也不够，两种情况都不能填充第i行，那么最大高度为第i-1行

ac代码：

class Solution {
public:
    int maxHeightOfTriangle(int red, int blue) {
         int cnt[2]={0,0};

         for(int i=1;i<=2000;i++){
               cnt[i%2]+=i;
           if((cnt[0]>red||cnt[1]>blue)&&(cnt[0]>blue||cnt[1]>red))
                return i-1;    
         }


   return 0;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.z找出有效子序列的最大长度I

题意：给一个整数数组，有效子序列的定义为：

(sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2

返回数组的最长的有效子序列的长度

思路：模数是固定为2的，那么情况只有0，1，那么要使得相邻项数满足有效子序列的定义，则有四种情况，0000，1111，0101，1010，算出这四种情况的最大的长度取一个max

ac代码：

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        for(int i=0;i<nums.size();i++)
            nums[i]%=2;
    int cnt1=0,cnt2=0,cnt3=0,cnt4=0;

      for(int i=0;i<nums.size();i++)
          if(nums[i]==0)   cnt1++;

         for(int i=0;i<nums.size();i++)
          if(nums[i]==1)   cnt2++;

        int ok=0;
           for(int i=0;i<nums.size();i++)
           if(!ok&&nums[i]==0)    cnt3++,ok=1;
           else if(ok&&nums[i]==1) cnt3++,ok=0;

                 ok=0;
           for(int i=0;i<nums.size();i++)
           if(!ok&&nums[i]==1)    cnt4++,ok=1;
           else if(ok&&nums[i]==0) cnt4++,ok=0;     
     int res=max(cnt1,cnt2);
     res=max(res,cnt3);
     res=max(res,cnt4);
     return res;   
   
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

3.找出有效子序列的最大长度II

题意：和上一题一样，只是模数2换成了k

思路：通过这个式子(sub[i] + sub[i+1]) % k == (sub[i+1] + sub[i+2]) % k可以变形成为（sub[i] + sub[i+1]）-(sub[i+1] + sub[i+2])%k==0即(sub[i]-sub[i+2])%k==0，因此sub[i]和sub[i+2]同余，只要寻找一个最长的子序列，满足子序列奇数项都相同，偶数项都相同即可满足条件，因此我们可以设一个函数f[y][x]表示当前已i为结尾的数后两位(肯定为一奇一偶)，我们在这个后面添加nums[i],那么最后两项模k分别为x和y的子序列的长度会增加1

ac代码：

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int ans = 0;
        vector<vector<int>> f(k, vector<int>(k));
        for (int x : nums) {
            x %= k;
            for (int y = 0; y < k; y++) {
                f[y][x] = f[x][y] + 1;
                ans = max(ans, f[y][x]);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15