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

面试刷题咯~每天10道~

🔗
 楼主| soliloquyyy 2018-12-3 11:49:03 | 只看该作者
全局:
louiseruiwenli 发表于 2018-12-3 06:51
建议楼主可以把所有做过的题目总结分类,把思绪写在本子上,每天尽量抽时间来重温,这样对于题目的理解和举 ...

是的是的,感觉重温很重要。之前做过的题过一段时间没看到就又忘了。谢谢你~你也加油
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-3 11:49:17 | 只看该作者
全局:
ldzhjn 发表于 2018-12-3 10:05
楼主加油 支持你

谢谢谢谢~~一起加油
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-3 11:57:32 | 只看该作者
全局:
本帖最后由 soliloquyyy 于 2018-12-3 12:48 编辑

Leetcode 417 Pacific Atlantic Water Flow
这道题有一个小trick就是一定不要从每一点出发去寻找是否能够连同两个海洋。而是可以从两个海洋出发,分别找到他们相连的点,然后再找到两片海洋共同连同的点。这样时间复杂度就会低很多。
所以代码实现上来说呢就是首先创建两个array大小和给定的grid相同,这两个array分别代表着两片海洋对于某一点是否连接的信息,是则为1,不是为0。所以初始化的时候,讲两片海洋自身包含的点先设为1(即左边/上边是太平洋,右边/下面则是大西洋)。同时还需要创建两个array用来存储那些已经visited过的点
接着遍历这些海洋自身所包含的点,用一个dfs的helper函数进行recursive call。
  1. class Solution {
  2.   public void flow(int[][] matrix, int[][] ocean, int[][] visited, int x, int y)
  3.    {
  4.            ocean[x][y] = 1;
  5.         visited[x][y] = 1;
  6.         int[] dx = new int[] {0,0,1,-1};
  7.         int[] dy = new int[] {1,-1,0,0};

  8.         for(int i=0;i<4;i++)
  9.         {
  10.                 if(x+dx[i] >= 0 && x+dx[i]<ocean.length && y+dy[i] >= 0 && y+dy[i]<ocean[0].length && visited[x+dx[i]][y+dy[i]] == 0 && matrix[x+dx[i]][y+dy[i]]>= matrix[x][y])
  11.                 flow(matrix, ocean, visited, x+dx[i], y+dy[i]);
  12.         }

  13.    }




  14.     public List<int[]> pacificAtlantic(int[][] matrix) {
  15.         List<int[]> res = new ArrayList<>();
  16.         if(matrix.length == 0 || matrix[0].length == 0)
  17.         return res;


  18.         int[][] pacific = new int[matrix.length][matrix[0].length];      
  19.                 int[][] atlantic = new int[matrix.length][matrix[0].length];


  20.                 for(int i=0;i<matrix.length;i++)
  21.                 {
  22.                         int[][] pacific_visited = new int[matrix.length][matrix[0].length];      
  23.                 int[][] atlantic_visited = new int[matrix.length][matrix[0].length];
  24.                         flow(matrix,pacific, pacific_visited,i,0);
  25.                         flow(matrix, atlantic, atlantic_visited,i,matrix[0].length-1);
  26.                 }

  27.                 for(int i=0;i<matrix[0].length;i++)
  28.                 {
  29.                         int[][] pacific_visited = new int[matrix.length][matrix[0].length];      
  30.                 int[][] atlantic_visited = new int[matrix.length][matrix[0].length];
  31.                         flow(matrix,pacific, pacific_visited,0,i);
  32.                         flow(matrix, atlantic, atlantic_visited,matrix.length-1,i);
  33.                 }

  34.                 for(int i=0;i<matrix.length;i++)
  35.                 {
  36.                         for(int j=0;j<matrix[0].length;j++)
  37.                         {
  38.                                 if(pacific[i][j] == 1 && atlantic[i][j] == 1)
  39.                                         res.add(new int[]{i,j});
  40.                         }
  41.                 }
  42.                 return res;


  43.                

  44.     }
  45. }


复制代码


回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-3 13:47:50 | 只看该作者
全局:
本帖最后由 soliloquyyy 于 2018-12-3 14:09 编辑

