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

面试刷题咯~每天10道~

🔗
 楼主| soliloquyyy 2018-12-6 14:57:44 | 只看该作者
全局:
本帖最后由 soliloquyyy 于 2018-12-6 15:02 编辑

684. Redundant Connection
这道题是union find用来找cycle的一个application。
扫描所有的edge array,如果两个点的uion的时候,他们的祖先是一样的说明这个是cycle
  1. class Solution {
  2.     class unionFind{
  3.         int[] parent;
  4.         int[] rank;
  5.         public unionFind(int len)
  6.         {
  7.             parent = new int[len+1];
  8.             rank = new int[len+1];
  9.             // parent = new int[edges.length+1];
  10.             for(int i=1;i<parent.length;i++)
  11.             {
  12.                 parent[i]=i;
  13.                 rank[i] = 1;
  14.             }
  15.                
  16.         
  17.         }
  18.         
  19.         public int find(int x)
  20.         {
  21.             if(x == parent[x])
  22.                 return x;
  23.             return find(parent[x]);
  24.         }
  25.         
  26.         public boolean union(int x, int y)
  27.         {
  28.             int rootx = find(x);
  29.             int rooty = find(y);
  30.             
  31.             if(rootx == rooty)
  32.                 return false;
  33.             if(rank[rootx] > rank[rooty])
  34.             {
  35.                 parent[rooty] = rootx;
  36.                 rank[rootx] += rank[rooty];
  37.             }else
  38.             {
  39.                 parent[rootx] = rooty;
  40.                 rank[rooty] += rank[rootx];
  41.             }
  42.                
  43.             
  44.             return true;
  45.             
  46.         }
  47.     }
  48.    
  49.     public int[] findRedundantConnection(int[][] edges) {
  50.         unionFind uf = new unionFind(edges.length);
  51.         
  52.         for(int[] edge: edges)
  53.         {
  54.             if(uf.union(edge[0],edge[1]) == false)
  55.                 return edge;
  56.         }
  57.         return new int[]{};
  58.     }
  59. }
复制代码

