也谈阿里巴巴面试题_身高排队问题

论坛 › 期权论坛 › 脚本     
已经匿名di用户   2022-7-2 21:51   2778   0

首先申明，我没有去阿里巴巴面试这个题目的，我是看到坛子里有人贴出问题的。我想如果是我去面试，我该怎么解决，如何去分析这个问题，这个问题背后隐藏的是什么哪类问题，花了一个晚上终于把它给弄出来了，不足之处大家给意见。

题目是这样的：12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

初看这个问题，如果是应试，还真有点摸不着头脑，但是静心想想，还是有规律的，一般面试题目都是一些经典的算法问题，只是常常将问题以某种看似日常化，生活的题目来叙述罢了。

首先把问题抽象，题目变成：给定一组整数（当然可以是整数，浮点数等，这里姑且当成整数处理，道理是一样的），这组整数中每个数值大小不一样，把这组整数分成两组，每组按照从小到大排列，要求一组每个成员数值比对应位置上的另外一组的成员数值小。

再进一步分解抽象：就是给定一组整数，从这整数中找X个整数出来，使得这X个数之和不大于给定整数数组之和的一半，如果这个一半的情况找到了，另外一半基本确定，因此，现在题目转化成从给定数组中找一个X个数，使得X个数之和小于给定数组之和的一半。

既然问题抽象了，那么现在来设计算法，一个最简单的算法就是穷举，人脑简直是太有限了，让计算机穷举去贝，这里采用遍历整个数组，即确定一个首元素后采用 栈来确定这个栈里面的元素是否符合上文中X个数的情况，如果符合就记录下来，如果不符合就进入下一步选择。具体算法是：
（1）先对给定数组Q排序，按照从小到大的顺序排列。
（2）然后循环这个数组（其时排序后循环一半就可以了，理由是找小的一半数组H，最小的元素肯定小于1/2长度的那个元素），把这个循环中的整数A1加入一个栈S，然后从给定数组Q中找比栈顶元素次大的一个元素最为下一个栈顶元素入栈，循环入栈操作。
（3）符合情况的记录：如果这个栈S的元素长度达到给定数组Q元素长度的一半时，就要判断这个栈S元素之和是否小于Q数组之和的一半，如果符合就记录这个 栈S的所有元素，并弹出栈顶元素Top，从Q数组中找下一个入栈元素，条件时这个入栈元素要比这个出栈元素Top大
（4）不符合半组H的情况：当栈S元素长度等于Q数组长度一半时，并且此时出栈元素是最后一个了（排序后最大的元素），那么就要出栈两个元素；当栈S元素长度等于Q数组长度一半时，并且此时栈S元素之和已大于给定数组Q之和的一半了，也要出栈两个元素；
（5）退出循环情况：当栈S只有小于等于一个元素了，且下一个元素为空，那么退出当前循环；当栈S小于等于两个元素长度，且下一个元素为数组Q最后一个元素时，那么退出当前循环；当栈S大于两个元素长度，且下一个元素为数组Q最后一个元素时，那么要出栈两个元素。
本人采用java语言实现了这个算法过程，可以任意定义数组大小，最后打印出来这个排列组合，具体程序如下：

