Chapter 6 Array

  • sorting
  • binary search
  • two/three pointers

6.1 75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

https://leetcode.com/problems/sort-colors/

This is an application of Dutch national flag problem or three way partition.

procedure three-way-partition(A : array of values, mid : value):
    i ← 0, j ← 0, n ← size of A - 1
    while j ≤ n:
        if A[j] < mid:
            swap A[i] and A[j]
            i ← i + 1
            j ← j + 1
        else if A[j] > mid:
            swap A[j] and A[n]
            n ← n - 1
        else:
            j ← j + 1

or

三个指针,red,cur,还有blue. red代表指向0的,cur指向1,blue指向2.

https://en.wikipedia.org/wiki/Dutch_national_flag_problem
https://en.wikipedia.org/wiki/American_flag_sort

It is a quicksort variant.

Follow up:

http://www.1point3acres.com/bbs/thread-206999-1-1.html

lc sort color 要求swap次数最少.那个经典的国旗算法不work,不能保证swap最少,最优解是on时间o1space,我没给出最优解,给出了on时间onspace的.

Minimum swap of DNF

Minimum swap of DNF

Algorithm in the picture above:

  • Swap 2, 0 inwardly
  • Swap 1, 0 inwardly
  • Swap 2, 1 inwardly

T: \(O(N)\), S:\(O(1)\)

Check this paper

https://cs.stackexchange.com/questions/12560/use-minimum-number-of-swaps-so-each-bin-contains-balls-of-the-same-color

Ternary partitioning: http://www.sciencedirect.com/science/article/pii/S002001900900012X?via%3Dihub

6.2 Sort Colors II - Rainbow Sort

http://www.lintcode.com/en/problem/sort-colors-ii/

Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, … k.

Example: Given colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].

Challenge

A rather straight forward solution is a two-pass algorithm using counting sort. That will cost O(k) extra memory. Can you do it without using extra memory?

http://wdxtub.com/interview/14520606003957.html

Algo: A variant of counting sort.

这个算法其实还是counting sort,只不过在节约空间上花了点心思.一个array包含index和value两个信息,index是单调连续递增的从0到L-1,表示范围为L(array的长度). Counting Sort的本质是构建一个counter保存原数组信息,然后重构, 具体来说就是用index表示值(value),用value表示count. 这里利用本题的特点(value都是正,而且值是从1到k,不过有重复而已),对普通的counting sort进行了空间上的优化.局限性也很强:如果有负数是不行的

如果array里面有数字missing也是不行的.比如: [2,5,5,5,5,5,3,3] 最后会变成counter [x,-1,-2,x,-5,x,x,x] where x is placeholder.在用counter backwardly重构array的时候,会变成[x,3,3,5,5,5,5,5],因为-1在-2重构的时候被覆盖掉了!一个解决办法是探测到有覆盖的话,就换另一边重构.算法实现略.

Follow up:

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=209155

Dual Pivot: http://rerun.me/2013/06/13/quicksorting-3-way-and-dual-pivot/

6.3 442. Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?

Example:
Input: [4,3,2,7,8,2,3,1]
Output: [2,3]

https://leetcode.com/problems/find-all-duplicates-in-an-array/

6.4 280. Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]….

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

https://leetcode.com/problems/wiggle-sort/
https://segmentfault.com/a/1190000003783283

6.4.1 Algo 1: Sort and Swap Pair

T: \(O(NlogN)\)

如果把for loop里面的L换成n.size()会有runtime error.因为unsigned integer 0 minus 1 will be a huge number, instead of -1. So it is always safe to write int L=n.size().

i%2==0 is better than i&2==0(the latter need a parenthesis, should be (i&2)==0).

6.4.2 Algo 2: Swap in one Sweep

当index i为奇数的时候,该数应该大于它前面的数; 为偶数的时候,应该小于它前面的数. 这样循环一次把不符合规则的数调整好就行了.
T: \(O(N)\)

6.5 324. Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note: You may assume all input has valid answer.

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

https://leetcode.com/problems/wiggle-sort-ii

注意: nth_element并不是说前段的所有值都小于pivot,而是not greater than.
T: \(O(N)\)

This is an application of three way partition.
但是这个index re-wiring的技术才是关键:

  • Explanation

First I find a median using nth_element. That only guarantees O(n) average time complexity and I don’t know about space complexity. I might write this myself using O(n) time and O(1) space, but that’s not what I want to show here.

This post is about what comes after that. We can use a reverse three-way partitioning to arrange the numbers so that those larger than the median come first, then those equal to the median come next, and then those smaller than the median come last.

