基礎(chǔ)知識：

字符串長度： int length = s.length(); /length = s.size():不包括‘\0'

【面試題49：把字符串轉(zhuǎn)換成整數(shù)】String to Integer (atoi)

題目：實現(xiàn)一個函數(shù)stringToInt,實現(xiàn)把字符串轉(zhuǎn)換成整數(shù)這個功能谱俭，不能使用atoi或者其他類似的庫函數(shù)。

I think we only need to handle four cases:
discards all leading whitespaces
sign of the number
overflow
invalid input

【面試題04：替換空格】

題目：請實現(xiàn)一個函數(shù)弯屈，把字符串中的每個空格替換成"%20"，例如“We are happy.”全释，則輸出“We%20are%20happy.”已骇。
思路：先確定空格數(shù)量以及替換后字符串長度孝凌，然后從后往前遍歷完成移動方咆。時間復(fù)雜度O(n)。

class Solution {
public:
    void replaceSpace(char *str,int length) {
        int count=0; 
        int strlength =0;
        int i =0 ;
        while(str[i] != '\0'){
            if (str[i] == ' ' )
                count++;
            strlength ++;
            i++;
        } 
        int newlength = strlength + 2*count;
        int p1 = strlength;
        int p2 = newlength;
        while( p1 >= 0 && p2>p1){
            if( str[p1--] == ' '){ 
                str[p2--] = '0';  str[p2--] = '2'; str[p2--] = '%';
            }
            else
                str[p2--] = str[p1--];
        }
    }
};

【面試題53：正則表達(dá)式匹配】Regular Expression Matching

題目：請實現(xiàn)一個函數(shù)用來匹配包括'.'和 '*' 的正則表達(dá)式胎许。模式中的字符'.'表示任意一個字符峻呛，而'*'表示它前面的字符可以出現(xiàn)任意次（包含0次）。 在本題中辜窑，匹配是指字符串的所有字符匹配整個模式钩述。例如，字符串"aaa"與模式"a.a"和"abaca"匹配穆碎，但是與"aa.a"和"ab*a"均不匹配牙勘。

class Solution {
public:
    bool isMatch(string s, string p) {  
        /*
        if 第二個字符為‘*’
            if 第一個字符相等
                三種情況
            else
                Match(sPos,pPos+2,s,p);
        else
            if 第一個字符相等
                Match(sPos+1,pPos+1,s,p);
            else
                false
        */
        return Match(0,0,s,p); 
    }
    bool Match(int sPos, int pPos, string &s, string &p) {
        //s結(jié)束，p結(jié)束所禀，返回true
        if(sPos >= s.length() && pPos >= p.length())
            return true;
        //s未結(jié)束方面，p結(jié)束，返回false
        if(sPos < s.length() && pPos >= p.length())
            return false;
        //p未結(jié)束色徘，不管s結(jié)束沒恭金，都有可能匹配成功
        if(pPos+1 < p.length() && p[pPos+1] == '*'){ 
            if(sPos<s.length() && (s[sPos] == p[pPos] || p[pPos] == '.'))
                return Match(sPos,pPos+2,s,p)
                ||Match(sPos+1,pPos+2,s,p)
                ||Match(sPos+1,pPos,s,p);
            else
                return Match(sPos,pPos+2,s,p);
        } 
        if(sPos<s.length() && (s[sPos] == p[pPos] || p[pPos] == '.'))
            return Match(sPos+1,pPos+1,s,p);    
        return false;
    } 
};

【面試題54：表示數(shù)值的字符串】

題目：請實現(xiàn)一個函數(shù)用來判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）。例如褂策，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數(shù)值横腿。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
思路：逐字符掃描斤寂，A.Be/EC耿焊，A、C有符號遍搞，B無符號罗侯。.前后不能都沒數(shù)，e/E前后必有數(shù)溪猿。

class Solution {
public:
    bool isNumber(string s) {
        if(s.empty())
            return false;
        int pos = 0;
        //" 0.1 " => true钩杰，開頭空格情況
        while(pos<s.length() && s[pos] == ' ')
            pos++;
        bool result = isInt(s,pos);
        if(pos<s.length() && s[pos] == '.'){ 
            if(++pos<s.length())
                result = isUnsignedInt(s,pos) || result; 
            else
                return result;
        }
        if(pos<s.length() && (s[pos] == 'e' || s[pos] =='E')){ 
            if(++pos<s.length())
                result = isInt(s,pos) && result;
            else
                return false;
        }
        //“1  ” =>true，結(jié)尾空格情況
        while(pos<s.length() && s[pos] == ' ')
            pos++;
        return result && (pos == s.length());
    }
    
