狗家OA面经 12月果然有新题

64203221 发表于 2018-12-7 14:52
刚做完OA， 我发现题意好像是 有重复数字的话 跳 index最小的那个

这样嘛，感觉我没仔细看题目，那样看来我没凉啊哈哈哈哈哈哈

LalalaX 发表于 2018-12-7 11:14
谢谢lZ分享。其实是怕烙印来看资料～哈哈哈

学到了学到了哈哈哈哈哈哈哈

1. class Solution {
   
2.     // 第一题 给一个全是int的array A，可以选择从array的任何一个index开始跳往后跳。
   
3.     // 记当前是第i次jump，如果i是奇数，需要跳到后面所有比当前数字大的数字中最小的一个的位置，如果i是偶数，就要跳到所有比当前数字小的中，数字最大的一个的位置。
   
4.     // 求输出整个array中能跳到最后一位的数字有几个。
   
5.     // 比如说[10,13,12,14,15], 只有14可以跳到15（第1次跳，是奇数，14后面只有15，且15>14，到达），以及15本身就在最后，所以输出2.
   
6.     int num = 0;
   
7. 
   
8.     public int findAll(int[] input) {
   
9.         for(int i=0;i<input.length;i++){
   
10.             findNumberOfJumps(input, i, i, true);
    
11.         }
    
12.         return num;
    
13.     }
    
14. 
    
15.     public void findNumberOfJumps(int[] input, int pivotIndex, int currIndex, boolean isOdd) {
    
16.         if(currIndex >= input.length){
    
17.             return;
    
18.         }
    
19. 
    
20.         if(currIndex==input.length-1){
    
21.             num++;
    
22.             return;
    
23.         }
    
24. 
    
25.         int index;
    
26.         if(isOdd){
    
27.             index = findSmallestOfLarge(input, pivotIndex, currIndex);
    
28.         }else{
    
29.             index = findLargestOfSmall(input, pivotIndex, currIndex);
    
30.         }
    
31. 
    
32.         if(index==-1){
    
33.             return;
    
34.         }
    
35. 
    
36.         findNumberOfJumps(input, pivotIndex, index, !isOdd);
    
37. 
    
38.     }
    
39. 
    
40.     public int findSmallestOfLarge(int[] arr, int pivotIndex, int currIndex) {
    
41.         int result = arr[pivotIndex];
    
42.         int index = 0;
    
43.         for(int i = currIndex+1; i<arr.length; i++) {
    
44.             int elem = arr[i];
    
45.             if(i == currIndex+1 && elem > result) {
    
46.                 result = elem;
    
47.                 index = i;
    
48.                 continue;
    
49.             }
    
50. 
    
51.             if(elem > arr[pivotIndex] && elem < result){
    
52.                 result = elem;
    
53.                 index = 1;
    
54.             }
    
55.         }
    
56. 
    
57.         return result == arr[pivotIndex] ? - 1 : index;
    
58.     }
    
59. 
    
60.     public int findLargestOfSmall(int[] arr, int pivotIndex, int currIndex) {
    
61.         int result = arr[pivotIndex];
    
62.         int index = 0;
    
63.         for(int i = currIndex+1; i<arr.length; i++) {
    
64.             int elem = arr[i];
    
65.             if(i == currIndex+1 && elem < result) {
    
66.                 result = elem;
    
67.                 index = i;
    
68.                 continue;
    
69.             }
    
70. 
    
71.             if(elem < arr[pivotIndex] && elem > result){
    
72.                 result = elem;
    
73.                 index = i;
    
74.             }
    
75.         }
    
76. 
    
77.         return result == arr[pivotIndex] ? - 1 : index;
    
78.     }
    
79. }

复制代码

补充内容 (2018-12-9 04:40):
随手写了一下，求大神们指点。。。

补充内容 (2018-12-9 04:41):
应该还有特别简单的方法，求大神po下～

lz请问下给你发据信的跟给你发oa的是同一个人么？多谢

balla2011 发表于 2018-12-12 08:53
lz请问下给你发据信的跟给你发oa的是同一个人么？多谢

对的，就是那个对接的recruiter