Ordinarily, you’d then use one more phase to bring the numbers to their final positions to reach the overall wiggle-property. But I don’t know a nice O(1) space way for this. Instead, I embed this right into the partitioning algorithm. That algorithm simply works with indexes 0 to n-1 as usual, but sneaky as I am, I rewire those indexes where I want the numbers to actually end up. The partitioning-algorithm doesn’t even know that I’m doing that, it just works like normal (it just uses A(x) instead of nums[x]).

Let’s say nums is [10,11,…,19]. Then after nth_element and ordinary partitioning, we might have this (15 is my median):

index: 0 1 2 3 4 5 6 7 8 9
number: 18 17 19 16 15 11 14 10 13 12

I rewire it so that the first spot has index 5, the second spot has index 0, etc, so that I might get this instead:

index: 5 0 6 1 7 2 8 3 9 4
number: 11 18 14 17 10 19 13 16 12 15

And 11 18 14 17 10 19 13 16 12 15 is perfectly wiggly. And the whole partitioning-to-wiggly-arrangement (everything after finding the median) only takes O(n) time and O(1) space.

If the above description is unclear, maybe this explicit listing helps:

Accessing A(0) actually accesses nums[1].
Accessing A(1) actually accesses nums[3].
Accessing A(2) actually accesses nums[5].
Accessing A(3) actually accesses nums[7].
Accessing A(4) actually accesses nums[9].
Accessing A(5) actually accesses nums[0].
Accessing A(6) actually accesses nums[2].
Accessing A(7) actually accesses nums[4].
Accessing A(8) actually accesses nums[6].
Accessing A(9) actually accesses nums[8].

注意: nth_element的空间复杂度没说,时间复杂度是平均O(N).

Refer:

6.6 283. Move Zeroes

Given an array nums, write a function to move all 0 to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

https://leetcode.com/problems/move-zeroes

  • Simplified version

这个题的简单版本是不需要维护非0数字的顺序,那么就可以这样写:

  • Algo - Two pointers

i指向第一个为0的点,k指向第一个非0的点. i在每次swap之后前进,k always moves forward.

初始化i=-1
当遇到0时,如果i还没有被初始化,就初始化i,如果i已经初始化了,就不用干事情(k++).
当遇到非0时,如果i还没初始化,就不用干事情,如果i已经初始化了,就swap,然后i,k同时加1.

上面的算法能得到正确答案但都不够高效,是挂掉面试的象征.

下面这样的解法可以pass. c表示非0元素的个数:

By using STL, you can finish it in one line:

Or

Followup: Minimize the total number of operations

问个问题 move zero leetcode 那题, how to minimize the number of overwrite ? 能提供下思路吗? 也是fb长考的 感谢

http://bit.ly/2wdvWbF, http://bit.ly/2wenXLr, http://bit.ly/2wdGpnq, http://bit.ly/2wdOhp0, http://bit.ly/2wdyRB9

计算每个非0元素num[i]之前0的个数,如果0的个数是1,num[i]往前挪一个位置就是了,如果是2,往前挪两个,以此类推.最后一个数挪完了就往剩下的位置里填0.因为是从前往后遍历,所以这样move不会覆盖数组里的非零元素.我认为这是move最少的了吧,因为每个元素都直接挪到目的位置….

这个是track目前为止非0元素的个数.同样也是得到最小overwrite的方法.

6.7 Reverse Words in a String

Given an input string, reverse the string word by word.

For example, Given s = “the sky is blue”, return “blue is sky the”.

https://leetcode.com/problems/reverse-words-in-a-string/

edge cases有: word之间多个空格,string首尾有space.

  • JAVA
  • Python

Follow up:

  • Using stack

  • “1,hello.world:you” ==> “you,world.hello:1”

stack + queue

6.10 189. Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

https://leetcode.com/problems/rotate-array/

The basic idea is that, for example, nums = [1,2,3,4,5,6,7] and k = 3, first we reverse [1,2,3,4], it becomes[4,3,2,1]; then we reverse[5,6,7], it becomes[7,6,5], finally we reverse the array as a whole, it becomes[4,3,2,1,7,6,5] —> [5,6,7,1,2,3,4].

Reverse is done by using two pointers, one point at the head and the other point at the tail, after switch these two, these two pointers move one position towards the middle.

