Java 岗开发 3 年，公司临时抽查算法，离职后这几题我记一辈子

17. {
    

18. if(price[t] && syn < 3) syn++;
    

19. if(syn == 3) break;
    

20. t++;
    

21. }
    

22. syn == 3 ? cout << t : cout << -1;
    

23. }
    

</pre>

2、一个数轴上共有 N 个点，第一个点的坐标是度度熊现在位置，第 N-1 个点是度度熊的家。现在他需要依次的从 0 号坐标走到 N-1 号坐标。

但是除了 0 号坐标和 N-1 号坐标，他可以在其余的 N-2 个坐标中选出一个点，并直接将这个点忽略掉，问度度熊回家至少走多少距离？

解答：

从 N-2 个坐标中选出一个点，并直接将这个点忽略掉。直接忽略一个点只会直接影响到，这个节点前后节点的距离。这个 影响的距离我们暂且命名为优化距离，将所有节点按顺序组成三个节点的集合，通过这种方式只需要通过一次循环便能得到结果。

优化距离越大说明如果去掉这个集合的中点元素将会使得总距离越短，下面上代码。

1. import
   

2. java.util.
   

3. Scanner;
   

4. publicclass
   

5. Main
   

6. {
   

7. publicstaticvoid
   

8. main(String[] args)
   

9. {
   

10. Scanner
    

11. scanner = new
    

12. Scanner(System.in);
    

13. int
    

14. length = scanner.nextInt();
    

15. int[] arrays = newint[length];
    

16. for(int i = 0; i < length; i++)
    

17. {
    

18. arrays[i] = scanner.nextInt();
    

19. }
    

20. /**
    

21. * sum 总距离
    

22. * repetition 三个节点 中被重复计算的总距离
    

23. * select 优化距离最大的 三个节点两两相加的距离
    

24. * add 三个结尾距离为 max 中 头尾节点的距离
    

25. * last 最后三个节点中 尾距离没有被计算两次 需要加上
    

26. * optimizeDistance 优化距离
    

27. */
    

28. int
    

29. sum = 0,
    

30. int
    

31. repetition = 0,
    

32. intselect = 0,
    

33. int
    

34. add = 0,
    

35. intlast = 0,
    

36. int
    

37. optimizeDistance = 0;
    

38. for(int i = 0; i <= (arrays.length - 3); i++)
    

39. {
    

40. intbegin = arrays[i];
    

41. int
    

42. mid = arrays[i + 1];
    

43. intend = arrays[i + 2];
    

44. //三个点之间的距离
    

45. int
    

46. threePointDistance = Math.abs(mid - begin) + Math.abs(end - mid);
    

47. //两个点之间的距离 即被多次计算待会需要减掉的距离
    

48. int
    

49. twoPointDistance = Math.abs(end - mid);
    

50. int
    

51. contrast = threePointDistance - Math.abs(begin - end);
    

52. repetition += twoPointDistance;
    

53. sum += threePointDistance;
    

54. last = twoPointDistance;
    

55. if(contrast > optimizeDistance)
    

56. {
    

57. optimizeDistance = contrast;
    

58. select = threePointDistance;
    

59. add = Math.abs(end - begin);
    

60. }
    

61. }
    

62. System.
    

63. out.println((sum - select + last) - repetition + add);
    

64. }
    

65. }
    

</pre>

3、度度熊最近对全排列特别感兴趣,对于 1 到 n 的一个排列,度度熊发现可以在中间根据大小关系插入合适的大于和小于符号(即 '>' 和 '<' )使其成为一个合法的不等式数列。

但是现在度度熊手中只有 k 个小于符号即('<'')和 n-k-1 个大于符号(即'>'),度度熊想知道对于 1 至 n 任意的排列中有多少个排列可以使用这些符号使其为合法的不等式数列。

解答：

dp[i][j] = (dp[i - 1][j - 1] * (i - j) + dp[i - 1][j] * (j + 1)) % 2017;

dp[i][j]表示有 i 个数字及 j 个小于号所能组成的数量(大于号数量当然是 i - j - 1 次，后面需要使用)

而加入第 i + 1 个数字时，分以下四种情况：

1. 如果将 i+1 插入当前序列的开头，即有了 1<2，加入后成为 3>1<2，会发现等于同时加入了一个大于号！(此时可以无视 1 与 2 之间的关系，因为 i+1>i)

2. 如果将 i+1 插入当前序列末尾,即 1<2 变成了 1<2<3，会发现等于同时加入了一个小于号！(此时可以无视 1 与 2 之间的关系，因为 i

【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开：qq.cn.hn/FTf 免费领取

+1>i)

3. 如果将 i+1 加入一个小于号之间，即已经有 1<2 了，向中间加入 3,会发现变成了 1<3>2，等于同时加入了一个大于号！

4. 如果将 i+1 加入一个大于号中间，即有了 2>1，变成了 2<3>1，等于同时加入了一个小于号！

综上所述，dp[i][j]等于以上四种情况之和：

dp[i - 1][j]?将 i 加在开头等于加入一个大于号，即要求 i-1 个数时已经有了 j 个小于号；

dp[i - 1][j - 1]?将 i 加在末尾等于加入一个小于号，即要求 i-1 个数时已经有了 j-1 个小于号；

dp[i - 1][j] * j?将 i 加在任意一个小于号之间，等于加入了一个大于号，即要求 i-1 个数时已经有了 j 个小于号，每个小于号都可以进行这样的一次插入；

dp[i - 1][j - 1] * (i- j - 1)?将 i 加载任意一个大于号之间，等于加入了一个小于号，即要求 i-1 个数时有了 j-1 个小于号；

而此时共有(i - 1) - (j - 1)- 1 个大于号，每个大于号都要进行一次这样的操作合并同类项即为 dp[i][j] = (dp[i - 1][j - 1] * (i - j) + dp[i - 1][j] * (j + 1))。

最后要记得取模。

......