随笔(5)—谈谈binary search

binary search是面试中非常经常被问到的一个题。应该这么说binary search是一个比较简单的算法，但是变形很多，很容易掉到陷阱里面出不来。

废话不说，先看两个题:

这个题应该首先向面试官提问有没有重复

这是我去年面试morgan stanley中遇到的一个题目。诚然对于搜索，最次最次有 $O(n)$ 复杂度的算法，但一般我们都希望能找到复杂度为$O(logn)$的算法。这个题tricky的点在于他做了一次rotate，如果没有这个rotate，对于一个sorted的数列，直接无脑使用binary search就行了。可是它翻转了，我们应该怎么做呢？

一个自然的想法是如果我们能找到pivot point，那么在pivot point左右两边序列都是sorted的，那么我们在两边分别使用binary search就行了，问题是find_pivot这个算法不能太复杂，最好复杂度也是 $O(logn)$ ，否则这个改进就没有意义了。下面我们看下答案：

 int binary_search(vector<int>& nums,int target,int l,int r){
    int mid=(l+r)/2;
    if(l>r)
        return -1;
    if(nums[mid]==target)
        return mid;
    else if(nums[mid]>target)
        return binary_search(nums,target,l,mid-1);
    else
        return binary_search(nums,target,mid+1,r);
}