[https://leetcode.com/problems/rotate-array/discuss/54252/Java-O(1)-space-solution-of-Rotate-Array].

6.11 798. Smallest Rotation with Highest Score

Given an array A, we may rotate it by a non-negative integer K so that the array becomes A[K], A[K+1], A{K+2], … A[A.length - 1], A[0], A[1], …, A[K-1]. Afterward, any entries that are less than or equal to their index are worth 1 point.

For example, if we have [2, 4, 1, 3, 0], and we rotate by K = 2, it becomes [1, 3, 0, 2, 4]. This is worth 3 points because 1 > 0 [no points], 3 > 1 [no points], 0 <= 2 [one point], 2 <= 3 [one point], 4 <= 4 [one point].

Over all possible rotations, return the rotation index K that corresponds to the highest score we could receive. If there are multiple answers, return the smallest such index K.

Example 1:
Input: [2, 3, 1, 4, 0]
Output: 3
Explanation:  
Scores for each K are listed below: 
K = 0,  A = [2,3,1,4,0],    score 1
K = 1,  A = [3,1,4,0,2],    score 3
K = 2,  A = [1,4,0,2,3],    score 3
K = 3,  A = [4,0,2,3,1],    score 4
K = 4,  A = [0,2,3,1,4],    score 3

So we should choose K = 3, which has the highest score.

https://leetcode.com/problems/smallest-rotation-with-highest-score

O(N) Sloution:

6.12 Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

6.13 80. Remove Duplicates from Sorted Array II

Follow up for “Remove Duplicates”: What if duplicates are allowed at most twice?

For example, Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

  • Two pointers

example: [1,1,1,1,1,2,2,2,3] return 5.

6.14 Disjoint Set and Union Find

Union Find use two arrays to store trees: one array stores boss’ index(called bo), another arry stores team size(called sz). Boss’s boss is big boss. The data structure is called disjoint set. It can be implemented with one or two arrays.

To find max team, use *max_element. To find number of teams, use count_if.

Refer to: CLRS(chp21), Sedgewick(P216)

6.16 Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

https://leetcode.com/problems/longest-consecutive-sequence/

  • Corner case

Input: [0,0,-1], Expected: 2.

Method 1:

Method 2:

既然要O(n)算法,排序显然不行,所以自然想到用hash table.将序列中的所有数存到一个unordered_set中.对于序列里任意一个数A[i],我们可以通过set马上能知道A[i]+1和A[i]-1是否也在序列中.如果在,继续找A[i]+2和A[i]-2,以此类推,直到将整个连续序列找到.为了避免在扫描到A[i]-1时再次重复搜索该序列,在从每次搜索的同时将搜索到的数从set中删除.直到set中为空时,所有连续序列搜索结束.

复杂度:由于每个数字只被插入set一次,并删除一次,所以算法是O(n)的.

http://bangbingsyb.blogspot.com/2014/11/leetcode-longest-consecutive-sequence.html

6.17 Number of Islands

https://leetcode.com/problems/number-of-islands/

Another way to make set:

  1. boss array is filled as all -1
  2. while to replace recursion

6.18 Prefix Tree(Trie)

PDF:

http://web.stanford.edu/class/cs166/lectures/15/Small15.pdf

Code:

https://github.com/s-yata/marisa-trie

http://marisa-trie.readthedocs.io/en/latest/tutorial.html#tutorial

Bitwise trie

  • binary trie/bit trie
[cling]$ struct btrie{bool isend; btrie* children[2];};
[cling]$ sizeof(btrie)
(unsigned long) 24
[cling]$ struct btrie2{int val; btrie* children[2];};
[cling]$ sizeof(btrie2)
(unsigned long) 24

http://www.geeksforgeeks.org/find-the-maximum-subarray-xor-in-a-given-array/
https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems

  • XFastTrie

  • YFastTrie

  • Hash trie

  • PATRICA trie

https://cw.fel.cvut.cz/wiki/_media/courses/a4m33pal/paska13trie.pdf
https://www.youtube.com/watch?v=AXjmTQ8LEoI
http://blog.csdn.net/jiutianhe/article/details/8076835

[cling]$ class trie_node{bool isend; trie_node* next[26];};
[cling]$ sizeof(trie_node)
(unsigned long) 216
[cling]$ class trie_node2{bool isend; map<char,trie_node2*> children;};
[cling]$ sizeof(trie_node2)
(unsigned long) 56
[cling]$ class trie_node3{bool isend; unordered_map<char,trie_node3*> children;};
[cling]$ sizeof(trie_node3)
(unsigned long) 64
[cling]$ class trie_node4{bool isend; unordered_map<wchar_t,trie_node4*> next;}; // for unicode
[cling]$ sizeof(trie_node4)
(unsigned long) 64

6.18.1 flat_map/flat_set

6.19 Interval Series

6.21 57. Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

https://leetcode.com/problems/insert-interval/

http://www.cnblogs.com/boring09/p/4244313.html

Think opposite and negate!

这道题考interval trichotomy(CLRS p348.). There are 3 cases, but 6 sub-cases, where 4 sub-cases are for overlapping.

Don’t make it unncesarily complex for the overlapping sub-cases. Just use one line code for the 4 sub-cases:

n.start = min(e.start,n.start), n.end=max(e.end,n.end);

//TODO - re-draw this graph

Another difficulty of this problem is to merge one with many.

  • Merge one to one => easy
  • Merge one to many => medium
  • Merge many to many => difficult

代码说明:
1. 已经循环到e,然后n在e的左边,所以n很可能已经(在处理e之前的元素的时候)被merge过了.
3. 假设n覆盖了所有原始的intervals,那么即使循环完了n也不会被merge,所以要特殊处理以下这种情况.

6.21.1 Total Covered Interval Length

参见: linkedin-2015-1

6.22 277. Find the Celebrity

https://leetcode.com/problems/find-the-celebrity/

http://www.geeksforgeeks.org/the-celebrity-problem/

Two pointers

一次know()调用一定可以移动一个值!

这道题本质是在一个矩阵寻找满足条件的行列.knows(i,j)其实可以看成一个矩阵M[i][j],取值是0或者1. 现在要在矩阵里面找如下模式:

模式是(除对角线外)整列M[*][k]是1并且整行M[k][*]是0. 用这个矩阵我们也可以很容易的证明(by contradiction)如果存在这样的celebrity,一定是唯一的.

既然是唯一的,所以找这个模式不用遍历整个矩阵,只要上三角矩阵就可以了.下面是找到备选k的过程(绿色):

找到之后再遍历整列M[*][k]和整行M[k][*]检查是否满足条件.从上图可以看出复杂度是\(O(N)\).

Facebook, Linkedin喜欢考这个题及变形.

另一种考法,是直接给出矩阵为参数的函数接口,让你完成:

这里我用两个for loop,是因为感觉cpu cache locality会使得这样更快.(不过没有测试.)

这个是用矩阵形式来考的面经:

6.22.1 变形

这个面经里面第一轮和celebrity问题一样.也是在矩阵里面找类似的pattern,这个pattern的0,1和上面的恰好倒过来了.M[i][j]==1表示第i个object大于第j个object.

代码大概类似下面:

其实这个题要简单点,Why? 因为a>b那么b必然小于a.所以这个问题的矩阵必然有对称关系(延对角线0,1相反的反值对称).

但是celebrity问题里面,a认识b,b就不一定认识a.所以celebrity问题里面的矩阵没有对称关系.

6.23 238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in \(O(n)\).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:

Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

https://leetcode.com/problems/product-of-array-except-self/

  1. coding 一中一印,(1) product with the element itself, 我先讲了不用除法的 方法, 然后是用除法的方法,需要考虑没有0,一个0和多于一个0的情况 (2) 判断一个 graph 是不是 bipartite, 我用了 BFS 的方法,起始结点标左边,然后相邻标右边, 再相邻标左边,如顺利标完则是 bipartite,发现冲突则不是..

6.23.1 Algo1

面试的时候no assumption. 如果让用除法的话,那这道题就应该属于Easy,因为可以先遍历一遍数组求出所有数字之积,然后:

如果没有0,除以对应位置的上的数字.
如果有一个0在index i,结果是其他所有值都是0,只有在index i的值等于其他元素的乘积.
如果有greater than or equal to两个0,那么结果都是0.

catch 1: 0 in vector
catch 2: int overflow

T:2 to 3 pass. O(N); S: No extra space.

6.23.2 Algo2

两次扫描,两个方向. Scan forward and backward to get forward and backward cumulative product.

因为是cumulative product,就要放seed.加法放0,乘法放1.

参见代码如下:

我们可以对上面的方法进行空间上的优化,由于最终的结果都是要乘到结果res中,所以我们可以不用单独的数组来保存乘积,而是直接累积到res中,我们先从前面遍历一遍,将乘积的累积存入res中,然后从后面开始遍历,用到一个临时变量right,初始化为1,然后每次不断累积,最终得到正确结果.

  • C++
  • Java

6.24 36. Valid Sudoku

https://leetcode.com/problems/valid-sudoku/

方法1: 依次检查每一行、每一列以及每一个九宫格的数字元素是否在1-9之间,并且是否没有重复.

方法2: 横竖方一共有27种需要验证1-9的独立性, 遍历一次填入这27个向量里, 如果已有则证明重复.

两种方法速度一样.

6.27 532. K-diff Pairs in an Array

https://leetcode.com/problems/k-diff-pairs-in-an-array/

Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

今天早上电面 打电话过来,直接在hackerrank上面给题目.
第一题: 给一个distinct int array,还有一个int k.找出里面difference是k的pair的数量.这个秒写好.
第二题:给一个input 是这样的形式 const char *c
(int)(A-G)(int)
例子1: 1A1
例子2:4D8
A-G代表的数字是 2,4,8,16,32,64…(后面自己@)
第一个int代表整数位
中间的字母代表分母
右边的int代表分子
然后就要求输出一个float
“2A1”就输出2.5 因为 2+(1/A) = 2+0.5 = 2.5
题目要求是不能用library的function 比如说什么string的function或者sstream.
两题20分钟结束了.然后要skype.结果他们那里skype坏了.于是就等到明天再继续
补充内容 (2016-4-5 21:33):
skype面已跪 问project 没准备好= =ggwp

http://www.1point3acres.com/bbs/thread-184199-1-1.html

6.29 88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

https://leetcode.com/problems/merge-sorted-array/

6.30 643. Maximum Average Subarray I

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

https://leetcode.com/problems/maximum-average-subarray-i

6.31 644. Maximum Average Subarray II

Given an array consisting of n integers, find the contiguous subarray whose length is greater than or equal to k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation:
when length is 5, maximum average value is 10.8,
when length is 6, maximum average value is 9.16667.
Thus return 12.75.

https://leetcode.com/problems/maximum-average-subarray-ii

T: \(O(NK)\)

这题的关键是如果max length-K average和max length-2K Average的关系.如果x,y是相邻两个length-K Average,那么相应的length-2K Average肯定介于二者之间(inclusive).如果求出了max length-K Average,那么length-2K及其以上的都不用求了.所以这题的复杂度可以从\(O(N^2)\)降到\(O(NK)\). 这个分析能力和直觉是解本题的关键.

用cumulative sum也是一个方法,但是更有可能overflow,而且这不是本题的关键.

6.32 633. Sum of Square Numbers

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c.

Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

这题必须用sqrt(c),否则过不了测试. 这个算法是\(O(N)\).

6.34 325. Maximum Size Subarray Sum Equals k

https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/

6.35 525. Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

https://leetcode.com/problems/contiguous-array

这题的\(O(N)\)解法非常巧妙. 把所有的0换成-1,然后用Maximum Size Subarray Sum Equals k的方法(2sum)解,这里的K就是0.

6.36 523. Continuous Subarray Sum

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:
Input: [23, 2, 4, 6, 7], k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:
Input: [23, 2, 6, 4, 7], k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42=6*7.

https://leetcode.com/problems/continuous-subarray-sum

http://www.cnblogs.com/grandyang/p/6504158.html

子序列和问题有很多变种,和为k倍数问题是其中一种,题目难度不大,可以用各种方式去做,只要注意k取0 的情况就行. 要求连续和满足一个倍数.

很容易证明: 若数字a和b分别除以数字c,若得到的余数相同,那么(a-b)必定能够整除c.根据这个可以\(O(N)\)解决本题.

Also, 求cumulative sum可以用partial_sum, 如下:

[cling]$ #include <henry.h>
[cling]$ vector<int> v={1,2,3,4};
[cling]$ partial_sum(v.begin(), v.end(), v.begin());
[cling]$ v
(std::vector<int> &) { 1, 3, 6, 10 }

本题还有两个麻烦的地方:
1, subarray长度必须大于等于2;
2, 如果k是0,会有edge case, logic会不一样.

6.37 410. Split Array Largest Sum

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied: 1 <= n <= 1000, 1 <= m <= min(50, n)

Examples:
Input:
nums = [7,2,5,10,8], m = 2
Output: 18

Explanation:
There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

https://leetcode.com/problems/split-array-largest-sum

http://www.cnblogs.com/grandyang/p/5933787.html

6.38 27. Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example: Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

https://leetcode.com/problems/remove-element

6.39 219. Contains Duplicate II

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

https://leetcode.com/problems/contains-duplicate-ii/

找vector里面长度为K+1的滚动数组里面是否有重复数字.

6.40 41. First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

https://leetcode.com/problems/first-missing-positive

这题说得不清楚,其实就是指从1开始的一些数本应连续,缺了一些,找第一个缺的数出来.

如果不是S: \(O(1)\) 的要求的话,用unordered_set解决. 但是要求O(1)就只能用swap的方法了.

Q: 请问,如果输入是[9,4,-1,1],那么9无对应的数组index,这种情况怎么处理?
A: 那9还是放在原地不动啊,跟-1的处理方式一样.最后全部调整结束之后是[1,4,-1,9],返回2.

Q: 如果数组中有重复元素,你这个解法就不对吧?
A: 正确的,有重复的元素,这些元素会被放到末尾.判断第一个出现下标和值不一值的就是要求的值.

下面写了两个解法,就是index的取值上面有点差异,核心算法是一样的.

6.41 370. Range Addition

Assume you have an array of length n initialized with all 0’s and are given k update operations.
Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex … endIndex] (startIndex and endIndex inclusive) with inc.
Return the modified array after all k operations were executed.
Example:
Given:

