Leetcode-字符串刷题记录

520. 检测大写字母

public boolean detectCapitalUse(String word) {
        int i = 0;
        char[] arr = word.toCharArray();
        int up = 0, low = 0;
        while(i < arr.length){
            if(arr[i] >= 'a'){
                low++;
            }else{
                up++;
            }
            i++;
        }
        if(up == arr.length) return true;
        if(low == arr.length) return true;
        if(up == 1 && arr[0] < 'a') return true;
        return false;
    }

125. 验证回文串

经典问题，需要过滤非字符非数字。

public boolean isPalindrome(String s) {
        if(s == null) return true;
        s = s.toLowerCase();
        StringBuilder str = new StringBuilder(s.length());
        for (char c : s.toCharArray()) {
            if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z')) {
                str.append(c);
            }
        }
        return str.toString().equals(str.reverse().toString());
    }

14. 最长公共前缀

• 首先计算出最短字符串的长度，这个长度就是外层循环的遍历次数。
• 内层逐个比较字符串的指定位置的值。
• 通过StringBuilder拼接公共前缀。

public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) 
            return "";
        StringBuilder sb = new StringBuilder();
        int minLength = 1000;
        //计算最短字符串长度
        for(String str : strs){
            if(str.length() < minLength){
                minLength = str.length();
            }
        }
        String demo = strs[0];
        for(int i = 0; i< minLength; i++){
            boolean flag = true;
            char c = demo.charAt(i);
            for(int j = 1; j < strs.length; j++){
                if(strs[j].charAt(i) != c){
                    //不等于
                    flag = false;
                    break;
                }
            }
            if(flag){
                sb.append(c);
                flag = true;
            }else{
                break;
            }
        }
        return sb.toString();
    }

434. 字符串中的单词数

一轮遍历即可，判断依据是：当前值是空格，前一位非空格

public int countSegments(String s) {
        if (s == null) {
            return 0;
        }
        s = s.trim();
        if (s.length() == 0) {
            return 0;
        }
        int count = 1;
        for (int i = 1; i < s.length(); i++) {
            // 当前值是空格，前一位非空格
            if (s.charAt(i) == 32 && s.charAt(i - 1) != 32) {
                count++;
            }
        }
        return count;
    }

58. 最后一个单词的长度

public int lengthOfLastWord(String s) {
        String[] s1 = s.split(" ");
        if(s1.length == 0) return 0;
        return s1[s1.length -1].length() == 0 ? 0 : s1[s1.length -1].length();
    }

344. 反转字符串

public void reverseString(char[] s) {
        int left = 0, right = s.length -1;
        while(left < right){
            swap(s , left, right);
            left++;
            right--;
        }
    }

    public void swap(char[] s, int i, int j){
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }

541 反转字符串Ⅱ

public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();
        for(int i = 0; i < arr.length; i+= 2*k){
            //每隔2k反转一次
            //判断剩余字符
            int rest = arr.length - i;
            if(rest < k){
               reverse(arr,i, arr.length - 1); 
            }else if(rest < 2 * k && rest >= k){
                reverse(arr,i, i + k - 1);
            }else{
                reverse(arr,i, i+k - 1);
            }
        }
        return String.valueOf(arr);
    }


    public void reverse(char[] s,int i, int j) {
        int left = i, right = j;
        while(left < right){
            swap(s , left, right);
            left++;
            right--;
        }
    }

    public void swap(char[] s, int i, int j){
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }

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

public String reverseWords(String s) {
        String[] strs = s.split(" ");
        String[] reverseString = new String [strs.length];
        int index = 0;
        for(String str : strs){
            reverseString[index++] = new StringBuffer(str).reverse().toString();
        }
        StringBuilder sb = new StringBuilder();
        for(int i =0; i < strs.length; i++){
            sb.append(reverseString[i]);
            if(i != reverseString.length - 1) sb.append(" ");
        }
        return sb.toString();
    }

151. 反转字符串中的单词

public String reverseWords(String s) {
        s = s.trim();
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }

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

