8.2 字符串中等（阅读难度） 165 Compare Version Numbers 299 Bulls and Cows

今天两道题难点都在读懂题目要求，思路并不难

165 Compare Version Numbers

class Solution { public:     vector<vector<int>> getVersion(string s){         vector<vector<int>> v;         vector<int> current;         for(char ch : s){             //忽略前导零             if(ch == '0' && current.empty()){                 continue;             }             //记录数值             if(ch != '.'){                current.push_back(ch-'0');             }else{                 v.push_back(current);                 current.clear();              }         }         v.push_back(current);         return v;     }     int vectorToInt(vector<int> num){         int res = 0;         int n = num.size();         if(n == 0){             return 0;         }         for(int i = 0 ; i < n ; i++){             res = res * 10 + num[i];         }         return res;     }     int compareVersion(string version1, string version2) {         /* 读题         //比较版本号-->修订号转为int 并忽略前导零         //从左到右一个个比较，忽略前导零         //如果v1<v2 -1 v1>v2 1 否则0*/          //主体遍历：单项思维：遇到.就比较后面的值转为int题目中都告诉了是肯定可以被int承载的         vector<vector<int>> v1 , v2;         v1 = getVersion(version1);         v2 = getVersion(version2);         //获取修订号：忽略前导零 且 拆分版本号         //遍历对应的v1[0] v2[0]要获取这俩的整数         int n1 = v1.size(), n2 = v2.size();         int n = max(n1, n2);         for(int i = 0 ; i < n;i++){             int num1 = i < n1 ? vectorToInt(v1[i]) : 0;             int num2 = i < n2 ? vectorToInt(v2[i]) : 0;              if(num1 > num2) return 1;             if(num1 < num2) return -1;         }         return 0;              } }; 

c++代码学习

1. 二维数组的输入 vector<vector<int>> v; vector<int> current; 先填满current 在v.push_back(current); current.clear();然后重复这个过程  2. 将数组中的数字组合为一个整数 pow会导致浮点数计算，尽量避免： for(int i = 0 ; i < n ; i++){       res = res * 10 + num[i]; }		  

299 Bulls and Cows

class Solution { public:     string getHint(string secret, string guess) {     	/* 读题         //玩bulls & cows这个游戏         //我写一个数字 让我朋友猜         //猜了以后：bulls代表在正确位置且数字也对了A cows不在正确位置但是数字对了 B         //返回形式 "xAyB"x和y都有可能是三位数 不是个位数 */                  string res = "";         int n = secret.size() , bulls =0 ,cows=0;         //判断bull公牛数          for(int i = 0 ; i < n ; i ++){             if(secret[i] == guess[i]){                 bulls++;                 secret[i] = 'b';                 guess[i] = 'b';             }         }         //难点1：cows奶牛数的判别 数字对了但是位置不对，那就是说有多少个不重复的相同数字n^2         for(int i = 0 ; i < n ; i++){             char ch1 = secret[i];             if(!isdigit(ch1))continue;             for(int j = 0 ; j < n ; j++){                 char ch2 = guess[j];                 if(!isdigit(ch2))continue;                 if(ch1 == ch2){                     cows++;                     guess[j] = 'c';                     break;                 }             }         }         //难点2：多位数字转字符 to_string         res.append(to_string(bulls));         res += 'A';         res.append(to_string(cows));         res += 'B';         return res;     } }; 

时间复杂度为$O(n^2)$，官方题解中有为$O(n)$的算法。这个是类似于之前建立26字母表计数的方法。【review 7.26 242 Valid Anagram几乎一模一样】思路练习：387 First Unique Character in a String 389 Find the Difference

class Solution { public:     string getHint(string secret, string guess) {         int n = secret.size();         int bulls = 0 , cows = 0;         vector<int> secretCount(10 , 0) , guessCount(10 , 0);         for(int i = 0 ; i < n ; i ++){             if(secret[i] == guess[i]){                 bulls++;             }             else{                 secretCount[secret[i] - '0']++;                 guessCount[guess[i] - '0']++;             }         }          //计算奶牛数         for(int i = 0 ; i <10 ; i++){             cows += min(secretCount[i] , guessCount[i]);         }          return to_string(bulls)+'A'+to_string(cows)+'B';     } }; 

字符串题中 寻找两字符串中相同字符数目，且不要求位置一致时，转换思路为计算整个字符串中不同字符的数目，取两个字符串中计数较小的值即为ans。