length = 5,
updates = [
    [1,  3,  2],
    [2,  4,  3],
    [0,  2, -2]
]

Output:

[-2, 0, 3, 5, 3]

Explanation:
Initial state:[ 0, 0, 0, 0, 0 ]
After applying operation [1, 3, 2]:[ 0, 2, 2, 2, 0 ]
After applying operation [2, 4, 3]:[ 0, 2, 5, 5, 3 ]
After applying operation [0, 2, -2]:[-2, 0, 3, 5, 3 ]

https://leetcode.com/problems/range-addition

在开头坐标startIndex位置加上inc,而在结束位置加1的地方加上-inc,那么根据题目中的例子,我们可以得到一个数组,nums = {-2, 2, 3, 2, -2, -3},然后我们发现对其做累加和就是我们要求的结果result = {-2, 0, 3, 5, 3}

6.42 598. Range Addition II

Given an m * n matrix M initialized with all 0’s and several update operations.
Operations are represented by a 2D array, and each operation is represented by an array with two positive integers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b.
You need to count and return the number of maximum integers in the matrix after performing all the operations.
Example:

Input: 
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation: 
Initially, M = 
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

After performing [2,2], M = 
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]

After performing [3,3], M = 
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]

So the maximum integer in M is 2, and there are four of it in M. So return 4.

