重要提示：该博客不再更新！最新文章请参考LeetCode系列！
为了更好地巩固算法知识，打下扎实的计算机基础。。。好吧，实在编不下去了。。。其实是闲着没事儿做，不如动动脑，刷刷题，被虐一虐。以前零零散散也刷了一些，这次我准备按专题来刷，更有针对性一些。下面将会出现一些部分专题的刷题感悟，没事儿您就看看呗，哈哈哈！
1.Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
解答：
public class Solution {
//success 1
//sort方法，很trick，对于任何数组来说，如果存在majority element，sort后一定在length/2处。
// public int majorityElement(int[] nums) {
// Arrays.sort(nums);
// int length = nums.length;
// return nums[length/2];
// }
//success 2
//利用hashMap
// public int majorityElement(int[] nums) {
// int length = nums.length;
// HashMap<Integer,Integer> map = new HashMap<>();
// for (int num:
// nums) {
// if(!map.containsKey(num)){
// map.put(num,1);
// }else{
// int value = map.get(num)+1;
// map.put(num,value);
// }
// if(map.get(num)>length/2){
// return num;
// }
// }
// return -1;
// }
//success 3
//该问题专用的算法：Boyer–Moore majority vote algorithm
public int majorityElement(int[] nums) {
int value = Integer.MAX_VALUE;
int count = 0;
for (int num:
nums) {
if(count==0){
value = num;
count++;
}else if(value!=num){
count--;
}else{
count++;
}
}
return value;
}
}关于算法三，可以参考Boyer–Moore majority vote algorithm。另附：一个演示该算法的网站。
2.Search a 2D Matrix II
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
1.Integers in each row are sorted in ascending from left to right.
2.Integers in each column are sorted in ascending from top to bottom.
从上面两条规则可以得出，一个元素的所有左上角元素一定比之小，一个元素的所有右下角元素一定比之大，其他部位（右上角和左下角）的所有元素与之关系不确定。
For example,
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]Given target = 5, return true.
Given target = 20, return false.
我刚开始误以为对角线元素可以做分割，但之后确认是错误的，贴出错误代码：
//请注意，该代码不完整，只是为了演示我最初的思路
public boolean findMatrix(int[][] matrix,int[] start,int[] end,int target) {
int[] middle = new int[2];
middle[0] = (start[0]+end[0])/2;
middle[1] = (start[1]+end[1])/2;
int middleValue = matrix[middle[0]][middle[1]];
if(target==middleValue){
return true;
}else if(target<middleValue){
//错误思路：只考虑左上角
return findMatrix(matrix,start,middle,target);
}else if(target>middleValue){
//错误思路：只考虑右下角
return findMatrix(matrix,middle,end,target);
}
}思路2：根据规则，最左上为最小，最右下为最大。跟这样的元素做比较然后通过递归调用是没有用的，因为对于不同的路分割条件是一样的。
如果取右上角元素就可以递归，因为不同的路分割条件是不一样的。比如，如果target比该元素小，那么排除该元素所在的列（因为都比target大），同理，如果比该元素小，排除该元素所在的行。这样，每次调用方法都排除一行或一列，总的时间复杂度为O(M+N)。
代码如下：
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int M = matrix.length;
int N = matrix[0].length;
if(target<matrix[0][0]||target>matrix[M-1][N-1]){
return false;
}
boolean result = findTarget(matrix,0,N-1,target);
return result;
}
public boolean findTarget(int[][] matrix,int row,int column,int target){
if(row>=0&&row<matrix.length&&column>=0&&column<matrix[0].length){
int compareValue = matrix[row][column];
if(target==compareValue){
return true;
}else if(target<compareValue){
//排除列
return findTarget(matrix,row,column-1,target);
}else if(target>compareValue){
//排除行
return findTarget(matrix,row+1,column,target);
}
}else{
return false;
}
return false;
}
}上述代码解决很优美，如果想关于此题的更多解法，可参考Search in a Sorted Matrix 。
3.Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
代码如下：
public class Solution {
//success 1
//O(N lg N) running time + O(1) memory
//直接排序，然后找出来
// public int findKthLargest(int[] nums, int k) {
// Arrays.sort(nums);
// int reveredK = nums.length+1-k;
// return nums[reveredK-1];
// }
//success 2
//O(N lg K) running time + O(K) memory
//维护一个k size的优先队列
public int findKthLargest(int[] nums, int k) {
//对于Integer来说，优先队列默认顺序是数值小的在队列头
final PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int val : nums) {
//添加进队列，添加后会自动排序
pq.offer(val);
if(pq.size() > k) {
//弹出队列头元素
pq.poll();
}
}
//取得队列头元素值，但不弹出
return pq.peek();
}
}4.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.
第一种方法很简单，直接写：
public class Solution {
//success 1
//直接写，很简单
public int maxSubArray(int[] nums) {
int count=0,largest=Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
count+=nums[i];
if(count>largest){
largest=count;
}
if(count<0){
count=0;
}
}
return largest;
}
}我自己写的算法居然还跟著名的算法Kadane’s Algorithm一样！哈哈哈！它应该是针对此类问题的比较好的解法。
第二种方法，我想用分治法实现，但是出问题了，代码如下：
public class Solution {
public int maxSubArray(int[] nums) {
if(nums.length==1){
return nums[0];
}
if(nums.length==2){
return Math.max(nums[0]+nums[1],Math.max(nums[0],nums[1]));
}
int[] result = findMaxArray(nums,0,nums.length-1);
return result[2];
}
public int[] findMaxArray(int[] nums,int left,int right){
//return maxsum's low,high and the sum
System.out.println(left+" "+right);
if(right==left){
int[] result = {left,right,nums[left]};
return result;
}
//注意：此种写法容易引起溢出
//int middle = (left+right)/2;
//正确写法
int middle = left+(right-left)/2;
int[] leftResult = findMaxArray(nums,left,middle);
int[] rightResult = findMaxArray(nums,middle+1,right);
int leftLargest = leftResult[2];
int rightLargest = rightResult[2];
int leftHigh = leftResult[1];
int rightLow = rightResult[0];
int intervalSum=0;
for (int i = leftHigh+1; i < rightLow; i++) {
intervalSum+=nums[i];
}
int middleLargest = leftLargest+rightLargest+intervalSum;
System.out.println("left: "+leftLargest+" right: "+rightLargest+" middle: "+middleLargest);
if(leftLargest >= rightLargest && leftLargest >= middleLargest){// left part is max
System.out.println("left");
return leftResult;
}
if(rightLargest >= leftLargest && rightLargest >= middleLargest){// right part is max
System.out.println("right");
return rightResult;
}
System.out.println("middle");
int[] result = {leftResult[0],rightResult[1],middleLargest};
return result;
}
}通过打log，输出如下：
0 8
0 4
0 2
0 1
0 0
1 1
left: -2 right: 1 middle: -1
right
2 2
left: 1 right: -3 middle: -2
left
3 4
3 3
4 4
left: 4 right: -1 middle: 3
left
left: 1 right: 4 middle: 2
right
5 8
5 6
5 5
6 6
left: 2 right: 1 middle: 3
middle
7 8
7 7
8 8
left: -5 right: 4 middle: -1
right
left: 3 right: 4 middle: 2
right
left: 4 right: 4 middle: 5
middle通过log，分析得出错误原因：在定义middle时并不是包含中间元素的最大和子数组。log中发现对于leftLargest=4，rightLargest=4时，程序发现[4,-1,2,1,-5,4]和为5，比leftLargest和rightLargest都大，所以输出最大和子数组为5。但是，我们可以通过[4,-1,2,1]发现最大和为6。
修改定义middle的策略，得出正确答案：
public class Solution {
public int maxSubArray(int[] nums) {
if(nums.length==1){
return nums[0];
}
if(nums.length==2){
return Math.max(nums[0]+nums[1],Math.max(nums[0],nums[1]));
}
int[] result = findMaxArray(nums,0,nums.length-1);
return result[2];
}
public int[] findMaxArray(int[] nums,int left,int right){
//return maxsum's low,high and the sum
System.out.println(left+" "+right);
if(right==left){
int[] result = {left,right,nums[left]};
return result;
}
//注意：此种写法容易引起溢出
//int middle = (left+right)/2;
//正确写法
int middle = left+(right-left)/2;
int[] leftResult = findMaxArray(nums,left,middle);
int[] rightResult = findMaxArray(nums,middle+1,right);
int leftLargest = leftResult[2];
int rightLargest = rightResult[2];
int leftSum=Integer.MIN_VALUE,rightSum=Integer.MIN_VALUE,leftSumTmp=0,rightSumTmp=0,middleLeft=0,middleRight=0;
for (int i = middle; i >=left; i--) {
leftSumTmp+=nums[i];
if(leftSumTmp>leftSum){
leftSum = leftSumTmp;
middleLeft=i;
}
}
for (int i = middle+1; i <=right; i++) {
rightSumTmp+=nums[i];
if(rightSumTmp>rightSum){
rightSum = rightSumTmp;
middleRight=i;
}
}
int middleLargest = leftSum+rightSum;
System.out.println("left: "+leftLargest+" right: "+rightLargest+" middle: "+middleLargest);
if(leftLargest >= rightLargest && leftLargest >= middleLargest){// left part is max
System.out.println("left");
return leftResult;
}
if(rightLargest >= leftLargest && rightLargest >= middleLargest){// right part is max
System.out.println("right");
return rightResult;
}
System.out.println("middle");
int[] result = {middleLeft,middleRight,middleLargest};
return result;
}
}通过log发现，程序正常运转：
0 8
0 4
0 2
0 1
0 0
1 1
left: -2 right: 1 middle: -1
right
2 2
left: 1 right: -3 middle: -2
left
3 4
3 3
4 4
left: 4 right: -1 middle: 3
left
left: 1 right: 4 middle: 2
right
5 8
5 6
5 5
6 6
left: 2 right: 1 middle: 3
middle
7 8
7 7
8 8
left: -5 right: 4 middle: -1
right
left: 3 right: 4 middle: 2
right
left: 4 right: 4 middle: 6
middle
//最大子数组start index
3
//最大子数组end index
6
//最大子数组sum
65.Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Given nums = [5, 2, 6, 1]
Return the array [2, 1, 1, 0].
第一种思路比较简单，就是无脑对比，贴上源码：
public class Solution {
//fail 1，Time Limit Exceeded
//思想很朴素，就是无脑对比
public List<Integer> countSmaller(int[] nums) {
if(nums.length==0){
return new ArrayList<>();
}
Integer[] smallerArray = new Integer[nums.length];
smallerArray[smallerArray.length-1] = 0;
for (int i = nums.length-2; i >=0; i--) {
int count=0;
for (int j = i; j < nums.length; j++) {
if(nums[i]>nums[j]){
count++;
}
if(j==nums.length-1){
smallerArray[i]=count;
}
}
}
List<Integer> list = new ArrayList<>();
list = Arrays.asList(smallerArray);
return list;
}
}此方法的时间效率不高，在submit时会出现TimeOut。得想出更高效率的算法啊。有大神在Discuss中提到一个思路：
The smaller numbers on the right of a number are exactly those that jump from its right to its left during a stable sort. So I do mergesort with added tracking of those right-to-left jumps.
因此我可以用merge sort的思想实现试试。
首先温习一下merge sort：
Merge Sort
贴出源码：
public class Solution {
//success 2
//运用merge sort追加记录的方式实现
public List<Integer> countSmaller(int[] nums) {
Integer[] smaller = new Integer[nums.length];
Arrays.fill(smaller,0);
MapNums[] mapNums= new MapNums[nums.length];
for (int i = 0; i < nums.length; i++) {
mapNums[i] = new MapNums(i,nums[i]);
}
sort(mapNums, 0, mapNums.length-1,smaller);
List<Integer> list = new ArrayList<>();
list = Arrays.asList(smaller);
return list;
}
void merge(MapNums arr[], int l, int m, int r,Integer[] smaller)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
MapNums L[] = new MapNums [n1];
MapNums R[] = new MapNums [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i].number <= R[j].number)
{
arr[k] = L[i];
//本算法精髓
smaller[L[i].index]+=j;
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
//本算法精髓
smaller[L[i].index]+=j;
i++;
k++;
}
/* Copy remaining elements of L[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(MapNums arr[], int l, int r,Integer[] smaller)
{
if (l < r)
{
// Find the middle point
//注意：此种写法容易引起溢出
//int m = (l+r)/2;
//正确写法
int m = l+(r-l)/2;
// Sort first and second halves
sort(arr, l, m,smaller);
sort(arr , m+1, r,smaller);
// Merge the sorted halves
merge(arr, l, m, r,smaller);
}
}
//内部类
//类MapNums主要是记录每个元素的index和number，
//因为运用merge sort排序后，如果不记录index（在原始数组中的位置）的话，就没有办法向smaller数组中写入正确信息。
class MapNums{
int number;
int index;
public MapNums(int index,int number){
this.index = index;
this.number = number;
}
}
}1.Contains Duplicate
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
运用merge sort的实现：
public class Solution {
//success 1
//运用merge sort的思想，如果在sort或merge中有相同的情况，那么返回true，否则为false。时间复杂度为O(NlogN)
public boolean containsDuplicate(int[] nums) {
return sort(nums,0,nums.length-1);
}
/* Java program for Merge Sort */
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
boolean merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] < R[j])
{
arr[k] = L[i];
i++;
}
else if(L[i] > R[j])
{
arr[k] = R[j];
j++;
}else{
return true;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of L[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
return false;
}
// Main function that sorts arr[l..r] using
// merge()
boolean sort(int arr[], int l, int r)
{
if (l < r)
{
// Find the middle point
//注意：此种写法容易引起溢出
//int m = (l+r)/2;
//正确写法
int m = l+(r-l)/2;
// Sort first and second halves
boolean left = sort(arr, l, m);
boolean right = sort(arr , m+1, r);
// Merge the sorted halves
boolean merge = merge(arr, l, m, r);
if(left||right||merge){
return true;
}
}
return false;
}
}此外，还有其他的一些方法，如果追求小的时间复杂度，可以用hashTable来实现。参考：
其他解法
2.Median of Two Sorted Arrays
寻找两个数组连接起来的中位数。
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
我并没有想出实现的方式，参考Discuss中大神的思路。自己动手实现一下：
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
if (m > n) {
return findMedianSortedArrays(nums2, nums1);
}
int i = 0, j = 0, imin = 0, imax = m, half = (m + n + 1) / 2;
double maxLeft = 0, minRight = 0;
while(imin <= imax){
i = (imin + imax) / 2;
j = half - i;
if(j > 0 && i < m && nums2[j - 1] > nums1[i]){
imin = i + 1;
}else if(i > 0 && j < n && nums1[i - 1] > nums2[j]){
imax = i - 1;
}else{
if(i == 0){
maxLeft = (double)nums2[j - 1];
}else if(j == 0){
maxLeft = (double)nums1[i - 1];
}else{
maxLeft = (double)Math.max(nums1[i - 1], nums2[j - 1]);
}
break;
}
}
if((m + n) % 2 == 1){
return maxLeft;
}
if(i == m){
minRight = (double)nums2[j];
}else if(j == n){
minRight = (double)nums1[i];
}else{
minRight = (double)Math.min(nums1[i], nums2[j]);
}
return (double)(maxLeft + minRight) / 2;
}
}3.Find Peak Element
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
代码如下：
public class Solution {
//success 1
// public int findPeakElement(int[] nums) {
// if(nums.length==1){
// return 0;
// }
// for (int i = 0; i < nums.length; i++) {
// if (i == 0) {
// if (nums[i] > nums[i + 1]) {
// return 0;
// }
// } else if (i == nums.length - 1) {
// if (nums[i] > nums[i - 1]) {
// return nums.length - 1;
// }
// } else {
// if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
// return i;
// }
// }
// }
// return 0;
// }
//success 2
//简化1
public int findPeakElement(int[] nums) {
for (int i = 1; i < nums.length; i++) {
if(nums[i-1]>nums[i]){
return i-1;
}
}
return nums.length-1;
}
}除了上面两种简单的方法，还有O(logN)的方法：
This problem is similar to Local Minimum. And according to the given condition, num[i] != num[i+1], there must exist a O(logN) solution. So we use binary search for this problem.
1.If num[i-1] < num[i] > num[i+1], then num[i] is peak
2.If num[i-1] < num[i] < num[i+1], then num[i+1…n-1] must contains a peak
3.If num[i-1] > num[i] > num[i+1], then num[0…i-1] must contains a peak
4.If num[i-1] > num[i] < num[i+1], then both sides have peak
方法三代码：
public class Solution {
//success 3
//运用binary search
public int findPeakElement(int[] nums) {
return findPeak(nums,0,nums.length-1);
}
public int findPeak(int[] num,int start,int end){
if(start == end){
return start;
}else if(start+1 == end){
if(num[start] > num[end]) return start;
return end;
}else{
//注意：此种写法容易引起溢出
//int m = (start+end)/2;
//正确写法
int m = start+(end-start)/2;
//condition 1
if(num[m] > num[m-1] && num[m] > num[m+1]){
return m;
//condition 3
}else if(num[m-1] > num[m] && num[m] > num[m+1]){
return findPeak(num,start,m-1);
//condition 2 and conditon 4
}else{
return findPeak(num,m+1,end);
}
}
}
}4.Find Minimum in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
运用binary search，参考：
public class Solution {
public int findMin(int[] nums) {
if (nums==null || nums.length==0) { return Integer.MIN_VALUE; }
int left = 0, right = nums.length-1;
//保证比较数组中至少有三个元素
while (left < right-1) { // while (left < right-1) is a useful technique
int mid = left + (right-left)/2;
if (nums[mid] > nums[right]) { left = mid; }
else { right = mid; }
}
if (nums[left] > nums[right]) { return nums[right]; }
return nums[left];
}
}5.Find Minimum in Rotated Sorted Array II
4题上的变种（考虑有重复的元素）：
Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
public class Solution {
public int findMin(int[] nums) {
if (nums==null || nums.length==0) { return Integer.MIN_VALUE; }
int left = 0, right = nums.length-1;
//保证比较数组中至少有三个元素
while (left < right-1) { // while (left < right-1) is a useful technique
int mid = left + (right-left)/2;
if (nums[mid] > nums[right]) { left = mid; }
else if(nums[mid] < nums[right]) { right = mid; }
//相等情况，不能确定在左还是右，只能减少一点边界
else{
right-=1;
}
}
if (nums[left] > nums[right]) { return nums[right]; }
return nums[left];
}
}注意：Java曾经的一个系统级的binary search bug，可以google “binary search bug”，这个bug是，当使用int mid = (left + right)/2;时，如果当left和right都很大时，left+right将发生overflow，进而产生负数，Java在2006年已经在系统级别binary search上进行了修复。但是我们自己手写代码时，如果不注意这个bug，在left和right都很大时，就会产生错误。所以我推荐使用int mid = left + (right-left)/2;，当然最精确的方法是看看Java源码中的实现，然后照着改写之。
相关文章参考：
google blog
java bug
1.Implement strStr()
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
思路一：直接两个指针，暴力法
public class Solution {
//success 1
public int strStr(String haystack, String needle) {
//haystack长度必须大
if(haystack.length()<needle.length()){
return -1;
}
if(needle.isEmpty()){
return 0;
}
for (int i = 0; i < haystack.length(); i++) {
for(int j=0;j<needle.length();j++){
//保证charAt(i+j)不越界
if(i+j>=haystack.length()){
return -1;
}
if(haystack.charAt(i+j)==needle.charAt(j)){
if(j==needle.length()-1){
return i;
}
continue;
}else{
break;
}
}
}
return -1;
}
//success 2
//方法1的简洁版
// public int strStr(String haystack, String needle) {
// for (int i = 0; ; i++) {
// for (int j = 0; ; j++) {
// if (j == needle.length()) return i;
// if (i + j == haystack.length()) return -1;
// if (needle.charAt(j) != haystack.charAt(i + j)) break;
// }
// }
// }
}思路二：可以用KMP子字符串比对算法。
下面我们先来复习一下KMP算法，参考(KMP) Pattern Matching(Substring search)实现之，使上面暴力算法的时间复杂度从O(M×N)降至O(M+N)，主要思路是借助了一个辅助数组，避免了每次比对不成功时都从pattern数组最起始位置重新比较：
//success 3
//kmp的实现,参考https://www.youtube.com/watch?v=GTJr8OvyEVQ
public class Solution {
public int strStr(String haystack, String needle) {
char[] haystackArray = haystack.toCharArray();
char[] needleArray = needle.toCharArray();
//haystack长度必须大
if (haystack.length() < needle.length()) {
return -1;
}
if (needle.isEmpty()) {
return 0;
}
Integer[] assistArray = patternPrehandle(needle);
int m = haystack.length();
int i=0,j=0;
while(i<m){
if(haystackArray[i]==needleArray[j]){
i++;
j++;
if(j==needle.length()){
return i-needle.length();
}
}else if(j!=0){
j = assistArray[j-1];
}else{
i++;
}
}
return -1;
}
Integer[] patternPrehandle(String pattern1){
char[] pattern = pattern1.toCharArray();
Integer[] result = new Integer[pattern.length];
int i=0,j=1;
result[0] = 0;
if(pattern.length==1){
return result;
}
while((i>=0)&&(i<j)&&(j<pattern.length)){
if(pattern[i]==(pattern[j])){
result[j]=i+1;
i++;
j++;
}else if(i!=0){
i = result[i-1];
}else{
result[j]=0;
j++;
}
}
return result;
}
}2.Add Binary
Given two binary strings, return their sum (also a binary string).
For example,
a = “11”
b = “1”
Return “100”.
就是简单的实现二进制的加法：
public class Solution {
public String addBinary(String a, String b) {
int i=a.length()-1,j=b.length()-1;
//进位和加和
int carry=0,sum=0;
StringBuilder sb = new StringBuilder("");
while(i>=0||j>=0){
sum=carry;//进位
if(i>=0){
int add1 = a.charAt(i)-'0';
sum+=add1;
i--;
}
if(j>=0){
int add2 = b.charAt(j)-'0';
sum+=add2;
j--;
}
sb.append(String.valueOf(sum%2));
carry=sum/2;
}
if(carry!=0){
sb.append(String.valueOf(carry));
}
return sb.reverse().toString();
}
}当然，如果想要更简单一点，可以用Java自带的BigInteger实现。
3.Simplify Path
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = “/home/”, => “/home”
path = “/a/./b/../../c/”, => “/c”
Corner Cases:
Did you consider the case where path = “/../”?
In this case, you should return “/”.
Another corner case is the path might contain multiple slashes ‘/’ together, such as “/home//foo/”.
In this case, you should ignore redundant slashes and return “/home/foo”.
两种方式实现，第二种更简洁明了一点：
public class Solution {
//success 1
//直接利用string实现
public String simplifyPath(String path) {
//化简成标准型
String stardardPath="";
String pathTmp = path.replace("/./","/");
//循环，直到所有替换完成
while(pathTmp.contains("/./")){
pathTmp = pathTmp.replace("/./","/");
}
stardardPath = pathTmp.replaceAll("/+","/");
String[] pathArray = stardardPath.split("/");
String finalString = "/";
int lastEleIndex = 1;
for (int i = 1; i < pathArray.length; i++) {
if(i==pathArray.length-1&&("".equals(pathArray[i])||".".equals(pathArray[i]))){
break;
}
if("..".equals(pathArray[i])){
if(finalString.length()==1){
continue;
}else{
//除去"/"char
finalString = finalString.substring(0,finalString.length()-2);
int lastIndex = finalString.lastIndexOf("/");
finalString = finalString.substring(0,lastIndex+1);
}
}else{
finalString = finalString+pathArray[i]+"/";
}
}
if(finalString.length()>1){
//除去"/"char
finalString = finalString.substring(0,finalString.length()-1);
}
return finalString;
}
//success 2,利用stack实现
// public String simplifyPath(String path) {
// Deque<String> stack = new LinkedList<>();
// //特殊情况为..,.,空
// Set<String> skip = new HashSet<>(Arrays.asList("..",".",""));
// for (String dir : path.split("/")) {
// if (dir.equals("..") && !stack.isEmpty()) stack.pop();
// else if (!skip.contains(dir)) stack.push(dir);
// }
// String res = "";
// for (String dir : stack) res = "/" + dir + res;
// return res.isEmpty() ? "/" : res;
// }
}4.Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
采用分治算法实现：
public class Solution {
//success 1
// public List<String> generateParenthesis(int n) {
// List<String> list = new ArrayList<String>();
// backtrack(list, "", 0, 0, n);
// return list;
// }
// public void backtrack(List<String> list, String str, int open, int close, int max){
// if(str.length() == max*2){
// list.add(str);
// return;
// }
// if(open < max)
// backtrack(list, str+"(", open+1, close, max);
// if(close < open)
// backtrack(list, str+")", open, close+1, max);
// }
//success 2
//想象leftIndex和rightIndex为一个数组或者stack的index，从last到0
public List<String> generateParenthesis(int n) {
List list = new ArrayList();
generate("",list,n-1,n-1);
return list;
}
private void generate(String path,List list,int leftIndex,int rightIndex){
//当rightIndex==-1时，一个组合结束
if(rightIndex==-1){
list.add(path);
return;
}
if(leftIndex>=0){
generate(path+"(",list,leftIndex-1,rightIndex);
}
if(rightIndex>leftIndex){
generate(path+")",list,leftIndex,rightIndex-1);
}
}
}5.Scramble String
题目链接
解答：
public class Solution {
public boolean isScramble(String s1, String s2) {
if (s1.equals(s2)) return true;
int[] letters = new int[26];
for (int i=0; i<s1.length(); i++) {
letters[s1.charAt(i)-'a']++;
letters[s2.charAt(i)-'a']--;
}
for (int i=0; i<26; i++) if (letters[i]!=0) return false;
for (int i=1; i<s1.length(); i++) {
if (isScramble(s1.substring(0,i), s2.substring(0,i))
&& isScramble(s1.substring(i), s2.substring(i))) return true;
if (isScramble(s1.substring(0,i), s2.substring(s2.length()-i))
&& isScramble(s1.substring(i), s2.substring(0,s2.length()-i))) return true;
}
return false;
}
}在刷这个专题之前，有必要温习一下DP的思想，知乎上有人总结的不错，可以参考之：
什么是动态规划？动态规划的意义是什么？中徐凯强 Andy和王勐同学的回答，他们的回答在于用浅显易懂的话来解释DP的思想，比复杂的数学推导更有意思更实际更让人不想睡觉，哈哈哈。
另外怎么列动态规划递推方程？比较实际，可以参考之。
以及它跟divide and conquer思想的不同：
What is the difference between dynamic programming and divide and conquer? 在其中指出它们的主要区别：
divide and conquer主要分为三个步骤：
1.divide-将一个大问题分成若干个小问题
2.conquer-对于每一个小问题，都用迭代的方法来分别算出他们独立的结果
3.combine-将每个小问题的独立结果合并起来，组成最终大问题的解
典型的应用算法有：Merge Sort, Binary Sort等。
DP算法在将大问题分解为小问题这一点上与divide and conquer类似。DP算法的关键在于remembering。这就是我们为什么要在一个table中存储小问题的结果，这样我们对于同样的小问题，就不用再计算了，从而节省了时间。
典型的应用算法有：Matrix Chain Multiplication, Tower of Hanoi puzzle等。
另一个区别是：在divide and conquer中，子问题的结果通常都是独立的，而DP的一个问题的求解可能需要另一个问题的结果。DP的小问题之间通常有重叠，因此对于重叠部分，可以利用之前算出的结果，而不用重新再算一次。可以简单地认为DP = recursion + re-use。
stackoverflow上的回答，并附带例子，很形象
那么我们现在就开始刷题吧。
1.Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.
实际上，这个问题的抽象是找到数组中后元素与前元素的最大差。参考前面Maximum Subarray 用到的Kadane’s Algorithm。参考Discuss中Kadane’s Algorithm：
public class Solution {
public int maxProfit(int[] prices) {
int maxCur = 0, maxSoFar = 0;
for(int i = 1; i < prices.length; i++) {
maxCur = Math.max(0, maxCur + prices[i] - prices[i-1]);
maxSoFar = Math.max(maxCur, maxSoFar);
}
return maxSoFar;
}
}关于DP：
some elegant design principles—such as divide-andconquer, graph exploration, and greedy choice—that yield definitive algorithms for a variety
of important computational tasks. The drawback of these tools is that they can only be used on very specific types of problems. We now turn to the two sledgehammers of the algorithms craft, dynamic programming and linear programming, techniques of very broad applicability that can be invoked when more specialized methods fail.
Predictably, this generality often comes with a cost in efficiency.
2.Partition Equal Subset Sum
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
分析思路：
这道题给了我们一个数组，问我们这个数组能不能分成两个非空子集合，使得两个子集合的元素之和相同。那么我们想，原数组所有数字和一定是偶数，不然根本无法拆成两个和相同的子集合，那么我们只需要算出原数组的数字之和，然后除以2，就是我们的target，那么问题就转换为能不能找到一个非空子集合，使得其数字之和为target（重点！）。运用动态规划DP。先定义一个一维的dp数组，其中dp[i]表示数字i是否是原数组的任意个子集合之和，那么我们最后只需要返回dp[target]就行了。我们初始化dp[0]为true，由于题目中限制了所有数字为正数，那么我们就不用担心会出现和为0或者负数的情况。那么关键问题就是要找出递归公式了，我们需要遍历原数组中的数字，对于遍历到的每个数字nums[i]，我们需要更新我们的dp数组，要更新[nums[i], target]之间的值，那么对于这个区间中的任意一个数字j，如果dp[j - nums[j]]为true的话，那么dp[j]就一定为true，于是地推公式如下：
dp[j] = dp[j] || dp[j - nums[i]] (nums[i] <= j <= target)
有了递推公式，那么我们就可以写出最终解答：
public class Solution {
public boolean canPartition(int[] nums) {
if(nums.length==0||nums==null){
return true;
}
int total = 0;
for (int i = 0; i < nums.length; i++) {
total+=nums[i];
}
if(total%2!=0){
return false;
}
int target = total/2;
boolean[] dp = new boolean[target+1];//0到target
dp[0] = true;
for (int i = 0; i < nums.length; i++) {
for (int j = target; j>=nums[i]; j--) {
dp[j] = dp[j]||dp[j-nums[i]];
}
}
return dp[target];
}
}3.Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
思路1：从下到上，将相邻的数进行比较取最小，然后加到上一层对应的元素上，然后如此循环。这种思想相当于说，如果要去最小，那么我应该再加多少offset呢。解答如下：
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int m = triangle.size();
for (int i = m-1; i >0; i--) {
for (int j = 0; j < i; j++) {
int offset = Math.min(triangle.get(i).get(j),triangle.get(i).get(j+1));
int value = triangle.get(i-1).get(j)+offset;
triangle.get(i-1).set(j,value);
}
}
return triangle.get(0).get(0);
}
}我的程序跟DP Solution for Triangle中的bottom-to-up DP程序思想是一样的。
4.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.
public class Solution {
//success 1
//需要维护三个重要变量，一个是maxsofar，代表【0，index】区间上最大子数组积；maxhere和maxmin表示包含当前index的结果。
public int maxProduct(int[] A) {
if (A.length == 0) {
return 0;
}
int maxherepre = A[0];
int minherepre = A[0];
int maxsofar = A[0];
int maxhere, minhere;
for (int i = 1; i < A.length; i++) {
maxhere = Math.max(Math.max(maxherepre * A[i], minherepre * A[i]), A[i]);
minhere = Math.min(Math.min(maxherepre * A[i], minherepre * A[i]), A[i]);
maxsofar = Math.max(maxhere, maxsofar);
maxherepre = maxhere;
minherepre = minhere;
}
return maxsofar;
}
}Note:
There’s no need to use O(n) space, as all that you need is a minhere and maxhere. (local max and local min), then you can get maxsofar (which is global max) from them.
该题Maximum Product Subarray与Maximum Subarray的思想基本上一样，因此我将上面代码的乘号改写成加号，然后提交到Maximum Subarray问题上，也是可以通过的。参见success 3。
但是Maximum Subarray的success 1方法却没法改写成Maximum Product Subarray版本，因为它们毕竟还是有些不同啊，负负得正，可能得到最大的积，而负负相加却只能更小。这就是success1没办法改写的原因。
5.Longest Increasing Subsequence（LIS）
LIS应该算是DP的经典应用了。
思路一：没有比这个视频讲的思路更简单的了，直接实现该思想。
public class Solution {
//success 1
//视频https://www.youtube.com/watch?v=CE2b_-XfVDk的思想的实现
public int lengthOfLIS(int[] nums) {
if(nums.length==0||nums==null){
return 0;
}
int length = nums.length;
int[] dp = new int[length];
Arrays.fill(dp,1);//至少存在自己一个LIS，所以LIS肯定大于等于1
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if(nums[j]<nums[i]){
dp[i] = Math.max(dp[i],dp[j]+1);//状态转移方程
}
}
}
//find the largest
int largest=Integer.MIN_VALUE;
for (int i = 0; i < dp.length; i++) {
if(dp[i]>largest){
largest = dp[i];
}
}
return largest;
}
}状态dp[i]代表在区间0-i之间LIS的长度。此方法的时间复杂度为O(N×N)。
能不能有所提升到O(logN×N)呢？
思路二：
参考Java/Python Binary search O(nlogn) time with explanation，它维护了一个数组，tails is an array storing the smallest tail of all increasing subsequences with length i+1 in tails[i].这个数组是递增数组，因此在情况2下要更新值时，就可以用binary search从而能够使复杂度降为O(logN×N)。代码如下：
public class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int i = 0, j = size;
while (i != j) {
int m = (i + j) / 2;
if (tails[m] < x)
i = m + 1;
else
j = m;
}
tails[i] = x;
if (i == size) ++size;
}
return size;
}
}1.Assign Cookies
分配糖果的问题，很简单，直接写：
public class Solution {
public int findContentChildren(int[] g, int[] s) {
//sort
Arrays.sort(g);
Arrays.sort(s);
int m = g.length;
int n = s.length;
int i=0,j=0,sum=0;
while(i<m&&j<n){
if(g[i]<=s[j]){
sum++;
i++;
j++;
}else{
j++;
}
}
return sum;
}
}2.Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
public class Solution {
//success 1
//从后向前
public boolean canJump(int[] nums) {
int n = nums.length;
int last=n-1;
for(int i=n-2;i>=0;i--){
if(i+nums[i]>=last)last=i;
}
return last<=0;
}
//success 2
//从前向后
// public boolean canJump(int[] nums) {
// int reachable = 0;
// for (int i=0; i<nums.length; ++i) {
// if (i > reachable) return false;
// reachable = Math.max(reachable, i + nums[i]);
// }
// return true;
// }
}3.Wiggle Subsequence
A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.
For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.
Examples:
Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Input: [1,2,3,4,5,6,7,8,9]
Output: 2
public class Solution {
//success 1
//跟LIS的思路相同
public int wiggleMaxLength(int[] nums) {
int length = nums.length;
if(length==0){
return 0;
}
Pair[] dp = new Pair[length];
//特别注意：这种写法fill的都是同一个对象，所以会相互影响！
//Arrays.fill(dp,new Pair(1,0));
//改写为下式
for (int i = 0; i < dp.length; i++) {
Pair pair = new Pair(1,0);
dp[i] = pair;
}
//from j to i
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if(nums[j]<nums[i]){
if(dp[j].symbol!=1){
if(dp[i].value<dp[j].value+1){
dp[i].value = dp[j].value+1;
dp[i].symbol=1;
}
}
}else if(nums[j]>nums[i]){
if(dp[j].symbol!=2){
if(dp[i].value<dp[j].value+1){
dp[i].value = dp[j].value+1;
dp[i].symbol=2;
}
}
}
}
}
int largest = Integer.MIN_VALUE;
for (int i = 0; i < dp.length; i++) {
if(dp[i].value>largest){
largest = dp[i].value;
}
}
return largest;
}
class Pair{
public int value;
//1 for add,2 for sub,0 for init
public int symbol;
public Pair(int value,int symbol){
this.value = value;
this.symbol = symbol;
}
}
}思路二：运用greedy的思想，参考Very Simple Java Solution with detail explanation实现之：
public class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length == 0 || nums.length == 1) {
return nums.length;
}
int k = 0;
while (k < nums.length - 1 && nums[k] == nums[k + 1]) { //Skips all the same numbers from series beginning eg 5, 5, 5, 1
k++;
}
if (k == nums.length - 1) {
return 1;
}
int result = 2; // This will track the result of result array
boolean smallReq = nums[k] < nums[k + 1]; //To check series starting pattern
for (int i = k + 1; i < nums.length - 1; i++) {
if (smallReq && nums[i + 1] < nums[i]) {
nums[result] = nums[i + 1];
result++;
smallReq = !smallReq; //Toggle the requirement from small to big number
} else {
if (!smallReq && nums[i + 1] > nums[i]) {
nums[result] = nums[i + 1];
result++;
smallReq = !smallReq; //Toggle the requirement from big to small number
}
}
}
return result;
}
}根据该greedy的实现思想，如果需要，还能够返回具有该最大长度的数组是哪个。
4.Candy
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?代码：
public class Solution {
//fail 1
//timeout
// public int candy(int[] ratings) {
// int length = ratings.length;
// int[] candys = new int[length];
// Arrays.fill(candys,1);
// for (int j = 0; j < length-1; j++) {
// if(ratings[j]>ratings[j+1]){
// while(j>=0&&candys[j]<=candys[j+1]&&ratings[j]>ratings[j+1]){
// candys[j]=candys[j+1]+1;
// j--;
// }
// }else if(ratings[j]<ratings[j+1]){
// candys[j+1]=candys[j]+1;
// }
// }
// int num = 0;
// for (int i = 0; i < candys.length; i++) {
// num+=candys[i];
// }
// return num;
// }
//success 2
//在1的基础上进行优化
public int candy(int[] ratings) {
int len = ratings.length;
int[] candy = new int[len];
candy[0] =1;
for (int i = 1; i < len; ++i) {
if (ratings[i] > ratings[i-1]) {
candy[i] = candy[i-1] + 1;
} else {
candy[i] = 1;
}
}
int total = candy[len-1];
for (int i = len - 2; i >= 0; --i) {
if (ratings[i] > ratings[i+1] && candy[i] <= candy[i+1]) {
candy[i] = candy[i+1] + 1;
}
total += candy[i];
}
return total;
}
}5.Create Maximum Number
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:
You can assume that you can always reach the last index.
public class Solution {
//fail 1
//timeOut
//dp的思想
// public int jump(int[] nums) {
// if(nums.length<=1){
// return 0;
// }
// if(nums.length==2){
// return 1;
// }
// //dp代表最小几步到下一层
// int length = nums.length;
// int[] dp = new int[length];
// Arrays.fill(dp,Integer.MAX_VALUE);
// dp[length-1]=0;
// for (int i = length-2; i >=0 ; i--) {
// for (int j = i+1; j < length; j++) {
// //can reach
// if(nums[i]+i>=j){
// if(dp[j]!=Integer.MAX_VALUE){
// dp[i] = Math.min(dp[i],dp[j]+1);
// }
// }
// }
// }
// return dp[0];
// }
//success 2
//BFS solution
public int jump(int A[]) {
int n=A.length;
if(n<2)return 0;
int level=0,currentMax=0,i=0,nextMax=0;
while(currentMax-i+1>0){ //nodes count of current level>0
level++;
for(;i<=currentMax;i++){ //traverse current level , and update the max reach of next level
nextMax=Math.max(nextMax,A[i]+i);
if(nextMax>=n-1)return level; // if last element is in level+1, then the min jump=level
}
currentMax=nextMax;
}
return 0;
}
}1.Integer Break
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
Note: You may assume that n is not less than 2 and not larger than 58.
利用求导来分析，分析结果得到大部分情况应该按3切分，如果n>=5，那么果断都应该按3切分，如果n<5，作为特殊情况来考虑（比如4就应该拆分成2*2，而不是3*1）。
public class Solution {
public int integerBreak(int n) {
//特殊情况
if(n==2){
return 1;
}
if(n==3){
return 2;
}
int product=1;
while(n>=5){
product = product*3;
n=n-3;
}
product = product*n;
return product;
}
}2.Self Crossing
题目
参考Java Oms with explanation实现：
public class Solution {
/* i-2
case 1 : i-1┌─┐
└─┼─>i
i-3
i-2
case 2 : i-1 ┌────┐
└─══>┘i-3
i i-4 (i overlapped i-4)
case 3 : i-4
┌──┐
│i<┼─┐
i-3│ i-5│i-1
└────┘
i-2
*/
//只有上述四种情况之一
public boolean isSelfCrossing(int[] num) {
int length = num.length;
if(length<=3){
return false;
}
for (int i = 3; i < length; i++) {
//case 1
if(num[i-1]<=num[i-3]&&num[i]>=num[i-2]){
return true;
}
//case 2
if(i>=4){
if(num[i-1]==num[i-3]&&num[i]+num[i-4]>=num[i-2]){
return true;
}
}
//case 3
if(i>=5){
if(num[i]+num[i-4]>=num[i-2]&&num[i-1]+num[i-5]>=num[i-3]&&num[i-1]<=num[i-3]&&num[i-2]>num[i-4]){
return true;
}
}
}
return false;
}
}1.Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
getMin() – Retrieve the minimum element in the stack.
记录最小值，这样可以实现快速返回，注意Stack里为long，因为有int的相减，可能发生越界。
public class MinStack {
Stack<Long> stack;
long min;//存储最小的值，这样可以快速返回
/**
* initialize your data structure here.
*/
public MinStack() {
stack = new Stack<>();
}
public void push(int x) {
if (stack.isEmpty()) {
min = x;
stack.push(0L);
} else {
//push动作比较的最小值是push动作之前所有值中的最小值
stack.push(x - min);
if (x < min) {
min = x;
}
}
}
public void pop() {
if (stack.isEmpty()) {
return;
} else {
long tmp = stack.pop();
if (tmp < 0) {
min = min - tmp;
}
}
}
public int top() {
long result = stack.peek();
if (result > 0) {
return (int)(result + min);
} else {
return (int)min;
}
}
public int getMin() {
return (int)min;
}
}2.Binary Tree Preorder Traversal
实现二叉树的前序遍历。
思路一：利用递归（简单标准做法）：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
//success 1
//Recursive method
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root!=null){
recursive(root,list);
}
return list;
}
public void recursive(TreeNode root,List list){
if(root!=null){
list.add(root.val);
}
if(root.left!=null){
recursive(root.left,list);
}
if(root.right!=null){
recursive(root.right,list);
}
}
}思路二：用递归的实现很简单，但需要调用更多的程序栈，我们可以用迭代的思想再实现之：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
//success 2
//iterative method
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
//Stack is a subclass of Vector that implements a standard last-in, first-out stack.
Stack<TreeNode> stack = new Stack<>();
//用stack来记录right
while(root!=null){
list.add(root.val);
//处理right
if(root.right!=null){
stack.push(root.right);
}
//处理left
root = root.left;
if(root==null&&!stack.isEmpty()){
root = stack.pop();
}
}
return list;
}
}下面我们来了解一种数据结构，叫segment tree：
如果我们需要在一个array中查找index在[start，end]区间中的最小值（最大值，和等），那么我们最朴素的做法是直接比较，然后返回，这样对于m次不同的查找，时间复杂度为O(mn)，m为次数，n为array的length。当m很大，即查询次数很多时，效率就很低，这时就可以引入segment tree了，它能够使查询的时间复杂度为O(logN)。
一种加快的方式是，事先计算好这些结果，然后存入矩阵中，矩阵中元素(i,j)的值代表index在区间[i,j]上的最小值。但是，要维护这个矩阵，我们需要O(N×N)时间创建它，需要O(N×N)空间存储，我们还可以用更好的数据结构来得到这种便利。
segment tree：我们花O(N)来创建它，需要O(N)空间存储，查询复杂度为O(logN)。Segment Tree Range Minimum Query youtube 视频。
如视频截图，我们的模型虽然是tree，但存储该树的元素是用数组存储的，这跟heap sort中实现的策略是一样的。
视频中对于递归方法调用的步骤分析用到了lineNumber，这种分析思路值得借鉴。
具体的关于创建和查询的代码：
public class Solution {
private int[] input;
private int[] segTree;
void init(int[] input1){
input = input1;
int n = input.length;
int length;
if(isPowOfN(n,2)){
length=2*n-1;
}else{
length = 2*findNextPowOfN(n,2)-1;
}
segTree = new int[length];
//fill max value
Arrays.fill(segTree,Integer.MAX_VALUE);
//pos 表示tree的根节点
constructTree(input,segTree,0,n-1,0);
}
void constructTree(int[] input,int[] segTree,int low,int high,int pos){
if(low==high){
segTree[pos] = input[low];
return;
}
int mid = low+(high-low)/2;
//left
constructTree(input,segTree,low,mid,2*pos+1);
//right
constructTree(input,segTree,mid+1,high,2*pos+2);
segTree[pos] = Math.min(segTree[2*pos+1],segTree[2*pos+2]);
}
boolean isPowOfN(int num,int n){
if(n==0){
return false;
}
while(num%n==0){
num = num/n;
}
return num==1;
}
int findNextPowOfN(int num,int n){
if(n==0){
return 0;
}
while(!isPowOfN(num,n)){
num++;
}
return num;
}
int rangeMinQuery(int[] segTree,int qlow,int qhigh,int low,int high,int pos){
//case 2:totally overlap
if(qlow<=low&&qhigh>=high){
return segTree[pos];
}
//case 3:no overlap
else if(qlow>high||qhigh<low){
return Integer.MAX_VALUE;
}
//case 1:partially overlap
else {
int mid = low + (high - low) / 2;
//区间减半，pos变成child
int left = rangeMinQuery(segTree, qlow, qhigh, low, mid, 2 * pos + 1);
int right = rangeMinQuery(segTree, qlow, qhigh, mid + 1, high, 2 * pos + 2);
return Math.min(left, right);
}
}
int query(int qlow,int qhigh){
//注意low与high是相对于input的
return rangeMinQuery(segTree,qlow,qhigh,0,input.length-1,0);
}
public static void main(String[] args){
int input[] = {0,3,4,2,1,6,-1};
Solution s = new Solution();
s.init(input);
System.out.println(s.query(0,3));
System.out.println(s.query(1,5));
System.out.println(s.query(1,6));
System.out.println(s.query(6,6));
}
}3.Largest Rectangle in Histogram
思路一是利用上述的RMQ的segmentTree实现，思路二是Largest Rectangular Area in a Histogram GeeksforGeeks的实现。
关于思路二更多的参考资料：
1.What is the algorithmic approach to find the maximum rectangular area in a histogram?
2.Tushar Roy大神的讲解
// public class Solution {
// //fail 1
// //timeOut
// public int largestRectangleArea(int[] heights) {
// if(heights.length==0){
// return 0;
// }
// init(heights);
// int max=Integer.MIN_VALUE;
// for(int i=0;i<heights.length;i++){
// int area=Integer.MIN_VALUE;
// for(int j=i;j<heights.length;j++){
// area = Math.max(area,query(i,j)*(j-i+1));
// }
// max = Math.max(max,area);
// }
// return max;
// }
// private int[] input;
// private int[] segTree;
// void init(int[] input1){
// input = input1;
// int n = input.length;
// int length;
// if(isPowOfN(n,2)){
// length=2*n-1;
// }else{
// length = 2*findNextPowOfN(n,2)-1;
// }
// segTree = new int[length];
// //fill max value
// Arrays.fill(segTree,Integer.MAX_VALUE);
// //pos 表示tree的根节点
// constructTree(input,segTree,0,n-1,0);
// }
// void constructTree(int[] input,int[] segTree,int low,int high,int pos){
// if(low==high){
// segTree[pos] = input[low];
// return;
// }
// int mid = low+(high-low)/2;
// //left
// constructTree(input,segTree,low,mid,2*pos+1);
// //right
// constructTree(input,segTree,mid+1,high,2*pos+2);
// segTree[pos] = Math.min(segTree[2*pos+1],segTree[2*pos+2]);
// }
// boolean isPowOfN(int num,int n){
// if(n==0){
// return false;
// }
// while(num%n==0){
// num = num/n;
// }
// return num==1;
// }
// int findNextPowOfN(int num,int n){
// if(n==0){
// return 0;
// }
// while(!isPowOfN(num,n)){
// num++;
// }
// return num;
// }
// int rangeMinQuery(int[] segTree,int qlow,int qhigh,int low,int high,int pos){
// //case 2:totally overlap
// if(qlow<=low&&qhigh>=high){
// return segTree[pos];
// }
// //case 3:no overlap
// else if(qlow>high||qhigh<low){
// return Integer.MAX_VALUE;
// }
// //case 1:partially overlap
// else {
// int mid = low + (high - low) / 2;
// //区间减半，pos变成child
// int left = rangeMinQuery(segTree, qlow, qhigh, low, mid, 2 * pos + 1);
// int right = rangeMinQuery(segTree, qlow, qhigh, mid + 1, high, 2 * pos + 2);
// return Math.min(left, right);
// }
// }
// int query(int qlow,int qhigh){
// //注意low与high是相对于input的
// return rangeMinQuery(segTree,qlow,qhigh,0,input.length-1,0);
// }
// }
//success 2
public class Solution {
public int largestRectangleArea(int[] height) {
int len = height.length;
Stack<Integer> s = new Stack<Integer>();
int maxArea = 0;
for(int i = 0; i <= len; i++){
//这里有个小技巧，就是最后i==len时，
//h=0是肯定小于height[s.peek()]的，
//所以最后stack中的元素得以弹出，不然的话
//就得像success 3那样多写几步实现之。
int h = (i == len ? 0 : height[i]);
if(s.isEmpty() || h >= height[s.peek()]){
s.push(i);
}else{
int tp = s.pop();
maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
i--;
}
}
return maxArea;
}
}Tushar Roy的实现（跟success 2思路一样）：
//success 3
//Tushar Roy的实现
public class Solution {
public int largestRectangleArea(int[] height) {
int len = height.length;
Stack<Integer> s = new Stack<Integer>();
int maxArea = 0,area=0,i;
for(i = 0; i < len; i++){
if(s.isEmpty() || height[i] >= height[s.peek()]){
s.push(i);
}else{
int tp = s.pop();
maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
i--;
}
}
//多写几步，将stack清空
while(!s.isEmpty()){
int tp = s.pop();
maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
}
return maxArea;
}
}1.Maximum Depth of Binary Tree
求最大depth，很简单：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return findDepth(root,1);
}
public int findDepth(TreeNode node,int num){
int left=Integer.MIN_VALUE,right=Integer.MIN_VALUE;
if(node.left==null&&node.right==null){
return num;
}
if(node.left!=null){
left = findDepth(node.left,num+1);
}
if(node.right!=null){
right = findDepth(node.right,num+1);
}
num = Math.max(left,right);
return num;
}
}关于java位运算符（<<,>>）：
1.<<：左移运算符，num << n，相当于num乘以2的n次方，如3<<4=48。
2.>>：右移运算符，num >> n，相当于num除以2的n次方，如32>>4=2。
2.Count Complete Tree Nodes
计算一颗完全二叉树的nodes数。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
//success 1
//可能timeOut,每次都需要计算height，所以很慢
// class Solution {
// int height(TreeNode root) {
// return root == null ? -1 : 1 + height(root.left);
// }
// public int countNodes(TreeNode root) {
// int h = height(root);
// return h < 0 ? 0 :
// //如果相差1，说明左边是完全二叉树，那么加左半边
// //如果不相差1，说明左边不是完全二叉树，那么加上上半部分，将root下移。
// height(root.right) == h-1 ? (1 << h) + countNodes(root.right)
// : (1 << h-1) + countNodes(root.left);
// }
// }
//success 2
class Solution {
int height(TreeNode root) {
return root == null ? -1 : 1 + height(root.left);
}
public int countNodes(TreeNode root) {
int nodes = 0, h = height(root);
while (root != null) {
if (height(root.right) == h - 1) {
nodes += 1 << h;
root = root.right;
} else {
nodes += 1 << h-1;
root = root.left;
}
h--;
}
return nodes;
}
}可参考Concise Java solutions O(log(n)^2)。
3.Serialize and Deserialize BST
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root==null){
return "error";
}
List list = preorderTraversal(root);
StringBuilder sb = new StringBuilder("");
for (int i = 0; i < list.size(); i++) {
sb.append(list.get(i));
sb.append(",");
}
return sb.toString().substring(0,sb.length()-1);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if("error".equals(data)){
return null;
}
String[] array = data.split(",");
TreeNode root = new TreeNode(Integer.valueOf(array[0]));
for (int i=1;i<array.length;i++){
TreeNode node = new TreeNode(Integer.valueOf(array[i]));
findPlace(node,root);
}
return root;
}
void findPlace(TreeNode node,TreeNode root){
if(node.val<root.val){
if(root.left==null){
root.left=node;
}else{
findPlace(node,root.left);
}
}else{
if(root.right==null){
root.right=node;
}else{
findPlace(node,root.right);
}
}
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
//Stack is a subclass of Vector that implements a standard last-in, first-out stack.
Stack<TreeNode> stack = new Stack<>();
//用stack来记录right
while(root!=null){
list.add(root.val);
//处理right
if(root.right!=null){
stack.push(root.right);
}
//处理left
root = root.left;
if(root==null&&!stack.isEmpty()){
root = stack.pop();
}
}
return list;
}
}4.Unique Binary Search Trees
受Count Number of Binary Search Tree Possible given n keys Dynamic Programming的启发，采用DP的思想来计算。
public class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for (int i = 1; i <= n; i++) {
calDpM(dp,i);
}
return dp[n];
}
void calDpM(int[] dp,int m){
int sum=0;
for (int i = 0; i <= m-1; i++) {
sum+=dp[i]*dp[m-1-i];
}
dp[m] = sum;
}
}5.Binary Tree Inorder Traversal
实现二叉树的中序遍历。跟前面2.Binary Tree Preorder Traversal实现的前序遍历思路一样，也是有递归和迭代两种解法（当然，迭代肯定要难一点）。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
//success 1
//recusive method
// public class Solution {
// public List<Integer> inorderTraversal(TreeNode root) {
// List<Integer> list = new ArrayList<>();
// if(root==null){
// return list;
// }
// recursive(list,root);
// return list;
// }
// void recursive(List list,TreeNode node){
// if(node.left!=null){
// recursive(list,node.left);
// }
// list.add(node.val);
// if(node.right!=null){
// recursive(list,node.right);
// }
// }
// }
//success 2
//iterative method
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur!=null || !stack.empty()){
while(cur!=null){
stack.add(cur);
cur = cur.left;
}
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
return list;
}
}6.Binary Tree Postorder Traversal
有了前面的前序和中序遍历，我们乘热打铁把后序遍历的两种方法也实现了吧！
前序遍历的顺序：root-left-right
中序遍历的顺序：left-root-right
后序遍历的顺序：left-right-root
注意到后序遍历与前序遍历之间的关系，将前序遍历中left与right互换，然后将结果reverse就得到了后序（trick）。所以在前序遍历的基础上改动：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
//success 1
//recusive method
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root==null){
return list;
}
recursive(list,root);
return list;
}
void recursive(List list,TreeNode node){
if(node.left!=null){
recursive(list,node.left);
}
if(node.right!=null){
recursive(list,node.right);
}
list.add(node.val);
}
}
//success 2
//iterative method
// public class Solution {
// public List<Integer> postorderTraversal(TreeNode root) {
// List<Integer> list = new ArrayList<>();
// //Stack is a subclass of Vector that implements a standard last-in, first-out stack.
// Stack<TreeNode> stack = new Stack<>();
// //用stack来记录left
// while(root!=null){
// list.add(root.val);
// //处理left
// if(root.left!=null){
// stack.push(root.left);
// }
// //处理right
// root = root.right;
// if(root==null&&!stack.isEmpty()){
// root = stack.pop();
// }
// }
// Collections.reverse(list);
// return list;
// }
// }关于三种顺序的迭代算法总结：Preorder, Inorder, and Postorder Iteratively Summarization。
1.Valid Sudoku
题目描述
public class Solution {
public boolean isValidSudoku(char[][] board) {
for (int i = 0; i < 9; i++) {
HashSet<Character> rows = new HashSet<>();
HashSet<Character> columns = new HashSet<>();
HashSet<Character> cubes = new HashSet<>();
for (int j = 0; j < 9; j++) {
//row不满足条件
if(board[i][j]!='.'&&!rows.add(board[i][j])){
return false;
}
//column不满足条件
if(board[j][i]!='.'&&!columns.add(board[j][i])){
return false;
}
//定义每个cube最左上坐标
int rowIndex = 3*(i/3);//产生0，3，6
int columnIndex = 3*(i%3);//产生0，3，6
if(board[rowIndex+j/3][columnIndex+j%3]!='.'&&!cubes.add(board[rowIndex+j/3][columnIndex+j%3])){
return false;
}
}
}
return true;
}
}2.Group Anagrams
Given an array of strings, group anagrams together.
For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:
[
[“ate”, “eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
Note: All inputs will be in lower-case.
算法的重点是：anagrams之间的共同点是sort后array一样！
熟悉map的iteration，熟悉char[]与String之间的互换。
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new ArrayList<>();
if(strs.length==0){
return result;
}
HashMap<String,List<String>> map = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
String eachString = strs[i];
char[] charArray = eachString.toCharArray();
//anagrams的共同点是sort后array一样！
Arrays.sort(charArray);
//char[] to string
String sortedString = String.valueOf(charArray);
if(map.containsKey(sortedString)){
map.get(sortedString).add(eachString);
}else{
List<String> list = new ArrayList();
list.add(eachString);
map.put(sortedString,list);
}
}
//iterate for map
for(Map.Entry<String,List<String>> entry:map.entrySet()){
result.add(entry.getValue());
}
return result;
}
}3.Sort Characters By Frequency
Given a string, sort it in decreasing order based on the frequency of characters.
主要思路：掌握hashmap等各类map的自定义排序，掌握Simple way to repeat a String in java。
public class Solution {
public String frequencySort(String s) {
Map<Character,Integer> map = new HashMap<>();
char[] charArray = s.toCharArray();
StringBuilder result = new StringBuilder("");
if(s.length()==0){
return result.toString();
}
for (int i = 0; i < charArray.length; i++) {
if(map.containsKey(charArray[i])){
map.put(charArray[i],map.get(charArray[i])+1);
}else{
map.put(charArray[i],1);
}
}
//参见http://www.cnblogs.com/chenssy/p/3264214.html，对hashmap的排序
List<Map.Entry<Character,Integer>> list = new ArrayList<Map.Entry<Character,Integer>>(map.entrySet());
//实现Comparator接口
Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {
@Override
public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
return -(o1.getValue().compareTo(o2.getValue()));//降序排列
}
});
for(Map.Entry<Character,Integer> mapping:list){
//char[] to String
String key = String.valueOf(mapping.getKey());
//repeat string n times
String repeated = new String(new char[mapping.getValue()]).replace("\0", key);
result.append(repeated);
}
return result.toString();
}
}4.Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.
Note:
If there is no such window in S that covers all characters in T, return the empty string “”.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
public class Solution {
public String minWindow(String s, String t) {
HashMap<Character,Integer> map = new HashMap();
for(char c : s.toCharArray())
map.put(c,0);
for(char c : t.toCharArray())
{
if(map.containsKey(c))
map.put(c,map.get(c)+1);
else
return "";
}
int start =0, end=0, minStart=0,minLen = Integer.MAX_VALUE, counter = t.length();
while(end < s.length())
{
char c1 = s.charAt(end);
if(map.get(c1) > 0)
counter--;
map.put(c1,map.get(c1)-1);
end++;
//当找到第一个window时
while(counter == 0)
{
if(minLen > end-start)
{
minLen = end-start;
minStart = start;
}
char c2 = s.charAt(start);
map.put(c2, map.get(c2)+1);
if(map.get(c2) > 0)
counter++;
start++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart,minStart+minLen);
}
}通过运行程序设断点来厘清程序实现。
Discuss中一个大神写的关于substring的通用解决模板。上述代码是该模板的JAVA版本。
5.Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
思路一：
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
//success 1
//map存储斜率，处理边界条件为：1.重合点2.斜率为正无穷，即相同横坐标的情况
//但是map的key存储Double进行比较不安全，具体讲解：
//http://stackoverflow.com/questions/1074781/double-in-hashmap
public class Solution {
public int maxPoints(Point[] points) {
if(points.length <= 0) return 0;
if(points.length <= 2) return points.length;
int result = 0;
for(int i = 0; i < points.length; i++){
HashMap<Double, Integer> hm = new HashMap<Double, Integer>();
int samex = 1;
int samep = 0;
for(int j = 0; j < points.length; j++){
if(j != i){
if((points[j].x == points[i].x) && (points[j].y == points[i].y)){
samep++;
}
if(points[j].x == points[i].x){
samex++;
continue;
}
double k = (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
if(hm.containsKey(k)){
hm.put(k,hm.get(k) + 1);
}else{
hm.put(k, 2);
}
result = Math.max(result, hm.get(k) + samep);
}
}
result = Math.max(result, samex);
}
return result;
}
}思路二：
//success 2
//通过两个Integer来对Double比较进行优化
public class Solution{
public int maxPoints(Point[] points) {
if (points==null) return 0;
if (points.length<=2) return points.length;
Map<Integer,Map<Integer,Integer>> map = new HashMap<Integer,Map<Integer,Integer>>();
int result=0;
for (int i=0;i<points.length;i++){
map.clear();
int overlap=0,max=0;
for (int j=i+1;j<points.length;j++){
int x=points[j].x-points[i].x;
int y=points[j].y-points[i].y;
if (x==0&&y==0){
overlap++;
continue;
}
int gcd=generateGCD(x,y);
if (gcd!=0){
x/=gcd;
y/=gcd;
}
if (map.containsKey(x)){
if (map.get(x).containsKey(y)){
map.get(x).put(y, map.get(x).get(y)+1);
}else{
map.get(x).put(y, 1);
}
}else{
Map<Integer,Integer> m = new HashMap<Integer,Integer>();
m.put(y, 1);
map.put(x, m);
}
max=Math.max(max, map.get(x).get(y));
}
result=Math.max(result, max+overlap+1);
}
return result;
}
private int generateGCD(int a,int b){
if (b==0) return a;
else return generateGCD(b,a%b);
}
}关于Double in HashMap的缺陷与优化。
1.Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode current,pre,start;
pre = new ListNode(Integer.MIN_VALUE);
start = pre;
while(l1!=null&&l2!=null){
if(l1.val<l2.val){
current = new ListNode(l1.val);
pre.next = current;
pre = current;
l1 = l1.next;
}else{
current = new ListNode(l2.val);
pre.next = current;
pre = current;
l2 = l2.next;
}
}
while(l1!=null){
current = new ListNode(l1.val);
pre.next = current;
pre = current;
l1 = l1.next;
}
while(l2!=null){
current = new ListNode(l2.val);
pre.next = current;
pre = current;
l2 = l2.next;
}
if(start.next!=null){
return start.next;
}else{
return null;
}
}
}2.Reverse Linked List
Reverse a singly linked list.
Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
//success 1
//iterative method
// public class Solution {
// public ListNode reverseList(ListNode head) {
// if(head==null){
// return null;
// }
// Stack<Integer> stack = new Stack<>();
// while(head!=null){
// stack.add(head.val);
// head = head.next;
// }
// ListNode current,pre,start;
// pre = new ListNode(Integer.MIN_VALUE);
// start = pre;
// while(!stack.isEmpty()){
// int value = stack.pop();
// current = new ListNode(value);
// pre.next = current;
// pre = current;
// }
// if(start.next!=null){
// return start.next;
// }else{
// return null;
// }
// }
// }
//success 2
//recursive method
//这里要注意，我起初是定义了一个ListNode newStart来存储起始node，但是不起作用，主要原因是退出调用栈时,如果newStart没有被任何对象引用
//就会在退出时销毁，这样newStart就又回到了Integer.MIN_VALUE值。可以试试将start定义为成员变量，然后在该赋值时赋值为成员变量start，这样程序
//能够正确运行。对比于list.add，因为head添加到了list中，所以不会在推出栈时被销毁。这样也就可以保存最后head信息。
public class Solution {
//可以试试
// private ListNode start1;
public ListNode reverseList(ListNode head) {
if(head==null){
return null;
}
// ListNode start=new ListNode(Integer.MIN_VALUE);
List<ListNode> start = new ArrayList<>();
recursive(head,start);
return start.get(0);
}
ListNode recursive(ListNode head,List newStart){
if(head.next==null){
// newStart = head;
newStart.add(head);
return head;
}
ListNode current = new ListNode(head.val);
recursive(head.next,newStart).next=current;
return current;
}
}3.Insertion Sort List
Sort a linked list using insertion sort.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode insertionSortList(ListNode head) {
//原链表前加头
ListNode newHead = new ListNode(Integer.MIN_VALUE);
newHead.next = head;
ListNode start;
start = newHead;
if(head==null){
return null;
}
if(head.next==null){
return head;
}
while(newHead!=null){
ListNode compare,pre,current,minPre=null,minCur=null,compareNext,minNext;
compare = newHead;
int minimum = Integer.MAX_VALUE;
current = newHead.next;
pre = newHead;
//处理边界情况
if(current==null){
break;
}
while(current!=null){
if(current.val<=minimum){
minimum = current.val;
minCur = current;
minPre = pre;
}
pre = current;
current = current.next;
}
compareNext = compare.next;
minNext = minCur.next;
minPre.next = minNext;
compare.next = minCur;
//处理边界情况，防止发生链表循环
if(minCur!=compareNext){
minCur.next = compareNext;
}
newHead = newHead.next;
}
return start.next;
}
}4.Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
//success 1
//参考https://discuss.leetcode.com/topic/2861/share-my-java-solution-with-explanation
public class Solution {
public ListNode rotateRight(ListNode head, int n) {
if (head==null||head.next==null) return head;
//原链表添加头
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode fast=dummy,slow=dummy;
int i;
for (i=0;fast.next!=null;i++)//Get the total length
fast=fast.next;
for (int j=i-n%i;j>0;j--) //Get the i-n%i th node
slow=slow.next;
//变换
fast.next=dummy.next; //Do the rotation
dummy.next=slow.next;
slow.next=null;
return dummy.next;
}
}注意上述代码中变换部分。
5.Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
public class Solution {
//success 1
//利用优先队列来存储lists中的node，每次返回val最小的node，同时将该node.next加入优先队列
public ListNode mergeKLists(ListNode[] lists) {
if (lists==null||lists.length==0) return null;
//pop返回最小数的优先队列
PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.length,new Comparator<ListNode>(){
@Override
public int compare(ListNode o1,ListNode o2){
if (o1.val<o2.val)
return -1;
else if (o1.val==o2.val)
return 0;
else
return 1;
}
});
ListNode dummy = new ListNode(0);
ListNode tail=dummy;
for(int i=0;i<lists.length;i++){
if (lists[i]!=null)
queue.add(lists[i]);
}
while (!queue.isEmpty()){
tail.next=queue.poll();
tail=tail.next;
if (tail.next!=null)
queue.add(tail.next);
}
return dummy.next;
}
}默认情况下，如果优先队列中存储的元素为Integer，它返回的顺序为优先返回最小的。Integer中compare方法的实现：
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}那么，如果我们要返回ListNode中存储val最小的元素，只需要像Integer一样重写之。
注意：在优先队列的定义中，优先返回的是具有最大优先级的元素，那么也就是说，对于Integer来说，优先级顺序为小于，等于，大于（即-1，0，1，至于这些小于，等于，大于怎么定义，就是另一回事了。你可以用实际上大于的情况来返回-1，这样的话，重写之后的Integer将按照从大到小的顺序输出）。
思路二：我们也可以利用分治的思想实现之：
//success 2
//利用分治法的思想
public ListNode mergeKLists(ListNode[] lists){
return partion(lists,0,lists.length-1);
}
public ListNode partion(ListNode[] lists,int s,int e){
if(s==e) return lists[s];
if(s<e){
int q=(s+e)/2;
ListNode l1=partion(lists,s,q);
ListNode l2=partion(lists,q+1,e);
return merge(l1,l2);
}else
return null;
}
//This function is from Merge Two Sorted Lists.
//注意该merge方法的实现，很简洁
public static ListNode merge(ListNode l1,ListNode l2){
if(l1==null) return l2;
if(l2==null) return l1;
if(l1.val<l2.val){
l1.next=merge(l1.next,l2);
return l1;
}else{
l2.next=merge(l1,l2.next);
return l2;
}
}
}1.Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int minDepth(TreeNode root) {
if(root==null){
return 0;
}
return recursive(root);
}
int recursive(TreeNode root){
if(root.left==null&&root.right==null){
return 1;
}else if(root.left!=null&&root.right!=null){
return Math.min(recursive(root.left)+1,recursive(root.right)+1);
}else if(root.left!=null){
return recursive(root.left)+1;
}else if(root.right!=null){
return recursive(root.right)+1;
}
return Integer.MIN_VALUE;//error
}
}2.Number of Islands
题意
//success 1
//添加外围的一层0，使得边界条件更好表示，DFS思想很明显
public class Solution {
public int numIslands(char[][] grid) {
if(grid==null){
return 0;
}
int m = grid.length;
if(m==0){
return 0;
}
int n = grid[0].length;
if(n==0){
return 0;
}
char[][] newGrid = new char[m+2][n+2];
for (int i = 0; i < m+2; i++) {
Arrays.fill(newGrid[i],'0');
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
newGrid[i+1][j+1] = grid[i][j];
}
}
//store visited
Set<String> visited = new HashSet<>();
int count=0;
for (int i = 1; i < m+1; i++) {
for (int j = 1; j < n+1; j++) {
if(newGrid[i][j]=='1'&&!visited.contains(String.valueOf(i)+","+String.valueOf(j))){
DFS(newGrid,visited,i,j);
count++;
}
}
}
return count;
}
void DFS(char[][] grid,Set visited,int i,int j){
//up
if(grid[i-1][j]=='1'&&!visited.contains(String.valueOf(i-1)+","+String.valueOf(j))){
visited.add(String.valueOf(i-1)+","+String.valueOf(j));
DFS(grid,visited,i-1,j);
}
//down
if(grid[i+1][j]=='1'&&!visited.contains(String.valueOf(i+1)+","+String.valueOf(j))){
visited.add(String.valueOf(i+1)+","+String.valueOf(j));
DFS(grid,visited,i+1,j);
}
//left
if(grid[i][j-1]=='1'&&!visited.contains(String.valueOf(i)+","+String.valueOf(j-1))){
visited.add(String.valueOf(i)+","+String.valueOf(j-1));
DFS(grid,visited,i,j-1);
}
//right
if(grid[i][j+1]=='1'&&!visited.contains(String.valueOf(i)+","+String.valueOf(j+1))){
visited.add(String.valueOf(i)+","+String.valueOf(j+1));
DFS(grid,visited,i,j+1);
}
}
}3.Sum Root to Leaf Numbers
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
很简单，直接写：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution{
public int sumNumbers(TreeNode root) {
List<Integer> nums = new ArrayList<>();
String path = "";
if(root==null){
return 0;
}
DFS(root,nums,path);
int total=0;
for (Integer num:
nums) {
total+=num;
}
return total;
}
void DFS(TreeNode root,List list,String path){
if(root.left==null&&root.right==null){
list.add(Integer.valueOf(path+String.valueOf(root.val)));
return;
}
if(root.left!=null){
DFS(root.left,list,path+String.valueOf(root.val));
}
if(root.right!=null){
DFS(root.right,list,path+String.valueOf(root.val));
}
}
}4.Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
很简单，直接写：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private static final int LEFT=1;
private static final int RIGHT=2;
public TreeNode sortedArrayToBST(int[] nums) {
TreeNode root = null;
if(nums.length==0||nums==null){
return root;
}
if(nums.length==1){
root = new TreeNode(nums[0]);
return root;
}
if(nums.length==2){
root = new TreeNode(nums[0]);
TreeNode node = new TreeNode(nums[1]);
root.right=node;
return root;
}
int mid = (nums.length-1)/2;
root = new TreeNode(nums[mid]);
recursive(root,LEFT,nums,0,mid-1);
recursive(root,RIGHT,nums,mid+1,nums.length-1);
return root;
}
void recursive(TreeNode node,int direction,int[] nums,int low,int high){
if(high-low>=2){
int mid = low+(high-low)/2;
TreeNode midNode= new TreeNode(nums[mid]);
if(direction==LEFT){
node.left = midNode;
}else{
node.right = midNode;
}
recursive(midNode,LEFT,nums,low,mid-1);
recursive(midNode,RIGHT,nums,mid+1,high);
}else if(low==high){
TreeNode midNode= new TreeNode(nums[low]);
if(direction==LEFT){
node.left = midNode;
}else{
node.right = midNode;
}
}else if(high-low==1){
TreeNode lowNode= new TreeNode(nums[low]);
if(direction==LEFT){
node.left = lowNode;
}else{
node.right = lowNode;
}
TreeNode highNode= new TreeNode(nums[high]);
lowNode.right = highNode;
}
}
}5.Longest Increasing Path in a Matrix
题意
解题思路：遍历每一个节点，存储每个节点到自身能够到达的顶点的最远距离，这样当再track到这个点时，能够直接返回，不用重复计算（DP思想）。cache存储的是在一个点能够到达的所有的点的最远距离值。比如[1,2,3,4]，那么在遍历1节点时，就已经将这条路上所有点的最远距离值都存储在cache中了，这样，遍历到2,3,4节点时直接返回的值，没有计算。代码如下：
//success 1
//参考https://discuss.leetcode.com/topic/34835/15ms-concise-java-solution
public class Solution {
public static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public int longestIncreasingPath(int[][] matrix) {
if(matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
//cache存储每个点到它所能达到的最顶点的长度
int[][] cache = new int[m][n];
int max = 1;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
int len = dfs(matrix, i, j, m, n, cache);
max = Math.max(max, len);
}
}
return max;
}
public int dfs(int[][] matrix, int i, int j, int m, int n, int[][] cache) {
if(cache[i][j] != 0) return cache[i][j];
int max = 1;
//注意for循环中这四个方向的简洁写法
for(int[] dir: dirs) {
int x = i + dir[0], y = j + dir[1];
if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue;
int len = 1 + dfs(matrix, x, y, m, n, cache);
max = Math.max(max, len);
}
cache[i][j] = max;
return max;
}
}参考：
1.15ms Concise Java Solution
2.Java 14ms relative short & easy to code solution with explanation. O(mn) time O(mn) space. DFS + DP
6.Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
参考：Accepted short solution in Java，代码如下：
public class Solution {
int maxValue;
public int maxPathSum(TreeNode root) {
maxValue = Integer.MIN_VALUE;
maxPathDown(root);
return maxValue;
}
private int maxPathDown(TreeNode node) {
if (node == null) return 0;
int left = Math.max(0, maxPathDown(node.left));
int right = Math.max(0, maxPathDown(node.right));
maxValue = Math.max(maxValue, left + right + node.val);
return Math.max(left, right) + node.val;
}
}7.Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
参考Simple and Powerful In-Order Traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
//success 1
//运用该方法的原理是：一个BST的中序遍历应该是升序的，我们可以找到不是升序的两项，然后交换之。
public class Solution {
TreeNode firstElement = null;
TreeNode secondElement = null;
// The reason for this initialization is to avoid null pointer exception in the first comparison when prevElement has not been initialized
TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
// In order traversal to find the two elements
traverse(root);
// Swap the values of the two nodes
//只交换值，很机智啊
int temp = firstElement.val;
firstElement.val = secondElement.val;
secondElement.val = temp;
}
private void traverse(TreeNode root) {
if (root == null)
return;
traverse(root.left);
// Start of "do some business",
// If first element has not been found, assign it to prevElement (refer to 6 in the example above)
if (firstElement == null && prevElement.val >= root.val) {
firstElement = prevElement;
}
// If first element is found, assign the second element to the root (refer to 2 in the example above)
if (firstElement != null && prevElement.val >= root.val) {
secondElement = root;
}
prevElement = root;
// End of "do some business"
traverse(root.right);
}
}1.Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
跟硬币问题很相似，同样是利用DP思想，直接写：
public int numSquares(int n) {
List<Integer> perfertSqu = new ArrayList<>();
for (int i = 1; i < n; i++) {
if(i*i<=n){
perfertSqu.add(i*i);
}else{
break;
}
}
int[] dp = new int[n+1];
dp[0]=0;
dp[1]=1;
for (int i = 2; i < n+1; i++) {
int min=Integer.MAX_VALUE;
for (int j = 0; j < perfertSqu.size(); j++) {
int num = perfertSqu.get(j);
if(num<=i){
min = Math.min(min,dp[i-num]+1);
}else{
break;
}
}
dp[i] = min;
}
return dp[n];
}
}2.Minimum Height Trees
题意
参考：Share some thoughts
The actual implementation is similar to the BFS topological sort. Remove the leaves, update the degrees of inner vertexes. Then remove the new leaves. Doing so level by level until there are 2 or 1 nodes left. What’s left is our answer!
//success 1
//跟BFS拓扑排序的思想类似
public class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return Collections.singletonList(0);
//将用edges表示的图关系转换为邻接链表
List<Set<Integer>> graph = new ArrayList<>(n);
for(int i=0;i<n;i++){
graph.add(new HashSet<>());
}
for(int[] edge:edges){
int i = edge[0];
int j = edge[1];
graph.get(i).add(j);
graph.get(j).add(i);
}
//定义leaves，即degree为1的vertices
List<Integer> leaves = new ArrayList<>();
for(int i=0;i<n;i++){
if(graph.get(i).size()==1){
leaves.add(i);
}
}
//最后只剩1个或2个leaf
while(n>2){
n-=leaves.size();
List<Integer> newLeaves = new ArrayList<>();
System.out.println(leaves.size());
for(int i=0;i<leaves.size();i++){
int start = leaves.get(i);
//取得set中的数
int end = graph.get(start).iterator().next();//遍历set
graph.get(end).remove(start);
if(graph.get(end).size()==1){
newLeaves.add(end);
}
}
leaves = newLeaves;
}
return leaves;
}
}3.Remove Invalid Parentheses
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
参考：
1.Java DFS 3 ms solution
2.Share my Java BFS solution
//success 1
//很难理解
// public class Solution {
// public List<String> removeInvalidParentheses(String s) {
// List<String> ans = new ArrayList<>();
// remove(s, ans, 0, 0, new char[]{'(', ')'});
// return ans;
// }
// public void remove(String s, List<String> ans, int last_i, int last_j, char[] par) {
// for (int stack = 0, i = last_i; i < s.length(); ++i) {
// if (s.charAt(i) == par[0]) stack++;
// if (s.charAt(i) == par[1]) stack--;
// if (stack >= 0) continue;
// for (int j = last_j; j <= i; ++j)
// if (s.charAt(j) == par[1] && (j == last_j || s.charAt(j - 1) != par[1]))
// remove(s.substring(0, j) + s.substring(j + 1, s.length()), ans, i, j, par);
// return;
// }
// String reversed = new StringBuilder(s).reverse().toString();
// if (par[0] == '(') // finished left to right
// remove(reversed, ans, 0, 0, new char[]{')', '('});
// else // finished right to left
// ans.add(reversed);
// }
// }
//success 2
//空间效率很低，思想比较直观
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();
// sanity check
if (s == null) return res;
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
// initialize
queue.add(s);
visited.add(s);
boolean found = false;
while (!queue.isEmpty()) {
s = queue.poll();
System.out.println("queue poll: "+s);
if (isValid(s)) {
System.out.println("res: "+s);
// found an answer, add to the result
res.add(s);
//这句话非常重要，在found到一个valid string时，那么这个值就被永久置为true了
//它将不会执行generate all possible states后面的语句，一直在queue中取值，直到为空
//因为题意是Remove the minimum number，一旦found为true，那么只需要在跟它长度相同的string
//中查找，在queue中查找都有一部分冗余，可以从stdOut中看出来
found = true;
}
System.out.println("found: "+found);
if (found) continue;
// generate all possible states
for (int i = 0; i < s.length(); i++) {
// we only try to remove left or right paren
if (s.charAt(i) != '(' && s.charAt(i) != ')') continue;
String t = s.substring(0, i) + s.substring(i + 1);
System.out.println(t);
if (!visited.contains(t)) {
// for each state, if it's not visited, add it to the queue
System.out.println("not visited: "+t);
queue.add(t);
visited.add(t);
}
}
}
return res;
}
// helper function checks if string s contains valid parantheses
boolean isValid(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') count++;
if (c == ')' && count-- == 0) return false;
}
return count == 0;
}
}对于输入：
"()())()"上述stdOut输出为：
queue poll: ()())()
found: false
)())()
not visited: )())()
(())()
not visited: (())()
()))()
not visited: ()))()
()()()
not visited: ()()()
()()()
()()))
not visited: ()()))
()())(
not visited: ()())(
queue poll: )())()
found: false
())()
not visited: ())()
)))()
not visited: )))()
)()()
not visited: )()()
)()()
)()))
not visited: )()))
)())(
not visited: )())(
queue poll: (())()
res: (())()
found: true
queue poll: ()))()
found: true
queue poll: ()()()
res: ()()()
found: true
queue poll: ()()))
found: true
queue poll: ()())(
found: true
queue poll: ())()
found: true
queue poll: )))()
found: true
queue poll: )()()
found: true
queue poll: )()))
found: true
queue poll: )())(
found: true最终输出结果为：
["(())()","()()()"]1.Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
“A man, a plan, a canal: Panama” is a palindrome.
“race a car” is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
//success 1
//需要预处理，比较容易想到，success 2更简洁
// public class Solution {
// public boolean isPalindrome(String s) {
// if(s.isEmpty()){
// return true;
// }
// //pre process
// StringBuilder sb = new StringBuilder("");
// for(int i=0;i<s.length();i++){
// //大写与小写之间还有间隔
// if((s.charAt(i)>='A'&&s.charAt(i)<='Z')||(s.charAt(i)>='a'&&s.charAt(i)<='z')||(s.charAt(i)>='0'&&s.charAt(i)<='9')){
// sb.append(String.valueOf(s.charAt(i)).toLowerCase());
// }
// }
// String string = sb.toString();
// if(string.length()==0||string.length()==1){
// return true;
// }
// for(int i=0;i<string.length()/2+1;i++){
// if(string.charAt(i)!=string.charAt(string.length()-1-i)){
// return false;
// }
// }
// return true;
// }
// }
//success 2
//two pointers
public class Solution {
public boolean isPalindrome(String s) {
if (s.isEmpty()) {
return true;
}
int head = 0, tail = s.length() - 1;
char cHead, cTail;
while(head <= tail) {
cHead = s.charAt(head);
cTail = s.charAt(tail);
if (!Character.isLetterOrDigit(cHead)) {
head++;
} else if(!Character.isLetterOrDigit(cTail)) {
tail--;
} else {
if (Character.toLowerCase(cHead) != Character.toLowerCase(cTail)) {
return false;
}
head++;
tail--;
}
}
return true;
}
}2.Intersection of Two Arrays
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Note:
Each element in the result must be unique.
The result can be in any order.
参考：Three Java Solutions，代码如下：
//success 1
//Use two hash sets
//Time complexity: O(n)
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Set<Integer> intersect = new HashSet<>();
for (int i = 0; i < nums1.length; i++) {
set.add(nums1[i]);
}
for (int i = 0; i < nums2.length; i++) {
if (set.contains(nums2[i])) {
intersect.add(nums2[i]);
}
}
//转换为array
int[] result = new int[intersect.size()];
int i = 0;
for (Integer num : intersect) {
result[i++] = num;
}
return result;
}
}
//success 2
//Sort both arrays, use two pointers
//Time complexity: O(nlogn)
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
//预排序
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0;
int j = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
set.add(nums1[i]);
i++;
j++;
}
}
int[] result = new int[set.size()];
int k = 0;
for (Integer num : set) {
result[k++] = num;
}
return result;
}
}
//success 3
//Binary search
//Time complexity: O(nlogn)
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Arrays.sort(nums2);
for (Integer num : nums1) {
if (binarySearch(nums2, num)) {
set.add(num);
}
}
int i = 0;
int[] result = new int[set.size()];
for (Integer num : set) {
result[i++] = num;
}
return result;
}
public boolean binarySearch(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return false;
}
}3.Intersection of Two Arrays II
题意
实现该题意并不难，我们回答它的follow-up questions：
先回顾下上一节Intersection of Two Arrays中，我们使用的三种方法，1.Use two hash sets，时间复杂度O(n)，2.Sort both arrays, use two pointers，时间复杂度O(nlogn)，3.Binary search，时间复杂度O(nlogn)。
1.What if the given array is already sorted? How would you optimize your algorithm?
solution：如果已经排好序，那么我们可以使用方法2，two pointers。
2.What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
solution：如果一方特别小，那么可以将另一方作为被比较对象，这样在遍历时，我们的次数会很小。
3.What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
solution（参考Solution to 3rd follow-up question）：
1.If only nums2 cannot fit in memory, put all elements of nums1 into a HashMap, read chunks of array that fit into the memory, and record the intersections.如果只是num2太大，那么将num1映射成hashmap，然后分片读取num2。
2.If both nums1 and nums2 are so huge that neither fit into the memory, sort them individually (external sort), then read 2 elements from each array at a time in memory, record intersections.如果都太大，那么分别使用外部排序进行排序，每次分别将num1和num2的一个元素（或者合适size的元素）放入内存进行比较。
4.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.
很简单，直接写：
public class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
//因为num1的size很大，我们可以考虑直接在num1中原地排序
//trick：如果从index 0开始，1.我们不好判断num1真实有值的情况什么时候结束
//2.而且可能对真实值造成了破坏。我们考虑从后向前来赋值！
int end = m+n-1;
int i = m-1;
int j = n-1;
while(i>=0&&j>=0){
if(nums1[i]>nums2[j]){
nums1[end] = nums1[i];
end--;
i--;
}else{
nums1[end] = nums2[j];
end--;
j--;
}
}
//只需要对num2不为空进行处理
while(j>=0){
nums1[end] = nums2[j];
end--;
j--;
}
}
}5.Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
解答：
//fail 1
//timeOut
// public class Solution {
// public int lengthOfLongestSubstring(String s) {
// if(s.isEmpty()||s.length()==0){
// return 0;
// }
// int length = s.length();
// int i=0,j=0;
// int max = Integer.MIN_VALUE,len=0;
// Set<String> set = new HashSet<>();
// while(i<=j&&j<length){
// //不重复
// if(!set.contains(String.valueOf(s.charAt(j)))){
// set.add(String.valueOf(s.charAt(j)));
// j++;
// len++;
// }else{
// //从i+1继续
// i++;
// j=i;
// set.clear();
// max = Math.max(max,len);
// len=0;
// }
// }
// return Math.max(max,len);
// }
// }
//success 2
//方法1中如果是重复情况，那么就从i的下一个位置重新开始，可以对这里进行优化
//通过记录每个字母最后一次出现的index，来优化，注意这里的i和j的含义跟
//方法1相反
public class Solution{
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max=0;
for (int i=0, j=0; i<s.length(); ++i){
if (map.containsKey(s.charAt(i))){
j = Math.max(j,map.get(s.charAt(i))+1);
}
map.put(s.charAt(i),i);
max = Math.max(max,i-j+1);
}
return max;
}
}如果仔细体会的话，方法二运用了DP的思想，字符串s在[0,i]区间上的最大不重复子串长度dp[i]=
1.若在[0,i-1]区间上存在s[i]，等于i-m+1(m为s[i]最后出现位置，所以才要维护map啊)
2.若不存在s[i]，那么等于dp[i-1]+1，并把自身信息加入到map中
参考：11-line simple Java solution, O(n) with explanation
6.Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a 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.
//success 1
//运用DP的思想，map中存入index,start(小于但最接近s的index)，num(start到index之和)
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int length = nums.length;
if(length==0){
return 0;
}
//注意该初始化的写法，实际后面的<Integer,Map<Integer, Integer>>可以不写
Map<Integer,Map<Integer,Integer>> dp = new HashMap<Integer,Map<Integer, Integer>>(length+1);
Map<Integer,Integer> m = new HashMap<Integer,Integer>();
//两个map都put
m.put(0, 0);
dp.put(0, m);
int min=Integer.MAX_VALUE;
for (int i = 0; i < length; i++) {
if(nums[i]>=s){
return 1;
}else{
Map<Integer,Integer> mapPreI = dp.get(i);
int start=0,num = 0;
for (Integer key:mapPreI.keySet()) {
num = mapPreI.get(key);
start = key;
}
while(num+nums[i]>=s){
num = num-nums[start];
start++;
min = Math.min(min,i-start+2);
}
//更新dp[i]
Map<Integer,Integer> dpI = new HashMap<Integer,Integer>();
dpI.put(start, num+nums[i]);
dp.put(i+1, dpI);
}
}
return min==Integer.MAX_VALUE?0:min;
}
}一个更简洁的版本：
//success 2
//跟我的思想一样，但很简洁啊，话说这种变量少（指需要自己维护的变量，如success 1中的index,start,num就分别对应于success 2中的j,i,sum）
//而且要求连续的题目（一般为substring问题），确实用dp存储太耗费时间空间了
//但！！！DP的思想是非常重要的！
public class Solution{
public int minSubArrayLen(int s, int[] a) {
if (a == null || a.length == 0)
return 0;
int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;
while (j < a.length) {
sum += a[j++];
while (sum >= s) {
min = Math.min(min, j - i);
sum -= a[i++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}7.Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
参考：
1.Java O(1) space solution with detailed explanation.
2.Concise JAVA solution based on slow fast pointers
两种方法都是运用two pointers思想来解决的。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast=head,slow=head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==slow){
ListNode slow2 = head;
while(slow2!=slow){
slow = slow.next;
slow2 = slow2.next;
}
return slow;
}
}
return null;
}
}8.Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.
跟上述7类似，我们也可以利用寻找linkedlist中环的起点中two pointers的思想来处理重复number。可以将数组看成linkedlist嘛，如果出现相等元素，那么就意味着遍历到了相同的node，也即是出现了环！
为什么我们能将该数组看成环呢？因为数组有n+1个元素，而每个元素都在1到n之间（正好在index范围内，我想题意也是有意为之。不然不能看成链表的话，很难做啊）。代码如下：
public class Solution {
public int findDuplicate(int[] nums) {
int fast=nums[0],slow=nums[0];
while(true){
fast = nums[nums[fast]];
slow = nums[slow];
if(fast==slow){
int slow2 = nums[0];
while(slow2!=slow){
slow = nums[slow];
slow2 = nums[slow2];
}
return slow;
}
}
}
}跟上述7的思想非常类似，说一模一样也不为过！
1.Arranging Coins
题意
方法二参考：Java O(1) Solution - Math Problem
//success 1
//直接写，很朴素
// public class Solution {
// public int arrangeCoins(int n) {
// int counter = 1;
// while(n>=counter){
// n-=counter;
// counter++;
// }
// return counter-1;
// }
// }
//success 2
//运用公式，也很朴素
public class Solution {
public int arrangeCoins(int n) {
//注意(long)n将n从int转换为long
return (int)((-1 + Math.sqrt(1 + 8 * (long)n)) / 2);
}
}Note that 8.0 * n is very important because it will cause Java to implicitly autoboxed the intermediate result into double data type. The code will not work if it is simply 8 * n. Alternatively, an explicit casting can be done 8 * (long) n).
2.Find Right Interval
题意
思路一：直接无脑比较
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
//fail 1
//timeOut,思想很朴素，时间复杂度为n的平方
public class Solution {
public int[] findRightInterval(Interval[] intervals) {
int n = intervals.length;
int[] result=new int[n];
for(int i=0;i<n;i++){
int num=-1;
int min=Integer.MAX_VALUE;
for(int j=0;j<n;j++){
if(i!=j){
if(intervals[j].start>=intervals[i].end){
if(intervals[j].start<min){
min = intervals[j].start;
num=j;
}
}
}
}
result[i] = num;
}
return result;
}
}思路二：参考Java clear O(n logn) solution based on TreeMap，代码如下：
//success 2
//利用treemap
public class Solution {
public int[] findRightInterval(Interval[] intervals) {
int[] result = new int[intervals.length];
java.util.NavigableMap<Integer, Integer> intervalMap = new TreeMap<>();
for (int i = 0; i < intervals.length; ++i) {
intervalMap.put(intervals[i].start, i);
}
for (int i = 0; i < intervals.length; ++i) {
Map.Entry<Integer, Integer> entry = intervalMap.ceilingEntry(intervals[i].end);
result[i] = (entry != null) ? entry.getValue() : -1;
}
return result;
}
}补充关于Map,sortedMap,NavigableMap,TreeMap的知识：
在idea ide下打开这些类，看看对应关系，以及有哪些方法。（左下角点击structure查看类下所有方法）
1.Map:
public interface Map<K,V> {}
//An object that maps keys to values.
//A map cannot contain duplicate keys;
//each key can map to at most one value.
//代替jdk1.0就出现的Dictionary抽象类，目前Dictionary已经废弃
//The Map interface provides three collection views, which
//allow a map's contents to be viewed as
//1.a set of keys,
//2.collection of values,
//3.or set of key-value mappings.
//解除map中该key与value的对应关系，并返回该解除了对应关系的value。
//如果map中没有该key，返回null。注意，在允许value=null的map中，
//返回null理所当然地并不意味着没有该key，也可能是value本身就为null。
V remove(Object key);
//复制一个map中的所有对应关系到本map中，相当于将源map中key，value
//全部取出（get方法），然后全部复制存储到本map中。
//注意：
//The behavior of this operation is undefined if the
//specified map is modified while the operation is
//in progress.
//试着翻译：在该操作执行过程中，如果源map有改动，那么结果未知。
void putAll(Map<? extends K, ? extends V> m);
//三种不同视角遍历：
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
//遍历得到key，value的示例：
for (Map.Entry<String, String> entry : map.entrySet())
{
System.out.println(entry.getKey() + "/" + entry.getValue());
}
//在map类还定义了Entry内部类，上面的key，value视角就用到了哈
interface Entry<K,V> {}
//每个entry代表了一个对应关系，可以得到该entry中的key和value
//如该Entry中的K getKey();和V getValue();2.SortedMap：
public interface SortedMap<K,V> extends Map<K,V> {}
//从名称可以看出，是有顺序的map
//（这种顺序是针对于key来说的，不是value）
//如果在创建时指定了Comparator，
//那么返回的顺序由该Comparator定义，否则按照正常的自然的顺序返回。
//在遍历map的三种方式中，这种顺序都能够体现。
//return the comparator used to order the keys in thismap,
//or null if this map uses the natural ordering of itskeys
Comparator<? super K> comparator();
//返回fromKey到toKey之间的subMap
SortedMap<K,V> subMap(K fromKey, K toKey);
//high endpoint (exclusive) of the keys in the returned
//map，相当于subMap（最小的key,toKey)
SortedMap<K,V> headMap(K toKey);
//low endpoint (inclusive) of the keys in the returned map
//相当于subMap（fromkey,最大的key+1)
SortedMap<K,V> tailMap(K fromKey);
//Returns the first (lowest) key currently in this map.
//第一个当然时最low的啦
K firstKey();
//同理
K lastKey();3.NavigableMap：
public interface NavigableMap<K,V> extends SortedMap<K,V> {}
//A SortedMap extended with navigation methods returning
//the closest matches for given search targets.
//Methods lowerEntry,floorEntry,ceilingEntry,and
//higherEntry return Map.Entry objects associated with
//keys respectively less than, less than or equal,greater
//than or equal, and greater than a given key, returning
//null if there is no such key. Similarly, methods
//lowerKey, floorKey, ceilingKey, and higherKey return
//only the associated keys. All of these methods are
//designed for locating, not traversing entries.
//第一句话告诉我们NavigableMap其实一点都不特别，他只是
//具有locat功能的SortedMap而已；最后一句话告诉我们，
//上述这些方法只是用来定位，并不是用来遍历的，这很显然嘛。
//返回所有小于key的keys中最大的key的entry，即closest matches
Map.Entry<K,V> lowerEntry(K key);
//其他相似的方法都同理
//Returns a key-value mapping associated with the least
//key in this map, or null if the map is empty.
Map.Entry<K,V> firstEntry();
//Removes and returns a key-value mapping associated with
//the least key in this map, or null if the map is empty.
Map.Entry<K,V> pollFirstEntry();
//Returns a reverse order view of the mappings contained
//in this map.The descending map is backed by this map,
//so changes to the map are reflected
//in the descending map, and vice-versa.相互会影响
NavigableMap<K,V> descendingMap();
//Returns a NavigableSet view of the keys contained in
//this map.
//The set's iterator returns the keys in ascending order.
NavigableSet<K> navigableKeySet();
//同理，但顺序相反
NavigableSet<K> descendingKeySet();4.TreeMap：
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{}
//红黑树实现之
//A Red-Black tree based NavigableMap implementation.
//The map is sorted according to the Comparable
//natural ordering of its keys,
//or by a Comparator provided at map creation time,
//depending on which constructor is used.
//时间复杂度
//This implementation provides guaranteed log(n) time
//cost for the containsKey, get, put and remove operations.
//Copies all of the mappings from the specified map to
//this map.These mappings replace any mappings that this
//map had for any of the keys currently in the specified
//map.
public void putAll(Map<? extends K, ? extends V> map) {}
//Returns a shallow copy of this TreeMap instance.
//(The keys and values themselves are not cloned.)
public Object clone() {}再补充关于HashMap,HashTable的知识：
1.HashMap：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {}
//可以看出其与HashTable的关系
//Hash table based implementation of the Map interface.
//This implementation provides all of the optional map
//operations, and permits（允许）
//null values and the null key.
//(The HashMap class is roughly equivalent to Hashtable,
//except that it is unsynchronized and permits nulls.)
//从这里可以看出他们的主要差别！
//This class makes no guarantees as to the order of
//the map; in particular, it does not guarantee that
//the order will remain constant over time.
//也不保证order不随时间变化
//只要hash函数分散的好，那么该map的基本操作，如get，put都将只花费常数时间。遍历花费的时间比较复杂，记住下面的tip
//Thus, it's very important not to set the
//initial capacity too high (or the load factor too low)
//if iteration performance is important.
//HashMap原理，跟HashTable原理肯定一样啊
//An instance of HashMap has two parameters that
//affect its performance:
//1.initial capacity
//2.load factor.
//The capacity is the number of buckets in the
//hash table, and the initial capacity is simply
//the capacity at the time the hash table is created.
//The load factor is a measure of how full the
//hash table is allowed to get before its capacity
//is automatically increased. When the number of
//entries in the hash table exceeds the product of
//the load factor and the current capacity,
//the hash table is rehashed (that is, internal
//data structures are rebuilt) so that the hash table
//has approximately twice the number of buckets.
//As a general rule, the default load factor
//(.75)（默认情况是.75） offers a good tradeoff between
//time and space costs.
//Higher values decrease the space overhead but
//increasethe lookup cost
//If many mappings are to be stored in a
//HashMap instance, creating it with a sufficiently
//large capacity will allow the mappings to be stored
//more efficiently than letting it perform
//automatic rehashing as needed to grow the table.
//如果要存入很多，可以在开始时指定较大的容量2.Hashtable
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {}
//跟HashMap真的差不多啊关于这两者的比较：
1.HashMap和Hashtable的区别
2.Differences between HashMap and Hashtable?
Hashtable和HashMap有几个主要的不同：线程安全以及速度。仅在你需要完全的线程安全的时候使用Hashtable，而如果你使用Java 5或以上的话，请使用ConcurrentHashMap吧。
这样看的话，Hashtable还是有点过时了。
3.Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x.
//success 1
//二分法
public class Solution{
public int mySqrt(int x) {
if (x == 0)
return 0;
int left = 1, right = Integer.MAX_VALUE;
while (true) {
int mid = left + (right - left)/2;
if (mid > x/mid) {
right = mid - 1;
} else {
//如果不能整开方，取近似值
if (mid + 1 > x/(mid + 1))
return mid;
left = mid + 1;
}
}
}
}
//success 2
//牛顿法
// public class Solution{
// public int mySqrt(int x){
// long r = x;
// while (r*r > x)
// r = (r + x/r) / 2;
// return (int) r;
// }
// }4.Kth Smallest Element in a Sorted Matrix
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.
Note:
You may assume k is always valid, 1 ≤ k ≤ n2.
跟Divide and Conquer部分的Search a 2D Matrix II题目类似。
//fail 1
//思路完全错了，并不是最小row和column之间取得所有最小的数
//跟原来的Search a 2D Matrix II这个类似的题犯错的思路一样
public class Solution {
public int kthSmallest(int[][] matrix, int k) {
int m = matrix.length;
int n = matrix[0].length;
int row=0,column=0,rowI=0,columnI=0;
int preI=0,preJ=0;
int count=k+1;
while(count>0&&row<m&&column<n&&rowI<n&&columnI<m){
if(matrix[row][rowI]<=matrix[columnI][column]){
preI = row;
preJ = rowI;
if(rowI<n-1){
rowI++;
}else{
row++;
rowI=column+1;
}
}else{
preI = columnI;
preJ = column;
if(columnI<m-1){
columnI++;
}else{
column++;
columnI=row+1;
}
}
count--;
}
if(count>0){
if(row==m||rowI==n){
return matrix[columnI+count-1][column];
}else{
return matrix[row][rowI+count-1];
}
}
return matrix[preI][preJ];
}
}参考：细语呢喃同学的解答：
1.如果行和列都无序怎么解
2.如果行列只有一个有序怎么解
3.如果都有序（即本题）怎么解
都写的非常好！
//success 1
//利用了行列都有序的特点
//思想演进：
//思想1.在最小数和最大数之间每个数每个数试（穷举法）（第一步：选数），在matrix中找出小于等于它的元素的个数（第二步：找出该数顺序），
//如果正好为k，那么找到啦。
//针对第一步，优化思想就是利用二分法，相比于穷举法可以更快的找出这个数来
//针对第二步，优化的思想实际上跟Search a 2D Matrix II很相似，更快的找出该数顺序
//这样两种优化方法相结合，完美！
// public class Solution {
// public int kthSmallest(int[][] matrix, int k) {
// int n = matrix.length;
// //初始L为最小数，初始R为最大数
// int L = matrix[0][0], R = matrix[n - 1][n - 1];
// while (L < R) {
// int mid = L + ((R - L) >> 1);
// int temp = search_lower_than_mid(matrix, n, mid);
// if (temp < k) L = mid + 1;
// else R = mid;
// }
// return L;
// }
// //在matrix中，寻找小于等于mid的元素的个数
// private int search_lower_than_mid(int[][] matrix,int n,int x) {
// int i = n - 1, j = 0, cnt = 0;
// while (i >= 0 && j < n) {
// if (matrix[i][j] <= x) {
// j++;
// cnt += i + 1;
// }
// else i--;
// }
// return cnt;
// }
// }
//fail 2
//值得注意的是枚举答案应该用下界,因为猜想的解不一定在数组中，不断的收缩直到找到在数组中的元素为止。
//如下演示，看起来思想相同，但因为找的数不一定在数组中，所以会运行失败
// public class Solution {
// public int kthSmallest(int[][] matrix, int k) {
// int n = matrix.length;
// //初始L为最小数，初始R为最大数
// int L = matrix[0][0], R = matrix[n - 1][n - 1];
// while (L <= R) {
// int mid = L + ((R - L) >> 1);
// int temp = search_lower_than_mid(matrix, n, mid);
// if(temp<k){
// L = mid+1;
// }else if(temp>k){
// R = mid-1;
// }else{
// return mid;
// }
// }
// return L;
// }
// //在matrix中，寻找小于等于mid的元素的个数
// private int search_lower_than_mid(int[][] matrix,int n,int x) {
// int i = n - 1, j = 0, cnt = 0;
// while (i >= 0 && j < n) {
// if (matrix[i][j] <= x) {
// j++;
// cnt += i + 1;
// }
// else i--;
// }
// return cnt;
// }
// }
//fail 3
//timeOut,但算法应该没问题
//直接利用穷举法，即未经过优化1
public class Solution {
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
//初始L为最小数，初始R为最大数
int L = matrix[0][0], R = matrix[n - 1][n - 1];
int s = L;
for(s = L;s<=R;s++){
if(search_lower_than_mid(matrix, n, s)>=k){
return s;
}
}
return s;
}
//在matrix中，寻找小于等于mid的元素的个数
private int search_lower_than_mid(int[][] matrix,int n,int x) {
int i = n - 1, j = 0, cnt = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] <= x) {
j++;
cnt += i + 1;
}
else i--;
}
return cnt;
}
}5.Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
关于在一个有序数组中二分查找，按下面代码流程，无论哪种情况都会退化到low==high的情况（二分查找本来就应该很简洁啊！记住这二分法的简洁套路啊！）：
1 int[] data;
2 int size;
3
4 public boolean binarySearch(int key)
5 {
6 int low = 0;
7 int high = size - 1;
8
9 while(high >= low) {
10 int middle = (low + high) / 2;
11 if(data[middle] == key) {
12 return true;
13 }
14 if(data[middle] < key) {
15 low = middle + 1;
16 }
17 if(data[middle] > key) {
18 high = middle - 1;
19 }
20 }
21 return false;
22 }该题还多了一个如果没有找到返回插入位置的功能，实际上就是将上述return false的替换掉而已（实际上就是返回low的位置！）。代码如下：
public class Solution{
public int searchInsert(int[] A, int target) {
int low = 0, high = A.length-1;
while(low<=high){
int mid = (low+high)/2;
if(A[mid] == target) return mid;
else if(A[mid] > target) high = mid-1;
else low = mid+1;
}
return low;
}
}6.Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
代码如下：
public class Solution{
public int divide(int dividend, int divisor) {
//Reduce the problem to positive long integer to make it easier.
//Use long to avoid integer overflow cases.
int sign = 1;
if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0))
sign = -1;
long ldividend = Math.abs((long) dividend);
long ldivisor = Math.abs((long) divisor);
//Take care the edge cases.
if (ldivisor == 0) return Integer.MAX_VALUE;
if ((ldividend == 0) || (ldividend < ldivisor)) return 0;
long lans = ldivide(ldividend, ldivisor);
int ans;
if (lans > Integer.MAX_VALUE){ //Handle overflow.
ans = (sign == 1)? Integer.MAX_VALUE : Integer.MIN_VALUE;
} else {
ans = (int) (sign * lans);
}
return ans;
}
private long ldivide(long ldividend, long ldivisor) {
// Recursion exit condition
if (ldividend < ldivisor) return 0;
// Find the largest multiple so that (divisor * multiple <= dividend),
// whereas we are moving with stride 1, 2, 4, 8, 16...2^n for performance reason.
// Think this as a binary search.
long sum = ldivisor;
long multiple = 1;
while ((sum+sum) <= ldividend) {
sum += sum;
multiple += multiple;
}
//Look for additional value for the multiple from the reminder (dividend - sum) recursively.
return multiple + ldivide(ldividend - sum, ldivisor);
}
}7.Max Sum of Rectangle No Larger Than K
返回子matrix和不超过k的最大和。
题意
参考：Maximum Sum Rectangular Submatrix in Matrix，该视频代码，视频中方法适用于matrix中至少有一个为正数的情况，这个算法巧妙在把二维数组按行或列拆成多个一维数组，然后利用一维数组的累加和来找符合要求的数字，也就是将二维的情况退化成多个一维，然后求解。我以为思想相同，只需要改写存入maxSum的条件即可，但经过了如下改写，运行却是错误的。说明，两个题目的内涵不同，不能通过简单地改写来实现。以下为改写代码：
//改写1
//在视频代码的if(kadaneResult.maxSum > result.maxSum){后添加
if(kadaneResult.maxSum<=target){//最大不超过的数
System.out.println("test");
test = Math.max(test,kadaneResult.maxSum);
}
//改写2
在视频代码的if(kadaneResult.maxSum > result.maxSum)判断中
//添加&&kadaneResult.maxSum<=target也不对弃用之，寻找其他方法！
改变策略，不在上述maxSum时才判断是否小于等于target，而是改写原来的Maximum Subarray算法为Maximum Subarray no larger than k。
参考：
1.Quora-思想并附上CPP实现
2.largest sum of contiguous subarray No Larger than k-java实现
3.细语呢喃
4.Java Binary Search solution
原算法：
public int maxSubArray(int[] nums) {
int count=0,largest=Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
count+=nums[i];
if(count>largest){
largest=count;
}
if(count<0){
count=0;
}
}
return largest;
}改写后（小于等于k）：
public int maxSumSubArray2(int[] a , int k){
int max = Integer.MIN_VALUE;
int sumj = 0;
TreeSet<Integer> s = new TreeSet();
s.add(0);
for(int i=0;i<a.length;i++){
int t = sumj + a[i];
sumj = t;
Integer gap = s.ceiling(sumj - k);
if(gap != null) max = Math.max(max, sumj - gap);
s.add(t);
}
return max;
}最终本题的Solution：
//success 1
public class Solution {
public int maxSumSubmatrix(int input[][],int target){
int rows = input.length;
int cols = input[0].length;
int temp[] = new int[rows];
int maxSum = Integer.MIN_VALUE;
for(int left = 0; left < cols ; left++){
for(int i=0; i < rows; i++){
temp[i] = 0;
}
for(int right = left; right < cols; right++){
for(int i=0; i < rows; i++){
temp[i] += input[i][right];
}
int max = maxSumSubArray2(temp,target);
maxSum = Math.max(max,maxSum);
}
}
return maxSum;
}
//Maximum Subarray no larger than k
public int maxSumSubArray2(int[] a , int k){
int max = Integer.MIN_VALUE;
int sumj = 0;
TreeSet<Integer> s = new TreeSet();
s.add(0);
for(int i=0;i<a.length;i++){
int t = sumj + a[i];
sumj = t;
//Returns the least element in this set greater than or equal to
//the given element, or null if there is no such element.
//E ceiling(E e);
//对于当前的和为sum，我们只需要找到一个最小的数x，使得 sum – k <=x，这样可以保证sum – x <=k。
Integer gap = s.ceiling(sumj - k);
if(gap != null) max = Math.max(max, sumj - gap);
s.add(t);
}
return max;
}
}先来复习一下stack，queue，heap的特点：
1.stack：FILO（先进后出）
2.queue：FIFO（先进先出）
3.heap：两个rules，1.the tree is complete,2.parent is always smaller than its two children.
参考differences
1.Design Twitter
题意
未实现显示前10状态的功能，如果要实现肯定是可以的，将Twitter写成一个类，类中包含成员变量时间，然后在getNewsFeed方法中取出每条twitter后再来一次排序，这样就能得到最新发表的前10条状态。但这样也有弊端，如果插入的时间间隔很短，很可能出现两条状态时间相同的情况，而维护一个队列或者其他不依靠绝对时间有序的方法可以避免这样bug情况。并且这样实现的方法都太naive了，想想更高级的实现方法吧。初级代码如下：
public class Twitter {
//users关系
Set<User> relations=new HashSet<>();
/** Initialize your data structure here. */
public Twitter() {
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
for (User each:
relations) {
if(each.id==userId){
each.twitters.add(tweetId);
return;
}
}
User user = new User();
user.id = userId;
user.twitters.add(tweetId);
relations.add(user);
}
/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
public List<Integer> getNewsFeed(int userId) {
List<User> users = new ArrayList<>();
for (User each:
relations) {
if(each.id==userId){
users.add(each);
users.addAll(each.followers);
}
}
List<Integer> news = new ArrayList<>();
for (User eachUser:
users) {
news.addAll(eachUser.twitters);
}
for (Integer each:
news) {
System.out.println("news: "+each);
}
System.out.println("------");
return news;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
if(followerId==followeeId){
return;
}
User follower = new User();
follower.id = followerId;
User followee = new User();
followee.id = followeeId;
follower.followers.add(followee);
followee.followees.add(follower);
relations.add(follower);
relations.add(followee);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
public void unfollow(int followerId, int followeeId) {
if(followerId==followeeId){
return;
}
for (User each:
relations) {
if(each.id==followerId){
for (User ss:
each.followers) {
if(ss.id==followeeId){
each.followers.remove(ss);
break;
}
}
}else if(each.id==followeeId){
for (User ss:
each.followees) {
if(ss.id==followerId){
each.followees.remove(ss);
break;
}
}
}
}
}
}
class User{
int id=Integer.MIN_VALUE;//用户标识
List<Integer> twitters=new ArrayList<>();//发文
Set<User> followees=new HashSet<>();//被哪些关注了
Set<User> followers=new HashSet<>();//关注了哪些
}比我高到不知道哪里的实现：
public class Twitter {
//非常聪明，全局的time计数，这样每次不管哪个user发送twitter，自增1后都能保证是对的顺序，同时又避免使用庞大的Date等time类来解决
//从这里看出换个角度来想问题的重要性
private static int timeStamp=0;
// easy to find if user exist
//这样就不必像我实现的那样遍历Set，来看id是否匹配了！
private Map<Integer, User> userMap;
// Tweet link to next Tweet so that we can save a lot of time
// when we execute getNewsFeed(userId)
private class Tweet{
public int id;
public int time;
public Tweet next;
public Tweet(int id){
this.id = id;
//保证顺序
time = timeStamp++;
next=null;
}
}
// OO design so User can follow, unfollow and post itself
//用户调用方法
public class User{
public int id;
public Set<Integer> followed;
//只保存tweet head，节省空间
public Tweet tweet_head;
public User(int id){
this.id=id;
followed = new HashSet<>();
follow(id); // first follow itself
tweet_head = null;
}
public void follow(int id){
followed.add(id);
}
public void unfollow(int id){
followed.remove(id);
}
// everytime user post a new tweet, add it to the head of tweet list.
public void post(int id){
Tweet t = new Tweet(id);
t.next=tweet_head;
tweet_head=t;
}
}
/** Initialize your data structure here. */
public Twitter() {
userMap = new HashMap<Integer, User>();
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
if(!userMap.containsKey(userId)){
User u = new User(userId);
userMap.put(userId, u);
}
userMap.get(userId).post(tweetId);
}
//重点部分
// Best part of this.
// first get all tweets lists from one user including itself and all people it followed.
// Second add all heads into a max heap. Every time we poll a tweet with
// largest time stamp from the heap, then we add its next tweet into the heap.
// So after adding all heads we only need to add 9 tweets at most into this
// heap before we get the 10 most recent tweet.
public List<Integer> getNewsFeed(int userId) {
List<Integer> res = new LinkedList<>();
if(!userMap.containsKey(userId)) return res;
Set<Integer> users = userMap.get(userId).followed;
//注意该初始化操作，指定了capacity和comparator
PriorityQueue<Tweet> q = new PriorityQueue<Tweet>(users.size(), (a,b)->(b.time-a.time));
for(int user: users){
//将tweet head存入priorityQueue中
Tweet t = userMap.get(user).tweet_head;
// very imporant! If we add null to the head we are screwed.
if(t!=null){
q.add(t);
}
}
int n=0;
while(!q.isEmpty() && n<10){
Tweet t = q.poll();
res.add(t.id);
n++;
//因为poll掉了head，所以将head.next加入进来
if(t.next!=null)
q.add(t.next);
}
return res;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
if(!userMap.containsKey(followerId)){
User u = new User(followerId);
userMap.put(followerId, u);
}
if(!userMap.containsKey(followeeId)){
User u = new User(followeeId);
userMap.put(followeeId, u);
}
userMap.get(followerId).follow(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
public void unfollow(int followerId, int followeeId) {
if(!userMap.containsKey(followerId) || followerId==followeeId)
return;
userMap.get(followerId).unfollow(followeeId);
}
}2.Find Median from Data Stream
不断变化的数组寻找中位数。
题意
参考：
1.Short simple Java
2.max,min priorityQueue
//fail 1
//timeOut
// public class MedianFinder {
// List<Integer> list = new ArrayList<>();
// int pointer = -1;
// boolean even=true;
// // Adds a number into the data structure.
// public void addNum(int num) {
// list.add(num);
// Collections.sort(list);
// even=!even;
// if(even==false){
// pointer++;
// }
// }
// // Returns the median of current data stream
// public double findMedian() {
// if(even){
// double sum = list.get(pointer)+list.get(pointer+1);
// return sum/(double)2;
// }else{
// return list.get(pointer);
// }
// }
// }
//success 2
//维护两个priorityQueue
class MedianFinder {
private Queue<Long> small = new PriorityQueue(),
large = new PriorityQueue();
public void addNum(int num) {
large.add((long) num);
small.add(-large.poll());
if (large.size() < small.size())
large.add(-small.poll());
}
public double findMedian() {
return large.size() > small.size()
? large.peek()
: (large.peek() - small.peek()) / 2.0;
}
}这里补充priorityQueue如何遍历呢？很自然的想法是利用iterator，如下：
PriorityQueue<Integer> integers = new PriorityQueue<>(Collections.reverseOrder());//自然顺序的逆序
integers.offer(7);
integers.offer(9);
integers.offer(3);
integers.offer(5);
//test iterator
Iterator<Integer> i = integers.iterator();
while(i.hasNext()){
System.out.println(i.next());
}
System.out.println("------");
System.out.println("size: "+integers.size());
//test poll
for (int j = 0; j < 4; j++) {
System.out.println(integers.poll());
}输出结果为：
9
7
3
5
------
size: 4
9
7
5
3说明在priorityQueue中利用iterator保证顺序的遍历并不靠谱！该遍历方式没办法保证顺序！
javaDoc中讲到：
The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).参考：
1.How to iterate over a PriorityQueue?
那么在Stack中使用iterator有没有这样的错误呢？实验：
Stack<Integer> integers = new Stack<>();
integers.push(7);
integers.push(9);
integers.push(3);
integers.push(5);
//test iterator
Iterator<Integer> i = integers.iterator();
while(i.hasNext()){
System.out.println(i.next());
}
System.out.println("------");
System.out.println("size: "+integers.size());
//test pop
for (int j = 0; j < 4; j++) {
System.out.println(integers.pop());
}输出结果：
7
9
3
5
------
size: 4
5
3
9
7参考javaDoc-bug（没看错，就是个java bug），申明到：
The iterator method on java.util.Stack iterates through a Stack from the bottom
up. One would think that it should iterate as if it were popping off the top of
the Stack.Stack的iterator是从bottom到up进行遍历的，可以看出这种遍历是有顺序的，只是跟我们希望的从栈顶开始遍历的方式相反而已。
其实java中关于FILO（先进后出）数据结构更好的实现方式是Deque而不是Stack（因为兼容问题，并没有废除Stack，而是用Deque更好地实现，好怪，Stack居然不是Stack的最好实现，哈哈哈），参考javaDoc：
The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.
When a stack is first created, it contains no items.
A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:
Deque<Integer> stack = new ArrayDeque<Integer>();Deque的iterator实现就是我们想要的顺序了（从栈顶up到栈底bottom的遍历顺序）！
关于heap数据结构在java中实现标准就是PriorityQueue。参考：
1.javaDoc
An unbounded priority queue based on a priority heap.
The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.
A priority queue does not permit null elements.
The head of this queue is the least element with respect to the specified ordering.
The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.
The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).
Note that this implementation is not synchronized.(不是线程安全)，多线程下可以使用PriorityBlockingQueue。
时间复杂度：
Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).这里干脆直接总结一下java里面的Collections类吧，请参考我的另一篇博客java解惑。