首发于范浩博科学院。本次编程王者大赛分为研发、测试、移动战场3个组别。这里只讨论研发战场上的问题。本次比赛共有7道题。主要考点是基础算法。做题语言不限，但需在在线验证平台使用标准输入并通过验证。最后的分数是正确的。评估基于性别和回答时间。在所有的问题中，水库问题的第4题让我困惑了很久。其他问题更容易看到检查点。这里我给出7道题的实现方法，仅作为解题参考。如果您有更好的想法欢迎讨论交流。本章只介绍前三个比较简单的问题，后续的问题和解题思路会在编程王系列赛中列出。标准输入过滤由于使用标准输入进行输入，为了防止冗余字符的输入影响程序执行结果，需要对输入进行过滤。//等待输入和过滤while(!$input=trim(fgets(STDIN),"\t\n\r\0\x0B[]"));问题1标题活动“四清广播，1元就是租房”，庆典当天，签约入住30天的客户，赠送金额为（首月租金-1元）将被退还。租赁卡的面额遵循类似于人民币的固定面额（1000元、500元、100元、50元、20元、10元、5元、1元）。请实现一种算法，使返回给客户的租赁卡数量最少。例子：输入（租卡金额）：54输出：5输入（租卡金额）：9879输出：20解题思路问题其实是，租卡的金额与房租面额的比值题中所列的卡片按照最大值从小到大的顺序做生意，直到余数为0。实现功能的代码getCards($rent){$cardMoney=array(1000,500,100,50,20,10,5,1);$cardNumber=array_fill(0,count($cardMoney),0);$i=0;做{$cardNumber[$i]=intval($rent/$cardMoney[$i]);$rent=$rent%$cardMoney[$i];if($rent<$cardMoney[$i]){//移动到下一个面额$i++;}}while($rent);return$cardNumber;}//输入：54$card=getCards((int)$input);echoarray_sum($card),PHP_EOL;2课题（整理组合）2016年，自如将质量管理中心升级为安全质量管理中心，开通自如举报信箱。请看下面的公式123456789=110（报告邮箱前缀号码）；为了使等式成立，需要在数字之间填上加号或减号（可以留空，但不能填其他符号）。将数字组合起来，中间不填符号组成一个数字，例如：12+34+56+7-8+9就是合格的填法。请帮忙计算一下可能的组合有多少种，至少3种以上才算有效。例：输入：[123456789]输出：12+34+56+7-8+9解题思路需要确定两个相邻数字的连接符。假设待连数的长度为n，那么问题可以描述为在n-1个相邻待连数之间的位置插入空格，+，-，所以有3^n-1种情况，然后判断每个case的计算结果是否是等式右边的数。为了得到3种连接器的3^n-1种组合，这里我们巧妙地使用了3进制运算来实现。算法执行过程：EncodingImplementation实现类结构如下，其中提取了特殊方法，将一一详细说明。originLen=count($data);$this->sum=$sum;foreach($dataas$k=>$value){$this->data[$k*2]=$value;}}}3进制运算的实现，注意高位需要补0，这里的数是3^n-1（组合）。publicfunctionternary($number){$pos=2*$this->originLen-3;做{$mod=$number%3;$number=(int)($number/3);$this->data[$pos]=$this->operate[$mod];$pos-=2;}while($number);//高位加0while($pos>0){$this->data[$pos]=$this->operate[0];$pos-=2;}ksort($this->data);}3种连接器组成3^n-1种组合，根据等式的成立进行选择：publicfunctionrun(){$result=array();$times=pow(3,$this->originLen-1);for($i=0;$i<$times;$i++){//模拟3个基操作$this->ternary($i);//决策$str=implode('',$this->data);if(eval("return$str;")==$this->sum){$result[]=$str;}}return$result;}接收标准输入输出结果：//Input:[123456789]$rank=newRank(explode('',$input),110);array_walk($rank->run(),function($value){echo$value,PHP_EOL;});问题3标题（排序）给定一个所有元素都非负的数组，连接所有数字以找到最大的数字。例：输入：4,94,9,14,1输出：9944141输入：121,89,98,15,4,3451输出：98894345115121本题解题思路本题为我司笔试题之一。之前写的《求非负元素数组所有元素能组合的最大字符串》一文已经描述了实现过程。当然，这道题的实现方式可能有很多种，但我觉得最合适的方式还是用排序，简单易懂，实现起来也简单。比较规则：分析a和b的排列，因为这两个数有两种排列方式，都是a_b和b_a，如果a_b的组合值大于b_a的组合，那么a就认为“大于”b，那么a需要排在b的前面，否则需要交换a和b的位置。与我们熟悉的排序算法唯一不同的是，它不是直接比较两个元素值的大小，而是需要比较排序后两个新值的大小。排序算法：由于只是比较规则不同，常用的排序算法（冒泡、快速、堆）也适用。这里用冒泡排序来说明，每次求待排序元素的最小值，算法执行过程如下：代码实现定义比较规则，比较ab和ba组合后的数在值中：functioncmp($a,$b){if($a==$b){return0;}返回$a。$b>$b。$一个？-1:1;}接收输入输出结果：functionarray_form_max_str(array$Arr){foreach($Arras$value){if($value<0){return'';}}usort($Arr,"cmp");//拼接returnimplode('',$Arr);}//Input:4,94,9,14,1echoarray_form_max_str(explode(',',$input)),PHP_EOL;总结这3道题作为热身，第二道题巧妙的用三元运算来模拟排列，比较容易，只是在实现方式上讲究优雅与否。虽然简单，但是不建议一上来就开始coding。首先你要有一个清晰的解决问题的思路，然后代码去实现。相关文章?编程大赛之王二——水库（2017-12-05）编程大赛之王三——01背包（2017-12-05）编程大赛之王四——约瑟夫·林（2017-12-06）编程大赛之王五——The最短路径(2017-12-06)
