开发者社区> 技术mix呢> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

庞果英雄会部分题目解答

简介:
+关注继续查看

一、数组排序

  题目链接:http://hero.pongo.cn/Question/Details?ExamID=92&ID=94&bsh_bid=281776595

题目详情:

  给定一个包含1-n的数列,我们通过交换任意两个元素给数列重新排序。求最少需要多少次交换,能把数组排成按1-n递增的顺序,其中,数组长度不超过100。

  例如:

  原数组是3,2,1, 我们只需要交换1和3就行了,交换次数为1,所以输出1。

  原数组是2,3,1,我们需要交换2和1,变成1,3,2,再交换3和2,变为1,2,3,总共需要的交换次数为2,所以输出2。

  分析:

  通过示例可以看出,可以用数组的第一项跟最后一项比较,如果第一项比较大就换顺序,然后拿第二项跟最后一项(这时最后一项已经变了)比较,以此类推。这样最后一项就是最大的了,然后去掉最后一项再次执行这个过程。

  JavaScript代码如下:  

function arrSortMincount(arr) {
    var comCount = 0,
        lastItem = 0;
    console.log("sort arr: [" + arr.join(",") + "]");
    if(arr.length == 1) {
        return 0;
    }
    for (var i = 0, j = arr.length; i < j; i++) {
        lastItem = arr[j - 1];
        if (lastItem < arr[i]) {
            console.log("change " + arr[i] + " and " + lastItem);
            arr[j - 1] = arr[i];
            arr[i] = lastItem;
            comCount++;
        }
    }
    if (arr.length > 1) {
        arr.pop();
    }
    return comCount + arrSortMincount(arr);
}

console.log(arrSortMincount([1,2,3]));
console.log(arrSortMincount([3,2,1]));
console.log(arrSortMincount([2,3,1]));
console.log(arrSortMincount([1,3,2]));
console.log(arrSortMincount([9,8,7,6,5,4,3,2,1,0]));

//日志如下:
//sort arr: [1,2,3]
//sort arr: [1,2]
//sort arr: [1]
//0

//sort arr: [3,2,1]
//change 3 and 1
//sort arr: [1,2]
//sort arr: [1]
//1

//sort arr: [2,3,1]
//change 2 and 1
//change 3 and 2
//sort arr: [1,2]
//sort arr: [1]
//2

//sort arr: [1,3,2]
//change 3 and 2
//sort arr: [1,2]
//sort arr: [1]
//1

//sort arr: [9,8,7,6,5,4,3,2,1,0]
//change 9 and 0
//sort arr: [0,8,7,6,5,4,3,2,1]
//change 8 and 1
//sort arr: [0,1,7,6,5,4,3,2]
//change 7 and 2
//sort arr: [0,1,2,6,5,4,3]
//change 6 and 3
//sort arr: [0,1,2,3,5,4]
//change 5 and 4
//sort arr: [0,1,2,3,4]
//sort arr: [0,1,2,3]
//sort arr: [0,1,2]
//sort arr: [0,1]
//sort arr: [0]
//5

  如有更好算法欢迎讨论。

 

二、字符串消除

  题目链接:http://hero.pongo.cn/Question/Details?ExamID=83&ID=85&bsh_bid=278004606

题目详情:

定一个字符串,仅由a,b,c 3种小写字母组成。当出现连续两个不同的字母时,你可以用另外一个字母替换它,如

  1. 有ab或ba连续出现,你把它们替换为字母c;
  2. 有ac或ca连续出现时,你可以把它们替换为字母b;
  3. 有bc或cb 连续出现时,你可以把它们替换为字母a。

你可以不断反复按照这个规则进行替换,你的目标是使得最终结果所得到的字符串尽可能短,求最终结果的最短长度。

输入:字符串。长度不超过200,仅由abc三种小写字母组成。

输出: 按照上述规则不断消除替换,所得到的字符串最短的长度。

例如:输入cab,输出2。因为我们可以把它变为bb或者变为cc。

          输入bcab,输出1。尽管我们可以把它变为aab -> ac -> b,也可以把它变为bbb,但因为前者长度更短,所以输出1。

  分析:

  通过分析,可以发现从字符串开始替换,然后判断结果中是否还可以替换,如果有再进行这个过程。

  JavaScript代码:

function getMinLength(str){
    console.log("Test: ", str);
    var m = new RegExp("ab|ac|bc|ba|ca|cb", "g");
    str = str.replace(m, function(s){
        var reg = new RegExp(s.split("").join("|"), "g"),
            changeTo = "abc".replace(reg, "");
        console.log("replace " + s + " to " + changeTo);
        return changeTo;
    });
    if (m.test(str)) {
        return getMinLength(str);
    } else {
        console.log("Result: ", str);
        return str.length;
    }
}

