标签 算法 下的文章

并查集与渗漏问题

前两周的时候看到有人推荐https://www.coursera.org/learn/algorithms-part1/的算法课,正好基础也忘得差不多了,觉得也是应该复(yu)习(xi)一下了,普林斯顿的这个公开课确实不错。

好了,废话不多说,来总结一下第一周,说说并查集和渗漏问题吧。

数据结构介绍

并查集是一个处理连接问题的数据结构,可以用这个结构快速的找到两个元素是否属于同一集合(或者说连通),和图的连通算法不同的是它忽略了路径的概念,只需要结果。

- 阅读剩余部分 -

JavaScript 确定一个字符串的所有字符均不同

上次去Google Girls送了我一本面试金典,前天无聊就看了起来,看到的部分目前还是比较基础也有些意思的,在我看到第一堆算法题的时候我说了一句,这个题看着有点简单啊……然后秒被打脸,可以说,所有的题都是想简单就简单,想难就难,主要看你考虑了多少。

今天就拿其中一道题来说说上面的观点。

实现一个算法,确定一个字符串的所有字符是否不同,假设不允许使用额外的数据结构,又该如何处理。

- 阅读剩余部分 -

rsync配置与使用指南

好了,这一篇我们顺着上面几篇的思路来说说rsync,所有的内容在参考链接中都可以看到更详细应该也是更有深度的说明……

rsync科普级介绍

如果你在寻找一个差异同步上传机制,那么rsync就是你想要的,在目录中选择性拷贝,安全保障,提供多种传输方式,具体的功能可以从之后的介绍和扩展阅读中看出。

rsync算法介绍

酷壳有一篇介绍,不过一些名词介绍的比较让人郁闷,先给个总结:rsync = 分块hash check + 滑动窗口。

- 阅读剩余部分 -

JavaScript 排列与组合

排列与组合在我们日常生活中其实也是挺常用的,包括在算法中,也算是比较实用的东西,但是排列组合也是一个难点,这里我们先从简单的出发。

最简单的是全排列和全组合,其中组合的思路更加简单易行,因此我们先从全组合说起。

在说之前,我们先来确定一下定义(数学渣只能从自己下定义开始以免误导读者),我们的全排列,指的是PNN,也就是有n个数字,坑也有n个,求全部的排列情况;全组合,则是除了空集外,n个字母能组成多少种可能性(不一定要全部使用)。

由此,我们开始了我们的全组合之旅:

- 阅读剩余部分 -

JavaScript 说说随机排序(洗牌程序)

在小鱼的gayhub看到了这样的一题,其中就需要用到洗牌程序,当然,我在看到排序算法的时候就想到这样可以用于排序,所以很快就有了第一个排序算法:

var shuffleHack = function(arr) {

    var result = arr.slice();

    result.sort(function() {

        return Math.random() - 0.5;

    });


    return result;

};


- 阅读剩余部分 -

JavaScript 说一个排序算法

依旧还是面试题,比较麻烦的是,这个排序的关键在于,我们需要时间复杂度为O(n),空间复杂度为O(1)。

题目大概是这样的,看了输入输出基本就会明白了:

