【九章算法基础班】数与数组

发表于 | 分类于 ， | 浏览 次
字数统计: 17,024 | 阅读时长 ≈ 88

outline

  1. Sorted Array
    • merge two sorted array
      • Intersection of Two Arrays
      • Multiply Two Arrays
    • median of two sorted array
  2. Subarray
    • Best Time to Buy and Sekk Stoocks I,II,III
    • Subarrat I,II,III,IV
  3. Two pointers
    • Two Sum,3Sum,4Sum,kSum,3Sum Closest
    • Partition Array

排序数组Sorted Array

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.

给定两个排序数组nums1,nums2，合并到nums1

三个指针i,j,k分别指向nums1元素结尾，nums2结尾，nums1数组结尾

依次向前遍历，比较大小，插入nums1

public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while(i >= 0 && j >= 0){
            if(nums1[i] > nums2[j]){
                nums1[k] = nums1[i];
                i--;
            }
            else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }
        if (i < 0){
            while(j >=0){
                nums1[k] = nums2[j];
                j--;
                k--;
            }
        }
        if(j < 0){
            while(i >=0){
                nums1[k] = nums1[i];
                i--;
                k--
            }
        }
    }

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.

给定两个数组，返回交集，返回的交集中在原数组中的相对位置保持不变，元素只出现一次。

方法:

  1. 把两个数组排序
  2. 两指针分别遍历两个数组比较大小，如果两指针指向的元素相等，且与result中前一个元素不相等，加入result
public int[] intersection(int[] nums1, int[] nums2) {
        //排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        int index = 0;
        int[] result = new int[nums1.length];
        while(i < nums1.length && j < nums2.length){
            if(nums1[i] == nums2[j]){
                if(index == 0 || nums1[i] != result[index-1]){
                    result[index] = nums1[i];
                    index++;
                }
                i++;
                j++;
            }
            else if(nums1[i] <nums2[j]){
                i++;
            }
            else {
                j++ ;
            }
        }
        int[] res = new int[index];
        for(int idx = 0;idx < index;idx++) {
            res[idx] = result[idx];
        }
        return res;
    }

Sparse Matrix Multiplication

题目

Given two sparse matrices A and B, return the result of AB.

You may assume that A‘s column number is equal to B‘s row number.

Example:

> A = [
>   [ 1, 0, 0],
>   [-1, 0, 3]
> ]
>
> B = [
>   [ 7, 0, 0 ],
>   [ 0, 0, 0 ],
>   [ 0, 0, 1 ]
> ]
>
>
>      |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
> AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
>                   | 0 0 1 |
>

分析

逐个遍历计算

public int[][] multiply(int[][] A, int[][] B) {
  int[][] result = new int[A.length][B[0].length];
  int A_rows = A.length;
  int A_cols = A[0].length;
  int B_rows = B.length;
  int B_cols = B[0].length;
  for(int i = 0; i < A_rows;i++){
    for(int j = 0; j < B_cols;j++){
      for(int k = 0;k < A_cols;k++){
        if(A[i][k] != 0 && B[k][j] != 0){
          result[i][j] = result[i][j] + A[i][k] * B[k][j];
        }
      }
    }
  }
  return result;
}

优化

  1. 遍历矩阵B，把B中值不为0的位置（注意是位置不是值）按每一列存下来
  2. 遍历A矩阵，寻找B中对应位置不为0的元素做乘积
public int[][] multiply2(int[][] A, int[][] B) {
    ArrayList<ArrayList<Integer>> nonZeroIndexB = new ArrayList<>();
    ArrayList<ArrayList<Integer>> nonZeroIndexA = new ArrayList<>();
    int[][] result = new int[A.length][B[0].length];
    int A_rows = A.length;
    int A_cols = A[0].length;
    int B_rows = B.length;
    int B_cols = B[0].length;
    //按列将B中的非零元素index存储下来
    for(int col = 0;col < B_cols;col++){
        ArrayList<Integer> rowIndex = new ArrayList<>();
        for(int row = 0; row < B_rows;row++){
            if(B[row][col] != 0){
                rowIndex.add(row);
            }
        }
        nonZeroIndexB.add(rowIndex);
    }
    //按行将A中的非零元素index存储下来
    for(int row = 0;row < A_rows;row++){
        ArrayList<Integer> rowIndex = new ArrayList<>();
        for(int col = 0; col < A_cols;col++){
            if(A[row][col] != 0){
                rowIndex.add(col);
            }
        }
        nonZeroIndexA.add(rowIndex);
    }
    //遍历矩阵A.B
    for(int i = 0; i < A_rows;i++){
        for(int j = 0; j < B_cols;j++){
           int ii = 0;
           int jj = 0;;
           while(ii < nonZeroIndexA.get(i).size() && jj < nonZeroIndexB.get(j).size()){
               if(nonZeroIndexA.get(i).get(ii) == nonZeroIndexB.get(j).get(jj)){
                   result[i][j] += A[i][nonZeroIndexA.get(i).get(ii)] * B[nonZeroIndexB.get(j).get(jj)][j];
                   ii++;
                   jj++;
               }
               else if(nonZeroIndexA.get(i).get(ii) < nonZeroIndexB.get(j).get(jj)){
                   ii++;
               }
               else {
                   jj++;
               }
           }
        }
    }
    return result;
}

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.

分析

方法一：

在前面的课程里讲过可以利用堆Heap

方法二：

利用quickselect的方法，来源于quicksort

quicksort核心思想：每次选一个数字作为基准，比它小的放到左边，比它大的放到右边，然后再递归对左右两边数组做quicksort

步骤：从数组中选取一个数字作为“基准”pivot，找第K大的元素时可以跟基准比较：

  1. pivot左边元素个数 = K-1，该基准元素就是第K大元素
  2. pivot左边元素个数 > K-1，丢弃右边全部元素，在左边元素中继续寻找
  3. pivot左边元素个数 < K-1，丢弃左边全部元素，在右边元素中继续寻找
