451. 根据字符出现频率排序

  1. 哈希map存储{字符，频数}，自定义sort排序 ```cpp //yxc class Solution { public: string frequencySort(string s) {

    1.  unordered_map<char, int> cnt;
    2.  for (auto c: s) cnt[c] ++ ;
    3.  sort(s.begin(), s.end(), [&](char a, char b) {
    4.      //首先按频数排，其次按字典序排
    5.      if (cnt[a] != cnt[b]) return cnt[a] > cnt[b];
    6.      return a < b;
    7.  });
    8.  return s;

    } }; //sort比较器用Lambda表达式表示 class Solution { public: string frequencySort(string s) {

     unordered_map<char, int> s_count;
 for(auto &c : s) s_count[c] ++;

 vector<pair<char, int>> vec;
 for(auto &s : s_count) vec.push_back(s);

 sort(vec.begin(), vec.end(), [](pair<char, int> &a, pair<char, int> &b)
 {
     return a.second > b.second || (a.second == b.second && a.first < b.first);
 });

 string res; 

 for(auto &[c, i] : vec)
 {
     while(i --) res.push_back(c);
 }

 return res;

    } }; //sort比较器用结构体表示 struct cmp { bool operator()(pair &a, pair &b) {

     return a.second > b.second || (a.second == b.second && a.first < b.first);

    } };

class Solution { public: string frequencySort(string s) { unordered_map s_count; for(auto &c : s) s_count[c] ++;

    vector<pair<char, int>> vec;
    for(auto &s : s_count) vec.push_back(s);
    //cmp()有括号
    sort(vec.begin(), vec.end(), cmp());

    string res; 

    for(auto &[c, i] : vec)
    {
        while(i --) res.push_back(c);
    }

    return res;

}

};


2. 桶排序 buckets[频数] = 字符
```cpp
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> s_count;
        int maxFreq = 0;
        for(auto &c : s) maxFreq = max(maxFreq, ++ s_count[c]);

        vector<string> buckets(maxFreq + 1);
        for(auto &[ch, cnt] : s_count) buckets[cnt].push_back(ch);
        string res;
        for(int i = maxFreq; i > 0; i --)
        {
            string &bucket = buckets[i];
            for(auto &ch : bucket)
            {
                for(int k = 0; k < i; k ++)
                    res.push_back(ch);
            }
        }
        return res;
    }
};

NC97 字符串出现次数的TopK问题

struct cmp
{
    bool operator()(pair<int, string> &a, pair<int, string> &b)
    {
        return a.first > b.first || (a.first == b.first && a.second < b.second);
    }
};

class Solution {
public:
    /**
     * return topK string
     * @param strings string字符串vector strings
     * @param k int整型 the k
     * @return string字符串vector<vector<>>
     */
    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        // write code here
        //哈希map存储字符串频数
        unordered_map<string, int> s_count;
        for(auto &s : strings) s_count[s] ++;

        //小根堆存储频率最高的k个字符串，顺序由多到少
        priority_queue<pair<int, string>, vector<pair<int, string>>, cmp> q;

        for(auto &p : s_count)
        {
            if(q.size() < k) q.push({p.second, p.first});
            else
            {
                if(p.second > q.top().first || (p.second == q.top().first && p.first < q.top().second))
                {
                    q.pop();
                    q.push({p.second, p.first});
                }
            }
        }

        vector<vector<string>> res;
        while(k --)
        {
            res.push_back({q.top().second, to_string(q.top().first)});
            q.pop();
        }

        reverse(res.begin(), res.end());
        return res;
    }
};

520. 检测大写字母

题解1 题解2

//三种情况
//1.全部大写 2.全部小写 3.首字母大写
class Solution {
public:
    bool detectCapitalUse(string word) {
        int n = word.size();
        int small = 0, big = 0;
        for(int i = 0; i < n; i ++)
        {
            if(isupper(word[i])) big ++;
            else small ++;
        }

        if(small == n || big == n) return true;
        else if(big == 1 && isupper(word[0])) return true;

        return false;
    }
};

//改进
class Solution {
public:
    bool detectCapitalUse(string word) {
        int n = word.size();
        int big = 0;//记录大写字母个数
        for(int i = 0; i < n; i ++)
        {
            //至少有一个大写字母，且如果大写字母个数小于正在遍历的下标，返回不正确
            if(isupper(word[i]) && big ++ < i) return false;
        }

        //考虑其他情况，如果满足以下条件，返回正确
        //1. 有0或n个大写字母
        //2. 有1个大写字母，且大写字母个数等于正在遍历的下标，即只有第一个是大写字母
        return big <= 1 || big == n;

    }
};

