4道算法题目

 发表于 November 26, 2017  |  3 分钟  |  469 个字  |  svtter

四道做的比较走心的算法题目。

最接近的数字

题目

一个K位的数N

$$

(K\leq2000，N\leq10^{20})

$$

找出一个比N大且最接近的数，这个数的每位之和与N相同，用代码实现之。

例如：0050 所求书数字为0104；112 所求数为121；

算法分析 算法思想

直接暴力求这个数字是不可以的，数字的量级太大，有K位的数字，不可能直接用int，或者float来表示，使用数组来存储。应该分析这个数字，step1，从右边开始的最小位数开始，分解最后一位数字，分解出1来拿给前面的一位。9和0比较特殊，因此从左往右扫描的开始，遇到0就跳过，遇到第一个非0的数字，就把这个数字-1，然后移到最后面去，然后，step2，开始找第一个非9的数字，如果遇到9，就把9放到最后面去，遇到非9，就+1，结束运算。

一个般的例子：

1999000 -> 1990008-> 2000899

要注意一个问题，就是如果是 999000 这种情况，在数字的最开头补1，结果是1000899

几个刁蛮的数据：29399 -> 29489

伪代码

分析时间复杂度O

因为reverse操作，2K，加上最后整理最小数到最前面，最坏情况接近K，3K，在循环中的操作看运气，但是最糟糕的情况也只有5K，所以时间复杂度为

$$

O(3K) \approx O(K)

$$

源代码

测试结果

使用python生成测试数据进行测试：

存在错误的情况：

通过：

后期改善优化的地方

  1. reverse 是为了编程方便进行的处理，但是如果数字太大，速度肯定会受影响，这个时候就不要使用reverse了。
  2. 用链表来做可以简化代码，减少分析的，更加节省时间
  3. 处理移位的时候考虑几个问题

寻找发帖水王

题目

如果“水王”没有了，但有三个发帖很多的ID，发帖的数目都超过了帖子做数的1/4，又如何快速找出他们的ID。

算法分析 算法思想

从0-n扫描ID数组，记录3个数字的个数，如果出现第四个数字，就把三个数字的个数减少1，如果有一个数字的个数减少到0，那么把新来的数字作为原本三个数字之一进行记录。

如此一来，扫描完ID数组之后，剩下记录的3个数字的个数便是需要求的三个数字。

伪代码

分析时间复杂度O

数列的大小为N，记录数字的数组大小为3，每次判断记录数组count是否存在0，以及找到已存在的数字++，都会花费3个单位时间，因此其时间复杂度为

$$

O(3n) \approx O(n)

$$

源代码

测试结果

本测试数据采用Python自动生成。

后期改善优化的地方

  1. 对于N比较小的情况可以在内存中进行查找，但是一旦涉及到更大的数据，这个方法可能就没有那么简单了，不能在内部建立数组，需要一部分一部分的从磁盘中读数；
  2. 如果需要查找的id数量变多，那么需要的临时保存的数列可能更大；
  3. 这个实现没有使用STL中的map，如果使用map，还能进一步使得代码见解易懂，map使用hash来做内部实现，可以使得面对数据量更大的数据的时候，加快查找数据的速度。

山西煤老板

题目

你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车只能装1000吨煤，且能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板，你会怎么运送才能运最多的煤到集市？

算法分析 算法思想

从动态规划的角度求最优解：

假设起始运送货物量为t，终点路程为s，火车容量为c，可以运抵终点的最多货物量为函数 F(t, s)。

3种基本情况：

（1）t < s：货物量不足以运送到此距离，所以F(t, s) = 0;

（2）s < t < c：火车一次就可以装完货物，所以F(t, s) = t – s;

（3）2s < c 使得火车一次无法运完，但可以采用往返的方式多次运输，这种情况下最有的方式就是减少总共往返的次数，也就是直接运到终点而不在中间卸货，所以

$$

F(t, s) = (t / c – 1) * (c – 2s) + (c – s)

$$

可得递归式：

$$

F(t, s) = max{ F( F(t, i), s – i)} (1 <= i < s)

$$

分析了一下这个方程是有问题的，比如F(1750, 250)会计算出1125；

所以正确的结果应该对t/c进行处理，也就是说，起点剩余的燃料不足运输到终点，直接舍弃。第三阶段的方程式应该是

$$

