leetcodeContest138

    1. Height Checker – easy
    1. Grumpy BookStore owner –medium
    1. Previous Permutation with One Step –medium
    1. Distant Barcodes –medium

1. Height Checker

  • solution
    • sort and check differ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int heightChecker(vector<int>& heights) {
       vector<int> tmp;
       for(auto it: heights){
           tmp.push_back(it);
       }
       sort(heights.begin(), heights.end());
       int res = 0;
       for(int i = 0; i < heights.size(); ++i){
           if(heights[i]!=tmp[i]){
               cout<<heights[i] <<endl;
               res++;
           }
       }
       return res;
   }

2. Grumpy Bookstore owner

solution: sliding window
when ungrumpy, all is set setisfied, otherwise we sliding window to count the max setSatisfied.
code style similar to TwoSum, which is on-fly process!

1
2
3
4
5
6
7
8
9
10
maxSatisfied(vector<int>& cs, vector<int> grumpy){
	auto satisfied = 0, totalAddSatisfied = 0, addSatisfied = 0;
	for(auto i = 0; i < cs.size(); i++){
		satisfied += grumpy[i] ? 0 : cs[i];
		addSatisfied += grumpy[i]? cs[i] : 0;
		if(i>=X) addSatisfied -= grumpy[i-X]?cs[i-X]:0;
		totalAddSatisfied = max(addSatisfied, totalAddSatisfied);
	}
	return satisfied + totalAddSatisfied;
}

My realtime solution during test, in which I pick out all the grumpy[i]==1 into a vector, and
process to max addSum. So the space complexity become bigger!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
        vector<pair<int,int>> mp;
        int res=0;
        for(int i = 0; i < grumpy.size(); i++){
            if(grumpy[i]==1){
                mp.push_back(make_pair(i,customers[i]));
            }
            res += grumpy[i]?0:customers[i];
        }
        int tmp_res = res;
        for(int i = 0; i < mp.size(); ++i){ 
            int j = i;
            int tmp = tmp_res;
            cout<<tmp<<endl;
            while(j<mp.size()&&mp[j].first-mp[i].first+1<=X){
                tmp += mp[j].second;
                j++;
            }
            res = max(res, tmp);
        }
        return res;
    }
};

3. Previous Permutation with One Step