    bool isInt(string &s, int &pos){ 
        if(s[pos] == '+' || s[pos] == '-')
            pos++;
        return isUnsignedInt(s,pos);
    }
    
    bool isUnsignedInt(string &s, int &pos){
        bool result = false;
        while(pos<s.length() && (s[pos]>='0' && s[pos]<='9')){
            pos++;
            result = true;
        } 
        return result;
    }
};

【面試題28：字符串的排列】

題目： 輸入一個字符串,按字典序打印出該字符串中字符的所有排列诊县。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba榜苫。
思路：回溯，先提二叉樹的遍歷翎冲，以二叉樹中和為某一值的路徑為例（路徑以根節(jié)點開始，即對應(yīng)前序遍歷）媳荒，從根節(jié)點一直左子樹遍歷到葉節(jié)點抗悍，每次將根節(jié)點壓入vector驹饺，然后回溯到父節(jié)點并刪除當(dāng)前vector中節(jié)點，然后遍歷其右子樹缴渊。
該問題類似多叉樹赏壹，從左往右遍歷字符，每個字符與之后所有字符（包括自己）交換衔沼，一直到最后一個字符蝌借，產(chǎn)生深度為串長度的多叉樹。在進行回溯時需要通過循環(huán)遞歸（不像二叉樹指蚁，只有左右子樹菩佑，展開來寫）。從左往右每個數(shù)分別跟之后的交換凝化，然后處理下個數(shù)稍坯。遞歸結(jié)束的條件是處理到最后一個數(shù)字。ps:已經(jīng)說不清楚了

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string>result;
        if(str.empty())
            return {};
        Permutation(str,0,result);
        //從小到大排序
        sort(result.begin(), result.end());
        return result;
    }
    void Permutation(string &str, int pos, vector<string> &result){ 
        //當(dāng)遍歷到最后一個字符是輸出搓劫；類似于樹的葉節(jié)點瞧哟。
        //不同問題不同條件，如最短路徑枪向，統(tǒng)計路徑小于最短勤揩，則更新路徑；
        if(pos == str.length()-1)
            result.push_back(str);
        //循環(huán)接下來所有字符秘蛔，類似多叉樹陨亡，二叉樹，只需循環(huán)左右子樹缠犀。
        //當(dāng)一次遍歷到葉節(jié)點時数苫，要回溯，需要swap回來辨液，類似回到父節(jié)點虐急，然后到下個葉節(jié)點。
        for(int i=pos; i<str.length();i++){
            if( pos == i || str[pos] != str[i]){
                swap(str[pos],str[i]);
                Permutation(str,pos+1,result);
                swap(str[i],str[pos]); //返回父節(jié)點滔迈，恢復(fù)當(dāng)一次交換               
            } 
        }  
        
    }
};

【面試題46：把數(shù)字翻譯成字符串】 Decode Ways

題目：給定一個數(shù)字止吁，按照如下規(guī)則翻譯成字符串：1翻譯成“a”，2翻譯成“b”...26翻譯成“z”燎悍。一個數(shù)字有多種翻譯可能敬惦，例如12258一共有5種，分別是bccfi谈山，bwfi俄删，bczi，mcfi，mzi畴椰。實現(xiàn)一個函數(shù)臊诊，用來計算一個數(shù)字有多少種不同的翻譯方法。
思路：動態(tài)規(guī)劃斜脂，f(n) = f(n-1) + coef(n,n-1)*f(n-2),遇特殊情況：1)開頭遇0抓艳，直接return；2）中間遇10或20帚戳，f(i) = f(i-2)玷或，否則return。