public int quickselect(int [] nums,int start,int end,int k){
  //快速排序，寻找pivot应该放置的位置
  int i = start;
  int j = end;
  int pivot = nums[i];
  while(i < j){
    while(i < j && nums[j] >= pivot){
      j--;
    }
    nums[i] = nums[j];
    while(i < j && nums[i] <= pivot){
      i++;
    }
    nums[j]
  nums[i] = pivot;
  //start~i-1的元素都小于等于pivot，一共用i-start个
  //i+1到end的元素都大于等于pivot，一共end-i个
  if(i-start == k-1){
    return nums[i];
  }
  else if(i-start > k-1){
    return quickselect(nums,start,i-1,k);
  }
  else {
    return quickselect(nums,i+1,end,k-(i-start+1));
  }
}
public int findKthLargest(int[] nums, int k) {
  return quickselect(nums,0,nums.length-1,nums.length+1-k);
}

Median

题目

Given a unsorted array with integers, find the median of it.

A median is the middle number of the array after it is sorted.

If there are even numbers in the array, return the N/2-th number after sorted.

Example

Given [4, 5, 1, 2, 3], return 3.

Given [7, 9, 4, 5], return 5.

返回给定数组中位数

和上一题思路一样，K=nums.length/2

代码

public int quickSelect(int[] nums,int start,int end,int k){
    int i = start;
    int j = end;
    int pivot = nums[i];
    while(i < j){
        while (i < j && nums[j] >= pivot){
            j--;
        }
        nums[i] = nums[j];
        while (i < j && nums[i] <= pivot){
            i++;
        }
        nums[j] = nums[i];
    }
    nums[i] = pivot;
    if(i - start == k-1){
        return nums[i];
    }
    else if(i-start > k-1){
        return quickSelect(nums,start,i-1,k);
    }
    else {
        return quickSelect(nums,i+1,end,k-(i-start+1));
    }
}
public int median(int[] nums) {
    // write your code here
    return quickSelect(nums,0,nums.length-1,nums.length - nums.length/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
>

分析

这道题在二分法里面讲过了，先将找中点的问题转化成找第k大的问题，然后继续沿用二分法中的思路。详见【九章算法基础班】二分法

代码

  public int findKthInTwo(int[] nums1,int start1,int[] nums2,int start2,int k){
      //end1中没有元素了，返回nums2中的第k个
      if(start1 >= nums1.length){
          return nums2[start2+k-1];
      }
      //end2中没有元素了，返回nums1中的第k个
      if(start2 >= nums2.length){
          return nums1[start1+k-1];
      }
//边界条件，递归出口
      if(k ==1){
          return Math.min(nums1[start1],nums2[start2]);
      }
      //nums1中剩余元素不足K/2个,nums2的前K/2个元素一定在前k个中，
      // 去掉nums2的前K/2个元素
      if(nums1.length - start1 < k/2){
          return findKthInTwo(nums1,start1,nums2,start2+k/2,k-k/2);
      }
      if(nums2.length - start2 < k/2){
          return findKthInTwo(nums1,start1+k/2,nums2,start2,k-k/2);
      }
     
      if(nums1[start1 + k/2 - 1] < nums2[start2 + k/2 - 1]){
          return findKthInTwo(nums1,start1+k/2,nums2,start2,k-k/2);
      }
      else {
          return findKthInTwo(nums1,start1,nums2,start2+k/2,k-k/2);
      }
  }
  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      int len = nums1.length+nums2.length;
      //偶数个元素
      if(len % 2 == 0){
          int k1 = findKthInTwo(nums1,0,nums2,0,len/2);
          int k2 = findKthInTwo(nums1,0,nums2,0,len/2+1);
          return (double) (k1+k2)/2.0;
      }
      //奇数个元素
      else {
          return findKthInTwo(nums1,0,nums2,0,len/2+1);
      }
  }

子数组 Subarray

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.

最大子数组，找到子数组（连续），和最大

分析

前缀和数组prefixSum：sum[i] = SUM(nums[0~i])

数组中从i到j的数组和：sum[i~j] = sum[j]-sum[i-1]

以当前位置i为结尾的最大子数组是sum[i]-min(sum[0]~sum[i-1])

所以思路就是：从前向后遍历，三个变量存储信息：

  1. 从起点到当前元素的和，前缀和
  2. 截止目前的最大子数组
  3. 前面的最小和

代码

public int maxSubArray(int[] nums) {
  int sum = 0;//记录前缀和
  int min_before = 0;//记录前面最小和,初始化为0,
  int max = Integer.MIN_VALUE;//记录最大子数组
  for(int i = 0; i < nums.length;i++){
    sum += nums[i];//从0到当前元素的前缀和
    max = Math.max(max,sum-min_before);//更新最大子数组
    min_before = Math.min(min_before,sum);//更新前面最小和
  }
  return max;
}

二维数组的Maximum Subarray

前缀和

  i-1  i           x
   *---*---*---*---*
   |   |   |   |   |
j-1*---*---*---*---*
   |   |   |   |   |
 j *-[i,j]-*---*---*
   |   |   |   |   |
   *---*---*---*---*
   |   |   |   |   |
y  *---*---*---*-[x,y]
sum[i,j - x,y] = sum[x,y] - sum[x,j-1] - sum[i-1,y] + sum[i-1,j-1]

Range Sum Query 2D - Immutable

题目

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

> Given matrix = [
>   [3, 0, 1, 4, 2],
>   [5, 6, 3, 2, 1],
>   [1, 2, 0, 1, 5],
>   [4, 1, 0, 1, 7],
>   [1, 0, 3, 0, 5]
> ]
>
> sumRegion(2, 1, 4, 3) -> 8
> sumRegion(1, 1, 2, 2) -> 11
> sumRegion(1, 2, 2, 4) -> 12
>
>

>

Note:

  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

分析

利用二维数组的前缀和，给定左上和右下的坐标为(row1, col1)， (row2, col2)

那么和为sum[i,j - x,y] = sum[x,y] - sum[x,j-1] - sum[i-1,y] + sum[i-1,j-1]

class NumMatrix {
    int[][] Matrix;
    int[][] Sum;
    public NumMatrix(int[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0){
            return;
        }
        this.Matrix = new int[matrix.length][matrix[0].length];
        this.Sum = new int[matrix.length][matrix[0].length];
        Sum[0][0] = matrix[0][0];
        for(int i = 1 ; i < matrix.length;i++){
            Sum[i][0] = Sum[i-1][0] + matrix[i][0];
        }
        for(int i = 1 ; i < matrix[0].length;i++){
            Sum[0][i] = Sum[0][i-1] + matrix[0][i];
        }
        for(int i = 1;i < matrix.length;i++){
            for(int j = 1 ; j < matrix[0].length;j++){
                Sum[i][j] = Sum[i-1][j] + Sum[i][j-1] - Sum[i-1][j-1] + matrix[i][j];
            }
        }
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1 == 0 && col1 == 0){
            return Sum[row2][col2];
        }
        if(row1 == 0){
            return Sum[row2][col2] - Sum[row2][col1 -1];
        }
        if(col1 == 0){
            return Sum[row2][col2] - Sum[row1-1][col2];
        }
        return Sum[row2][col2] - Sum[row1-1][col2] - Sum[row2][col1 -1] + Sum[row1-1][col1 -1 ];
    }
}

Range Sum Query 2D - Mutable

题目

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10

Note:

  1. The matrix is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRegion function is distributed evenly.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

代码

public void update(int row, int col, int val) {
  int delta = val  - Matrix[row][col];//更新值和原来差值
  this.Matrix[row][col] = val;
  for(int i = row;i < Matrix.length;i++){
    for(int j = col;j  < Matrix[0].length;j++){
      Sum[i][j] += delta;
    }
  }
}

最小子数组

Given an array of integers, find the subarray with smallest sum.

Return the sum of the subarray.

Example

For [1, -1, -2, 1], return -3.

和最大子数组相同的思路

public int minSubArray(List<Integer> nums) {
    // write your code here
    int sum = 0;
    int minsub = Integer.MAX_VALUE;
    int maxbefore = 0;
    for(int i = 0 ; i < nums.size();i++){
        sum += nums.get(i);
        minsub = Math.min(minsub,sum - maxbefore);
        maxbefore = Math.max(maxbefore,sum);
    }
    return minsub;
}

Minimum Size Subarray Sum

题目

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

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

求和大于等于s的连续子数组的最小长度

分析

用滑动窗口来做。

两个指针i和j分别指向子数组的头和尾

sumi代表从nums[0]到nums[i]的和

sumj代表从nums[0]到nums[j]的和

如果sumj-sumi >= s，将i向后移动，直至sumj-sumi < s，此时子数组和>=s的长度为j-i+2，更新最小值

public int minSubArrayLen(int s, int[] nums) {
        int sumj = 0;
        int sumi = 0;
        int minlen = Integer.MAX_VALUE;
        int i = 0;
        for(int j = 0; j < nums.length;j++){
            sumj += nums[j];
            int delta = sumj - sumi;
            while(delta >= s){
                sumi += nums[i];
                i++;
                delta = sumj - sumi;
            }
            //跳出时sumj-sumi < s
            if(sumj >= s){
                minlen = Math.min(minlen,j-i+2);
            }
        }
        if(minlen != Integer.MAX_VALUE){
            return minlen;
        }
        else return 0;
    }

Maximum Subarray II

题目

Given an array of integers, find two non-overlapping subarrays which have the largest sum.
The number in each subarray should be contiguous.
Return the largest sum.

Example

For given [1, 3, -1, 2, -1, 2], the two subarrays are [1, 3] and [2, -1, 2] or [1, 3, -1, 2] and [2], they both have the largest sum 7.

求数组中两个不相交的最大子数组的和最大

思路

两个数组不相交，两个数组中间必然存在一个分割线，分割线左边求一个maxsubarray，右边求一个maxsubarray，两个子数组的和加在一起，就是当前分割线的最大子数组和

从左向右遍历分割线，分别求左边和右边的最大子数组，求和，记录最大值

public int MaxSubarray(List<Integer> nums,int start,int end){
    if (start == end) {
        return nums.get(start);
    }
    int maxSum = Integer.MIN_VALUE;
    int minbefore = 0;
    int sum = 0;
    for(int i = start;i <= end;i++){
        sum += nums.get(i);
        maxSum = Math.max(maxSum,sum - minbefore);
        minbefore = Math.min(minbefore,sum);
    }
    return maxSum;
}
public int maxTwoSubArrays(List<Integer> nums) {
    int maxSum = Integer.MIN_VALUE;
    // write your code here
    for(int i = 0; i < nums.size()-1;i++){
        int sum = MaxSubarray(nums,0,i) + MaxSubarray(nums,i+1,nums.size()-1);
        maxSum = Math.max(maxSum,sum);
    }
    return maxSum;
}

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.

求乘积最大的子数组

思路

子数组乘积最大值的可能性为：累乘的最大值碰到了一个正数；或者，累乘的最小值（负数），碰到了一个负数。所以每次要保存累乘的最大（正数）和最小值（负数）。同时还有一个选择起点的逻辑，如果之前的最大和最小值同当前元素相乘之后，没有当前元素大（或小）那么当前元素就可作为新的起点，比如遇到了0。

代码

public int maxProduct(int[] nums) {
    if(nums.length == 1){
        return nums[0];
    }
    //局部最大最小
    int min = nums[0];
    int max = nums[0];
    //全局最大
    int global_max = nums[0];
    for(int i =1; i < nums.length;i++){
        //计算局部最大和最小与当前数字的乘积
        int a = max * nums[i];
        int b = min * nums[i];
        //更新局部最大和最小，必在a,b,nums[i]之中
        max = Math.max(Math.max(a,b),nums[i]);
        min = Math.min(Math.min(a,b),nums[i]);
        //更新全局最大
        global_max = Math.max(global_max,max);
    }
    return  global_max;
}

最大子数组差

题目

Given an array with integers.

Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest.

Return the largest difference.

The subarray should contain at least one number

Example

For [1, 2, -3, 1], return 6.

思路

两个不相交的数字，中间必然存在分割线，对分割线左右两边一编求最大一边求最小，|SUM(A) - SUM(B)|最大有两种情况：

  1. max_sum(A) - min_sum(B)
  2. min_sum(A) - max_sum(B)

遍历分割线，计算，取1,2的绝对值的最大值

代码

public int maxSubarray(int[] nums,int start,int end){
    if(start == end){return nums[start];}
    int sum = 0;
    int min_before = 0;
    int max = Integer.MIN_VALUE;
    for(int i = start ; i <= end;i++){
        sum += nums[i];
        max = Math.max(max,sum - min_before);
        min_before = Math.min(min_before,sum);
    }
    return max;
}
public int minSubarray(int[] nums,int start,int end){
    if(start == end){return nums[start];}
    int sum = 0;
    int max_before = 0;
    int min = Integer.MAX_VALUE;
    for(int i = start ; i <= end;i++){
        sum += nums[i];
        min = Math.min(min,sum - max_before);
        max_before = Math.max(max_before,sum);
    }
    return min;
}
public int maxDiffSubArrays(int[] nums) {
    int max_abs = Integer.MIN_VALUE;
    // write your code here
    for(int i = 0 ; i < nums.length-1;i++){
        int left_max = maxSubarray(nums,0,i);
        int left_min = minSubarray(nums,0,i);
        int right_max = maxSubarray(nums,i+1,nums.length-1);
        int right_min = minSubarray(nums,i+1,nums.length-1);
        int max = Math.max(Math.abs(left_max - right_min),Math.abs(left_min - right_max));
        max_abs = Math.max(max_abs,max);
    }
    return max_abs;
}

子数组之和

题目

Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.

There is at least one subarray that it’s sum equals to zero.

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

返回和为0的子数组开始和结尾所对应的idx

分析

计算出每一个位置的前缀和，然后二重循环计算每一个子数组的和sum[i,j]，遇到有等于0的就返回，时间复杂度，超时了

public List<Integer> subarraySum(int[] nums) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<>();
        int[] prefixSum = new int[nums.length+1];
        int sum = 0;
        for(int i = 0 ; i  < nums.length;i++){
            prefixSum[i] = sum;
            sum += nums[i];
        }
        prefixSum[nums.length] = sum;
        System.out.println(prefixSum);
        for(int i = 1 ; i <= nums.length;i++){
            for (int j = i-1;j >= 0;j--){
                if(prefixSum[i] - prefixSum[j] == 0){
                    result.add(j);
                    result.add(i-1);
                    return result;
                }
            }
        }
        return result;
    }

