leetcode-每日打卡-day 1

leetcode 每日打卡

附上kuangbin大佬话激励自己:
人一我百，人十我万，追逐青春得梦想，怀着自信的心，永不放弃！
2020.2.8

---

记录下来自己做题时得思路，并不一定是最优解

#1282 用户分组

struct node{
    int id, group;
};
bool cmp(node a,node b){return a.group < b.group;} 
class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<node> tmp;
        for(int i = 0;i < groupSizes.size();i ++)
            tmp.push_back({i,groupSizes[i]});
        sort(tmp.begin(),tmp.end(),cmp);
        int index = 0;
        while(index < groupSizes.size())
        {
            vector<int> now;
            for(int i = index;i < index + tmp[index].group;i ++)
                now.push_back(tmp[i].id);
            index += now.size();
            ans.push_back(now);
        }
        return ans;       
    }
};

#1221 分割平衡字符串

class Solution {
public:
    int balancedStringSplit(string s) {
        int ans = 0, k = 0;
        for(int i = 0;i < s.size();i ++)
        {
            if(s[i] == 'L')k++;
            if(s[i] == 'R')k--;
            if(k == 0)ans ++;
        }
        return ans;
    }
};

#861 翻转矩阵后的得分

class Solution {
public:
    void turncol(int col,vector<vector<int>>& A){
        for(int i = 0;i < A.size();i++){
            A[i][col] ^= 1;
        }
    }
    void turnrow(int row,vector<vector<int>>& A){
        for(int i = 0;i < A[0].size();i++){
            A[row][i] ^= 1;
        }
    }
    int matrixScore(vector<vector<int>>& A) {
        // 优先考虑第一列全部换成 1
        for(int i = 0;i < A.size();i ++){
            if(A[i][0] != 1){
                turnrow(i,A);
            }
        }
        // 确保这一列 count(1) > count(0)
        for(int i = 1;i < A[0].size();i ++){
            int count1 = 0,count0 = 0;
            for(int j = 0;j < A.size();j ++){
                if(A[j][i] == 1)count1++;
                else count0++;
            }
            if(count0 > count1)turncol(i,A);
        }
        int ans = 0;
        for(int i = 0;i < A.size();i ++){
            int k = 1;
            for(int j = A[i].size() - 1;j >= 0;j--){
                if(A[i][j])ans += k;
                k *= 2;
            }
        }
        return ans;
    }
};

#921 使括号有效的最少添加

class Solution {
public:
    int minAddToMakeValid(string S) {
        int l = 0,r = 0;
        for(int i = 0;i < S.size();i ++){
            if(S[i] == '(') l++;
            if(S[i] == ')'){
                if(l > 0)l--;
                else r++;
            }
        }
        return l + r;
    }
};

#763 划分字母区间

class Solution {
public:
    vector<int> ans;
    vector<int> partitionLabels(string S) {
        map<char,int> lastindex;
        for(int i = 0;i < S.size();i ++){
            lastindex[S[i]] = i;
        }
        //从头开始遍历 如果遇到一个新的字母就得出他最后出现位置得值
        //和当前最大得位置比较如果遍历到最大得位置还没有出现新的字母就将其加入答案
        int i = 0;
        int maxl = lastindex[S[0]];
        while(i < S.size()){
            int len = 0;
            for(;i <= maxl;i++){
                maxl = max(maxl,lastindex[S[i]]);
                len++;
            }
            ans.push_back(len);
            len = 0;
            maxl = lastindex[S[i]];
        }
        return ans;
    }
};