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

面试刷题咯~每天10道~

🔗
 楼主| soliloquyyy 2018-12-2 04:50:01 | 只看该作者
全局:
Leetcode 278. First Bad Version
这道题,很简单binary search想法。
直接贴代码把
需要注意的就是,当时goodversion的时候,我们是mid+1 而bad=mid。因为我们找的是badversion,因为mid本就是good,bad只能从下一个开始。而bad的话,你不能排除掉本身。
  1. public class Solution extends VersionControl {
  2.     public int firstBadVersion(int n) {
  3.         int start = 1;
  4.         int end = n;
  5.         int mid = 0;
  6.         while(start<end)
  7.         {
  8.             mid = start+(end-start)/2;
  9.             if(isBadVersion(mid))
  10.             {
  11.                 end = mid;
  12.             }else
  13.             {
  14.                 start = mid+1;
  15.             }
  16.         }
  17.         
  18.         return start;
  19.     }
  20. }

复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-2 06:20:02 | 只看该作者
全局:
本帖最后由 soliloquyyy 于 2018-12-2 08:55 编辑

Leetcode 322 Coin Change
这道题其实挺日常的,解决的方法也很intuitive。
假设我们想要去拼凑11块钱,而我们已经有10块了,而且凑巧我们有1元的面额,那么就只需要再加一块即可。output就是10块钱的output再加一。
所以这道题的idea就是,用dp。dp储存的是拼凑amount最少要多少硬币。
假设我们需要拼凑n块钱,我们从0元开始遍历,在每次iteration当中再遍历所有面额,如果面额比需要的amount少,而且我们dp储存的里面没有之前初始化的值,那么我们就比较看现在dp中储存的值和上一个面额储存的值+1谁小,我们就用哪个。
代码如下
  1.         public int coinChange(int[] coins, int amount)
  2. {
  3.     if(coins==null || amount <0 || coins.length <= 0)
  4.         return 0;

  5.         int[] dp = new int[amount+1];
  6.         Arrays.fill(dp, Integer.MAX_VALUE);
  7.         dp[0]=0;

  8.         for(int i=0;i<=amount;i++)
  9.         {
  10.                 for(int j=0;j<coins.length;j++)
  11.                 {
  12.                         if(coins[j]<=i && dp[i - coins[j]] != Integer.MAX_VALUE)
  13.                         dp[i] = Math.min(dp[i - coins[j]]+1, dp[i]);
  14.                 }
  15.         }

  16.     if (dp[amount] == Integer.MAX_VALUE)
  17.                 return -1;
  18.         else
  19.                 return dp[amount];

  20. }
复制代码
[/i][/i]
我还看到一种解法,在forloop上有不同
  1. public int coinChange(int[] coins, int amount) {
  2.     if (amount < 1) return 0;
  3.     int[] dp = new int[amount + 1];
  4.     Arrays.fill(dp, Integer.MAX_VALUE);
  5.     dp[0] = 0;
  6.     for (int coin : coins) {
  7.         for (int i = coin; i <= amount; i++) {
  8.             if (dp[i - coin] != Integer.MAX_VALUE) {
  9.                 dp[i] = Math.min(dp[i], dp[i - coin] + 1);
  10.             }
  11.         }
  12.     }
  13.     return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
  14. }
复制代码