console.log(getMinLength("cab"));
console.log(getMinLength("bcab"));
console.log(getMinLength("abccbaabccba"));
/*
Test: cab
replace ca to b
Result: bb
2

Test: bcab
replace bc to a
replace ab to c
Test: ac
replace ac to b
Result: b
1

Test: abccbaabccba
replace ab to c
replace cb to a
replace ab to c
replace cb to a
Test: ccaaccaa
replace ca to b
replace ac to b
replace ca to b
Test: cbbba
replace cb to a
replace ba to c
Test: abc
replace ab to c
Result: cc
2
*/

  如有更好算法欢迎讨论。

 

三、倒水

  题目链接:http://hero.pongo.cn/Question/Details?ID=70&ExamID=68

题目详情:

有两个容器,容积分别为A升和B升,有无限多的水,现在需要C升水。

我们还有一个足够大的水缸,足够容纳C升水。起初它是空的,我们只能往水缸里倒入水,而不能倒出。

可以进行的操作是:

  1. 把一个容器灌满;
  2. 把一个容器清空(容器里剩余的水全部倒掉,或者倒入水缸);
  3. 用一个容器的水倒入另外一个容器,直到倒出水的容器空或者倒入水的容器满。
    问是否能够通过有限次操作,使得水缸最后恰好有C升水。

输入:三个整数A, B, C,其中 0 < A , B, C <= 1000000000

输出:0或1,表示能否达到要求。

  分析:先求出由A升和B升可以得到几升(小于A和B中较大值),结果为一个数组,记为D(从大到小排列),然后用C对D逐项求余判断是否为0即可。
  如A=10,B=7,则D = [10, 9, 7, 6, 3]
  JavaScript代码:
function can(a, b, c) {
    var allContainer = getAllContainers(a, b);
    console.log(allContainer);
    for(var i = 0, j = allContainer.length; i < j; i++) {
        c = c % allContainer[i];
        if (c == 0 ) {
            break;
        }
    }
    return  c == 0 ? 1 : 0;
}

function getAllContainers(a, b) {
    if (a == b) {
        return [a];
    } else {
        var min = Math.min(a, b),
            max = Math.max(a, b),
            result = [];
        a = max;
        b = min;
        while(max - min < a) {
            result.push(max - min);
            min = b - (max - min);
        }
        result.push(b, a);
        return result.sort(function(a, b){
            return b - a;
        });
    }
}

console.log(can(10,7,3));
console.log(can(9,3,121));
console.log(can(11,7,22));
/*
[10, 9, 7, 6, 3]
1

[9, 6, 3]
0

[11, 8, 7, 4]
1
*/

  如有更好算法欢迎讨论。

版权

作者:Artwl

出处:http://artwl.cnblogs.com

本文首发博客园,版权归作者跟博客园共有。转载必须保留本段声明,并在页面显著位置给出本文链接,否则保留追究法律责任的权利。






本文转自Artwl博客园博客,原文链接:http://www.cnblogs.com/artwl/,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
30行代码爬取英雄联盟全英雄皮肤
30行代码爬取英雄联盟全英雄皮肤
30 0
拉我室友打了一把英雄联盟搞会了IntelliJ IDEA的安装与配置
拉我室友打了一把英雄联盟搞会了IntelliJ IDEA的安装与配置
34 0
427. 建立四叉树 : 递归与前缀和优化
427. 建立四叉树 : 递归与前缀和优化
43 0
jsp的C标签一般使用方法以及js接收servlet中的对象及对象数字
jsp的C标签一般使用方法以及js接收servlet中的对象及对象数组     由于现流行的javaWeb框架提倡前后端分离,比如在SpringMvc中已经很少写servlet的一些东西;目前 前端jsp中大多是一些纯html和js,很少用到jstl的一堆东西,后端也仅仅处理一些前端的post、get请求或页面跳转,无须以往繁琐的xml路径映射和filter过滤。
1061 0
H.264学习笔记之一(层次结构,NAL,SPS)
一 H.264句法 1.1元素分层结构 H.264编码器输出的Bit流中,每个Bit都隶属于某个句法元素。句法元素被组织成有层次的结构,分别描述各个层次的信息。     图1 H.264分层结构由五层组成,分别是序列参数集、图像参数集、片(Slice)、和宏块和子块。
935 0
艾伟也谈项目管理,较大型项目的产品工作心得
  最近做的一个项目从需求分析到上线绵延了四个月之久,这也是目前接手过功能点最繁复,产品线对接最多的一个项目。从中得到的一些关于设计较大型产品的心得,拿出来跟大家分享。   立项前   1、统一元素设计需考虑周全   也许是初创团队的缘故,我不得不感叹团队对产品经理要求之严格之缜密,项目全程只有一个人负责,所以大到产品线对接,小到一句提示的位置和展示形式都需要一一推敲。
1137 0
+关注
2968
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载