LeetCode + 《剑指Offer II》刷题笔记。

字符串

014. 字符串中的变位词

剑指 Offer II 014. 字符串中的变位词

双指针 + 哈希表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if(s2.length()<s1.length()) return false;
        vector<int> count(26);
        for(int i=0;i<s1.length();i++){
            count[s1[i]-'a']++;
            count[s2[i]-'a']--;
        }
        if(areAllZero(count)) return true;
        for(int i=s1.length();i<s2.length();i++){
            count[s2[i]-'a']--;
            count[s2[i-s1.length()]-'a']++;
            if(areAllZero(count)) return true; 
        }
        return false;
    }
    bool areAllZero(vector<int> count){
        for(int cnt:count){
            if(cnt!=0) return false;
        }
        return true;
    }
};

在上述函数checkInclusion中，第2个for循环中的下标i相当于第2个指针，指向子字符串的最后一个字符。第1个指针指向下标为i-s1.length()的位置。两个指针之间的子字符串的长度一直是字符串s1的长度。

  • 时间复杂度：O(m+n)。如果s1,s2的长度分别是m和n，基于双指针和哈希表的算法需要扫描字符串s1和s2各一次。
  • 空间复杂度是：O(1)。数组的长度是英文小写字母的个数（即26），是一个常数，也就是说，数组的大小不会随着输入字符串长度的变化而变化。

015. 字符串中的所有变位词

剑指 Offer II 015. 字符串中的所有变位词

 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

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen=s.length(),pLen=p.length();
        vector<int> res;
        if(sLen<pLen) return res;
        vector<int> count(26);
        int i=0;
        for(;i<pLen;i++){
            count[p[i]-'a']++;
            count[s[i]-'a']--;
        }
        if(areAllZero(count)) res.push_back(0);
        for(;i<sLen;i++){
            count[s[i]-'a']--;
            count[s[i-pLen]-'a']++;
            if(areAllZero(count)){
                res.push_back(i-pLen+1);
            }
        }
        return res;
    }
    bool areAllZero(vector<int> count){
        for(int cnt:count){
            if(cnt!=0) return false;
        }
        return true;
    }
};

 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

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen=s.length(),pLen=p.length();
        List<Integer> res=new LinkedList<>();
        if(sLen<pLen) return res;
        int[] count=new int[26];
        int i=0;
        for(;i<pLen;i++){
            count[p.charAt(i)-'a']++;
            count[s.charAt(i)-'a']--;
        }
        if(areAllZero(count)) res.add(0);
        for(;i<sLen;i++){
            count[s.charAt(i)-'a']--;
            count[s.charAt(i-pLen)-'a']++;
            if(areAllZero(count)){
                res.add(i-pLen+1);
            }
        }
        return res;
    }
    private boolean areAllZero(int[] count){
        for(int cnt:count){
            if(cnt!=0) return false;
        }
        return true;
    }
}
  • 时间复杂度：O(m+n)。如果s,p的长度分别是m和n，基于双指针和哈希表的算法需要扫描字符串s和p各一次。
  • 空间复杂度是：O(1)

016. 不含重复字符的最长子字符串

剑指 Offer II 016. 不含重复字符的最长子字符串

注意：s 由英文字母、数字、符号和空格组成。

多次遍历哈希表

 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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length()==0) return 0;
        int maxLen=1;
        //s 由英文字母、数字、符号和空格组成
        vector<int> count(256);
        int i=-1,j=0;
        for(;j<s.length();j++){
            count[s[j]]++;
            while(hasGreatThan1(count)){
                i++;
                count[s[i]]--;
            }
            maxLen=max(maxLen,j-i);
        }
        return maxLen;
    }
    bool hasGreatThan1(vector<int> count){
        for(int cnt:count){
            if(cnt>1) return true;
        }
        return false;
    }
};

避免多次遍历哈希表

真正关心的是哈希表中有没有比1大的数字，因为如果有大于1的数字就说明子数组中包含重复的数字。

可以定义一个变量countDup来存储哈希表中大于1的数字的个数，即子字符串中重复字符的个数。

每次向右移动第2个指针使子字符串包含更多字符时都会把哈希表中对应的数字加1。当一个字符对应的数字从1变成2时，表示该字符重复出现了，因此变量countDup加1。

当向右移动第1个指针删除子字符串中最左边的字符时，都会把哈希表中对应的数字减1。当一个字符对应的数字由2变成1时，该字符不再重复出现，因此变量countDup减1。

这样就去掉了hasGreatThan1这个多次遍历哈希表的函数，相比时间效率有所提高。

 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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length()==0) return 0;
        int maxLen=1;
        //s 由英文字母、数字、符号和空格组成
        vector<int> count(256);
        int i=-1,j=0;
        int countDup=0;
        for(;j<s.length();j++){
            count[s[j]]++;
            if(count[s[j]]==2){
                countDup++;
            }
            while(countDup>0){
                i++;
                count[s[i]]--;
                if(count[s[i]]==1){
                    countDup--;
                }
            }
            maxLen=max(maxLen,j-i);
        }
        return maxLen;
    }
};

017. 含有所有字符的最短字符串

剑指 Offer II 017. 含有所有字符的最短字符串

018. 有效的回文

剑指 Offer II 018. 有效的回文

筛选 + 判断

验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    bool isPalindrome(string s) {
        string sgood;
        for(char ch:s){
            if(isalnum(ch)){
                sgood+=tolower(ch);
            }
        }
        //使用字符串翻转API得到sgood的逆序字符串sgood_rev
        string sgood_rev(sgood.rbegin(),sgood.rend());
        return sgood==sgood_rev;
    }
};

注意：

使用字符串翻转API得到sgood的逆序字符串sgood_rev，使用的是rbegin()和rend()