[/i][/i]
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-2 07:12:55 | 只看该作者
全局:
518. Coin Change 2
这种能够用之前一道题的第二种solution进行扩展。思路和第一个大同小异就不解释了。
  1. class Solution {
  2.     public int change(int amount, int[] coins) {
  3.         // if(coins == null || coins.length == 0 || amount == 0)
  4.         //     return 0;
  5.         // if(coins.length == 1 && coins[0] != amount)
  6.         //     return 0;
  7.         // if(coins.length == 1 && coins[0] == amount)
  8.         //     return 1;
  9.         
  10.         int[] dp = new int[amount+1];
  11.         dp[0] = 1;
  12.         
  13.         for(int coin: coins)
  14.         {
  15.             for(int i=coin;i<=amount;i++)
  16.             {
  17.                 dp[i] += dp[i-coin];
  18.             }
  19.         }
  20.         
  21.         return dp[amount];
  22.     }
  23. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-2 07:14:16 | 只看该作者
全局:
终于第一天的10题做完了。
今晚尽量赶工第二天的10题~~
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-2 08:22:34 | 只看该作者
全局:
Leetcode 39. Combination Sum
这道题可以用recursive来做。
我们首先要sort一下提供的candidates,因为如果不sort的话,结果会少很多。
因为我们的函数是从最小的candidate开始的,然后慢慢增加,这样就能把所有的possible outcome遍历完整。
我们会maintain一个target,如果target == 0说明,这个list在之前已经满足条件了,直接return上一轮的。
如果小于0,则直接break,这个combination是invalid。
大于0的话,我们加入目前的所在的candidate。然后target减少相应的指。这样recursive的call下去。
  1. class Solution {
  2.     public void helper( List<List<Integer>> res,int[] candidates,int target,int index,List<Integer> cur_list)
  3.     {
  4.         if(target == 0)
  5.             res.add(new ArrayList<Integer>(cur_list));
  6.         if(target > 0)
  7.         {
  8.             for(int i=index;i<candidates.length;i++)
  9.             {
  10.                 if(candidates[i] > target)
  11.                     break;
  12.    
  13.                     cur_list.add(candidates[i]);
  14.                     helper(res,candidates,target-candidates[i],i,cur_list);
  15.                     cur_list.remove(cur_list.size()-1);
  16.             }
  17.         }
  18.     }
  19.    
  20.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  21.         if(candidates == null || candidates.length == 0 || target <=0 )
  22.             return null;
  23.         List<List<Integer>> res = new ArrayList<>();
  24.         Arrays.sort(candidates);
  25.         helper(res, candidates, target, 0, new ArrayList<>());
  26.         return res;
  27.     }
  28. }
复制代码
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-2 08:54:58 | 只看该作者
全局:
Leetcode 40. Combination Sum II
这道题是上面Combination sum的follow up
区别在于,上面的element是可以多次使用且没有duplicate,这道题不仅没有去处duplicate而且每个元素只能使用一次
所以递归的时候要把index+1来避免使用多次元素,同时在判断条件的时候要注意比较前一个元素和先一个是不是一样的,如果是的话continue,从此来避免造成结果里的duplicate
  1. class Solution {
  2.     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         List<Integer> curList = new ArrayList<>();
  5.         if(candidates==null)
  6.             return res;
  7.         
  8.         Arrays.sort(candidates);
  9.         
  10.         helper(candidates,target, 0, curList, res);
  11.         return res;
  12.     }
  13.    
  14.     public void helper(int[] candidates, int target, int index, List<Integer> cur_list, List<List<Integer>> res)
  15.     {
  16.         if(target == 0)
  17.         {
  18.             res.add(new ArrayList<Integer>(cur_list));
  19.         }else if (target > 0)
  20.         {
  21.             for(int i=index;i<candidates.length;i++)
  22.             {
  23.                 if(i != index && candidates[i] == candidates[i-1])
  24.                     continue;
  25.                 cur_list.add(candidates[i]);
  26.                 helper(candidates,target-candidates[i],i+1,cur_list,res);
  27.                 cur_list.remove(cur_list.size()-1);
  28.             }
  29.         }
  30.     }
  31. }
复制代码
回复

使用道具 举报

🔗
terrytan95 2018-12-2 10:27:50 | 只看该作者
全局:
加油加油, 我也在刷题
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2018-12-3 06:41:50 | 只看该作者
全局:
Leetcode 268 Missing Number
这道题可以用两种方法。
首先因为这个给定的数组的特殊性,我们可以用等差数列公式求出sum 然后再循环一遍减去这个当前元素,剩下的就是所要return的值。
另一个方法就是用bit manipulation的xor. 因为xor的特性是a^b^b = a 也就是说一个值xor两次则会被消除。那么在遍历数组的情况下,如果有一个值missing,也就是只xor一次,那么最后最后返回的值也就是这个啦。
  1. class Solution {
  2.     public int missingNumber(int[] nums) {
  3.     int len = nums.length;
  4.     int sum = (0+len)*(len+1)/2;
  5.     for(int i=0; i<len; i++)
  6.         sum-=nums[i];
  7.     return sum;
  8. }   
  9. }
复制代码

  1. class Solution {
  2.     public int missingNumber(int[] nums) {
  3.     int res = 0;
  4.     for(int i=1;i<=nums.length;i++)
  5.     {
  6.         res =res ^ i^nums[i-1];
  7.     }

  8. return res;
  9.     }
  10. }
复制代码
回复

使用道具 举报

全局:
建议楼主可以把所有做过的题目总结分类,把思绪写在本子上,每天尽量抽时间来重温,这样对于题目的理解和举一反三的能力很有帮助~加油~
回复

使用道具 举报

🔗
ldzhjn 2018-12-3 10:05:37 | 只看该作者
全局:
楼主加油 支持你
回复

使用道具 举报

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

本版积分规则

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