125. 验证回文串

  • 数据预处理erase()，首尾对比

    class Solution {
public:
  bool isPalindrome(string s) {
      for(string :: iterator it = s.begin(); it != s.end(); it ++)
      {
          //isalnum()判断string的某个字符是否是数字或字母
          //string::erase(),删除迭代器所指的字符，迭代器指向下一个字符（已经包含了一个it++）
          if(!isalnum(*it)) s.erase(it --);
          else if(isupper(*it)) *it = tolower(*it);
      }

      //双指针
      int n = s.size();
      int left = 0, right = n - 1;
      while (left < right) {
         if (s[left] != s[right]) {
              return false;
          }
          ++left,--right;
      }
      return true;
  }
};

  • reverse()

    class Solution {
public:
  bool isPalindrome(string s) {
      string sgood;
      for(char ch : s)
          if(isalnum(ch)) sgood += tolower(ch);

      string sgood_rev(sgood.rbegin(), sgood.rend());
      return sgood == sgood_rev;
  }
};

  • 双指针

    class Solution {
public:
  bool isPalindrome(string s) {
      int n = s.size();
      int left = 0, right = n - 1;
      while (left < right) {
          while(left < right && !isalnum(s[left]))
              ++left;

          while(left < right && !isalnum(s[right]))
              --right;

          if (left < right) {
              if (tolower(s[left]) != tolower(s[right])) {
                  return false;
              }
              ++left;
              --right;
          }
      }
      return true;
  }
};

    14. 最长公共前缀

    题解

  • 横向扫描

时间复杂度O(mn),n表示字符串个数，m表示字符串平均长度
空间复杂度O(1)

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        //字符串数组strs为空，返回""
        if(!strs.size()) return "";

        int n = strs.size();//共有n个字符串
        string prefix = strs[0];
        //遍历strs，更新最长公共前缀，如果最长公共前缀为空，跳出循环
        for(int i = 1; i < n; i ++)
        {
            prefix = longestCommonPrefix(strs[i], prefix);
            if(!prefix.size()) break;
        }
        return prefix;
    }

    string longestCommonPrefix(string str1, string str2)
    {
        int length = min(str1.size(), str2.size());
        int index = 0;//更新最长公共前缀长度
        while(index < length && str1[index] == str2[index]) 
            index ++;

        return str1.substr(0, index);
    }


};
  • 纵向扫描

时间复杂度O(mn),n表示字符串个数，m表示字符串平均长度
空间复杂度O(1)

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        //字符串数组strs为空，返回""
        if(!strs.size()) return "";

        int n = strs.size();//共有n个字符串
        int m = strs[0].size();//第一个字符串长度为m

        for(int i = 0; i < m; i ++)//遍历列
        {
            char c = strs[0][i];//c存储第一个字符串的第i列
            for(int j = 1; j < n; j ++)//遍历行
            {
                //停止增加公共前缀的条件
                //1.第j个字符串长度等于i,即没有strs[j][i]不存在 或 2.strs[j][i]不等于c
                if(strs[j].size() == i || strs[j][i] != c)
                    return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }
};
  • 分治

时间复杂度:O（mn）
递推T(n) = 2T(n/2)+O(m)
IMG_20211221_205349_edit_66986761604360.jpg
空间复杂度：m 是字符串数组中的字符串的平均长度，n是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为logn，每层需要m的空间存储返回结果。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        //字符串数组strs为空，返回""
        if(!strs.size()) return "";
        else return longestCommonPrefix(strs, 0, strs.size() - 1);
    }

    string longestCommonPrefix(const vector<string>& strs, int start, int end)
    {
        if(start == end) return strs[start];//start和end相同，同一个字符串，不做处理，返回这个字符串
        else
        {
            int mid = (start + end) >> 1;
            string lcpleft = longestCommonPrefix(strs, start, mid);
            string lcpright = longestCommonPrefix(strs, mid + 1, end);
            return commonprefix(lcpleft, lcpright);
        }
    }

    string commonprefix(const string &lcpleft, const string &lcpright)
    {
        int minlen = min(lcpleft.size(), lcpright.size());
        for(int i = 0; i < minlen; i ++)
            if(lcpleft[i] != lcpright[i]) return lcpleft.substr(0, i);
        return lcpright.substr(0, minlen);
    }
};

434. 字符串中的单词数

题解

/*
    碰到每个单词的第一个下标，计数
    如何判断i是单词的第一个下标：
    1.s[i]不为空格且s[i-1]为空格
*/
class Solution {
public:
    int countSegments(string s) {
        int n = s.size();
        int cnt = 0;
        for(int i = 0; i < n; i ++)
        {
            //边界i = 0时，没有i - 1，满足s[i] != ' ' && i == 0时，计数
            if(s[i] != ' ' && (i == 0 || s[i - 1] == ' '))
                cnt ++;
        }

        return cnt;
    }
};

344. 反转字符串

class Solution {
public:
    void reverseString(vector<char>& s) {
    return reverse(s.rbegin(), s.rend());
    }
};

//双指针
class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1; 
        while(left < right)
        {
            swap(s[left], s[right]);
            left ++;
            right --;
        }
    }
    void swap(char &l, char &r)
    {
        char tmp = l;
        l = r;
        r = tmp;
    }
};

557. 反转字符串中的单词 III

题解
时间复杂度O(n) 空间复杂度O(1)

