leetcode-3

  1. 赎金信
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

bool canConstruct(string ransomNote, string magazine) {
    if(ransomNote.size()>magazine.size()){
        return false;
    }
    int hstable[26];
    for(auto i:magazine){
        hstable[i-'a']++;
    }
    for(auto i:ransomNote){
        hstable[i-'a']--;
        if(hstable[i-'a']<0){
            return false;
        }
    }
    return true;
}
  1. 汇总区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

vector<string> summaryRanges(vector<int>& nums) {
    vector<string> ret;
    int i=0;
    int n =nums.size();
    while(i<n){
        int low =i;
        i++;
        while(i<n &&nums[i]==nums[i-1]+1){
            i++;
        }
        int high =i-1;
        string tmp = to_string(nums[low]);
        if(low<high){
            tmp.append("->");
            tmp.append(to_string(nums[high]));
        }
        ret.push_back(tmp);
    }
    return ret;
}
  1. 文本左右对齐
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

string blank(int n){
    return string(n,' ');
}

string join(vector<string>&words,int left,int right,string sep){
    string s=words[left];
    for(int i=left+1;i<right;i++){
        s+=sep+words[i];
    }
    return s;
}

vector<string> fullJustify(vector<string>& words, int maxWidth) {
    vector<string>ans;
    int right=0;
    int n =words.size();
    while(1){
        int left =right;
        int sumLen =0;
        while(right<n && sumLen+words[right].length()+right-left<=maxWidth){
            sumLen+=words[right].length();
            right++;
        }

        if(right==n){
            string s= join(words,left,n," ");
            ans.emplace_back(s+blank(maxWidth-s.length()));
            return ans;
        }

        int numWords = right-left;
        int numSpaces = maxWidth-sumLen;

        if(numWords==1){
            ans.emplace_back(words[left]+blank(numSpaces));
            continue;
        }

        int aveSpace = numSpaces/(numWords-1);
        int extraSpace = numSpaces%(numWords-1);
        string s1 =join(words,left,left+extraSpace+1,blank(aveSpace+1));
        string s2 = join(words,left+extraSpace+1,right,blank(aveSpace));
        ans.emplace_back(s1+blank(aveSpace)+s2);

    }
        return ans;
}
  1. 合并区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if(intervals.size()==0){
        return {};
    }

    sort(intervals.begin(),intervals.end());
    vector<vector<int>> merged;
    for(int i=0;i<intervals.size();i++){
        int left = intervals[i][0];
        int right = intervals[i][1];
        if(!merged.size()||merged.back()[1]<left){
            merged.push_back({left,right});
        }
        else{
            merged.back()[1]=max(merged.back()[1],right);
        }
    }
    return merged;
  1. 找出字符串中第一个匹配项的下标
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int strStr(string haystack, string needle) {
    if(haystack.length()<needle.length()){
        return -1;
    }
    int left =0;
    for(;left<haystack.length();left++){
        int right = left+needle.length();
        if(right>haystack.length()){
            return -1;
        }
        if(haystack.substr(left,needle.length())==needle){
             return left;
        }
    }
    return -1;
}