public static int firstUniqChar(String s) {
        int[] letter=new int[26];
        for (char c:s.toCharArray()) {
            letter[c-'a']++;
        }
        for (int i = 0; i <s.length() ; i++) {
            if(letter[s.charAt(i)-'a']==1) {
                return i;
            }
        }
        return -1;
    }

389. 找不同

char findTheDifference(string s, string t) {
        vector<int> count(26,0);
        for(char ch : s){
            count[ch - 'a']++;
        }
        for(char ch : t){
            count[ch - 'a']--;
            if(count[ch - 'a'] < 0) return ch;
        }
        return ' ';
    }

383. 赎金信

bool canConstruct(string ransomNote, string magazine) {
        vector<int> count(26, 0);
        for(char ch : magazine){
            count[ch - 'a']++;
        }
        for(char ch : ransomNote){
            count[ch - 'a']--;
            if(count[ch - 'a'] < 0){
                return false;
            }
        }
        return true;
    }

242. 有效的字母异位词

bool isAnagram(string s, string t) {
        vector<int> cnt(26,0);
        for(char ch : s) cnt[ch - 'a']++;
        for(char ch : t) cnt[ch - 'a']--;
        for(int count : cnt) if(count != 0) return false;
        return true;
    }

49. 字母异位词分组

vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        map<string, vector<string>> map;
        for(int i =0; i < strs.size(); i++){
            string key = strs[i];
            sort(key.begin(), key.end());
            map[key].push_back(strs[i]);
        }
        for(auto ite = map.begin(); ite != map.end(); ite++) res.push_back(ite->second);
        return res;
    }

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

string frequencySort(string s) {
        map<char,int> map;
        for(char c : s) map[c]++;
        //sort
        vector<pair<char, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(), [](auto & a, auto & b){
            return a.second > b.second;
        });
        string res;
        for(auto v : vec) res += string(v.second,v.first);
        return res;
    }

657. 机器人能否返回原点

bool judgeCircle(string moves) {
        int index = 0;
        int updown = 0, rightleft = 0;
        while(index <= moves.length()){
            switch(moves[index]){
                case 'R':
                    rightleft++;
                    break;
                case 'L':
                    rightleft--;
                    break;
                case 'U':
                    updown++;
                    break;
                case 'D':
                    updown--;
                    break;
            }
            index++;
        }
        if(updown == 0 && rightleft == 0) return true;
        return false;
    }

551. 学生出勤记录Ⅰ

bool checkRecord(string s) {
        int late = 0, absent = 0;
        for(int i = 0; i < s.length(); i++){
            if(s[i] == 'A'){
                //absent
                absent++;
                late = 0;
                if(absent > 1) return false;
            }else if(s[i] == 'L'){
                late++;
                if(late > 2) return false;
            }else {
                //P
                late = 0;
            }
        }
        return true;
    }

28. 实现strStr()

int strStr(string haystack, string needle) {
        if ( needle == "" )
            return 0;
        int hlen = haystack.length();
        int nlen = needle.length();
        int i,j;
        for(i=0;i<hlen;i++){
            for(j=0;j<nlen;j++)
                if(haystack[i+j]!=needle[j])
                    break;      //不符合就结束本轮匹配
            if(j==nlen)
                return i;
        }
        return -1;
    }

8. 字符串转换整数

int myAtoi(string s) {
        int i=0; // 遍历的游标
        while(i<s.size()&&s[i]==' ') i++; // 去掉空白字符
        if(i==s.size()) return 0; // 如果s为全空
        
        // 处理第一个非空字符
        int sign=1;
        if(s[i]=='-'){
            sign=-1;
            i++;
        }
        else if(s[i]=='+')
            i++;
        else if(!isdigit(s[i]))
            return 0;

        // 处理第一个数字字符
        int n=0;
        while(isdigit(s[i])&&i<s.size()){
            if((INT_MAX-(s[i]-'0'))/10.0<n) return sign==-1?sign*INT_MAX-1:INT_MAX; // 如果溢出
            n=10*n+(s[i]-'0');
            i++;
        }
        return sign*n;
    }