改进，利用HashMap

根据给的例子：[-3, 1, 2, -3, 4]，其累加和:
nums [-3, 1,  2, -3,  4]
      0   1   2   3   4
sum  [-3，-2， 0， -3， 1]
       i           j
1. i=2出现了一个数0 -> sum[0,i] = 0  ,是一个答案
2. 同时在i,j发现两个-3   -> sum[i+1,j] = 0 ,是一个答案
因此前缀和中如果有0或者有两个相等的，即为所求

代码

public List<Integer> subarraySum(int[] nums) {
    // write your code here
    ArrayList<Integer> result = new ArrayList<>();
    HashMap<Integer,Integer> map = new HashMap<>();
    int sum = 0;
    for(int i = 0 ; i  < nums.length;i++){
        sum += nums[i];
        if(sum == 0){
            result.add(0);
            result.add(i);
            return result;
        }
        if(map.containsKey(sum)){
            result.add(map.get(sum)+1);
            result.add(i);
            return result;
        }
        map.put(sum,i);//key是前缀和，value是idx
    }
    return result;
}

Subarray Sum Equals K

题目

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

> Input:nums = [1,1,1], k = 2
> Output: 2
>
>

>

Note:

  1. The length of the array is in range [1, 20,000].
  2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

分析

跟上一题类似的思路，利用HashMap，存储前缀和的值和出现的次数，当有相同的前缀和出现时，result增加的数量就是当前map里面改值出现的次数。

代码

public int subarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int result = 0;
        int sum = 0;
        for(int i = 0 ; i  < nums.length;i++){
            sum += nums[i];
            //如果之前出现过该值
            if(map.containsKey(sum-k)){
                result += map.get(sum-k);
            }
            if(map.containsKey(sum)){
                map.put(sum,map.get(sum)+1);
            }
            //如果之前没有出现过该值，加入map
            else {
                map.put(sum,1);//key是前缀和，value是出现次数，初始化为1
            }
        }
        return result;
    }

Maximum Size Subarray Sum Equals k

题目

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

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

Example 1:

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

Example 2:

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

Follow Up:
Can you do it in O(n) time?

计算和为k的子数组的最大长度

思路

利用hashmap将出现过的前缀和第一次出现所在的index记录下来，在hashmap中寻找sum[i]-k，若找到，子数组的长度为i - map.get(sum-k) ，记录下满足条件的子数组的最大长度。

public int maxSubArrayLen(int[] nums, int k) {
    HashMap<Integer,Integer> map = new HashMap<>();
    map.put(0,-1);
    int maxlen = 0;//用以记录子数组的最大长度
    int sum = 0;
    for(int i = 0 ; i  < nums.length;i++){
        sum += nums[i];
        //如果之前出现过sum-k
        if(map.containsKey(sum-k)){
            maxlen = Math.max(maxlen,i - map.get(sum-k));
        }
        //该值在map中没有出现过
        if(!map.containsKey(sum)){
            map.put(sum,i);//key是前缀和，value是index
        }
    }
    return maxlen;
}

Subarray Sum Closest

题目

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

Example

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

给定数组，返回和最接近0的子数组的开始和结束位置的index

分析

计算前缀和，排序，取每一个位置的前缀和和相邻前缀和的差的最大值，记录其起点终点，取最小值

