📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: soliloquyyy
跳转到指定楼层
上一主题 下一主题
收起左侧

面试刷题咯~每天10道~

🔗
 楼主| soliloquyyy 2018-12-14 17:06:01 | 只看该作者
全局:
Leetcode 124 Binary Tree Maximum Path Sum
这道题和我之前po的tree diameter很相似。只不过那个是求长度,这个是求sum。
我们只要在比较本地max的时候看看max(left,right)+root.val 和root.val哪个大然后return。因为node里面的数是有可能为负数,所以我们要在更新global max情况下看着三个case:
root val, root+left+right, left+right
  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. *     int val;
  5. *     TreeNode left;
  6. *     TreeNode right;
  7. *     TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. class Solution {
  11.     int max = Integer.MIN_VALUE;
  12.     public int maxPathSum(TreeNode root) {
  13.         maxDepth(root);  
  14.         return max;  
  15.     }
  16.    
  17.     public int maxDepth(TreeNode root)
  18.     {
  19.         if(root == null)
  20.             return 0;
  21.         int left = maxDepth(root.left);
  22.         int right = maxDepth(root.right);
  23.         // max = Math.max(Math.max(Math.max(max, left+right), left+right+root.val),root.val);
  24.         int localMax = Math.max(root.val, root.val + Math.max(left, right));
  25.         
  26.         max = Math.max(max, Math.max(localMax, root.val + left + right));
  27.          
  28.         return localMax;
  29.     }
  30. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-16 12:19:35 | 只看该作者
全局:
809. Expressive Words
这道题我们首先需要想清楚一个:
1) 如果一个letter不是extendable的说明它连续出现的次数小于3次。那么这样的letter在word中必须要和S中一样。那么我们在s和word中的pointer都++
2)如果是extendable,那么这个letter出现的次数肯定大于2。但是我们判断的时候并不需要算出多少的次数这么复杂。我们只要看S中看i-1,i,i+1这三个位置是不是一样 或者 i-2,i-1,i是不是一样。这里的意思是,如果这两个条件满足一个就说明至少有3个letter连续出现,那么我们只要把S的pointer++就好了。
如果以上case不满足,说明这个word不是stretchy的。
  1. class Solution {
  2.     public int expressiveWords(String S, String[] words) {
  3.         if(S == null || S.length() == 0 || words.length == 0)
  4.             return -1;
  5.         
  6.         int res = 0;
  7.         for(String word: words)
  8.         {
  9.             if(helper(S, word))
  10.                 res++;
  11.         }
  12.         
  13.         return res;
  14.     }
  15.    
  16.    
  17.     public boolean helper(String S, String word)
  18.     {
  19.         int i = 0;
  20.         int j = 0;
  21.         
  22.         while(i<S.length())
  23.         {
  24.             if(j < word.length() && S.charAt(i) == word.charAt(j))
  25.             {
  26.                 i++;
  27.                 j++;
  28.             }
  29.             else if( i-1 >= 0 && i+1 < S.length() && S.charAt(i-1) == S.charAt(i) && S.charAt(i) == S.charAt(i+1))
  30.             {
  31.                 i++;
  32.             }
  33.             else if(i-2 >= 0  && S.charAt(i-1) == S.charAt(i) && S.charAt(i) == S.charAt(i-2))
  34.             {
  35.                 i++;
  36.             }
  37.             else
  38.                 return false;
  39.         }
  40.         
  41.         return j == word.length();
  42.         
  43.             
  44.     }
  45. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-16 13:56:28 | 只看该作者
全局:
Leetcode 62/63 Unique Paths I/II
这道题用dp的思想很好处理。
首先对于62题,我们用一个2d array来保留从起点到(i,j)的路径数。因为我们只能往下和往右,对于(i,j)来说,他的路径数就是(i-1,j)+(i,j-1)
然后我们开始初始化,对于第一行和第一列来说,她们都为1.
  1. class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         int[][] dp = new int[m][n];
  4.         
  5.         for(int i=0;i<n;i++)
  6.             dp[0][i] = 1;
  7.         
  8.         for(int i=0;i<m;i++)
  9.             dp[i][0] = 1;
  10.         
  11.         for(int i=1;i<m;i++)
  12.         {
  13.             for(int j=1;j<n;j++)
  14.                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
  15.         }
  16.         
  17.         return dp[m-1][n-1];
  18.         
  19.     }
  20. }