F(t, s) = (t // c – 1) * (c – 2s) + (c – s) + (t % c – 2 s), if (t%c > 2s)

$$

伪代码

分析时间复杂度O

时间复杂度为

$$

O(3000*3000)

$$

因为每个数字都要计算一遍。

源代码

测试结果

后期改善优化的地方

  1. 去除了一下数据进行加速

  2. 保存f减少重复运算值

  3. 应该有更加简单的方法，类似这种，但是不好解释。

  1. $$
3y=1000\
 
5x=1000\
 
解得x+y=200+333=533，因此使得最后一辆火车抵达时节省了533吨煤\
 
$$

Facebook

题目

Given a list of words, L, that are all the same length, and a string, S, find the starting position of the substring of S that is concatenation of each word in L exactly once and without intervening characters. This substring will occur exactly once in S.

算法分析 算法思想

使用hashmap来保存word的hash值，来加快查找速度。（旧）

直接用hash函数求字符串的hash值，最后求得结果。

依据公式

$$

hash(w_1) + hash(w_2) = hash(w_2) + hash(w_1)

$$

伪代码

分析时间复杂度O

就是字符串长度

$$

O(lengthOfS)

$$

源代码

测试结果

测试数据生成意义不是很大，

后期改善优化的地方

  1. hash尽管在速度上非常优秀，但是在准确度方面，如果出现hash冲突，那么值可能不准确。此时可以利用hashmap来解决这个问题，不过会多出重置hashmap的相关时间。

For n -m – problems

Problemset

Assume we have a sequence that contains N numbers of type long. And we know for sure that among this sequence each number does occur exactly n times except for the one number that occurs exactly m times (0 < m < n). How do we find that number with O(N) operations and O(1) additional memory?

Algorithm

^ is the add operation without carry.

默认one,two都是0, 即任何数字都不存在

数字a第一次来的时候, one标记a存在, two不变

数字a第二次来的时候, one标记a不存在, two标记a存在

数字a第三次来的时候, one不变, two标记a不存在

构造这样一种运算，通过异或将数据保存在one和two里面。

Pseudocode

### Source code

“`python

!/usr/bin/env python

def solve(array):

one, two = 0, 0

for i in array:

one = (one ^ i) & ~two

two = (two ^ i) & ~one

return one, two

if name == ‘main‘:

array = input()

array = array.split(‘ ‘)

array = list(map(lambda x: int(x), array))

# print(array)

_, res = solve(array)

print(res)

“`

Test

Use python generate data to test.

Discussion and improve

如果n不是3，那么需要构造更多的临时变量。

很长的数组

题目

一个很长很长的short型数组A，将它分成m个长为L的子数组B1，B2，…，Bm，其中每个数组排序后都是递增的等差数列，求最大的L值。

$$

例如，A = {-1, 3, 6, 1, 8, 10} 可以分成B_1 = {-1, 1, 3}, B_2 = {6, 8, 10},; L = 3 即为所求。

$$

算法分析

首先进行排序，然后开始分三步走。

  1. 统计元素个数 O(n)

  2. 排序 O(nlog(n))

​

第一步用来枚举L和m的大小，由题目可知，L * m = 数组的长度。从m为1开始枚举，保证得到的L为最大值。

第二步搜索为深搜，确定当前子数组的起点和初始步长，使用pos记录当前数组选定的元素。

第三步枚举，根据起点给定的初始步长，开始枚举步长，如果枚举的步长可以在数组中找到足够的元素，即数字为L，那么记录这种分法，开始枚举下一个起点。如果枚举的步长和起点无法满足条件，回溯到上一个节点，把上一个节点记录的步长+1再一次搜索。当枚举的起点数达到m，即满足要求输出。

大白话来讲，就是从头开始分原始数组到m个数组中去，排序过后，在前面的每一个节点未被分配的元素，都是子数组起点。如果使用广度优先搜索，即每次都给一个子数组分配一个满足子数组步长要求的数，会导致在最后才发现分配的元素数不满足要求，从而浪费大量时间。

其中，深度优先搜索还有几个剪枝的技巧：

  1. 当前步长*(L-1)如果超过了数组的最大元素，可以不继续搜索

  2. 如果在给定步长的情况下， 下一个数字的大小超过之前的数字+步长，那么可以不必继续搜索。

因为数组已经排好序。

  1. 还有其他的剪枝技巧，体现在代码中了。

时间复杂度

n为数组长度，排序的时间为 O(nlogn)，枚举m时间为n，枚举step时间为65536【short跨度】，枚举全部元素时间为n，因此算法的时间上界为

$$

O(65536n^2)

$$

实际情况下，由于剪枝等操作的存在，应优于这个时间。

伪代码

源代码

测试

测试样例生成结果未必准确，找了部分的测试样例，可以通过修改代码中array来提现。

讨论

  1. 在记录了起点和步长，应该可以利用这两点推出当前使用了哪些元素，如果空间大小不够使用，可以不适用record记录，如果下一层不满足条件回溯的时候，可以利用起点和步长回推已经使用的元素。