Java代码 收藏代码
  1. package com.fruitking.test;
  3. import java.util.ArrayList;
  4. import java.util.Iterator;
  5. import java.util.List;
  6. import java.util.Stack;
  8. /**
  9. * 给定一个整数列表（每个数大小都不一样），分成两队，
  10. * 每对按照高矮排列，且左边一对比右边一对对应位置上的值要小
  11. * @author XuGuo
  12. * @since 2009-10-27
  13. */
  14. public class HalfOfQueue {
  16. private List<Integer> queueList; //存储整个编队的人的身高数据列表
  17. private Stack<Integer> halfStack = new Stack<Integer>(); //遍历时候临时使用的栈
  18. private List<List<Integer>> halfResultList = new ArrayList<List<Integer>>(); //用于临时存储半个队列
  19. private List<List<Pair>> resultList = new ArrayList<List<Pair>>(); //用于存储结果排序好的符合要求的队列
  20. private int sum = 0 ; //整个编队的总大小
  21. private Integer lastMember; //排序后最大的元素
  23. public HalfOfQueue(List<Integer> queueList){
  24. this .queueList = this .sortQueueList(queueList);
  25. this .sumOfQueueList();
  26. if (queueList!= null &&queueList.size()>= 2 ){
  27. this .lastMember = queueList.get(queueList.size()- 1 );
  28. }
  29. }
  31. /**
  32. * 打印总过有多少组合，并且组合是哪些
  33. */
  34. public List<List<Pair>> getResultPairList(){
  35. return this .resultList;
  36. }
  38. /**
  39. * 查找和结果整理
  40. */
  41. public void run(){
  42. this .halfQueue();
  43. this .handlePairQueue();
  44. }
  46. /**
  47. * 匹配成对
  48. */
  49. private void handlePairQueue(){
  50. if (halfResultList!= null &&!halfResultList.isEmpty()){
  51. for ( int i= 0 ;i<halfResultList.size();i++){
  52. List<Integer> tempOneList = halfResultList.get(i);
  53. List<Integer> tempOtherList = new ArrayList<Integer>();
  54. int queueSize = this .queueList.size();
  55. if (tempOneList!= null &&!tempOneList.isEmpty()){
  56. Integer tempMember = null ;
  57. for ( int k= 0 ;k<queueSize;k++){
  58. tempMember = queueList.get(k);
  59. if (!tempOneList.contains(tempMember)){
  60. tempOtherList.add(tempMember);
  61. }
  62. }
  63. tempOtherList = this .sortQueueList(tempOtherList);
  64. }
  65. List<Pair> pairList = new ArrayList<Pair>();
  66. for ( int k= 0 ;k<tempOneList.size();k++){
  67. Pair pair = new Pair(tempOneList.get(k),tempOtherList.get(k));
  68. if (pair.isCorrectPair()){
  69. pairList.add(pair);
  70. }
  71. }
  72. if (pairList.size()== this .queueList.size()/ 2 ){
  73. this .resultList.add(pairList);
  74. }
  75. }
  76. }
  77. }
  79. /**
  80. * 半块队列的穷举
  81. */
  82. private void halfQueue(){
  83. for ( int i= 0 ;i<queueList.size()/ 2 ;i++){
  84. if (queueList.size()< 2 ){
  85. return ;
  86. }
  87. halfStack.clear();
  88. halfStack.push(queueList.get(i));
  89. Integer inNextMember = halfStack.peek();
  90. Integer topStackMember = null ;
  91. while ( true ){
  92. if (halfStack.size()<(queueList.size()/ 2 )){
  93. inNextMember = getNextMember(inNextMember);
  94. if (inNextMember!= null ){
  95. halfStack.push(inNextMember);
  96. }else {
  97. if (halfStack.size()<= 1 ){
  98. break ; //退出条件
  99. }else {
  100. halfStack.pop();//退出最后一个元素
  101. inNextMember = halfStack.pop();//退出到数第二个元素
  102. continue ;
  103. }
  104. }
  105. if (halfStack.size()==(queueList.size()/ 2 )){
  106. if ( this .isHalfOfSumQueueList()){
  107. List<Integer> tempList = new ArrayList<Integer>();
  108. tempList.addAll(halfStack);
  109. halfResultList.add(tempList);
  110. topStackMember = halfStack.pop();//当栈满时退出最后一个栈元素
  111. if (topStackMember.intValue()== this .lastMember.intValue()){
  112. //最后一个元素了
  113. inNextMember = halfStack.pop();//当栈差一个元素满时退出最后一个元素
  114. }
  115. }else {
  116. halfStack.pop();//退出最后一个元素（这个元素的加入已经满足此栈所有元素不符合业务逻辑的情况了）
  117. inNextMember = halfStack.pop();//退出到数第二个元素（即使后面还有元素已经不满足业务逻辑了）
  118. }
  119. }else if (inNextMember.intValue()== this .lastMember.intValue()){
  120. if (halfStack.size()<= 2 ){ //第一个元素和最后一个元素了也就要退出
  121. break ; //退出条件
  122. }else {
  123. halfStack.pop();//退出最后一个元素（这个元素一定是编队中最大的元素）
  124. inNextMember = halfStack.pop();//退出到数第二个元素
  125. }
  126. }
  127. }
  128. }
  129. }
  130. }
  132. /**
  133. * 是否是编队值的一半的最大值
  134. * @return
  135. */
  136. private boolean isHalfOfSumQueueList(){
  137. int sumOfHalf = 0 ;
  138. if (halfStack!= null &&!halfStack.isEmpty()){
  139. Iterator<Integer> halfStackIt = halfStack.iterator();
  140. while (halfStackIt.hasNext()){
  141. sumOfHalf = sumOfHalf + halfStackIt.next().intValue();
  142. }
  143. if (sumOfHalf<=( this .sum/ 2 -queueList.size()/ 4 )){
  144. return true ;
  145. }
  146. }
  147. return false ;
  148. }
  152. /**
  153. * 获得比当前元素大的元素，已经对成员列表排序了
  154. * 如果当前为空就返回最小的那个元素，如果当前元素最大，就返回最大的那个元素
  155. * @return
  156. */
  157. private Integer getNextMember(Integer currentMember){
  158. Integer nextMember = null ;
  159. if (queueList!= null &&!queueList.isEmpty()){
  160. if (currentMember!= null &&currentMember.intValue()== this .lastMember.intValue()){
  161. return null ;
  162. }
  163. Iterator<Integer> memberIt = queueList.iterator();
  164. while (memberIt.hasNext()){
  165. nextMember = memberIt.next();
  166. if (currentMember!= null ){
  167. if (nextMember.intValue()>currentMember.intValue()){
  168. break ;
  169. }
  170. }else {
  171. break ;
  172. }
  173. }
  174. }
  175. return nextMember;
  176. }
  178. /**
  179. * 求队列和
  180. */
  181. private void sumOfQueueList(){
  182. if (queueList!= null &&!queueList.isEmpty()){
  183. for ( int k= 0 ;k<queueList.size();k++){
  184. sum = sum + queueList.get(k).intValue();
  185. }
  186. }
  187. }
  189. /**
  190. * 对编队按照从小到大排序
  191. * @param queueList
  192. * @return
  193. */
  194. private List<Integer> sortQueueList(List<Integer> srcQueueList){
  195. List<Integer> destQueueList = new ArrayList<Integer>();
  196. if (srcQueueList!= null &&!srcQueueList.isEmpty()){
  197. List<Integer> tempList = new ArrayList<Integer>();
  198. tempList.addAll(srcQueueList);
  199. Iterator<Integer> outIt = tempList.iterator();
  200. while (outIt.hasNext()){
  201. Integer nextMember = null ;
  202. Integer tempMember = null ;
  203. Iterator<Integer> inIt = tempList.iterator();
  204. while (inIt.hasNext()){
  205. tempMember = inIt.next();
  206. if (nextMember== null ){
  207. nextMember = tempMember;
  208. }
  209. if (nextMember.intValue()>tempMember.intValue()){
  210. nextMember = tempMember;
  211. }
  212. }
  213. if (nextMember!= null ){
  214. destQueueList.add(nextMember);
  215. tempList.remove(nextMember);
  216. outIt = tempList.iterator();
  217. }
  218. }
  219. }
  220. return destQueueList;
  221. }
  222. }

