Notes by Louisa
Notes by Louisa
Notes by Louisa
  • Introduction
  • Chapter1 Python Cheatsheet
    • Reference, Deep Copy and Shallow Copy
    • Iterators
    • List Comprehensions
    • Numpy
    • Pandas
    • Data Visualization
    • DateTime
    • Python Good to knows
  • Chapter2 Java Cheatsheet
    • Fundamentals to Java
    • Interface, Abstract Class, Access Modifier, Exceptions
    • Linked List and Java List
    • Java Queue, Stack and Deque
    • Binary Tree
    • Heap in Java
    • Map/Set/Hash
    • OOD
  • Chapter3 Algorithm
    • Fundamental Knowledge
    • Binary Search
    • Basic Sorting
    • Advanced Sorting
    • Linked List
    • Recursion 1
    • HashTable
    • Queue
    • Sliding Window
    • Stack
    • Binary Tree
    • Binary Search Tree
    • Heap
    • String
    • Graph Search DFS1 (Back Tracking)
    • Recursion II and Memoization
    • Dynamic Programming
    • Complete Binary Tree, Segment Tree, Trie Tree
    • Graph Search BFS
    • Graph Search BFS 2
    • Graph Search DFS2
    • Problems from 'JianZhi Offer'
    • Problems Categorized
    • Bit Operations
  • Chapter4 Model
    • Linear Regression
    • Logistic Regression
    • Regularization and Feature Selection
    • Model Evaluation
    • Nonlinear Models
    • PCA
    • Unsupervised Learning
    • Gradient Descent and Gradient Boosting
    • XG Boost and Light GBD
    • Deep Learning
    • Tensorflow/Keras
    • RNN
  • Chapter5 Statistics and A/B Testing
    • Inference about independence
    • Probability, Sampling and Randomization with Python
    • A/B Testing
    • Stats Interview Review
    • Statistics Glossary
  • Chapter6 SQL
    • Student Scores Query
    • Order Query
    • Movie Rating Query
    • Social-Network Query
    • LeetCode SQL题目总结
    • Spark SQL
  • Chapter7 Big Data and Spark
    • Introduction to Pyspark
    • Data Cleaning with Apache Spark
    • Feature Engineering with Pyspark
    • Building Recommendation Engines with Pyspark
    • Building Data Engineering Pipelines in Python
    • Hadoop MapReduce
    • Big Data Related Paper
  • Chapter8 Code Walk-Throughs
    • Python
    • R
    • Shell
  • Chapter9 Special Topics
    • Anomaly Detection
    • E Commerce
    • Supply Chain
    • Social Network Analysis
    • NLP intro
    • Time Series
    • Challenge Prophet with LSTM models
  • Project: The Winning Recipes to an Oscar Award
  • Project: A Crime Analysis of the Last Decade NYC
  • Project: Predict User Type Based on Citibike Data
  • GeoSpark/GeoSparkVis for Geospatial Big Data
  • Single Scattering Albedo
  • Sea Ice Albedo Retrievals
  • Lidar Project
Powered by GitBook
On this page
  • Memoization
  • 普通的Fibo
  • 优化重复计算Fibo
  • 从小到大填表
  • 一维原始数据,求最大、最小
  • Longest Ascending Subarray
  • Maximal Product When Cutting Rope
  • Dictionary Problem
  • Jump Game 1
  • Jump Game 2
  • Largest Sum of Subarray
  • Maximum subarray sum in a circular array.
  • Max subarray sum with at least size k
  • Unsorted Array 最长连续1
  • 十字架
  • X
  • 空心1
  • 火柴
  • 任意subarray sum
  • sum最大的长方形
  • 二维
  • Edit Distance
  • Largest Square of 1's in a Binary Matrix
  1. Chapter3 Algorithm

Dynamic Programming

Memoization

普通的Fibo