https://leetcode.com/problems/range-addition-ii
http://bit.ly/2x2lstR

598. Range Addition II

598. Range Addition II

6.43 493. Reverse Pairs

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j]. You need to return the number of important reverse pairs in the given array.

Example1:
Input: [1,3,2,3,1]
Output: 2

Example2:
Input: [2,4,3,5,1]
Output: 3

Note:
The length of the given array will not exceed 50,000.
All the numbers in the input array are in the range of 32-bit integer.

https://leetcode.com/problems/reverse-pairs

这道题还有很多更好的解法,参考: http://bit.ly/2xb0p8F, http://bit.ly/2xbd8Ie

6.44 665. Non-decreasing Array

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.
We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:
Input: [4,2,3]
Output: True
Explanation: You could modify the first 4　to 1　to get a non-decreasing array.

Example 2:
Input: [4,2,1]
Output: False
Explanation: You can’t get a non-decreasing array by modify at most one element.

https://leetcode.com/problems/non-decreasing-array

Take 4,2,3 and 3,2,4 and 3,4,2,3 as examples.

http://bit.ly/2xop7CL

6.45 526. Beautiful Arrangement

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:

The number at the ith position is divisible by i. i is divisible by the number at the ith position.

Now given N, how many beautiful arrangements can you construct?

