微软笔试算法（一）
最近求职中接到的好多外包公司的电话，一般我都是拒绝的，其中告知外包到微软的就有三家，有一家说是微软小冰项目，给了我八道算法题，都不是太难，有的在LeetCode上还做过，在这里记录一下，正好也整理下LeetCode上刷过的题。
这里记录的算法是只用python实现，也是我目前能想到的最优解，一共八个问题。
- 完成一个函数：def Add(num1, num2):其中，两个输入都是数字，都是字符串（如：“12345678986543210123456789”），要求计算两个数字的和，返回一个字符串，不能使用内置函数，如int，long等。例如，输入两个数字是：“1000000000000000”和“-1”，返回“999999999999999”。
这个问题比较简单了，主要就是三个小问题：
- 字符串和数字的互转
- 加法的进位
- 减法的借位
字符串和数字的互转不让用int函数，这个简单，python只要写个字典就解决了，C的话就要写switch case来一个一个比较了。这里就解决了字符转数字的问题了。
到的数字开始计算，因为要设计借位和进位，答案会有四种情况
- 正数 + 正数 = 正数 2 + 3 = 5
- 负数 + 负数 = 负数 -2 + -3 = -5
- 大正数 + 负数 = 正数 -2 + 3 = 1
- 正数 + 大负数 = 负数 2 + -3 = -1
貌似就是这样，但是观察结果除了负号就是两种，所以程序一开始应该先分析负号，进位的情况有1,2，借位情况是3,4，正好这两个结果除了负号答案一样，所以分两类就OK
# 问题 1
def question1_add(num1, num2):
# 创建个字典用来把字符转为int便于计算
def strtoint(str):
numdict = {"0": 0, "1": 1, "2": 2, "3": 3, "4": 4, "5": 5, "6": 6, "7": 7, "8": 8, "9": 9}
return numdict.get(str)
# 把列表中的数字转会字符串
def inttostr(lt):
ls2 = [str(i) for i in lt]
return ''.join(ls2)
lt, x, y = [], [], []
# 两个数是否为负数的标记
minusflag1, minusflag2 = 0, 0
# 首先先提取出负号，记录负号的情况
if num1[0] is "-":
x = list(map(strtoint, num1[1:]))
minusflag1 = 1
else:
x = list(map(strtoint, num1))
if num2[0] is "-":
y = list(map(strtoint, num2[1:]))
minusflag2 = 1
else:
y = list(map(strtoint, num2))
# 把 x作为最长的那列，y是短的那列
if len(x) < len(y):
x, y = y, x
maxlen, minlen = len(x), len(y)
# 在短的那列前面插上0让两列一样齐以便于计算
for i in range(maxlen-minlen):
y.insert(0, 0)
# 计算通常是从最低位开始，所以i从最低位开始
# carry记录借位和进位情况
i, carry = 0, 0
# 两个数都是正数或负数
if (minusflag1 == 0 and minusflag2 == 0) or (minusflag1 == 1 and minusflag2 == 1):
# +1是为了防止最高位有进位的情况，给最高位加一个0
for j in range(maxlen+1):
i -= 1
if j < maxlen:
sum = x[i] + y[i] + carry
else:
sum = carry
# 两个数相加大于十代表有进位， 把结果和10的商给新列表，余给进位标志
if sum >= 10:
lt.insert(0, sum%10)
carry = sum//10
else:
lt.insert(0, sum)
carry = 0
# 如果最高位没有进位 把0删除
if lt[0] == 0:
lt.pop(0)
# 如果都为负数 加 -
if minusflag1 == 1 and minusflag2 == 1:
lt.insert(0, "-")
return inttostr(lt)
else:
return inttostr(lt)
# 一正一负
if (minusflag1 == 1 and minusflag2 == 0) or (minusflag1 == 0 and minusflag2 == 1):
for j in range(maxlen):
i -= 1
sum = x[i] - y[i] + carry
if sum < 0:
lt.insert(0, sum%10)
carry = sum//10
else:
lt.insert(0, sum)
carry = 0
while lt[0] == 0:
lt.pop(0)
if len(lt) == 1:
break
# 判断是否应该加 - 号
if (num1[0] is "-" and len(num1[1:]) > len(num2)) or num2[0] is "-" and len(num2[1:]) > len(num1) :
lt.insert(0, "-")
return inttostr(lt)
return inttostr(lt)
- 给定一个数组nums，然后对其排序，使得排序结果满足nums[0] < nums[1] > nums[2] < nums[3]…。 例如给定数组nums=[1,2,3,4,5,6,7,8,9],其中一个满足条件的结果是1<6>2<7>3<8>4<9>5.给出一个结果即可（可能无解）。最优解法是O(n)时间复杂度和O(1)空间复杂度。
原题位置：https://leetcode.com/problems/wiggle-sort-ii/
这道题就比较有趣了，LeetCode上大神给出的算法挺多，但是最优解不是O(n)，用python实现的话还能比O(n)小。
先说我看到题第一眼的想法和看了LeetCode上大神的方法吧，很简单就三行
nums.sort()
median = len2] - 1
nums[::2], nums[1::2] = nums[median::-1], nums[:median:-1]
首先排序，找到中位数，然后把中位数左右两边的交叉相排就OK了。
好吧，详细一点吧，S代表比中位数小的，L代表比中位数大的，M代表中位数
Small half: M . S . S . S Small half: M . S . S . S .
Large half: . L . L . M . Large half: . L . L . L . M
-------------------------- --------------------------
Together: M L S L S M S Together: M L S L S L S M
根据这个原理还可以写成其他形式
nums.sort()
median = len2]
nums[1::2], nums[::2] = nums[median:],nums[:median]
这个方式简单但是不满足O(n)时间复杂度的要求，这个方法是LeetCode上大神想出的叫virtual indexing，地址https://leetcode.com/problems/wiggle-sort-ii/discuss/77677/O(n)+O(1)-after-median-Virtual-Indexing,我就是照着用python抄袭了一遍o(￣︶￣)o，顺便说下我写的这个稍有区别，时间复杂度比O(n)小一点。
解释一下site()函数的作用
为了防止median的元素挨在一起，也就是说奇数位置上的值是median，同时与他相邻的某个偶数位置上的值也是median导致排序失败
为了避免这个问题，可以采用一种方法，即另j 每次移动两步，也就是说先另j直线奇数位置，再另j指向偶数位置，所以对于大小为10的序列，j的变化可能像是这样
1 -> 3 -> 5 -> 7 -> 9 -> 0 -> 2 -> 4 -> 6 -> 8
暂且先不考虑怎么实现这样的改变，先说一下这样做带来的好处
由上面j的变化可知，j的改变是每次移动两步，所以，根据算法描述。所有和median相等的元素一定是最后才固定位置，又因为当j指向的值等于median时，是不与i和k指向的任何一个元素交换的。所以，每次移动两步带来的结果是这些median永远不可能相邻。换句话说就是永远不会出现两个median挨着的情况
def question2_sort2(nums):
def site(n):
return (1 + 2 * n) % (len(nums) | 1)
nums.sort()
if len(nums) % 2 == 0:
median = (nums[len(nums) // 2] + nums[len(nums) // 2 - 1]) / 2
else:
median = nums[len(nums) // 2]
i, j, k = 0, 0, len(nums) - 1
while j <= k:
if nums[site(j)] > median:
nums[site(i)], nums[site(j)] = nums[site(j)], nums[site(i)]
i += 1
j += 1
elif nums[site(j)] < median:
nums[site(j)], nums[site(k)] = nums[site(k)], nums[site(j)]
k -= 1
j += 1 # 没错就是这里，我认为执行过交换后j就在正确的位置上了，所以我让j+1结果就是循环次数减少了，如果进行j+1则会循环N次，两种的结果不同但都复合条件
else:
j += 1
return nums
- 写一个函数，输入是两个int数组A和B。要求从A和B中分别取出一个数，使他们的和为20。打印出所有的组合。要求数字在数组中的位置和数字本身。比如输入为 A = [18, 2, 7, 8, 3], B = [17, 1, 19]，输出为 3 (A4) + 17 (B0) = 20，表示A的第4个元素是3，B的第0个元素是17
这就是道送分题了，嵌套循环就OK了，没什么好说的。
def question3_take(a, b):
for i in range(len(a)):
for j in range(len(b)):
if a[i] + b[j] == 20:
print("%d (A%d) + %d (B%d) = 20" % (a[i], i, b[j], j))
return
print(" No solution!")
- 写一个函数，输入一个随机的01序列，打印出这个序列中最长的01交替出现的序列的起始位置和结束位置。例如：输入“000101010101101”，输出起始位置2, 结束位置10
这题让我纠结了下，因为需要记录的位置有点多
因为我们要遍历这个序列中所有的01所以要两个指针同时移动才能确保01的出现，当出现01我们计数器n +1，然后判断是否到结尾或者下一个不是01的情况，我们就结束这段，记录这段的长度和结束开始的位置，如果下一段出现的01长我们就替换掉上次的记录。
值得注意的是01可能出现在序列的奇数或偶数位上，所以要遍历两次，再比较奇偶上哪个长，返回长的那段。
def func(i, j, num):
start, end, n, count = 0, 0, 0, 0
while j < len(num):
if num[i] is '0' and num[j] is '1':
n += 1
if j+1 >= len(num) - 1 or num[i+2] is '1' or num[j+2] is '0':
if n > count:
count = n
n = 0
end = j + 1
start = end - count*2
i += 2
j += 2
return start, end
def question4(num):
i, j = 0, 1
start1, end1 = func(i, j, num)
i, j = 1, 2
start2, end2 = func(i, j, num)
if end1 - start1 > end2- start2:
return start1, end1
else:
return start2, end2