//來自leetcode片任，0沒有對應(yīng)的碼子偏友，只有10和20能翻譯
class Solution {
public:
    int numDecodings(string s) {
        if(s.empty()) 
            return 0; 
        int* counts = new int[s.length()]; 
        if(s[0] == '0') return 0;
        counts[0] = 1;
        
        for(int i=1;i<s.length();i++){    
            int digit1 = s[i] - '0'; 
            int digit2 = s[i-1] -'0';
            if(digit1 == 0){ 
                if(digit2 == 1 || digit2 == 2){
                    counts[i] = (i == 1 ? 1: counts[i-2]);
                    continue; 
                }//遇到10或20，counts[i] = counts[i-2]
                else
                    return 0; 
            }  
            int coefficient = 0;
            int judgeDigit = digit2*10 + digit1;
            if(judgeDigit>=10 && judgeDigit<=26)
                coefficient = 1;   
            counts[i] = counts[i-1] + coefficient * ( i == 1 ? 1: counts[i-2]);
        }
        int result = counts[s.length()-1];
        delete[] counts;
        return result;
        
    }
};

【面試題48：最長不含重復(fù)字符的子字符串】

題目：請從字符串中找出一個最長的不包含重復(fù)字符串的子字符串蚂踊，計算該最長子字符串的長度约谈。假設(shè)字符串中只包含‘a(chǎn)’~‘z’的字符。
思路：動態(tài)規(guī)劃犁钟，f(i)定義為第i個字符結(jié)尾時最長子字符串的長度棱诱。關(guān)于f(i),分兩種情況：1）第i個字符之前從未出現(xiàn)，或之前出現(xiàn)涝动，但距離第i個字符的長度d大于f(i-1)(即上一個最長字符串長度)迈勋。這時f(i) = f(i-1)+1；2）之前出現(xiàn)醋粟，且位于f(i-1)中靡菇，這時f(i) = d,即被更新成以第i個字符結(jié)尾的最長串長度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        int position[128];
        for(int i = 0; i<128;i++)
            position[i]=-1;
        int curLength = 0;
        int maxLength = 0;
        for(int i =0; i<s.size();i++){
            int prePos = position[s[i]-' '];
            if(prePos<0 ||i-prePos>curLength)
                curLength++;
            else{
                curLength = i-prePos;
            }
            position[s[i]-' ']= i; //更新字符坐標(biāo)
            if(curLength>maxLength)
                maxLength = curLength;
        }
        return maxLength;
    }
};

【面試題50：第一個只出現(xiàn)一次的字符】First Unique Character in a String

題目：請實現(xiàn)一個函數(shù)用來找出字符流中第一個只出現(xiàn)一次的字符米愿。
思路：map計數(shù)

class Solution {
public:
    int firstUniqChar(string s) {
        map<char,int>mapping;
        for(int i = 0 ; i< s.size();i++){
            mapping[s[i]]++;
        }
        for(int i = 0; i < s.size(); i++){
            if(mapping[s[i]]==1)
                return i;
        }
        return -1;
    }
};

Buddy Strings

題目：給定字符串A和B厦凤，判斷A是否僅交換兩個字符能與B相等。
思路：遍歷A育苟，找到第一個與B不同的字符较鼓，然后接著找到第二個與B不同的字符，然后交換兩個字符违柏，判斷是否相等博烂。時間復(fù)雜度O(n)。ps：存在A==B的特殊情況漱竖，單獨考慮禽篱。

class Solution {
public:
    bool buddyStrings(string A, string B) {
        if (A.size() != B.size())  return false;
        if(A == B) return isDifferent(A);//如A等于B，若A中有相同字符馍惹，即true躺率，否則false玛界；
        int pos1 = 0;
        while(pos1<A.size() && (A[pos1] == B[pos1]))
            pos1++;
        int pos2 = pos1+1;
        while(pos2<A.size() && (A[pos2] == B[pos2]))
            pos2++;
        int temp = A[pos1];
        A[pos1] = A[pos2];
        A[pos2] = temp;
        return A==B? true:false;
    }
    bool isDifferent(string A){
        map<char,int>count;
        for(int i =0 ; i<A.size();i++){
            count[A[i]]++;
            if(count[A[i]] >1)
                return true;
        }
        return false;
    }
};

Construct String from Binary Tree

題目：You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.
思路：二叉樹的先序遍歷，同時需要考慮括號肥照，左子樹必須加括號脚仔，右子樹非空時加括號。

Example 1:
Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     

Output: "1(2(4))(3)"