复制代码


而63题是有障碍物的版本。我们同样是有一个dp 2d array。但是初始化的时候不一样,在第一行和第一列的时候,如果中间一旦有一个障碍物,那一行或者那一列在1后边的元素都是0.
然后我们在处理(i,j)的时候要注意原有grid是否是障碍物是的话,直接等于0.不是的话就看上边和左边。
  1. class Solution {
  2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3.         if(obstacleGrid.length == 0 || obstacleGrid[0].length == 0)
  4.             return 0;
  5.             
  6.         int m = obstacleGrid.length;
  7.         int n = obstacleGrid[0].length;
  8.         
  9.         int[][] dp = new int[m][n];
  10.         
  11.         int flag = 0;
  12.         for(int i=0;i<m;i++)
  13.         {
  14.             if(obstacleGrid[i][0] == 1)
  15.                 flag = 1;
  16.             if(flag == 0 && obstacleGrid[i][0] == 0)
  17.                 dp[i][0] = 1;
  18.             else if (flag == 1 && obstacleGrid[i][0] == 0)
  19.                 dp[i][0] = 0;
  20.         }

  21.         flag = 0;
  22.         for(int i=0;i<n;i++)
  23.         {
  24.             if(obstacleGrid[0][i] == 1)
  25.                 flag = 1;
  26.             if(flag == 0 && obstacleGrid[0][i] == 0)
  27.                 dp[0][i] = 1;
  28.             else if (flag == 1 && obstacleGrid[0][i] == 0)
  29.                 dp[0][i] = 0;
  30.         }
  31.         
  32.         for(int i=1;i<m;i++)
  33.         {
  34.             for(int j=1;j<n;j++)
  35.             {
  36.                 if(obstacleGrid[i][j] != 1)
  37.                     dp[i][j] = dp[i-1][j] + dp[i][j-1];
  38.                 else
  39.                     dp[i][j] = 0;
  40.                     
  41.             }
  42.         }
  43.         return dp[m-1][n-1];
  44.     }
  45. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-16 14:24:48 | 只看该作者
全局:
64. Minimum Path Sum
这道题和上面unique path 很像,都可以用dp解决。只不过dp的意义不一样了。在这里是从起点到(i,j)最小路径sum。(i,j)取决于上面和左边的最小值再加上grid[i][j].
初始化,第一行第一列是累加的过程。

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         int m = grid.length;
  4.         int n = grid[0].length;
  5.         if(m == 0 || n == 0)
  6.             return 0;
  7.         
  8.         int[][] dp = new int[m][n];
  9.         dp[0][0] = grid[0][0];
  10.         
  11.         for(int i=1;i<m;i++)
  12.         {
  13.             dp[i][0] = dp[i-1][0] + grid[i][0];
  14.         }
  15.         
  16.         for(int i=1;i<n;i++)
  17.         {
  18.             dp[0][i] = dp[0][i-1] + grid[0][i];
  19.         }
  20.         
  21.         for(int i=1;i<m;i++)
  22.         {
  23.             for(int j=1;j<n;j++)
  24.             {
  25.                 dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
  26.             }
  27.         }
  28.         
  29.         return dp[m-1][n-1];
  30.     }
  31. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-17 02:23:57 | 只看该作者
