脸家加面，似乎他家最近新题很多？

edyyy 发表于 2017-8-5 11:00
数一数有多少个子集（subset）使得子集里面的最大元素加上最小元素小于K。
A: [2, 3, 5, 7]  K: 8
=> #  ...

3+3<8
所以应该是一个

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

LZ面的是哪个组？是那个做business app的组吗？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

twosumii 发表于 2017-8-5 00:28
哈哈，可是你拿了offer我挂了，呜呜

我刚好碰到做过的题，比较幸运而已。

pomme2016 发表于 2017-8-5 13:27
我自己想一开始用的DP，然后发现真的可以双指针呢。
感觉下面写的代码是对的，跑了几个test case

当 i == j 时, if (nums[i] + nums[j] < K) 要转化成 if (nums[i]  < K) 吧

Darkduke68 发表于 2017-8-6 13:25
不需要加吧，while (i

nums = { 1}, k = 2 呢, 30楼的code , 跑完是0?

第二题双指针是可以，但是不能简单数学方法算subset，会有很多重复的啊。。。

自己写的，比较直接的解法：

1. import java.util.*;
   
2. 
   
3. // 给一个排序好的数组，数一数有多少个子集（subset）使得子集里面的最大元素加上最小元素小于K。
   
4. // A: [2, 3, 5, 7]  K: 8
   
5. // => # of subsets S: Max(S) + Min(S) < K.
   
6. // => [2] , [2, 3], [2, 5], [2, 3, 5], [3] => #: 5
   
7. 
   
8. class LessThanK{
   
9.     public static void main(String[] args) {
   
10.         int[] nums = {2,3,3, 5, 7};
    
11.         int k = 8;
    
12.         LessThanK test = new LessThanK();
    
13.         int res = test.getNumber_noDuplicate(nums, k);
    
14.         System.out.println(res);
    
15.       
    
16.         System.out.println("Backtracking Way:");
    
17.       
    
18.         int res2 = test.getNumber_dfs_Duplicate(nums, k);
    
19.         System.out.println(res2);
    
20.     }
    
21. 
    
22.     // ========= if No Duplicate ===========
    
23.     public int getNumber_noDuplicate(int[] nums, int k) {
    
24.         int cnt = 0;
    
25.         int i = 0, j = nums.length - 1;
    
26. 
    
27.         while (i <= j) {
    
28.             if (nums[i] + nums[j] < k) {
    
29.                 cnt += (int) Math.pow(2, j - i);
    
30.                 i++;
    
31.             } else {
    
32.                 j--;
    
33.             }
    
34.         }
    
35. 
    
36.         return cnt;
    
37.     }
    
38. 
    
39.     // ========= With Dulicate, like Combination Sum II  ========= ：

复制代码

补充内容 (2017-8-6 09:42):
next page （cont..）