Example 2: 如無左節(jié)點舆绎，用null，空().
Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 

Output: "1(2()(4))(3)"

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* t) {
        string res ;
        ConstructStr(t,res);
        return res; 
    }
    void ConstructStr(TreeNode* t, string &res){
        if(!t) return;
        res += to_string(t->val);
        if(!t->left && !t->right) return; 
        
        res += '(';
        ConstructStr(t->left,res);
        res += ')';
        
        if( !t->right ) return; //若無右子樹们颜，則返回吕朵。與無左子樹不同。
        res += '(';
        ConstructStr(t->right,res);
        res += ')'; 
    }
};

Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

創(chuàng)建一個map： map<char,int>mapping = {{},{},{}};
該字符值大于下一字符值就累加窥突，小于累減努溃。

class Solution {
public:
    int romanToInt(string s) {
        int sum =0;
        map<char,int>mapping={
            {'I',1},
            {'V',5},
            {'X',10},
            {'L',50},
            {'C',100},
            {'D',500},
            {'M',1000} 
        };
        for(int i =0; i < s.length()-1; i++){
            if(mapping[s[i]]>=mapping[s[i+1]])
                sum += mapping[s[i]];
            else
                sum -= mapping[s[i]];
        }
        sum += mapping[s[s.length()-1]];
        return sum;
    }
};

Valid Parentheses

題目：Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

[],{},(),成對出現(xiàn)，采用棧的數(shù)據(jù)結(jié)構(gòu)阻问，先進后出梧税。先進棧的符號之后配對。
判斷條件：空棧称近，即所有左開口符號均配對成功第队。不成立條件：1）空棧時遇上右開口；2）非空棧時刨秆，遇上右開口與出棧的左開口不配對凳谦。

class Solution {
public:
    bool isValid(string s) {
        map<char,char>mapping = {{'(',')'},{'{','}'},{'[',']'}};
        stack<char>pareStack;
        for(int i = 0; i<s.size(); i++){
            if(s[i] == '(' || s[i] == '{' ||s[i] == '[')
                pareStack.push(s[i]);
            else{
                if(pareStack.empty())
                    return false;
                if(s[i] != mapping[pareStack.top()])
                    return false;
                pareStack.pop();
            }
        } 
        return pareStack.empty();
    }
};

Add Binary

題目：Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
思路： 數(shù)字字符轉(zhuǎn)數(shù)字：s[i]-'0'; 數(shù)字轉(zhuǎn)字符：to_string

class Solution {
public:
    string addBinary(string a, string b) {
        int Pa = a.size()-1;
        int Pb = b.size()-1;
        int overflow = 0;
        string addStr = "";
        while(Pa>= 0 || Pb>= 0){
            int aStr = Pa>-1 ? a[Pa]-'0': 0;
            int bStr = Pb>-1 ? b[Pb]-'0': 0;
            addStr += to_string((aStr+bStr+overflow)%2);
            overflow = (aStr+bStr+overflow)/2;
            Pa--;Pb--;
        }
        if(overflow)
            addStr += '1';  
        changeChars(addStr,0,addStr.size()-1);
        return addStr;
    }
    void changeChars(string &s, int begin, int end){
        while(begin<end){
            char temp = s[begin]; 
            s[begin] = s[end];
            s[end] = temp;
            begin++;end--;
        }
    }
};

Longest Common Prefix

題目：寫一個函數(shù)，找到數(shù)組中字符串元素的最長公共字首衡未，如無公共字符尸执，返回空字符串。
思路：先確定前兩個字符串的公共字首缓醋，然后將公共字首與第三個比較如失，以此類推，確定最后的最長公共字首送粱。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        string samestr = strs[0];
        for (int i =1;i<strs.size();i++){
            samestr = JudgeSameStr(samestr, strs[i]);  
            if(samestr.empty()) return samestr;
        }
        return samestr;
    }
    string JudgeSameStr(string str1,string str2){ 
        string samestr ="";
        for(int j=0; j<str1.size();j++){
            if(j>str2.size()-1 || str1[j]!=str2[j]) return samestr;
            samestr += str1[j];
        } 
        return samestr;
    }
};

Reverse Words in a String III

