Blue Bridge Cup practice 008

Interview question 01.06 String compression

String compression. Using the number of character repetitions, write a method to realize the basic string compression function. For example, the string aabcccccaaa becomes a2b1c5a3. If the "compressed" string is not shorter, the original string is returned. You can assume that the string contains only uppercase and lowercase English letters (a to z).

Example 1:

Enter: "aabcccccaaa"
Output: "a2b1c5a3"

Example 2:

Input: "abbccd"
Output: "abbccd"
Explanation: "abbccd" is "a1b2c2d1" after compression, which is longer than the original string length.

Tips:

The string length is in the range of [0, 50000].

Source: LeetCode

Link: https://leetcode-cn.com/problems/compress-string-lcci

Problem solving ideas

The passed parameter is the string to be compressed. You can first save the first character of the string into the cur variable, and use a count variable to store the number of occurrences of the current character, initialize it to 1, and then traverse the string from the second position of the string for judgment.

If the current character cur is equal to the character at a certain position of the string, the value of count is added by one. If it is not equal, the current character and the value of count are spliced into the string variable to save the result. It should be noted that the variable count of int type needs to be used as to_ The string method is converted to a string type.

It should also be noted that when you get to the last position, because there is no comparison with the last character, you need to add the last part to the result after the loop ends.
After the conversion, the output needs to be controlled to judge whether the length after conversion is less than the previous length. If it is less than, the converted string will be output; otherwise, the string before conversion will be output.

code

class Solution {
public:
    string compressString(string S) {
        string ans = "";//Save results
        char cur = S[0];//Used to mark the current character
        int count = 1;//Number of current characters
        for (int i = 1; i < S.length(); i++) {//Traversal of strings
            if (cur != S[i]) {//The current character and the next character are not equal
                ans += cur + to_string(count);//Saves the current character and number to the result
                cur = S[i];//Replace the current character with the next character
                count = 1;//Quantity reset to 1
            }
            else count++;//The current character is equal to the next character, and the number is increased by one
        }
        ans += cur + to_string(count);//Deal with the last part
        return ans.length() < S.length() ? ans : S;//Return the one with shorter string according to the title requirements
    }
};

Sword finger Offer38 Arrangement of strings

Title Requirements

Enter a string and print out all the arrangements of characters in the string.

You can return this string array in any order, but there can be no duplicate elements.

Example:

Enter: s = "abc"
Output: ["abc", "acb", "bac", "bca", "cab", "cba"]

Limitations:

Length of 1 < = s < = 8

Source: LeetCode

Link: https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof

Problem solving ideas

code

class Solution {
public:
    vector<string> ret;//Storage results
    vector<string> permutation(string s) {
        f(s, 0);//Start with the first one
        return ret;
    }
    //Recursive solution of Full Permutation
    void f(string& s, int startIndex) {
        //Exit mechanism
        if (startIndex == s.length()) {//Save the results in ret when it comes to the end
            ret.push_back(s);
            return;
        }
        //Traverse backward from startIndex
        for (int i = startIndex; i < s.length(); i++) {
            //Add a judgment and return directly when the previous first word is the same as now
            bool isContinue = true;//sign
            for (int j = startIndex; j < i; j++) {
                if (s[j] == s[i]) {//If it has happened before, you don't have to change positions
                    isContinue = false;
                }
            }
            if (!isContinue) continue;//If this letter has appeared before, there is no need to exchange positions
            swap(s[startIndex], s[i]);//Arrange the exchange position of the current letter and the following letter completely
            f(s, startIndex + 1);//Find the next one
            swap(s[startIndex], s[i]);//Swap the letters you exchanged back
        }
    }
};