public int fibN(int n) {
    if (n==0||n==1) {
        return n;
    }
    return fibN(n-1)+fibN(n-2);
}

优化重复计算Fibo

int[] memo; //or HashMap, <key = Integer (n), value = Integer(Fib(n))>

public int fibN(int n) {
    if (n==0||n==1) {
        return n;
    }
    
    if (memo[n]!=0) {
        return memo[n];
    }
    
    int result= fibN(n-1)+fibN(n-2);
    memo[n] = result;
    return result;
}

Time = O(n) Extra Space = O(n)

从小到大填表

DP的解题方式就是如何定义表格里每个element的意义,以及把表格里的value填满

public int fibN(int n) {
    int[] fibsFound = new int[n+1];
    fibsFound[0] = 0;
    fibsFound[1] = 1;
    for (int i=2; i<=n; i++) {
        fibsFound[i] = fibsFound[i-1] + fibsFound[i-2];
    }
    return fibsFound[n];
}

从小到大记录subsolution

  • base case

  • induction rule

class Solution(object):
  def fibonacci(self, K):
    """
    input: int K
    return: long
    """
    # write your solution here
    if K<=0:
      return 0
    array = [0]*(K+1)
    array[1] = 1
    for i in range (2,K+1):
      array[i] = array[i-2]+array[i-1]
    return array[K]

一维原始数据,求最大、最小

linear scan and look back to the previous elements

Longest Ascending Subarray

class Solution(object):
  def longest(self, array):
    """
    input: int[] array
    return: int
    """
    # write your solution here
    if len(array)==0:
      return 0
    result, curr = 1, 1
    for i in range(1, len(array)):
      if array[i]>array[i-1]:
        curr+=1
        result = max(result, curr)
      else:
        curr=1
    return result

Given an unsorted array, find the length of the longest subarray in which the numbers are in ascending order.

区别sub-array vs sub-sequence:

  • sub-array: contiguous elements in an array

  • sub-sequence: not necessarily contiguous (can jump)

memo[i] 的物理意义: within the range from the 0-th element to the i-th element, the maximum length of the ascending subarray, including the i-th element

index = 0 1 2 3 4 5 6 7
input = 7 2 3 1 5 8 9 6
M[]   = 1 1 2 1 2 3 4 1
globalMax = 4

Base Case: memo[0] = 1 Induction Rule: within the range from the 0-th element to the i-th element, the maximum length of the ascending subarray, including the i-th element M[i] = M[i-1]+1 if input[i-1]<input[i] 1 otherwise

Time = O(n) Space = O(n)

优化空间复杂度O(1)

只存一个元素,previous element

Maximal Product When Cutting Rope

Given a rope with integer-length n, how to cut the rope into m integer-length parts with length p[0], p[1]...p[m-1], in order to get the maximal product of p[0]*p[1]*p[2]...p[m-1], m is determined by you and must be greater than 0 (at least one cut must be made).

Solution 1: DFS (recursion)

先考虑最右边的第一刀cut在哪里,然后再往左切

Time: O(n!)

Solution 2: DP 左大段+右大段

Base Case: size=1 M[1] = invalid //max(maxProd(1), 1) Induction Rule: M[i]的物理意义:i-m rope,cut at least once, what's the maximum product size = 2: there's only 1 way to cut this rope; its M[2] = max (M[1], 1) * max (M[1], 1) = 1*1 = 1 size = 3: there are two possible ways for the first cut case 1: - | - - M[3] = max(M[1],1)*max(M[2],2) = 1*2 = 2 case 2: - - | - M[3] = max(M[2],2)*max(M[1],1) = 2 M[3] = max(case1, case2) = 2

size = 4: there are 3 possible ways for the 1st cut case 1: max(M[1],1)+max(M[3],3) = 1*3 = 3 case 2: max(M[2],2)+max(M[2],2) = 2*2 = 4 case 3: max(M[3],3)+max(M[1],1) = 1*3 = 3 M[4] = max(case1, case2, case3) = 4