題目：Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
思路：分兩部分：1)確定每個word的起始點褪贵；2）每個word進行reverse。
PS：判斷word結(jié)尾的兩種情況葫督，1）空格 竭鞍；2）串尾

class Solution {
public:
    string reverseWords(string s) {
        int begin = 0;
        int end = 0;
        while(end<s.size()){
            if(s[end] == ' '){
                changeChars(s,begin,--end);
                begin = end = end+2;
            } 
            else if(end == s.size()-1){
                changeChars(s,begin,end++);
            }
            else{
                end++;
            }
        }
        return s;
        
    }
    void changeChars(string &s, int begin, int end){
        while(begin<end){
            char temp = s[begin]; 
            s[begin] = s[end];
            s[end] = temp;
            begin++;end--;
        }
    }
}; 

void TransStr(string &str, int begin, int end){
    if(!str.empty()){
        while(begin<end)
            swap(str[begin++],str[end--]);
    }
}
int main(){
    string str;
    while(getline(cin,str)){
        if(str.empty() || str.length()>100)
            return 0;
        TransStr(str,0,str.length()-1);
        int begin = 0;
        int end = 0;
        while(end < str.length()){
            if(str[begin] == ' '){
                begin++;
                end++;
            }
            while(end < str.length() && str[end] != ' ')
                end++;
            TransStr(str,begin,end-1);
            begin = end; 
        }
        for(int i=0; i<str.length();i++)
            cout<<str[i];
    }
    return 0;
}

Longest Valid Parentheses

題目：Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring。
思路：由于括號先進后出規(guī)律橄镜，采用棧的結(jié)構(gòu)偎快，我們需要通過計算坐標(biāo)找出最長子串的長度，所以棧中存放的是括號在主串的位置洽胶。計算規(guī)律：一次匹配意味著一次出棧晒夹，計算此時坐標(biāo)與棧頂?shù)木嚯x壹店，即為此時的有效子串長度。注意棧頂元素的意義技羔，向前未匹配有效的坐標(biāo)蚀同。如果沒有出棧條件，均入棧读跷。一種情況是空棧梗搅，意味著此時坐標(biāo)之前的串均有效。

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int>sequence;
        int max = 0;
        for(int i=0; i<s.size(); i++){ 
            if(s[i] == ')' && !sequence.empty() && s[sequence.top()] == '('){
                sequence.pop();
                int length = sequence.empty()? i+1: i-sequence.top();
                max = std::max(length, max);
            }
            else 
                sequence.push(i);
        }
        return max;
    }
};

Push Dominoes

題目：用字符定義骨牌的狀態(tài)效览，‘L’代表向左倒无切，‘R’代表向右倒，‘.’代表讓為站立丐枉。例如".L.R...LR..L.."哆键，輸出為"LL.RR.LLRRLL.."。
思路：考慮清楚三種情況：1）RL形成區(qū)間瘦锹，2）從左往右籍嘹，只有L，3）從左往右弯院，只有R辱士。
例如...L..R...R...L...L...R....

class Solution {
public:
    string pushDominoes(string str) {
        string changeStr;
        for (int i = 0; i<str.length(); i++)
            changeStr += ".";
        int pos = 0;
        int nextRight = -1; 
        while (pos<str.length()) {
            if (str[pos] == 'R') {
                if (nextRight == -1)
                    nextRight = pos;//遇到R且前面沒有R
                else {
                    //遇到R且前面有R
                    for (int i = nextRight; i < pos; i++)
                        changeStr[i] = 'R';
                    nextRight = pos;//更新R的位置。
                } 
            }
            else if (str[pos] == 'L') {
                if (nextRight == -1) { 
                    changePos(changeStr, -1, pos);
                }//遇到L且前面沒有R狀態(tài)（這個狀態(tài)是指可以形成RL區(qū)間的抽兆，而不是已經(jīng)右倒?fàn)顟B(tài)）
                else {
                    changePos(changeStr, nextRight, pos);
                    nextRight = -1;
                }//遇到L且前面有R狀態(tài)识补，形成RL區(qū)間
            }
            pos++;
        }
        if(nextRight != -1)
            changePos(changeStr, nextRight, str.length()); 
        return changeStr;
    }
    