全局:
Leetcode777. Swap Adjacent in LR String
最近这道题出现的评率比较高在面经里。首先我们要明白的是R和L其实是保持的相对位置,也就是说start和end去掉X之后,这两个string 应该是一样的。
换个思路来说就是,start和End中L/R 的index是有变化的。如果start中的L的index 小于 end中的index,直接return false。 相反,R也是一样的。
  1. class Solution {
  2.     public boolean canTransform(String start, String end) {
  3.         
  4.         int s_len = start.length();
  5.         int e_len = end.length();
  6.         
  7.         int i = 0;
  8.         int j = 0;
  9.         
  10.         while(i<s_len && j<s_len)
  11.         {
  12.             while(i < s_len && start.charAt(i) == 'X')
  13.                 i++;
  14.             while(j < e_len && end.charAt(j) == 'X')
  15.                 j++;
  16.             
  17.             if(i == s_len && j == e_len)
  18.                 return true;
  19.             if(i == s_len || j == e_len)
  20.                 return false;
  21.             
  22.             if(start.charAt(i) != end.charAt(j))
  23.                 return false;
  24.             if((start.charAt(i) == 'L' && i<j) || (start.charAt(i) == 'R' && i>j))
  25.                 return false;
  26.             i++;
  27.             j++;
  28.         }
  29.         
  30.         return true;
  31.     }
  32. }
复制代码
回复

使用道具 举报

🔗
bubbleSort123 2018-12-17 02:39:33 | 只看该作者
全局:
楼主加油, 我也在刷题
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-17 04:28:40 | 只看该作者
全局:
Leetcode 833. Find And Replace in String
这道题首先我们要把indexes从小到大sort一遍,否则你在append的时候会导致index的错乱。
然后就是很基本的想法了,把第一个index之前的append,然后替换掉相应的string,append index和下一个index之间gap的substring, append最后一个index之后的substring


  1.     public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
  2.         int len = indexes.length;
  3.         int[][] sort_index = new int[len][len];
  4.         
  5.         for(int i=0;i<len;i++)
  6.             sort_index[i] = new int[]{indexes[i],i};
  7.         
  8.         Arrays.sort(sort_index, (a,b)->a[0]-b[0]);
  9.         
  10.         StringBuilder sb = new StringBuilder();
  11.         
  12.         int i=0;
  13.         int check_len = 0;
  14.         int starting_index = sort_index[0][0];
  15.         check_len = sources[sort_index[0][1]].length();
  16.         String source = sources[sort_index[0][1]];
  17.         String target = targets[sort_index[0][1]];
  18.         
  19.         if(starting_index != 0) //append substring that's before the first index
  20.             sb.append(S.substring(0, starting_index));
  21.         
  22.         while(i<len)
  23.         {
  24.             starting_index = sort_index[i][0];
  25.             check_len = sources[sort_index[i][1]].length();
  26.             source = sources[sort_index[i][1]];
  27.             target = targets[sort_index[i][1]];
  28.             
  29.             String to_check = S.substring(starting_index, starting_index+check_len);
  30.             if(to_check.equals(source))
  31.             {
  32.                 sb.append(target);
  33.             }else
  34.             {
  35.                 sb.append(to_check);
  36.             }
  37.             
  38.             if(i+1 < len) //append substring that's in between indexes
  39.             {
  40.                 int next_index = sort_index[i+1][0];
  41.                  sb.append(S.substring(starting_index+check_len, next_index));
  42.             }
  43.             
  44.             i++;
  45.         }
  46.         
  47.         if(starting_index+check_len < S.length()) //append substring that's after the last index
  48.             sb.append(S.substring(starting_index+check_len));
  49.         
  50.         return sb.toString();
  51.     }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-17 08:23:38 | 只看该作者
