Algorithm notes from Leecode -- 1

Algorithm Leetcode

Links

[https://www.dailycodingproblem.com/?ref=csdojo]{.underline}
[https://www.csdojo.io/#]{.underline}
https://github.com/mission-peace/interview/tree/master/src/com/interview/dynamic
[https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns]{.underline}
daily coding problem book pdf free download

[https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20题解%20-%20目录.md]{.underline}

leetcodeGithub project in intelliJ

tasks to hands on

~~0/1 knapsack~~
~~fibnachi memoized and bottom up approaches~~
median of two sorted array
64 minimum path sum
Maximum sub array (kadane algorithm)

[Slide Window]

（1）没有重复字符的子字符的最大长度：给一个字符串，获得没有重复字符的最长子字符的长度

例子：

输入："abcbabcbb"

输出：3

解释：因为没有重复字符的子字符是'abc'，所以长度是3

public class Solution {//时间复杂度O(2n)

//滑动窗口算法

public int [lengthOfLongestSubstring]{.underline}(String s) {

int n = s.length();

Set<Character> set = new HashSet<>();

int ans = 0, i = 0, j = 0;

while (i < n && j < n) {//窗口的左边是i，右边是j，下列算法将窗口的左右移动，截取出其中一段

// try to extend the range [i, j]

if (!set.contains(s.charAt(j))){//如果set中不存在该字母，就将j+1，相当于窗口右边向右移动一格，左边不动

set.add(s.charAt(j++));

ans = Math.max(ans, j - i);//记录目前存在过的最大的子字符长度

}

else {//如果set中存在该字母，则将窗口左边向右移动一格，右边不动，直到该窗口中不存在重复的字符

set.remove(s.charAt(i++));

}

return ans;

}

作者：DrXu

链接：https://juejin.im/post/5c74a2e2f265da2dea053355

来源：掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

====

解法3：优化的滑动窗口算法

上面的滑动窗口算法最多需要2n的步骤，但这其实是能被优化为只需要n步。我们可以使用HashMap定义字符到索引之间的映射，然后，当我们发现子字符串中的重复字符时，可以直接跳过遍历过的字符了。

（2）public class Solution {//时间复杂度o(n)

public int lengthOfLongestSubstring(String s) {

int n = s.length(), ans = 0;

//使用hashmap记录遍历过的字符的索引，当发现重复的字符时，可以将窗口的左边直接跳到该重复字符的索引处

Map<Character, Integer> map = new HashMap<>(); // current index of character

// try to extend the range [i, j]

for (int j = 0, i = 0; j < n; j++) {//j负责向右边遍历，i根据重复字符的情况进行调整

if (map.containsKey(s.charAt(j))) {//当发现重复的字符时,将字符的索引与窗口的左边进行对比，将窗口的左边直接跳到该重复字符的索引处

i = Math.max(map.get(s.charAt(j)), i);

}

//记录子字符串的最大的长度

ans = Math.max(ans, j - i + 1);

//map记录第一次遍历到key时的索引位置，j+1,保证i跳到不包含重复字母的位置

map.put(s.charAt(j), j + 1);

}

return ans;

}

作者：DrXu

链接：https://juejin.im/post/5c74a2e2f265da2dea053355

来源：掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[Slide Window]

Min Windows

------------- best solution---

（3）public static String minWindowBetter(String s, String t){

if(s==null||t==null|s.length()==0||t.length()==0){

return "";

}

int left=0,right=0,count=0,min=Integer.MAX_VALUE;

int pool[] = new int[256];

String rtn="";

for(int i =0;i<t.length();i++){

pool[t.charAt(i)]++;

}

while(right<s.length()){

if(pool[s.charAt(right++)]-->0){//[!]

// (a) if(pool[s.charAt(right++)]-->=0), rather than if(pool[right++]-->=0)

// (b) this is ">0", but not ">=0"

count++;

}

while(count==t.length()){

if((right-left)<min){

min=right-left;

rtn=s.substring(left,right);

}

//shrink window

if(++pool[s.charAt(left++)]>0){

count--;

}

return rtn;

}

10 lines code to solve most “substring” problem

I will first give the solution then show you the magic template.

The code of solving this problem is below. It might be the shortest among all solutions provided in Discuss.

string minWindow(string s, string t) {

vector<int> map(128,0);

for(auto c: t) map[c]++;

int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;

while(end<s.size()){

if(map[s[end++]]-->0) counter--; //in t

while(counter==0){ //valid

if(end-begin<d) d=end-(head=begin);

if(map[s[begin++]]++==0) counter++; //make it invalid

}

return d==INT_MAX? "":s.substr(head, d);

}

Here comes the template.

For most substring problem, we are given a string and need to find a substring of it which satisfy some restrictions. A general way is to use a hashmap assisted with two pointers. The template is given below.

int findSubstring(string s){

vector<int> map(128,0);

int counter; // check whether the substring is valid

int begin=0, end=0; //two pointers, one point to tail and one head

int d; //the length of substring

for() { /* initialize the hash map here */ }

while(end<s.size()){

if(map[s[end++]]-- ?){ /* modify counter here */ }

while(/* counter condition */){

/* update d here if finding minimum*/

//increase begin to make it invalid/valid again

if(map[s[begin++]]++ ?){ /*modify counter here*/ }

}

/* update d here if finding maximum*/

}

return d;

}

One thing needs to be mentioned is that when asked to find maximum substring, we should update maximum after the inner while loop to guarantee that the substring is valid. On the other hand, when asked to find minimum substring, we should update minimum inside the inner while loop.

The code of solving [Longest Substring with At Most Two Distinct Characters]{.underline} is below:

（4）int lengthOfLongestSubstringTwoDistinct(string s) {

vector<int> map(128, 0);

int counter=0, begin=0, end=0, d=0;

while(end<s.size()){

if(map[s[end++]]++==0) counter++;

while(counter>2) if(map[s[begin++]]--==1) counter--;

d=max(d, end-begin);

}

return d;

}

The code of solving [Longest Substring Without Repeating Characters]{.underline} is below:

Update 01.04.2016, thanks \@weiyi3 for advice.

[（5）]{.underline}int lengthOfLongestSubstring(string s) {

vector<int> map(128,0);

int counter=0, begin=0, end=0, d=0;

while(end<s.size()){

if(map[s[end++]]++>0) counter++;

while(counter>0) if(map[s[begin++]]-->1) counter--;

d=max(d, end-begin); //while valid, update d

}

return d;

}

I think this post deserves some upvotes! : )

[[sliding window ]]{.underline}

string minWindow(string s, string t) {

unordered_map<char, int> m;

// Statistic for count of char in t

for (auto c : t) m[c]++;

// counter represents the number of chars of t to be found in s.

size_t start = 0, end = 0, counter = t.size(), minStart = 0, minLen = INT_MAX;

size_t size = s.size();

// Move to find a valid window.

while (end < size) {

// If char in s exists in t, decrease counter

if (m[s[end]] > 0)

counter--;

// Decrease m[s[end]]. If char does not exist in t, m[s[end]] will be negative.

m[s[end]]--;

end++;

// When we find a valid window, the move starts to find a smaller window.

while (counter == 0) {

if (end - start < minLen) {

minStart = start;

minLen = end - start;

}

m[s[start]]++;

// When char exists in t, increase the counter.

if (m[s[start]] > 0)

counter++;

start++;

}

if (minLen != INT_MAX)

return s.substr(minStart, minLen);

return "";

}

～～～～java version～～

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++;

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);

}

[DP]

[（6]{.underline}）longestCommonSubsequence

public int longestCommonSubsequence(String text1, String text2) {

// xx-est is meant for dynamic programming

// x keys for DP

// 1st, declare a DP table for bottom up

// 2nd set global value

// ================

// for top down, use memo

int m = text1.length(); //[!!!!] it's "length()" method for String

int n = text2.length();

int[][] memo = new int[m+1][n+1];

for(int i=0;i<m;i++){

for(int j=0;j<n;j++){

// if(i==0||j==0){ //[!!!!!222] here is no need, because default value in array is zero

// // 1st col or 1st row, set to 0

// memo[i][j]=0;

// }else{

if(text1.charAt(i)==text2.charAt(j)){

memo[i+1][j+1] = 1 + memo[i][j];

}else{

// current char is different, so go to carry previous biggest value from either left or up

memo[i+1][j+1] = Math.max(memo[i+1][j],memo[i][j+1]);

}

// }

}

return memo[m][n];

}

[DP]

LengthOfLIS

[（7]{.underline}）public class LengthOfLIS {

System.out.println("===test failed case (DP) :"+inst.lengthOfLIS_tail(new int[]{4,10,4,3,8,9}));

System.out.println("===test failed case (DP) :"+inst.lengthOfLIS_tail(new int[]{2,2})); //expect output "1"

public int lengthOfLIS_naive(int[] nums){

//edge case

if(nums.length<0){

return 0;

}

int m=nums.length;

int max=0; // global max

int[] dp=new int[m];

//embedded loop to search max value brute forcely

for (int i = 0; i <m ; i++) {

// loop each digits

int localMax=0; // holder for MAX length of increase sequence before i

for (int j = 0; j < i; j++) {

// loop to find all increasing BEFORE this number

if(dp[j]>localMax && nums[j]<nums[i]){

// previous number is SMALLER than i and greater than local max, that means it's increasing

localMax=dp[j];

}

// after looped ALL previous numbers, add current one

dp[i]=localMax+1;

max = Math.max(max,dp[i]);

}

return max;

}

public int [lengthOfLIS_tail]{.underline}(int[] nums){

int m=nums.length;

if(m==0) return 0;

int[] dp=new int[m]; // dp[x]=y : value "y" of dp stores "the last number" (tail) of increasing sequence whose length is "x"

int maxLen=0;

dp[0]=nums[0];

//for loop each number in array

for (int i = 1; i < m; i++) { //[!!!!!!!!1111111] it should start with "1", as "0" is already setup

// there are 3 scenarios we need to update dp

if(nums[i]<dp[0]){

// current number is even smaller than most smallest LIS, update it

dp[0]=nums[i];

}else if(nums[i]>dp[maxLen]){

//current number is greater than 'tail' of largest LIS, then update the last LIS

dp[++maxLen]=nums[i];

}else{

// current number is in the middle, so we go to find the *correct* position to locate the LIS in DP

dp[binarySearchLIS(dp,0,maxLen,nums[i])]=nums[i];

}

return maxLen+1; // because dp is zero based, so add one for result

}

public int binarySearchLIS(int[] dp, int min, int max, int target){

while(min<=max){

int middle =min + (max-min)/2; //[!!!!!!!] don't forget to add prefix "min +" in front of (max-min)/2

if(dp[middle]==target){

return middle;

}else if(dp[middle]>target){

max=middle-1;

} else if(dp[middle]<target){

min=middle+1;

}

return min;

}

[Graph]

RottingOrange

[（8]{.underline}）public class GraphRottingOrange {

public static void main(String[] args) {

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;

the value 1 representing a fresh orange;

the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]

Output: 4

Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]

Output: -1

Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: [[0,2]]

Output: 0

Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

1 <= grid.length <= 10

1 <= grid[0].length <= 10

grid[i][j] is only 0, 1, or 2.

GraphRottingOrange inst = new GraphRottingOrange();

deleted 2-D array due to hexo error

System.out.println("===output of findRottenMinutes:" + inst.orangesRotting(grid));

}

public int orangesRotting(int[][] grid) {

int m = grid.length;

int n = grid[0].length;

List<String> listRotten = new ArrayList<>();

List<String> listFresh = new ArrayList<>();

int nMinutes = 0;

//firstly, find and enlist rotten ones

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (grid[i][j] == 2) {

//current cell is a rotten tomato, so check adjacent and contract them

listRotten.add(i + "" + j);

} else if (grid[i][j] == 1) {

// fresh tomato, to record it , so check zero of this list to confirm ALL tomato got infected

listFresh.add(i + "" + j);

}

// loop until empty of fresh ones

while (!listFresh.isEmpty()) {

List<String> infected = new ArrayList<>();

for (String strRotten : listRotten) {

int x = strRotten.charAt(0) - '0';

int y = strRotten.charAt(1) - '0';

//to search 4 directions both vertically and horizontally

deleted 2-D array due to hexo error

for (int[] direction : directions) {

int newX = x + direction[0];

int newY = y + direction[1];

String newLoc = newX + "" + newY;

if (listFresh.contains(newLoc)) {

// make new tomato as rotten

listFresh.remove(newLoc);

// listRotten.add(newLoc);

infected.add(newLoc); // add to infected, rather than Rotten to avoid "ConcurrentModificationException" as it's our loop list

}

// return -1 in case no more been infected

if (infected.isEmpty()) {

return -1;

}

// assign infected to listRotten to further check

listRotten=infected;

++nMinutes;

}

return nMinutes;

}

public int orangesRotting_Iterative(int[][] grid) {

if(grid == null || grid.length == 0) return 0;

int rows = grid.length;

int cols = grid[0].length;

Queue<int[]> queue = new LinkedList<>();

int count_fresh = 0;

//Put the position of all rotten oranges in queue

//count the number of fresh oranges

for(int i = 0 ; i < rows ; i++) {

for(int j = 0 ; j < cols ; j++) {

if(grid[i][j] == 2) {

queue.offer(new int[]{i , j});

}

else if(grid[i][j] == 1) {

count_fresh++;

}

//if count of fresh oranges is zero --> return 0

if(count_fresh == 0) return 0;

int count = 0;

deleted 2-D array due to hexo error

//bfs starting from initially rotten oranges

while(!queue.isEmpty()) {

++count;

int size = queue.size();

for(int i = 0 ; i < size ; i++) {

int[] point = queue.poll();

for(int dir[] : dirs) {

int x = point[0] + dir[0];

int y = point[1] + dir[1];

//if x or y is out of bound

//or the orange at (x , y) is already rotten

//or the cell at (x , y) is empty

//we do nothing

if(x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] == 0 || grid[x][y] == 2) continue;

//mark the orange at (x , y) as rotten

grid[x][y] = 2;

//put the new rotten orange at (x , y) in queue

queue.offer(new int[]{x , y});

//decrease the count of fresh oranges by 1

count_fresh--;

}

return count_fresh == 0 ? count-1 : -1;

}

[DP]

DecodeWays

package algo;

[（9]{.underline}）public class DecodeWays {

public static void main(String[] args) {

[reverse integer]{.underline}

class Solution {

public int reverse(int x) {

long res = 0;

while (x != 0) {

res *= 10;

res += x % 10;

x /= 10;

}

return (int)res == res ? (int)res : 0;

}

public class Solution {

public int reverse(int x) {

long result =0;

while(x != 0)

{

result = (result*10) + (x%10);

if(result > Integer.MAX_VALUE) return 0;

if(result < Integer.MIN_VALUE) return 0;

x = x/10;

}

return (int)result;

}

Find median of two sorted array

<1> Set imin = 0, imax = m, then start searching in [imin, imax]

<2> Set i = (imin + imax)/2, j = (m + n + 1)/2 - i

<3> Now we have len(left_part)==len(right_part). And there are only 3 situations

that we may encounter:

<a> B[j-1] <= A[i] and A[i-1] <= B[j]

Means we have found the object `i`, so stop searching.

<b> B[j-1] > A[i]

Means A[i] is too small. We must `ajust` i to get `B[j-1] <= A[i]`.

Can we `increase` i?

Yes. Because when i is increased, j will be decreased.

So B[j-1] is decreased and A[i] is increased, and `B[j-1] <= A[i]` may

be satisfied.

Can we `decrease` i?

`No!` Because when i is decreased, j will be increased.

So B[j-1] is increased and A[i] is decreased, and B[j-1] <= A[i] will

be never satisfied.

So we must `increase` i. That is, we must ajust the searching range to

[i+1, imax]. So, set imin = i+1, and goto <2>.

<c> A[i-1] > B[j]

Means A[i-1] is too big. And we must `decrease` i to get `A[i-1]<=B[j]`.

That is, we must ajust the searching range to [imin, i-1].

So, set imax = i-1, and goto <2>.

When the object i is found, the median is:

max(A[i-1], B[j-1]) (when m + n is odd)

or (max(A[i-1], B[j-1]) + min(A[i], B[j]))/2 (when m + n is even)

Number of distinct Islands

private static int rows, cols;

deleted 2-D array due to hexo error

public int numDistinctIslands(int[][] grid) {

cols = grid[0].length;

rows = grid.length;

Set<String> uniqueShapes = new HashSet<>(); // Unique shpes.

StringBuilder shape;

for (int i = 0; i < rows; i++) {

for (int j = 0; j < cols; j++) {

if (grid[i][j] == 1) {

grid[i][j] = 0; // mark it as 'visited'

shape = new StringBuilder("s"); //'s' indicate Start

dfsTraversal(i, j, grid, shape);

uniqueShapes.add(shape.toString());

}

return uniqueShapes.size();

}

private static void dfsTraversal(int x, int y, int[][] matrix, StringBuilder shape) {

for (int i = 0; i < directions.length; i++) {

int nx = x + directions[i][0];

int ny = y + directions[i][1];

if (nx >= 0 && ny >= 0 && nx < rows && ny < cols) {

if (matrix[nx][ny] == 1) {

matrix[nx][ny] = 0; // mark as 'visited'

shape.append(i);

dfsTraversal(nx, ny, matrix, shape);

}

shape.append("_");

}

//=======

class Solution {

deleted 2-D array due to hexo error

public int numDistinctIslands(int[][] grid) {

Set<String> set= new HashSet<>();

int res=0;

for(int i=0;i<grid.length;i++){

for(int j=0;j<grid[0].length;j++){

if(grid[i][j]==1) {

StringBuilder sb= new StringBuilder();

helper(grid,i,j,0,0, sb);

String s=sb.toString();

if(!set.contains(s)){

res++;

set.add(s);

}

return res;

}

public void helper(int[][] grid,int i,int j, int xpos, int ypos,StringBuilder sb){

grid[i][j]=0;

sb.append(xpos+""+ypos);

for(int[] dir : dirs){

int x=i+dir[0];

int y=j+dir[1];

if(x<0 || y<0 || x>=grid.length || y>=grid[0].length || grid[x][y]==0) continue;

helper(grid,x,y,xpos+dir[0],ypos+dir[1],sb);

}

UPDATE: We can use direction string instead of using number string in set.

Below is \@wavy code using direction string.

public int numDistinctIslands(int[][] grid) {

Set<String> set = new HashSet<>();

for(int i = 0; i < grid.length; i++) {

for(int j = 0; j < grid[i].length; j++) {

if(grid[i][j] != 0) {

StringBuilder sb = new StringBuilder();

dfs(grid, i, j, sb, "o"); // origin

grid[i][j] = 0;

set.add(sb.toString());

}

return set.size();

}

private void dfs(int[][] grid, int i, int j, StringBuilder sb, String dir) {

if(i < 0 || i == grid.length || j < 0 || j == grid[i].length

|| grid[i][j] == 0) return;

sb.append(dir);

grid[i][j] = 0;

dfs(grid, i-1, j, sb, "u");

dfs(grid, i+1, j, sb, "d");

dfs(grid, i, j-1, sb, "l");

dfs(grid, i, j+1, sb, "r");

sb.append("b"); // back

}

In a complete binary tree every level, *except possibly the

last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h^* nodes at the last level h.[^[18]^](https://en.wikipedia.org/wiki/Binary_tree#cite_note-complete_binary_tree-18) An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed. Some authors use the term complete to refer instead to a perfect binary tree as defined below, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree.^[19][20]^ A complete binary tree can be efficiently represented using an array.[^[18]^](https://en.wikipedia.org/wiki/Binary_tree#cite_note-complete_binary_tree-18)

{width=”2.2916666666666665in” height=”1.1944444444444444in”}

A complete binary tree (that is not full)

A perfect binary tree is a binary tree in which all interior

nodes have two children and all leaves have the same depth or same level.[^[21]^](https://en.wikipedia.org/wiki/Binary_tree#cite_note-21) An example of a perfect binary tree is the (non-incestuous) ancestry chart of a person to a given depth, as each person has exactly two biological parents (one mother and one father). Provided the ancestry chart always displays the mother and the father on the same side for a given node, their sex can be seen as an analogy of left and right children, children being understood here as an algorithmic term. A perfect tree is therefore always complete but a complete tree is not necessarily perfect.

Heap Tree is a special balanced binary tree data structure where root node is compared with its children and averaged accordingly. There are two type of trees, min heap tree and map heap tree.

For Min heap tree, it’s parent is either smaller or equals its childers.

Get Tree Height

static int getHeight_recursive(TreeNode root){

if(root==null){

return 0;

}

return Math.max(getHeight_recursive(root.left),getHeight_recursive(root.right))+1; //[!!!!!] Here is the key point, it should add "1" at last

}

The basic idea:

1. traverse layer by layer

2. For each layer, firslty get number of element,

3. Then add its left & right child for each element

4. Increase height once all element of current layer finished

static int getHeight_Iteratively(TreeNode root) {

int height=0;

Stack<TreeNode> stack=new Stack<>();

stack.add(root);

while(!stack.isEmpty()){

int numberOfSibling=stack.size();

// loop in all element in this layer till none is left

while(numberOfSibling-- >0){

root = stack.pop();

// add current element's children

if(root.left!=null) stack.push(root.left);

if(root.right!=null) stack.push(root.right);

}

height++;

}

return height;

}

InvertTree

package algo;

public class TreeInvertBST {

public static void main(String[] args) {

System.out.printf("===start===");

TreeNode root = invertTree(TreeNode.buildBSTTree());

System.out.printf("invert tree: "+ root);

}

static TreeNode invertTree(TreeNode root){

if(root==null) return null;

TreeNode tmpLeft = root.left;

root.left=invertTree(root.right);

root.right=invertTree(tmpLeft);

return root;

}

[Number of islands]{.underline}

static int numberOfIslands(char[][] grid){

int number = 0;

if(grid==null || grid.length <0 || grid[0].length<0 ) {

return 0;

}

for (int i = 0; i < grid.length; i++) {

for (int j = 0; j <grid[i].length ; j++) {

if(grid[i][j]=='1') {

// DFS to clear adjacent "1" to avoid dup counting

DFS(grid, i, j);

++number;

}

return number;

}

// the main purpose of calling DFS is to set “0” for all adjacent “1” cells. As they all together to form one island

static void DFS(char[][] grid, int x, int y){

//edge case

if(grid==null || x<0 || x >= grid.length || y<0 || y>=grid[0].length || grid[x][y]=='0') { //[!!!!] should >= length, not ">"

// if(grid==null || x<0 || x > grid.length || y<0 || y>grid[0].length || grid[x][y]==0) {

// return if cursor node is NOT 1

return;

}

// means current cursor node is "1"

grid[x][y]='0'; // mark this cell as visited

// check all adjacent cells

DFS(grid, x-1, y);

DFS(grid, x+1, y);

DFS(grid, x, y-1);

DFS(grid, x, y+1);

}

---------

Is a same tree:

static boolean isSameTree(TreeNode tree1, TreeNode tree2) {

// check base case, null checking

if(tree1==null || tree2 ==null){

return tree1 == tree2; // true when both null, false when only one is null

}

/* same tress should be :

1. node data is same

2. left sub tree is same

4. right sub tree is same

return tree1.val==tree2.val && isSameTree(tree1.left,tree2.left) && isSameTree(tree1.right,tree2.right);

}

Search BST

public static TreeNode searchBST(TreeNode root, int val) {

if(root==null){

return null;

}

if(root.val==val){

return root;

}else if(val > root.val){

return searchBST(root.right, val);

} else {

return searchBST(root.left,val);

}

public static TreeNode searchBST_Iterative(TreeNode root, int val) {

// recursive approach means recursively assgin/update variables

while(root != null && root.val != val){

root = val<root.val? root.left:root.right;

}

return root;

}

Tree Traverse:

static public List<Integer> inorderTraversal_better(TreeNode root) {

List<Integer> listRtn = new ArrayList<>();

// for inorder trave iteratively we'll push/pop stacks

Stack<TreeNode> stack = new Stack<>();

// to determine when to push stack

// for inorder traverse, to push left first, then pop root, then last right

while(root!=null || !stack.empty()) {

while(root!=null){

stack.push(root);

// keep on assign left to root for in order traverse

root=root.left;

}

root = stack.pop(); // pop up value of root

listRtn.add(root.val);

root=root.right;

}

return listRtn;

}

This one is more intuitive

static public List<Integer> preorderTraversal_better(TreeNode root) {

List<Integer> listRtn = new ArrayList<>();

Stack<TreeNode> stack = new Stack<>();

stack.push(root);

while (!stack.empty()) {

root = stack.pop(); // pop up value of root

if (root != null) {

listRtn.add(root.val);

stack.push(root.right);

stack.push(root.left);

}

return listRtn;

}

static List<Integer> postOrderTraversal_stack_better(TreeNode node) {

List<Integer> list = new ArrayList<>();

if(node==null) {

return list;

}

Stack<TreeNode> stack = new Stack<>();

stack.push(node);

while(!stack.isEmpty()){

node= stack.pop();

list.add(0, node.val); //[!!!!!!!!!!] here is key logic, add item at postion "0" means at the begining

if(node.left!=null) stack.push(node.left);

if(node.right!=null) stack.push(node.right);

}

return list;

}

binaryTreeIsBST

The key logic are:

1. assign two boundaries (lower , upper) for each node,

2. update upper to current node for its left child and lower for its right child

3. recursively check each node

static boolean binaryTreeIsBST(TreeNode node, int lower, int upper){

// for recursive, base case

// Number 1: base case is null return true

if(node==null) return true;

// Number 2: check data

if(node.val < lower || node.val>upper) {

System.out.printf("%s failed in BST check [%d,%d]: ", node, lower,upper);

return false;

}

// for left child node, it's value should between current's node's lower boundary and current node's value

// for right child node, it's value should between current node's value and current's node's upper boundary

return binaryTreeIsBST(node.left,lower,node.val) && binaryTreeIsBST(node.right,node.val, upper);

}

Iteratively check binary tree is BST: (use inOrder search , only replace list.add with checking pre)

public boolean isValidBST(TreeNode root) {

if (root == null) return true;

Stack<TreeNode> stack = new Stack<>();

TreeNode pre = null;

while (root != null || !stack.isEmpty()) {

while (root != null) {

stack.push(root);

root = root.left;

}

root = stack.pop();

if(pre != null && root.val <= pre.val) return false;

pre = root;

root = root.right;

}

return true;

}

======

Kth smallest element

public int kthSmallest(TreeNode root, int k) {

Stack<TreeNode> stack = new Stack<>();

while(root != null || !stack.isEmpty()) {

while(root != null) {

stack.push(root);

root = root.left;

}

root = stack.pop();

if(--k == 0) break;

root = root.right;

}

return root.val;

}

contrapositive

contradiction

cases

induction

Interview tips:

Do not silent, ask” can I think for a second “
Think out loud
Use examples
Ask “ does that sound a good strategy” rather than write code right

away
Better naming variable. For dynamic programing. If you use memoized

solution, better to name array as “// memorized solitoon memo[]

编辑距离问题就是给我们两个字符串 s1 和 s2，只能用三种操作，让我们把 s1 变成 s2，求最少的操作数。需要明确的是，不管是把 s1 变成 s2 还是反过来，结果都是一样的，所以后文就以 s1 变成 s2 举例。

前文「」说过，解决两个字符串的动态规划问题，一般都是用两个指针 i,j 分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模。

一、动态规划解法

动态规划的核心设计思想是数学归纳法

总结一下动态规划的设计流程：

首先明确 dp 数组所存数据的含义。这步很重要，如果不得当或者不够清晰，会阻碍之后的步骤。

然后根据 dp 数组的定义，运用数学归纳法的思想，假设 $dp[0...i-1]$ 都已知，想办法求出 $dp[i]$，一旦这一步完成，整个题目基本就解决了。

但如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组。

最后想一想问题的 base case 是什么，以此来初始化 dp 数组，以保证算法正确运行。

最长递增子序列（Longest Increasing Subsequence，简写 LIS）是比较经典的一个问题，比较容易想到的是动态规划解法，时间复杂度 O(N\^2)，

我们的定义是这样的：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。

根据刚才我们对 dp 数组的定义，现在想求 dp[5] 的值，也就是想求以 nums[5] 为结尾的最长递增子序列。

nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。

当然，可能形成很多种新的子序列，但是我们只要最长的，把最长子序列的长度作为 dp[5] 的值即可。

还有一个细节问题，dp 数组应该全部初始化为 1，因为子序列最少也要包含自己，所以长度最小为 1。下面我们看一下完整代码：

public int [lengthOfLIS]{.underline}(int[] nums) {

int[] dp = new int[nums.length];

// dp 数组全都初始化为 1

Arrays.fill(dp, 1);

for (int i = 0; i < nums.length; i++) {

for (int j = 0; j < i; j++) {

if (nums[i] > nums[j])

dp[i] = Math.max(dp[i], dp[j] + 1);

}

int res = 0;

for (int i = 0; i < dp.length; i++) {

res = Math.max(res, dp[i]);

}

return res;

}

public int lengthOfLIS(int[] nums) {

int[] top = new int[nums.length];

// 牌堆数初始化为 0

int piles = 0;

for (int i = 0; i < nums.length; i++) {

// 要处理的扑克牌

int poker = nums[i];

/***** 搜索左侧边界的二分查找 *****/

int left = 0, right = piles;

while (left < right) {

int mid = (left + right) / 2;

if (top[mid] > poker) {

right = mid;

} else if (top[mid] < poker) {

left = mid + 1;

} else {

right = mid;

}

/*********************************/

// 没找到合适的牌堆，新建一堆

if (left == piles) piles++;

// 把这张牌放到牌堆顶

top[left] = poker;

}

// 牌堆数就是 LIS 长度

return piles;

}

至此，二分查找的解法也讲解完毕。

这个解法确实很难想到。首先涉及数学证明，谁能想到按照这些规则执行，就能得到最长递增子序列呢？其次还有二分查找的运用，要是对二分查找的细节不清楚，给了思路也很难写对

/* Dynamic Programming Java implementation of LIS problem */

class LIS

{

/* lis() returns the length of the longest increasing

subsequence in arr[] of size n */

static int lis(int arr[],int n)

{

int lis[] = new int[n];

int i,j,max = 0;

/* Initialize LIS values for all indexes */

for ( i = 0; i < n; i++ )

lis[i] = 1;

/* Compute optimized LIS values in bottom up manner */

for ( i = 1; i < n; i++ )

for ( j = 0; j < i; j++ )

if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)

lis[i] = lis[j] + 1;

/* Pick maximum of all LIS values */

for ( i = 0; i < n; i++ )

if ( max < lis[i] )

max = lis[i];

return max;

}

public static void main(String args[])

{

int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };

int n = arr.length;

System.out.println("Length of lis is " + lis( arr, n ) + "\n" );

}

/*This code is contributed by Raja

-----

Find number of days between two given dates

Given two dates, find total number of days between them. The count of days must be calculated in O(1) time and O(1) auxiliary space.

Examples:

Input: dt1 = {10, 2, 2014}

dt2 = {10, 3, 2015}

Output: 393

dt1 represents "10-Feb-2014" and dt2 represents "10-Mar-2015"

The difference is 365 + 28

Input: dt1 = {10, 2, 2000}

dt2 = {10, 3, 2000}

Output: 29

Note that 2000 is a leap year

Input: dt1 = {10, 2, 2000}

dt2 = {10, 2, 2000}

Output: 0

Both dates are same

Input: dt1 = {1, 2, 2000};

dt2 = {1, 2, 2004};

Output: 1461

Number of days is 365*4 + 1

One Naive Solution is to start from dt1 and keep counting days till dt2 is reached. This solution requires more than O(1) time.

A Better and Simple solution is to count total number of days before dt1 from i.e., total days from 00/00/0000 to dt1, then count total number of days before dt2. Finally return the difference between two counts.

Let the given two dates be "1-Feb-2000" and "1-Feb-2004"

dt1 = {1, 2, 2000};

dt2 = {1, 2, 2004};

Count number of days before dt1. Let this count be n1.

Every leap year adds one extra day (29 Feb) to total days.

n1 = 2000*365 + 31 + 1 + Number of leap years

Count of leap years for a date 'd/m/y' can be calculated

using following formula:

Number leap years

= y/4 - y/100 + y/400 if m > 2

= (y-1)/4 - (y-1)/100 + (y-1)/400 if m <= 2

All above divisions must be done using integer arithmetic

so that the remainder is ignored.

For 01/01/2000, leap year count is 1999/4 - 1999/100

+ 1999/400 which is 499 - 19 + 4 = 484

Therefore n1 is 2000*365 + 31 + 1 + 484

Similarly, count number of days before dt2. Let this

count be n2.

Finally return n2-n1

// Java program two find number of

// days between two given dates

class GFG

{

// A date has day 'd', month 'm' and year 'y'

static class Date

{

int d, m, y;

public Date(int d, int m, int y)

{

this.d = d;

this.m = m;

this.y = y;

}

};

// To store number of days in

// all months from January to Dec.

static int monthDays[] = {31, 28, 31, 30, 31, 30,

31, 31, 30, 31, 30, 31};

// This function counts number of

// leap years before the given date

static int countLeapYears(Date d)

{

int years = d.y;

// Check if the current year needs to be considered

// for the count of leap years or not

if (d.m <= 2)

{

years--;

}

// An year is a leap year if it is a multiple of 4,

// multiple of 400 and not a multiple of 100.

return years / 4 - years / 100 + years / 400;

}

// This function returns number

// of days between two given dates

static int getDifference(Date dt1, Date dt2)

{

// COUNT TOTAL NUMBER OF DAYS BEFORE FIRST DATE 'dt1'

// initialize count using years and day

int n1 = dt1.y * 365 + dt1.d;

// Add days for months in given date

for (int i = 0; i < dt1.m - 1; i++)

{

n1 += monthDays[i];

}

// Since every leap year is of 366 days,

// Add a day for every leap year

n1 += countLeapYears(dt1);

// SIMILARLY, COUNT TOTAL NUMBER OF DAYS BEFORE 'dt2'

int n2 = dt2.y * 365 + dt2.d;

for (int i = 0; i < dt2.m - 1; i++)

{

n2 += monthDays[i];

}

n2 += countLeapYears(dt2);

// return difference between two counts

return (n2 - n1);

}

// Driver code

public static void main(String[] args)

{

Date dt1 = new Date(1, 2, 2000);

Date dt2 = new Date(1, 2, 2004);

System.out.println("Difference between two dates is " +

getDifference(dt1, dt2));

}

Last Edit: 6 hours ago

karansingh1559

179

I am trying to compile a list of DP questions commonly asked in interviews. This will help me and others trying to get better at DP. The list will be sorted by difficulty. If you've come across DP questions, do mention them in the comments.

EASY:

121. Best time to buy and sell stock

198. House Robber

256. Paint House

MEDIUM:

63. Unique Paths II

64. Minimum Path Sum

91. Decode Ways

139. Word Break

221. Maximal Square

300. Longest Increasing Subsequence

322. Coin Change

464. Can I Win

474. Ones and Zeroes

516. Longest Palindromic Subsequence

698. Partition to K Equal Sum Subsets

787. Cheapest Flights Within K Stops

1027. Longest Arithmetic Sequence

1049. Last Stone Weight II

1105. Filling Bookcase Shelves

1143. Longest Common Subsequence

1155. Dice Roll Sum

HARD:

32. Longest Valid Parantheses

44. Wildcard Matching

72. Edit Distance

123. Best Time to Buy and Sell Stock III

312. Burst Balloons

1000. Minimum Cost to Merge Stones

1335. Minimum Difficulty of a Job Schedule

dynamic programming

Minimum (Maximum) Path to Reach a Target

Generate problem statement for this pattern

Statement

Given a target find minimum (maximum) cost / path / sum to reach the target.

Approach

Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state.

routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]

Generate optimal solutions for all values in the target and return the value for the target.

for (int i = 1; i <= target; ++i) {

for (int j = 0; j < ways.size(); ++j) {

if (ways[j] <= i) {

dp[i] = min(dp[i], dp[i - ways[j]]) + cost / path / sum;

}

return dp[target]

Tree

Find minimum path

class Solution {

public int minDepth(TreeNode root) {

if(root == null) return 0; // base case

int left = minDepth(root.left); // get depth of left

int right = minDepth(root.right); // get depth of right

if(root.left == null) return right + 1; // leaf nodes are in right subtree

if(root.right == null) return left + 1; // leaf nodes are in left subtree

// if left/right subtrees both contains leaf nodes

return Math.min(left, right) + 1;

}

Get min depth in Iterative approach

public int minDepth(TreeNode root) {

if(root == null)

return 0;

Queue<TreeNode> que = new LinkedList();

int level =1;

que.add(root);

while(!que.isEmpty()){

int size = que.size();

while(size>0){

TreeNode node =que.poll();

if(node.left == null && node.right ==null)

return level;

if(node.left != null)

que.add(node.left);

if(node.right != null)

que.add(node.right);

size--;

}

level++;

}

return level;

}

=================

two solutions with explanation: DFS & BFS:

/** Solution 1: DFS

* Key point:

* if a node only has one child -> MUST return the depth of the side with child, i.e. MAX(left, right) + 1

* if a node has two children on both side -> return min depth of two sides, i.e. MIN(left, right) + 1

* */

public int minDepth(TreeNode root) {

if (root == null) {

return 0;

}

int left = minDepth(root.left);

int right = minDepth(root.right);

if (left == 0 || right == 0) {

return Math.max(left, right) + 1;

}

else {

return Math.min(left, right) + 1;

}

/** Solution 2: BFS level order traversal */

public int minDepth2(TreeNode root) {

if (root == null) {

return 0;

}

Queue<TreeNode> queue = new LinkedList<>();

queue.offer(root);

int level = 1;

while (!queue.isEmpty()) {

int size = queue.size();

for (int i = 0; i < size; i++) {

TreeNode curNode = queue.poll();

if (curNode.left == null && curNode.right == null) {

return level;

}

if (curNode.left != null) {

queue.offer(curNode.left);

}

if (curNode.right != null) {

queue.offer(curNode.right);

}

level++;

}

return level;

}

Preorder Traversal

In preorder traversal, we traverse the root first, then the left and right subtrees.

We can simply implement preorder traversal using recursion:

public void traversePreOrder(Node node) {

if (node != null) {

visit(node.value);

traversePreOrder(node.left);

traversePreOrder(node.right);

}

We can also implement preorder traversal without recursion.

To implement an iterative preorder traversal, we'll need a Stack, and we'll go through these steps:

Push root in our stack

While stack is not empty

Pop current node

Visit current node

Push right child, then left child to stack

public void traversePreOrderWithoutRecursion() {

Stack<Node> stack = new Stack<Node>();

Node current = root;

stack.push(root);

while(!stack.isEmpty()) {

current = stack.pop();

visit(current.value);

if(current.right != null) {

stack.push(current.right);

}

if(current.left != null) {

stack.push(current.left);

}

Convert Sorted List to Binary Search Tree

Medium

1503

Add to List

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

/ \

-3 9

/ /

-10 5

breadth first search

First of all, let's reuse the algorithm from above, adapted to the new structure:

public static <T> Optional<Node<T>> search(T value, Node<T> start) {

Queue<Node<T>> queue = new ArrayDeque<>();

queue.add(start);

Node<T> currentNode;

while (!queue.isEmpty()) {

currentNode = queue.remove();

if (currentNode.getValue().equals(value)) {

return Optional.of(currentNode);

} else {

queue.addAll(currentNode.getNeighbors());

}

return Optional.empty();

}

[Binary search]{.underline}

分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。

------

Sliding window

In any sliding window based problem we have two pointers. One right pointer whose job is to expand the current window and then we have the left pointer whose job is to contract a given window. At any point in time only one of these pointers move and the other one remains fixed.

Smallest window contains sub string

public class Solution {

public String minWindow(String s, String t) {

if(s == null || s.length() < t.length() || s.length() == 0){

return "";

}

HashMap<Character,Integer> map = new HashMap<Character,Integer>();

for(char c : t.toCharArray()){

if(map.containsKey(c)){

map.put(c,map.get(c)+1);

}else{

map.put(c,1);

}

int left = 0;

int minLeft = 0;

int minLen = s.length()+1;

int count = 0;

for(int right = 0; right < s.length(); right++){

if(map.containsKey(s.charAt(right))){

map.put(s.charAt(right),map.get(s.charAt(right))-1);

if(map.get(s.charAt(right)) >= 0){

count ++;

}

while(count == t.length()){

if(right-left+1 < minLen){

minLeft = left;

minLen = right-left+1;

}

if(map.containsKey(s.charAt(left))){

map.put(s.charAt(left),map.get(s.charAt(left))+1);

if(map.get(s.charAt(left)) > 0){

count --;

}

left ++ ;

}

if(minLen>s.length())

{

return "";

}

return s.substring(minLeft,minLeft+minLen);

}

public static String minWindowOp(String s, String t) {

int [] map = new int[128];//map to track number of occurrence of each character of sub string

for (char c : t.toCharArray()) {

map[c]++;

}

int start = 0, end = 0, minStart = 0, minLen = Integer.MAX_VALUE, counter = t.length();

// counter is number of distinct chars in sub string

while (end < s.length()) {

final char c1 = s.charAt(end);// walk through each char in source string

if (map[c1] > 0) {

counter--; // if cached char number greater than 0, decrease counter

}

map[c1]--;//decrease cached char number, for chars not in substring, it will be negative

end++; //move right pointer

while (counter == 0) { //counter is zero means all chars found

if (minLen > end - start) { //to find and cache minimum sliding window length and minimum start

minLen = end - start;

minStart = start;

}

final char c2 = s.charAt(start);

map[c2]++;// A is -2， B is 1

if (map[c2] > 0) {

counter++; //if current char exist in cache, increase counter, otherwise keep counter zero

}

start++;

}

return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);

}

------

I agree with your code, but I prefer this code when count == t.length(),

class Solution {

public String minWindow(String s, String t) {

// corner case

if(s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) return "";

// construct model

int minLeft = 0;

int minRight = 0;

int min = s.length();

boolean flag = false;

Map<Character, Integer> map = new HashMap<>();

int count = t.length(); // the number of characters that I need to match

for(char c : t.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);

// unfixed sliding window, 2 pointers

int i = 0;

int j = 0;

while(j < s.length()){

char c = s.charAt(j);

if(map.containsKey(c)){

map.put(c, map.get(c) - 1);

if(map.get(c) >= 0) count--; // if still unmatched characters, then count--

}

// if found a susbtring

while(count == 0 && i <= j){

// update global min

flag = true;

int curLen = j + 1 - i;

if(curLen <= min){

minLeft = i;

minRight = j;

min = curLen;

}

// shrink left pointer

char leftC = s.charAt(i);

if(map.containsKey(leftC)){

map.put(leftC, map.get(leftC) + 1);

if(map.get(leftC) >= 1) count++;

}

i++;

}

j++;

}

return flag == true ? s.substring(minLeft, minRight + 1): "";

}

First part: when the right pointer is getting incremented we are decrementing the map count of char if it's part of 't' string. When we see that the map count of that char after decrementing is positive/zero means that the right ptr has found a useful char and hence we increment the 'count' variable (which is keeping track of the number of useful chars)

Second part: when the left pointer is getting incremented we are essentially making the window smaller and giving back the chars to the map (i.e. incrementing the map count). If we find that for the particular char the map count has now become positive means that we actually gave back a useful char and hence the 'count' is to be decremented.

At this point then we again start increasing our window and see each time if the count has become equal to the number of chars in 't' string.

----

Generally, there are following steps:

create a hashmap for each character in t and count their frequency

in t as the value of hashmap.
Find the first window in S that contains T. But how? there the

author uses the count.
Checking from the leftmost index of the window and to see if it

belongs to t. The reason we do so is that we want to shrink the size of the window.
3-1) If the character at leftmost index does not belong to t, we can directly remove this leftmost value and update our window(its minLeft and minLen value)
3-2) If the character indeed exists in t, we still remove it, but in the next step, we will increase the right pointer and expect the removed character. If find so, repeat step 3.

public String minWindow(String s, String t) {

HashMap<Character, Integer> map = new HashMap();

for(char c : t.toCharArray()){

if(map.containsKey(c)){

map.put(c, map.get(c)+1);

}

else{

map.put(c, 1);

}

int left = 0, minLeft=0, minLen =s.length()+1, count = 0;

for(int right = 0; right<s.length(); right++){

char r = s.charAt(right);

if(map.containsKey(r)){//the goal of this part is to get the first window that contains whole t

map.put(r, map.get(r)-1);

if(map.get(r)>=0) count++;//identify if the first window is found by counting frequency of the characters of t showing up in S

}

while(count == t.length()){//if the count is equal to the length of t, then we find such window

if(right-left+1 < minLen){//jsut update the minleft and minlen value

minLeft = left;

minLen = right-left+1;

}

char l = s.charAt(left);

if(map.containsKey(l)){//starting from the leftmost index of the window, we want to check if s[left] is in t. If so, we will remove it from the window, and increase 1 time on its counter in hashmap which means we will expect the same character later by shifting right index. At the same time, we need to reduce the size of the window due to the removal.

map.put(l, map.get(l)+1);

if(map.get(l)>0) count--;

}

left++;//if it doesn't exist in t, it is not supposed to be in the window, left++. If it does exist in t, the reason is stated as above. left++.

}

return minLen==s.length()+1?"":s.substring(minLeft, minLeft+minLen);

------------- best solution---

public static String minWindowBetter(String s, String t){

if(s==null||t==null|s.length()==0||t.length()==0){

return "";

}

int left=0,right=0,count=0,min=Integer.MAX_VALUE;

int pool[] = new int[256];

String rtn="";

for(int i =0;i<t.length();i++){

pool[t.charAt(i)]++;

}

while(right<s.length()){

if(pool[s.charAt(right++)]-->0){//[!]

// (a) if(pool[s.charAt(right++)]-->=0), rather than if(pool[right++]-->=0)

// (b) this is ">0", but not ">=0"

count++;

}

while(count==t.length()){

if((right-left)<min){

min=right-left;

rtn=s.substring(left,right);

}

//shrink window

if(++pool[s.charAt(left++)]>0){

count--;

}

return rtn;

}

while(right < length of s){

Deincrement characters frequence at right pointer in String s from bank

Right -- (expand window)

If that character was inside of t, increase count

while(count equal to length of t - condition){

Check if right-left less than min, if so, update min and curr string

Increate characters frequences at left pointer in string, s from bank

Left++ (shift window)

If bank[character at left pointer]>=0, then decrease count.

}

[knapsack 0/1 背包]{.underline}

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：”将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为”前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为”前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

private static int knapsack01(int[] weights, int[] value, int quota) {

// we are using dynamic programming bottom up

// one tab to keep track of value, size is quota + 1

int[][] dp = new int[value.length+1][quota+1];

// as size is actual size + 1, so here is "<=" , rather than "<"

for(int i=0;i<=value.length;i++){

for (int j =0;j<=quota;j++){

//base value

if(i==0 || j==0){

// initilize first line and first column to '0'

dp[i][j] = 0;

continue;

}

// non zero

if(j>=weights[i-1]){

// current weight not bigger than current quota

// so add it to our backtrack

// get the max one of (1) Not include , (2) include this node

dp[i][j]= Math.max(dp[i-1][j], dp[i-1][j-weights[i-1]]+value[i-1]);

}else{

// required weight is less than provided, so skip this

dp[i][j] = dp[i-1][j]; //use value (j) of previous (i-1

}

return dp[value.length][quota];

}

[KMP 算法]{.underline}

KMP 算法永不回退txt的指针i，不走回头路（不会重复扫描txt），而是借助dp数组中储存的信息把pat移到正确的位置继续匹配，时间复杂度只需 O(N)，用空间换时间，所以我认为它是一种动态规划算法。

// 暴力匹配（伪码）

int search(String pat, String txt) {

int M = pat.length;

int N = txt.length;

for (int i = 0; i < N - M; i++) {

int j;

for (j = 0; j < M; j++) {

if (pat[j] != txt[i+j])

break;

}

// pat 全都匹配了

if (j == M) return i;

}

// txt 中不存在 pat 子串

return -1;

---

dynamic programming

public class KMP {

private int[][] dp;

private String pat;

public KMP(String pat) {

this.pat = pat;

// 通过 pat 构建 dp 数组

// 需要 O(M) 时间

}

public int search(String txt) {

// 借助 dp 数组去匹配 txt

// 需要 O(N) 时间

}

为了描述状态转移图，我们定义一个二维 dp 数组，它的含义如下：

dp[j][c] = next

0 <= j < M，代表当前的状态

0 <= c < 256，代表遇到的字符（ASCII 码）

0 <= next <= M，代表下一个状态

dp[4]['A'] = 3 表示：

当前是状态 4，如果遇到字符 A，

pat 应该转移到状态 3

dp[1]['B'] = 2 表示：

当前是状态 1，如果遇到字符 B，

pat 应该转移到状态 2

根据我们这个 dp 数组的定义和刚才状态转移的过程，我们可以先写出 KMP 算法的 search 函数代码：

public int search(String txt) {

int M = pat.length();

int N = txt.length();

// pat 的初始态为 0

int j = 0;

for (int i = 0; i < N; i++) {

// 当前是状态 j，遇到字符 txt[i]，

// pat 应该转移到哪个状态？

j = dp[j][txt.charAt(i)];

// 如果达到终止态，返回匹配开头的索引

if (j == M) return i - M + 1;

}

// 没到达终止态，匹配失败

return -1;

}

for 0 <= j < M: # 状态

for 0 <= c < 256: # 字符

dp[j][c] = next

这个 next 状态应该怎么求呢？显然，如果遇到的字符c和pat[j]匹配的话，状态就应该向前推进一个，也就是说next = j + 1，我们不妨称这种情况为状态推进：

如果遇到的字符c和pat[j]不匹配的话，状态就要回退（或者原地不动），我们不妨称这种情况为状态重启：

那么，如何得知在哪个状态重启呢？解答这个问题之前，我们再定义一个名字：影子状态（我编的名字），用变量X表示。所谓影子状态，就是和当前状态具有相同的前缀。比如下面这种情况：

当前状态j = 4，其影子状态为X = 2，它们都有相同的前缀 "AB"。因为状态X和状态j存在相同的前缀，所以当状态j准备进行状态重启的时候（遇到的字符c和pat[j]不匹配），可以通过X的状态转移图来获得最近的重启位置。

比如说刚才的情况，如果状态j遇到一个字符 "A"，应该转移到哪里呢？首先状态 4 只有遇到 "C" 才能推进状态，遇到 "A" 显然只能进行状态重启。状态j会把这个字符委托给状态X处理，也就是dp[j]['A'] = dp[X]['A']：

int X # 影子状态

for 0 <= j < M:

for 0 <= c < 256:

if c == pat[j]:

# 状态推进

dp[j][c] = j + 1

else:

# 状态重启

# 委托 X 计算重启位置

dp[j][c] = dp[X][c]

---

影子状态X是如何得到的呢？下面先直接看完整代码吧。

public class KMP {

private int[][] dp;

private String pat;

public KMP(String pat) {

this.pat = pat;

int M = pat.length();

// dp[状态][字符] = 下个状态

dp = new int[M][256];

// base case

dp[0][pat.charAt(0)] = 1;

// 影子状态 X 初始为 0

int X = 0;

// 当前状态 j 从 1 开始

for (int j = 1; j < M; j++) {

for (int c = 0; c < 256; c++) {

if (pat.charAt(j) == c)

dp[j][c] = j + 1;

else

dp[j][c] = dp[X][c];

}

// 更新影子状态

X = dp[X][pat.charAt(j)];

}

public int search(String txt) {...}

}

先解释一下这一行代码：

// base case

dp[0][pat.charAt(0)] = 1;

这行代码是 base case，只有遇到 pat[0] 这个字符才能使状态从 0 转移到 1，遇到其它字符的话还是停留在状态 0（Java 默认初始化数组全为 0）。

影子状态X是先初始化为 0，然后随着j的前进而不断更新的。下面看看到底应该如何更新影子状态X：

int X = 0;

for (int j = 1; j < M; j++) {

...

// 更新影子状态

// 当前是状态 X，遇到字符 pat[j]，

// pat 应该转移到哪个状态？

X = dp[X][pat.charAt(j)];

}

更新X其实和search函数中更新状态j的过程是非常相似的：

int j = 0;

for (int i = 0; i < N; i++) {

// 当前是状态 j，遇到字符 txt[i]，

// pat 应该转移到哪个状态？

j = dp[j][txt.charAt(i)];

...

}

其中的原理非常微妙，注意代码中 for 循环的变量初始值，可以这样理解：后者是在txt中匹配pat，前者是在pat中匹配pat[1:]，状态X总是落后状态j一个状态，与j具有最长的相同前缀。所以我把X比喻为影子状态，似乎也有一点贴切。

另外，构建 dp 数组是根据 base casedp[0][..]向后推演。这就是我认为 KMP 算法就是一种动态规划算法的原因。

至此，KMP 算法就已经再无奥妙可言了！看下 KMP 算法的完整代码吧：

public class KMP {

private int[][] dp;

private String pat;

public KMP(String pat) {

this.pat = pat;

int M = pat.length();

// dp[状态][字符] = 下个状态

dp = new int[M][256];

// base case

dp[0][pat.charAt(0)] = 1;

// 影子状态 X 初始为 0

int X = 0;

// 构建状态转移图（稍改的更紧凑了）

for (int j = 1; j < M; j++) {

for (int c = 0; c < 256; c++) {

dp[j][c] = dp[X][c];

dp[j][pat.charAt(j)] = j + 1;

// 更新影子状态

X = dp[X][pat.charAt(j)];

}

public int search(String txt) {

int M = pat.length();

int N = txt.length();

// pat 的初始态为 0

int j = 0;

for (int i = 0; i < N; i++) {

// 计算 pat 的下一个状态

j = dp[j][txt.charAt(i)];

// 到达终止态，返回结果

if (j == M) return i - M + 1;

}

// 没到达终止态，匹配失败

return -1;

}

经过之前的详细举例讲解，你应该可以理解这段代码的含义了，当然你也可以把 KMP 算法写成一个函数。核心代码也就是两个函数中 for 循环的部分，数一下有超过十行吗？

[labuladong]{.underline}

你只要把住两点就行了：

1、遍历的过程中，所需的状态必须是已经计算出来的。

2、遍历的终点必须是存储结果的那个位置。

PS：但凡遇到需要递归的问题，最好都画出递归树，这对你分析算法的复杂度，寻找算法低效的原因都有巨大帮助

int fib(int n) {

if (n == 2 || n == 1)

return 1;

int prev = 1, curr = 1;

for (int i = 3; i <= n; i++) {

int sum = prev + curr;

prev = curr;

curr = sum;

}

return curr;

}

首先，这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。啥叫相互独立？你肯定不想看数学证明，我用一个直观的例子来讲解。

比如说，你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高…… 为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高…… 当然，最终就是你每门课都是满分，这就是最高的总成绩。

得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，”每门科目考到最高”这些子问题是互相独立，互不干扰的。

但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，此消彼长。这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为子问题并不独立，语文数学成绩无法同时最优，所以最优子结构被破坏。

PS：为啥 dp 数组初始化为 amount + 1 呢，因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值

最优子结构并不是动态规划独有的一种性质，能求最值的问题大部分都具有这个性质；但反过来，最优子结构性质作为动态规划问题的必要条件，一定是让你求最值的，以后碰到那种恶心人的最值题，思路往动态规划想就对了，这就是套路。

动态规划不就是从最简单的 base case 往后推导吗，可以想象成一个链式反应，以小博大。但只有符合最优子结构的问题，才有发生这种链式反应的性质

----------

「状态」很明显，就是当前拥有的鸡蛋数K和需要测试的楼层数N。随着测试的进行，鸡蛋个数可能减少，楼层的搜索范围会减小，这就是状态的变化。

「选择」其实就是去选择哪层楼扔鸡蛋。回顾刚才的线性扫描和二分思路，二分查找每次选择到楼层区间的中间去扔鸡蛋，而线性扫描选择一层层向上测试。不同的选择会造成状态的转移。

现在明确了「状态」和「选择」，动态规划的基本思路就形成了：肯定是个二维的dp数组或者带有两个状态参数的dp函数来表示状态转移；外加一个 for 循环来遍历所有选择，择最优的选择更新结果：

SuperEggDrop

Drop eggs is a very classical problem.

Some people may come up with idea O(KN\^2)

where dp[K][N] = 1 + max(dp[K - 1][i - 1],dp[K][N - i]) for i in 1...N.

However this idea is very brute force, for the reason that you check all possiblity.

So I consider this problem in a different way:

dp[M][K]means that, given K eggs and M moves,

what is the maximum number of floor that we can check.

The dp equation is:

dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1,

which means we take 1 move to a floor,

if egg breaks, then we can check dp[m - 1][k - 1] floors.

if egg doesn't breaks, then we can check dp[m - 1][k] floors.

dp[m][k] is similar to the number of combinations and it increase exponentially to N

public int superEggDrop(int K, int N) {

int[][] floors = new int[N + 1][K + 1];

int move = 0;

while (floors[move][K] < N) {

++m;

for (int egg = 1; egg <= K; ++egg)

floors[move][egg] = floors[move - 1][egg] + 1 + floors[move - 1][egg - 1];

}

return m;

}

The dp equation is:

dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1,

assume, dp[m-1][k-1] = n0, dp[m-1][k] = n1

the first floor to check is n0+1.

if egg breaks, F must be in [1,n0] floors, we can use m-1 moves and k-1 eggs to find out F is which one.

if egg doesn't breaks and F is in [n0+2, n0+n1+1] floors, we can use m-1 moves and k eggs to find out F is which one.

So, with m moves and k eggs, we can find out F in n0+n1+1 floors, whichever F is.

---

Great, I understand this solution too.

The key concept of original O(KN\^2) solution is to try all the floor to get the min cost min(max(broke, not broke)) as the answer.

This solution is somehow a reverse thinking:

No matter which floor you try, egg will only break or not break, if

break, go to downstairs, if not break, go to upstairs.
No matter you go up or go down, the num of all the floors is always

upstairs + downstairs + the floor you try, which is dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1.

====

the logic of "dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1", my confusion is, if dp[m - 1][k - 1] and dp[m - 1][k] are two different case break or not break; why we combine them together, instead of use the smaller one? would you please explain more?

→

This one move will separate the floors into two non-overlapping groups, below or above (the current level we choose to drop the egg); so no matter what happened to the egg, we only need to check one of those two group. If we need to check the level below the current level, then it means the egg is break, so the maximum level we are able to check is dp[m - 1][k - 1]. Otherwise if we need to check the level above or equal o the current level, it means the egg is not break, so the maximum level we can check is dp[m - 1][k], we should only return dp[m - 1][k - 1] + dp[m - 1][k]; however, we count the level from 0, instead of 1, so we need to add the extra one level (i.e; if dp[m - 1][k - 1] = 1 and dp[m - 1][k] = 2, means we can check (2 + 3 == 5) levels, so we need to return 4; which is dp[m - 1][k - 1] + dp[m

1][k] + 1)

Notes:

Find max “1” matrix in a square

Instead to create a cache and initialise all element by copying when I,j =0.

Better solution is to clone input “matrix” this will lead to faster and cleaner code

If(I=0 || j=0) {// do nothing because those element remain unchanged in matrix copy}

For Two sum, should raise Exception e.g. no findings rather than

return “null”

public int[] [twoSum]{.underline}(int[] nums, int target) {

for (int i = 0; i < nums.length; i++) {

for (int j = i + 1; j < nums.length; j++) { // I used int j=i, which is wrong as it may cause one item to be used twice

if (nums[j] == target - nums[i]) {

return new int[] { i, j };

}

throw new IllegalArgumentException("No two sum solution");

}

Return specific Exception, e.g.

throw new IllegalArgumentException("No two sum solution");

Error of two sums

if(map1.containsKey(diff)) {

return new int[]{i, map1.get(diff)};

} else{

// be careful put number itself (rather than supplement) to map

map1.put(nums[i], i);

}

Summary:
- If possible, make use of HashMap to increase search performance
- If there are two loops, try to reduce to use one in-flight
  
  hashmap lookup
Multiply string
- Naiive solution

ublic String [multiply]{.underline}(String num1, String num2) {

String n1 = new StringBuilder(num1).reverse().toString();

String n2 = new StringBuilder(num2).reverse().toString();

int[] d = new int[num1.length()+num2.length()];

//multiply each digit and sum at the corresponding positions

for(int i=0; i<n1.length(); i++){

for(int j=0; j<n2.length(); j++){

d[i+j] += (n1.charAt(i)-'0') * (n2.charAt(j)-'0');

}

}

StringBuilder sb = new StringBuilder();

//calculate each digit

for(int i=0; i<d.length; i++){

int mod = d[i]%10;

int carry = d[i]/10;

if(i+1<d.length){

d[i+1] += carry;

}

sb.insert(0, mod);

}

//remove front 0's

while(sb.charAt(0) == '0' && sb.length()> 1){

sb.deleteCharAt(0);

}

return sb.toString();

}

-----Best Multiply String---

private static String multiply(String num1, String num2) {

int nLen1 = num1.length(), nLen2=num2.length();

int[] result = new int[nLen1+nLen2];

for(int c1=nLen1-1;c1>=0;c1--) {

for(int c2=nLen2-1;c2>=0;c2--){

int nMulti= (num1.charAt(c1) - '0') * (num2.charAt(c2) - '0');

int sum = nMulti + result[c1+c2+1];

result[c1+c2] += sum / 10; //This is for “carry”, so must to be “+” in front of “=”

result[c1+c2+1] = sum % 10; // This is a reminder, so this only be assigned without “+”

}

}

StringBuffer buff = new StringBuffer();

for(int p:result) {

if(!(result.length==0 && p==0)) {

//remove prefix 0

buff.append(p);

}

}

return buff.toString();

}

greedy algorithm

[Greedy]

const int N = 5;

int Count[N] = {5,2,2,3,5};//每一张纸币的数量

int Value[N] = {1,5,10,50,100};

int [solve]{.underline}(int money) {

int num = 0;

for(int i = N-1;i>=0;i--) {

int c = min(money/Value[i],Count[i]);//每一个所需要的张数

money = money-c*Value[i];

num += c;//总张数

}

if(money>0) num=-1;

return num;

}

Add One:

private static int[] plusOneBest(int[] ary) {

for (int i = ary.length - 1; i >= 0; i--) {

if (ary[i] != 9) {

ary[i]++; //[!] Here is key step, for two cases: (1) last digit, add one then exit (2) Next digit with carry, add on and exit

break;

} else {

ary[i] = 0;

}

}

if (ary[0] == 0) {

int[] aryRtn = new int[ary.length + 1];

System.arraycopy(aryRtn, 1, ary, 0, ary.length);

aryRtn[0] = 1;

return aryRtn;

} else {

return ary;

}

}

Add two Single nodes

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode(int x) { val = x; }

* }

*/

class Solution {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode lResult = new ListNode(0);

int carry=0,sum =0;

ListNode itNode = lResult; // [!] to setup an iterator

while(l1!=null || l2!=null){

// sum = l1.val + l2.val;

sum = (l1!=null?l1.val:0) + (l2!=null?l2.val:0); // to void null in get reference

sum += carry; // to accumulate 'carry'

carry = sum /10;

// lResult.val = sum % 10;

itNode.next = new ListNode(sum % 10);

itNode = itNode.next; // [!] this is the key step

if(l1!=null) {

l1 = l1.next;

}

if(l2!=null){

l2 = l2.next;

}

if(carry>0) itNode.next = new ListNode(carry);

}

return lResult.next;

}

}

Longest unique characters
- Naive approach

class Solution {

public int lengthOfLongestSubstring(String s) {

// analysis:

// embeded two loops to foreach every element and inner loop step from current element of 1st loop

// check whether each sub-string is all unique

// if so, get length and compare with global temp max length

int maxLen=0;

for(int i=0;i<s.length();i++) {

//for inner loop, it start from i+1 (rather than i)

for(int j=i+1;i<=s.length();j++){

if(noDup(s, i , j)){

maxLen = Math.max(maxLen, (j-i));

}

}

}

return maxLen;

}

private boolean noDup(String sub, int start, int end){

//check whether thsi sub string is unique

// char[] aryOccurance=new char[127];

// int[] aryOccurance=new int[127];

Set<Character> set=new HashSet<>();

for(int k=start;k<end;k++){

Character c = sub.charAt(k);

if(set.contains(c)){

return false;

}else{

set.add(c);

}

}

return true;

}

}

Sliding window

[https://developpaper.com/share-several-algorithmic-interview-questions-related-to-sliding-window/]{.underline}

[Longest Substring Without Repeating Characters]{.underline}

public int lengthOfLongestSubstring(String s) {

Map<Character, Integer> map= new HashMap<>();// map to cache position of each occruance

int start=0, len=0;

// abba

for(int i=0; i<s.length(); i++) {

char c = s.charAt(i);

if (map.containsKey(c)) {// here is the key step for “without repeating chars” in questions.

if (map.get(c) >= start)

start = map.get(c) + 1;// found duplicate, so get started a new round, assign start from 1st occurance of ‘duplicate char’ plus one.

}

len = Math.max(len, i-start+1);

map.put(c, i);

}

return len;

}

My solution vs leetcode one, latter one is much more consice

// better solution leveraging slide window

// Runtime: 12 ms, faster than 26.95% of Java online submissions for Longest Substring Without Repeating Characters.

public int lengthOfLongestSubstring(String s){

Set<Character> set =new HashSet<>();

int maxLen = 0, left=0,right =-1, n=s.length();

while(left<n) {

if((right+1)<n && !set.contains(s.charAt(right+1))){

// not in slide window

right++;//expand slide window

set.add(s.charAt(right));

}else{

// dup with existing slide window

// shrink window

set.remove(s.charAt(left));

left++;

}

maxLen = Math.max(maxLen, right - left +1);// [!] be carefulf there is "+1" as this is for getting count

}

return maxLen;

}

-----leetcode solution-----

public int lengthOfLongestSubstring(String s){

int i=0,j=0,n=s.length(),rtn=0;

Set<Character> set = new HashSet<>();

while(i<n && j<n) {

if(!set.contains(s.charAt(j))) {

set.add(s.charAt(j++));

rtn = Math.max(rtn, j-i) ;

}else{

set.remove(s.charAt(i++));

}

}

return rtn;

}

-----------

Palindrome integer (not string)

class Solution {

public boolean isPalindrome(int x) {

//first of all, boundary (or edge case)

if(x<0 || (x!=0 && x%10==0)) {

return false;

}

int reverse =0;

while(x> reverse) {

reverse = reverse * 10 + x%10;

x /= 10;

}

// When the length is an odd number, we can get rid of the middle digit by revertedNumber/10

// For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123,

// since the middle digit doesn't matter in palindrome(it will always equal to itself), we can simply get rid of it.

return x == reverse || x == reverse/10;

}

}

Find longest common sub array among two arrays

[DP]

public static int findLength_dp(int[] A, int[] B) {

// for dynamic programing, normally it compare itself with its sibling, using max/min

// try to construct a matrix to keep track of path

int m=A.length,n=B.length,max=0;

int[][] memo = new int[m+1][n+1]; // "+1" to keep extra space

for(int i = 0;i <= m;i++) {

for (int j = 0; j <= n; j++) {

//for DP, firstly to setup begin point

if(i==0 || j==0) {

memo[i][j]=0;

}else{

if(A[i-1]==B[j-1]){ // it they are same

memo[i][j] = 1+ memo[i-1][j-1]; // increase one to cache

max = Math.max(max,memo[i][j]); // get global max

}

}

}

}

return max;

}

Dynamic programing:

重叠子问题、最优子结构、状态转移方程就是动态规划三要素。

What is dynamic programming?

Simply put, dynamic programming is an optimization technique that we can use to solve problems where the same work is being repeated over and over. You know how a web server may use caching? Dynamic programming is basically that.

However, dynamic programming doesn’t work for every problem. There are a lot of cases in which dynamic programming simply won’t help us improve the runtime of a problem at all. If we aren’t doing repeated work, then no amount of caching will make any difference.

A problem can be optimized using dynamic programming if it:

has an optimal substructure.
has overlapping subproblems

[Optimal substructure]{.underline} simply means that you can find the optimal solution to a problem by considering the optimal solution to its subproblems.

Overlapping Subproblems

Overlapping subproblems is the second key property that our problem must have to allow us to optimize using dynamic programming. Simply put, having overlapping subproblems means we are computing the same problem more than once.

Imagine you have a server that caches images. If the same image gets requested over and over again, you’ll save a ton of time. However, if no one ever requests the same image more than once, what was the benefit of caching them?

[Dynamic Programming Methods]{.underline}

DP offers two methods to solve a problem:

1. Top-down with Memoization

In this approach, we try to solve the bigger problem by recursively finding the solution to smaller sub-problems. Whenever we solve a sub-problem, we cache its result so that we don’t end up solving it repeatedly if it’s called multiple times. Instead, we can just return the saved result. This technique of storing the results of already solved subproblems is called Memoization.

2. Bottom-up with Tabulation

Tabulation is the opposite of the top-down approach and avoids recursion. In this approach, we solve the problem “bottom-up” (i.e. by solving all the related sub-problems first). This is typically done by filling up an n-dimensional table. Based on the results in the table, the solution to the top/original problem is then computed.

Tabulation is the opposite of Memoization, as in Memoization we solve the problem and maintain a map of already solved sub-problems. In other words, in memoization, we do it top-down in the sense that we solve the top problem first (which typically recurses down to solve the sub-problems).

Let’s apply Tabulation to our example of Fibonacci numbers. Since we know that every Fibonacci number is the sum of the two preceding numbers, we can use this fact to populate our table.

Here is the code for our bottom-up dynamic programming approach:

class Fibonacci {

public int CalculateFibonacci(int n) {

int dp[] = new int[n+1];

//base cases

dp[0] = 0;

dp[1] = 1;

for(int i=2; i<=n; i++)

dp[i] = dp[i-1] + dp[i-2];

return dp[n];

}

public static void main(String[] args) {

Fibonacci fib = new Fibonacci();

System.out.println("5th Fibonacci is ---> " + fib.CalculateFibonacci(5));

System.out.println("6th Fibonacci is ---> " + fib.CalculateFibonacci(6));

System.out.println("7th Fibonacci is ---> " + fib.CalculateFibonacci(7));

}

Generally speaking, dynamic programming is the technique of storing repeated computations in memory, rather than recomputing them every time you need them. The ultimate goal of this process is to improve runtime. Dynamic programming allows you to use more space to take less time.

Dynamic programming relies on overlapping subproblems, because it uses memory to save the values that have already been computed to avoid computing them again. The more overlap there is, the more computational time is saved.

Top-down and bottom-up

Top-down and bottom-up refer to two general approaches to dynamic programming. A top-down solution starts with the final result and recursively breaks it down into subproblems. The bottom-up method does the opposite. It takes an iterative approach to solve the subproblems first and then works up to the desired solution.

both solutions are equally valid and that one solution can be determined from the other. In an interview situation, although bottom-up solutions often result in more concise code, either approach is appropriate. I recommend that you use whatever solution makes the most sense to you.

The important point is that top-down = recursive and bottom-up = iterative.

There are four steps in the FAST method:

First solution
Analyze the first solution
Identify the Subproblems
Turn the solution around

First solution

This is an important step for any interview question but is particularly important for dynamic programming. This step finds the first possible solution. This solution will be brute force and recursive. The goal is to solve the problem without concern for efficiency. It means that if you need to find the biggest/ smallest/longest/shortest something, you should write code that goes through every possibility and then compares them all to find the best one.

Your solution must also meet these restrictions:

The recursive calls must be self-contained. That means no global

variables.
You cannot do tail recursion. Your solution must compute the results

to each subproblem and then combine them afterwards.
Do not pass in unnecessary variables. Eg. If you can count the depth

of your recursion as you return, don’t pass a count variable into your recursive function.

Analyze the first solution

In this step, we will analyze the first solution that you came up with. This involves determining the time and space complexity of your first solution and asking whether there is obvious room for improvement.

// Compute the nth Fibonacci number recursively. // Optimized by caching subproblem results public int fib(int n) {

if (n < 2) return n;

// Create cache and initialize to -1

int[] cache = new int[n+1];

for (int i = 0; i < cache.length; i++) {

cache[i] = -1;

}

// Fill initial values in cache

cache[0] = 0;

cache[1] = 1;

return fib(n, cache);

}

// Overloaded private method

private int fib(int n, int[] cache) {

// If value is set in cache, return

if (cache[n] >= 0) return cache[n];

// Compute and add to cache before returning

cache[n] = fib(n-1, cache) + fib(n-2, cache);

return cache[n];

}

Fig 3. Top-down dynamic Fibonacci solution

Turn the solution around

Since we now have a top-down solution, it is possible to reverse the process and solve it from the bottom up. This [can be done by starting with the base cases and building up the solution from there by computing the results of each subsequent subproblem, until we reach our result.]{.underline}

In this problem, [our base cases are fib(0) = 0 and fib(1) = 1. From these two values, we can compute the next largest Fibonacci number, fib(2) = fib(0) + fib(1). Once we have the value of fib(2), we can calculate fib(3) etc. As we successively compute each Fibonacci number, the previous values are saved and referred to as necessary, eventually reaching fib(n).]{.underline}

Our code for this process is fairly straightforward (fig 5).

This process yields a bottom-up solution. Since we iterate through all of the numbers from 0 to n once, our time complexity will be O(n) and our space will also be O(n), since we create a 1D array from 0 to n. This makes our current solution comparable to the top-down solution, although without recursion. This code is likely easier to understand.

// Compute the nth Fibonacci number iteratively

public int fib(int n) {

if (n == 0) return 0;

// Initialize cache

int[] cache = new int[n+1];

cache[1] = 1;

// Fill cache iteratively

for (int i = 2; i <= n; i++) {

cache[i] = cache[i-1] + cache[i-2];

}

return cache[n];

}

Fig 5. Bottom-up dynamic Fibonacci solution

it is possible to improve our solution further. During the computation process, we only refer to the most recent two subproblems (cache[i-1] and cache[i-2]) to compute the value of the current subproblem. Therefore, cache[0] through cache[i-3] are unnecessary and do not need to be kept in memory.

We can, therefore, improve the space complexity of our solution to O(1) by only caching the most recent two values.

// Compute the nth Fibonacci number iteratively // with constant space. We only need to save // the two most recently computed values

public int fib(int n) {

if (n < 2) return n;

int n1 = 1, n2 = 0;

for (int i = 2; i < n; i++) {

int n0 = n1 + n2;

n2 = n1;

n1 = n0;

}

return n1 + n2;

}

For any problem where you are asked [to find the most/least/ largest/smallest]{.underline} etc, an excellent technique [is to compare every possible combination]{.underline}. Although it will be inefficient, efficiency is not the most important current consideration and a solution of that nature is easy to make dynamic.

Make change

// Brute force solution. Go through every

// combination of coins that sum up to c to // find the minimum number

public static int makeChange(int c) {

int[] coins = new int[]{10, 6, 1};

if (c == 0) return 0;

int minCoins = Integer.MAX_VALUE;

// Try removing each coin from the total and // see how many more coins are required

for (int coin : coins) {

// Skip a coin if it’s value is greater

// than the amount remaining

if (c - coin >= 0) {

int currMinCoins = makeChange(c - coin);

if (currMinCoins < minCoins)

minCoins = currMinCoins;

} }

// Add back the coin removed recursively

return minCoins + 1;

}

How to convert one naive loop solution to dynamic programming

top-down approach

Based on this understanding, we can turn our solution into a top-down dynamic solution. We can cache the results as they are computed. That means that we will cache the minimum number of coins needed to make various smaller amounts of change.

Like the Fibonacci problem, our code doesn’t actually have to change very much. It’s only necessary to overload our function with another that can initialize the cache. Then we update the original function in order to check the cache before doing the computation and saving the result to the cache afterwards

// Top down dynamic solution. Cache the values as we compute them

// transform naive approach to top-down need:

// overload existing method with new one accept cache

// while existing one do two tasks: (1) initialize cache (2) call new method passing in cache

public int makeChange_top_down(int c) {

// Initialize cache with values as -1

int[] cache = new int[c + 1];

for (int i = 1; i < c + 1; i++)

cache[i] = -1;

return makeChange_top_down(c, cache);

}

// Overloaded recursive function

private int makeChange_top_down(int c, int[] cache) {

int[] coins = new int[]{10, 6, 1};

// Return the value if it’s in the cache

if (cache[c] >= 0) return cache[c];

int minCoins = Integer.MAX_VALUE; //declare result oppositely, e.g. question is "min", so init return value would be Integer.MAX_VALUE

// Find the best coin

for (int coin : coins) {

if (c - coin >= 0) {

int currMinCoins =

makeChange_top_down(c - coin, cache);

if (currMinCoins < minCoins)

minCoins = currMinCoins;

} }

// Save the value into the cache

cache[c] = minCoins + 1; // add one to the return value

return cache[c];

}

Turn the solution around

Once the top-down solution is completed, it’s possible to flip it around. We do this by solving the same subproblems in reverse order. Rather than starting with our result in mind, we start with no change and work our way up until we reach the solution.

The next step is to determine the subproblems that must be solved, in order to solve successive subproblems. If we want to compute makeChange(c), then we will have n different subproblems. If our coins are {10, 6, 1}, we need to have the solutions for makeChange(c - 10), makeChange(c - 6), and makeChange(c - 1).

Once makeChange() is solved for 0 through c - 1, it will be easy to compute the value of makeChange(c). This is done by using the first value, 0 as our base case. We can then compute the remaining values from the previously computed values.

// Bottom up dynamic programming solution. // Iteratively compute number of coins for // larger and larger amounts of change

public int makeChange(int c) {

int[] cache = new int[c + 1];

for (int i = 1; i <= c; i++) {

int minCoins = Integer.MAX_VALUE;

// Try removing each coin from the total

// and see which requires the fewest

// extra coins

for (int coin : coins) {

if (i - coin >= 0) {

int currCoins = cache[i-coin] + 1;

if (currCoins < minCoins) {

minCoins = currCoins;

}

} }

cache[i] = minCoins;

}

return cache[c];

}

2024 10
2023 98
2022 51
2021 19
2020 25
2019 7
2018 39
2017 38
2016 50

2024

Streamline Your Workflow by Fastest way to run Maven Builds with a Keyboard Shortcut in IntelliJ

A leader takes people where they want to go. A great leader takes people where they don’t necessarily want to go, but ought to be. —Rosalynn Carter, forme...

使用 c3p0 连接池解决 Spring Boot 中断的数据库连接问题（解决 Spring Boot 中断的数据库连接问题）

一旦你知道答案，一切都会变得简单。” —— 戴夫·梅吉（Dave Magee）

Resolving Disconnected Database Connections in Spring Boot with c3p0 Connection Pool

“Everything is easy, once you know the answer. —Dave Magee

IntelliJ sudden crashed of compile error MapStruct or Kotlin

Life begins at the edge of the comfort zone

Deep dive for word press preview nonce

One must learn by doing the thing; for though you think you know it, you have no certainty, until you try. —Sophocles

你不了解的word press 的 preview nonce

One must learn by doing the thing; for though you think you know it, you have no certainty, until you try. —Sophocles

Notes and pitfalls for redis development

A younger brother knows his older brother better than anyone else.

2023

Awesome Jq For Coders

Mastering JSON Data Manipulation with jq: A Comprehensive Guide

Awesome Xlookup Over Vlookup

XLOOKUP vs. VLOOKUP: Excel’s Dynamic Duo for Data Lookup

Ports Discovery On Hosts

To find out the port numbers running in servers

Troubleshoot Mariadb In Linux

The simplest way to check an mariadb is runnning systemctl status mariadb

Az Cli

To run commands in VMs in Azure

From filter to CNN (Convolutional Network)

The biggest room in the world is the room for improvement. Filters in Convolutional Neural Networks (CNNs) In the context of convolutional neural net...

Unlocking Network Secrets A MacBook Traceroute Tutorial

A younger brother knows his older brother better than anyone else.

How to Test Logging Output in JUnit

A younger brother knows his older brother better than anyone else.

Cheap and flexible computing

whether it seems possible or not - go for it Cheaper X 2 to EC2, to use Fargate Spot With Fargate Spot you can run interruption tolerant Amazon ECS t...

How Guru to use Capturing Groups in Python Regular Expressions

A dream deferred is a dream denied. -Langston Hughes

Composition and Aggregation in Object-Oriented Modeling

“The past does not equal the future unless you live there.” - Tony Robbins

Exploring the `useRequest` Hook from `ahooks`

“The best way to predict the future is to invent it.” - Alan Kay

Understanding Python’s Late Binding Behavior A Deep Dive

“Hang Out with People Who are Better than You.” — Warren Buffett

Understanding React export a Component

A young idler, an old beggar. - William Shakespeare Understanding React export a Component In this blog post, we will dive into the code of the RepoU...

why use mid = (low + high) // 2 but not (high-low)//2

“Don’t let yesterday take up too much of today.” - Will Rogers

Introduction to Generator Expressions in Python

“It always seems impossible until it’s done.” - Nelson Mandela

Introduction to Generator Expressions in Python

We never lose friends but just start to find real ones. - William Shakespeare

Understanding Backpropagation in Neural Networks

Your past is a lesson. Not a life sentence. Forgive yourself and focus on the future. -Mel Robbins

Understanding Confusion Matrix in WEKA

Your past is a lesson. Not a life sentence. Forgive yourself and focus on the future. -Mel Robbins

Useful Shortcut Tips for MacBook Office Workers

A young idler, an old beggar. - William Shakespeare

Understanding d-Separation in Graphical Models

A young idler, an old beggar. - William Shakespeare

How To Split Sql Insert Statement

“Don’t let yesterday take up too much of today.” - Will Rogers

docker-commands-bible

“Don’t let yesterday take up too much of today.” - Will Rogers

Weird Problem Changed Configurations In Pom Xml Not Work

“I can’t relate to lazy people. We don’t speak the same language.” — Kobe Bryant

AI Basics, Talk About Searches

“What you seek is seeking you.” — Rumi

Xpath Playground Best Practices

A young idler, an old beggar. - William Shakespeare

UUID deep dive

A young idler, an old beggar. - William Shakespeare

Compile Error Java Kotlin Coexist Project In Intellij

The biggest room in the world is the room for improvement. — Helmut Schmidt

Who Is Running On Port 8080

A young idler, an old beggar. - William Shakespeare

Let AI To Manage Stripe Payment

A young idler, an old beggar. - William Shakespeare

RestTemplate Powered Http2

Why HTTP/2 is Better

Compile Error Java Kotlin Coexist Project In Intellij

How to Fine Tune RestTemplate

how-to-travel-in-cairns

大堡礁的一些知识

Compile Error Java Kotlin Coexist Project In Intellij

The root cause is your customized HttpMessageConverter stopped processing of WebSecurity

io_mockk_MockKException__no_answer_found_for

A young idler, an old beggar. - William Shakespeare

which-port-my-service-is-running

Summary As a Java developer, it’s important to know how to find out which port number your Spring service is running on. This information is useful when you ...

How To Install Sonarqube Via Docker

“Hang Out with People Who are Better than You.” — Warren Buffett

how-to-auto-login-for-citrix-receiver-vpn-client

“Hang Out with People Who are Better than You.” — Warren Buffett

pip-install-behind-proxy

Failure of timeout or connection when running pip install

Elk Search Tips

message:/'Invoking SP with quoteContext*werqewr-1234asdf-sdf23-9d83-asdf23*'/

what is StrictHostKeyChecking in ssh

What’s and how to avoid error of the authenticity of host ‘xxx’ can’t be established You can suppress the “The authenticity of host ‘’ can’t be established” ...

know in and out of free command

You are not a drop in the ocean, you are the entire ocean in a drop.

Chinese Verb

知其雄，守其雌什么意思

Deep dive for errors during Spring Boot Tests

Transaction silently rolled back because it has been marked as rollback-only

Is Import Star Devil

Why using wildcard import is devil

How To Run Testing Multiple Threading

A sample to test concurrent JPA modifications

Stress Test Concurrency Jpa Entity Random Update

A runnable example in Java to create a cucumber test code files to simulate multiple read and write entity via JPA repository

How To Use Aop Test Utils.jpg

What’s purpose of AopTestUtils.getTargetObject()?

A Brief Introduction To Lookbehind And Lookahead In Regular Expressions

“The only way to do great work is to love what you do.” - Steve Jobs

master-spring-properties-injection

“The only way to do great work is to love what you do.” - Steve Jobs

Transaction Commit In Hibernate Jpa

Give me sample to test concurrent JPA modifications

Spring Boot Test In A Nutshell

what’s spring boot test annotation

How To Detach In Jpa

A real sample of using JPA detach

Feature Flag Spring Boot

summary Feature flag library in spring boot

What’s Difference Of Cny And Cnh

what’s difference of CNY and CNH CNY and CNH are both currencies used in China, but they are different in a few important ways:

Hibernate Transaction Management

Details of how hibernate transaction management works

Spring Cloud Masterpiece 10

In spring cloud what’s when to use feign client and when to sue resttemplate

Spring Cloud Master Piece 9

What’s spring cloud config Spring Cloud Config is a distributed configuration server that provides a centralized location to manage external properties for a...

Spring API Gateway Best Practices

Splitting A Monolithic Application Into Microservices

Splitting a monolithic application into microservices can be a complex process that requires careful planning and implementation. Here is a high-level approa...

Spring Cloud Master Piece 6

Sample me build a micro service payment system with spring cloud Here’s an example of building a microservice payment system using Spring Cloud:

Difference Between Using Ribbon And A Load Balancer

The main difference between using Ribbon and a Load Balancer is the location of the load balancing logic.

Spring Cloud Master Piece 5

How to add security among micro service in spring boot

Spring Cloud Master Piece 4

How to use service discovery in spring book

Spring Cloud Master Piece 3

Sample me how to build a eureka service discovery

Spring Cloud Master Piece 2

what’s usage of bootstrap yml In a Spring Boot application, the bootstrap.yml (or bootstrap.properties) file is used for configuring the application’s enviro...

Spring Cloud Master Piece 1

what’s API gateway An API Gateway is a key component in microservices architecture that acts as a single entry point for client requests to a microservices-b...

annoying-debug-logs-in-springboot-test

Stop annoying debug logs in spring boot test

how-to-stop-quartz-scheduling-during-springboot-test

Date Is The Most Ignored Treasure In Macbook

“The only way to do great work is to love what you do.” - Steve Jobs

Mysql Operator To Extract Json

“Believe you can and you’re halfway there.” - Theodore Roosevelt

Master Microfrontends

“The only way to do great work is to love what you do.” - Steve Jobs

How To Convert One Monolith Java System To Microservices

Whatever is worth doing is worth doing well.

How To Config JFR Java Flight Control

“Climb the mountains and get their good tidings. Nature’s peace will flow into you as sunshine flows into trees. The winds will blow their own freshness i...

How To Read Jdk Mission Control Report

Live the life you’ve imagined.

Jdk Mission Control Can Not Start In Macbook M1

“Climb the mountains and get their good tidings. Nature’s peace will flow into you as sunshine flows into trees. The winds will blow their own freshness i...

How To Keep Multiple Copy Paste Value In Macbook

“Winning is nice if you don’t lose your integrity in the process.” — Arnold Horshak

Google マップ内の写真のコメントが表示されない

紹介私は、私のOppo Androidスマートフォンのアプリ「Googleマップ」で奇妙な問題が発生していることに気づきました。Googleマップで特定の場所（例えば「中央公園」）を検索すると、通常、このアプリは公園の写真やコメントリストを表示するはずです。例えば、誰かが公園の芝生や川の写真を投稿し、便利な場所...

Les commentaires des photos ne s’affichent pas dans Google Maps.

Introduction J’ai remarqué un problème étrange avec l’application “Google Maps” de mon téléphone Android Oppo. Lorsque vous recherchez un lieu sur Google Map...

Is Kerberos One Ssl/tls?

Nothing is as easy as it looks.

How To Save Expect Script Run Output To File Locally

Nothing is as easy as it looks.

Refind Java Concurrency

You are not a drop in the ocean, you are the entire ocean in a drop.

Refind Java Solid Principles

You are not a drop in the ocean, you are the entire ocean in a drop.

How To Extract Table Name From Sql By Python

You are not a drop in the ocean, you are the entire ocean in a drop.

How to find non-empty json value in mysql

You are not a drop in the ocean, you are the entire ocean in a drop.

master-cglib-in-java

You are not a drop in the ocean, you are the entire ocean in a drop.

What is shape function in python pandas

An honest days’ work makes for a good night’s sleep.

What is shape function in python pandas

Imagination is the key ingredient to a happy life.

What is default logic in python try except else

Keep an eye on the fruits of your labor.

Not just use git but know how git symbolic-ref work

Superheros come in all shapes and sizes.

Fix rejection error in Hexo

The heart can see what is invisible to the eye.

Guide to code productively, get more time back for you

The heart can see what is invisible to the eye.

Is Fibonacci sequence that starts with 0 or 1

The best way to predict the future is to create it.

To increase your productivity 10 times, learn expect and read this blog

Som are born beautiful. The rest of us have to work at it.

Treasure Bowl for SQL, helpful for your daily database jobs

Don’t be greedy. Half of something is better than all nothing.

How to fix most permission issues when using Git

The best way to predict the future is to create it.

One killer page to fix most permission issues when using Git

The best way to predict the future is to create it.

How to check your CPU model and Linux distribution in your AWS VM

Lift is short, enjoy the ride.

2022

Magic-in-Micronaut-JPA

The best way to predict the future is to create it.

谷歌地图里面照片的评论和照片在华为手机里面显示不出来

枝上柳棉吹又少, 天涯何处无芳草. –苏轼

Cannot find symbol class Generated or var

The best way to predict the future is to create it.

GraphQL noteworthy points

Life is like the ocean, it goes up and down.

Scripts bible for MySql

Be the Sun of your solar system.

Minium Workable Mvp Vimrc

”—————————————————————- “ 4. User interface “—————————————————————- “ Set X lines to the cursor when moving vertically set scrolloff=0

How to build unit/integration tests for Spring State Machine

Get busy living or get busy dying.

Magic after maven target spring-boot-run

Turn your wounds into wisdom

Bamboo pipeline deployment failure caused by Kubenetes Finalizer

Today a reader, tomorrow a leader.

Gemfire Geode Error on Peer or client version with ordinal xx not supported. Highest known version is 1.12.1 Client

Take the risk or lose the chance!

Password must not null in gemfire and geode, but I’ve assigned password in yaml properties file

Worries less, smile more!

One page to cover most commonly found errors for fat jar in SpringBoot

Kill time, or kiss time!

Awesome Shortcuts to boost productivity

One must learn by doing the thing; for though you think you know it, you have no certainty, until you try. —Sophocles

Core Java tips required an interview

Success is the sum of small efforts, repeated.

Tell me difference of truststore and keystore in short answer

Do what you say, say what you do.

GIT useful scripts or error solutions

Don’t wish for it, work for it.

Tell me difference of yarn install and npm install in short answer

Don’t find fault. Find a remedy.

Bible blog for most commonly found Gradle errors

People are smarter than you think. Give them a chance to prove themselves.

Pearls in Front end development

Be happy in front of people who don’t like you, it kills them.

Ruby from zero to hero

This is your life. Do what you love, and do it often.

Everything you’d know for Groovy interviews

Life is short. Don’t waste it with negative people who don’t appreciate you. Keep them in your heart but keep them out of your life.

To outstanding as professional MacBook pro user

The most effective way to do it, is to do it Homebrew The best practice is to run brew info before install new software. It will generally list what’s c...

Failed to install gem in Mac, incompatible architecture and missing psych

Burn your ego before it burns you.

IntelliJ Tips to boost your productivity 10 times

Don’t be afraid to make s splash.

Everything you’d know about state machine for interviews

Less expecting, more accepting.

Tips about algorithm resolving from Leetcode

Stay focused, believe that you can achieve at the highest level, surround yourself with others who believe in you and do not stray from your goals.

Solution center for Node errors

Fina a way. If there’s none, make one!

Triple your productivities by Visual studio code keyboard shortcuts

The sentence The quick brown fox jumps over the lazy dog uses every letter of the alphabet.

TypeScript noteworthy notes

The moment you start focusing on yourself, things start falling into place.

RXJS – reactive Programming like a hero

When love is real, it doesn’t lie, cheat, pretend or keep secrets.

Concurrency in Java

Little things make big things happens.

Linux Tips

Remember, some things have to end for better things to begin.

A taste of GraphQL

A good day starts with a good mindset!

A taste of GraphQL

A good day starts with a good mindset!

What’s inside magic in Spring Data JPA

A good day starts with a good mindset!

What’s inside magic in Spring Data JPA

A good day starts with a good mindset!

Why Spring turn a column name from camelNaming to snake_Naming

Don’t spend another year doing the same shit.

Some mistakes you’d avoid in java

With great power comes great responsibilities.

Untold stories for Jupiter, any differences JUnit 5 vs Junit 4

Don’t tell people your plans. Just show them your results!

Git commands you can show off for 100 years

Life is short, make a big splash!

FileNotFound Exception when loading data file in IntelliJ

Take time to do what makes your soul happy!

How to ace AWS certification just like play a game

Life isn’t about finding yourself. Life is about creating yourself.

Java Deep Notes

Code to draw a Big H with all stars

Coding is everything! Code Now!

Code to draw a Big H with all stars

Coding is everything! Code Now!

Single vs Double precisions, float vs double data type

Leave nothing for tomorrow which can be done today. -Abraham Lincoln.

SkipTest-Not-Work-In-Multiple-models-project

Leave nothing for tomorrow which can be done today. -Abraham Lincoln.

SkipTest-Not-Work-In-Multiple-models-project

Leave nothing for tomorrow which can be done today. -Abraham Lincoln.

Maven error and solution on No such host is known

Don’t promis when you are hapy. Don’t reply when you’re angry and don’t decide when you’re sad Service keep on restarting If you spot service is restartin...

Maven error and solution on No such host is known

Don’t promis when you are hapy. Don’t reply when you’re angry and don’t decide when you’re sad

Gradle build stuck

Gradle build stuck, keep on running but never ending

2021

Save my eyes, let your cell phone to read screen content to you

Too much screen time

How logging system Bootstrapped in Spring Boot Application

Summary Following diagram demonstrated the process to bootstrap and use Logback for loggings in Spring Boot applciation.

SQLServer Error about This driver is not configured for integrated authentication

Symptoms When you are using integrated authentication (Kerberos connection) for MS SqlServer connection, there is one possible error :

How to copy files from resources folder in jar and save to a file

Why to extract resources from jar to local disk

Debug of SpringBoot run not working in IntelliJ

Normal approach to debug maven

How to watch specific kubenetes deployment by labels

Failed to talk to github.com from corporation network

Background It’s typical to get various network connection issues when you run commands within corporation network. For example, you’ll find diversed issues w...

Day-Day-Up-Java

More developer friendly Threa Sleep

How to user fire extinguisher

Summary As you know, staff and your safety is paramount. So what if emergency take place, such as fire in office, how to help yourself and your colleagues by...

Deep dive into ApplicationEvent in SpringBoot

Summary As you know, there are various event will be sent (multicast) when a specific story taken place.

2021-09-22-IT-Solutions-For-Remote-Learning

IT-Solutions-For-Remote-Learning.md

Deep dive into Kubernetes Client API

Summary To talk to K8s for getting data, there are few approaches. While K8s’ official Java library is the most widely used one. This blog will look into thi...

How to get CPU name, core, 64bit and speed in command line

Summary In windows operating system, if you want to get your CPU name, core, 64bit and speed in command line. Just follow below actions:

JetBrains/IntelliJ tips

Be a good person in real life, not in social media

Whitelabel Error Page

Summary Whitelabel Error Page is the default error page in Spring Boot web app. It provide a more user-friently error page whenever there are any issues when...

Google maps no photos reviews

Summary

谷歌地图里面照片的评论显示不出来

If you’d like to view solution in YouTube, check out at https://youtu.be/ICiwuqJ-yU8

Shall I still need booster even after I got dose 3?

The greatest wealth is health!

Debts in a nutshell

A debt security represents a debt owed by the issuer to an investor. Here, the investor acts as a lender to the issuer which may be a government, organisatio...

2020

How to process data from S3 download URL

S3 download URL As you know, AWS S3 object can be downloaded/processed by S3 download URL. I’m showing you two examples on how to process S3 Object by NIO f...

Debug Stuck IntelliJ

What happened to a debug job hanging in IntelliJ (IDEAS) IDE? You may find when you try to debug a class in Intellij but it stuck there and never proceed, e....

Awesome Kotlin

Difference with Scala Kotlin takes the best of Java and Scala, the response times are similar as working with Java natively, which is a considerable advantag...

Awesome tips for Chrome

Shortcuts & tips

JVM热身

此文是作者英文原文的翻译文章，英文原文在：http://todzhang.com/posts/2018-06-10-jvm-warm-up/

Awesome tips and shortcuts for Slack

Shortcuts for Slack

Awesome Reactive programming

Key points of Reactive Programming

Awesome Swift for iOS

Frame in Swift

Swift for iOS

Mock in kotlin

Argument Matching & Answers For example, you have mocked DOC with call(arg: Int): Intfunction. You want to return 1 if argument is greater than 5 and -1 ...

Mock in kotlin

Argument Matching & Answers For example, you have mocked DOC with call(arg: Int): Intfunction. You want to return 1 if argument is greater than 5 and -1 ...

Docker

Dockers Concepts

How to decode path parameters in All REST WebServices calls

Curl

Linux Curl command

AOP

The concept of join points as matched by pointcut expressions is central to AOP, and Spring uses the AspectJ pointcut expression language by default.

Micrometer notes

As a general rule it should be possible to use the name as a pivot. Dimensions allow a particular named metric to be sliced to drill down and reason about th...

Pigeons in holes principle

# Pigeonhole principle

Awesome solutions for algorithm questions

你就会发现只要涉及递归的问题，都是树的问题。

A Facial Recognition utility in a dozen of LOC

A Facial Recognition utility in a dozen of python LOC (Lines Of Code)

Awesome SSL certificates and HTTPS

What’s TLS TLS (Transport Layer Security) and its predecessor, SSL (Secure Sockets Layer), are security protocols designed to secure the communication betwee...

Java Pesistence API Notes

JPA

JVM warm up by Escape Analysis

Why JVM need warm up I don’t know how and why you get to this blog. But I know the key words in your mind are “warm” for JVM. As the name “warm up” suggested...

Java Concurrent Column 2

This is the second half about Java Concurrent of my blog

Java Concurrent

This blog is about noteworthy pivot points about Java Concurrent Framework Back to Java old days there were wait()/notify() which is error prone, while fr...

Algorithm notes from Leecode – 1

Algorithm Leetcode

2019

Conversations with God

Feelings is the language of the soul. If you want to know what’s true for you about something, look to how your’re feeling about.

Kafka In Spring

Enable Kafka listener annotated endpoints that are created under the covers by a AbstractListenerContainerFactory. To be used on Configuration classes as fol...

Terraform

Why Terraform

Kafka

Mifid

FX Spot is not covered by the regulation, as it is not considered to be a financial instrument by ESMA, the European Union (EU) regulator. As FX is considere...

Foreign Exchange

currency pairs Direct ccy: means USD is part of currency pair Cross ccy: means ccy wihtout USD, so except NDF, the deal will be split to legs, both with...

Inter Processes Communication

IPC

2018

Seconds

nano seconds

Citrix receiver

Simple Binary Encoding (SBE)

Citrix receiver

“Cannot connect to remote desktop” with Citrix Receiver

Guice

A new type of Juice Put simply, Guice alleviates the need for factories and the use of new in your Java code. Think of Guice’s @Inject as the new new. You wi...

YAML

Key points All YAML files (regardless of their association with Ansible or not) can optionally begin with — and end with …. This is part of the YAML format a...

Distruptor

multithreading

Mockito

Feature

Protobuf

What are protocol buffers?

Sudo in a Nutshell

Sudo in a Nutshell Sudo (su “do”) allows a system administrator to give certain users (or groups of users) the ability to run some (or all) commands as root...

Zoo-keeper

ZK Motto the motto “ZooKeeper: Because Coordinating Distributed Systems is a Zoo.”

Presto DB

WHAT IS PRESTO?

Chronicle

Overview

Cucumber

Acceptance testing vs unit test It’s sometimes said that unit tests ensure you build the thing right, whereas acceptance tests ensure you build the right thi...

Scala

Scala String

akka framework of scala

philosophy The actor model adopts the philosophy that everything is an actor. This is similar to the everything is an object philosophy used by some object-o...

File Util in Apache Camel

FileUtil.class

Apache Camel

Camel’s message model In Camel, there are two abstractions for modeling messages, both of which we’ll cover in this section. org.apache.camel.Message—The ...

QuickFixJ

Settings

JXM

Exporting your beans to JMX The core class in Spring’s JMX framework is the MBeanExporter. This class is responsible for taking your Spring beans and registe...

Solace MQ

Solace PubSub+ It is a message broker that lets you establish event-driven interactions between applications and microservices across hybrid cloud environmen...

Apigee

App deployment, configuration management and orchestration - all from one system. Ansible is powerful IT automation that you can learn quickly.

Ansible

Ansible: What Is It Good For? Ansible is often described as a configuration management tool, and is typically mentioned in the same breath as Chef, Puppet, a...

flexbox

How Flexbox works — explained with big, colorful, animated gifs

Jboss tips

commands:

Locking and multithreading

Single Writer principle

KDB

KDB However kdb+ evaluates expressions right-to-left. There are no precedence rules. The reason commonly given for this behaviour is that it is a much simple...

Foreign Exchange

Foreign Exchange markets

Portactor

Better to use smart wait

Agile and SCRUM

Key concept In Scrum, a team is cross functional, meaning everyone is needed to take a feature from idea to implementation.

DevOps-Philosophy

:100:DevOps Model Defined

rxjs pipe in depth

https://stormforger.com/blog/2016/07/08/types-of-performance-testing/

How to setup nodejs to install package from intranet

Error of ‘ECONNRESET’ You may face error ECONNRESET from intranet, even appropriate proxy tools (e.g. cntlm) is running. The errors may looks like ```bash $ ...

Strategy-Of-Openshift-Releases

Release & Testing Strategy There are various methods for safely releasing changes to Production. Each team must select what is appropriate for their own ...

NodeJs Notes

commands to read files var lineReader = require(‘readline’).createInterface({ input: require(‘fs’).createReadStream(‘C:\dev\node\input\git_reset_files.tx...

Minium Viable Product

https://blog.leanstack.com/minimum-viable-product-mvp-7e280b0b9418

What is difference between declarations, providers and import in NgModule

CORS :Cross-Origin Resource Sharing

Cross-Origin Request Sharing - CORS (A.K.A. Cross-Domain AJAX request) is an issue that most web developers might encounter, according to Same-Origin-Policy,...

ngrx

Why @Effects? In a simple ngrx/store project without ngrx/effects there is really no good place to put your async calls. Suppose a user clicks on a button or...

iOS programming

View A view is also a responder (UIView is a subclass of UIResponder). This means that a view is subject to user interactions, such as taps and swipes. Thus,...

2017

cloud computering

openshift vs openstack The shoft and direct answer is `OpenShift Origin can run on top of OpenStack. They are complementary projects that work well together....

cloud computering

Concepts Cloud computing is the on-demand demand delivery of compute database storage applications and other IT resources through a cloud services platform v...

Redux

whats @Effects You can almost think of your Effects as special kinds of reducer functions that are meant to be a place for you to put your async calls in suc...

reactive programing

The second advantage to a lazy subscription is that the observable doesn’t hold onto data by default. In the previous example, each event generated by the in...

RxJS reactive extension javascript

Streams

common errors in NPM or node

code E503 code E503 when run npm install packages, e.g.

Container

The Docker project was responsible for popularizing container development in Linux systems. The original project defined a command and service (both named do...

promise vs observiable

The drawback of using Promises is that they’re unable to handle data sources that produce more than one value, like mouse movements or sequences of bytes in ...

Openshift tips

Commands bible

google analysis

How Page Value is calculated

JDK source

interface RandomAccess Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary ...

SSH SFTP

Secure FTP SFTP over FTP is the equivalant of HTTPS over HTTP, the security version

Setup WebSphere profiles and application in command line

AWS Tips

After establishing a SSH session, you can install a default web server by executing sudo yum install httpd -y. To start the web server, type sudo service htt...

Oracle

ORA-12899: Value Too Large for Column

Spring notes

Spring Bean Life Cycle Callback Methods

Kindle notes

#《亿级流量网站架构核心技术》目录一览 TCP四层负载均衡使用Hystrix实现隔离基于Servlet3实现请求隔离限流算法令牌桶算法漏桶算法分布式限流 redis+lua实现 Nginx+Lua实现使用sharding-jdbc分库分表 Disruptor+Redis...

Java JIT compiler

This is talking about Java JIT (Just-In-Time) compiler

Java Security Notes

Java Security well-behaved: programs should be prevent from consuming too much system resources

SeriableVersionUID

Noteworthy points about SeriableVersionUID in Java

R Language

s<-read.csv("C:/Users/xxx/dev/R/IRS/SHH_SCHISHG.csv") # aggregate s2<-table(s$Original.CP) s3<-as.data.frame(s2) # extract by Frequency ordered s3...

SSH and Cryptography

SFTP versus FTPS SS: Secure Shell An increasing number of our customers are looking to move away from standard FTP for transferring data, so we are ofte...

Eclipse notes

How do I remove a plug-in? Run Help > About Eclipse > Installation Details, select the software you no longer want and click Uninstall. (On Macintosh i...

Java JVM

Class loading subsystem

Maven-Notes

Maven philosophy “It is important to note that in the pom.xml file you specify the what and not the how. The pom.xml file can also serve as a documentatio...

Java New IO

Notes JDK 1.0 introduced rudimentary I/O facilities for accessing the file system (to create a directory, remove a file, or perform another task), accessi...

Network Protocols

Net Protocols

IT-Architect

SOA SOA is a set of design principles for building a suite of interoperable, flexible and reusable services based architecture. top-down and bottom-up a...

Algorithm

This page is about key points about Algorithm

Dead Lock

Concept

Java-Tricky-Tech-Questions.md

What is the difference between Serializable and Externalizable in Java? In earlier version of Java, reflection was very slow, and so serializaing large ob...

NavigableMap Misc

What is NavigableMap

Compare-In-Java

Concepts If you implement Comparable interface and override compareTo() method it must be consistent with equals() method i.e. for equal object by equals(...

Java Collections Misc

Difference between equals and deepEquals of Arrays in Java Arrays.equals() method does not compare recursively if an array contains another array on oth...

HashMap in JDK

Hashmap in JDK Some note worth points about hashmap Lookup process Step# 1: Quickly determine the bucket number in which this element may resid...

Java 8 Tips

This blog is listing key new features introduced in Java 8

Arbitrage vs Heading

What is the difference between arbitrage and hedging?

Java Enum Misc

Enum Misc