LeetCode 47. Permutations II

用回溯法完成,跟普通排列问题不同的是,需要排除掉一些重复“路径”。

可以这样做,先把输入数组排个序,这样重复的数就在相邻位置了。随后在回溯探求的过程中,我们要保证相同值的两个数nums[i], nums[j],如果i<j,那遍历只能有一种次序:nums[i]先,nums[j]后。

换句话说,就是判断这种情况是需要提前终止的:两个数nums[i]==nums[j] && i<j,但是nums[i]还没有被遍历。所以找个东西记录一下访问就行了。

时间复杂度是O(N!),空间复杂度是O(N)

 

LeetCode 368. Largest Divisible Subset

思路:

想到一个词叫“传递性”,在这边应该也适用。就是如果b%a==0,然后c%b==0,那么肯定有c%a==0. 按照这个方法来构造一个集合就可以了,应该是动态规划的思想,results[i]保存包含数组元素nums[i]的最佳集合,构建集合的时候,首先从之前的results[j] (j=0…i-1)里面找到能够“传递”过来的集合(nums[i]%nums[i]==0)选作最佳(相当于找到c%b==0,当然这里的b是之前results[j]里面的最大元素,即nums[j])然后加上本身的nums[i]就构成了到第i个元素为止的最佳集合,如此继续…

时间复杂度应该是O(n^2)

 

LeetCode 424. Longest Repeating Character Replacement

思路很重要。

给定一个长度n的字符串s和限制k,将s中的部分字符替换(替换次数<=k)后,能得到连续字符(如AAAA)的长度最大为多少?

使用滑动窗口的思路可以在O(n)时间复杂度的情况下解决这个问题。需要记录当前窗口内各个字符的计数值(可以看做分布情况)以及当前窗口的起始点,窗口内最多字符的计数best。我们知道,最多字符的计数best+修改数量k如果还是不能使得当前窗口内的字符都统一的话,就得把窗口缩小(起始点后挪)。窗口缩小时记得把窗口计数更新一下。

这里有一个tricky的地方,best值本来在滑动窗口的时候是要更新的,因为可能窗口过了这个best会变小。但是由于我们要找的只是个最优的值,所以这个情况并不需要考虑对best进行更新,反正它也成不了最优。

代码

 

LeetCode 295. Find Median from Data Stream

题目大意是给定一个int数据流,判断当前整个数组的中位数值。由于数据流是可以不断增加的,因此采用两个堆(最大堆*1+最小堆*1)来实现。

这东西思路网上都有,每次新进一个数,维护堆就行了。维护一次的复杂度是O(logN),对应整个数组的复杂度是O(N logN)

STL 堆相关的三个函数 make_heap(), push_heap(), pop_heap()

STL是个好东西,在<algorithm>库里面就有三个与堆有关的函数,利用vector存储堆元素就可以调用这些函数来建立、更新堆。

make_heap(first, last, comp)是建立堆的函数,输入的first, last对应begin()和end()的iterator,comp函数可选,与库中sort()用到的方法相同,自定义的时候比较两个元素x, y的偏序关系,返回true说明x应该排在前面。相关的有两个仿函数叫less<T>() 和greater<T>(),直接用来比较<和>关系的。

push_heap(first, last, comp)使用时,将新元素放在数组末尾(代表堆的末叶节点),然后调用这个函数更新堆,是一个sift-up的过程。

pop_heap(first, last, comp)会将堆顶元素调整到数组末尾用于pop,同时调整更新堆。

代码

 

LeetCode 51. N-Queens

八皇后问题的延伸版,回溯实现。

 

LeetCode 220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

思路

基本思路是,假设当前运行到nums[i]的位置,则需要往前看k个数,并且找到其中任意一个数x满足 nums[i]-t <= x <=nums[i]+t。可以利用一个大小为k的二叉搜索树解决搜索范围的问题(问题就转变为:找到第一个>=nums[i]-t的数,判断他是否<=nums[i]+t)。整个算法的时间复杂度是O(N * logk),N为数组长度。
下面代码中用set实现,set是用红黑树实现的。

代码


 

LeetCode 223. Rectangle Area

题目

题目大意是给定两个长方形的坐标,计算他们一起覆盖的面积。

总的思路很简单,Area_A + Area_B – Overlap,具体求重合的面积则需要计算重合区域的两个坐标点。

那么就要分情况讨论,以重合区左下角点的横坐标为例,需要判断点E与横坐标AC的位置关系,即三种:E<A; A<E<C; C<E。

代码

 

 

LeetCode 40. Combination Sum II

思路

递归?呵呵

需要判断两个解是否相等,目前没有什么好办法,从boost库里抄了个hash函数过来。

代码

 

LeetCode 78. Subsets

思路

换个方法想问题。

有n个数,每个数是否作为输出用0/1状态来表示,比如[1,2,3]全出现就是(1,1,1) => 7,那n个元素的子数组的生成就是以下过程:[0, 2^n)里的每个数i,看这个数i里第[0,n)位是否为1,若为1则表示nums[i]被选中了,否则不选。

比如[1,2,3]的所有子集:

代码

 

LeetCode 93. Restore IP Addresses

思路

回溯(backtracing),用s的起始位置pos表示当前的状态(pos之前的已经处理完)。那么就依次尝试1~3位的字符看看是否符合要求,符合就把结果更新到buffer里,未完成就递归继续,然后递归返回的时候记得把buffer恢复到之前的状态。

按照题目的意思,应该不允许IP地址有前导0,即01.01.01.01这种状态.

对了,stoi函数很好用,应该是C++11新加的。

代码