【携程】算法岗笔试，100 100 100

第一题： int main() {     string s;     cin >> s;     unordered_map<char, int> m;     unordered_map<char, bool> flag;     int sum = 0, cur = 0;     vector<int> res;     for (int i = 0; i < s.size(); i++)         m[s[i]]++;     for (int i = 0; i < s.size(); i++) {         if (flag.find(s[i]) == flag.end()) {             sum += m[s[i]];             flag[s[i]] = true;         }         cur++;         if (cur == sum) {             res.push_back(cur);             cur = 0;             sum = 0;         }     }     for (int i = 0; i < res.size(); i++) {         if (i != res.size() - 1)             cout << res[i] << ',';         else             cout << res[i] << endl;     }     system("pause");     return 0; }

第二题： int main() {     int n;     cin >> n;     vector<double> pos;     vector<double> neg;     while (n--) {         int label;         double p;         cin >> label >> p;         if (label == 1)             pos.push_back(p);         else             neg.push_back(p);     }     double sum = 0;     for (int i = 0; i < pos.size(); i++) {         for (int j = 0; j < neg.size(); j++) {             if (pos[i] > neg[j])                 sum += 1;             else if (pos[i] == neg[j])                 sum += 0.5;         }     }     cout << fixed << setprecision(2) << sum / (pos.size() * neg.size()) << endl;     system("pause");     return 0; }

#当时没有考虑n==1的情况，以及判断没有路径的情况， 只有63% #不知道现在加上能不能ac def dfs(res,num,fg,i,cnt):     if sum(fg) == 2 and fg[0] == 1 and  num[i][0] != -1:  #只剩两个城市 ,起点还未到达, 且可以返回起点         res.append(cnt+num[i][0])         return      if fg[0] == 0:      #无法回到起点，起点被遍历两遍         return     for kk in range(n):         if num[i][kk] != -1 and fg[kk] > 0: #有路且去向城市未访问过             fg[i] -= 1             dfs(res,num,fg,kk,cnt+num[i][kk])  #             fg[i] += 1     return   n = int(input()) if n ==1:        #考虑n==1的情况     print(0) else:     m = int(input())     num =[[ -1 for i in range(n)] for j in range(n)]     for k in range(m):  #构造邻接矩阵         i,j,d = [int(tmp) for tmp in input().split(' ')]         num[i][j] = d         num[j][i] = d     fg = [1]*n         #改点是否访问标志     fg[0] = 2     #起点需访问两遍     res = []     dfs(res,num,fg,0,0)     if len(res) == 0: #考虑没有路径的情况         print(-1)     else:         print(min(res))

第三题： void helper(int idx, int nums, int &res, int cur, vector<vector<pair<int, int>>> &neigh, vector<bool> &flag) {     if (idx == 0 && flag[idx] == true) {         if (nums == flag.size())             res = min(res, cur);         return;     }     for (int i = 0; i < neigh[idx].size(); i++) {         if (flag[neigh[idx][i].first] == false) {             flag[neigh[idx][i].first] = true;             helper(neigh[idx][i].first, nums + 1, res, cur + neigh[idx][i].second, neigh, flag);             flag[neigh[idx][i].first] = false;         }     } } int main() {     int n, m;     cin >> n >> m;     if (n == 1) {         cout << 0 << endl;         return 0;     }     vector<vector<pair<int, int>>> neigh(n);     while (m--) {         int a, b, t;         cin >> a >> b >> t;         neigh[a].push_back(make_pair(b, t));         neigh[b].push_back(make_pair(a, t));     }     vector<bool> flag(n, false);     int res = INT_MAX;     helper(0, 0, res, 0, neigh, flag);     if (res == INT_MAX)         cout << -1 << endl;     else         cout << res << endl;     system("pause");     return 0; }

妈蛋忘记n等于1了

我后两题AC，第一题怎么都想不通过不了。 public static void main(String[] args) { Scanner sin = new Scanner(System.in); String schedule = sin.nextLine(); int n = schedule.length(); if(n==0) System.out.println(0); else{ HashMap<Character,Integer> end = new HashMap<>(); for(int i=0;i<n;i++){ end.put(schedule.charAt(i),i); } int t=0; String res=""; while(t<schedule.length()){ int e= t; int k =e; while(k<=e){ e = Math.max(end.get(schedule.charAt(k)),e); k++; } res += String.valueOf(e-t+1)+" "; t = e+1; } res = res.trim(); System.out.println(res); } }

忘记n ＝1😂

我一直88%第三题……n等于1我想考虑的，怎么考虑啊？输出-1还输出0啊……我好气啊。我应该都尝试一下……

第一题

用两个vec维护每个字母出现的第一个位置和最后一个位置。然后合并区间。这样也能解。

第一题 有没有可以讲解下的  还是没懂题

第三题写的状压dp为什么过不去

大佬 手里有offer了吗

第一题卡在88%是怎么回事😣

大佬，同九年，汝何秀

第一题什么思路

收到面试了吗