八皇后问题 Eight Queens Puzzle

八皇后问题是要在在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种方案。

算法

八皇后问题采用回溯法,每在一行放置一个皇后,先判断当前布局是否合理,合理就放置下一行,不合理则回溯,判断这一行的下一个位置。

C++代码实现

#include <iostream>
#include <cstdlib>
using namespace std;

class ChessBoard
{
    int n;
    int counter = 0; // 计数器,统计共有几个方案
    int* queens;

public:
    ChessBoard(int N)
    {
        n = N;
        queens = new int[n + 1]; // 该数组放置皇后的位置,下标1代表第一行
    }

    void Print() // 输出方案
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(j == queens[i]) // 如果该处放皇后, 就输出'#'
                    cout << "#";
                else
                    cout << "*"; // 如果该处不放皇后,就输出'*'
            }
            cout << "\n";
        }
        counter++; // 计数器自加
        cout << "\n";
    }

    void Place(int i) // 在第i行放置皇后
    {
        if(i > n) // 如果行数大于所求皇后数, 则代表该方案构造完毕, 输出
            Print();

        else
        {
            for(int j = 1; j <= n; j++) // 从第i行第1个位置开始试探
            {
                queens[i] = j; // 把皇后放置在第i行第j个位置
                if(currentOK(i)) // 判断当前布局是否合理
                    Place(i + 1); // 合理则放置下一行,不合理则回溯,试探该行的下一个位置
            }
        }
    }

    bool currentOK(int i) // 判断当前布局是否合理
    {
        for(int k = i - 1; k >= 1; k--)
            if(queens[i] == queens[k] || abs(queens[i] - queens[k]) == i - k) // 判断两个皇后是否列数一样,或是否在一条斜线上
                return false;
        return true;
    }

    int getCounter() // 返回计数器的值
    {
        return counter;
    }
};

int main()
{
    ChessBoard chessBoard(6);
    chessBoard.Place(1); // 从第1行开始放置
    cout << "Solutions: " << chessBoard.getCounter() << endl;
    return 0;
}

2016 小米 校园招聘 笔试题

线段覆盖

一条直线上有 N 条线段,已知它们的两个端点,计算这些线段覆盖了多大的长度(被多条线段覆盖的部分只计算一次)

算法

将线段打散成点,以处理重复的部分

Python代码实现


class Segment():
    def __init__(self, start, end):
        self.start = start
        self.end = end

def Sum(segments):
    coverd = set()
    for segment in segments:
        for i in range(segment.start, segment.end):
            coverd.add(i)
    return len(coverd)

if __name__ == '__main__':
    segments = [Segment(1, 3), Segment(2, 5), Segment(10, 15)]
    print Sum(segments)

移位数组

给定一个整数数组 A 和一整数 key ,已知这个数组是由一个已排序、递增的数组旋转移位而成,但现在不知道这个数组被移动了多少位。
请实现下面的函数,找出 keyA 中的位置。
最后请分析所写代码的时间、空间复杂度,评分会参考代码的正确性和效率。
例如:
A = [6, 7, 8, 5] // 由[5, 6, 7, 8]向右移动3位而成
n = 8
结果为2

算法

二分查找。总是在有序的那一半里比较key,如果在这一半中,就在这半部分里继续二分查找,如果不在这半部分里,就舍弃它,在另一半里重复上面的操作

Python代码实现


def rotatedBinarySearch(A, N, key):
    L = 0
    R = N - 1

    while L <= R:
        # 避免溢出, 和 M = (L + R) / 2 是一样的
        M = L + ((R - L) / 2)
        if A[M] == key:
            return M

        # 左半部分有序
        if A[L] <= A[M]:
            if A[L] <= key and key < A[M]:
                R = M - 1
            else:
                L = M + 1

        # 右半部分有序
        else:
            if A[M] < key and key <= A[R]:
                L = M + 1
            else:
                R = M - 1

    return -1

if __name__ == '__main__':
    A = [6, 7, 8, 5]
    N = len(A)
    key = 8    
    print rotatedBinarySearch(A, N, key) # 程序输出 2

