G家的onsite

hj735 发表于 2015-6-11 11:59
[1,3,4,7,8,9]， 至少有3个数大于3，而没有至少4个数大于4

那【1,2,4,7,8,9】是不是就没有了？2的话至少有2个数大于2，但至少有2+1个数大于2+1这个也成立~

Xin_walker 发表于 2015-6-20 07:20
那【1,2,4,7,8,9】是不是就没有了？2的话至少有2个数大于2，但至少有2+1个数大于2+1这个也成立~

答案是3 h-index不一定必须是存在于数组中

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

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

Xin_walker 发表于 2015-6-20 08:02
哦！谢谢！再确认一下最终结果:
1.如果数组最大值

对的 其实题目给的都是正整数

hj735 发表于 2015-6-20 09:07
对的 其实题目给的都是正整数

哦哦，谢啦~

round 2我会这样写，不知道好不好：

1.         //a has been desc-sorted
   
2.         public static int hidx(int[] a) {
   
3.                 int l = 0, r =a.length-1;
   
4.                 while (l<=r) {
   
5.                         int mid = (l+r)/2;
   
6.                         if (mid > a[mid]) {
   
7.                                 r = mid -1;
   
8.                         }
   
9.                         else if (mid <= a[mid] && (mid==a.length-1 || mid+1>a[mid+1])) {
   
10.                                 return mid;
    
11.                         }
    
12.                         else l= mid+1;
    
13.                 }
    
14.                 return a.length;
    
15.                
    
16.         }

复制代码

round 4 我会这么写，欢迎指正～

1. import java.util.Arrays;
   
2. import java.util.PriorityQueue;
   
3. 
   
4. /*
   
5. * 给一个字符串，该字符串由一些可能会重复的字符组成，重新排列这个字符串使得没有相邻的字符是相同字符。如aab变成aba
   
6. *
   
7. * Using priority Queue, delete 2 node each time till queue is empty
   
8. */
   
9. public class Rearrange {
   
10.         // create class to match char and its freq
    
11.         static class Node implements Comparable<Node>{
    
12.                 char val;
    
13.                 int freq;
    
14.                 Node(char val, int freq){
    
15.                         this.val = val;
    
16.                         this.freq = freq;
    
17.                 }
    
18.                 @Override
    
19.                 // Node with more freq would be in the front
    
20.                 public int compareTo(Node that) {
    
21.                         if (this.freq > that.freq) {
    
22.                                 return -1;
    
23.                         }
    
24.                         else if (this.freq < that.freq) {
    
25.                                 return 1;
    
26.                         }
    
27.                        
    
28.                         return 0;
    
29.                 }
    
30.         }
    
31.         public static String rearrage(String s){
    
32.                 if (s==null || s.length()<=1) return s;
    
33.                 // Build a max-freq priority queue
    
34.                 char[] chs = s.toCharArray();
    
35.                 int[] char_frequency = new int[128];
    
36.                 Arrays.fill(char_frequency,0);
    
37.                 for (char ch:chs) {
    
38.                         char_frequency[ch]+=1;
    
39.                 }
    
40.                 PriorityQueue<Node> pq = new PriorityQueue<Node>();
    
41.                 for (int i=0; i<char_frequency.length; i++) {
    
42.                         if (char_frequency[i]>0) {
    
43.                                 Node x = new Node((char)i,char_frequency[i]);
    
44.                                 //System.out.println(x.val+"-->"+x.freq);
    
45.                                 pq.offer(x);
    
46.                         }
    
47.                 }
    
48.                 //if freq of first ele > n/2+1, return false
    
49.                 if (pq.peek().freq>(s.length()+1)/2)  return null;
    
50.                
    
51.                 //get new string from queue
    
52.                 StringBuilder ans = new StringBuilder();
    
53.                 while (!pq.isEmpty()) {
    
54.                         Node first = pq.poll();
    
55.                         if (pq.isEmpty()) {
    
56.                                 ans.append(first.val);
    
57.                                 break;
    
58.                         }
    
59.                         Node second = pq.poll();
    
60.                         ans.append(first.val+""+second.val);
    
61. 
    
62.                         first.freq-=1;
    
63.                         second.freq-=1;
    
64.                         if (first.freq>0) pq.offer(first);
    
65.                         if (second.freq>0) pq.offer(second);
    
66.                 }
    
67.                 return ans.toString();
    
68.         }
    
69. 
    
70.         public static void main(String[] args) {
    
71.                 // TODO Auto-generated method stub
    
72.         System.out.println(rearrage("BCDAGAAAA"));
    
73.         }
    
74. 
    
75. }
    

复制代码

jaly50 发表于 2015-6-22 00:27
round 4 我会这么写，欢迎指正～

目测是正解，思路和我的有点不一样，都能完成任务

Cong！！！lz赞，去了什么组？

jaly50 发表于 2015-6-21 23:45
round 2我会这样写，不知道好不好：

目测有效，只不过你写反了，数组是升序排列，你假设是降序排列，所有条件反过来了。