王者编程大赛之一

justCoding 发布于2019-07-01 12:36 / 2589人阅读

摘要：首发于樊浩柏科学院本次王者编程大赛分为个组别，分别为研发测试移动战场。本章只叙述前道相对简单的题目，后续题目及解题思路将在王者编程大赛系列中列出。

首发于 樊浩柏科学院

本次王者编程大赛分为 3 个组别，分别为研发、测试、移动战场。这里只讨论研发战场所考的题目，本次大赛共有 7 道题，主要考查点为基础算法，解题所用语言不做限制，但是需要在在线验证平台使用标准输入并验证通过，最后成绩以正确性和答题时间为评定依据。

所有题目中第 4 题蓄水池问题，是困惑我时间比较长的，其他题目比较容易看出考察点，这里我给出了 7 道题目自己的实现方式，仅作为解题参考，若你有更好的思路欢迎讨论交流。

本章只叙述前 3 道相对简单的题目，后续题目及解题思路将在王者编程大赛系列中列出。

标准输入过滤

由于采用标准输入进行输入，为了防止输入多余的字符，影响程序执行结果，所以有必要对输入进行过滤处理。

//等待输入并过滤
while(!$input = trim(fgets(STDIN), " 	

x0B[]"));

题1 题目

活动“司庆大放送，一元即租房”，司庆当日，对于签约入住的客户，住满 30 天，返还（首月租金 -1 元）额度的租金卡。租金卡的面额遵循了类似人民币的固定面额（1000 元、500 元、100 元、50 元、20 元、10 元、5 元、1 元），请实现一个算法，给客户返还的租金卡张数是最少的。

示例：
输入（租金卡金额）：54
输出：5
输入（租金卡金额）：9879
输出：20

解题思路

该问题其实就是，对租金卡的金额对题目中所列出的租金卡面额按照从大到小的顺序做商，一直到余数为 0。

编码实现

function getCards($rent) {
    $cardMoney = array(1000, 500, 100, 50, 20, 10, 5, 1);
    $cardNumber = array_fill(0, count($cardMoney), 0);

    $i = 0;
    do {
        $cardNumber[$i] = intval($rent / $cardMoney[$i]);
        $rent = $rent % $cardMoney[$i];
        if ($rent < $cardMoney[$i]) {
            //移动到下一个面额
            $i++;
        }
    } while ($rent);

    return $cardNumber;
}

//输入:54
$card = getCards((int)$input);
echo array_sum($card), PHP_EOL;

题2 题目（排列组合）

2016 年自如将品质管理中心升级为安全与品质管理中心，并开通了自如举报邮箱。请看下边的算式

1 2 3 4 5 6 7 8 9 = 110（举报邮箱前缀数字）;

为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12 + 34 + 56 + 7 - 8 + 9 就是一种合格的填法。

请大家帮忙计算出多少个可能组合吧，至少 3 个以上算有效。

示例：
输入：[1 2 3 4 5 6 7 8 9]
输出：12 + 34 + 56 + 7 - 8 + 9

解题思路

该题考查点是排列组合问题，待连接的数字已经有序，所以只需要确定相邻两个数字的连接符即可。假设待连接数字的长度为 n，那么问题可以描述为，将空格、+、- 这 3 种连接符插入到 n-1 个相邻待连接数字之间的位置，所以共有 3^n-1 种情况，然后判断每种情况的计算结果是否为等式右边的数字。

为了获取 3 种连接符组成的 3^n-1 种组合情况，这里巧妙地运用 3 进制运算来实现。

算法执行流程：

编码实现

实现类结构如下，特殊的方法已提取出，并将一一详细说明。

originLen = count($data);
        $this->sum = $sum;

        foreach ($data as $k => $value) {
            $this->data[$k*2] = $value;
        }
    }
}

3 进制运算的实现，注意需要对高位进行补 0 的操作，其中 number 为 3^n-1（组合情况）。

public function ternary($number)
{
    $pos = 2 * $this->originLen - 3;

    do {
        $mod = $number % 3;
        $number = (int)($number / 3);
        $this->data[$pos] = $this->operate[$mod];
        $pos -= 2;
    } while($number);
    //高位补0
    while ($pos > 0) {
        $this->data[$pos] = $this->operate[0];
        $pos -= 2;
    }

    ksort($this->data);
}

对 3 种连接符组成 3^n-1 种组合，根据等式成立情况进行取舍：

public function run()
{
    $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;
}

接收标准输入并输出结果：

