算法之其他题型

0.输入格式处理

输入不说明有多少个 Input，以 EOF 为结束标志
C

    int a, b;
    // scanf 返回值为变量的个数，如果没有返回 -1，EOF 是一个预定义的常量 -1
    while (scanf("%d %d", &a, &b) != EOF) {  
        // ...
    }

C++

    int a, b;
    while (cin >> a >> b) {
        // ...
    }


输入不说明有多少个 Input，以某个特殊输入为结束标志
C

    // 示例 1
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF && (a != 0 && b != 0)) {
        // ...
    }
    
    // 或者
    while (scanf("%d %d", &a, &b) != EOF && (a || b)) {
        // ...
    }
    
    // 示例 2
    int n;
    while (scanf("%d", &n) != EOF && n != 0) {
        // ...
    }

C++

    // 示例 1
    int a, b;
    while (cin >> a >> b) {
        if (a == 0 && b == 0)
            break;
        // ...
    }
    
    // 示例 2
    int n;
    while (cin >> n && n != 0) {
        // ...
    }


指示有 N 个 Input

C

    int n;
    scanf("%d", &n);
    
    int a, b;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &a, &b);
        // ...
    }

C++

    int n;
    cin >> n;
    
    int a, b;
    while(n--) {
        cin >> a >> b;
    }

Python3

    n = int(input())
    for _ in range(n):
        # ...


指示有 N 组输入，并以某个特殊输入退出

C/C++

    int n;
    while (cin >> n && n != 0) {
        int a, b;
        for (int i = 0; i < n; i++) {
            cin >> a >> b;
            // ...
        }
    }


输入是一整行（包括空格）

用 char[] 接收（C/C++）

    const int MAXN = 1000;
    char buff[MAXN];
    
    // C
    gets(buff);
    puts(buff); // 输出
    
    // C++
    cin.getline(buff, MAXN);  // 第三个参数默认是 '\n'
    cin.getline(buff, MAXN, '\n');

用 string 接收（C++）

    string s;
    getline(cin, s);          // 第三个参数默认是 '\n'
    getline(cin, s, '\n');

输入是多行（包括空格）

C++

    int n;
    cin >> n;
    cin.get();  // 否则，n 也会计入下面的 getline()，导致少一组数据
    
    while (n--) {
        string s;
        getline(cin, s);
    }


从文件读取

C

    FILE *cfin = fopen("in.txt", "r");
    FILE *cfout = fopen("out.txt", "w");
    
    int a, b;
    // 注意要传入文件指针
    while (fscanf(cfin, "%d %d", &a, &b) != EOF) { // 类似的，把 scanf 替换成 fscanf
        fprintf(cfout, "%d\n", a + b);             // 把 printf 替换为 fprintf
    }
    
    fclose(cfin);
    fclose(cfout);

C++

    ifstream fin("in.txt");
    ofstream fout("out.txt");
    
    int a, b;
    while (fin >> a >> b) {
        fout << a + b << endl;
    }
    
    fin.close();
    fout.close();

1.如何判断一个自然数是否是某个数的平方

思路一：后n/2个数肯定不是平方，只需要对前一半的数进行判断即可。

思路二：使用二分查找，1-n有序进行查找即可。

2.如何判断一个数是否为2的n次方

思路一：对每一位进行判断即可。

思路二：使用trick如果是2的n次方那么（n-1）&n=0一定成立。

引申：求二进制中1的个数？也是使用思路二然后看可以循环多少次。

3.不使用除法操作实现两个数的除法

思路：进行减法，循环执行只要剩余的小于被除数，在这一过程进行计数即可。

引申：不使用加减乘除实现加法，使用位运算，分为三步，无进位相加使用异或，只进位使用按位与在左移，进位和无进位进行相加。一直循环直到进位为0。

如何只使用+=操作符实现加减乘除？

加法：a+b，执行a+=b即可

减法：a-b，把b+=到a即可

乘法：a*b，a+=a执行b次即可

除：a/b，对b不断的乘1，2，3..n，直到b*n>a，那么值为n-1。

4.根据rand7构造rand10

思路：（rand7-1）*7会返回一个集合{0，7，14....，42}每个数字生成概率为1/7，再加上一个rand7那么集合和可以等概论的生成0-49的数是1/49，因为p（AB）=P（A）P（B）=1/49。然后再对（rand7-1）*7+rand7进行截断成0-40，然后在对10取模然后进行加1操作即可。

5.如何求正整数n所有可能的整数组合（升序，可重复选取）

思路：每个递归都加一层for循环，每一层都会有不同的数被选取组合，但是要基于规则，例如：要保证升序和重复选取就必须循环的数大于等于已经选取的数。注意值的回溯。

6.如何等概率的从大小为n的数组中选取m个整数

思路：先随机的从n个数中随机选取一个数，然后把这个数交换到末尾，然后第二次再从剩余的n-1个数里面进行选取一个数，在交换到末尾一直这样进行m次就找到了m个数。

ps：因为第一个数被选中概率为1/n，那么第二个数被选中为：第一次没被选中乘第二次被选中的概率=n-1/n * 1/n-1= 1/n

扩展：洗牌算法

思路：指针从后向前，每次（在固定区间）rand一个int值进行交换。

def Knuth_Durstenfeld_shuffle(a):
    """Fisher–Yates Shuffle

    Args:
        a(list):
    """
    for i in range(len(a) - 1, 0, -1):
        j = random.randint(0, i)
        a[i], a[j] = a[j], a[i]

    return a