Leetcode 450 Delete Node in BST
这道题有几个步骤,首先找到要删除的node,然后有几种情况需要判断,
1. 如果要删除的node没有children,直接return null就好了
2. 如果有只有左/右children,则直接把左右children提上来代替要删除的node
3. 如果左右children都有,则找到右children subtree里的最小值,然后替换掉要删除的node。

  1. class Solution {
  2.     public TreeNode findMin(TreeNode node)
  3.     {
  4.         while(node.left != null)
  5.                 node = node.left;
  6.         return node;
  7.     }

  8.     public TreeNode deleteNode(TreeNode root, int key) {
  9.         if(root == null)
  10.             return null;
  11.    if(key > root.val)
  12.    {
  13.         root.right = deleteNode(root.right,key);
  14.    }else if(key < root.val)
  15.    {
  16.         root.left = deleteNode(root.left,key);
  17.    }else
  18.    {
  19.         if(root.left == null)
  20.         {
  21.                 return root.right;
  22.         }else if (root.right == null)
  23.                 return root.left;
  24.         TreeNode min = findMin(root.right);
  25.         root.val = min.val;
  26.         root.right = deleteNode(root.right, root.val);

  27.    }
  28.    return root;
  29. }

  30. }
复制代码


回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-3 15:39:09 | 只看该作者
全局:
leetcode 662. Maximum Width of Binary Tree
这道题把null也算进去了。我们可以引入id,用dfs。我们只要知道了一层里的最左边的node id 和最右边的node id,我们就可以计算出这一层的的width。id的左子节点是2*id 和右节点2*id +1 ;
  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.     private int ans;
  12.    
  13.     private void dfs(TreeNode cur, int level, int idx, List<Integer> leftIds) {
  14.         if (cur == null) {
  15.             return;
  16.         }
  17.         if (leftIds.size() == level) {
  18.             leftIds.add(idx);
  19.         }
  20.         ans = Math.max(ans, idx - leftIds.get(level) + 1);
  21.         dfs(cur.left, level + 1, idx * 2, leftIds);
  22.         dfs(cur.right, level + 1, idx * 2 + 1, leftIds);
  23.     }
  24.    
  25.     public int widthOfBinaryTree(TreeNode root) {
  26.         if (root == null) {
  27.             return 0;
  28.         }
  29.         ans = 1;
  30.         List<Integer> leftIds = new ArrayList<>();
  31.         dfs(root, 0, 1, leftIds);
  32.         return ans;
  33.     }
  34. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-3 15:58:50 | 只看该作者
全局:
凌晨2点了。。距离今天的任务还有4道题,有点不太想做新题了。复习一下写在本子上的题目,然后再重新做一下,放在这里。
回复

使用道具 举报

全局:
这个贴要收藏一下
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-4 23:53:49 | 只看该作者
全局:
昨天和女朋友吵架,一天都没更新。今天继续。
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-5 11:05:46 | 只看该作者
全局:
soliloquyyy 发表于 2018-12-4 23:53
昨天和女朋友吵架,一天都没更新。今天继续。

和女朋友和好了,继续写刷题准备面试
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-5 11:38:34 | 只看该作者
全局:
Leetcode 17 Letter Combination Of A Phone Number
很简单的dfs。就是扫描过去整个digits, 每碰到一个数就找出他相应的所有letter,在call dfs的时候加入你当前循环到的一个letter到一个候选string。 当index到digits长度了就结束。这题还是非常intuitive的
  1. class Solution {
  2.     public List<String> letterCombinations(String digits) {

  3.         
  4.         List<String> res = new ArrayList<>();
  5.         
  6.         if(digits == null || digits.length() == 0)
  7.             return res;
  8.         HashMap<Character, char[]> hs = new HashMap<>();
  9.         hs.put('2',new char[]{'a','b','c'});
  10.         hs.put('3',new char[]{'d','e','f'});
  11.         hs.put('4',new char[]{'g','h','i'});
  12.         hs.put('5',new char[]{'j','k','l'});
  13.         hs.put('6',new char[]{'m','n','o'});
  14.         hs.put('7',new char[]{'p','q','r','s'});
  15.         hs.put('8',new char[]{'t','u','v'});
  16.         hs.put('9',new char[]{'w','x','y','z'});
  17.         
  18.         
  19.         helper(digits, hs, res, "", 0);
  20.         return res;
  21.     }
  22.    
  23.     public void helper(String digits, HashMap<Character, char[]> hs, List<String> res, String temp, int letter_index)
  24.     {
  25.         if(letter_index == digits.length())
  26.         {
  27.             res.add(temp);
  28.         }else
  29.         {
  30.             char cur = digits.charAt(letter_index);
  31.             // System.out.println(cur);
  32.             if(hs.containsKey(cur))
  33.             {
  34.                 for(char ch: hs.get(cur))
  35.                 {
  36.                     helper(digits, hs, res, temp+ch,letter_index+1);
  37.                 }
  38.             }else
  39.             {
  40.                
  41.             }
  42.         
  43.         
  44.         
  45.     }
  46.    
  47. }
  48. }
复制代码
回复

使用道具 举报

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

本版积分规则

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