    void changePos(string &changeStr, int right, int left) {
    int i = left;
    while(right<0 && i >= 0 && changeStr[i] == '.') { 
        changeStr[i--] = 'L'; 
    }//L前面沒有R，向前置‘L’一直到非‘.’辫红。
    i = right;
    while(left >= changeStr.length() && i<changeStr.length()) { 
            changeStr[i++] = 'R'; 
    }//
    if (right >= 0 && left < changeStr.length()) {
        int middle = (right + left) / 2;
        for (int i = right; i<middle; i++)
            changeStr[i] = 'R';
        if ((right + left) % 2 == 1)
            changeStr[middle] = 'R';
        for (int i = middle + 1; i <= left; i++)
            changeStr[i] = 'L';
    } 
} 
};

華為-簡單錯誤記錄

問題描述：個簡單錯誤記錄功能小模塊凭涂，能夠記錄出錯的代碼所在的文件名稱和行號。
處理:
1.記錄最多8條錯誤記錄贴妻，對相同的錯誤記錄(即文件名稱和行號完全匹配)只記錄一條切油，錯誤計數(shù)增加；(文件所在的目錄不同名惩，文件名和行號相同也要合并)
2.超過16個字符的文件名稱澎胡，只記錄文件的最后有效16個字符；(如果文件名不同娩鹉，而只是文件名的后16個字符和行號相同攻谁，也不要合并)
3.輸入的文件可能帶路徑，記錄文件名稱不能帶路徑

輸入描述:

一行或多行字符串弯予。每行包括帶路徑文件名稱戚宦，行號，以空格隔開锈嫩。
文件路徑為windows格式
如：E:\V1R2\product\fpgadrive.c 1325

輸出描述:

將所有的記錄統(tǒng)計并將結(jié)果輸出受楼，格式：文件名代碼行數(shù)數(shù)目垦搬，一個空格隔開，如: fpgadrive.c 1325 1
結(jié)果根據(jù)數(shù)目從多到少排序艳汽，數(shù)目相同的情況下猴贰，按照輸入第一次出現(xiàn)順序排序。
如果超過8條記錄河狐，則只輸出前8條記錄.
如果文件名的長度超過16個字符米绕，則只輸出后16個字符

示例1 
## 輸入 
E:\V1R2\product\fpgadrive.c 1325
## 輸出
fpgadrive.c 1325 1


#include<iostream>
#include<vector>
#include<sstream>
#include<string>
using namespace std;
 
int str2num(string s)
{
    int num;
    stringstream ss(s);
    ss >> num;
    return num;
}
int main() {
    string str;
    vector<string>filenames;//存放文件名（文件名稱和行號）
    vector<int>count;//對應(yīng)文件的數(shù)量
    while(getline(cin,str)){
        if(str.length() == 0)
            break;
        unsigned int idx = str.rfind('\\');
        string filename = str.substr(idx+1);
        bool exist = false;//記錄文件是否存在
        for(int i=0;i<filenames.size();i++){
            if(filenames[i] == filename){
                count[i]++;
                exist = true;
                break;
            }
        }
        if(!exist){//如果未出現(xiàn)過，就記錄馋艺。
            filenames.push_back(filename);
            count.push_back(1);
        }
    }
    //直接插入排序
    for(int i=1; i<=filenames.size(); ++i){
        for(int j=i; j > 0; --j){
            if(count[j] > count[j -1]){
                swap(count[j],count[j-1]);
                swap(filenames[j],filenames[j-1]);
            }
        }
    }
    //按要求打印前8條記錄
    for(unsigned int k=0; k<8 && k<filenames.size();k++){
        unsigned int blankIdx = filenames[k].rfind(' ');
        string file = filenames[k];
        if(blankIdx >16)//文件名稱超過規(guī)定長度义郑。
            file = file.erase(0,blankIdx-16);
        cout<<file<<" "<<count[k]<<endl;;
    }
    return 0;
}

string的操作：
s.substr(pos,n); 返回一個string，包含s中從pos開始的n個字符的拷貝丈钙。
s.rfind(ch): 找到最后出現(xiàn)ch的位置。
s.find(ch): 找到第一次出現(xiàn)ch的位置交汤。
s.erase(pos,len)

華為-簡單錯誤記錄

問題描述：老師想知道從某某同學(xué)當(dāng)中雏赦，分?jǐn)?shù)最高的是多少，現(xiàn)在請你編程模擬老師的詢問芙扎。當(dāng)然星岗，老師有時候需要更新某位同學(xué)的成績.