时间复杂度为 O(2logN)

朋友圈

假如已知有 n 个人和 m 个好友关系( r )。如果两个人是直接或间接的好友(好友的好友的好友…),则认为他们属于同一个朋友圈。请写程序求出这n个人里一共有多少个朋友圈。
例如: n = 5, m = 3, r = [[1, 2], [2, 3], [4, 5]] , 表示有5个人,1和2是好友,2和3是好友,4和5是好友,则1、2、3属于一个朋友圈,4、5属于另一个朋友圈。结果为2个朋友圈。
最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。

算法

用并查集,具体可以看这篇博客

Python代码实现

class UnionFind():
    def __init__(self, n):
        self.id = range(1, n + 1)

    def find(self, p):
        return self.id[p - 1]

    def union(self, p, q):
        pID = self.find(p)
        qID = self.find(q)
        if pID == qID:
            return
        else:
            for i in range(len(self.id)):
                if self.id[i] == pID:
                    self.id[i] = qID

if __name__ == '__main__':
    n = 5
    m = 3
    r = [[1, 2], [2, 3], [4, 5]]
    UF = UnionFind(n)
    for relation in r:
        UF.union(relation[0], relation[1])
    count = set()
    for i in UF.id:
        print i
        count.add(i)
    print len(count) # 程序输出2

Count Primes

LeetCode上面有一道数质数的题(Count Primes),里面给的提示是一种非常快的算法,感觉很经典,现在我把它的提示翻译出来,并附上自己的Python代码。

  1. 先从 isPrime 函数开始说起。为确定一个数是否是质数,要检查它是否能被 n 以下的整数整除。所以 isPrime 的时间复杂度是O(n ), 而数质数的时间复杂度就是O(n2)。还能做到更好吗?

  2. 我们都知道这个数不能被 > n / 2 的数整除,所以我们可以把迭代次数砍半。还能做到更好吗?

  3. 先写一下12的约数:
    2 × 6 = 12
    3 × 4 = 12
    4 × 3 = 12
    6 × 2 = 12
    可以看出,没必要计算 4 × 3 和 6 × 2 。所以,只要计算到 √n 就可以了。因为如果 n 可以被 p 整除,那么 n = p × q, 又 pq,那么可以推出 p√n 。现在的时间复杂度达到了O(n1.5)。还有更快的办法吗?

  4. 埃拉托色尼筛选法(Sieve of Eratosthenes)是找质数最快的的算法。别看名字很吓人,概念其实很简单。
    埃拉托色尼筛选法
    这是一个 n 个数的表格。先看第一个数字,2。2的倍数显然不是质数,先把它们划掉。再看下一个数,3,把它的倍数也划掉。再看下一个数,4,它已经被划掉了。这告诉了你什么?我们还需要划掉4的倍数吗?

  5. 4不是质数,因为它可以被2整除,这就意味着所有4的倍数都能被2整除,而且已经被划掉了。所以我们可以跳过4。再看下一个数,5,它的倍数也可以被划掉。这里还有优化的空间,我们不需要从 5 × 2 = 10 开始,那么该从哪开始呢?

  6. 其实,我们可以从 5 × 5 = 25 开始。因为 5 × 2 = 10 在划2的倍数时就已经被划掉了,相似的,5 × 3 = 15 在划3的倍数时就已经被划掉了。所以,如果当前数字是 p ,我们可以从 p2 开始划,接着划p2 + p, p2 + 2p, …那么循环结束的条件是什么呢?

  7. p < n 来结束循环是最简单的想法,但它效率不高。你还记得第3点吗?

  8. 是的,可以用 p < √n 来结束循环,因为所有 ≥ √n 的非质数已经被划掉了。等循环结束时,表格中还没被划掉的数就是质数。

下面附上以上算法的Python代码实现:

import math
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        isPrime = [False, False] //0,1置成非质数
        for i in range(2, n):
            isPrime.append(True)
        k = int(math.ceil(math.sqrt(n)))
        for i in range(2, k):
            if not isPrime[i]:
                continue
            for j in range(i * i, n, i):
                isPrime[j] = False
        count = 0
        for i in range(2, n):
            if isPrime[i]:
                count += 1
        return count

