百度面试一面

第一题：从后往前扫描一遍，根据当前统计的'#'的数目，对每个字母向后移动相同数目的位置。 const int maxn = 1000+10; char s[maxn]; void solve() { int n = strlen(s); int cnt = 0; for(int i=n-1 ; i>=0 ; --i){ if(s[i]=='#'){ ++cnt; }else{ s[i+cnt] = s[i]; } } for(int i=0 ; i<cnt ; ++i){ s[i] = '#'; } }

第一道题其实就是剑指offer中调整数组顺序使奇数位于偶数前变形题。 如果需要保证相对顺序不变的话，可以直接另开两个字符串空间，第一个字符串保存#，另一个字符串保存字母，最后将这两个字符串的和重新赋值给原先的字符串。 void string_shift2(string &s,int len) { if(s.empty()) return; string s1,s2; for(auto e:s) { if(e=='#') s1+=e; else if(isalpha(e)) s2+=e; } s=s1+s2; } 如果不需要保证相对顺序的话，可以维护两个指针。第一个指针指向字符串的第一个字符，它只向后移动，直到遇见字符为字母，第二个指针指向数组的最后一个字符，它只向前移动，直到遇到#。然后交换两个指针的内容，一直重复上述过程，直到两个指针相遇。 void string_shift(string &s,int len) { if(s.empty()) return; int index1=0; int index2=len-1; while(index1<index2) { while(index1<index2&&!isalpha(s[index1])) ++index1; while(index1<index2&&isalpha(s[index2])) --index2; if(index1<index2) swap(s[index1],s[index2]); } }

第一题扫2遍，第一遍计算每个字符的最终位置，第二遍直接移位。 第二题dp。 第三题如果只询问一次且要输出路径的话暴力向上爬就好了，如果多次询问只询问路径长度就预处理下深度求LCA吧。

看来百度是挺注重基础的。