ps：从后向前也可以，一样的。

def Inside_Out_shuffle(src):
  """"""
  a = src[:]  # copy
  for i in range(len(a)):
      j = random.randint(0, i)
      a[i] = a[j]
      a[j] = src[i]
      # src[i] == 被赋值前的 a[i]
      #   可以看到 Inside_Out_shuffle 本质上就是 Knuth-Durstenfeld Shuffle 的拷贝版本

  return a

ps：无穷版本的蓄水池采样。（一样的）

def Inside_Out_shuffle_inf(src):
    """"""
    ret = []
    while True:
        try:
            j = random.randint(0, len(ret))
            if j == len(ret):
                ret.append(next(src))      #可以不用判断重复！走两步还是会覆盖的！
            else:
                ret.append(ret[j])
                ret[j] = next(src)
        except StopIteration:
            break

    return ret

扩展：等概率采样（请写出一个抽样算法，从该数据流中抽取`m`个数据，使得所有数据被选中的概率相等（以概率`m/n`被选中）。）

思路：当n<=m时全部选取。n>m时，从0-n选取一个数当成i，当i>=m时截断，i<m时进行替换第n = m+1个数据res[i] = src[n]。

ps：下标是从0开始的。

def Reservoir_sample(src, m):
    """下标从0开始的！！！！"""
    ret = []
    for i, item in enumerate(src):
        if i < m:
            ret.append(item)
        else:
            j = random.randint(0, i)  # i == m+k
            if j < m:  # 只要 j < m 就能加入 ret 表明 i >= m 之后的元素被选中的概率为 m/i = m/(m+k)
                ret[j] = src[i]

    return ret

ps：n=m+1时，根据算法定义，第m+1个元素被选中的概率=m/m+1，而前m个元素被选中的概率=1-被第m+1个元素替换的概率=1-(m/m+1)*(1/m)=m/m+1；说明前m+1个元素被选中的概率相等。

扩展：不等概率采样（查表法）

ps：类似word2vec的负例采样。

import random
from collections import Counter

def sample_non_balance(src, m):
    """"""
    cnt = Counter(src)  # 样本计数
    # 维护一个反向字典
    table = dict()
    i = 0
    for k, v in cnt.items():
        for _ in range(v):
            table[i] = k
            i += 1

    # 采样 m 次，m 可能大于 n
    n = len(src)
    ret = []
    for _ in range(m):
        j = random.randrange(n)
        ret.append(table[j])

    return ret

如何采样，使 n-1 被采样 n 次？

0 被采样 1 次，1 被采样 2 次，2 被采样 3 次，...

ps：其实一样的思路，查表法，先生成一个表，然后进行随机选择。

def solve(n):
    table = dict()
    index = 0
    for i in range(0, n):
        for _ in range(i + 1):
            table[index] = i
            index += 1

    i = random.randrange((1 + n) * n / 2)
    return table[i]

cnt = 1000000
ret = Counter([solve(4) for _ in range(cnt)])
for k, v in sorted(ret.items()):
    print(k, v / cnt)
'''
0 0.099951
1 0.200028
2 0.300225
3 0.399796
'''

扩展：生成随机数（用 rand_m() 生成 rand_n() ）

ps：rand_m() 生成的数在 [0, n)，当要生成的n大于m时，的处理方法！

思路：利用rand_m(m) * m + rand_m(m) 的意思是先等概率生成 0, m, 2m, .. (m-1)*m，然后在加上 rand_m(m)；最终效果相当于等概率生成 [0, m*m) 之间的数。

def rand_n(n, m):
    """"""
    o = rand_m(m) * m + rand_m(m)    # 错误写法: rand_m(m) * (m+1)
    t = (m*m) // n * n               # t 为小于 m*m 的 n 的最大整数倍
    while o >= t:
        o = rand_m(m) * m + rand_m(m)

    o = o % n
    return o

# 测试代码
cnt = 100000
d = Counter([rand_n(7, 5) for _ in range(cnt)])
for k, v in d.items():
    print(k, v / cnt)
print()
'''
3 0.14584
4 0.14105
0 0.14178
6 0.14287
1 0.14273
2 0.14088
5 0.14485
'''

扩展一：洗牌；扩展二：采样（采样m个位置，且每个位置采样的概率是m/n）；扩展三：采样（不等概率，例如负例采样）；

扩展四：生成随机数（处理生成n<m的方式，生成m平方的形式，然后进行截取即可！）

7.如何组合1，2，5这三个数使其和为100

思路一：使用暴力递归，每层递归都会有三种选择，超过100进行截断即可。

思路二：使用组合的方式，100最多有100个1或者50个2或者20个5，x+2*y+5*z=100满足即可。进行三重for循环枚举即可。

思路三：变换表达式x+5*z=100-2*y，代表x+5*z必须要是个偶数且x+5*z<=100加限制条件进行递归剪支。

8.非递归的快排和非递归的归并

快排：因为快排本身是自顶向下进行计算的，要实现非递归必须要利用栈结构，来模拟这一过程。

ps：类似先序遍历。

归并：归并本身是自顶向下到底后，才开始进行两两归并，然后依次回溯合并的过程；所系不需要一个栈结构来模拟，直接自底向上进行归并即可。

ps：递归到底层进行回溯的时候才会开始真正的归并。

9.判断还有几盏灯亮着