leetcode 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.

题意:一个数组,由0,1,2组成,现在要求升序排列

思路:无脑做法就是计数排序,扫两遍,时间复杂度O(n),空间复杂度O(1)

如果只扫一遍呢?

一个容易想到的思路是两个指针:

需要注意 的是,交换2后要再次遍历到当前位置,或者说,只有当不交换2的时候,才执行cur++

 

 

 

还有一个神奇的思路:r,w,b分别表示下一个对应颜色要放的位置。

如果当前是0,那么0,1,2都要后移一个。

如果当前是1,那么1,2的位置需要后移。

如果当前是2,那么2的位置需要后移。

 

leetcode 11. Container With Most Water (two pointer)

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

题意:n条竖直的线段 (i,0)->(i,a[i]),从中选2条,和x轴共同组成一个开口的容器,问容器的最大面积。

思路:一开始想错了,以为是最大连续矩形面积…还在想leetcode竟然考单调栈???

然而实际上只取两个线段,中间的线段有没有,长度,都是无所谓的。

因此two pointer就好了。。。

 

leetcode 16. 3Sum Closest (k-sum问题,two pointer)

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

思路: 排序,然后two pointer,复杂度 O(n^2)

 

leetcode 18. 4Sum (k-sum问题,two pointer)

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

思路: O(n^2)枚举两个元素,变成2-sum问题,总体复杂度O(n^3)

hash的解法以后补

 

leetcode 15. 3Sum (k-sum问题,two pointer)

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

 

思路:排序O(nlgn),然后枚举一个元素O(n),对于每个元素,在剩下的区间中 two pointer O(n)

整体复杂度 O(n^2)。

hash的解法以后补。