Example 1: Input: 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

https://leetcode.com/problems/beautiful-arrangement

这道题的本质其实是求全排列,然后在所有全排列中筛选出符合题意的排列 http://www.cnblogs.com/grandyang/p/6533276.html

6.46 667. Beautiful Arrangement II

Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n and obeys the following requirement: Suppose this list is [a1, a2, a3, … , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, … , |an-1 - an|] has exactly k distinct integers.

If there are multiple answers, print any of them.

Example 1:
Input: n = 3, k = 1
Output: [1, 2, 3]
Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.

Example 2:
Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.

https://leetcode.com/problems/beautiful-arrangement-ii/

The requirement of k distinct distance can be achieved from 1, 2, …, k+1 (<= n), by the following strategy:

1, k+1, 2, k, 3, k-1 ...
The distance of this sequence is k, k-1, k-2, ..., 2, 1

Then append the remaining numbers to the list.

http://bit.ly/2xoFZcf

6.47 448. Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:
Input: [4,3,2,7,8,2,3,1]
Output: [5,6]

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/　　 http://bit.ly/2waH3lJ

开始想用移动的方法,后来发现编码很麻烦．还是用swap方便.

6.48 565. Array Nesting

A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], … } subjected to the rule below.

Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right before a duplicate element occurs in S.

Example 1:

