Coursera 两道题版本的OA

本来5天前收到的链接，准备了好久的题库，顺便也恢复一下状态，结果刚点开就发现Coursera新发来个OA，之前的链接作废了。

于是从5道题的版本变成了两道题。而之前卡住许久的题目就是lovely number，这次查了一下新面

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

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

est，就当是熟练一下手感。
祝各位都好运~

by the way，这家是海投就给OA，希望能有下文吧。

mymax2009 发表于 2016-9-23 02:03
然后其实我想问的是  Ashley 这题， 121算不算是repeated digit number，还是要连续的？

121 应该是算repeated number的
我的思路是先计算1到m不重复的个数减去1到n-1的不重复个数
举个例子吧 比如说要算1-223中不重复的个数，先存1-9，10-99的不重复个数90个，当算到最高位2时，我们开始算100-199的个数，百位有1众取法“1”，十位9种，个位8种，就是72，接下来算200-219的个数，这时候用个vector保存已经用过的数字，十位有“0，1”两种取法，个位有8种，总共16种，220-223，有0个。关键就在于每次计算当前位数字取整减一不重复数字的个数。最后累加起来。每次计算一个数字的复杂度就是O(1)，因为m，n digit最多为5位。这是我的想法。

mymax2009 发表于 2016-9-23 01:39
segment这题应该可以O(N)解决，遍历number，用deque存升序number的index（当前number

嗯嗯 用queue做O(N)复杂度 ， 不过我的做法是pq里面存pair<nums[i],i> 然后做法和你一样啦

恕我直言，暴力枚举复杂度太高了吧？顶我上去，分享简单做法

1. Segment

1. public int segment(int x, int[] arr) {
   
2. 
   
3.         if (x == 0 || x > arr.length) {
   
4.             return 0;
   
5.         }
   
6. 
   
7.         List<List<Integer>> list = new ArrayList<List<Integer>>();
   
8. 
   
9.         for (int i = 0; i < arr.length; i++) {
   
10.             ArrayList<Integer> nums = new ArrayList();
    
11. 
    
12.             for (int j = i; j < x + i && i != arr.length - 1; j++) {
    
13.                 nums.add(arr[j]);
    
14.             }
    
15.             list.add(nums);
    
16.         }
    
17. 
    
18.         List<Integer> minValues = new ArrayList<>();
    
19. 
    
20.         for (int i = 0; i < list.size(); i++) {
    
21. 
    
22.             List<Integer> nums = list.get(i);
    
23.             if (nums == null || nums.size() == 0) {
    
24.                 continue;
    
25.             }
    
26. 
    
27.             int min = Integer.MAX_VALUE;
    
28.             for (int j = 0; j < nums.size(); j++) {
    
29.                 min = Math.min(nums.get(j), min);
    
30.             }
    
31.             minValues.add(min);
    
32.         }
    
33. 
    
34.         int max = Integer.MIN_VALUE;
    
35.         for (int i = 0; i < minValues.size(); i++) {
    
36.             max = Math.max(max, minValues.get(i));
    
37.         }
    
38. 
    
39.         return max;
    
40.     }

复制代码

2. Lovely numbers

1. public void countNumbers(int[][] arr) {
   
2. 
   
3.         if (arr == null || arr.length == 0 || arr[0].length == 0) {
   
4.             return;
   
5.         }
   
6. 
   
7.         int m = arr.length;
   
8.         int count;
   
9.         ArrayList<Integer> list = new ArrayList<>();
   
10. 
    
11.         for (int i = 0; i < m; i++) {
    
12.             count = 0;
    
13.             for (int j = arr[i][0]; j <= arr[i][1]; j++) {
    
14.                 if (!checkRepeating(j)) {
    
15.                      count++;
    
16.                 }
    
17.             }
    
18.             list.add(count);
    
19.         }
    
20. 
    
21.         for (int i = 0; i < list.size(); i++) {
    
22.             System.out.println(list.get(i));
    
23.         }
    
24.     }
    
25. 
    
26.     private boolean checkRepeating(int num) {
    
27. 
    
28.         Set<Integer> set = new HashSet<>();
    
29. 
    
30.         while (num > 0) {
    
31.             if (set.contains(num % 10)) {
    
32.                 return true;
    
33.             }
    
34.             set.add(num % 10);
    
35.             num /= 10;
    
36.         }
    
37. 
    
38.         return false;
    
39.     }

复制代码

chensheng 发表于 2016-9-3 14:19
1. Segment

层主这种方法的时间复杂度应该是 O(n*maxLen) 吧？

y111d 发表于 2016-9-6 08:30
层主这种方法的时间复杂度应该是 O(n*maxLen) 吧？

没错啊，正确

多谢楼主！

我也是MSE转的CS。。USC37学分的。。一口气看了你写的那些课程的经验介绍，感觉。。。。更虚了。。。。。。。。。。。。LZ名字是LTM吗？

laahaa 发表于 2016-9-18 20:08
我也是MSE转的CS。。USC37学分的。。一口气看了你写的那些课程的经验介绍，感觉。。。。更虚了。。。。。。 ...

我去。。。这是抓到我真人了？

求问下楼主他家能用C++做吗？ 我看input全是stdin，是要先从std::cin预处理input再写算法对吗

楼主给力！