空气床 电面

电面题目如同：

今天(Mar 11) 刚

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

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

CUZ_CODE_0        ]

是不是没考虑   比如 num 12000  Lower Bound 200.。。。Leading Zero

感觉好长啊.. 楼主的解法时间复杂度怎样啊
感觉直接暴力back tracking就可以了. 30行不到..就是n^m看着不好...

调一个all permutation 就可以了
在 base case 里面做一些文章而已  为了少一点参数，全部global了。
理解意思就好。
关于时间复杂度，因为只要找到就可以提前终止 recursion 了， 这里没写，在base case里只要find，throw exception 的方式终止。类似 break loop。

1. public class FindSmallestPermutationK {
   
2.     int num;
   
3.     int lowerBound;
   
4.     int res;
   
5.     boolean find;
   
6.     public int findSmallPer(int num, int lowerBound) {
   
7.         this.num = num;
   
8.         this.lowerBound = lowerBound;
   
9.         this.res = Integer.MIN_VALUE;
   
10.         this.find = false;
    
11. 
    
12.         char[] array = Integer.toString(num).toCharArray();
    
13.         Arrays.sort(array);
    
14.         allPermutation(array, 0, array.length);
    
15.         return res;
    
16.     }
    
17. 
    
18.     private void allPermutation(char[] array, int index, int n) {
    
19.         if (index == n) {
    
20.             int cur = Integer.parseInt(new String(array));
    
21. 
    
22.             if (!find && cur > num && cur > lowerBound) {
    
23.                 res = cur;
    
24.                 find = true;
    
25.             }
    
26.             return;
    
27. 
    
28.         }
    
29. 
    
30.         for (int i = index; i < n; i++) {
    
31.             swap(array, i, index);
    
32.             allPermutation(array, index + 1, n);
    
33.             swap(array, i, index);
    
34.         }
    
35.     }
    
36. 
    
37.     private void swap(char[] array, int a, int b) {
    
38.         char temp = array[a];
    
39.         array[a] = array[b];
    
40.         array[b] = temp;
    
41.     }
    
42. 
    
43. 
    
44.     public static void main(String[] args) {
    
45.         FindSmallestPermutationK sol = new FindSmallestPermutationK();
    
46.         System.out.println(sol.findSmallPer(4319, 200));
    
47.         System.out.println(sol.findSmallPer(123, 100));
    
48.         System.out.println(sol.findSmallPer(123, 911));
    
49.         System.out.println(sol.findSmallPer(12378, 12456));
    
50.         System.out.println(sol.findSmallPer(12345, 12678));
    
51. //        System.out.println(sol.findSmallPer(123, 911));
    
52.     }
    
53. }

复制代码

[/b][/b]

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

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

请问LZ申请的什么level呀

请问楼主，这个题如果0 能放在leading 吗？ 比如1200， lower bound 200， 应该return 1002 还是201? 如果是1002， 那么这个code 好像不支持