67. 二进制求和

string addBinary(string a, string b) {
        string result;
        const int n = a.size() > b.size() ? a.size() : b.size();
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        int carry = 0;
        for(int i = 0; i < n; i++){
            int ai = i < a.size() ? a[i] - '0' : 0;
            int bi = i < b.size() ? b[i] - '0' : 0;
            int val = (ai + bi + carry) % 2;
            carry = (ai + bi + carry) / 2;
            result.insert(result.begin(), val + '0');
        }
        if(carry == 1) result.insert(result.begin(), '1');
        return result;
    }

412. Fizz Buzz

vector<string> fizzBuzz(int n) {
        vector<string> res;
        for(int i = 1; i <= n; i++){
            string tmp;
            if(i % 15 == 0){
                res.push_back("FizzBuzz");
            }else if(i % 5 == 0){
                res.push_back("Buzz");
            }else if(i % 3 == 0){
                res.push_back("Fizz");
            }else{
                res.push_back(to_string(i));
            }
            
        }
        return res;
    }

299. 猜数字游戏

需要注意数字出现的次数。

string getHint(string secret, string guess) {
        int bull = 0, cow = 0;
        vector<int> num(10,0);
        for(int i = 0; i < guess.size(); i++){
            if(guess[i] == secret[i]){
                bull++;
            }else {
                //当前位置不一致，需要判断当前字符是否出现在secret里面
                //通过vector存储数字出现次数
                if(num[secret[i] - '0']++ < 0) cow++;
                if(num[guess[i] - '0']-- > 0) cow++;
            }
        }
        return to_string(bull) + 'A' + to_string(cow) + 'B';
    }

506. 相对名次

vector<string> findRelativeRanks(vector<int>& score) {
        vector<int> org = score;
        sort(score.rbegin(), score.rend());
        unordered_map<int, string> order;
        for(int i = 0; i < score.size(); i++){
            if(i >= 3) order[score[i]] = to_string(i+ 1);
            if(i == 0) order[score[i]] = "Gold Medal";
            if (i == 1) order[score[i]] = "Silver Medal";
            if (i == 2) order[score[i]] = "Bronze Medal";
        }
        vector<string> res(score.size(), "");
        for(int i = 0; i < res.size(); i++){
            res[i] = order[org[i]];
        }
        return res;
    }

539. 最小时间差

• 将时间转换成分钟。
• 注意钟表是模运算。

int findMinDifference(vector<string>& timePoints) {
        vector<int> q;
        int res = INT_MAX;
        for(string t : timePoints){
            int hour = 10 * (t[0] - '0') + t[1] - '0';
            int min = 10 * (t[3] - '0') + t[4] - '0';
            q.push_back(60 * hour + min);
        }
        sort(q.begin(), q.end());
        q.push_back(q[0] + 24 * 60);
        for(int i = 1; i < q.size(); i++){
            res = min(res, q[i] - q[i - 1]);
        }
        return res;
    }

553. 最优除法

题解：被除数不变，除数最小，如果能理解这个数学知识，那么就是一道easy难度的题目。

string optimalDivision(vector<int>& nums) {
        if(nums.size() == 1){
            return to_string(nums[0]);
        }else if(nums.size() == 2){
            return to_string(nums[0]) + "/" + to_string(nums[1]);
        }
        string res(to_string(nums[0]) + "/(");
        for(int i = 1; i < nums.size() - 1; i++){
            res += to_string(nums[i]) + "/";
        }
        res += to_string(nums.back()) + ")";
        return res;
    }

38. 外观数列

public String countAndSay(int n) {
        String res = "1";
        for(int i = 2; i <= n; i++){
            StringBuilder temp = new StringBuilder();
            for(int j = 0; j < res.length(); j++){
                int count = 1;
                while(j + 1 < res.length() && res.charAt(j) == res.charAt(j + 1)){
                    j++;
                    count++;
                }
                temp.append(count).append(res.charAt(j));
            }
            res = temp.toString();
        }
        return res;
    }