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

面试刷题咯~每天10道~

🔗
 楼主| soliloquyyy 2018-12-5 11:57:44 | 只看该作者
全局:
Leetcode 189 Rotate Array
其实这道题如果是O(n)的空间复杂度会很简单,就是新创一个array,然后把向右移k step的index 放在新array里就好了。但是发现discuss里面的O(1)确实是一个比较聪明的做法。
就是讲一个数组首先以把整个array翻转,比如【1,2,3,4,5,6,7】 变成【7,6,5,4,3,2,1】。然后把Kstep前(包括K)的数翻转,加入k=3变成【5,6,7,4,3,2,1】。然后再K index后面的翻转
变成【5,6,7,1,2,3,4】
说实话我没太明白这其中为什么这样。感觉记住就好了。。。

  1. class Solution {
  2.     public void rotate(int[] nums, int k) {
  3.         k = k % nums.length;
  4.         reverse(nums, 0, nums.length - 1);
  5.         reverse(nums, 0, k - 1);
  6.         reverse(nums, k, nums.length - 1);
  7.         
  8.     }
  9.     public void reverse(int[] nums, int start, int end)
  10.     {
  11.         while(start < end)
  12.         {
  13.             int temp = nums[start];
  14.             nums[start] = nums[end];
  15.             nums[end] = temp;
  16.             start++;
  17.             end--;
  18.         }
  19.     }
  20. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-5 12:25:40 | 只看该作者
全局:
Leetcode 56 Merge Intervals
这道题呢有一个重点是,如果我们按照一般的方法去做,我们需要对一个interval的endtime和其他interval的start time进行比较,时间复杂度是O(n^2).
而有一个小trick是我们可以把start和end提出来放在两个array里,然后分别sort他们,然后再比较,如果end time比另一个starttime要大则i++ 这样拓展需要merge的界线。
  1. /**
  2. * Definition for an interval.
  3. * public class Interval {
  4. *     int start;
  5. *     int end;
  6. *     Interval() { start = 0; end = 0; }
  7. *     Interval(int s, int e) { start = s; end = e; }
  8. * }
  9. */
  10. class Solution {
  11.     public List<Interval> merge(List<Interval> intervals) {
  12.    
  13.         List<Interval> res = new ArrayList<>();
  14.         if(intervals == null)
  15.             return res;
  16.         int[] start = new int[intervals.size()];
  17.         int[] end = new int[intervals.size()];

  18.         for(int i=0;i<intervals.size();i++)
  19.         {
  20.             start[i] = intervals.get(i).start;
  21.             end[i] = intervals.get(i).end;
  22.         }

  23.         Arrays.sort(start);
  24.         Arrays.sort(end);

  25.         int i=0;
  26.         while(i<intervals.size())
  27.         {
  28.             int start_time = start[i];

  29.             while(i<intervals.size()-1 && start[i+1] <= end[i]) i++;
  30.             int end_time = end[i];
  31.             res.add(new Interval(start_time, end_time));
  32.             i++;
  33.         }

  34.         return res;


  35.     }
  36. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-5 12:37:17 | 只看该作者
全局:
面经:https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=462914&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3089%5D%5Bvalue%5D%5B2%5D%3D2%26searchoption%5B3089%5D%5Btype%5D%3Dcheckbox%26searchoption%5B3046%5D%5Bvalue%5D%3D1%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311%26orderby%3Ddateline&_dsign=a4911dc6

有一堆interval [i,j]表示领导同志们召开记者会的时间
翡翠台要派出香港记者们去参加所有的记者会。
因为香港记者们姿势水平有限,所以一个记者在同一时间只能参加一场记者会
因为香港记者们跑得很快,所以可以在结束完一场记者会后瞬时漂移到下一场
写一个function来告工作人员应该如何安排这些香港记者……使得翡翠台只需要出动最小数量的记者就参加了所有的记者会
其实就是leetcode meeting room 2。
这道题和我刚刚做的很像。
就是如果有重叠就+1;
  1. /**
  2. * Definition for an interval.
  3. * public class Interval {
  4. *     int start;
  5. *     int end;
  6. *     Interval() { start = 0; end = 0; }
  7. *     Interval(int s, int e) { start = s; end = e; }
  8. * }
  9. */
  10. class Solution {
  11.     public int minMeetingRooms(Interval[] intervals) {
  12.         int res = 0;
  13.         if(intervals == null)
  14.             return res;
  15.         int[] start = new int[intervals.length];
  16.         int[] end = new int[intervals.length];

  17.         for(int i=0;i<intervals.length;i++)
  18.         {
  19.             start[i] = intervals[i].start;
  20.             end[i] = intervals[i].end;
  21.         }

  22.         Arrays.sort(start);
  23.         Arrays.sort(end);

  24.         int i=0;
  25.         int j=0;
  26.         while(i<intervals.length)
  27.         {
  28.             if(start[i]<end[j])
  29.                 res++;
  30.             else
  31.                 j++;
  32.             i++;
  33.         }

  34.         return res;
  35.     }
  36. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-5 14:48:03 | 只看该作者
全局:
308. Range Sum Query 2D - Mutable
这道题需要将matrix[i][j]储存i-1row以上所有的和。简单的idea
  1. class NumMatrix {
  2.     int[][] presum;
  3.     int[][] matrix;
  4.    
  5.     public NumMatrix(int[][] matrix) {
  6.         if(   matrix           == null
  7.        || matrix.length    == 0
  8.        || matrix[0].length == 0   ){
  9.         return;   
  10.      }
  11.         
  12.         
  13.         this.matrix = matrix;
  14.         presum = new int[matrix.length+1][matrix[0].length];
  15.         
  16.         for(int i=1;i<presum.length;i++)
  17.         {
  18.             for(int j=0;j<presum[0].length;j++)
  19.             {
  20.                 presum[i][j] = presum[i-1][j] + matrix[i-1][j];
  21.             }
  22.         }
  23.     }
  24.    
  25.     public void update(int row, int col, int val) {
  26.          for(int i = row + 1; i < presum.length; i++){
  27.             presum[i][col] = presum[i][col] - matrix[row][col] + val;
  28.         }
  29.         matrix[row][col] = val;
  30.     }
  31.    
  32.     public int sumRegion(int row1, int col1, int row2, int col2) {
  33.         int ret = 0;
  34.    
  35.         for(int j = col1; j <= col2; j++){
  36.             ret += presum[row2 + 1][j] - presum[row1][j];
  37.         }
  38.         
  39.         return ret;
  40.    
  41.     }
  42. }

  43. /**
  44. * Your NumMatrix object will be instantiated and called as such:
  45. * NumMatrix obj = new NumMatrix(matrix);
  46. * obj.update(row,col,val);
  47. * int param_2 = obj.sumRegion(row1,col1,row2,col2);
  48. */
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-5 16:06:19 | 只看该作者
全局:
接上一条,用binary index tree 实现,
可以到O(logn)的query 和update,对于mutable 的array应该算是最优了。
  1. public class NumMatrix {

  2.     int[][] tree;
  3.     int[][] nums;
  4.     int m;
  5.     int n;
  6.    
  7.     public NumMatrix(int[][] matrix) {
  8.         if (matrix.length == 0 || matrix[0].length == 0) return;
  9.         m = matrix.length;
  10.         n = matrix[0].length;
  11.         tree = new int[m+1][n+1];
  12.         nums = new int[m][n];
  13.         for (int i = 0; i < m; i++) {
  14.             for (int j = 0; j < n; j++) {
  15.                 update(i, j, matrix[i][j]);
  16.             }
  17.         }
  18.     }

  19.     public void update(int row, int col, int val) {
  20.         if (m == 0 || n == 0) return;
  21.         int delta = val - nums[row][col];
  22.         nums[row][col] = val;
  23.         for (int i = row + 1; i <= m; i += i & (-i)) {
  24.             for (int j = col + 1; j <= n; j += j & (-j)) {
  25.                 tree[i][j] += delta;
  26.             }
  27.         }
  28.     }

  29.     public int sumRegion(int row1, int col1, int row2, int col2) {
  30.         if (m == 0 || n == 0) return 0;
  31.         return sum(row2+1, col2+1) + sum(row1, col1) - sum(row1, col2+1) - sum(row2+1, col1);
  32.     }
  33.    
  34.     public int sum(int row, int col) {
  35.         int sum = 0;
  36.         for (int i = row; i > 0; i -= i & (-i)) {
  37.             for (int j = col; j > 0; j -= j & (-j)) {
  38.                 sum += tree[i][j];
  39.             }
  40.         }
  41.         return sum;
  42.     }
  43. }
复制代码
回复

使用道具 举报

🔗
Scala688 2018-12-6 00:34:51 | 只看该作者
全局:
加油加油, 我也在刷题
回复

使用道具 举报

🔗
fymaterials 2018-12-6 11:27:53 | 只看该作者
全局:
赞, 介绍经验贴
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-6 13:38:43 | 只看该作者
全局:
Leetcode 43 Multiply Strings
这道题呢很简答就是正常的两个数相乘的实现
  1. class Solution {
  2.     public String multiply(String num1, String num2) {
  3.             int m = num1.length(), n = num2.length();
  4.         int[] result = new int[m+n
  5.                               ];
  6.         for(int i=m-1;i>=0;i--)
  7.         {
  8.                 for(int j=n-1;j>=0;j--)
  9.                 {
  10.                 int mul = (num1.charAt(i)-'0')*(num2.charAt(j)-'0');
  11.                 int p2 = i+j+1;
  12.                 int p1 = i+j;
  13.                 // mul += result[pos_low];
  14.                 int sum = mul + result[p2];
  15.                 result[p2] = sum%10;
  16.                 result[p1] += sum/10;
  17.                 }
  18.         }
  19.         
  20.     StringBuilder sb = new StringBuilder();
  21.     for(int p : result) if(!(sb.length() == 0 && p == 0)) sb.append(p);
  22.     return sb.length() == 0 ? "0" : sb.toString();
  23.     }
  24. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-6 13:55:16 | 只看该作者
全局:
Leetcode 94. Binary Tree Inorder Traversal
因为是inorder也就是先打印出左边,再中间,最后右边。
我们首先用while loop移动到最左边的node,然后用stack记录移动的值,最后把最左边的加入result。这样当你pop的时候就可以找到最近的上一个node,然后再循环右边。
  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.     public List<Integer> inorderTraversal(TreeNode root) {
  12.         List<Integer> res = new ArrayList<>();
  13.         Stack<TreeNode> st = new Stack<>();
  14.         
  15.         TreeNode cur = root;
  16.         
  17.         while(cur != null || !st.empty())
  18.         {
  19.             while(cur != null)
  20.             {
  21.                 System.out.println("Left path"+cur.val);
  22.                 st.push(cur);
  23.                 cur = cur.left;
  24.                
  25.             }
  26.             
  27.             cur = st.pop();
  28.             System.out.println("pop val"+cur.val);
  29.             res.add(cur.val);
  30.             
  31.             cur = cur.right;
  32.             
  33.         }
  34.         return res;
  35.         
  36.         
  37.         
  38.         
  39.     }
  40. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-6 14:35:16 | 只看该作者
全局:
Leetcode 23 Merge K sorted List
这道题的核心在于用一个priorityqueue来保持每个linkedlist当前node,poll出最小val的,然后只要poll出来的node.next不是null,就把下一个加进去。就OK拉
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. class Solution {
  10.     public ListNode mergeKLists(ListNode[] lists) {
  11.         
  12.         ListNode head = new ListNode(0);
  13.         ListNode res = head;
  14.         
  15.         PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b)->a.val-b.val);
  16.         
  17.         for(int i=0;i<lists.length;i++)
  18.         {
  19.             if(lists[i] != null)
  20.                 pq.add(lists[i]);
  21.         }
  22.         
  23.         
  24.         while(!pq.isEmpty())
  25.         {
  26.             ListNode temp = pq.poll();
  27.             head.next = temp;
  28.             head = head.next;
  29.             if(temp.next != null)
  30.                 pq.add(temp.next);
  31.         }
  32.         
  33.         return res.next;
  34.     }
  35. }
复制代码
回复

使用道具 举报

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

本版积分规则

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