分类 字符串 下的文章

根据字符出现频率排序

问题描述

给定一个字符串,请将字符串里的字符按照出现的频率降序排列。

示例 1:
输入:
"tree"
输出:
"eert"

解释:
'e'出现两次,'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外,"eetr"也是一个有效的答案。

示例 2:
输入:
"cccaaa"
输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外,"aaaccc"也是有效的答案。
注意"cacaca"是不正确的,因为相同的字母必须放在一起。

示例 3:
输入:
"Aabb"
输出:
"bbAa"

解释:
此外,"bbaA"也是一个有效的答案,但"Aabb"是不正确的。

注意'A'和'a'被认为是两种不同的字符。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sort-characters-by-frequency

思路

  • 基本思路是用map来实现。
  • 首先,对字符串s为空时,进行特判。
  • 然后,字符串s不为空时,遍历s,将字符和其出现次数之间形成k-v映射。按照出现次数对映射进行排序。
    按照排序后的映射,生成返回结果字符串ret。

题解

class Solution {
public:
    static bool cmp(pair<char,int> tmp1,pair<char,int> tmp2){
        return tmp1.second>tmp2.second;
    }
    string frequencySort(string s) {
        int n = s.size();
        string ret;
        if (n == 0) return ret;
        map<char,int> table;
        for(int i=0;i<n;i++){
            table[s[i]]++;
        }
        vector<pair<char,int>> tmp;
        for(auto each:table){
            tmp.push_back(each);
        }
        sort(tmp.begin(),tmp.end(),cmp);
        for(auto each: tmp){
            for(int i=0;i<each.second;i++){
                ret+=each.first;
            }
        }
        return ret;
    }
};

翻转字符串里的单词 II

问题描述

给定一个字符串,逐个翻转字符串中的每个单词。

示例:
输入: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
输出: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

注意:
单词的定义是不包含空格的一系列字符
输入字符串中不会包含前置或尾随的空格
单词与单词之间永远是以单个空格隔开的
进阶:使用 O(1) 额外空间复杂度的原地解法。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-words-in-a-string-ii

思路

  • 以空格为分隔,将每个单词提取出来。
  • 按照单词之间的倒序顺序,但是单词内部的正常顺序,将单词存到ret中。
  • 最后,返回ret即可。

题解

class Solution {
public:
    void reverseWords(vector<char> &s) {
        vector<char> ret;
        string tmp;
        vector<string> tmp1;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != ' ') {
                tmp += s[i];
            } else if (s[i] == ' ') {
                tmp1.push_back(tmp);
                tmp = "";
            }
        }
        tmp1.push_back(tmp);
        reverse(tmp1.begin(), tmp1.end());
        for (int i = 0; i < tmp1.size(); i++) {
            for (int j = 0; j < tmp1[i].length(); j++) {
                ret.push_back(tmp1[i][j]);
            }
            if (i != tmp1.size() - 1) {
                ret.push_back(' ');
            }
        }
        s=ret;
    }
};

翻转字符串里的单词

问题描述

给定一个字符串,逐个翻转字符串中的每个单词。

示例 1:
输入: "the sky is blue"
输出: "blue is sky the"

示例 2:
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。

示例 3:
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

说明:
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
 
进阶:
请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-words-in-a-string

思路

基本思路和之前做过的简化路径是一样的,只是这个更简单一些。
简化路径 https://www.irene.ink/archives/163/

题解

class Solution {
public:
    string reverseWords(string s) {
        string ret;
        int n=s.size();
        if(n==0) return ret;
        string tmp;
        stack<string> stack1;
        for(int i=0;i<n;i++){
            if(s[i]==' '){
                if(tmp!=""){
                    stack1.push(tmp);
                } 
                tmp="";
            } else{
                tmp+=s[i];
            }
        }
        if(tmp!=""){
            stack1.push(tmp);
            tmp="";
        }
        while (!stack1.empty()){
            ret+=stack1.top();
            ret+=" ";
            stack1.pop();
        }
        ret=ret.substr(0,ret.size()-1);
        return ret;
    }
};

简化路径

问题描述

# 以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。
在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径
请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能以 / 结尾。此外,规范路径必须是表示绝对路径的最短字符串。

示例 1:
输入:"/home/"
输出:"/home"
解释:注意,最后一个目录名后面没有斜杠。

示例 2:
输入:"/../"
输出:"/"
解释:从根目录向上一级是不可行的,因为根是你可以到达的最高级。

示例 3:
输入:"/home//foo/"
输出:"/home/foo"
解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。

示例 4:
输入:"/a/./b/../../c/"
输出:"/c"

示例 5:
输入:"/a/../../b/../c//.//"
输出:"/c"

示例 6:
输入:"/a//b////c/d//././/.."
输出:"/a/b/c"

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/simplify-path

思路

基本思路是用栈来实现。返回值是ret,ret最开始为"/"

  • 单词之间是通过“/“来隔开的。
  • 如果两个”/“之间是".",那么continu;如果是“..",如果栈不为空的话,弹出顶端元素。如果是正常的字母组合,那么将压入栈中。
    此处应该注意,路径的最后不是以“/”结尾,所以应该在遍历结束后,单独进行判断
  • 最后,我用两个栈实现了双端队列,来将栈中的内容存储到ret中

题解

class Solution {
public:
    string simplifyPath(string path) {
        string ret="/";
        stack<string> stack1;
        string tmp = "";
        for (int i = 0; i < path.size(); i++) {
            if (path[i] == '/') {
                if (tmp.size() == 0) {
                    continue;
                } else if (tmp == ".") {
                    tmp="";
                    continue;
                } else if (tmp == "..") {
                    tmp="";
                    if (!stack1.empty()) {
                        stack1.pop();
                    } else continue;
                } else{
                    stack1.push(tmp);
                    tmp="";
                }
            } else{
                tmp+=path[i];
            }
        }
        if(tmp==".."){
            if(!stack1.empty()) stack1.pop();
        } else if(tmp!="."&&tmp.size()!=0){
            stack1.push(tmp);
        }
        stack<string> stack2;
        while (!stack1.empty()){
            stack2.push(stack1.top());
            stack1.pop();
        }
        int flag=1;
        if(!stack2.empty()) flag=0;
        while (!stack2.empty()){
            ret+=stack2.top();
            stack2.pop();
            ret+="/";
        }
        if(flag==0) ret=ret.substr(0,ret.size()-1);
        return ret;
    }
};

解码方法

问题描述

一条包含字母 A-Z 的消息通过以下方式进行了编码:

'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串,请计算解码方法的总数。

示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"(1 2)或者 "L"(12)。

示例 2:
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/decode-ways

思路

作者:user8973
链接:https://leetcode-cn.com/problems/two-sum/solution/dong-tai-gui-hua-fen-lei-tao-lun-by-user8973/

题解

class Solution {
public:
    int numDecodings(string s) {
        int len = s.length();
        if (len == 0 || s[0] == '0') {
            return 0;
        }
        vector<int> dp(len + 1, 0);
        dp[0] = 1; dp[1]=1;
        for (int i = 1; i < len; i++) {
            if (s[i - 1] != '0') {
                int num = (s[i - 1] - '0') * 10 + (s[i] - '0');
                if (num >= 1 && num <= 26) {
                    dp[i + 1] = ((s[i] != '0') ? dp[i - 1] + dp[i] : dp[i - 1]);
                } else if (s[i] != '0') {
                    dp[i + 1] = dp[i];
                } else return 0;
            } else if (s[i] != '0') {
                dp[i + 1] = dp[i];
            } else return 0;
        }
        return dp[len];
    }
};