Java代码 收藏代码
  1. package com.fruitking.test;
  3. /**
  4. * 数据封装而已，不想用太多的数组这样的单个东西
  5. * @author XuGuo
  6. * @since 2009-10-27
  7. */
  8. public class Pair {
  10. private Integer left;
  11. private Integer right;
  13. public Pair(Integer left,Integer right){
  14. this .left = left;
  15. this .right = right;
  16. }
  18. /**
  19. * 判断这对是否是正确的组合（即左边这个元素是否小于右边这个元素）
  20. * @return
  21. */
  22. public boolean isCorrectPair(){
  23. if (left!= null &&right!= null &&left.intValue()<right.intValue()){
  24. return true ;
  25. }else {
  26. return false ;
  27. }
  28. }
  30. public int getLeft() {
  31. return left;
  32. }
  34. public void setLeft( int left) {
  35. this .left = left;
  36. }
  38. public int getRight() {
  39. return right;
  40. }
  42. public void setRight( int right) {
  43. this .right = right;
  44. }
  45. }

Java代码 收藏代码
  1. package com.fruitking.test;
  3. import java.util.ArrayList;
  4. import java.util.List;
  6. /**
  7. * @author XuGuo
  8. * @since 2009-10-27
  9. */
  10. public class Test10 {
  12. /**
  13. * 12个高矮不同的人,排成两排,每排必须是从矮到高排列,
  14. * 而且第二排比对应的第一排的人高,问排列方式有多少种?
  15. */
  16. public static void main(String[] args) {
  17. List<Integer> list = new ArrayList<Integer>();
  18. list.add(new Integer( 2 ));list.add( new Integer( 4 ));
  19. list.add(new Integer( 1 ));list.add( new Integer( 3 ));
  20. list.add(new Integer( 5 ));list.add( new Integer( 6 ));
  21. list.add(new Integer( 7 ));list.add( new Integer( 8 ));
  22. list.add(new Integer( 9 ));list.add( new Integer( 11 ));
  23. list.add(new Integer( 10 ));list.add( new Integer( 12 ));
  24. HalfOfQueue test1 = new HalfOfQueue(list);
  25. test1.run();
  26. List<List<Pair>> resultList = test1.getResultPairList();
  27. /**
  28. * 打印总过有多少组合，并且组合是哪些
  29. */
  30. System.out.println();
  31. System.out.println("---总共有" +resultList.size()+ "个组合---" );
  32. for ( int i= 0 ;i<resultList.size();i++){
  33. List<Pair> tempList = resultList.get(i);
  34. if (tempList!= null &&!tempList.isEmpty()){
  35. System.out.println("--------------------" );
  36. for ( int k= 0 ;k<tempList.size();k++){
  37. System.out.print(tempList.get(k).getLeft()+" " );
  38. }
  39. System.out.println();
  40. for ( int k= 0 ;k<tempList.size();k++){
  41. System.out.print(tempList.get(k).getRight()+" " );
  42. }
  43. System.out.println();
  44. }
  45. }
  46. }
  47. }