一维博客迁移到GitHub!

一维博客迁移到 prdwb.github.io !

利用 SAE 实现新成绩提醒

现在到了很多大学期末的出分阶段,但是不少学校的手机助手都没有新成绩提醒的功能,那现在我就给大家演示如何利用 SAE 实现这一功能。它涉及解析 JSON 数据、SAE 上 Mail ,  Cron , 和 Storage 服务的使用等。

主要的想法是将代码部署在 SAE 上,利用 Cron 服务定时查询成绩,解析返回的 JSON 数据,将课程名和成绩取出来,存入新的数组中并计数,当下次查到的成绩个数有变化时,就调用 Mail 服务给自己发送邮件。

  1. 先通过抓包等方式获得查询成绩的接口,比如我们学校的接口是这样的:
http://yimutest.sinaapp.com/dutserver/index.php?r=edu/scoreall&pass=password&stuid=studentID&

其中 password 换成密码,studentID 换成学号。

  1. 在 SAE 上新建一个项目,叫做 dutscore, 再在 Storage 中新建一个 domain 叫做 dutscore,然后在其中新建一个文件,叫做 counter_old_mem.php,用于存放上次查询到的成绩个数,这个文件要先写入如下内容:
<?php return $counter_old = 0; ?>

3.在代码管理中创建一个新版本的代码,在 index.php 中写入如下代码:

<?php
$api = 'http://yimutest.sinaapp.com/dutserver/index.php?r=edu/scorethis&pass=password&stuid=studentID';

//初始化计数器
$counter = 0;

//向学校服务器请求成绩信息,存入变量 info
$info = file_get_contents($api);

//解析返回的 JSON 数据
$de_json = json_decode($info, true);
$list =  $de_json['result']['Score.list'];
$count = count($list);
$output = array($count);

//将课程名称和成绩取出来,存入数组 output,并统计成绩个数,存入变量 counter
for( $i = 0; $i < $count; $i ++ )
{   $output[$list[$i]['name']] = $list[$i]['score'];
	if($list[$i]['score'] != NULL)
        $counter++;
}

//从外部文件读入上次查询的成绩个数
$counter_old = include 'saestor://dutscore/counter_old_mem.php';

//如果这次查到的成绩个数与上次不同,就发送邮件通知我们
if($counter != $counter_old)
{   $to = '用于接收邮件的邮箱';
    $subject = '新成绩!';
    $msgbody = print_r($output,true);
    $smtp_user = '用于发邮件的邮箱';
    $smtp_pass = '用于发邮件的邮箱的密码';

    $mail = new SaeMail();

    $ret = $mail->quickSend($to, $subject, $msgbody, $smtp_user, $smtp_pass);

    //发送失败时输出错误码和错误信息
    if ($ret === false) {
        var_dump($mail->errno(), $mail->errmsg());
    }

    $mail->clean(); //重用此对象

    //将这次查到的成绩个数写入外部文件
    $context = '<?php return $counter_old = '.$counter.'; ?>';

    file_put_contents('saestor://dutscore/counter_old_mem.php', $context);
}

?>

以上代码适用于大连理工大学,其他学校需要根据具体情况进行微调。需要调整的地方一定有 api,可能有解析 JSON 数据的部分。

  1. 接下来就要实现定时执行上一步创建的脚本,利用的是 SAE 的 Cron 服务。

在代码根目录下已有的 config.yaml 中写入如下代码:

name: dutscore
version: 1
accesskey: ACCESSKEY
cron:
    - description: dutscore
     url: index.php
     schedule: every 1 hour, from 6:00 to 23:00
     timezone: Beijing

其中 accesskey 部分填写该项目的 accesss key,url 部分填写要执行的脚本, schedule 部分填写执行的时间安排。

至此,你就完成了了一个简单的 新成绩通知 的小程序啦!

由于我是第一次接触 PHP,代码中肯定有不规范、不简洁的地方,希望大家可以指出。