//输入:[1 2 3 4 5 6 7 8 9]
$rank = new Rank(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 的排列，因为这 2 个数存在 2 种排列情况，既 a_b 和 b_a，若 a_b 组合值大于 b_a 组合，那么认为 a "大于" b，则 a 需要排列在 b 前面，反之则需要交换 a 和 b 的位置。同我们熟悉的排序算法唯一不同的是，这里不是直接通过比较 2 个元素值大小，而是需要通过排列后的 2 个新值进行大小比较。

排序算法：由于只是比较规则的不同，所以常用的排序算法（冒泡、快速、堆）一样适用。

这里使用冒泡排序来进行说明，每一趟找出待排序元素的最小值，算法执行流程如下：

编码实现

定义比较规则，ab 和 ba 组合后的数字进行值大小的比较：

function cmp($a, $b) {
    if ($a == $b) {
        return 0;
    }
    return $a . $b > $b . $a ? -1 : 1;
}

接收输入并输出结果：

function array_form_max_str(array $Arr) {
    foreach ($Arr as $value) {
        if ($value < 0) {
            return "";
        }
    }

    usort($Arr, "cmp");
    //拼接
    return implode("", $Arr);
}

//输入:4,94,9,14,1
echo array_form_max_str(explode(",", $input)), PHP_EOL;

总结

这 3 道题算是热身吧，第 2 题巧妙运用 3 进制运算来模拟排列情况，都相对较容易，只是实现方式你是否会在意优雅而已。虽然简单，但是也不建议一上来就开始编码，首先要想清楚解题思路，然后编码实现即可。

相关文章 »

王者编程大赛之二 — 蓄水池（2017-12-05）

王者编程大赛之三 — 01背包（2017-12-05）

王者编程大赛之四 — 约瑟夫环（2017-12-06）

王者编程大赛之五 — 最短路径（2017-12-06）

服务器托管 idc机房托管世界编程大赛数据分析之一 webrtc学习之一开篇王者

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/31077.html

王者编程大赛之三 — 01背包

摘要：动态规划概念动态规划过程每次决策依赖于当前状态，又随即引起状态的转移。相关文章王者编程大赛之一王者编程大赛之二蓄水池王者编程大赛之四约瑟夫环王者编程大赛之五最短路径首发于樊浩柏科学院服务目前每月会对搬家师傅进行评级，根据师傅的评级排名结果，我们将优先保证最优师傅的全天订单。 showImg(https://img3.fanhaobai.com/2017/12/2017-ziro...

Cympros 2019-07-01 12:36 评论0 收藏0
王者编程大赛之五 — 最短路径

摘要：由于是从顶点到的最短路径，则有。算法流程根据最短路径的最优子结构性质，提出了以最短路径长度递增，逐次生成最短路径的算法。相关文章王者编程大赛之一王者编程大赛之二蓄水池王者编程大赛之三背包王者编程大赛之四约瑟夫环首发于樊浩柏科学院自如年底就会拥有 50W 间房子，大家知道每间房房子都是需要配置完才能出租给自如客的，整个房租的配置过程是很复杂的，每天都需要大量的物流师傅将家电、家具...

yuanzhanghu 2019-07-01 12:36 评论0 收藏0
王者编程大赛之二 — 蓄水池

摘要：相关文章王者编程大赛之一王者编程大赛之三背包王者编程大赛之四约瑟夫环王者编程大赛之五最短路径首发于樊浩柏科学院自如寓打算门口用砖头围立一个蓄水池子，从上面看凹凸不平，凹的地方会有积水。那如果用数字代表每个砖头的高度，就形成一个二维数据（如示例），请问这个池子能存储多少单位的水？showImg(https://segmentfault.com/img/remote/1460000...

Me_Kun 2019-07-01 12:36 评论0 收藏0
Get 了滤镜、动画、AR 特效，速来炫出你的短视频开发特技！

摘要：月日，七牛云联合八大短视频特效平台共同推出了中国短视频开发者创意大赛，面向全国邀请广大开发者，基于大赛提供的或使用其他适合的，进行短视频轻应用的开发设计。在滤镜美颜、搞怪特效、炫酷场景等各种新奇玩法驱动下，短视频开始让人上瘾。 12 月 3 日，七牛云联合八大短视频特效平台共同推出了中国短视频开发者创意大赛（China Short Video Contest），面向全国邀请广大开发者...

xzavier 2019-07-16 16:22 评论0 收藏0
好雨云帮开发者大赛第二期：「Beego」

摘要：许式伟七牛云存储社区发起人语言专家，著有语言编程。年创办七牛云存储，成功打造了全新的公有云存储服务。合作伙伴好雨及有权取消侵权作品参赛资格，并保留追究权利。用最拿手的语言和框架，在很棒棒的severless架构PaaS平台上做沉浸式DevOps流开发，轻松抱得大奖归！ [好雨云帮开发者大赛「第二期」：Beego]剧情已写好，就差有创意、有技术、有天赋、有实力的你来参加！ Progra...

tracy 2019-06-28 10:52 评论0 收藏0