Input: A = [5,4,0,3,1,6,2]
Output: 6
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

Note:

N is an integer within the range [1, 20,000].
The elements of A are all distinct.
Each element of A is an integer within the range [0, N-1].

https://leetcode.com/problems/array-nesting/description/

6.49 775. Global and Local Inversions

We have some permutation A of [0, 1, …, N - 1], where N is the length of A.

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

Return true if and only if the number of global inversions is equal to the number of local inversions.

Example 1:
Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.

Example 2:
Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.

Note:

A will be a permutation of [0, 1, ..., A.length - 1].
A will have length in range [1, 5000].
The time limit for this problem has been reduced.

https://leetcode.com/contest/weekly-contest-69/problems/global-and-local-inversions/

6.50 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

https://leetcode.com/problems/maximum-subarray/

思路1:

用死记硬背的方法容易写出这样的代码:

是Two Pass. 因为里面有个edge case: 所有数都为负.

稍微调整下可以变成one pass, 直接得到最优解.

注意g = max(g,l);的位置特别重要.第一个例子在循环的最后一行,就要考虑全部数是负数的情况.

思路2:

当前和为sum,如果sum >0,那么加上当前元素,否则sum=A[i] (即抛弃负数的sum,重新开始.因为负数的sum是累赘- -好难听的样子)

仔细观察上面代码1,2两处,可以改写成:

这就是Kadane's algorithm(卡登算法) https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm

Recurrence Equation: dp[i] = max(dp[i-1] + A[i], A[i])
Boundary Condition: dp[0] = A[0]

注意
1. A[i]是负数的时候不能舍弃,只有当dp[i-1]是负数的时候,在计算中才能舍去.
2. 这个dp只是local max.不是最后答案,如果要最后答案,还要用一个g来跟踪.

6.50.1 Follow up

  1. 求相应的start和end的index.

http://www.1point3acres.com/bbs/thread-190773-1-1.html

这个分两种情况:

  1. 都是负数的时候,index就是最小数的index.
  2. 否则,起始点肯定在local maxsum重新开始的时候,终止点在最后一次g比l小的时候. 需要区分这两种情况:

(1.) --起始(ps)---终止(e)---起始(s)---终止(e)
(2.) --起始(ps)---终止(e)---起始(s)--

如果s比e大的话,结果是[ps,e],否则是[s,e]

一种可行的代码是:

  1. 输入是stream咋办?

http://www.mitbbs.com/article_t/JobHunting/33055923.html

C++有三种istream(分别是: 标准io,文件,内存字符串):

http://www.cplusplus.com/reference/istream/istream/

如果是stream的话就有delimiter来分隔token. 代码如下:

进一步的题目有:
http://www.lintcode.com/en/problem/maximum-subarray-ii/
http://www.lintcode.com/en/problem/maximum-subarray-iii/

解法参考: http://blog.hyoung.me/cn/2017/02/maximum-subarray/

6.51 Subarray Sum Closest

https://www.lintcode.com/en/problem/subarray-sum-closest/

Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.

Example
Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4].

https://goo.gl/RkNjeh

6.52 152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

https://leetcode.com/problems/maximum-product-subarray/

先贴个自己写的代码: 值的大小取决于负数的奇偶个数,还有遇到0就sink了.先把数组用0切分,然后对每段找负数的个数,是偶数的话就是全部数的乘积,如果是奇数的话,就从左右两边累积相乘到遇到最后一个负数为止,然后返回大的那个数. 这个算法是O(N)的.空间是O(N)但是很容易优化到O(1),不想折腾就没写.

DP Solution:

https://discuss.leetcode.com/topic/4417/possibly-simplest-solution-with-o-n-time-complexity

C version:

C++ version的最优解如下:

[2,3,-2,-4] => 48

i nums[i] mi mx r
0 2 2 2 2
1 3 3 6 6
2 -2 -12 -2 6
3 -4 -2 48 48

这题确切的标题应该是max subarray product,当subarry只有一个数字的时候,结果就是那个值本身.

这个算法也考虑到了0的情况,比如 [2,3,-2,-4,0,100] => 100

