有n辆共享单车,编号依次为A,B,C,… 。现在要将单车整齐摆放,其中A车、B车属于特殊车型,并且B车比A车大,现要求B车必须摆在A车后,例如A-B-C, A-C-B等,有多少种摆放方法。备注:至少3辆单车。-笔试面试资料

这是qklbishe.com第19973 篇笔试面试资料
提供答案分析,通过本文《有n辆共享单车,编号依次为A,B,C,… 。现在要将单车整齐摆放,其中A车、B车属于特殊车型,并且B车比A车大,现要求B车必须摆在A车后,例如A-B-C, A-C-B等,有多少种摆放方法。备注:至少3辆单车。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:
有n辆共享单车,编号依次为A,B,C,… 。现在要将单车整齐摆放,其中A车、B车属于特殊车型,并且B车比A车大,现要求B车必须摆在A车后,例如A-B-C, A-C-B等,有多少种摆放方法。备注:至少3辆单车。

有n辆共享单车,编号依次为A,B,C,... 。现在要将单车整齐摆放,其中A车、B车属于特殊车型,并且B车比A车大,现要求B车必须摆在A车后,例如A-B-C, A-C-B等,有多少种摆放方法。备注:至少3辆单车。 零葬
憋了很久,本想对AA…ABB…B进行插空,但这样好像只能计算出方案数,不容易得到具体的排列。并且在其他类型的车比AB的间隔多时会牵涉到某一段的全排列,并没有提高效率。所以懒得憋高超诡谲的技巧了,先用暴力方法试试测试用例,结果AC了。

深度优先搜索

DFS进行全排列得到所有的方案,在生成方案的过程中检查方案是否满足所有A都在B之前(只需检查最后一个A是不是在第一个B之前),同时计数,将满足题意的方案添加进结果字符串。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException;  public class Main {     static int count = 0;     static StringBuilder res = new StringBuilder();     public static void main(String  
[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int n = Integer.parseInt(br.readLine());         String
[] bikes = br.readLine().split(" ");         permutation(bikes, 0, n - 1);         res.append(count);         System.out.println(res);     }          private static void permutation(String
[] arr, int start, int end) {         if(start == end){             if(isValid(arr)) {                 count ++;                 StringBuilder path = new StringBuilder();                 for(int i = 0; i < arr.length; i++){                     path.append(arr
[i]);                     if(i < arr.length - 1){                         path.append("-");                     }else{                         path.append(" ");                     }                 }                 res.append(path.toString());             }         }else{             for(int i = start; i <= end; i++){                 swap(arr, start, i);                 permutation(arr, start + 1, end);                 swap(arr, start, i);             }         }     }          private static boolean isValid(String
[] arr) {         int lastA = 0, firstB = 0;         boolean flag = true;         for(int i = 0; i < arr.length; i++){             if(flag && "B".equals(arr
[i])){                 firstB = i;                 flag = false;             }             if("A".equals(arr
[i])){                 lastA = i;             }         }         return lastA < firstB;     }          private static void swap(String
[] arr, int i, int j) {         if(i != j){             String temp = arr
[i];             arr
[i] = arr
[j];             arr
[j] = temp;         }     } }

不得不说奇安信春招的算法编程题比秋招还是要难的,春招的题多少还有点技巧,秋招卷的编程题都是些水题,所以同学们还是尽量不要拖到春招啊,秋招赶紧上岸~

今天 09:36:53 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 有n辆共享单车,编号依次为A,B,C,… 。现在要将单车整齐摆放,其中A车、B车属于特殊车型,并且B车比A车大,现要求B车必须摆在A车后,例如A-B-C, A-C-B等,有多少种摆放方法。备注:至少3辆单车。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情