public class Solution {
    /*
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    class node implements Comparable<node>{
        int sum;
        int idx;
        public node(int sum,int idx){
            this.sum = sum;
            this.idx = idx;
        }
        public int compareTo(node b) {// Comparable接口中的方法
            return this.sum- b.sum; // 按书的id比较大小，用于默认排序
        }
    }
    public int[] subarraySumClosest(int[] nums) {
        // write your code here
        int[] result = new int[2];
        int sum = 0;
        node[] prefixSum = new node[nums.length];
        for(int i = 0 ; i < nums.length;i++){
            sum += nums[i];
            prefixSum[i] = new node(sum,i);
        }
        Arrays.sort(prefixSum);
        int min = Math.abs(prefixSum[0].sum);
        int min_a = -1;
        int min_b = prefixSum[0].idx;
        for(int i = 1;i < nums.length;i++){
            if(Math.abs(prefixSum[i].sum) < min){
                min = Math.abs(prefixSum[i].sum);
                min_a = -1;
                min_b = prefixSum[i].idx;
            }
            if(Math.abs(prefixSum[i].sum - prefixSum[i-1].sum) < min){
                min = Math.abs(prefixSum[i].sum - prefixSum[i-1].sum);
                min_a = prefixSum[i].idx;
                min_b = prefixSum[i-1].idx;
            }
        }
        int min_idx = Math.min(min_a,min_b);
        int max_idx = Math.max(min_a,min_b);
      result[0] = min_idx+1;
      result[1] = max_idx;
        return result;
    }
}

Contiguous Array

题目

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

Example 1:

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

>

Example 2:

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

>

Note: The length of the given binary array will not exceed 50,000.

思路

计算从0到i位中0的个数zeroSum和1的个数oneSum，以及0比1多多少zeroMoreThanOne

利用hashmap将zeroMoreThanOne和index存储起来，当遇到zeroMoreThanOne == 0或者map.containsKey(zeroMoreThanOne )时说明遇到了01数量相等的子数组，记录最大长度

代码

public int findMaxLength(int[] nums) {
    int maxlen = 0;
    HashMap<Integer,Integer> map = new HashMap<>();//存储0比1多多少idx
    int zeroSum = 0;
    int oneSum = 0;
    int zeroMoreThanOne = 0;
    map.put(0,-1);
    for(int i = 0 ; i < nums.length ;i++){
        if(nums[i] == 0){
            zeroSum++;
        }
        else{
            oneSum++;
        }
        zeroMoreThanOne = zeroSum - oneSum;
        if(map.containsKey(zeroMoreThanOne)){
            int len = i - map.get(zeroMoreThanOne);
            maxlen = Math.max(maxlen,len);
        }
        else{
            map.put(zeroMoreThanOne,i);
        }
    }
    return maxlen;
}

Longest Continuous Increasing Subsequence

题目

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).

Example 1:

> Input: [1,3,5,4,7]
> Output: 3
> Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. 
> Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4. 
>
>

>

Example 2:

> Input: [2,2,2,2,2]
> Output: 1
> Explanation: The longest continuous increasing subsequence is [2], its length is 1. 
>
>

>

Note: Length of the array will not exceed 10,000.

求最长递增子数组

思路

从前向后遍历，两个变量maxlen，len_local 分别记录全局最长递增子数组和局部最长递增子数组的长度，如果

  1. nums[i]>nums[i-1]，len_local++,更新maxlen
  2. nums[i]>nums[i-1]，len_local重置为1

代码

public int findLengthOfLCIS(int[] nums) {
    if(nums.length == 0){
        return 0; 
    }
    int maxlen = 1;
    int len_local = 1;
    for(int i = 1 ; i < nums.length;i++){
        if(nums[i] > nums[i-1]){
            len_local++;
            maxlen = Math.max(maxlen,len_local);
        }
        else{
            len_local = 1;
        }
    }
    return maxlen;
}

Degree of an Array

题目

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

> Input: [1, 2, 2, 3, 1]
> Output: 2
> Explanation: 
> The input array has a degree of 2 because both elements 1 and 2 appear twice.
> Of the subarrays that have the same degree:
> [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
> The shortest length is 2. So return 2.
>
>

>

Example 2:

> Input: [1,2,2,3,1,4,2]
> Output: 6
>
>

>

Note:

nums.length will be between 1 and 50,000.

nums[i] will be an integer between 0 and 49,999.

思路

方法一：利用hashmap存储元素出现的次数和第一次出现的idx，从前向后遍历，更新出现次数最多的元素和最小子数组长度

方法二：遍历数组，用left[val]和right[val]存储val出现的第一次和最后一次，记录出现次数最多的元素和最短长度

代码

class node{
    int earlyIdx;
    int nums;
    public node(int idx,int nums){
        this.earlyIdx = idx;
        this.nums = nums;
    }
}
public int findShortestSubArray(int[] nums) {
    int maxNum = 0;//记录元素出现的最多次数
    int minlen = 1;//记录最短长度
    HashMap<Integer,node> map = new HashMap<>();
    for(int i = 0;i < nums.length;i++){
        //如果之前有此元素了
        if(map.containsKey(nums[i])){
            //算上这次跟当前出现最多次数的元素一样
            if(map.get(nums[i]).nums + 1 == maxNum) {
                minlen = Math.min(minlen,i - map.get(nums[i]).earlyIdx+1);
            }
            //算上这次比当前出现最多次数的元素还多
            else if(map.get(nums[i]).nums + 1 > maxNum) {
                maxNum = map.get(nums[i]).nums + 1;//更新最多次数
                minlen = i - map.get(nums[i]).earlyIdx+1;//更新最短长度
            }
            //更新map
            node newNode = new node(map.get(nums[i]).earlyIdx,map.get(nums[i]).nums+1);
            map.put(nums[i],newNode);
        }
        else {
            map.put(nums[i],new node(i,1));
        }
    }
    return minlen;
}

Container With Most Water

题目

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

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

给定数组a1, a2, …, an,表示边界高度，选取其中两个作为边界，求能够容纳水的最大量。

思路

若选取i,j作为边界，能够容纳的水量是：

步骤：

  1. 初始化：i指向height[0],j指向height[len-1]
  2. 两指针由外向内移动，记录最大的容水量：
    1. 如果height[i] < height[j],i++
    2. 如果height[i] >= height[j],j—

代码

public int maxArea(int[] height) {
    int i = 0;
    int j = height.length-1;
    int max = Integer.MIN_VALUE;
    while(i < j){
        if(height[i] < height[j]){
            max = Math.max(max,(j-i) *height[i]);
            i++;
        }
        else {
            max = Math.max(max,(j-i) * height[j]);
            j--;
        }
    }
    return max;
}

Array Nesting

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

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

Example 1:

> Input: A = [5,4,0,3,1,6,2]
> Output: 6
> Explanation: 
> A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
>
> One of the longest S[K]:
> S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
>
>

>

Note:

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

求数组中能够成环的最大长度

思路

i从头向后遍历，以i为入口访问环，把访问过的标记为-1，记录最大长度

代码

public int arrayNesting(int[] nums) {
        int maxlen = 0;//记录最大长度
        for(int i = 0 ;i < nums.length;i ++){
            int len = 0;//记录以i为入口的环长度
            int j = i;
            while(nums[j] != -1){
                len++;
                int temp = j;
                j = nums[j];
                nums[temp] = -1;//访问过的元素标记
            }
           maxlen = Math.max(maxlen,len);
        }
        return maxlen;
    }

Find Pivot Index

Given an array of integers nums, write a method that returns the “pivot” index of this array.

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:

> Input: 
> nums = [1, 7, 3, 6, 5, 6]
> Output: 3
> Explanation: 
> The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
> Also, 3 is the first index where this occurs.
>
>

>

Example 2:

> Input: 
> nums = [1, 2, 3]
> Output: -1
> Explanation: 
> There is no index that satisfies the conditions in the problem statement.
>

思路

先计算数组的全部元素和sum ，再遍历一次，计算前缀和prefixsum，二者做差是右边的和，prefixsum-nums[i]是左边的和，二者相等就返回

代码

public int pivotIndex(int[] nums) {
  int sum = 0;
  for(int i = 0 ; i < nums.length ;i++){
    sum += nums[i];
  }
  int prefixsum = 0;
  for(int i = 0; i < nums.length;i++){
    prefixsum += nums[i];
    if(sum - prefixsum == prefixsum - nums[i]){
      return i;
    }
  }
  return -1;
}

Product of Array Except Self

题目

思路

要分三种情况讨论：

  1. 如果没有0，计算总乘积、当前乘积
  2. 有1个0，除了0位置不为0，其余位置都是0
  3. 有2个以上0，所有位置都为0

代码

public int[] productExceptSelf(int[] nums) {
  int[] res = new int[nums.length];
  int zeros = 0;
  int product = 1;
  int zeroloc = 0;
  for(int i = 0 ; i < nums.length;i++){
    if(nums[i] == 0){
      zeros += 1;
      zeroloc = i;
    }
    else{
      product *= nums[i];
    }
  }
  if(zeros == 0){
    for(int i = 0 ; i <res.length;i++){
      res[i] = product/nums[i];
    }
  }
  else if(zeros == 1){
    res[zeroloc] = product;
  }
  return res;
}

股票问题

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

分析

第i天卖出所获的最大利润为：

prices[i] - min(prices[0]~prices[i-1])

步骤：从前向后遍历，更新到当前天的价格最低值，更新到当前天的利润最大值

代码

public int maxProfit(int[] prices) {
  if (prices.length == 0){
    return 0;
  }
  //记录最大利润
  int maxprofit = Integer.MIN_VALUE;
  //记录当前最低价格，初始化不能是0，应该是第一天的价格
  int minprice = prices[0];
  for(int i = 0 ; i < prices.length;i++){
    maxprofit = Math.max(maxprofit,prices[i] - minprice);//更新最大利润
    minprice = Math.min(minprice,prices[i]);//更新最低价格
  }
  return maxprofit;
}

Best Time to Buy and Sell Stock II

题目

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

相比Best Time to Buy and Sell Stock I，可以多次买卖，计算可获得的最大利润

思路

计算每一天跟前一天的价格差，将价格差大于0 的利润累加，就是获得的最大利润

public int maxProfit(int[] prices) {
    int max = 0;
    for(int i = 1 ; i < prices.length;i++){
        int delta = prices[i] - prices[i-1];
        if(delta > 0){
            max += delta;
        }
    }
    return max;
}

Best Time to Buy and Sell Stock III

题目

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

可以交易两次，设计算法求出最大利润

分析

可以交易两次，可将数组分成左右两段，分别计算左段和右段的最大值

可以采用两次遍历，第一次从左向右，计算从0到i的最大利润，存在maxprofits[i]里。

第二次从右向左，计算从i到0的最大利润

maxprofit[i] = maxprofitfromleft[i]+maxprofitfromright[i]

以第i天为分割点的最大利润 = 从0到i的最大利润+从i到末尾的最大利润之和

以第i天为分割点在左右同时计算，包含了只交易一次，即第i天不买不卖的操作

代码

public int maxProfit(int[] prices) {
        int maxresult = 0;//最终结果
        int minprice = Integer.MAX_VALUE;
        int maxprofitfromleft = 0;
        int[] maxprofits = new int[prices.length];//记录从0到i的最大利润
        //计算从前到i最大利润
        for(int i = 0 ; i < prices.length;i++){
            minprice = Math.min(minprice,prices[i]);
            maxprofitfromleft = Math.max(maxprofitfromleft,prices[i] - minprice);
            maxprofits[i] = maxprofitfromleft;
        }
        //计算从后到i最大利润+从前导i-1最大利润和
        int maxprice = Integer.MIN_VALUE;
        int maxprofitformright = 0;
        for(int i = prices.length - 1;i > 0;i--){
            maxprice = Math.max(maxprice,prices[i]);//从后向前最高价格
            maxprofitformright = Math.max(maxprofitformright,maxprice - prices[i]);//从后向前最大利润
            maxresult = Math.max(maxresult,maxprofitformright + maxprofits[i]);
        }
        return maxresult;
    }

Best Time to Buy and Sell Stock with Transaction Fee

题目

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:

> Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
> Output: 8
> Explanation: The maximum profit can be achieved by:
> Buying at prices[0] = 1Selling at prices[3] = 8Buying at prices[4] = 4Selling at prices[5] = 9The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
>

不限制交易次数，但需支付交易费用，求最大利润

分析

方法一：

规定：
1.买入时扣费,扣交易费
2.卖出时计算收益
符号定义：
cash:在第i天不持股所获最大利润
hold:在第i天持股所获最大利润
转移方程：
在第i天cash状态的例如来源于两个方面：
  1.前一天cash，第i天不操作
  2.前一天hold，第i天卖出，收益prices[i]
在第i天hold状态的例如来源于两个方面：
  1.前一天hold，第i天不操作
  2.前一天cash，第i天买入，扣去prices[i]和交易费用fee
因此状态转移方程为：
temp = cash
cash = max(cash,hold + price[i])
hold = max(hold,cash - price[i] - fee)
  
返回值：
cash 最后一天结束时不持股的最大利润
初始化：
cash = 0 第0天不持股，利润为0
hold = -prices[0] - fee 为了使第一天买入时利润为0，将第0天持股，利润设置为 ：-prices[0] - fee
代码：
    public int maxProfit(int[] prices, int fee) {
        int cash = 0;
        int hold = -prices[0] - fee;
        for(int i = 0 ; i < prices.length;i++){
        	int temp = cash;
            cash = Math.max(cash,hold + prices[i]);
            hold = Math.max(hold,temp - prices[i] - fee);
        }
        return cash;
    }

方法二：

规定：
1.买入时计算交易次数，扣费,扣交易费
2.卖出时计算收益
符号定义：T表示收益
T[i][0]表示到第i天，第i天不持股
T[i][1]表示到第i天，第i天持股
转移方程：
【第i天交易k次不持股】的状态可以由两种情况可以产生：
    1.不卖：第i-1天不持股，第i天不操作
    2.卖：第i-1天持股，第i天卖掉，得到收益prices[i]
【第i天交易k次持股】的状态可以由两种情况可以产生：
    1.不买：第i-1天持股，第i天不操作  
    2.买：第i-1天不持股，第i天买入，花费prices[i]+fee
综上，转移方程为：
T[i][0] = Math.max(T[i-1][0],T[i-1][1] + prices[i])
T[i][1] = Math.max(T[i-1][1]，T[i-1][0] - prices[i]-fee)
  
初始化：
T[0][1] = -Infinity; 
返回值：
T[i][0]:最后一天用光所有交易次数不持股的最大利润
代码：
public int maxProfit(int[] prices, int fee) {
  int profit[][] = new int[prices.length+1][2];
  profit[0][1] = - prices[0] - fee;
  for(int i = 1 ; i <= prices.length;i++){
    profit[i][0] = Math.max(profit[i-1][0],profit[i-1][1] + prices[i-1]);
    profit[i][1] = Math.max(profit[i-1][1],profit[i-1][0] - prices[i-1] - fee);
  }
  return profit[prices.length][0];
}

Best Time to Buy and Sell Stock with Cooldown

题目

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

  • You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
  • After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

> prices = [1, 2, 3, 0, 2]
> maxProfit = 3
> transactions = [buy, sell, cooldown, buy, sell]
>

买卖股票存在一天的冷却期，卖出股票后第二天不可以买入，需要冷却一天，求最大利润。

分析

方法一：

方法二：

规定：
1.买入时计算交易次数，扣费
2.卖出时计算收益
符号定义：T表示收益
T[i][0]表示到第i天，第i天不持股
T[i][1]表示到第i天，第i天持股
转移方程：
【第i天不持股】的状态可以由两种情况可以产生：
    1.不卖：第i-1天不持股，第i天不操作
    2.卖：第i-1天持股，第i天卖掉，得到收益prices[i]
【第i天持股】的状态可以由两种情况可以产生：
    1.不买：第i-1天持股，第i天不操作  
    2.买：第i-2天不持股，第i天买入，花费prices[i]
综上，转移方程为：
T[i][0] = Math.max(T[i-1][0],T[i-1][1] + prices[i])
T[i][1] = Math.max(T[i-1][1]，T[i-2][0] - prices[i])
  
初始化：
T[i][0] = T[-1][0] = 0; //前i天无操作，利润为0；没有股票利润为0
T[i][1] = T[-1][1] = -Infinity; //前i天无操作持股，没有股票持股，不可能，利润为负无穷
返回值：
T[i][0]:最后一天用光所有交易次数不持股的最大利润
代码：
    public int maxProfit(int[] prices) {
        if(prices.length <= 1){
            return 0;
        }
        int[][] profit = new int[prices.length+2][2];
        profit[0][1] = Math.max(-prices[0],-prices[1]);
        profit[1][1] = -prices[0];
        for(int i = 2;i <= prices.length+1;i++){
            profit[i][0] = Math.max(profit[i-1][0],profit[i-1][1] + prices[i-2]);
            profit[i][1] = Math.max(profit[i-1][1],profit[i-2][0] - prices[i-2]);
        }
        return profit[prices.length+1][0];
    }

Best Time to Buy and Sell Stock IV

题目

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

最多可以买卖k次，求最大收益

分析

动态规划的思想，下面是一种通用解法，前面的题目也同样适用

规定：
1.买入时计算交易次数，扣费
2.卖出时计算收益
符号定义：T表示收益
T[i][k][0]表示到第i天，交易k次，第i天不持股
T[i][k][1]表示到第i天，交易k次，第i天持股
转移方程：
【第i天交易k次不持股】的状态可以由两种情况可以产生：
    1.不卖：第i-1天不持股，之前操作k次，第i天不操作
    2.卖：第i-1天持股，之前操作k次，第i天卖掉，得到收益prices[i]
【第i天交易k次持股】的状态可以由两种情况可以产生：
    1.不买：第i-1天持股，之前操作k次，第i天不操作  
    2.买：第i-1天不持股，之前操作k-1次，第i天买入，花费prices[i]
综上，转移方程为：
T[i][k][0] = Math.max(T[i-1][k][0],T[i-1][k][1] + prices[i])
T[i][k][1] = Math.max(T[i-1][k][1]，T[i-1][k-1][0] - prices[i])
  
初始化：
T[i][0][0] = T[-1][k][0] = 0; //前i天无操作，利润为0；没有股票利润为0
T[i][0][1] = T[-1][k][1] = -Infinity; //前i天无操作持股，没有股票持股，不可能，利润为负无穷
返回值：
T[i][k][0]:最后一天用光所有交易次数不持股的最大利润

代码

public int maxProfit(int k, int[] prices) {
  if(prices.length == 0 || k <= 0){
    return 0;
  }
  if(k >= prices.length/2){
    int profit = 0;
    for (int i = 1 ; i < prices.length;i++){
      if(prices[i] >= prices[i-1]){
        profit += prices[i] - prices[i-1];
      }
    }
    return profit;
  }
  int[][][] profit = new int[prices.length+1][k+1][2];
  //初始化
  for(int i = 0;i <= prices.length;i++){//前i天无操作，持股，不可能
    profit[i][0][1] = Integer.MIN_VALUE;
  }
  for(int i = 0 ; i <= k;i++){//没有股票持股，不可能
    profit[0][i][1] = Integer.MIN_VALUE;
  }
  for(int kk = 1 ; kk <= k ; kk++){
    for(int i = 1 ; i <= prices.length;i++){
      profit[i][kk][0] = Math.max(profit[i-1][kk][0],profit[i-1][kk][1] + prices[i-1]);
      profit[i][kk][1] = Math.max(profit[i-1][kk][1],profit[i-1][kk-1][0] - prices[i-1]);
    }
  }
  return profit[prices.length][k][0];
}

Two Sum问题

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

> Given nums = [2, 7, 11, 15], target = 9,
>
> Because nums[0] + nums[1] = 2 + 7 = 9,
> return [0, 1].
>

方法一：遍历，用hash表存储下来，然后遍历数组i,在hash表中查找是否有target-i

方法二：

2  3  7  9  11  18 ,target=16
↑                ↑
i                j
步骤：
1. 排序，需要把元素在原来数组中的idx存下来
2. 两个指针i,j，i指向头，j指向尾
3.if(nums[i]+nums[j] < targert) i++
  if(nums[i]+nums[j] > targert) j--
  if(nums[i]+nums[j] == targert) return

若给定数组是有序的Two Sum II - Input array is sorted用方法二就非常简单了

public int[] twoSum(int[] nums, int target) {
    int[] result = new int[2];
    Arrays.sort(nums);
    int i = 0;
    int j = nums.length - 1;
    while(i < j){
        if(nums[i] + nums[j] == target){
            result[0] = i;
            result[1] = j;
            return result;
        }
        else if(nums[i] + nums[j] < target){
            i++;
        }
        else {
            j--;
        }
    }
    return result;
}

3Sum

题目

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

Note: The solution set must not contain duplicate triplets.

> For example, given array S = [-1, 0, 1, 2, -1, -4],
>
> A solution set is:
> [
>   [-1, 0, 1],
>   [-1, -1, 2]
> ]
>

方法

方法一：hash + 遍历 , 空间 + 时间

方法二：排序后two pointer，空间 + 时间

  1. 排序
  2. 求a+b+c = target
    固定a ， 然后对b + c利用Two Sum方法
  3. 需要注意的是遍历时要跳过重复的元素

代码

public List<List<Integer>> threeSum(int[] nums) {
  List<List<Integer>> results = new ArrayList<>();
  //排序
  Arrays.sort(nums);
  //遍历a
  for(int a = 0; a < nums.length -3;a++){
    //跳过重复元素
    if(a > 0 && nums[a] == nums[a-1]){
      continue;
    }
    //b和c做TwoSum
    int b = a+1;
    int c = nums.length-1;
    while(b < c){
      //找到了一组解
      if(nums[b] + nums[c] + nums[a] == 0){
        ArrayList<Integer> result = new ArrayList<>();
        result.add(nums[a]);
        result.add(nums[b]);
        result.add(nums[c]);
        results.add(result);
        b++;
        c--;
        // 跳过重复的 , 一定要注意这里，我自己没做上
        while (b < c && nums[b] == nums[b - 1]){
          b++;
        }
        while (b < c && nums[c] == nums[c + 1]){
          c--;
        }
      }
      else if(nums[b] + nums[c]+ nums[a] < 0){
        b++;
      }
      else {
        c--;
      }
    }
  }
  return results;
}

3Sum Closest

题目

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

>     For example, given array S = {-1 2 1 -4}, and target = 1.
>
>     The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
>

思路

跟上一题一样的思路，计算nums[b] + nums[c] + nums[a] - target的值：

  1. nums[b] + nums[c] + nums[a] - target == 0，最小差为0，直接返回
  2. nums[b] + nums[c] + nums[a] - target < 0,跟新最小差，b++
  3. nums[b] + nums[c] + nums[a] - target > 0,跟新最小差，c—

代码

public int threeSumClosest(int[] nums, int target) {
  //排序
  Arrays.sort(nums);
  int min_delta = Integer.MAX_VALUE;//记录最小差值
  int sum = 0;//记录最小差值时三个数字和
  //遍历a
  for(int a = 0; a < nums.length - 2;a++){
    //跳过重复元素
    if(a > 0 && nums[a] == nums[a-1]){
      continue;
    }
    //b和c做TwoSum
    int b = a+1;
    int c = nums.length-1;
    while(b < c){
      //找到和target相等的情况
      if(nums[b] + nums[c] + nums[a] - target == 0){
        sum = target;
        return sum;
      }
      else if(nums[b] + nums[c] + nums[a] < target){
        int delta = Math.abs(nums[b] + nums[c] + nums[a] - target);
        if(delta < min_delta){
          min_delta = delta;
          sum = nums[b] + nums[c] + nums[a];
        }
        b++;
        while(b < c && nums[b] == nums[b-1]){
          b++;
        }
      }
      else {
        int delta = Math.abs(nums[b] + nums[c] + nums[a] - target);
        if(delta < min_delta){
          min_delta = delta;
          sum = nums[b] + nums[c] + nums[a];
        }
        c--;
        while(b < c && nums[c] == nums[c+1]){
          c--;
        }
      }
    }
  }
  return sum;
}

3Sum Smaller

题目

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

> [-2, 0, 1]
> [-2, 0, 3]
>
>

>

Follow up:
Could you solve it in O(n2) runtime?

思路

这道题没有说清楚，重复的元素也可以，步骤如下：

  1. 排序
  2. 从0到len-3遍历a，b从a+1到len-2，c从len-1到b+1
  3. 确定a和b的位置之后，c从后向前遍历，寻找第一个满足nums[b] + nums[c] + nums[a] < target的位置，则从当前的b+1到找到的c的位置之间的c-b个位置都可以作为c，使得nums[b] + nums[c] + nums[a] < target

代码

public int threeSumSmaller(int[] nums, int target) {
  int res = 0;
  Arrays.sort(nums);
  //遍历a
  for(int a = 0; a < nums.length - 2;a++) {
    //b和c做TwoSum
    int b = a + 1;
    int c = nums.length - 1;
    while (b < c) {
      while (b < c && nums[b] + nums[c] + nums[a] >= target) {
        c--;
      }//跳出时nums[b] + nums[c] + nums[a] < target,或者b==c了
      //找到了第一个c的位置使得nums[b] + nums[c] + nums[a] < target
      if(b < c && nums[b] + nums[c] + nums[a] < target){
        res += c - b;//b+1~c之间的元素都可以做c满足nums[b] + nums[c] + nums[a] < target
      }
      b++;
      c = nums.length - 1;
    }
  }
  return res;
}

4Sum

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

Note: The solution set must not contain duplicate quadruplets.

> For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
>
> A solution set is:
> [
>   [-1,  0, 0, 1],
>   [-2, -1, 1, 2],
>   [-2,  0, 0, 2]
> ]
>
>

跟前面一样的思路，固定a，b对c,d做2Sum

代码

public List<List<Integer>> fourSum(int[] nums, int target) {
  List<List<Integer>> results = new ArrayList<>();
  //排序
  Arrays.sort(nums);
  //遍历a
  for(int a = 0; a < nums.length - 3;a++){
    //跳过重复元素
    if(a > 0 && nums[a] == nums[a-1]){
      continue;
    }
    for(int b = a+1;b < nums.length - 2;b++){
      //跳过重复元素
      if(b > a+1 && nums[b] == nums[b-1]){
        continue;
      }
      //c和d做TwoSum
      int c = b+1;
      int d = nums.length-1;
      while(c < d){
        //找到了一组解
        if(nums[b] + nums[c] + nums[d] + nums[a] == target){
          ArrayList<Integer> result = new ArrayList<>();
          result.add(nums[a]);
          result.add(nums[b]);
          result.add(nums[c]);
          result.add(nums[d]);
          results.add(result);
          c++;
          d--;
          // 跳过重复的 , 一定要注意这里，我自己没做上
          while (c < d && nums[c] == nums[c - 1]){
            c++;
          }
          while (c < d && nums[d] == nums[d + 1]){
            d--;
          }
        }
        else if(nums[b] + nums[c] + nums[d] + nums[a] < target){
          c++;
        }
        else {
          d--;
        }
      }
    }
  }
  return results;
}

4Sum II

题目

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

> Input:
> A = [ 1, 2]
> B = [-2,-1]
> C = [-1, 2]
> D = [ 0, 2]
>
> Output:
> 2
>
> Explanation:
> The two tuples are:
> 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
> 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
>
>

给四个数组，从每个数组中选一个数字，和为0的选择方案有多少

思路

方法一：直接遍历四个数组，复杂度

方法二：AB为一组，CD为一组，用两个hashmap记录两组中出现的和及其出现次数，互为相反数的和为0。

改进：存储两个hashmap再遍历速度很慢，所以只计算AB的和存入hashmap，然后计算CD时去AB的hashmap中寻找-sum出现的次数累加到result上即可。

代码

public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int result = 0;
        HashMap<Integer,Integer> mapab = new HashMap<>();
        //计算AB的和，存入hashmap
        for(int i = 0;i < A.length;i++){
            for(int j = 0 ; j < A.length;j++){
                int sumab = A[i]+B[j];
                if(mapab.containsKey(sumab)){
                    mapab.put(sumab,mapab.get(sumab)+1);
                }
                else{
                    mapab.put(sumab,1);
                }
            }
        }
        for(int i = 0;i < A.length;i++){
            for(int j = 0 ; j < A.length;j++){
                int sum = C[i] + D[j];
                if(mapab.containsKey(-sum)){
                    result += mapab.get(-sum);
                }
            }
        }
        return result;
    }

Valid Triangle Number

题目

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

> Input: [2,2,3,4]
> Output: 3
> Explanation:
> Valid combinations are: 
> 2,3,4 (using the first 2)
> 2,3,4 (using the second 2)
> 2,2,3
>

选取三个数组作为三边长度，返回能够组成三角形的选取方案数

思路

构成三角形条件：两边之和大于第三边

  1. 排序，两个小边之和大于第三边
  2. 固定a，遍历b、c，寻找第一个nums[a] + nums[b] > nums[c]的位置
  3. bc之间的位置都可以作为c，使得nums[a] + nums[b] > nums[c]，result+= c-b。

代码

public int triangleNumber(int[] nums) {
  int result = 0;
  Arrays.sort(nums);
  //遍历a
  for(int a = 0; a < nums.length - 2;a++){
    //b和c做TwoSum
    int b = a+1;
    int c = nums.length-1;
    while(b < c){
      while(b < c && nums[a] + nums[b] <= nums[c]){
        c--;
      }//跳出时nums[a] + nums[b] > nums[c]或者b==c
      if(b < c && nums[a] + nums[b] > nums[c]){
        result += c-b;
      }
      b++;
      c = nums.length - 1;
    }
  }
  return result;
}

Partition类问题

不开额外的空间，用两个指针分成两个、三个部分，利用quicksort的思想

partition Array

题目

Given an array nums of integers and an int k, partition the array (i.e move the elements in “nums”) such that:

  • All elements < k are moved to the left
  • All elements >= k are moved to the right

Return the partitioning index, i.e the first index i nums[i] >= k.

Example

If nums = [3,2,2,1] and k=2, a valid answer is 1.

分析

利用quicksort的思想，两指针一前一后向中间遍历，前面遇到大的，后面遇到小的交换，最后判断nums[j]和target的大小关系，返回结果。

代码

public int partitionArray(int[] nums, int k) {
    if(nums.length==0){
        return 0;
    }
    // write your code here
    int i = 0;
    int j = nums.length - 1;
    while(i < j){
        while(i < j && nums[i] < k){
            i++;
        }
        while(i < j && nums[j] >= k){
            j--;
        }//j右边都>=k
        if(i < j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    if(nums[j] >= k){
        return j;
    }
    else {
        return j+1;
    }
}

两个指针，利用快速排序

Sort Colors

题目

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

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

思路

方法一：计数排序，遍历，记录0,1,2出现的个数，然后重新输出，时间复杂度

方法二：两次partition，先把0分一堆，1，2分一堆，然后再把1,2分开

public void sortColorsPartition(int[] nums){
  if(nums.length <= 1){
    return;
  }
  int i = 0;
  int j = nums.length-1;
  //先分成左边都<1，右边>=1
  while(i <= j){
    while(i <= j && nums[i] < 1){
      i++;
    }//i是第一个>=1的位置，或者是与j相遇且过了
    while(i <= j && nums[j] >= 1){
      j--;
    }//j是第一个<1的位置，或者是与i相遇且过了
    //如果还未相遇，交换ij元素，如果恰好相遇，
    if(i <= j){
      int temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
      i++;
      j--;
    }
  }
  //对右半段，分成成左边都<2，右边>=2
  j = nums.length-1;
  while(i <= j){
    while(i <= j && nums[i] < 2){
      i++;
    }//i是第一个>=1的位置，或者是与j相遇了
    while(i <= j && nums[j] >= 2){
      j--;
    }//j是第一个<1的位置，或者是与i相遇了
    if(i <= j){
      int temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
      i++;
      j--;
    }
  }
}

方法三：背程序，三个指针三分法。

  1. i，j指向头和尾，mid在中间
  2. mid向后遍历，遇到0与i交换，遇到2与j交换
public void sortColors(int[] nums) {
  if(nums.length <= 1){
    return;
  }
  int i = 0;
  int j = nums.length-1;
  int mid = 0;
  while(mid <= j){
    if(mid <= j && nums[mid] == 1){
      mid++;
    }
    else if(mid <= j && nums[mid] == 0) {
      int temp = nums[i];
      nums[i] = nums[mid];
      nums[mid] = temp;
      mid++;
      i++;
    }
    else {
      int temp = nums[j];
      nums[j] = nums[mid];
      nums[mid] = temp;
      j--;
    }
  }
}

Sort Colors II

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

Example

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

思路

代码

public void sortColors2(int[] colors, int k) {
    // write your code here
    if(colors.length <= 1){
        return;
    }
    int i = 0;
    int j = colors.length-1;
    int kk = 2;
    //先分成左边都<1，右边>=1
    while(kk <= k){
        while(i <= j){
            while(i <= j && colors[i] < kk){
                i++;
            }//i是第一个>=1的位置，或者是与j相遇且过了
            while(i <= j && colors[j] >= kk){
                j--;
            }//j是第一个<1的位置，或者是与i相遇且过了
            //如果还未相遇，交换ij元素，如果恰好相遇，
            if(i <= j){
                int temp = colors[i];
                colors[i] = colors[j];
                colors[j] = temp;
                i++;
                j--;
            }
        }
        j = colors.length-1;
        kk++;
    }
}

Sort Letters by Case

题目

Given a string which contains only letters. Sort it by lower case first and upper case second.

For "abAcD", a reasonable answer is "acbAD"

给一串字母，把小写的排在左边，大写的排在右边

代码

public void sortLetters(char[] chars) {
  // write your code here
  int i = 0;
  int j = chars.length - 1;
  while (i < j){
    while(i < j && chars[i] >= 'a'){
      i++;
    }
    while(i < j && chars[j] <= 'Z'){
      j--;
    }
    if(i < j){
      char temp = chars[i];
      chars[i] = chars[j];
      chars[j] = temp;
      i++;
      j--;
    }
  }
}

Interleaving Positive and Negative Numbers

Given an array with positive and negative integers. Re-range it to interleaving with positive and negative integers.

Example

Given [-1, -2, -3, 4, 5, 6], after re-range, it will be [-1, 5, -2, 4, -3, 6] or any other reasonable answer.

把正的和负的先都挑出来，然后交替放入数组。如果正的多余负的，先放正的，否则先放负的。

public void rerange(int[] A) {
    int[] zheng = new int[A.length];
    int[] fu = new int[A.length];
    // write your code here
    int zhengi = 0;
    int fui = 0;
    for(int i = 0 ; i < A.length;i++){
        if(A[i] < 0){
            fu[fui] = A[i];
            fui++;
        }
        else {
            zheng[zhengi] = A[i];
            zhengi++;
        }
    }
    if(fui < zhengi){
        int i = 0;
        int zhengj = 0;
        int fuj = 0;
        while(i < A.length-2){
            A[i] = zheng[zhengj];
            zhengj++;
            i++;
            A[i] = fu[fuj];
            fuj++;
            i++;
        }
        A[i] = zheng[zhengj];
    }
    else {
        int i = 0;
        int zhengj = 0;
        int fuj = 0;
        while(i < A.length-2){
            A[i] = fu[fuj];
            fuj++;
            i++;
            A[i] = zheng[zhengj];
            zhengj++;
            i++;
        }
        A[i] = fu[fuj];
        i++;
        if(A.length % 2 == 0){
            A[i] = zheng[zhengj];
        }
    }
}

Two pointer问题

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.

给定一个字符串，计算不包含重复字母的最长子串

分析

用滑动窗口做，窗口边界left、right，用数组int[] map = new int[256]存储当前窗口内出现的元素，用maxlen、len_local记录最大长度和当前窗口长度

  1. 初始化left,right=0
  2. right向后滑动，直至遇到窗口中已经存在该元素
  3. left向后滑动，窗口缩小，直至将已经出现过的元素挪到窗口外面
  4. 循环更新local长度和全局最大长度

代码

public int lengthOfLongestSubstring(String s) {
  if(s.length() <= 1){
    return s.length();
  }
  int left = 0;
  int right = 0;
  int maxlen = Integer.MIN_VALUE;
  int len_local = 0;//局部长度
  int[] map = new int[256];
  while(right < s.length()){
    //如果字母还未出现过
    if(map[s.charAt(right)] == 0){
      //存入字母表
      map[s.charAt(right)]++;
      //更新局部长度和全局最大长度
      len_local++;
      maxlen = Math.max(maxlen,len_local);
      right++;
    }
    //出现过
    else {
      //寻找之前该元素出现的位置
      while (s.charAt(left) != s.charAt(right)){
        //路上把滑窗缩减的字母从字母表中去掉
        map[s.charAt(left)]--;
        left++;
        len_local--;
      }//跳出时left和right字母相等
      left++;
      right++;
    }
  }
  return maxlen;
}

Implement strStr()

题目

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

> Input: haystack = "hello", needle = "ll"
> Output: 2
>
>

>

Example 2:

> Input: haystack = "aaaaa", needle = "bba"
> Output: -1
>

分析

方法一：双指针遍历比较判断每一个字符是否一样

方法二：return haystack.indexOf(needle);

方法三：haystack.substring(i, i + needle.length()).equals(needle)

代码

public int strStr(String haystack, String needle) {
  if(needle.length() == 0){
    return 0;
  }
  int i = 0;
  int j = 0;
  int k = 0;
  while(j < haystack.length()){
    //遇到相等的字母
    if(haystack.charAt(i) == needle.charAt(k)){
      //j和k同时向后移动
      while(j < haystack.length() && k < needle.length() && haystack.charAt(j) == needle.charAt(k)){
        j++;
        k++;
      }//跳出时或者到头了或者有不相等的了
      //如果k到头了，说明已经包含了needls
      if(k == needle.length()){
        return i;
      }
      //j到头了，剩下的字符串不够长了，不可能包含了
      else if(j == haystack.length()){
        return -1;
      }
      else {
        i++;
        j = i;
        k = 0;
      }
    }
    //不是相等的字母，ij向后移动
    else{
      i++;
      j++;
    }
  }
  return -1;
}

Reverse Vowels of a String

题目

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = “hello”, return “holle”.

Example 2:
Given s = “leetcode”, return “leotcede”.

Note:
The vowels does not include the letter “y”.

对换元音字母

分析

两指针一前一后向中间遍历，遇到元音对换即可。

这里需要注意的是java的String是不可更改的，需要用StringBuilder复制一份再做修改：result.setCharAt(i,s.charAt(j));

代码

public class ReverseVowelsofaString {
    public boolean isVowel(char ch){
        if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'
                || ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U'){
            return true;
        }
        else return false;
    }
    public String reverseVowels(String s) {
        StringBuilder result = new StringBuilder(s);
        int i = 0;
        int j = s.length() -1;
        while (i < j){
            while(i < j && !isVowel(s.charAt(i))){
                i++;
            }
            while(i < j && !isVowel(s.charAt(j))){
                j--;
            }
            char temp = s.charAt(i);
            result.setCharAt(i,s.charAt(j));
            result.setCharAt(j,temp);
            i++;
            j--;
        }
        return result.toString();
    }
}

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.

有效回文串，判断字符串中的有效字符是否可以构成有效回文串，其中有效字符仅包括字母和数字，大小写算同一个字母

分析

步骤

  1. 需要一个确定是否是有效字符的函数isvalid,利用java中的Character.isLetter()和Character.isDigit()
  2. 两指针一前一后遍历，遇到无效字符跳过，比较两指针指向的字符是否相等，如果不相等直接返回false

代码

private boolean isvalid (char c) {
  return Character.isLetter(c) || Character.isDigit(c);
}
public boolean isPalindrome(String s) {
  int i = 0;
  int j = s.length()-1;
  while (i < j){
    while(i < j && !isvalid(s.charAt(i))){
      i++;
    }
    //全是invalid字符的情况
    if(i == s.length()){
      return true;
    }
    while(i < j && !isvalid(s.charAt(j))){
      j--;
    }
    if(Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))){
      return false;
    }
    i++;j--;
  }
  return true;
}

Valid Palindrome II

题目

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

> Input: "aba"
> Output: True
>
>

>

Example 2:

> Input: "abca"
> Output: True
> Explanation: You could delete the character 'c'.
>

给定字符串，判断如果最多可以去掉一个字符，改字符串是否可以成为回文串

分析

跟上一题的思路有点不太一样，没有想到巧妙的方法

两指针指向头尾，如果两个指针指向元素相等，则i++;j—

如果两指针指向元素不相等，那么s[i+1]~s[j]和s[i]~s[j-1]中必然有一个是回文串

代码

//判断是否是回文串
public boolean isPalindrome(String s,int start,int end){
  if(start == end){
    return true;
  }
  int left = start;
  int right = end;
  while(left < right){
    if(s.charAt(left) != s.charAt(right)){
      return false;
    }
    left++;
    right--;
  }
  return true;
}
public boolean validPalindrome(String s) {
  if(s.length() <= 2){
    return true;
  }
  int i = 0;
  int j = s.length() -1;
  while (i < j){
    if(s.charAt(i) == s.charAt(j)){
      i++;
      j--;
    }
    else{
      return isPalindrome(s,i,j-1) || isPalindrome(s,i+1,j);
    }
  }
  return true;
}

Longest Word in Dictionary through Deleting

题目

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

> Input:
> s = "abpcplea", d = ["ale","apple","monkey","plea"]
>
> Output: 
> "apple"
>
>

>

Example 2:

> Input:
> s = "abpcplea", d = ["a","b","c"]
>
> Output: 
> "a"
>

给定一个字符串s和一个字符串数组d,返回d中字符串是s的子序列的最长字符串，如果有长度相同的则返回在字母表中顺序最靠前的

思路

遍历d中的字符串，看其是否能够由s的子序列构成，如果能，更新最大长度，如果和当前最大长度相等，取字典序小的

代码

//判断是否能够是s的子序列
public boolean issubqueue(String s,String stemp){
  int si = 0;
  int stempi = 0;
  while(si < s.length() && stempi < stemp.length()){
    while(si < s.length() && s.charAt(si) != stemp.charAt(stempi)){
      si++;
    }//跳出时si==len或者遇到相等的了
    if(si == s.length()){
      return false;
    }
    si++;
    stempi++;
  }
  return stempi == stemp.length();
}
public String findLongestWord(String s, List<String> d) {
  int maxlen = Integer.MIN_VALUE;
  String result = new String();
  for(int i = 0;i < d.size();i++){
    String stemp = d.get(i);
    int len = stemp.length();
    boolean flag = issubqueue(s,stemp);
    if(flag){
      if(len > maxlen){
        maxlen = len;
        result= stemp;
      }
      if(len == maxlen && stemp.compareTo(result) < 0){
        result = stemp;
      }
    }
  }
  return result;
}

这里判断t是否是s的子序列存在优化的空间，可以利用Java的String中的indexOf(char,indexfrom)来判断。

//s是否包含t
private boolean isContain(String s,String t){
  if(t.length() > s.length()){
    return false;
  }
  int pos = 0;
  for(int i = 0; i < t.length();i++){
    pos = s.indexOf(t.charAt(i),pos);
    if(pos != -1){
      pos++;
    }
    else {return false;}
  }
  return true;
}

Permutation in String

题目

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

> Input:s1 = "ab" s2 = "eidbaooo"
> Output:True
> Explanation: s2 contains one permutation of s1 ("ba").
>

>

Example 2:

> Input:s1= "ab" s2 = "eidboaoo"
> Output: False
>

给定字符串s1和s2，返回s2中是否包含一个子串，使得该子串可以由s1中字母的某种排列方式构成。

分析

滑动窗口法，窗口长度设置为s1的长度，在s2中寻找s1的排列子串

窗口向右滑动，直到窗口内出现的字母以及每个字母出现的次数和s1中一样，此时找到了满足条件的子数组。

将s1中出现的字母和每个字母出现的次数记录在一个hashtable中，因为只有26个字母，可以用一个长度为26的数组记录每个字母出现的次数

代码

public boolean isSame(int[] s1map,int[] s2map){
  for(int i = 0 ; i < 26;i++){
    if(s1map[i] != s2map[i]){
      return false;
    }
  }
  return true;
}
public boolean checkInclusion(String s1, String s2) {
  if(s1.length() > s2.length()){
    return false;
  }
  int[] s1map = new int[26];
  int[] s2map = new int[26];
  for(int i = 0 ; i < s1.length();i++){
    s1map[s1.charAt(i) - 'a']++;
    s2map[s2.charAt(i) - 'a']++;
  }
  for(int i = 0 ; i < s2.length() - s1.length();i++){
    if(isSame(s1map,s2map)){
      return true;
    }
    s2map[s2.charAt(s1.length()+i) - 'a']++;
    s2map[s2.charAt(i) - 'a']--;
  }
  return isSame(s1map,s2map);
}

改进

这里判断字符串相等还有可以优化的空间，用变量count表示当前窗口内和s1出现相同次数的字母的个数，当count == 26，则所有的字母都出现相同次数了，找到了解。当滑窗向后移动时，需要更新count

public boolean checkInclusion2(String s1, String s2) {
  if(s1.length() > s2.length()){
    return false;
  }
  int count = 0;
  int[] s1map = new int[26];
  int[] s2map = new int[26];
  for(int i = 0 ; i < s1.length();i++){
    s1map[s1.charAt(i) - 'a']++;
    s2map[s2.charAt(i) - 'a']++;
  }
  for(int i = 0 ; i < 26;i++){
    if(s1map[i] == s2map[i]){
      count++;
    }
  }
  for(int i = 0 ; i < s2.length() - s1.length();i++){
    int r = s2.charAt(s1.length()+i) - 'a';
    int l = s2.charAt(i) - 'a';
    //所有字母出现次数相等
    if(count == 26){
      return true;
    }
    //窗口将右边元素加入
    s2map[r]++;
    if(s1map[r] == s2map[r]){//新加入元素后这个元素变得个数相等了
      count++;
    }
    else if(s2map[r] == s1map[r]+1){//新加入元素后比s1多一个了
      count--;
    }
    ////窗口将左边元素去掉
    s2map[l]--;
    if(s1map[l] == s2map[l]){
      count++;
    }
    else if(s1map[l] == s2map[l]+1){
      count--;
    }
  }
  return count == 26;
}

Subarray Product Less Than K

题目

Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:

> Input: nums = [10, 5, 2, 6], k = 100
> Output: 8
> Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
> Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
>

分析

滑窗+两指针i,j题:

如果窗口内乘积>=k，i++,窗口缩小

如果滑窗内乘积<k，窗口内包含的以j为结束的子数组个数为j-i+1

代码

public int numSubarrayProductLessThanK(int[] nums, int k) {
  int start = 0;
  int end = 0;
  int product = 1;
  int count = 0;
  while(start < end && end < nums.length){
    product *= nums[end];
    while (start < end && product >= k){
      product /= nums[start];
      start++;
    }
    count += end - start +1;
    end++;
  }
  return count;
}

其他

Wiggle Sort II

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

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

Note:
You may assume all input has valid answer.

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

分析

方法一：

这道题给了我们一个无序数组，让我们排序成摆动数组，满足nums[0] < nums[1] > nums[2] < nums[3]…，并给了我们例子。我们可以先给数组排序，然后在做调整。调整的方法是找到数组的中间的数，相当于把有序数组从中间分成两部分，然后从前半段的末尾取一个，在从后半的末尾取一个，这样保证了第一个数小于第二个数，然后从前半段取倒数第二个，从后半段取倒数第二个，这保证了第二个数大于第三个数，且第三个数小于第四个数，以此类推直至都取完。

follow up：要求空间复杂度O(1)，没做上，要问下邓邓

代码

public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int end = nums.length-1;
        int mid = end/2;
        boolean flag = false;
        int[] copy = new int[nums.length];
        int idx = 0;
        while(idx < nums.length){
            if (flag == false){
                copy[idx] = nums[mid];
                mid--;
                flag = true;
            }
            else {
                copy[idx] = nums[end];
                end--;
                flag = false;
            }
            idx++;
        }
        for(int i = 0 ; i < nums.length;i++){
            nums[i] = copy[i];
        }
    }

Super Ugly Number

题目

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

给定n和素数序列，返回第n个ugly number:因子只能出现在素数序列中

分析

用上面的hashmap+heap的方法会超时，看了九章的答案和网上大神们给出的答案，才看明白啥意思

以上一题prime只有三个数字2,3,5为例，我们知道丑陋数序列可以拆分为下面3个子列表：

(1) 1x2, 2x2, 2x2, 3x2, 3x2, 4x2, 5x2…

(2) 1x3, 1x3, 2x3, 2x3, 2x3, 3x3, 3x3…

(3) 1x5, 1x5, 1x5, 1x5, 2x5, 2x5, 2x5…

仔细观察上述三个列表，我们可以发现每个子列表都是一个丑陋数分别乘以2,3,5，而要求的丑陋数就是从已经生成的序列中取出来的，我们每次都从三个列表中取出当前最小的那个加入序列，比如第一次，ugly number当前只有1，分别于2,3,5相乘之后得到2,3,5三个数字，此时除1外，最小的是2，因此先把2加入ugly number 里，然后此时2就可以与当前ugly number中比1大的下一个数字相乘，与上一轮的3,5，进行比较了，。。。

因此，上面的规律总结起来就是：

  1. 一共进行n轮计算和选择
  2. 每轮计算a*b，其中b是给定的prime列表中的数字，a是ugly number中的数字
  3. 每一轮选择本轮（本列）最小的元素加入ugly number,下一轮该行所选取的”a”的idx后移一位。

代码

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] uglyNumbers = new int[n];
        int[] idx = new int[primes.length];
        uglyNumbers[0] = 1;
        for(int i = 1;i < n;i++){
            int min = Integer.MAX_VALUE;
            for(int j = 0 ; j < primes.length;j++){
                min = Math.min(min,primes[j] * uglyNumbers[idx[j]]);
            }
            uglyNumbers[i] = min;
            for(int j = 0;j < primes.length;j++){
                if(min == primes[j] * uglyNumbers[idx[j]]){
                    idx[j]++;
                }
            }
        }
        return uglyNumbers[n-1];
    }
}

Meeting Rooms II

题目

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

给定一个interval序列，代表会议的开始和结束时间，返回需要的最大会议室数量，也就是同时开会的最大数量。

分析

方法一：扫描线的思路+heap实现

将会议的开始和结束时间排序，然后从较小的开始遍历，初始sum=0,遇到start+1,遇到end-1，过程中最大的sum即为同时召开的最大会议数量。要注意的是，遇到同一时刻既有会议开始也有会议结束时应该先访问end，将sum-1,然后再访问start.

需要用小顶堆维护会议开始和结束时间，小顶堆的判断依据为time和Start or End

Comparator<Node> tmp = new Comparator<Node>() {
  @Override
  public int compare(Node o1, Node o2) {
    if(o1.time != o2.time) return o1.time - o2.time;
    else{
      if(o1.isStart == true){
        return 1;
      }
      else return -1;
    }
  }
};

方法二：

将所有开始时间和结束时间分别放入两个数组，分别排序，然后两指针一个指向开始数组i，一个指向结束数组j，初始化sum = 0;

i后移时sum++;

j后移时sum—;

当指向开始数组的指针>=结束数组指针所指的值时，结束数组向后移动一位，否则开始指针后移。

代码

方法一：

import java.util.Comparator;
import java.util.PriorityQueue;
public class MeetingRoomsII {
    public class Interval {
        int start;
        int end;
        Interval() { start = 0; end = 0; }
        Interval(int s, int e) { start = s; end = e; }
    }
    class Node{
        int time;
        boolean isStart;
        Node(int time,boolean isStart){
            this.time = time;
            this.isStart = isStart;
        }
    }
    public int minMeetingRooms(Interval[] intervals) {
        Comparator<Node> tmp = new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.time != o2.time) return o1.time - o2.time;
                else{
                    if(o1.isStart == true){
                        return 1;
                    }
                    else return -1;
                }
            }
        };
        PriorityQueue<Node> heap = new PriorityQueue<>(tmp);
        for(int i = 0 ; i < intervals.length;i++){
            heap.add(new Node(intervals[i].start,true));
            heap.add(new Node(intervals[i].end,false));
        }
        int max = 0;
        int sum = 0;
        while(!heap.isEmpty()){
            if(heap.poll().isStart){
                sum++;
                max = Math.max(max,sum);
            }
            else {sum--;}
        }
        return max;
    }
}

方法二：

public int minMeetingRooms(Interval[] intervals) {
    int[] starts = new int[intervals.length];
    int[] ends = new int[intervals.length];
    for(int i = 0 ; i < intervals.length;i++){
        starts[i] = intervals[i].start;
        ends[i] = intervals[i].end;
    }
    Arrays.sort(starts);
    Arrays.sort(ends);
    int max = 0;
    int sum = 0;
    int j = 0;
    int i = 0;
    while(i < starts.length && j < ends.length){
        if(starts[i] < ends[j]){
            sum++;
            max = Math.max(max,sum);
        }
        else {
            j++;
            sum--;
        }
    }
    return max;
}

The Skyline Problem

题目

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

Buildings

Skyline Contour

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ].

The output is a list of “key points“ (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

给定建筑物的坐标和高度，有重叠，计算轮廓

思路

扫描线

代码