全局:
Leetcode 527 word abbreviation
Google最近的高频题。首先我们把所有word都转换一次,prefix为1。然后对于每一个word我们找是否有相同的encode,如果有,就把他们放在set里面,把prefix+1再encode直到他们不相等为止。
  1. class Solution {
  2.     public List<String> wordsAbbreviation(List<String> dict) {
  3.         int len = dict.size();
  4.         String[] res = new String[len];
  5.         int[] prefix = new int[len];
  6.         
  7.         for(int i=0;i<len;i++)
  8.         {
  9.             prefix[i] = 1;
  10.             res[i] = helper(dict.get(i),prefix[i]);
  11.         }
  12.         
  13.         for(int i=0;i<len;i++)
  14.         {
  15.             while(true)
  16.             {
  17.                 HashSet<Integer> dup = new HashSet<>();
  18.                 for(int j=i+1;j<len;j++)
  19.                 {
  20.                     if(res[i].equals(res[j]))
  21.                         dup.add(j);
  22.                 }
  23.                
  24.                 if(dup.isEmpty())
  25.                     break;
  26.                 dup.add(i);
  27.                
  28.                 for(int k: dup)
  29.                     res[k] = helper(dict.get(k),++prefix[k]);
  30.                
  31.             }
  32.         }
  33.         
  34.         return Arrays.asList(res);
  35.     }
  36.    
  37.     public String helper(String word, int prefix)
  38.     {
  39.         if(prefix+2 >= word.length())
  40.             return word;
  41.         
  42.         int gap = word.length()-prefix-1;
  43.         StringBuilder sb = new StringBuilder(word.substring(0,prefix));
  44.         sb.append(gap);
  45.         sb.append(word.charAt(word.length()-1));
  46.         return sb.toString();
  47.     }
  48. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-17 10:51:58 | 只看该作者
全局:
Leetcode 855. Exam Room
在面经里看到这道题。
我们使用线段分割的方法来做这道题。
我们会创建一个interval的class 来记录目前两两之间的长度,然后创建一个priorityqueue来保存。
每次有人seat进来我们就会poll出最大length的interval,然后将这个interval分成两班。如果有人离开的话,就会找到左右邻居的interval进行合并。
  1. class ExamRoom {
  2.     class Interval {
  3.         int start;
  4.         int end;
  5.         int length;
  6.         public Interval(int start, int end) {
  7.             this.start = start;
  8.             this.end = end;
  9.             if (start == 0 || end == N - 1) {
  10.                 this.length = end - start;
  11.             } else {
  12.                 this.length = (end - start) / 2;
  13.             }
  14.         }
  15.     }
  16.     private PriorityQueue<Interval> pq;
  17.     private int N;
  18.    
  19.     public ExamRoom(int N) {
  20.         this.pq = new PriorityQueue<>((a, b) -> a.length != b.length ? b.length - a.length : a.start - b.start);
  21.         this.N = N;
  22.         pq.offer(new Interval(0, N - 1));
  23.     }
  24.    
  25.     public int seat() {
  26.         Interval in = pq.poll();
  27.         int result;
  28.         if (in.start == 0) {
  29.             result = 0;
  30.         } else if (in.end == N - 1) {
  31.             result = N - 1;
  32.         } else {
  33.             result = in.start + in.length;
  34.         }
  35.         
  36.         if (result > in.start) {
  37.             pq.offer(new Interval(in.start, result - 1));   
  38.         }
  39.         if (in.end > result) {
  40.             pq.offer(new Interval(result + 1, in.end));   
  41.         }
  42.         return result;
  43.     }
  44.    
  45.     public void leave(int p) {
  46.         List<Interval> list = new ArrayList(pq);
  47.         Interval prev = null;
  48.         Interval next = null;
  49.         for (Interval in: list) {
  50.             if (in.end + 1 == p) {
  51.                 prev = in;
  52.             }
  53.             if (in.start - 1 == p) {
  54.                 next = in;
  55.             }
  56.         }
  57.         pq.remove(prev);
  58.         pq.remove(next);
  59.         pq.offer(new Interval(prev == null ? p : prev.start, next == null ? p : next.end));
  60.         
  61.     }
  62. }
复制代码
回复

使用道具 举报

🔗
halowoyaojob 2018-12-17 12:57:07 | 只看该作者
全局:
楼主加油!我也在刷题 在准备fb面试
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表