int find_pivot(vector<int>& nums){
    int l=0;

    int r=nums.size()-1;
    int mid;

    if(nums[0]<nums[nums.size()-1])
        return 0;

    while(l<r){
        mid=(l+r)/2;
        if(nums[mid]>=nums[0]){
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    return l;
}

int search(vector<int>& nums, int target) {
    if(nums.size()==0)
        return -1;


    int pivot=this->find_pivot(nums);
    int idx1=this->binary_search(nums,target,0,pivot);
    int idx2=this->binary_search(nums,target,pivot,nums.size()-1);
    if(idx1==-1 && idx2==-1)
        return -1;

    if(idx1 !=-1){
        return idx1;
    }

    if(idx2 !=-1){
        return idx2;
    }

    return -1;

}

基本就是按照我们的思路写下来的，难点是如何写binary search.一般来讲binary search 由三个部分构成：

定义中间点mid
定义左起点和右起点 l和r，以及更新方式，一般地l或者r都要个加一或者减一
定义终止循环条件，一般有两种 while(l<r),第二种是while(l<=r), 另一种是while(l<r),具体选择使用那一种主要看l==r这个条件我们是不是要退出，如果要，就将条件设置成l<r。同时要注意，最后返回的时候注意l=mid+1，最后返回l就行。

另外有一点要说明的是，binary_search一般有两种实现方式，一种是使用循环，另一种是使用递归。我们一般都选择使用循环来实现，因为递归实在是too subtle了。当然，如果是vallina形式的binary search可以选择使用递归。

这里要说明的是这样一行代码if(nums[mid]>=nums[0])。请注意，这里是大于等于不是大于。这里我也没有想明白为什么。事实上，关于这些边界问题，我真的没有统一答案，只能一个一个试错了。

随笔(3)–Leetcode 53

废话不说，直接看题目

这个题目属于非常常见的一类，这是因为在实际中我们要求连续最大盈利。当然，这种题也是有暴力解法的，就是任选两个数字，计算 $\Sigma_{k=i}^{j}A[k]$ ,然后在得出最大值就可以了，这样做的复杂度是 $O(n^2)$ 。既然这样，我们不禁要问，能不能扫描一次就得出结果呢?

对于一个index i,我们定义 $S[i]=\Sigma_{k=}^{i}A[i]$ ，就是前i项的和，那么对于每个i，S[i]是固定的，接下来我们需要确定起点j从而最大化 $\Sigma_{k=j}^{i}A[k]$ ,也就是说，如果我们最小化S[j]，那么S[i]-S[j]就是以i为终点的max subarray sum。我们遍历i取出最大值就可以了。代码如下：

注意这里有一个陷阱，两个if条件是不能颠倒的，这里contagious的定义是至少要选一个元素，不能一个都不选，如果两个if条件颠倒了，出现[-1,-1,-1]这种数列，结果会输出零，这是不对的，需要注意

随笔(2)–Leetcode 121

老规矩，废话不说，先看题目吧

简单来讲，给你一个股票序列，交易规则是只能购买一次(先买后卖)，求你能获得的最大利润。明眼人看得出来就是找到这个序列的一个波峰和一个波谷，然后再相减。其实这个模型在实际中有很多应用，比如说求解maxmium drawdown.所以是很有可能被问到的。

先说一个最直观的解法，复杂度 $O(n^2)$ ，就是任意选一个序列的两个点，遍历所有的可能，然后选择出最大值。但是我们希望一遍扫描后就能获得结果，那么这就需要思考一下。

一个直觉的想法是，一个序列有很多波峰(局部最大值)和波谷(局部最小值)，一个成功的交易策略一定是在一个局部最小值开仓，在一个局部最大值平仓。但是由于我们只能先买后卖，所以波谷要出现在波峰前面。那么我们可以定一个min_price，它会动态的记录所有的局部最小值。然后我们定义一个max_profit,它会反复更新每一个在最小值处开仓的当前最大利润，遍历完后即为全局最大利润。代码如下

class Solution: def maxProfit(self, prices: List[int]) -> int: max_profit=0

    min_price=10000000
    for i in range(len(prices)):
        if prices[i]<min_price:
            min_price=prices[i]

        if (prices[i]-min_price)>max_profit:
            max_profit=prices[i]-min_price


    return max_profit

随笔(1)—Leetcode 76

废话不说，直接看题:

题目非常简单，给定一个distinct的列表，求它的power set。

先说一些题外话，这个函数实际上应用非常广，比如在machine learning中，如果我们需要做feature selection，就是从feature universe里面选出一个子集来提高validation set的准确率，我们就需要这个函数生成feature power set。当然这样做的复杂度比较高，是 $O( 2^{N})$ 。当然也可以选择forward selection，这样可以把复杂度降低到 $O(N^2)$ 。

所以我翻看了一下我的ML的课堂笔记，看看老师是怎么实现这个函数的:

def subsets(features): if len(features) == 0: return [] cs = subsets(features[1:]) return [[features[0],]] + [[features[0],]+ c for c in cs]+ cs

哈哈，乍一看根本不知道写的是个啥，不急，我们先来对python的基本语法做一些说明：

list的相加：python的语法里面是可以进行list的加法运算的，其效果就是把两个list的元素合并为一个list. e.g: [3]+[5]=[3,5]; []+[3]=[3]; ~~3+[5]=error!~~

所以直观上来看这个函数显而易见，首先cs求出这个列表第2至n项所生成的power set，再把第一个元素加上就行了，[[features[0]]]表示第一个元素生成的subset，[[features[0],]+ c for c in cs]表示第一个元素与cs合并生成的子集，cs表示剔除第一个元素后，别的元素生成的子集。

但是上面的代码有一点问题，他忽略的空集，修改后的代码如下所示：

def subsets(features): if len(features) == 0: return [[]] cs = subsets(features[1:]) return [[features[0]]+ c for c in cs]+ cs

当然上面那个代码也是有实际意义的，因为在machine learning中我们是不会对空集进行测试的。

先提纲挈领的说一下，这种题目在面试中经常考，与之相关的有排列，组合等问题，他们自身的复杂度本身就是指数级别的，所以不能从时间复杂度上进行优化，一般出这种题目是考察你的算法能力。解决这种题递归(recursion)和回溯(backtracking)是最常用的方法。下面对一些变形进行一些说明

2.上面题目不变，请选择出长度为k的子集(Two sigma onsite)

这个题是一道典型的组合问题，组合问题一般地解法就是回溯法(backtrack)。废话不说，先看答案

def subsets(nums): def backtrack(first = 0, curr = []): # if the combination is done if len(curr) == k: output.append(curr[:]) for i in range(first, n): # add nums[i] into the current combination curr.append(nums[i]) # use next integers to complete the combination backtrack(i + 1, curr) # backtrack curr.pop()

output = [] n = len(nums) for m in range(k,k + 1): backtrack() return output

回溯法的基本做法就是一个递归函数，一个判断是否为可行解，在这里可行解的判断条件是长度是否为k.实话说，递归函数看的人眼花缭乱，这里我们的做法就是从全局来看，比方说

if len(curr) == k: output.append(curr[:])

这个代码就是判断解是否满足条件，如果满足条件就把他放到最终的解空间里面。

for i in range(first, n): # add nums[i] into the current combination curr.append(nums[i]) # use next integers to complete the combination backtrack(i + 1, curr) # backtrack curr.pop()

这个是回溯函数的主体，第一行curr.append(nums[i])是把一个新元素放到列表里面，backtrack(i + 1, curr)是把从第i+1个到最后一个元素与第一个元素结合生成的所有可行解，curr.pop()将第一个元素剔除，然后进入下一个循环(因为以第一个元素构成的排列已经枚举完了)

3.排列问题(Permutation)

Given a list composed of distinct integers, generate its all permutations.

这个题使用递归就可以完美解决，下面先看答案

def permute(nums):
  
if len(nums) == 1:
        return [nums]

    result = []
    for i in range(len(nums)):
        nums[0], nums[i] = nums[i], nums[0]
        B = self.permute(nums[1:])
        result = result+[ele+[nums[0]] for ele in B]

    return result

本质和组合一样，也是使用递归。唯一的区别是因为排列是有顺序的，所以第一个元素可以由很多元素来担当，所以这个循环很关键，来让所有元素都当首元素。