空气床电面面经

题很简答，有一个菜单，求菜品总价达到target的combination。自

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

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

面试前还是到coderpad上练一练

题和解答如下图。。。。新建的类要写成static还满坑的。
来点大米吧~


补充内容 (2019-9-12 15:18):
这道题按图这样做是不行的！！！Double运算很坑，建议认真复习！

请问 "a, b" 和 "b, a"算两个吗？结果可以有顺序不同的重复是吗？

奋斗的叉子 发表于 2019-9-12 14:38
请问 "a, b" 和 "b, a"算两个吗？结果可以有顺序不同的重复是吗？

不算。。。。。。。。。。。

longmeier2008 发表于 2019-9-12 15:00
不算。。。。。。。。。。。

那楼主的答案好像会是"a,d" "d,a"
Given target = 2.8
如果我没搞错的话

longmeier2008 发表于 2019-9-12 11:04
题和解答如下图。。。。新建的类要写成static还满坑的。
来点大米吧~

我在coderpad上试了一下，其实新建的类也可以不用写成static

发一下我的代码吧 是OC写的。

1. #import <Foundation/Foundation.h>
   
2. #import <stdio.h>
   
3. 
   
4. @interface MenuItemSolution : NSObject
   
5. 
   
6. - (NSString *)findMenuFor:(double)target;
   
7. 
   
8. @end
   
9. 
   
10. @interface MenuItem : NSObject
    
11. @property(nonatomic, strong) NSString *name;
    
12. @property(nonatomic, assign) double price;
    
13. - (instancetype)initWith:(NSString *)name price:(double)price;
    
14. @end
    
15. 
    
16. @implementation MenuItem
    
17. 
    
18. - (instancetype)initWith:(NSString *)name price:(double)price
    
19. {
    
20.     if (self = [super init]) {
    
21.         self.name = name;
    
22.         self.price = price;
    
23.     }
    
24.     return self;
    
25. }
    
26. 
    
27. @end
    
28. 
    
29. @interface MenuItemSolution()
    
30. 
    
31. @property(nonatomic, strong) NSMutableArray<MenuItem *> *list;
    
32. 
    
33. @end
    
34. 
    
35. @implementation MenuItemSolution
    
36. 
    
37. -(instancetype)init {
    
38.     if (self = [super init]) {
    
39.         self.list = [NSMutableArray array];
    
40.         [self.list addObject:[[MenuItem alloc] initWith:@"a" price:1.8]];
    
41.         [self.list addObject:[[MenuItem alloc] initWith:@"b" price:1.5]];
    
42.         [self.list addObject:[[MenuItem alloc] initWith:@"c" price:1.5]];
    
43.         [self.list addObject:[[MenuItem alloc] initWith:@"d" price:1.5]];
    
44.         [self.list sortUsingComparator:^NSComparisonResult(MenuItem * _Nonnull obj1, MenuItem  * _Nonnull obj2) {
    
45.             if (obj1.price == obj2.price) {
    
46.                 return 0;
    
47.             } else if (obj1.price > obj2.price) {
    
48.                 return 1;
    
49.             } else {
    
50.                 return -1;
    
51.             }
    
52.         }];
    
53.         [self.list enumerateObjectsUsingBlock:^(MenuItem * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
    
54.             NSLog(@"%@:%f", obj.name, obj.price);
    
55.         }];
    
56.     }
    
57.     return self;
    
58. }
    
59. 
    
60. - (NSString *)findMenuFor:(double)target {
    
61.     NSMutableArray<NSString *> *temp = [NSMutableArray array];
    
62.     NSMutableArray<NSMutableArray<NSString *> *> *result = [NSMutableArray array];
    
63.     NSMutableArray *visited = [NSMutableArray new];
    
64.     for(int i = 0; i < self.list.count; i++) {
    
65.         [visited addObject:@(0)];
    
66.     }
    
67.     [self dfs:result temp:temp target:target visited:visited index:0];
    
68.     NSMutableString *str = [NSMutableString string];
    
69.     for(NSMutableArray<NSString *> *subList in result) {
    
70.         [str appendString:@"["];
    
71.         for(NSString *item in subList) {
    
72.             [str appendString:item];
    
73.             [str appendString:@","];
    
74.         }
    
75.         [str appendString:@"],"];
    
76.     }
    
77.     return [str copy];
    
78. }
    
79. 
    
80. - (void)dfs:(NSMutableArray<NSMutableArray<NSString *> *> *)result
    
81.        temp:(NSMutableArray<NSString *> *)temp
    
82.      target:(double)target
    
83.      visited:(NSMutableArray *)visited
    
84.       index:(int)index {
    
85.     if (index >= (int)self.list.count || target < 0) {
    
86.         return;
    
87.     }
    
88.     if (target == 0) {
    
89.         [result addObject:[temp copy]];
    
90.         return;
    
91.     }
    
92.    
    
93.     for (int i = index; i < self.list.count; i++) {
    
94.         MenuItem *item = [self.list objectAtIndex:i];
    
95.         [temp addObject:item.name];
    
96.         [visited replaceObjectAtIndex:i withObject:@(1)];
    
97.         [self dfs:result temp:temp target:target - item.price visited:visited index:i + 1];
    
98.         [temp removeLastObject];
    
99.         [visited replaceObjectAtIndex:i withObject:@(0)];
    
100.     }
     
101. }
     
102. 
     
103. @end
     
104. 
     
105. 
     
106. int main (int argc, const char * argv[])
     
107. {
     
108.   @autoreleasepool {
     
109.     MenuItemSolution *obj = [[MenuItemSolution alloc] init];
     
110.     NSString *res = [obj findMenuFor:3.0];
     
111.     NSLog(@"res:%@", res); ///  res:[b,c,],[b,d,],[c,d,],
     
112.   }
     
113. }
     

复制代码

backtrack，lc三九。顺便想问下设计input是什么意思？是说不能再hard code里写testcase而是一定要写cin的意思吗？

Cerax 发表于 2019-9-26 02:35
backtrack，lc三九。顺便想问下设计input是什么意思？是说不能再hard code里写testcase而是一定要写cin的意 ...

就是method的输入输出自己设计