回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-6 15:33:36 | 只看该作者
全局:
Leetcode 138. Copy List with Random Pointer
这道题有两种解法,time 都是O(n) 但是一种空间上O(n) ,另一种O(1).
O(n)的做法是用一个hashmap存储旧node和新node的关系。创建两个pointer分别指向老list和新list。首先循环一遍,把所有node加入hashmap,然后把新node加入list,复制random到hashmap,加入random到list。同时更新两个pointer
  1. /**
  2. * Definition for singly-linked list with a random pointer.
  3. * class RandomListNode {
  4. *     int label;
  5. *     RandomListNode next, random;
  6. *     RandomListNode(int x) { this.label = x; }
  7. * };
  8. */
  9. public class Solution {
  10.     public RandomListNode copyRandomList(RandomListNode head) {
  11.         HashMap<RandomListNode, RandomListNode> hs = new HashMap<>();
  12.         
  13.         RandomListNode dummy = new RandomListNode(0);
  14.         RandomListNode res =  dummy;
  15.         
  16.         while(head != null)
  17.         {
  18.             if(!hs.containsKey(head))   
  19.                 hs.put(head, new RandomListNode(head.label));
  20.             
  21.             dummy.next = hs.get(head);
  22.             
  23.             if(head.random != null)
  24.             {
  25.                 if(!hs.containsKey(head.random))
  26.                     hs.put(head.random, new RandomListNode(head.random.label));
  27.             }
  28.             
  29.             dummy.next.random = hs.get(head.random);
  30.             
  31.             head = head.next;
  32.             dummy = dummy.next;
  33.         }
  34.         return res.next;  
  35.         
  36.         
  37.         
  38.     }
  39. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-6 15:43:27 | 只看该作者
全局:

Leetcode 138. Copy List with Random Pointer solution 2

另一种做法是O(1)的空间。就是在原有list基础上做文章。
在每个node的next都insert一个和之前node一模一样的copy,然后根据原来node 的next 和random 关系链接node copy之间的关系。
最后把原有node删除就好了。
  1. /**
  2. * Definition for singly-linked list with a random pointer.
  3. * class RandomListNode {
  4. *     int label;
  5. *     RandomListNode next, random;
  6. *     RandomListNode(int x) { this.label = x; }
  7. * };
  8. */
  9. public class Solution {
  10.     public RandomListNode copyRandomList(RandomListNode head) {
  11.         
  12.         RandomListNode res =  head;
  13.         
  14.         while(head != null)
  15.         {
  16.             RandomListNode temp = new RandomListNode(head.label);
  17.             temp.next = head.next;
  18.             head.next = temp;
  19.             head = head.next.next;
  20.         }
  21.         
  22.         head = res;
  23.         while(head != null)
  24.         {
  25.             if(head.random != null)
  26.                 head.next.random = head.random.next;
  27.             head = head.next.next;
  28.         }
  29.         
  30.         head = res;
  31.         RandomListNode dummy = new RandomListNode(0);
  32.         RandomListNode dummy1 = dummy;
  33.         while(head != null)
  34.         {
  35.             dummy.next = head.next;
  36.             head.next = head.next.next;
  37.             dummy = dummy.next;
  38.             head = head.next;
  39.         }
  40.         
  41.         return dummy1.next;
  42.         
  43.         
  44.       
  45.     }
  46. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-7 01:12:07 | 只看该作者
全局:
369. Plus One Linked List
这道题有一些值得分享的小思想在里面。当我们把一个数加一的时候,我们会遇到两种情况,要么,这个数的结果表现为最后一位加一,比如13+1 = 14.这种情况比较好处理,就是直接把最低位加一就好了。
还有一种情况是要进位,比如19+1 = 20. 这个时候我们要把没进行加一之前的9变成0 然后往这之前以为加1。 而在这种情况里面,如果需要进位的是最高位,则需要新增以为,比如999+1=1000.
而在linkedlist里面,第二种方法能够很好的处理,只需要一个小trick。我们可以在head之前新增一个dummy node,值为0,如果要到999+1这种情况,我们就把dummy node的值变成1,然后返回dummy。而如果不需要新增位数,我们就可以返回dummy.next。
这道题呢,我们可以用两个pointer。一个pointer i记录最后一个不是9的node,而j呢走到最后一位。如果j的值是9,那么我们就把i所在node的值+1,然后把i到最后的node都设为0. 如果j不是9,直接+1就好了。
  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 plusOne(ListNode head) {
  11.         ListNode dummy = new ListNode(0);
  12.         dummy.next = head;
  13.         ListNode i = dummy;
  14.         ListNode j = dummy;
  15.         while(j.next != null)
  16.         {
  17.             if(j.val != 9)
  18.                 i = j;
  19.             j = j.next;
  20.         }
  21.         
  22.         if(j.val == 9)
  23.         {
  24.             i.val++;
  25.             while(i.next != null)
  26.             {
  27.                 i=i.next;
  28.                 i.val = 0;
  29.             }
  30.         }else
  31.         {
  32.             j.val++;
  33.         }
  34.         if(dummy.val == 0)
  35.             return dummy.next;
  36.         else
  37.             return dummy;
  38.         
  39.     }
  40. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-7 05:15:00 | 只看该作者
全局:
Leetcode 135. Candy
这道题有两个条件,第一每个小孩必须有一个,那我们可以首先创建一个int array记录每个小孩的candy数量,初始化为所有的都是1.
接着,另一个条件是,如果旁边小孩的分数高则candy数量要比自己大。这下我们可以分两个情况考虑。
首先左边的小孩,和右边的小孩。
我们从index = 1开始遍历,比较他左边的小孩,如果比左边大,则他的值是左边小孩的值+1
同时我们从右边遍历,但是我们不能使用同样的赋值方法,因为这样的话,原来左边小孩的值可能会被重新覆盖掉。
这下,从倒数第二个开始,比较他右边的小孩,如果大的话,赋值为他自己本来的值和他右边小孩的值+1 中大的那一个。
  1. class Solution {
  2.     public int candy(int[] ratings) {
  3.         if(ratings.length == 0)
  4.             return 0;
  5.         
  6.         int[] candy = new int[ratings.length];
  7.         
  8.         Arrays.fill(candy, 1);
  9.         
  10.         for(int i=1;i<ratings.length;i++)
  11.         {
  12.             if(ratings[i] > ratings[i-1])
  13.                 candy[i] = candy[i-1] + 1;
  14.         }
  15.         
  16.         for(int i=ratings.length-2;i>=0;i--)
  17.         {
  18.             if(ratings[i] > ratings[i+1])
  19.                 candy[i] = Math.max(candy[i],candy[i+1]+1);
  20.         }
  21.         
  22.         int sum = 0;
  23.         for(int can: candy)
  24.             sum+=can;
  25.         
  26.         return sum;
  27.     }
  28. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-7 09:27:52 | 只看该作者
全局:
Leetcode 496 Next Greater Element I
虽然这是一道easy难度的题,但是能想到用Stack也不是很容易。这道题如果用O(n^2)确实很容易,也是最容易想到的。
而这道题优化关键在于stack。首先我们需要一个stack来存储目前最大数,和一个hashmap来存储num2里面每个元素右边第一个最大的数。
首先我们遍历一遍nums2,从右往左,因为这样能够控制右边个数,从0开始keep track of 较大的数。
然后在循环里检查,
1. 如果stack是空(说明目前右边没有大数),则把目前的数push进去,map里面标记为-1;
2.如果不是空,检查:
是否目前的元素大于stack最顶端的,如果是,则一直pop stack直到stack里面的数大于目前的数或者stack全部pop完了。如果结束条件是第一种,就在map里面标记为stack最顶端的数,若是第二种则为-1.然后把目前的数push进去stack;
如果目前元素小于stack最顶端,则在map里标记为最顶端的数。
  1. class Solution {
  2.     public int[] nextGreaterElement(int[] nums1, int[] nums2) {
  3.         Map<Integer, Integer> hs = new HashMap<>();
  4.         Stack<Integer> st = new Stack<>();
  5.         
  6.         for(int i=nums2.length-1;i>=0;i--)
  7.         {
  8.             int cur = nums2[i];
  9.             while(!st.isEmpty() && cur>st.peek())
  10.                 st.pop();
  11.             
  12.             if(st.isEmpty())
  13.             {
  14.                 hs.put(cur,-1);
  15.             }else
  16.             {
  17.                 hs.put(cur,st.peek());
  18.             }
  19.             st.push(cur);
  20.         }
  21.         
  22.         int[] res = new int[nums1.length];
  23.         for(int i=0;i<res.length;i++)
  24.         {
  25.             res[i] = hs.get(nums1[i]);
  26.         }
  27.         
  28.         return res;
  29.     }
  30. }
复制代码

回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-7 10:51:12 | 只看该作者
全局:
Leetcode 527. Word Abbreviation
最近经常看到的高频面经题
其实没有什么巧的,就是一个很简单的思想。
首先把所有string都保留头尾压缩一下,然后对于每个string 找相同的case,如果有就把前面保留的部分增加1个,然后再压缩,直到没有相同的压缩后的string才停止。

  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.             res[i] = abbreviater(dict.get(i),1);
  10.         }
  11.         
  12.         for(int i=0;i<len;i++)
  13.         {
  14.             while(true)
  15.             {
  16.                 HashSet<Integer> set = new HashSet<>();
  17.                 for(int j=i+1;j<len;j++)
  18.                 {
  19.                     if(res[i].equals(res[j]))
  20.                         set.add(j);
  21.                 }
  22.                 if(set.isEmpty())
  23.                     break;
  24.                 set.add(i);
  25.                 for(int k: set)
  26.                     res[k] = abbreviater(dict.get(k),++prefix[k]);
  27.             }
  28.         }
  29.         
  30.         return Arrays.asList(res);
  31.     }
  32.    
  33.    
  34.     public String abbreviater(String str, int prefix)
  35.     {
  36.         if(prefix >= str.length()-2)
  37.             return str;
  38.         StringBuilder sb = new StringBuilder();
  39.         sb.append(str.substring(0,prefix));
  40.         int gap = str.length() - 1 - prefix;
  41.         sb.append(gap+"");
  42.         sb.append(str.charAt(str.length()-1));
  43.         return sb.toString();
  44.     }
  45. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-7 12:34:02 | 只看该作者
全局:
382. Linked List Random Node
这道题还真让我学习到了很多。我们日常中去randomly pick一个number是怎么做的?把所有number存起来,然后给他们一个index, 产生随机数,pick这个随机数的index。
但如果是data stream呢?或者无穷的data呢?我们就需要不同的做法了。让我们首先考虑几个case
如果是只有一个data,那我们直接return这个data,因为概率为100%
如果是有两个data,我们怎么pick呢?我们会产生一个0-1的随机数,如果大于0.5,则pick第一个,否则选第二个。
如果有三个data,我们怎么选。
如果第一个data point保留了下来,也就是说,他在第一轮保留了概率为1,第二轮1/2概率保留了,我们要达到1/3 的总概率,算出来,我们需要在第三轮2/3的概率选1才能总概率1/3;
同样的对于data point 2, 也是需要2/3的概率。
而对于第三个data point 3,我们只需要1/3。 那么我们只需要产生一个0-3的int随机数,看是不是是否等于3就可以了。这样保证了第三个datapoint是1/3的概率取得,同时也保证了其他data point概率是2/3。
  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.     private ListNode head;
  11.     private Random random;
  12.     /** @param head The linked list's head.
  13.         Note that the head is guaranteed to be not null, so it contains at least one node. */
  14.     public Solution(ListNode head) {
  15.         this.head = head;
  16.         random = new Random();
  17.     }
  18.    
  19.     /** Returns a random node's value. */
  20.     public int getRandom() {
  21.         ListNode cur = head;
  22.         int res = cur.val;
  23.         for(int i=1; cur.next != null;i++)
  24.         {
  25.             cur = cur.next;
  26.             if(random.nextInt(i+1) == i)
  27.                 res = cur.val;
  28.         }
  29.         
  30.         return res;
  31.     }
  32. }

  33. /**
  34. * Your Solution object will be instantiated and called as such:
  35. * Solution obj = new Solution(head);
  36. * int param_1 = obj.getRandom();
  37. */
复制代码
回复

使用道具 举报

🔗
811869280 2018-12-7 16:57:52 | 只看该作者
全局:
楼主加油!祝flag不倒!
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-8 02:16:17 | 只看该作者
全局:
811869280 发表于 2018-12-7 16:57
楼主加油!祝flag不倒!

谢谢谢谢~~大家一起加油!
回复

使用道具 举报

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

本版积分规则

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