小米第三道题

string alpha("0abcdefghijklmnopqrstuvwxyz"); void trans(string s,int cur,int n,string ans) {     if (cur == n)     {         ans+= alpha[s[cur] - '0'];         cout << ans << " ";         return;     }     else     {                  ans+=alpha[s[cur] - '0'];         trans(s, cur + 1, n,ans);         ans.erase(ans.size() - 1);         if (cur + 1 <= n)         {             int tmp = (s[cur] - '0') * 10 + s[cur + 1] - '0';             if (tmp <= 26)             {                 ans+=alpha[tmp];                 if (cur + 1 == n)                 {                     cout <<ans<< " ";                     return;                 }                 trans(s, cur + 2, n,ans);             }         }     } } int main() {     string s;     while (cin >> s)     {         string ans;         trans(s, 0, s.size()-1,ans);     } } dfs就行了

#include<iostream> #include<string> #include<vector> #include<stack> using namespace std; vector<char> str; void fun(string temp, int begin) { //    cout << begin<<endl;     if (begin >= temp.size())     {            for (int i = 0; i < str.size(); i++)         {             cout << str[i];         }         cout <<' ';         return;     }     str.push_back(temp[begin]+'a'-'1');         fun(temp, begin + 1);         str.pop_back();                  if (begin + 1 < temp.size() && (temp[begin] < '2' || (temp[begin] == '2'&&temp[begin + 1] < '6')))         {             int a=(int)(temp[begin] - '0') * 10 + (int)temp[begin + 1]-'0';             str.push_back(a+'a'-1);                          fun(temp, begin + 2);             str.pop_back();                      } } int main() {       string temp;     while (cin >> temp)     {         fun(temp, 0);     } } 33%，忙着做后边，没检查出来

#include<iostream> #include<vector> #include<string> using namespace std; char Change(int n){ return ('a'+n-1); } vector<vector<char> > ves; vector<char> res; void DFS(string str){ if(str.size()==0){ ves.push_back(res); return; } res.push_back(Change(str[0]-'0')); DFS(str.substr(1,str.size()-1)); res.pop_back(); if(str.size()>=2){ string t=str.substr(0,2); int n=atoi(t.c_str()); if(n<=26){ res.push_back(Change(n)); DFS(str.substr(2,str.size()-2)); res.pop_back(); } } } int main(){ string ss; cin>>ss; DFS(ss); int i,j; for(i=0;i<(ves.size()-1);++i){ for(j=0;j<ves[i].size();++j){ cout<<ves[i][j]; } cout<<" "; } for(j=0;j<ves[i].size();++j){ cout<<ves[i][j]; } cout<<endl; return 0; } 谁能帮忙看看哪里不对。 用例都结果都对，就是通过率为0%

其实因为数据限制在 1 到 26 所以就跟 上个和上上个有关系， 时间复杂度O（n）就解决了。

深搜，分成1个字符和2个字符分别递归

过了33%，内存爆掉了hhhhhhhh

1转化为a，2转化为b，一次类推，26转化为z，先输入一串数字 输入：123 输出：abc      aw     ic

public class Mima { private static Map<String, String> map = new HashMap<>(); static { map.put("1", "a"); map.put("2", "b"); map.put("3", "c"); map.put("4", "d"); map.put("5", "e"); map.put("6", "f"); map.put("7", "g"); map.put("8", "h"); map.put("9", "i"); map.put("10", "j"); map.put("11", "k"); map.put("12", "l"); map.put("13", "m"); map.put("14", "n"); map.put("15", "o"); map.put("16", "p"); map.put("17", "q"); map.put("18", "r"); map.put("19", "s"); map.put("20", "t"); map.put("21", "u"); map.put("22", "v"); map.put("23", "w"); map.put("24", "x"); map.put("25", "y"); map.put("26", "z"); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String str = sc.nextLine(); StringBuilder res = new StringBuilder(); helper(str, 0, res, new StringBuilder()); System.out.println(res.substring(0, res.length() - 1)); } sc.close(); } /** * * @param str * @param size 当前可以使用的字符的下标 * @param res 存放结果 */ private static void helper(String str, int size, StringBuilder res, StringBuilder tmp) { if (size == str.length()) { res.append(tmp.toString()).append(" "); return; } String tmpStr = str.substring(size, size + 1); if (map.get(tmpStr) != null) { tmp.append(map.get(tmpStr)); helper(str, size + 1, res, tmp); tmp.deleteCharAt(tmp.length() - 1); } if (size + 2 <= str.length()) { tmpStr = str.substring(size, size + 2); if (map.get(tmpStr) != null) { tmp.append(map.get(tmpStr)); helper(str, size + 2, res, tmp); tmp.deleteCharAt(tmp.length() - 1); } } } }

f(n) = {f(n - 1) + current, f(n - 2) + (pre+current)}

斐波那契数列？？