輸入描述:

輸入包括多組測試數(shù)據(jù)。
每組輸入第一行是兩個正整數(shù)N和M（0 < N <= 30000,0 < M < 5000）,分別代表學(xué)生的數(shù)目和操作的數(shù)目戒洼。
學(xué)生ID編號從1編到N俏橘。
第二行包含N個整數(shù)，代表這N個學(xué)生的初始成績圈浇，其中第i個數(shù)代表ID為i的學(xué)生的成績
接下來又M行寥掐，每一行有一個字符C（只取‘Q’或‘U’），和兩個正整數(shù)A,B,當(dāng)C為'Q'的時候, 表示這是一條詢問操作磷蜀，他詢問ID從A到B（包括A,B）的學(xué)生當(dāng)中召耘，成績最高的是多少
當(dāng)C為‘U’的時候，表示這是一條更新操作褐隆，要求把ID為A的學(xué)生的成績更改為B污它。

輸出描述:

對于每一次詢問操作，在一行里面輸出最高成績.

交換兩個同類型元素庶弃，可以直接使用swap函數(shù)衫贬；
取最大值可直接使用std::max;

示例1
輸入
5 7
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 4 5
U 2 9
Q 1 5
輸出
5
6
5
9

#include<iostream>
using namespace std;
  
int main(){
    int n,m;
    while(cin>>n>>m){
        int sorce[n];char op;int A,B;
        for(int i=0; i<n; i++)
            cin>>sorce[i]; 
        while(m--){
            cin>>op>>A>>B;
            if( op == 'Q'){
                int max = 0;
                if(A>B) swap(A,B);
                for(int i=A-1; i<B; i++)
                   max = std::max(max,sorce[i]);
                cout<<max<<endl;
            }
            else if(op == 'U')
                sorce[A-1] = B;
        }
    }
     
    return 0;
}

好未來-刪除公共字符

題目：輸入兩個字符串，從第一字符串中刪除第二個字符串中所有的字符歇攻。例如固惯，輸入”They are students.”和”aeiou”，則刪除之后的第一個字符串變成”Thy r stdnts.”

#include<iostream>
#include<string>
using namespace std;
  
int main(){
    string orgStr;
    string delStr;
    while(getline(cin,orgStr)){
        getline(cin,delStr);
        for(int i=0; i<delStr.length();i++){
            for (int j=0; j<orgStr.length();j++){
                if(orgStr[j] == delStr[i])
                    orgStr = orgStr.erase(j,1);
            }
        }
        cout<<orgStr<<endl;
    }
    return 0;
}

好未來-字符串組合

題目：固定數(shù)組：{0掉伏，1缝呕，2澳窑，3，4供常，5摊聋，6，7栈暇，8麻裁，9}，輸入布爾數(shù)組：{0源祈，1煎源，1，1香缺，1手销，1，1图张，1锋拖，1，0} 祸轮，0表示對應(yīng)數(shù)組的下標(biāo)元素可出現(xiàn)亦可不出現(xiàn)兽埃，1則表示必須出現(xiàn)。
輸出所有可能的組合适袜，最終結(jié)果按升序排序柄错。
思想：回溯，深度遍歷苦酱，遇0多一種情況售貌。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

void Collect(vector<int>& isIndex, string str, int pos, vector<string>& result) {
    if (pos == isIndex.size()) {
        result.push_back(str);
        return;
    }//遍歷到最后一個值時，結(jié)束遞歸躏啰。
    if (isIndex[pos] == 0)//遇0趁矾，多一種情況，直接跳過當(dāng)前值给僵。
        Collect(isIndex, str, pos + 1, result);
    //不管0/1毫捣，這種情況都存在，儲存當(dāng)前值
    str += to_string(pos);
    Collect(isIndex, str, pos + 1, result);
}

int main() {
    vector<int>isIndex;  
    int a;
    while (cin >> a)
        isIndex.push_back(a); 
    vector<string>result;
    string str;
    Collect(isIndex, str, 0, result);
    sort(result.begin(), result.end());
    for (int i = 0; i< result.size(); i++)
        cout << result[i] << endl;  
    return 0;
}