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

面试刷题咯~每天10道~

🔗
garyyang 2018-12-10 22:49:43 | 只看该作者
全局:
很多时候我连一道题都要几个星期,你这是神速啊。
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-11 08:03:14 | 只看该作者
全局:
1点50分 发表于 2018-12-10 20:26
请问这是按照什么顺序做的?

基本上是先看地里面经,然后找相应的leetcode
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-11 08:04:00 | 只看该作者
全局:
garyyang 发表于 2018-12-10 22:49
很多时候我连一道题都要几个星期,你这是神速啊。

我也是经常忘记,是需要时间消化的。多做几次就好了,老铁加油~
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-11 08:10:33 | 只看该作者
全局:
Leetcode 33. Search in Rotated Sorted Array
这道题我一开始想的是先把这个sort一遍再用binary search,但看到leetcode上的提示是O(logn)的复杂度,也就是说这道题是想让我们直接用binary search。
因为整个array是sorted,虽然顺序打乱了,但还是有两段。我们可以从判断这两段开始。
首先还是一样用binary search把两个pointer设置在array两端,但while循环的调节要设置为low+ 1 <high。这样能够有效避免死循环。比如说low在index为2,high在index为3,mid就是mid = 2 + 1/2 = 2; 这样就变成了forever loop了。
我们首先要确认的是nums[low] 是不是比nums[mid] 小或者等于,说明我们在一个sort 的array里面,然后再判断target是否在low和mid之间。如果是的话,就把high设置成mid。
  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         if(nums.length == 0)
  4.             return -1;
  5.         
  6.         int low = 0;
  7.         int high = nums.length - 1;
  8.         while(low+1 < high)
  9.         {
  10.             int mid = low + (high-low)/2;
  11.             if(target == nums[mid])
  12.                 return mid;
  13.             
  14.             if(nums[low] <= nums[mid])
  15.             {
  16.                 if(target <= nums[mid] && target >= nums[low])
  17.                 {
  18.                     high = mid;
  19.                 }else
  20.                     low = mid;
  21.             }
  22.             else if(nums[mid] <= nums[high])
  23.             {
  24.                 if(target >= nums[mid] && target <= nums[high])
  25.                 {
  26.                     low = mid;
  27.                 }else
  28.                     high = mid;
  29.             }
  30.         }
  31.         
  32.         if(nums[low] == target) return low;
  33.         if(nums[high] == target) return high;
  34.         return -1;
  35.         
  36.     }
  37. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-11 08:53:34 | 只看该作者
全局:
leetcode 695 Max Area of island
这道题是个特别明显的Graph题,自然而然想到是dfs。但是我第一眼看到max area我就想到了dp,但后来想想貌似dp只能得到正方形的area,这种不规则的应该用不了。correct me if i am wrong.
首先我们iterate整个2d array,如果是1就进行接下来的操作,以当前这个点为基础,像四个方向做dfs。
我们在做dfs的时候为了不重复便利,可以将已经visited的点设为0.
  1. class Solution {

  2.    
  3.     public int maxAreaOfIsland(int[][] grid) {
  4.         if (grid == null || grid.length == 0) {
  5.             return 0;
  6.         }
  7.         int m = grid.length;
  8.         int n = grid[0].length;
  9.         int max = 0;
  10.         for (int i = 0; i < m; i++) {
  11.             for (int j = 0; j < n; j++) {
  12.                 if (grid[i][j] == 1) {
  13.                     int area = dfs(grid, i, j, m, n, 0);
  14.                     max = Math.max(area, max);
  15.                 }
  16.             }
  17.         }
  18.         return max;
  19.     }

  20.     int dfs(int[][] grid, int i, int j, int m, int n, int area) {
  21.         if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
  22.             return area;
  23.         }
  24.         grid[i][j] = 0;
  25.         area++;
  26.         area = dfs(grid, i + 1, j, m, n, area);
  27.         area = dfs(grid, i, j + 1, m, n, area);
  28.         area = dfs(grid, i - 1, j, m, n, area);
  29.         area = dfs(grid, i, j - 1, m, n, area);
  30.         return area;
  31.     }
  32.     }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-11 09:36:18 | 只看该作者
