基礎(chǔ)知識(shí)：
字符串長(zhǎng)度： int length = s.length(); /length = s.size():不包括‘\0'
【面試題49：把字符串轉(zhuǎn)換成整數(shù)】String to Integer (atoi)
題目：實(shí)現(xiàn)一個(gè)函數(shù)stringToInt,實(shí)現(xiàn)把字符串轉(zhuǎn)換成整數(shù)這個(gè)功能，不能使用atoi或者其他類(lèi)似的庫(kù)函數(shù)。
I think we only need to handle four cases:
discards all leading whitespaces
sign of the number
overflow
invalid input
【面試題04：替換空格】
題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，把字符串中的每個(gè)空格替換成"%20"，例如“We are happy.”，則輸出“We%20are%20happy.”。
思路：先確定空格數(shù)量以及替換后字符串長(zhǎng)度，然后從后往前遍歷完成移動(dòng)。時(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
題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)匹配包括'.'和 '*' 的正則表達(dá)式。模式中的字符'.'表示任意一個(gè)字符，而'*'表示它前面的字符可以出現(xiàn)任意次（包含0次）。 在本題中，匹配是指字符串的所有字符匹配整個(gè)模式。例如，字符串"aaa"與模式"a.a"和"abaca"匹配，但是與"aa.a"和"ab*a"均不匹配。
class Solution {
public:
bool isMatch(string s, string p) {
/*
if 第二個(gè)字符為‘*’
if 第一個(gè)字符相等
三種情況
else
Match(sPos,pPos+2,s,p);
else
if 第一個(gè)字符相等
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é)束沒(méi)，都有可能匹配成功
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ù)值的字符串】
題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)判斷字符串是否表示數(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有符號(hào)，B無(wú)符號(hào)。.前后不能都沒(méi)數(shù)，e/E前后必有數(shù)。
class Solution {
public:
bool isNumber(string s) {
if(s.empty())
return false;
int pos = 0;
//" 0.1 " => true，開(kāi)頭空格情況
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：字符串的排列】
題目： 輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來(lái)的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。
思路：回溯，先提二叉樹(shù)的遍歷，以二叉樹(shù)中和為某一值的路徑為例（路徑以根節(jié)點(diǎn)開(kāi)始，即對(duì)應(yīng)前序遍歷），從根節(jié)點(diǎn)一直左子樹(shù)遍歷到葉節(jié)點(diǎn)，每次將根節(jié)點(diǎn)壓入vector，然后回溯到父節(jié)點(diǎn)并刪除當(dāng)前vector中節(jié)點(diǎn)，然后遍歷其右子樹(shù)。
該問(wèn)題類(lèi)似多叉樹(shù)，從左往右遍歷字符，每個(gè)字符與之后所有字符（包括自己）交換，一直到最后一個(gè)字符，產(chǎn)生深度為串長(zhǎng)度的多叉樹(shù)。在進(jìn)行回溯時(shí)需要通過(guò)循環(huán)遞歸（不像二叉樹(shù)，只有左右子樹(shù)，展開(kāi)來(lái)寫(xiě)）。從左往右每個(gè)數(shù)分別跟之后的交換，然后處理下個(gè)數(shù)。遞歸結(jié)束的條件是處理到最后一個(gè)數(shù)字。ps:已經(jīng)說(shuō)不清楚了
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)遍歷到最后一個(gè)字符是輸出；類(lèi)似于樹(shù)的葉節(jié)點(diǎn)。
//不同問(wèn)題不同條件，如最短路徑，統(tǒng)計(jì)路徑小于最短，則更新路徑；
if(pos == str.length()-1)
result.push_back(str);
//循環(huán)接下來(lái)所有字符，類(lèi)似多叉樹(shù)，二叉樹(shù)，只需循環(huán)左右子樹(shù)。
//當(dāng)一次遍歷到葉節(jié)點(diǎn)時(shí)，要回溯，需要swap回來(lái)，類(lèi)似回到父節(jié)點(diǎn)，然后到下個(gè)葉節(jié)點(diǎn)。
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é)點(diǎn)，恢復(fù)當(dāng)一次交換
}
}
}
};
【面試題46：把數(shù)字翻譯成字符串】 Decode Ways
題目：給定一個(gè)數(shù)字，按照如下規(guī)則翻譯成字符串：1翻譯成“a”，2翻譯成“b”...26翻譯成“z”。一個(gè)數(shù)字有多種翻譯可能，例如12258一共有5種，分別是bccfi，bwfi，bczi，mcfi，mzi。實(shí)現(xiàn)一個(gè)函數(shù)，用來(lái)計(jì)算一個(gè)數(shù)字有多少種不同的翻譯方法。
思路：動(dòng)態(tài)規(guī)劃，f(n) = f(n-1) + coef(n,n-1)*f(n-2),遇特殊情況：1)開(kāi)頭遇0，直接return；2）中間遇10或20，f(i) = f(i-2)，否則return。
//來(lái)自leetcode，0沒(méi)有對(duì)應(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：最長(zhǎng)不含重復(fù)字符的子字符串】
題目：請(qǐng)從字符串中找出一個(gè)最長(zhǎng)的不包含重復(fù)字符串的子字符串，計(jì)算該最長(zhǎng)子字符串的長(zhǎng)度。假設(shè)字符串中只包含‘a(chǎn)’~‘z’的字符。
思路：動(dòng)態(tài)規(guī)劃，f(i)定義為第i個(gè)字符結(jié)尾時(shí)最長(zhǎng)子字符串的長(zhǎng)度。關(guān)于f(i),分兩種情況：1）第i個(gè)字符之前從未出現(xiàn)，或之前出現(xiàn)，但距離第i個(gè)字符的長(zhǎng)度d大于f(i-1)(即上一個(gè)最長(zhǎng)字符串長(zhǎng)度)。這時(shí)f(i) = f(i-1)+1；2）之前出現(xiàn)，且位于f(i-1)中，這時(shí)f(i) = d,即被更新成以第i個(gè)字符結(jié)尾的最長(zhǎng)串長(zhǎng)度。
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：第一個(gè)只出現(xiàn)一次的字符】First Unique Character in a String
題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)找出字符流中第一個(gè)只出現(xiàn)一次的字符。
思路：map計(jì)數(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是否僅交換兩個(gè)字符能與B相等。
思路：遍歷A，找到第一個(gè)與B不同的字符，然后接著找到第二個(gè)與B不同的字符，然后交換兩個(gè)字符，判斷是否相等。時(shí)間復(fù)雜度O(n)。ps：存在A==B的特殊情況，單獨(dú)考慮。
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.
思路：二叉樹(shù)的先序遍歷，同時(shí)需要考慮括號(hào)，左子樹(shù)必須加括號(hào)，右子樹(shù)非空時(shí)加括號(hào)。
Example 1:
Input: Binary tree: [1,2,3,4]
1
/ \
2 3
/
4
Output: "1(2(4))(3)"
Example 2: 如無(wú)左節(jié)點(diǎn)，用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; //若無(wú)右子樹(shù)，則返回。與無(wú)左子樹(shù)不同。
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)建一個(gè)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.
[],{},(),成對(duì)出現(xiàn)，采用棧的數(shù)據(jù)結(jié)構(gòu)，先進(jìn)后出。先進(jìn)棧的符號(hào)之后配對(duì)。
判斷條件：空棧，即所有左開(kāi)口符號(hào)均配對(duì)成功。不成立條件：1）空棧時(shí)遇上右開(kāi)口；2）非空棧時(shí)，遇上右開(kāi)口與出棧的左開(kāi)口不配對(duì)。
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
題目：寫(xiě)一個(gè)函數(shù)，找到數(shù)組中字符串元素的最長(zhǎng)公共字首，如無(wú)公共字符，返回空字符串。
思路：先確定前兩個(gè)字符串的公共字首，然后將公共字首與第三個(gè)比較，以此類(lèi)推，確定最后的最長(zhǎng)公共字首。
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)確定每個(gè)word的起始點(diǎn)；2）每個(gè)word進(jìn)行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。
思路：由于括號(hào)先進(jìn)后出規(guī)律，采用棧的結(jié)構(gòu)，我們需要通過(guò)計(jì)算坐標(biāo)找出最長(zhǎng)子串的長(zhǎng)度，所以棧中存放的是括號(hào)在主串的位置。計(jì)算規(guī)律：一次匹配意味著一次出棧，計(jì)算此時(shí)坐標(biāo)與棧頂?shù)木嚯x，即為此時(shí)的有效子串長(zhǎng)度。注意棧頂元素的意義，向前未匹配有效的坐標(biāo)。如果沒(méi)有出棧條件，均入棧。一種情況是空棧，意味著此時(shí)坐標(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且前面沒(méi)有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且前面沒(méi)有R狀態(tài)（這個(gè)狀態(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前面沒(méi)有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';
}
}
};
華為-簡(jiǎn)單錯(cuò)誤記錄
問(wèn)題描述：個(gè)簡(jiǎn)單錯(cuò)誤記錄功能小模塊，能夠記錄出錯(cuò)的代碼所在的文件名稱(chēng)和行號(hào)。
處理:
1.記錄最多8條錯(cuò)誤記錄，對(duì)相同的錯(cuò)誤記錄(即文件名稱(chēng)和行號(hào)完全匹配)只記錄一條，錯(cuò)誤計(jì)數(shù)增加；(文件所在的目錄不同，文件名和行號(hào)相同也要合并)
2.超過(guò)16個(gè)字符的文件名稱(chēng)，只記錄文件的最后有效16個(gè)字符；(如果文件名不同，而只是文件名的后16個(gè)字符和行號(hào)相同，也不要合并)
3.輸入的文件可能帶路徑，記錄文件名稱(chēng)不能帶路徑
輸入描述:
一行或多行字符串。每行包括帶路徑文件名稱(chēng)，行號(hào)，以空格隔開(kāi)。
文件路徑為windows格式
如：E:\V1R2\product\fpgadrive.c 1325
輸出描述:
將所有的記錄統(tǒng)計(jì)并將結(jié)果輸出，格式：文件名代碼行數(shù)數(shù)目，一個(gè)空格隔開(kāi)，如: fpgadrive.c 1325 1
結(jié)果根據(jù)數(shù)目從多到少排序，數(shù)目相同的情況下，按照輸入第一次出現(xiàn)順序排序。
如果超過(guò)8條記錄，則只輸出前8條記錄.
如果文件名的長(zhǎng)度超過(guò)16個(gè)字符，則只輸出后16個(gè)字符
示例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;//存放文件名（文件名稱(chēng)和行號(hào)）
vector<int>count;//對(duì)應(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)過(guò)，就記錄。
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)//文件名稱(chēng)超過(guò)規(guī)定長(zhǎng)度。
file = file.erase(0,blankIdx-16);
cout<<file<<" "<<count[k]<<endl;;
}
return 0;
}
string的操作：
s.substr(pos,n); 返回一個(gè)string，包含s中從pos開(kāi)始的n個(gè)字符的拷貝。
s.rfind(ch): 找到最后出現(xiàn)ch的位置。
s.find(ch): 找到第一次出現(xiàn)ch的位置。
s.erase(pos,len)
華為-簡(jiǎn)單錯(cuò)誤記錄
問(wèn)題描述：老師想知道從某某同學(xué)當(dāng)中，分?jǐn)?shù)最高的是多少，現(xiàn)在請(qǐng)你編程模擬老師的詢(xún)問(wèn)。當(dāng)然，老師有時(shí)候需要更新某位同學(xué)的成績(jī).
輸入描述:
輸入包括多組測(cè)試數(shù)據(jù)。
每組輸入第一行是兩個(gè)正整數(shù)N和M（0 < N <= 30000,0 < M < 5000）,分別代表學(xué)生的數(shù)目和操作的數(shù)目。
學(xué)生ID編號(hào)從1編到N。
第二行包含N個(gè)整數(shù)，代表這N個(gè)學(xué)生的初始成績(jī)，其中第i個(gè)數(shù)代表ID為i的學(xué)生的成績(jī)
接下來(lái)又M行，每一行有一個(gè)字符C（只取‘Q’或‘U’），和兩個(gè)正整數(shù)A,B,當(dāng)C為'Q'的時(shí)候, 表示這是一條詢(xún)問(wèn)操作，他詢(xún)問(wèn)ID從A到B（包括A,B）的學(xué)生當(dāng)中，成績(jī)最高的是多少
當(dāng)C為‘U’的時(shí)候，表示這是一條更新操作，要求把ID為A的學(xué)生的成績(jī)更改為B。
輸出描述:
對(duì)于每一次詢(xún)問(wèn)操作，在一行里面輸出最高成績(jī).
交換兩個(gè)同類(lèi)型元素，可以直接使用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;
}
好未來(lái)-刪除公共字符
題目：輸入兩個(gè)字符串，從第一字符串中刪除第二個(gè)字符串中所有的字符。例如，輸入”They are students.”和”aeiou”，則刪除之后的第一個(gè)字符串變成”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;
}
好未來(lái)-字符串組合
題目：固定數(shù)組：{0，1，2，3，4，5，6，7，8，9}，輸入布爾數(shù)組：{0，1，1，1，1，1，1，1，1，0} ，0表示對(duì)應(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;
}//遍歷到最后一個(gè)值時(shí)，結(jié)束遞歸。
if (isIndex[pos] == 0)//遇0，多一種情況，直接跳過(guò)當(dāng)前值。
Collect(isIndex, str, pos + 1, result);
//不管0/1，這種情況都存在，儲(chǔ)存當(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;
}