input: arr = ['', 'a', 'b', '', 'a', 'c', '', 'm']
output: [ '
', '', '', 'a', 'a', 'b', 'c', 'm' ]
问题描述:将数组中的字母与星号分开

这里其实主要没做出来是因为我没有很好地理解怎么计算复杂度,尤其是空间复杂度,时间复杂度我勉强记忆成for循环的嵌套还是可以的,但是空间复杂度呢?

- 阅读剩余部分 -

菜鸟说动态规划

从我学习至今,我有三大心理阴影:递归、正则表达式、动态规划——这三个导致让我怀疑智商怀疑人生。

在这次假期刷题的时候,前两个似乎都已经不是问题了,就差动态规划——昨天不行random到一道题,一眼望着就是动态规划了——可是我不会啊。

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

题目来自LeetCode,本来是不准备写LeetCode的题了,全都在GitHub上了大家看看就行了,不过这题有助于让我们更好地理解(第一次理解)动态规划。

- 阅读剩余部分 -

SMU 算法题 情书的编码

题目:

截获了Bobwu的检讨以后,Linkinpaoger突然想到可以用自己的加密方式来加密情书。Linkinpaoger写了一封给Anonymous的情书并加密,然后发现密文中出现了很多类似ABBCCC的字符串。经过思索,Linkinpaoger决定按以下规则压缩密文:

1.任何包含k个相同字符的子串被替换为kX,X表示该子串中的唯一字符。

2.若某个这样的子串长度为1,那么省略‘1’。

按以上规则,ABBCCC将被压缩为A2B3C。现在请你帮Linkinpaoger压缩密文。

输入:

输入的第一行为一个正整数N,表示共有N组测试数据,接下来的每一行表示一组密文,密文仅由‘A'-’Z'组成。

1≤N≤100,每组密文的长度不超过10000个字符长度。

输出:

对于每组输入数据,输出一行压缩后的密文。

- 阅读剩余部分 -

SMU算法题 Weijie环

在欢送会上,大家决定玩一个游戏,这个游戏叫做Weijie 环,所有的N 个人站成一圈,由一个人随意说一个数字A,从他顺时针下一个人开始顺时针数,第A个人出圈(下次就不数出圈的人),然后从第A 个人顺时针后面1 个人开始顺时针数A+1,第A+1 个人出圈,依次数A+2,A+3……,最后留在圈内的人获胜。
现在轮到BobWu 说数字,他报出了一个数字A,现在BobWu 想知道自己是第几个出列的。

详情:http://mstc.shmtu.edu.cn/oj/problem.php?cid=1003&pid=2

好像以前看过类似的题,不过没做出来,当时也没准备做……结果发现就其本身而言不用数组也可以。

- 阅读剩余部分 -

SMU 算法题:BobWu的胜率统计

大家玩了很久,由于之前就有过大家玩游戏的记录,大家开始查看各自的胜率,游戏的结果对于每个人就两种,要么就赢,要么就输,今天大家玩了D 局,大家总共玩了G 局,但是当BobWu 查看胜率记录的时候,发现自己的今天的胜率恰好是一个整数PD,自己的总胜率也恰巧是一个整数PG!他开始怀疑是不是因为大家玩游戏输掉会被惩罚喝酒于是计算错了。可是由于大家都喝酒了,谁都记不得今天玩了几局(D),也记不得总共玩了几局(G),但是可以确定今天一定不可能玩超过了N 局(D≤N)现在BobWu 想知道这样的胜率究竟是有可能,还是一定计算错了。

题目详情:http://mstc.shmtu.edu.cn/oj/problem.php?cid=1003&pid=3

#include <stdio.h>

int divide(int big, int small)
{
    int r;

    r = big % small;

    while (r != 0)
    {
        big = small;
        small = r;
        r = big % small;
    }

     return small;
}

int main(void)
{
    unsigned int n[100], pd[100], pg[100], t, possible[100], big = 100, temp;
    int i;

    scanf("%u", &t);
    for (i = 0; i < t; i++)
    {
        scanf("%u", &n[i]);
        scanf("%u", &pd[i]);
        scanf("%u", &pg[i]);

        if (100 / divide(100, pd[i]) > n[i])
            possible[i] = 0;

        if( pg[i] > 100 || pg[i] == 100 && pd[i] != 100 || pg[i] == 0&& pd[i] != 0)
            possible[i] = 0;
        else
            possible[i] = 1;
    }

    for (i = 0; i < t; i++)
    {
        switch (possible[i])
        {
            case 1:
                printf("Case #%d: Possible\n", i + 1);
                break;
            case 0:
                printf("Case #%d: Broken\n", i + 1);
                break;
        }
    }

    return 0;
}

在我按了半天计算器之后,终于发现,要计算的是分母,而且要最简形式,问题就转换了,可是关键是怎么求……于是我尝试了各种方法,按了好多遍计算器最终发现求公约数就可以了OTZ100 / divide(100, pd[i])这样求出的就是分母了,没想到辗转相除法能这么用,不由得给那一次的上机题点赞了,数学不好的人科普福音啊。

估计效率也不咋的,凑合着用……

PS:科普链接:http://androidguy.blog.51cto.com/974126/1219145