i nums[i] mi mx r
0 2 2 2 2
1 3 3 6 6
2 -2 -12 -2 6
3 -4 -2 48 48
4 0 0 0 48
5 100 0 100 48

This is very similar to the “max cumulative sum subarray” problem. here you keep 2 values: the max cumulative product UP TO current element starting from SOMEWHERE in the past, and the minimum cumuliative product UP TO current element . it would be easier to see the DP structure if we store these 2 values for each index, like maxProduct[i],minProduct[i] .

At each new element, u could either add the new element to the existing product, or start fresh the product from current index (wipe out previous results), hence the 2 Math.max() lines.

If we see a negative number, the “candidate” for max should instead become the previous min product, because a bigger number multiplied by negative becomes smaller, hence the swap()

How to find the min product subarray?

[2,3,-2,-4] => -12
[2,3,-2,-4,0,100] => -12

一样的方法,只是把上面的min值拿出来而已.

How to find the start and end index?

[2,3,-2,-4] => (0,3)
[2,3,-2,-4,0,100] => (5,5)

我试图用max subarray sum的解法是可以解出来的(0要做特殊处理),但是相当繁琐,在面试的时候不可能写对.这种用DP思想的题要track信息还比较难.简单的办法是用最开始那个idea把数组按照0分为几段来求.

二刷:(return INT_MIN if nums is empty)

struct Solution {
    int maxProduct(vector<int>& nums) {
        int r=INT_MIN, mx=1, mi=1;
        for(int i=0;i<nums.size();++i){
            if(nums[i]<0) swap(mx,mi);
            mx=max(mx*nums[i], nums[i]);
            mi=min(mi*nums[i], nums[i]);
            r = max(mx,r);
        }
        return r;
    }
};

6.53 325. Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Note: The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

https://leetcode.com/problems/maximum-size-subarray-sum-equals-k http://www.cnblogs.com/grandyang/p/5336668.html

这道题只要往cumulative sum方向想就对了,自然会想到用2sum的方法做．

注意找set的最后一个元素要用*rbegin()而不是back().不过这种API名字记忆问题面试的时候不会担心,用back也不会丢分.
上面的解法存了所有的index但是没有利用起来,我们只用到最后一个.所以可以做如下优化.

再优化一下, 像2sum一样, build map on the fly:

6.54 209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum >= s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.

https://leetcode.com/problems/minimum-size-subarray-sum/

Two Pointers: 这道题给定了我们一个数字,让我们求子数组之和大于等于给定值的最小长度,跟之前那道 Maximum Subarray 最大子数组有些类似,并且题目中要求我们实现O(n)和O(nlgn)两种解法,那么我们先来看\(O(n)\)的解法,我们需要定义两个指针left和right,分别记录子数组的左右的边界位置,然后我们让right向右移,直到子数组和大于等于给定值或者right达到数组末尾,此时我们更新最短距离,并且将left像右移一位,然后再sum中减去移去的值,然后重复上面的步骤,直到right到达末尾,且left到达临界位置,即要么到达边界,要么再往右移动,和就会小于给定值.

  • C++
  • Java

讨论:本题有一个很好的Follow up,就是去掉所有数字是正数的限制条件,而去掉这个条件会使得累加数组不一定会是递增的了,那么就不能使用二分法,同时双指针的方法也会失效,只能另辟蹊径了.其实博主觉得同时应该去掉大于s的条件,只保留sum=s这个要求,因为这样我们可以再建立累加数组后用2sum的思路,快速查找s-sum是否存在,如果有了大于的条件,还得继续遍历所有大于s-sum的值,效率提高不了多少.

6.55 228. Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.

Example 1:

Input: [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]

Example 2:

Input: [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]

https://leetcode.com/problems/summary-ranges/

2017(4-6月) 码农类 硕士 - 内推 - 技术电面 |Otherfresh grad应届毕业生 发个Indeed 电面, 新鲜出炉,开始先问了一下简历以及经历,最擅长的领域,最熟悉什么数据结构,回答HashTable, 然后问了实现方式,以及不同实现方式的差别,实用范围等等.15分钟后开始做题,还是老题summary range, 用了stringbuilder, 遍历一遍,o(n)时间复杂度. 然后问,如果输入为[1,2,3,4,5,…….100000, 300000] 这种情况怎么办,有没有更好的方式,回答binary search,然后将核心部分写了一下,并且告诉了他这种方式的最坏情况和最好情况. 希望能给个onsite

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=282676