全局:
Leetcode 19. Remove Nth Node From End of List
这道题可以用2 pointers解决。一个fast 一个slow。既然我们需要删除倒数n个,我们可以让这两个pointer距离n个node,这样当fast 到达尾部的时候,slow.next就是要删除的node。我们可以slow.next = slow.next.next来删除。
  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 removeNthFromEnd(ListNode head, int n) {
  11.         
  12.         ListNode dummy = new ListNode(0);
  13.         dummy.next = head;
  14.         ListNode slow = dummy;
  15.         ListNode fast = dummy;
  16.         
  17.         int gap = n;
  18.         for(int i=0;i<n;i++)
  19.             fast = fast.next;
  20.         
  21.         while(fast.next != null)
  22.         {
  23.             fast = fast.next;
  24.             slow = slow.next;
  25.         }
  26.         
  27.         slow.next = slow.next.next;
  28.         return dummy.next;
  29.         
  30.     }
  31. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-12 06:52:33 | 只看该作者
全局:
sorted array,每一个数出现两次,只有一个数只出现一次,找到那个数.
其实我应该训练我自己一看到sorted就往binary search想。这一道题又是binary search的应用。最简单的方法就是扫一遍,但这不是最快的方法。
在一个sort array中如果除了要找的那个element出现一次,其他element都出现两次,这就会有一个小规律。在这个只出现一次的element前面,element的第一个出现都在偶数index上,而在之后,第一次出现都在odd上。我们可以根据这个规律来判断。
首先算mid,如果mid是偶数,则看他之后的那个element是不是和他一样,也就是说,看目前这一段出现在target element之前还是之后。如果一样则说明target在后面,就把low更新。
  1. class Main {
  2.   public static void main(String[] args) {
  3.     int[] test = new int[]{1,1,2,3,3,4,4,5,5};
  4.     //
  5.     int low = 0;
  6.     int high = test.length-1;

  7.     while(low<high)
  8.     {
  9.       int mid = low + (high-low)/2;
  10.       if(mid%2 == 0)
  11.       {
  12.         if(test[mid] == test[mid+1])
  13.           low = mid + 2;
  14.         else
  15.           high = mid;
  16.       }else
  17.       {
  18.         if(test[mid] == test[mid-1])
  19.           low = mid + 1;
  20.         else
  21.           high = mid-1;
  22.       }
  23.     }
  24.    
  25.     System.out.println(test[low]);


  26.   }
  27. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-13 03:53:16 | 只看该作者
全局:
Leetcode 835. Image Overlap
这道题有人在地里po了面经,马上做了。这道题看了discuss之后终于理解了。
我们的思路不应该局限于先怎么找到所有move的方式然后在于找最大overlap。我们应该换个思考方式:当我们move的时候,实际上就是整个图片都在动。
我们首先找到两个图片里1的coordinate存储在两个list里。接着,我们遍历包含A里面1的list,check在B的包含1的list里,他们之间的offset。如果有相同的距离,就频率+1.这些都存在map中。相同的offset距离说明这他们在做某一个move的时候是有overlap的
最后找出这个map中最大频率即可。
  1. class Solution {
  2.     public int largestOverlap(int[][] A, int[][] B) {
  3.         int len = A.length;
  4.         
  5.         List<Integer> index_A = new ArrayList<Integer>();
  6.         List<Integer> index_B = new ArrayList<Integer>();
  7.         
  8.         Map<Integer, Integer> freq = new HashMap<>();
  9.         
  10.         for(int i=0;i<len;i++)
  11.         {
  12.             for(int j=0;j<len;j++)
  13.             {
  14.                 if(A[i][j] == 1)
  15.                 {
  16.                     index_A.add(i*100+j);
  17.                 }
  18.                 if(B[i][j] == 1)
  19.                 {
  20.                     index_B.add(i*100+j);
  21.                 }
  22.             }
  23.         }
  24.         
  25.         
  26.         for(int i: index_A)
  27.         {
  28.             for(int j: index_B)
  29.             {
  30.                 freq.put(i-j, freq.getOrDefault(i-j,0)+1);
  31.             }
  32.         }
  33.         
  34.         int res = 0;
  35.         for(int i: freq.values())
  36.         {
  37.             res = Math.max(res, i);
  38.         }
  39.         
  40.         return res;
  41.     }
  42. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-13 03:53:38 | 只看该作者
全局:
chenling1994122 发表于 2018-12-12 12:50
hello, 我也那天面,要不要一起准备哇

你是咋准备的?
回复

使用道具 举报

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

本版积分规则

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