return M[n]

Time: O(n^2) 因为linear scan回头看所有元素,所以变成了n^2

Solution 2: DP 左大段+右小段

更general, 适用于最小可分元素是similar but not identical的情况

M[5] = case 1: max(M[4],4)*1 case 2: max(M[3],3)*2 case 3: max(M[2],2)*3 case 4: max(M[1],1)*4

class Solution(object):
  def maxProduct(self, length):
    """
    input: int length
    return: int
    """
    # write your solution here
    if length==2:
      return 1
    array = [0]*(length+1)
    array[2] = 1
    for i in range (3, len(array)):
      for j in range(1, i//2+1):
        array[i] = max(array[i], j*max(i-j, array[i-j]))
    return array[length]

Dictionary Problem

和绳子的题很像。但是只有左大段可以从表格读出来,右小段只能通过题目已知条件获得 大段:读表格,读M[i]的值获取solution;小段:manual操作 所以 左大段+右小段的思路更加general

M[i]的物理意义 前i个字母是否能切成单词的concatenation: true or false

Jump Game 1

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 can reach the last index.

从右往左做linear scan,从终点开始看,只要当前落脚点能True

Base Case: M[length-1] = True, because it's the target itself Induction Rule: M[i] 的物理意义: Whether I can jump from the current index to the target M[i] = true if 存在落脚点j,j在i的右侧,且不超过i<j<=min(i+A[i], A.length-1) 使得M[j]=True, or I can jump directly from i-th index to the target Return: M[0]

Time = O(n^2)

#有点问题
class Solution(object):
  def canJump(self, array):
    """
    input: int[] array
    return: boolean
    """
    # write your solution here
    if len(array)==1:
      return True
    canJump = [False]*len(array)
    for i in range (len(array)-2, -1, -1):
      if i+array[i]>=len(array)-1:
        canJump[i] = True
      else:
        for j in range (array[i],0):
          if (canJump[j+i]):
            canJump[i] = True
            break
    return canJump[0]

从左到右linear scan,从起点开始看

Base Case: M[i]的物理意义: whether I can jump from the start to the i-th index M[0] = true Induction Rule: M[i]=True if there exists a j where j<i and M[j]==true, and j+A[j]>=i Return: M[length-1]

Time = O(n^2)

Jump Game 2

从a[0]到a[n-1]的最少步数

Largest Sum of Subarray

M[i] 物理意义 the sum of the largest sum subarray that ends at a[i]

空间可以优化到O(1),因为只在用最近的一个

followup:how to return the left-right border of the solution

left: 达到M[i]时subarray的左边界(闭区间)的位置 i: 达到M[i]时的右边界(闭区间)的位置

Initialize: M[0] = a[0] left = 0

Maximum subarray sum in a circular array.

问题描述

Example 1:
Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:
Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:
Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4:
Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:
Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1

解题思路

Case1: max subarray只出现在array中间的一段,没有从最末连接到开头:直接求max subarray sum。 Case2: max subarray需要从最末连接到开头: 1. 求array中间出现的一段min subarray sum. 2. 用array所有元素的总的sum来减去中间出现的这一段min subarray sum,就是结果。 Return max(case1, case2)

此外要额外考虑的情况:如果所有array内的所有元素都是负数,则不需要考虑case2,直接返回case1的结果。

复杂度分析

  • 时间 O(n)

  • 空间 O(1)

Proposed Code

class Solution {
    public int maxSubarraySumCircular(int[] A) {
        if (A == null || A.length == 0)
            return Integer.MIN_VALUE;

        if (A.length == 1)
            return A[0];

        boolean allNegative = true;
        int total = 0;
        // check whether all numbers are negative and calculate total sum
        for (int num : A) {
            if (num >= 0)
                allNegative = false;

            total += num;
        }
        // case 1
        int sum1 = getMaxOrMinSubarraySum(A, true);
        // case 2 - skip if all numbers are negative
        int sum2 = allNegative ? Integer.MIN_VALUE : total - getMaxOrMinSubarraySum(A, false);
        return Math.max(sum1, sum2);
    }
    private int getMaxOrMinSubarraySum(int[] A, boolean isMax) {
        int result = isMax ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        int cur = A[0];
        for (int i = 1; i < A.length; i++) {
            cur = isMax ? Math.max(A[i], A[i] + cur) : Math.min(A[i], A[i] + cur);
            result = isMax ? Math.max(result, cur) : Math.min(result, cur);
        }
        return result;
    }
}

关于转圈的问题:

可以分成(1)中间 (2)连续 来表示 注意这道题和LeetCode#197 House Robber不同。197只需要考虑首位两个值,所以做题时特殊处理这两个就行,但这里的转圈不一定是2个值,没有办法只挖去首尾。

Max subarray sum with at least size k

问题描述

马甲:
Given an array of daily price changes of a stock, what's the maximum profit 
you can make if you buy once and sell once, and you have to hold the stock 
for at least k days?

Example
input = {-3, +1, -2, -4}, k = 2
output = -1

input = {+1, +1, +1, +1}, k = 2
output = 4

解题思路

当没有"size k"这个条件时,求max subarray sum,对于index i,只需要看dp array中的前一个值,如果是正数,就加上来,否则就另起炉灶。

现在要求至少size k,对于index i来说: 1. 从i-k+1 到i这个sliding window之内的值,必须要加进来。 2. 那i-k以及之前的值呢?就取决于以i-k为终点的max subarray sum是否为正数,是正数就加进来,否则就不要。 3. 所以要先做一次max subarray sum,存在一个dp array里,这样做#2的时候才能查看。

复杂度分析

  • 时间 O(n)

  • 空间 O(n)

Proposed Code

public int MaxSubarraySumSizeK(int[] array, int k) {
        if (array == null || array.length == 0 || k <= 0)
            return Integer.MIN_VALUE;

        int[] tmp = maxSubarraySum(array);
        int windowSum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            windowSum += array[i];
            if (i == k - 1) {
                max = Math.max(max, windowSum);
            } else if (i >= k) {
                windowSum -= array[i - k];
                int curSum = Math.max(windowSum, windowSum + tmp[i - k]);
                max = Math.max(max, curSum);
            }
        }
        return max;
    }

    private int[] maxSubarraySum(int[] array) {
        int[] tmp = new int[array.length];
        tmp[0] = array[0];
        for (int i = 1; i < array.length; i++)
            tmp[i] = Math.max(array[i], array[i] + tmp[i - 1]);

        return tmp;
    }

Unsorted Array 最长连续1

十字架

如果是brute force 需要n^3

这不是二维DP,而是四个方向的一维DP

Step1: 从左到右,从右到左,从上到下,从下到上,分别做“最长连续1” O(4n^2)

Step2: 四个方向的结果在当前取一个min O(n^2)

return global max among all M[i][j]

X

变成斜着做

空心1

火柴

每个顶点只考虑两个方向,右和下

可以两种表示,要么就tuple,要么就2-bit

任意subarray sum

prefix sum+ 1D

M[i] represents the sum from index 0 to index i

sum[i...j] = M[j] = M[i-1] 但是容易出界 更好的是M[j]-M[i]+input[i]

Time = O(n) Extra Space = O(n) Query Time = O(1)

sum最大的长方形

Prefix Sum 1D

Prefix Sum 2D

蓝-绿-红+橙

二维

Edit Distance

Largest Square of 1's in a Binary Matrix

M[i][j] 物理意义 以a[i][j]为右下角的最大全1正方形的边长

PreviousRecursion II and MemoizationNextComplete Binary Tree, Segment Tree, Trie Tree

Last updated 5 years ago