如果把

string sgood_rev(sgood.rbegin(),sgood.rend());

写为：

string sgood_rev(sgood.end(),sgood.begin());

报错：

terminate called after throwing an instance of ‘std::length_error’ what():

basic_string::_M_create

时间复杂度：O(|s|)，其中 |s| 是字符串 s 的长度。

空间复杂度：O(|s|)

在原字符串上直接判断

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

class Solution {
public:
    bool isPalindrome(string s) {
        int left=0,right=s.length()-1;
        while(left<right){
            if(!isalnum(s[left])){
                left++;
            }else if(!isalnum(s[right])){
                right--;
            }else{
                if(tolower(s[left])!=tolower(s[right])) return false;
                left++;
                right--;
            }
        }
        return true;
    }
};
  • 时间复杂度：O(|s|)，其中 |s| 是字符串 s 的长度。
  • 空间复杂度：O(1)

019. 最多删除一个字符得到回文

剑指 Offer II 019. 最多删除一个字符得到回文

s 由小写英文字母组成。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    bool validPalindrome(string s) {
        int start=0,end=s.length()-1;
        while(start<end){
            if(s[start]!=s[end]){
                return isPalindrome(s,start+1,end) || isPalindrome(s,start,end-1);
            }
            start++;
            end--;
        }
        return true;
    }
    bool isPalindrome(string s,int start,int end) {
        while(start<end){
            if(s[start]!=s[end]) return false;
            start++;
            end--;
        }
        return true;
    }
};

020. 回文子字符串的个数

剑指 Offer II 020. 回文子字符串的个数

暴力枚举

枚举出所有的子串，然后再判断这些子串是否是回文。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int countSubstrings(string s) {
        int count=0;
        for(int i=0;i<s.length();i++){
            for(int j=i;j<s.length();j++){
                if(isPalindrome(s,i,j)){
                    count++;
                }
            }
        }
        return count;
    }
    bool isPalindrome(string s,int start,int end) {
        while(start<end){
            if(s[start]!=s[end]) return false;
            start++;
            end--;
        }
        return true;
    }
};
  • 时间复杂度：O(n^3)
  • 空间复杂度：O(1)

中心拓展

枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int countSubstrings(string s) {
        int count=0;
        for(int i=0;i<s.length();i++){
            count+=countPalindrome(s,i,i);
            count+=countPalindrome(s,i,i+1);
        }
        return count;
    }
    int countPalindrome(string s,int start,int end) {
        int count=0;
        while(start>=0 && end<s.length() && s[start]==s[end]){
            count++;
            //中心拓展 
            start--;
            end++;
        }
        return count;
    }
};
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)

777 Swap Adjacent in LR String

Two Pointers

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    bool canTransform(string start, string end) {
        if(start.length()!=end.length()) return false;
        int n=start.length();
        int i=0,j=0;
        while(i<n || j<n){
            while(i<n && start[i]=='X') i++;
            while(j<n && end[j]=='X') j++;
            if(i==n || j==n) return i==j;
            //relative order
            //L: true:startIndex>endIndex false:else
            //R: true:startIndex<endIndex false:else
            if(start[i]!=end[j]) return false;
            else if(start[i]=='L' && i<j) return false;
            else if(start[i]=='R' && i>j) return false;
            i++;
            j++;
        }
        return true;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

49 Group Anagrams

Sort:

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

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string,vector<string>> mp;
        for(string str:strs){
            string temp=str;
            sort(temp.begin(),temp.end());
            mp[temp].push_back(str);
        }
        for(auto it=mp.begin();it!=mp.end();it++){
            res.push_back(it->second);
        }
        return res;
    }
};
  • 时间复杂度：O(nklogk)
  • 空间复杂度：O(nk)

8 String to Integer (atoi)

 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

class Solution {
    public int myAtoi(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        //1.去空格
        int index = 0;
        while (index < len && chars[index] == ' ')
            index++;
        //2.排除极端情况 "    "
        if (index == len) return 0;
        //3.设置符号
        int sign = 1;
        char firstChar = chars[index];
        if (firstChar == '-') {
            index++;
            sign = -1;
        } else if (firstChar == '+') {
            index++;
        }
        int res = 0, last = 0; //last 记录上一次的res，以此来判断是否溢出
        while (index < len) {
            char c = chars[index];
            if (c < '0' || c > '9') break;
            int tem = c - '0';
            last = res;
            res = res * 10 + tem;
            if (last != res / 10)  //如果不相等就是溢出了
                return (sign == (-1)) ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            index++;
        }
        return res * sign;
    }
}

但这个代码使用C++过不了，会报Runtime Error: signed integer overflow.

Line 24: Char 20: runtime error: signed integer overflow: 912834723 * 10 cannot be represented in type ‘int’ (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:33:20

  • 时间复杂度：O(n)
  • 空间复杂度：O(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

class Solution {
public:
    int myAtoi(string s) {
        int len=s.length();
        int sign=1;
        int index=0;
        while(index<len && s[index]==' '){
            index++;
        }
        if(index==len) return 0;
        if(s[index]=='-'){
            index++;
            sign=-1;
        }else if(s[index]=='+'){
            index++;
        }
        int res=0;
        while(index<len){
            if(s[index]>'9' || s[index]<'0'){
                break;
            }
            char curChar=s[index];
            if (res > INT_MAX / 10 || (res == INT_MAX / 10 && (curChar - '0') > INT_MAX % 10)) {
                return INT_MAX;
            }
            if (res < INT_MIN / 10 || (res == INT_MIN / 10 && (curChar - '0') > -(INT_MIN % 10))) {
                return INT_MIN;
            }
            res=res*10+sign*(curChar-'0');
            index++;
        }
        return res;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)