/* * 1.字符串移位，给出字符串abc##dfg##gh，实现将所有#移至字符串串头。输出####abcdfggh（个人认为可以用后向移位，减少移位次数） */ static void moveStep(char[] str){ if(str==null||str.length<1) return ; int len=str.length; int s=len-1,e=len-1; for(int i=len-1;i>=0;i--){ if(str[i]=='#'){ int j=i; while(j>=0&&str[j]=='#')j--; //find successive # if(j<0) break; if(s==len-1)s=i;//first initial e=j; i=j+1; }else{ int j=i; while(j>=0&&str[j]!='#')j--; //find successive abcd... if(s==e)continue; else{ //fill abcd for(int k=i;k>j&&s>=0;k--){ str[s--]=str[k]; } //fill # for(int k=s;k>j;k--) str[k]='#'; } if(j<0)break; i=j+1; } } } /* * 给出一个二维矩阵，从（0,0）出发走到右下角，只能向右或向下走，找到一条路径，是这条路径上的总和最大。（个人认为使用动态规划或深度遍历） */ static int findMaxSum(int[][] nums,int row,int col){ if(row<1||col<1) return 0; int[][] dp=new int[row][col]; for(int i=0;i<row;i++){ if(i==0)dp[i][0]=nums[i][0]; else dp[i][0]=dp[i-1][0]+nums[i][0]; } for(int i=1;i<col;i++){ dp[0][i]=dp[0][i-1]+nums[0][i]; } for(int i=1;i<row;i++){ for(int j=1;j<col;j++){ dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1])+nums[i][j]; } } return dp[row-1][col-1]; } /* * 给出一颗二叉树，两个叶节点，找到这两个叶节点互连通的一条最短路径。（个人认为主要是找两个叶节点的最近公共祖先） */ static int depthMin(TreeNode root,TreeNode s,TreeNode t){ if(root==null||s==t) return 0; ArrayList<Integer> l1=new ArrayList<Integer>(); ArrayList<Integer> l2=new ArrayList<Integer>(); find(root,s,new ArrayList<Integer>(),l1); find(root,t,new ArrayList<Integer>(),l2); //find common int i=0,j=0; /*for(int k=0;k<l1.size();k++) System.out.print(l1.get(k)+"->"); System.out.println(); for(int k=0;k<l2.size();k++) System.out.print(l2.get(k)+"->"); System.out.println(); */ while(i<l1.size()&&j<l2.size()&&l1.get(i)==l2.get(j)){ i++; j++; } int dep=l1.size()-i+l2.size()-j+1; //System.out.println(i+" "+j+" "+dep); return dep; } private static void find(TreeNode root, TreeNode t, ArrayList<Integer> cur,ArrayList<Integer> res) { // TODO Auto-generated method stub //System.out.println(root.val+" "+t.val); if(root==null) return; if(t==root){ cur.add(root.val); res.addAll(new ArrayList<Integer>(cur)); return; }else{ cur.add(root.val); //.for(int k=0;k<cur.size();k++) // System.out.print(cur.get(k)+"->"); //System.out.println(); find(root.left,t,cur,res); find(root.right,t,cur,res); cur.remove(cur.size()-1); } }

第一题：双指针 void core(string &str) {     int len = str.size(), cur, right;     cur = right = len - 1;     for (; cur >= 0; cur--)     {         if (str[cur] == '#')             continue;         else         {             if (cur != right)                 swap(str[cur], str[right]);             right--;         }     } } 第二题：动态规划 略 第三题：最小公共祖先+dfs  代码未测试 struct TreeNode {     int val;          TreeNode *left;     TreeNode *right;     TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {     if (!root || root == p || root == q) return root;     TreeNode *left = lowestCommonAncestor(root->left, p, q);     TreeNode *right = lowestCommonAncestor(root->right, p, q);     if (!left && !right)         return root;     if (!right) return right;     else return left; } bool dfs(TreeNode *root, TreeNode *p, TreeNode *q, vector<TreeNode*> &path, vector<vector<TreeNode*>> &res) {     if (!root) return false;     if (root == p || root == q)     {         path.push_back(root);         res.push_back(path);         path.pop_back();         return true;     }     path.push_back(root);     if (dfs(root->left, p, q, path, res)) return true;     if (dfs(root->right, p, q, path, res)) return true;     path.pop_back();     return false; } vector<TreeNode*> findPath(TreeNode* root, TreeNode* p, TreeNode* q) {     TreeNode *ancestor = lowestCommonAncestor(root, p, q);     vector<TreeNode*> left_path, right_path;     vector<vector<TreeNode*>> res;     dfs(ancestor->left, p, q, left_path, res);     dfs(ancestor->right, p, q, right_path, res);     vector<TreeNode*> path;     for (int i = res[0].size() - 1; i >= 0; i--)         path.push_back(res[0][i]);     path.push_back(ancestor);     for (int i = 0; i < (int)res[1].size() - 1; i++)         path.push_back(res[1][i]);          return path; }

楼主投的什么部门

是啊  挺基础的  重要的是根据思路清晰地把代码写出来，还要多练

具体部门没映像了，只是没想到进面试了。面试算法

问一下什么时候投的简历啊？还有除了这三个编程之外的问题能分享一下么

什么岗位

第一题可以投机取巧吗？用两个数组，一个记录#一个记录字母？也可以，只是不知道符合要求不

第一题不知道对不对，欢迎指出bug class Solution { public: string reorder(string &s){ int len = s.length(); int start = len - 1; int end = len - 1; while (start >= 0){ if (s[end] != '#'){ --start; --end; } else{ while (start>= 0 && s[start] == '#'){ --start; } if (start >= 0){ swap(s[start], s[end]); --end; --start; } } } return s; } };

第二题是dp.  第三题是最小公共祖先

第一题用两个指针，从后往前写，第一个指针到达数组头时，再从头开始写#直到第二个指针

第一题用选择排序，也可以实现吧，遍历后#向左移动。刚刚学了一个月，求高手分析

你这个是最近的百度内推吗？内推后发你个链接然后选择岗位投递的吗？

请问楼主，您是内推的吗？还是在百度实习了几个月的，然后统一给你们提取面试啊

static void resort(char[] s) { int n = s.length; int[] f = new int[n]; int count = 0; for (int i=n-1; i>=0; i--) { if (s[i] != '#') { f[i] = count; } else { count ++; } } for (int i=n-1; i>=0; i--) { if (s[i] != '#') { s[i+f[i]] = s[i]; } } for (int i=0; i<count; i++) { s[i] = '#'; } }

其实就是每次都把#移动到第一位吧