class Solution {
public:
    string reverseWords(string s) {
        int n = s.size();
        int i = 0, j = 0;
        while(i < n)
        {
            while(i < n && s[i] != ' ') i ++;//找到下一个空格

            int left = j, right = i - 1; //left单词起始，right单词结束
            while(left < right) swap(s[left ++], s[right --]);//单词反转

            j = i + 1;//当前空格加一，则为下一个单词的起始
            i ++;//i ++跳出当前空格
        }
        return s;
    }
};

387. 字符串中的第一个唯一字符

题解

  • 数组存储频数

时间复杂度O(n) 空间复杂度O(∣Σ∣)，∣Σ∣≤26

//数组存储频数 
//时间复杂度O(n),
//空间复杂度O(∣Σ∣)，其中Σ 是字符集，在本题中s只包含小写字母，
因此∣Σ∣≤26。需要O(∣Σ∣) 的空间存储数组。

class Solution {
public:
    int a[26];

    int firstUniqChar(string s) {
        int n = s.size();
        int res = 0;//结果
        for(int i = 0; i < n; i ++)
            a[s[i] - 'a'] ++;

        for(int i = 0; i < n; i ++)
            if(a[s[i] - 'a'] == 1) 
                return res = i;

        return -1;
    }
};
  • 哈希表存储频数

时间复杂度O(n) 空间复杂度O(∣Σ∣)，∣Σ∣≤26

//哈希表存储频数
//时间复杂度O(n),
//空间复杂度O(∣Σ∣)，其中Σ 是字符集，在本题中s只包含小写字母，
因此∣Σ∣≤26。需要O(∣Σ∣) 的空间存储哈希映射。
class Solution {
public:
    int firstUniqChar(string s) {
        int n = s.size();
        int res = 0;//结果
        unordered_map<int, int> frequency;

        for(char ch : s)
            frequency[ch] ++;

        for(int i = 0; i < n; i ++)
            if(frequency[s[i]] == 1) 
                return res = i;
        return -1;
    }
};
  • 哈希表存储索引

时间复杂度O(n) 空间复杂度O(∣Σ∣)，∣Σ∣≤26

//哈希表存储索引
//第一次遍历字符串
//键值对，键表示字符，值表示该字符首次出现的位置（该字符只出现一次）或表示-1（该字符出现多次）
//具体：如果哈希表里没有该字符，加入<字符，首次出现的位置>；如果有该字符，修改为<字符，-1>
//第二次遍历哈希表
//找出其中不为−1 的最小值，即为第一个不重复字符的位置。
//如果哈希映射中的所有值均为 -1，我们就返回 -1。

class Solution {
public:
    int firstUniqChar(string s) {
        int n = s.size();
        int res = 0;//结果
        unordered_map<int, int> position;

        for(int i = 0; i < n; i ++)
        {
            if(position.count(s[i])) position[s[i]] = -1;
            else position[s[i]] = i;
        }

        int first = n;//first存储第一个不重复字符的位置
        for(auto [_, pos] : position)
        {
            if(pos != -1 && pos < first)
                first = pos;
        }

        if(first == n) first = -1;//position中均为-1

        return first;
    }
};
  • 队列 ```cpp //哈希表存储索引 //第一次遍历字符串 //键值对，键表示字符，值表示该字符首次出现的位置（该字符只出现一次）或表示-1（该字符出现多次） //具体：如果哈希表里没有该字符，加入<字符，首次出现的位置>；如果有该字符，修改为<字符，-1> //第二次遍历哈希表 //找出其中不为−1 的最小值，即为第一个不重复字符的位置。 //如果哈希映射中的所有值均为 -1，我们就返回 -1。

class Solution { public: int firstUniqChar(string s) { int n = s.size(); int res = 0;//结果 unordered_map position; queue> q;

    for(int i = 0; i < n; i ++)
    {
        if(!position.count(s[i]))//s[i]没出现过
        {
            position[s[i]] = i;
            //在队尾插入字符 
            //push拷贝对象，emplace传入参数直接构造
            // q.emplace(s[i], i);
            q.push(make_pair(s[i], i));
        }
        else//s[i]已经出现过 
        {
            position[s[i]] = -1;
            while(!q.empty() && position[q.front().first] == -1)//在队列中弹出队头重复的字符
                q.pop();
        }
    }

    return q.empty()? -1 : q.front().second;
}

};

<a name="jinHB"></a>
#### [383. 赎金信](https://leetcode-cn.com/problems/ransom-note/)
[题解](https://leetcode-cn.com/problems/ransom-note/solution/gong-shui-san-xie-jian-dan-ji-shu-mo-ni-udpzn/)
```cpp
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if(ransomNote.size() > magazine.size()) return false;

        //对magazine中的字母计数 ++
        int cnt[26] = {0};
        for(int i = 0; i < magazine.size(); i ++)
            cnt[magazine[i] - 'a'] ++;

        //对ransomNote中的字母计数 --，如果该字母计数等于-1，说明magazine中没有，ransomNote有，返回false
        for(int i = 0; i < ransomNote.size(); i ++)
            if( -- cnt[ransomNote[i] - 'a'] < 0) return false;

        return true;
    }
};