运行结果：


---总共有132个组合---
--------------------
1 2 3 4 5 6
7 8 9 10 11 12
--------------------
1 2 3 4 5 7
6 8 9 10 11 12
--------------------
1 2 3 4 5 8
6 7 9 10 11 12
--------------------
1 2 3 4 5 9
6 7 8 10 11 12
--------------------
1 2 3 4 5 10
6 7 8 9 11 12
--------------------
1 2 3 4 5 11
6 7 8 9 10 12
--------------------
1 2 3 4 6 7
5 8 9 10 11 12
--------------------
1 2 3 4 6 8
5 7 9 10 11 12
--------------------
1 2 3 4 6 9
5 7 8 10 11 12
--------------------
1 2 3 4 6 10
5 7 8 9 11 12
--------------------
1 2 3 4 6 11
5 7 8 9 10 12
--------------------
1 2 3 4 7 8
5 6 9 10 11 12
--------------------
1 2 3 4 7 9
5 6 8 10 11 12
--------------------
1 2 3 4 7 10
5 6 8 9 11 12
--------------------
1 2 3 4 7 11
5 6 8 9 10 12
--------------------
1 2 3 4 8 9
5 6 7 10 11 12
--------------------
1 2 3 4 8 10
5 6 7 9 11 12
--------------------
1 2 3 4 8 11
5 6 7 9 10 12
--------------------
1 2 3 4 9 10
5 6 7 8 11 12
--------------------
1 2 3 4 9 11
5 6 7 8 10 12
--------------------
1 2 3 5 6 7
4 8 9 10 11 12
--------------------
1 2 3 5 6 8
4 7 9 10 11 12
--------------------
1 2 3 5 6 9
4 7 8 10 11 12
--------------------
1 2 3 5 6 10
4 7 8 9 11 12
--------------------
1 2 3 5 6 11
4 7 8 9 10 12
--------------------
1 2 3 5 7 8
4 6 9 10 11 12
--------------------
1 2 3 5 7 9
4 6 8 10 11 12
--------------------
1 2 3 5 7 10
4 6 8 9 11 12
--------------------
1 2 3 5 7 11
4 6 8 9 10 12
--------------------
1 2 3 5 8 9
4 6 7 10 11 12
--------------------
1 2 3 5 8 10
4 6 7 9 11 12
--------------------
1 2 3 5 8 11
4 6 7 9 10 12
--------------------
1 2 3 5 9 10
4 6 7 8 11 12
--------------------
1 2 3 5 9 11
4 6 7 8 10 12
--------------------
1 2 3 6 7 8
4 5 9 10 11 12
--------------------
1 2 3 6 7 9
4 5 8 10 11 12
--------------------
1 2 3 6 7 10
4 5 8 9 11 12
--------------------
1 2 3 6 7 11
4 5 8 9 10 12
--------------------
1 2 3 6 8 9
4 5 7 10 11 12
--------------------
1 2 3 6 8 10
4 5 7 9 11 12
--------------------
1 2 3 6 8 11
4 5 7 9 10 12
--------------------
1 2 3 6 9 10
4 5 7 8 11 12
--------------------
1 2 3 6 9 11
4 5 7 8 10 12
--------------------
1 2 3 7 8 9
4 5 6 10 11 12
--------------------
1 2 3 7 8 10
4 5 6 9 11 12
--------------------
1 2 3 7 8 11
4 5 6 9 10 12
--------------------
1 2 3 7 9 10
4 5 6 8 11 12
--------------------
1 2 3 7 9 11
4 5 6 8 10 12
--------------------
1 2 4 5 6 7
3 8 9 10 11 12
--------------------
1 2 4 5 6 8
3 7 9 10 11 12
--------------------
1 2 4 5 6 9
3 7 8 10 11 12
--------------------
1 2 4 5 6 10
3 7 8 9 11 12
--------------------
1 2 4 5 6 11
3 7 8 9 10 12
--------------------
1 2 4 5 7 8
3 6 9 10 11 12
--------------------
1 2 4 5 7 9
3 6 8 10 11 12
--------------------
1 2 4 5 7 10
3 6 8 9 11 12
--------------------
1 2 4 5 7 11
3 6 8 9 10 12
--------------------
1 2 4 5 8 9
3 6 7 10 11 12
--------------------
1 2 4 5 8 10
3 6 7 9 11 12
--------------------
1 2 4 5 8 11
3 6 7 9 10 12
--------------------
1 2 4 5 9 10
3 6 7 8 11 12
--------------------
1 2 4 5 9 11
3 6 7 8 10 12
--------------------
1 2 4 6 7 8
3 5 9 10 11 12
--------------------
1 2 4 6 7 9
3 5 8 10 11 12
--------------------
1 2 4 6 7 10
3 5 8 9 11 12
--------------------
1 2 4 6 7 11
3 5 8 9 10 12
--------------------
1 2 4 6 8 9
3 5 7 10 11 12
--------------------
1 2 4 6 8 10
3 5 7 9 11 12
--------------------
1 2 4 6 8 11
3 5 7 9 10 12
--------------------
1 2 4 6 9 10
3 5 7 8 11 12
--------------------
1 2 4 6 9 11
3 5 7 8 10 12
--------------------
1 2 4 7 8 9
3 5 6 10 11 12
--------------------
1 2 4 7 8 10
3 5 6 9 11 12
--------------------
1 2 4 7 8 11
3 5 6 9 10 12
--------------------
1 2 4 7 9 10
3 5 6 8 11 12
--------------------
1 2 4 7 9 11
3 5 6 8 10 12
--------------------
1 2 5 6 7 8
3 4 9 10 11 12
--------------------
1 2 5 6 7 9
3 4 8 10 11 12
--------------------
1 2 5 6 7 10
3 4 8 9 11 12
--------------------
1 2 5 6 7 11
3 4 8 9 10 12
--------------------
1 2 5 6 8 9
3 4 7 10 11 12
--------------------
1 2 5 6 8 10
3 4 7 9 11 12
--------------------
1 2 5 6 8 11
3 4 7 9 10 12
--------------------
1 2 5 6 9 10
3 4 7 8 11 12
--------------------
1 2 5 6 9 11
3 4 7 8 10 12
--------------------
1 2 5 7 8 9
3 4 6 10 11 12
--------------------
1 2 5 7 8 10
3 4 6 9 11 12
--------------------
1 2 5 7 8 11
3 4 6 9 10 12
--------------------
1 2 5 7 9 10
3 4 6 8 11 12
--------------------
1 2 5 7 9 11
3 4 6 8 10 12
--------------------
1 3 4 5 6 7
2 8 9 10 11 12
--------------------
1 3 4 5 6 8
2 7 9 10 11 12
--------------------
1 3 4 5 6 9
2 7 8 10 11 12
--------------------
1 3 4 5 6 10
2 7 8 9 11 12
--------------------
1 3 4 5 6 11
2 7 8 9 10 12
--------------------
1 3 4 5 7 8
2 6 9 10 11 12
--------------------
1 3 4 5 7 9
2 6 8 10 11 12
--------------------
1 3 4 5 7 10
2 6 8 9 11 12
--------------------
1 3 4 5 7 11
2 6 8 9 10 12
--------------------
1 3 4 5 8 9
2 6 7 10 11 12
--------------------
1 3 4 5 8 10
2 6 7 9 11 12
--------------------
1 3 4 5 8 11
2 6 7 9 10 12
--------------------
1 3 4 5 9 10
2 6 7 8 11 12
--------------------
1 3 4 5 9 11
2 6 7 8 10 12
--------------------
1 3 4 6 7 8
2 5 9 10 11 12
--------------------
1 3 4 6 7 9
2 5 8 10 11 12
--------------------
1 3 4 6 7 10
2 5 8 9 11 12
--------------------
1 3 4 6 7 11
2 5 8 9 10 12
--------------------
1 3 4 6 8 9
2 5 7 10 11 12
--------------------
1 3 4 6 8 10
2 5 7 9 11 12
--------------------
1 3 4 6 8 11
2 5 7 9 10 12
--------------------
1 3 4 6 9 10
2 5 7 8 11 12
--------------------
1 3 4 6 9 11
2 5 7 8 10 12
--------------------
1 3 4 7 8 9
2 5 6 10 11 12
--------------------
1 3 4 7 8 10
2 5 6 9 11 12
--------------------
1 3 4 7 8 11
2 5 6 9 10 12
--------------------
1 3 4 7 9 10
2 5 6 8 11 12
--------------------
1 3 4 7 9 11
2 5 6 8 10 12
--------------------
1 3 5 6 7 8
2 4 9 10 11 12
--------------------
1 3 5 6 7 9
2 4 8 10 11 12
--------------------
1 3 5 6 7 10
2 4 8 9 11 12
--------------------
1 3 5 6 7 11
2 4 8 9 10 12
--------------------
1 3 5 6 8 9
2 4 7 10 11 12
--------------------
1 3 5 6 8 10
2 4 7 9 11 12
--------------------
1 3 5 6 8 11
2 4 7 9 10 12
--------------------
1 3 5 6 9 10
2 4 7 8 11 12
--------------------
1 3 5 6 9 11
2 4 7 8 10 12
--------------------
1 3 5 7 8 9
2 4 6 10 11 12
--------------------
1 3 5 7 8 10
2 4 6 9 11 12
--------------------
1 3 5 7 8 11
2 4 6 9 10 12
--------------------
1 3 5 7 9 10
2 4 6 8 11 12
--------------------
1 3 5 7 9 11
2 4 6 8 10 12

http://fruitking.iteye.com/blog/505037

回复
分享到 :
0 人收藏
返回列表
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

3级会员
已经匿名di用户

积分:81
帖子:4969
精华:0
+ 关注 私信
期权论坛 期权论坛
期权网络科技版权所有
关于我们
联系我们
加入我们
反馈问题
免责声明
积分充值
统一社会信用代码
积分规则
网站地图
爱文库
下属网站
官方
新浪微博
微信公众号
◆
下载
表情包
App下载
期权论坛 期权论坛

QQ咨询|关于我们|Archiver|手机版|小黑屋|( 辽ICP备15012455号-4 ) Powered by 期权论坛 X3.2 © 2001-2016 期权工具网&期权论坛 Inc.

发布
内容

下载期权论坛手机APP