Byte beat favorite 64 algorithm questions (JS version)
April 12
The following article is from the Tuque community. The author is a Tuque
Front end technology optimization
Select high-quality technical blogs in the front-end field for you. Welcome to pay attention.
61 original content
official account
origin
At present, in the interview of large factories, the algorithm problem is almost a required item, and the real problem of LeetCode has appeared frequently in recent years. This article is for the author who got byte, Tencent and JD Offer. I personally brushed and encountered high-frequency algorithm problems in the process of preparing for the interview. The content of the article will be sorted out in modules, focusing on the real problems encountered by the author in the interview process[ 🔥] Mark.
At the same time, it's impolite to say that if you have limited preparation time and want to maximize the efficiency of algorithm problem preparation, you just need to brush the following questions according to the outline and familiarize yourself with the code, and you can deal with almost 90% of the interview algorithm questions.
One of the purposes of sorting out this content is that the author has accumulated a little when preparing for the interview, and it does help the author to pass the test in the interview algorithm. At the same time, I also hope to give you a little help in the gold, silver and four! 💪
Welfare at the end of the article:) 😈
This chapter includes the following modules:
-
High frequency algorithm series: linked list
-
[ 🔥] [true question] high frequency algorithm question series: String
-
[ 🔥] [real problem] high frequency algorithm problem series: Array Problem
-
High frequency algorithm series: binary tree
-
[ 🔥] High frequency algorithm series: sorting algorithm
-
[ 🔥] High frequency algorithm problem series: binary search
-
[ 🔥] High frequency algorithm series: dynamic programming
-
High frequency algorithm series: BFS
-
[ 🔥] High frequency algorithm series: stack
-
[ 🔥] High frequency algorithm series: DFS
-
[ 🔥] High frequency algorithm series: backtracking algorithm
Middle mark 🔥 The part of represents very high-frequency examination questions, many of which are the original questions encountered by the author. For each category, the included test questions will be listed first, and then the difficulty, knowledge points and whether it is a real interview question will be given for each test question. When each question is introduced in detail, the LeetCode link of each question will be given to help readers understand the meaning of the question and conduct the actual test. You can also watch the answers of others to better help prepare.
High frequency algorithm series: linked list
The high-frequency linked list questions encountered by the author mainly include these:
-
Find the midpoint of the linked list through the speed pointer [simple]
-
Determine the palindrome linked list problem through the subsequent traversal of the linked list [simple]
-
Reverse output of linked list [simple]
-
Merge K ascending linked lists [difficult]
-
Turn over the linked list in groups of K [difficult]
-
Circular linked list [simple]
-
Sort linked list [medium]
-
Intersecting linked list [simple]
Find the midpoint of the linked list
Problem solution
Find the midpoint of the linked list through the fast and slow pointer
/**
*
*/
function findCenter(head) {
let slower = head, faster = head;
while (faster && faster.next != null) {
slower = slower.next;
faster = faster.next.next;
}
//If ， fast ， is not equal to ， null, it indicates that it is an odd number, and slow ， moves another grid
if (faster != null) {
slower = slower.next;
}
return slower;
}
Pre order traversal judgment palindrome linked list
👉 [LeetCode through train]: 234 palindrome linked list (simple) [1]
Problem solution 1
Using the subsequent traversal of the linked list, the function call stack is used as the post order to traverse the stack to judge whether the palindrome
/**
*
*/
var isPalindrome = function(head) {
let left = head;
function traverse(right) {
if (right == null) return true;
let res = traverse(right.next);
res = res && (right.val === left.val);
left = left.next;
return res;
}
return traverse(head);
};
Problem solution 2
Find the midpoint of the linked list through the fast and slow pointers, then reverse the linked list and compare whether the two sides of the linked list are equal to judge whether it is a palindrome linked list
/**
*
*/
var isPalindrome = function(head) {
//Reverse the {slow} linked list
let right = reverse(findCenter(head));
let left = head;
//Start comparison
while (right != null) {
if (left.val !== right.val) {
return false;
}
left = left.next;
right = right.next;
}
return true;
}
function findCenter(head) {
let slower = head, faster = head;
while (faster && faster.next != null) {
slower = slower.next;
faster = faster.next.next;
}
//If ， fast ， is not equal to ， null, it indicates that it is an odd number, and slow ， moves another grid
if (faster != null) {
slower = slower.next;
}
return slower;
}
function reverse(head) {
let prev = null, cur = head, nxt = head;
while (cur != null) {
nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
Reverse linked list
👉 [LeetCode through train]: 206 reverse linked list (simple) [2]
Problem solution
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if (head == null || head.next == null) return head;
let last = reverseList(head.next);
head.next.next = head;
head.next = null;
return last;
};
Method 2
public ListNode reverseList(ListNode head) {
if(head==null){
return null;
}
ListNode pre=null,cur=head,next=head.next;
while(cur!=null){
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}Merge K ascending linked lists
👉 [LeetCode through train]: 23 merge K ascending linked lists (difficult) [3]
Problem solution
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pr=new PriorityQueue<ListNode>(new Comparator<ListNode>(){
public int compare(ListNode o1,ListNode o2){
return o1.val-o2.val;
}
});
ListNode head=new ListNode();
ListNode tail =head;
if(lists==null||lists.length==0){
return head.next;
}
for(ListNode temp:lists){
if(temp!=null){
pr.add(temp);
}
}
while(!pr.isEmpty()){
ListNode tempNode=pr.poll();
tail.next=tempNode;
tail =tail.next;
if(tempNode.next!=null)
pr.offer(tempNode.next);
}
return head.next;
}
class Solution {
public ListNode nextNewNode=null;
public ListNode reverseBetween(ListNode head, int left, int right) {
if(head==null){
return null;
}
if(right==0){
return head;
}
if(left==1){
return reverseNodesK(head,right);
}else{
head.next=reverseBetween(head.next,left-1,right-1);
return head;
}
}
ListNode reverseNodesK(ListNode head,int k){
if(head==null||head.next==null){
return head;
}
if(k==1){
this.nextNewNode=head.next;
return head;
}
ListNode next=head.next;
ListNode resultNode=reverseNodesK(next,k-1);
next.next=head;
head.next=nextNewNode;
return resultNode;
}
}Turn over the linked list in groups of K
👉 [LeetCode through train]: turn over the linked list in groups of 25 K (difficult) [4]
Problem solution
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head==null){
return null;
}
ListNode a=head,b=head;
for(int i=0;i<k;i++){
if(b==null){
return head;
}
b=b.next;
}
ListNode newNode=reverseAB(a,b);
a.next=reverseKGroup(b,k);
return newNode;
}
//Reverse the linked list between two nodes [a,b) does not contain B
private ListNode reverseAB(ListNode a,ListNode b){
ListNode pre=null,cur=a,next=a;
while(cur!=b){
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}Circular linked list
👉 [LeetCode through train]: 141 circular linked list (simple) [5]
Problem solution
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
if (head == null || head.next == null) return false;
let slower = head, faster = head;
while (faster != null && faster.next != null) {
slower = slower.next;
faster = faster.next.next;
if (slower === faster) return true;
}
return false;
};
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode faster=head,slower=head;
while(faster!=null&&faster.next!=null){
faster=faster.next.next;
slower=slower.next;
if(faster==slower){
slower=head;
while(slower!=faster){
slower=slower.next;
faster=faster.next;
}
return faster;
}
}
return null;
}
}Sort linked list
👉 [LeetCode through train]: 148 sorting linked list (medium) [6]
Problem solution
class Solution {
public ListNode sortList(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode middleNode=findMiddle(head);
ListNode nextList=middleNode.next;
middleNode.next=null;
ListNode sortedList1=sortList(head);
ListNode sortedList2=sortList(nextList);
return mergeSortedList(sortedList1,sortedList2);
}
public ListNode findMiddle(ListNode head){
ListNode faster=head,slower=head;
if(faster!=null&&faster.next!=null&&faster.next.next==null){
return faster;
}
while(faster!=null&&faster.next!=null){
faster=faster.next.next;
slower=slower.next;
}
return slower;
}
public ListNode mergeSortedList(ListNode a,ListNode b){
ListNode head=new ListNode(0);
ListNode tail=head;
while(a!=null&&b!=null){
if(a.val>b.val){
tail.next=b;
tail=tail.next;
b=b.next;
}else{
tail.next=a;
tail=tail.next;
a=a.next;
}
}
if(a==null){
tail.next=b;
}else{
tail.next=a;
}
return head.next;
}
}Intersecting linked list
👉 [LeetCode through train]: 160 intersection linked list (simple) [7]
Problem solution
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode tempA=headA,tempB=headB;
int i=0;
while(tempA!=tempB){
tempA=tempA.next;
tempB=tempB.next;
if(tempA==null){
tempA=headB;
i++;
}
if(tempB==null){
tempB=headA;
i++;
}
if(i>=3){
return null;
}
}
return tempA;
}
}[ 🔥] High frequency algorithm series: String
There are mainly the following types of high-frequency examination questions:
-
Longest palindrome substring [medium] [double pointer] [real interview question]
-
Longest common prefix [simple] [double pointer]
-
Longest substring without repeated characters [medium] [double pointer]
-
Minimum coverage substring [ difficulty ][ sliding window ][ real interview question ]
[interview question] longest palindrome substring [double pointer]
👉 [LeetCode through train]: 5 longest palindrome substring (medium) [8]
Problem solution
class Solution {
public String longestPalindrome(String s) {
int maxLength=0;
String longestPalindromeStr="";
if(s==null||s.length()==0){
return null;
}
if(s.length()==1){
return s;
}
int dp[][]=new int[s.length()][s.length()];
for(int i=0;i<s.length();i++){
dp[i][i]=1;
for(int j=0;j<i;j++){
if(i-j==1){
dp[j][i]=s.charAt(i)==s.charAt(j)?2:0;
}else{
if(dp[j+1][i-1]>0&&s.charAt(i)==s.charAt(j)){
dp[j][i]=dp[j+1][i-1]+2;
}
}
if(dp[j][i]>maxLength){
maxLength=dp[j][i];
longestPalindromeStr=s.substring(j,i+1);
}
}
}
if(maxLength==0){
return s.substring(0,1);
}
return longestPalindromeStr;
}
// public int longestPalindrome=0;
// public String longestPalindromeStr;
// public String longestPalindrome(String s) {
// if(s==null||s.length()==0){
// return null;
// }
// for(int i=0;i<s.length();i++){
// longestPalindromeDFS(s,i,i);
// longestPalindromeDFS(s,i,i+1);
// }
// return longestPalindromeStr;
// }
// public void longestPalindromeDFS(String s ,int start1,int start2){
// while(s!=null&&start1>=0&&start2<s.length()&&s.charAt(start1)==s.charAt(start2)){
// start1--;
// start2++;
// }
// if(start2-start1>longestPalindrome){
// longestPalindrome=start2-start1;
// longestPalindromeStr=s.substring(start1+1,start2);
// }
// }
}Longest common prefix [double pointer]
👉 [LeetCode through train]: 14 longest public prefix (simple) [9]
Problem solution
class Solution {
public String longestCommonPrefix(String[] strs) {
String longestCommonPrefix=strs[0];
for(int i=1;i<strs.length;i++){
longestCommonPrefix=twoCommonPrefix(longestCommonPrefix,strs[i]);
if(longestCommonPrefix==null){
break;
}
}
return longestCommonPrefix;
}
public String twoCommonPrefix(String s1,String s2){
int index=0;
while(index<s1.length()&&index<s2.length()&&s1.charAt(index)==s2.charAt(index)){
index++;
}
return s1.substring(0,index);
}
}
Longest substring without repeated characters [double pointer]
👉 [LeetCode through train]: 3 longest substring without repeated characters (medium) [10]
Problem solution
class Solution {
public int lengthOfLongestSubstring(String s) {
int left=0,right=0;
int maxLength=0;
if(s==null||"".equals(s)){
return 0;
}
if(s.length()==1){
return 1;
}
Set<Character> set=new HashSet<Character>();
for( ;right<s.length();right++){
Character curChar=s.charAt(right);
while(set.contains(curChar)){
set.remove(s.charAt(left));
left++;
}
set.add(curChar);
maxLength=Math.max(maxLength,right-left+1);
}
return maxLength;
}
}[interview question] minimum coverage substring [sliding window]
👉 [LeetCode through train]: 76 minimum coverage substring (difficult) [11]
Problem solution
class Solution {
public String minWindow(String s, String t) {
if(s==null||t==null||s.length()<t.length()){
return "";
}
Map<Character,Integer> mapT=new HashMap<Character,Integer>();
Map<Character,Integer> mapS=new HashMap<Character,Integer>();
for(int i=0;i<t.length();i++){
mapT.put(t.charAt(i),mapT.getOrDefault(t.charAt(i),0)+1);
}
int left=0,fitNum=0,right=0,minLength=Integer.MAX_VALUE;
String minStr="";
for(;right<s.length();right++){
Character curChar=s.charAt(right);
if(mapT.containsKey(curChar)){
mapS.put(curChar,mapS.getOrDefault(curChar,0)+1);
if(mapT.get(curChar).equals(mapS.get(curChar))){
fitNum++;
}
while(fitNum==mapT.keySet().size()){
if(right-left<minLength){
minLength=right-left;
minStr=s.substring(left,right+1);
}
char leftChar=s.charAt(left);
left++;
if(mapT.containsKey(leftChar)){
if(mapS.get(leftChar).equals(mapT.get(leftChar))){
fitNum--;
}
mapS.put(leftChar,mapS.get(leftChar)-1);
}
}
}
}
return minStr;
}
}[ 🔥] High frequency algorithm problem series: Array Problem
There are mainly several types of high-frequency examination questions:
-
Russian Doll envelope question [difficult] [sort + longest ascending subsequence] [real interview question]
-
Longest continuous increment sequence [simple] [double pointer]
-
Longest continuous sequence [difficult] [hash table]
-
Container holding the most water [difficult] [interview question]
-
Finding the median of two positively ordered arrays [difficult] [double pointer]
-
Delete duplicate items in ordered array [simple] [speed pointer]
-
Subarray with sum K [medium] [hash table]
-
nSum question [series] [simple] [hash table]
-
Answer [difficulties] [violence + memo optimization] [interview questions]
-
Jumping game [series] [medium] [greedy algorithm]
[interview question] Russian Doll envelope question [sort + longest ascending subsequence]
👉 [LeetCode through train]: 354 Russian Doll envelope problem (difficult) [12]
Problem solution
class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes,new Comparator<int[]>(){
public int compare(int []o1,int[]o2){
if(o1[0]!=o2[0]){
return o1[0]-o2[0];
}else{
return o2[1]-o1[1];
}
}
});
int []dp=new int [envelopes.length];
int result=0;
for(int i=0;i<envelopes.length;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(envelopes[i][1]>envelopes[j][1]){
dp[i]=Math.max(dp[i],dp[j]+1);
}
}
result=Math.max(result,dp[i]);
}
return result;
}
}Longest continuous increment sequence [speed pointer]
👉 [LeetCode through train]: 674 longest continuous increasing sequence (simple) [13]
Problem solution
class Solution {
public int findLengthOfLCIS(int[] nums) {
if(nums==null||nums.length==0){
return 0;
}
int tempResult=1;
int result=1;
for(int i=0;i<nums.length-1;i++){
if(nums[i+1]>nums[i]){
tempResult++;
}else{
tempResult=1;
}
result=Math.max(result,tempResult);
}
return result;
}
}Longest continuous sequence [hash table]
👉 [LeetCode through train]: 128 longest continuous sequence (difficult) [14]
Problem solution
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set=new HashSet<Integer>();
for(int num:nums){
set.add(num);
}
int result=0;
for(int i=0;i<nums.length;i++){
Integer curNum=nums[i];
if(!set.contains(curNum-1)){
int temp=1;
while(set.contains(curNum+1)){
temp++;
curNum+=1;
}
result=Math.max(result,temp);
}
}
return result;
}
}[interview question] container with the most water [hash table]
👉 [LeetCode through train]: 11 containers with the most water (medium) [15]
Problem solution
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let n = height.length;
let left = 0, right = n - 1;
let maxOpacity = 0;
while (left < right) {
let res = Math.min(height[left], height[right]) * (right - left);
maxOpacity = Math.max(maxOpacity, res);
if (height[left] < height[right]) left++
else right--;
}
return maxOpacity;
};
Find the median of two positively ordered arrays [double pointer]
👉 [LeetCode through train]: 4 finding the median of two positive arrays (difficult) [16]
Problem solution
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m=nums1.length,n=num2.length;
if(m>n){
int []temp=nums1;
nums1=nums2;
nums2=temp;
}
m=nums1.length,n=num2.length;
int totalLfetCount=n-(n-m+1)/2;
int nums1LeftCount=0;
int nums2LeftCount=0;
int left=0;right=m-1;
while(left<=right){
int middle=right-(right-left)/2;
int nums2Right=totalLfetCount-middle-1;
if(nums1[nums1LeftCount-1]>nums2[nums2LeftCount]){
right=nums1left-1;
}else{
left=nums1left+1;
}
}
}
}Delete duplicate items in the ordered array [speed pointer]
👉 [LeetCode through train]: 26 delete duplicates in ordered array (simple) [17]
Problem solution
class Solution {
public int removeDuplicates(int[] nums) {
int slower=0,faster=0;
while(faster<nums.length){
if(nums[slower]!=nums[faster]){
slower++;
nums[slower]=nums[faster];
}
faster++;
}
return slower+1;
}
}👉 [LeetCode through train]: the largest area of 695 Islands (medium) [18]
Problem solution
class Solution {
public int maxAreaOfIsland=0;
public int tempMaxAreaOfIsland=0;
public int maxAreaOfIsland(int[][] grid) {
int m=grid.length;
int n=grid[0].length;
boolean [][]used=new boolean[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(!used[i][j]&&grid[i][j]==1){
this.tempMaxAreaOfIsland=0;
maxAreaOfIslandDFS(grid,i,j,used);
}
}
}
return maxAreaOfIsland;
}
public void maxAreaOfIslandDFS(int[][]grid,int i,int j,boolean [][]used){
if(i<0||i>grid.length-1||j<0||j>grid[0].length-1){
return;
}
if(used[i][j]||grid[i][j]==0){
return;
}
tempMaxAreaOfIsland++;
maxAreaOfIsland=Math.max(maxAreaOfIsland,tempMaxAreaOfIsland);
used[i][j]=true;
maxAreaOfIslandDFS(grid,i+1,j,used);
maxAreaOfIslandDFS(grid,i-1,j,used);
maxAreaOfIslandDFS(grid,i,j-1,used);
maxAreaOfIslandDFS(grid,i,j+1,used);
}
}Subarray with sum K [hash table]
👉 [LeetCode through train]: 560 and K subarray (medium) [19]
Problem solution
class Solution {
public int subarraySum(int[] nums, int k) {
if(nums==null||nums.length==0){
return 0;
}
Map<Integer,Integer> mapResult=new HashMap<Integer,Integer>();
int temp=0;
int result=0;
mapResult.put(0,1);
for(int i=0;i<nums.length;i++){
temp+=nums[i];
if(mapResult.containsKey(temp-k)){
result+=mapResult.get(temp-k);
}
mapResult.put(temp,mapResult.getOrDefault(temp,0)+1);
}
return result;
}
}nSum question [hash table] [series]
-
👉 [LeetCode through train]: 1 sum of two numbers (simple) [20]
-
public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> map=new HashMap<Integer,Integer>(); for(int i=0;i<nums.length;i++){ if(map.containsKey(target-nums[i])){ return new int[]{map.get(target-nums[i]),i}; } map.put(nums[i],i); } return new int[]{-1,-1}; } -
👉 [LeetCode through train]: 167 sum of two numbers II - input ordered array (simple) [21]
-
public int[] twoSum(int[] numbers, int target) { int left=0,right=numbers.length-1; while(left<right){ int sum=numbers[left]+numbers[right]; if(sum==target){ return new int[]{left+1,right+1}; }else if(sum>target){ right--; }else{ left++; } } return new int[]{-1,-1}; } -
👉 [LeetCode through train]: 15 sum of three (medium) [22]
-
👉 [LeetCode through train]: 18 sum of four numbers (medium) [23]
class Solution {
//nsum problem, general template
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return nSumDFS(nums,target,4,0);
}
public List<List<Integer>> nSumDFS(int []nums,int target,int n,int start){
List<List<Integer>> result=new ArrayList<List<Integer>>();
if(n==2){
int left=start,right=nums.length-1;
while(left<right){
int tempLeft=left,tempRight=right;
if(nums[left]+nums[right]>target){
right--;
while(nums[tempRight]==nums[right]&&left>right){
right--;
}
}
else if(nums[left]+nums[right]<target){
left++;
while(nums[tempLeft]==nums[left]&&left<right){
left++;
}
}
else{
List<Integer> tempResult=new ArrayList<Integer>();
tempResult.add(nums[left]);
tempResult.add(nums[right]);
result.add(tempResult);
right--;left++;
while(left<right&&nums[tempRight]==nums[right]){
right--;
} while(left<right&&nums[tempLeft]==nums[left]){
left++;
}
}
}
}else{
for(int i=start;i<nums.length;i++){
if(i>start&&nums[i]==nums[i-1]){
continue;
}
int curNum=nums[i];
List<List<Integer>> tempResult=nSumDFS(nums,target-nums[i],n-1,i+1);
for(List<Integer> list:tempResult){
list.add(curNum);
result.add(list);
}
}
}
return result;
}
}
Connected to rainwater [violence + memo optimization]
👉 [LeetCode through train]: 42 rainwater (difficult) [24]
Problem solution
// 1. First of all, we need to find out what determines the amount of rain with subscript i
// It is determined by subtracting height[i] from the smaller of the maximum values on the left and right sides of I In example [0,1,0,2,1,0,1,3,2,1,2,1,1], the position value with subscript 2 is 0, and its water consumption is obtained by subtracting 0 from the smaller of the maximum value 1 on the left and the maximum value 3 on the right.
// 2. The double pointer of the solution of this problem first finds the smaller one of the currently maintained left and right maximum values. For example, if the current maximum value on the left at i is smaller than that on the right, then the influence of the maximum value on the right at i can be ignored, because the real maximum value on the right at i is definitely larger than that on the left. During continuous traversal, update max_l and max_r and return value. In example [0,1,0,2,1,0,1,3,2,1,2,1], when i=2, the value is 0 and max_l must be 1, current max_ If R is 2, even max_r is not the real maximum value of i on the right, and the influence of the maximum value on the right can also be ignored, because the real maximum value on the right must be greater than the real maximum value on the left.
public int trap(int[] height) {
if(height==null||height.length==0){
return 0;
}
int result=0,left=0,right=height.length-1,leftMax=0,rightMax=0;
while(left<right){
int heightLeft=height[left];
int heightRight=height[right];
leftMax=Math.max(leftMax, heightLeft);
rightMax=Math.max(rightMax, heightRight);
if(leftMax<rightMax){
left++;
result+=(leftMax-heightLeft);
}else{
right--;
result+=(rightMax-heightRight);
}
}
return result;
}
stack Way of
public int trap(int[] height) {
if(height==null||height.length==0){
return 0;
}
Stack<Integer> stack=new Stack<Integer>();
int result=0;
for(int i=0;i<height.length;i++){
if(stack.isEmpty()){
stack.push(i);
}else{
while(!stack.isEmpty()&&height[i]>height[stack.peek()]){
int heightLow=height[stack.pop()];
if(stack.isEmpty()){
break;
}
int deep=Math.min(height[stack.peek()],height[i])-heightLow;
result+=(deep*(i-stack.peek()-1)); //This must be the last value in the stack and cannot pop up from the previous one. For example, when 3, the width between 3 and 2 [4,2,0,3,2,5]
}
stack.push(i);
}
}
return result;
}Jumping game [greedy algorithm] [series]
-
👉 [LeetCode through train]: 55 Jumping Games (medium) [25]
-
class Solution { // In this way, we traverse each position in the array in turn and maintain the farthest reachable position in real time. For the currently traversed position xx, if it is within the range of the farthest reachable position, we can reach the position through several jumps from the starting point, so we can update the farthest reachable position with x + \textit{nums}[x]x+nums[x]. public boolean canJump(int[] nums) { if(nums==null||nums.length==0){ return true; } int rightMost=nums[0]; for(int i=1;i<nums.length;i++){ if(i<=rightMost){ rightMost=Math.max(rightMost,i+nums[i]); } } return rightMost>=nums.length-1; } //brute-force attack // public boolean canJump; // public boolean canJump(int[] nums) { // if(nums==null||nums.length==0){ // return false; // } // canJumpDFS(nums,0); // return canJump; // } // public void canJumpDFS(int[] nums,int start){ // if(canJump==true){ // return; // } // if(start>=nums.length-1){ // canJump=true; // return; // } // for(int i=start+1;i<=start+nums[start];i++){ // canJumpDFS(nums, i); // } // } } -
👉 [LeetCode through train]: 45 jumping game II (medium) [26]
Limited by space, only the code template of the first question is given here, which is also a real question.
Problem solution
class Solution {
public int jump(int[] nums) {
if(nums==null||nums.length<=1){
return 0;
}
int end=nums[0],farthest=nums[0],step=1;
for(int i=0;i<nums.length-1;i++){
if(i<=farthest){
farthest=Math.max(farthest,i+nums[i]);
}
if(i==end){
step++;
end=farthest;
}
}
return step;
}
}High frequency algorithm series: binary tree
There are mainly the following types of high-frequency examination questions:
-
Nearest common ancestor of binary tree [simple] [binary tree]
-
Search in binary search tree [simple] [binary tree]
-
Delete nodes in binary search tree [medium] [binary tree]
-
Number of nodes of complete binary tree [medium] [binary tree]
-
Zigzag sequence traversal of binary tree [medium] [binary tree]
The nearest common ancestor of a binary tree [binary tree]
👉 [LeetCode through train]: the nearest common ancestor of 236 binary tree (simple) [27]
Problem solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode result;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
lowestCommonAncestorDFS(root,p,q);
return result;
}
public boolean lowestCommonAncestorDFS(TreeNode root ,TreeNode p,TreeNode q){
if(root==null){
return false;
}
boolean inCurren=false;
if(root.val==p.val||root.val==q.val){
inCurren=true;
}
boolean inLeft=lowestCommonAncestorDFS(root.left,p,q);
boolean inRight=lowestCommonAncestorDFS(root.right,p,q);
if(inCurren&&(inLeft||inRight)){
result=root;
}
if(inLeft&&inRight){
result=root;
}
return inLeft||inRight||inCurren;
}
// public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// if(root==null){
// return null;
// }
// TreeNode left=lowestCommonAncestor(root.left,p,q);
// TreeNode right=lowestCommonAncestor(root.right,p,q);
// if((root.val==p.val||root.val==q.val)&&(left!=null||right!=null)){
// return root;
// }
// if(left!=null&&right!=null){
// return root;
// }
// if(left!=null){
// return left;
// }
// if(right!=null){
// return right;
// }
// if(root.val==p.val||root.val==q.val){
// return root;
// }
// return null;
// }
}Search in binary search tree [binary tree]
👉 [LeetCode through train]: search in 700 binary search tree (simple) [28]
Problem solution
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root==null){
return null;
}
if(root.val==val){
return root;
}
if(val>root.val){
return searchBST(root.right,val);
}else{
return searchBST(root.left,val);
}
}
}Delete node in binary search tree [binary tree]
👉 [LeetCode through train]: 450 delete nodes in binary search tree (medium) [29]
Problem solution
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null){
return null;
}
if(key>root.val){
root.right=deleteNode(root.right,key);
}else if(key<root.val){
root.left=deleteNode(root.left,key);
}else{
if(root.left==null){
return root.right;
}
if(root.right==null){
return root.left;
}
TreeNode smallestRight=getSmallestRight(root.right);
int temp=smallestRight.val;
smallestRight.val=root.val;
root.val=temp;
root.right=deleteNode(root.right,key);
}
return root;
}
//Get the right subtree minimum subtree
public TreeNode getSmallestRight(TreeNode root){
if(root==null){
return null;
}
while(root.left!=null){
root=root.left;
}
return root;
}
}Number of nodes of complete binary tree [binary tree]
👉 [LeetCode through train]: 222 nodes of complete binary tree (medium) [30]
Problem solution
class Solution {
public int countNodes(TreeNode root) {
if(root==null){
return 0;
}
int leftHeight=0;
TreeNode leftTree=root;
while(leftTree.left!=null){
leftTree=leftTree.left;
leftHeight++;
}
int rightHeight=0;
TreeNode rightTree=root;
while(rightTree.right!=null){
rightTree=rightTree.right;
rightHeight++;
}
if(leftHeight==rightHeight){
return (int)Math.pow(2,leftHeight+1)-1;
}else{
return 1+ countNodes(root.left)+countNodes(root.right);
}
}
}Zigzag sequence traversal of binary tree [binary tree]
👉 [LeetCode through train]: zigzag sequence traversal of 103 binary tree (medium) [31]
Problem solution
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
Queue <TreeNode> queue=new LinkedList<TreeNode>();
List<List<Integer>> result=new ArrayList<List<Integer>>();
int index=1;
if(root!=null){
queue.offer(root);
}
while(!queue.isEmpty()){
int size=queue.size();
Deque<Integer> deque=new LinkedList<Integer>();
for(int i=0;i<size;i++){
TreeNode curNode=queue.poll();
if(curNode.left!=null){
queue.offer(curNode.left);
}
if(curNode.right!=null){
queue.offer(curNode.right);
}
if(index%2==1){
deque.offerLast(curNode.val);
}else{
deque.offerFirst(curNode.val);
}
}
result.add(new ArrayList(deque));
index++;
}
return result;
}
}[ 🔥] High frequency algorithm series: sorting algorithm
There are mainly the following types of high-frequency examination questions:
-
Detonate the balloon with the least number of arrows [medium] [sort]
-
Merge interval [medium] [sorting algorithm + interval problem] [real interview question]
Detonate the balloon with the least number of arrows [sorting algorithm]
👉 [LeetCode through train]: 452 detonate the balloon with the minimum number of arrows (medium) [32]
Problem solution
class Solution {
public int findMinArrowShots(int[][] points) {
if(points==null){
return 0;
}
Arrays.sort(points,new Comparator<int []>(){
public int compare(int []o1,int []o2){
return Integer.compare(o1[1], o2[1]);
}
});
int startIndex=points[0][1];
int result=1;
for(int i=1;i<points.length;i++){
if(points[i][0]>startIndex){
result++;
startIndex=points[i][1];
}
}
return result;
}
}Merge interval [sorting algorithm + interval problem]
👉 [LeetCode through train]: 56 merging interval (medium) [33]
Problem solution
class Solution {
public int[][] merge(int[][] intervals) {
if(intervals==null){
return new int[][]{};
}
Arrays.sort(intervals,new Comparator<int[]>(){
public int compare(int[]a,int[]b){
return Integer.compare(a[0],b[0]);
}
});
List<int[]> result=new ArrayList<int[]>();
result.add(intervals[0]);
int maxRight=intervals[0][1];
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]> result.get(result.size()-1)[1]){
result.add(intervals[i]);
}else{
result.get(result.size()-1)[1]=Math.max(intervals[i][1], result.get(result.size()-1)[1]);
}
}
return result.toArray(new int [result.size()][]);
}
}High frequency algorithm problem series: binary search
There are mainly the following types of high-frequency examination questions:
-
Find the median of two positive arrays [difficult] [binary search]
-
Judgment subsequence [simple] [binary search]
-
Find the first and last positions of elements in the sorted array [medium] [binary search]
Find the median of two positively ordered arrays [binary search]
👉 [LeetCode through train]: 4 finding the median of two positive arrays (difficult) [34]
Problem solution
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
let m = nums1.length, n = nums2.length;
let i = 0, j = 0;
let newArr = [];
while (i < m && j < n) {
if (nums1[i] < nums2[j]) {
newArr.push(nums1[i++]);
} else {
newArr.push(nums2[j++]);
}
}
newArr = newArr.concat(i < m ? nums1.slice(i) : nums2.slice(j));
const len = newArr.length;
console.log(newArr)
if (len % 2 === 0) {
return (newArr[len / 2] + newArr[len / 2 - 1]) / 2;
} else {
return newArr[Math.floor(len / 2)];
}
};
Judgment subsequence [binary search]
👉 [LeetCode through train]: 392 judgment subsequence (simple) [35]
Problem solution
class Solution {
public boolean isSubsequence(String s, String t) {
if(s==null||t==null){
return true;
}
int m=s.length(),n=t.length(),i=0,j=0;
if(m>n){
return false;
}
while(i<m&&j<n){
if(s.charAt(i)==t.charAt(j)){
i++;
}
j++;
}
return i==m;
}
}💁 Find the first and last positions of elements in the sorted array [binary search]
👉 [LeetCode through]: 34 find the first and last positions of elements in the sorted array (medium) [36]
Problem solution
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums==null||nums.length==0){
return new int[]{-1,-1};
}
int left=binarySearch(nums,target,true);
int right=binarySearch(nums,target,false);
return new int[]{left,right};
}
public int binarySearch(int []nums,int target,boolean isFirst){
int left=0,right=nums.length-1;
while(left<=right){
int middle=right-(right-left)/2;
if(isFirst){
if(target<=nums[middle]){
right=middle-1;
}else{
left=middle+1;
}
}else{
if(target>=nums[middle]){
left=middle+1;
}else{
right=middle-1;
}
}
}
if(isFirst&&left<nums.length&&nums[left]==target){
return left;
}
if(!isFirst&&right>=0&&nums[right]==target){
return right;
}
return -1;
}
}[ 🔥] High frequency algorithm series: dynamic programming
There are mainly the following types of high-frequency examination questions:
-
Longest increasing subsequence [medium] [dynamic programming]
-
Change [medium] [dynamic planning] [real interview questions]
-
Longest common subsequence [medium] [dynamic programming] [real interview questions]
-
Edit distance [ difficulty ][ dynamic programming ]
-
Longest palindrome subsequence [medium] [dynamic programming] [real interview question]
-
Maximum subsequence and [simple] [dynamic programming] [real interview questions]
-
The best time to buy and sell stocks [series] [dynamic planning] [interview questions]
Longest increasing subsequence [dynamic programming]
👉 [LeetCode through train]: 300 longest increasing subsequence (medium) [37]
Problem solution
class Solution {
// Consider adding a num [i] after the longest ascending subsequence in]dp[0... I − 1]. Since dp[j] represents the longest ascending subsequence ending with num [j] in num [0... j], if
public int lengthOfLIS(int[] nums) {
if(nums==null||nums.length==0){
return 0;
}
int []dp=new int [nums.length];
dp[0]=1;
int result=0;
for(int i=0;i<nums.length;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i]=Math.max(dp[i],dp[j]+1);
}
}
result=Math.max(result,dp[i]);
}
return result;
}
}[interview questions] change [dynamic planning]
👉 [LeetCode through train]: 322 change (medium) [38]
Problem solution
class Solution {
public int coinChange(int[] coins, int amount) {
int dp[] =new int [amount+1];
for(int i=1;i<=amount;i++){
dp[i]=Integer.MAX_VALUE-1;
}
dp[0]=0;
for(int coin:coins){
for(int j=coin;j<=amount;j++){
dp[j]=Math.min(dp[j],dp[j-coin]+1);
}
}
return dp[amount]<(Integer.MAX_VALUE-1)?dp[amount]:-1;
}
}[interview questions] longest common subsequence [dynamic programming]
👉 [LeetCode through train]: 1143 longest common subsequence (medium) [39]
Problem solution
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
if(text1==null||text2==null){
return 0;
}
int dp[][]=new int[text1.length()+1][text2.length()+1];
for(int i=1;i<=text1.length();i++){
for(int j=1;j<=text2.length();j++){
if(text1.charAt(i-1)==text2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[text1.length()][text2.length()];
}
}Edit distance [dynamic programming]
👉 [LeetCode through train]: 72 edit distance (difficult) [40]
Problem solution
class Solution {
public int minDistance(String word1, String word2) {
int dp[][]=new int[word1.length()+1][word2.length()+1];
for(int i=0;i<=word1.length();i++){
dp[i][0]=i;
}
for(int i=0;i<=word2.length();i++){
dp[0][i]=i;
}
for(int i=1;i<=word1.length();i++){
for(int j=1;j<=word2.length();j++){
if(word1.charAt(i-1)==word2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=Math.min(
Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]
)+1;
}
}
}
return dp[word1.length()][word2.length()];
}
}[interview question] longest palindrome subsequence [dynamic programming]
👉 [LeetCode through train]: 516 longest palindrome subsequence (medium) [41]
Problem solution
class Solution {
public int longestPalindromeSubseq(String s) {
if(s==null||s.length()==0){
return 0;
}
int [][]dp=new int[s.length()+1][s.length()+1];
for(int i=0;i<s.length();i++){
dp[i][i]=1;
}
for(int i=0;i<s.length();i++){
for(int j=i-1;j>=0;j--){
if(s.charAt(j)==s.charAt(i)){
dp[j][i]=dp[j+1][i-1]+2;
}else{
dp[j][i]=Math.max(dp[j+1][i],dp[j][i-1]);
}
}
}
return dp[0][s.length()-1];
}
}[LeetCode through train]: 5 longest palindrome substring (medium) [41]
Problem solution
class Solution {
public String longestPalindrome(String s) {
int maxLength=0;
String longestPalindromeStr="";
if(s==null||s.length()==0){
return null;
}
if(s.length()==1){
return s;
}
int dp[][]=new int[s.length()][s.length()];
for(int i=0;i<s.length();i++){
dp[i][i]=1;
for(int j=0;j<i;j++){
if(i-j==1){
dp[j][i]=s.charAt(i)==s.charAt(j)?2:0;
}else{
if(dp[j+1][i-1]>0&&s.charAt(i)==s.charAt(j)){
dp[j][i]=dp[j+1][i-1]+2;
}
}
if(dp[j][i]>maxLength){
maxLength=dp[j][i];
longestPalindromeStr=s.substring(j,i+1);
}
}
}
if(maxLength==0){
return s.substring(0,1);
}
return longestPalindromeStr;
}
// public int longestPalindrome=0;
// public String longestPalindromeStr;
// public String longestPalindrome(String s) {
// if(s==null||s.length()==0){
// return null;
// }
// for(int i=0;i<s.length();i++){
// longestPalindromeDFS(s,i,i);
// longestPalindromeDFS(s,i,i+1);
// }
// return longestPalindromeStr;
// }
// public void longestPalindromeDFS(String s ,int start1,int start2){
// while(s!=null&&start1>=0&&start2<s.length()&&s.charAt(start1)==s.charAt(start2)){
// start1--;
// start2++;
// }
// if(start2-start1>longestPalindrome){
// longestPalindrome=start2-start1;
// longestPalindromeStr=s.substring(start1+1,start2);
// }
// }
}[interview questions] 💁 Maximum subsequence sum [dynamic programming]
👉 [LeetCode through train]: 53 maximum subsequence sum (simple) [42]
Problem solution
class Solution {
public int maxSubArray(int[] nums) {
int dp[] =new int[nums.length]; //The state cannot be defined as the first i continuous subarrays. i and i-1 may not be continuous during state transition. It is positioned as a continuous subarray ending with i
if(nums==null||nums.length==0){
return 0;
}
int maxSubArray=nums[0];
dp[0]=nums[0];
for(int i=1;i<nums.length;i++){
dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);
maxSubArray=Math.max(maxSubArray,dp[i]);
}
return maxSubArray;
}
// public int maxSubArray(int[] nums) {
// if(nums==null||nums.length==0){
// return 0;
// }
// int tempSum=0,result=Integer.MIN_VALUE;
// for(int num:nums){
// tempSum+=num;
// If (tempsum > 0) {/ / if the sum is greater than 0, it will gain the new array behind. You can continue to add
// result=Math.max(result,tempSum);
// }else{
// result=Math.max(result,tempSum);
// tempSum=0;
// }
// }
// return result;
// }
}[interview questions] 💁 The best time to buy and sell stocks [dynamic programming]
-
👉 [LeetCode through train]: 121 the best time to buy and sell stocks (simple) [43] [true interview question]
-
class Solution { public int maxProfit(int[] prices) { int minValue=Integer.MAX_VALUE,result=0; if(prices==null||prices.length==1){ return 0; } for(int price :prices){ minValue=Math.min(minValue,price); result=Math.max(result,price-minValue); } return result; } } -
👉 [LeetCode through train]: 122 the best time to buy and sell stocks II (simple) [44]
-
class Solution { // //Greedy algorithm, draw a rising and falling chart of the trend. The difference between the highest point and the lowest point in each rising stage is equivalent to the addition of the difference between each point in the middle // public int maxProfit(int[] prices) { // if(prices==null||prices.length<2){ // return 0; // } // int result=0; // for(int i=1;i<prices.length;i++){ // if(prices[i]>prices[i-1]){ // result+=(prices[i]-prices[i-1]); // } // } // return result; // } public int maxProfit(int[] prices) { if(prices==null||prices.length<2){ return 0; } int [][]dp=new int[prices.length][2]; //There are two situations: currently holding shares and not holding shares dp[0][0]=0; dp[0][1]=-prices[0]; for(int i=1;i<prices.length;i++){ dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]); //The maximum return not held at present is not held in the previous step. It is held in the previous step and sold at the current stock price dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]); //The maximum return of current holding is held in the previous step or not held in the previous step. Buy now } return Math.max(dp[prices.length-1][0], dp[prices.length-1][1]); } } -
👉 [LeetCode through train]: 123 the best time to buy and sell stocks III (difficulty) [45]
-
👉 [LeetCode through train]: 188 the best time to buy and sell stocks IV (difficulty) [46]
-
👉 [LeetCode through train]: 309 is the best time to buy and sell stocks, including freezing period (medium) [47]
-
class Solution { public int maxProfit(int[] prices) { if(prices==null||prices.length<1){ return 0; } int n=prices.length; int dp [][]=new int [n][3]; // [i][0] indicates that it is frozen and not held after today, [i][1] indicates that it is held after today, [i][2] indicates that it is in the non frozen and can be bought period dp [0][1]=-prices[0]; for(int i=1;i<prices.length;i++){ //If you are in the lock-in period after today, you must be in the buy period after yesterday and sell today dp[i][0]=dp[i-1][1]+prices[i]; //If you are in the holding period after today, you can hold it yesterday, or you can buy it yesterday and buy it today dp[i][1]=Math.max(dp[i-1][1],dp[i-1][2]-prices[i]); //If you are in the buying period after today, you may be in the locking period after yesterday, or you may be in the buying period after yesterday dp[i][2]=Math.max(dp[i-1][2],dp[i-1][0]); } return Math.max(Math.max(dp[prices.length-1][0],dp[prices.length-1][1]),dp[prices.length-1][2]); } } -
👉 [LeetCode through train]: 714 the best time to buy and sell stocks, including handling fee (medium) [48]
Limited by space, only the code template of the first question is given here. It is also a real question that is often tested. The author encountered it during the interview.
Problem solution
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let dp = [];
for (let i = -1; i < prices.length; i++) {
dp[i] = []
for (let j = 0; j <= 1; j++) {
dp[i][j] = [];
dp[i][j][0] = 0;
dp[i][j][1] = 0;
if (i === -1) {
dp[i][j][1] = -Infinity;
}
if (j === 0) {
dp[i][j][1] = -Infinity;
}
if (j === -1) {
dp[i][j][1] = -Infinity;
}
}
}
for (let i = 0; i < prices.length; i++) {
for (let j = 1; j <= 1; j++) {
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
}
}
return dp[prices.length - 1][1][0];
};
High frequency algorithm series: BFS
There are mainly the following types of high-frequency examination questions:
-
Open turntable lock [medium] [BFS]
-
Minimum depth of binary tree [simple] [BFS]
Open turntable lock [ BFS ]
👉 [LeetCode through train]: 752 open the turntable lock (medium) [49]
Problem solution
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> lockSet=new HashSet<String>();
Set<String> visited=new HashSet<String>();
for(String curLock:deadends){
lockSet.add(curLock);
}
Deque<String> queue=new LinkedList<String>();
queue.offer("0000");
// visited.add("0000");
int minLength=0;
while(!queue.isEmpty()){
int length=queue.size();
for(int j=0;j<length;j++){
String curstring=queue.poll();
if(lockSet.contains(curstring)||visited.contains(curstring)){
continue;
}
if(target.equals(curstring)){
return minLength;
}
visited.add(curstring);
for(int i=0;i<4;i++){
String plusString=plusOne(curstring,i);
queue.offer(plusString);
String minusString=minusOne(curstring,i);
queue.offer(minusString);
}
}
minLength++;
}
return -1;
}
public String plusOne(String s,int index){
char[] charArray=s.toCharArray();
if(charArray[index]=='9'){
charArray[index]='0';
}else{
charArray[index]+=1;
}
return new String(charArray);
}
public String minusOne(String s,int index){
char[] charArray=s.toCharArray();
if(charArray[index]=='0'){
charArray[index]='9';
}else{
charArray[index]-=1;
}
return new String(charArray);
}
}Minimum depth of binary tree [BFS]
👉 [LeetCode through train]: 111 minimum depth of binary tree (simple) [50]
Problem solution
class Solution {
public int minDepth(TreeNode root) {
if(root==null){
return 0;
}
Deque<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
int minDeep=1;
while(!queue.isEmpty()){
int length=queue.size();
for(int i=0;i<length;i++){
TreeNode curNode=queue.poll();
if(curNode.left==null&&curNode.right==null){
return minDeep;
}
if(curNode.left!=null){
queue.offer(curNode.left);
}
if(curNode.right!=null){
queue.offer(curNode.right);
}
}
minDeep++;
}
return minDeep;
}
}[ 🔥] High frequency algorithm series: stack
There are mainly the following types of high-frequency examination questions:
-
Minimum stack [simple] [stack]
-
Valid brackets [medium] [stack] [interview question]
-
Simplified path [medium] [stack]
-
Next larger element [series] [stack]
Minimum stack [stack]
👉 [LeetCode through train]: 155 minimum stack (simple) [51]
Problem solution
class MinStack {
Stack <Integer> stack;
Stack <Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
stack=new Stack<Integer>();
minStack=new Stack<Integer>();
}
public void push(int val) {
stack.push(val);
minStack.push(minStack.isEmpty()?val:Math.min(minStack.peek(),val));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/[series] next larger element [stack]
-
👉 [LeetCode through train]: 496 next bigger element I (simple) [52]
-
👉 [LeetCode through train]: 503 next bigger Element II (medium) [53]
Limited by space, only the code template of the first question is given here
Problem solution
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
Stack<Integer> stack=new Stack<Integer>();
int []result=new int[nums1.length];
for(int i=nums2.length-1;i>=0;i--){
while(!stack.isEmpty()&&nums2[i]>stack.peek()){
stack.pop();
}
int iResult=stack.isEmpty()?-1:stack.peek();
stack.push(nums2[i]);
map.put(nums2[i],iResult);
}
for(int i=0;i<nums1.length;i++){
result[i]=map.get(nums1[i]);
}
return result;
}
}
The next larger element 2 lists the array twice
class Solution {
public int[] nextGreaterElements(int[] nums) {
Stack<Integer> stack=new Stack<Integer>();
int n=nums.length;
int [] result=new int[n];
for(int i=2*n-1;i>=0;i--){
int index=i%n;
while(!stack.isEmpty()&&stack.peek()<=nums[index]){
stack.pop();
}
int curValue=stack.isEmpty()?-1:stack.peek();
stack.push(nums[index]);
result[index]=curValue;
}
return result;
}
}[interview question] valid brackets [stack]
👉 [LeetCode through train]: 20 valid brackets (medium) [54]
Problem solution
class Solution {
public static boolean isValid(String s) {
if(s==null||s.length()==0){
return true;
}
while(s.contains("()")||s.contains("{}")||s.contains("[]")){
s=s.replace("()", "");
s=s.replace("{}", "");
s=s.replace("[]", "");
}
return s.length()>0?false:true;
}
// public static boolean isValid(String s) {
// if(s==null||s.length()==0){
// return true;
// }
// Stack<Character> stack=new Stack<Character>();
// for(int i=0;i<s.length();i++){
// char curChar=s.charAt(i);
// if(curChar=='{'||curChar=='['||curChar=='('){
// stack.push(curChar);
// }else{
// if(stack.isEmpty()){
// return false;
// }
// Character leftChar=stack.pop();
// if(leftChar!=null&&leftChar=='{'&&curChar=='}'){
// continue;
// }else if(leftChar!=null&&leftChar=='['&&curChar==']'){
// continue;
// }else if(leftChar!=null&&leftChar=='('&&curChar==')'){
// continue;
// }else{
// return false;
// }
// }
// }
// return stack.size()>0?false:true;
// }
}Simplified path [stack]
👉 [LeetCode through train]: 71 simplified path (medium) [55]
Problem solution
class Solution {
public String simplifyPath(String path) {
if(path==null||"".equals(path)){
return "/";
}
String [] pathArray=path.split("/");
Stack<String> stack=new Stack<String>();
for(int i=0;i<pathArray.length;i++){
String curString =pathArray[i];
if(".".equals(curString)||"".equals(curString)){
continue;
}else if("..".equals(curString)&&!stack.isEmpty()){
stack.pop();
} else if("..".equals(curString)&&stack.isEmpty()){
// return "/";
}else{
stack.push(curString);
}
}
StringBuilder sb=new StringBuilder();
for(int i=0;i<stack.size();i++){
sb.append("/");
sb.append(stack.get(i));
}
return sb.length()==0?"/":sb.toString();
}
}[ 🔥] High frequency algorithm series: DFS
There are mainly the following types of high-frequency examination questions:
-
Maximum area of the island [medium] [DFS]
-
Same tree [simple] [DFS]
Maximum area of the island [DFS]
👉 [LeetCode through train]: the largest area of 695 Islands (medium) [56]
Problem solution
class Solution {
public int maxAreaOfIsland=0;
public int tempMaxAreaOfIsland=0;
public int maxAreaOfIsland(int[][] grid) {
int m=grid.length;
int n=grid[0].length;
boolean [][]used=new boolean[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(!used[i][j]&&grid[i][j]==1){
this.tempMaxAreaOfIsland=0;
maxAreaOfIslandDFS(grid,i,j,used);
}
}
}
return maxAreaOfIsland;
}
public void maxAreaOfIslandDFS(int[][]grid,int i,int j,boolean [][]used){
if(i<0||i>grid.length-1||j<0||j>grid[0].length-1){
return;
}
if(used[i][j]||grid[i][j]==0){
return;
}
tempMaxAreaOfIsland++;
maxAreaOfIsland=Math.max(maxAreaOfIsland,tempMaxAreaOfIsland);
used[i][j]=true;
maxAreaOfIslandDFS(grid,i+1,j,used);
maxAreaOfIslandDFS(grid,i-1,j,used);
maxAreaOfIslandDFS(grid,i,j-1,used);
maxAreaOfIslandDFS(grid,i,j+1,used);
}
}Same tree [DFS]
👉 [LeetCode through train]: 100 same tree (simple) [57]
Problem solution
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if((p!=null&&q!=null)&&(p.val==q.val)){
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}else if(p==null&&q==null){
return true;
}else{
return false;
}
}
}[ 🔥] High frequency algorithm series: backtracking algorithm
There are mainly the following types of high-frequency examination questions:
-
Queen N [difficulty] [backtracking algorithm] [real interview question]
-
Full Permutation [medium] [backtracking algorithm]
-
Bracket generation [medium] [backtracking algorithm]
-
Restore IP address [medium] [backtracking algorithm]
-
Subset [simple] [backtracking algorithm]
[interview question] queen N [backtracking algorithm]
👉 [LeetCode through train]: 51 N Queen (difficult) [58]
Problem solution
class Solution {
List<List<String>> result=new ArrayList<List<String>>();
public List<List<String>> solveNQueens(int n) {
char [][] queenChar=new char[n][n];
for(int i=0;i<n;i++){
Arrays.fill(queenChar[i],'.');
}
solveNQueensDFS(queenChar,0);
return result;
}
public void solveNQueensDFS(char[][]queenChar,int colIndex){
if(colIndex>queenChar.length){
return; //Theoretically, it is impossible to > n. if all rowindexes are not satisfied, there will be no depth traversal
}
if(colIndex==queenChar.length){
result.add(arrayToList(queenChar));
}
//Go through all the columns in the row
for(int i=0;i<queenChar.length;i++){
if(isLegal(queenChar,colIndex,i)){
queenChar[colIndex][i]='Q';
solveNQueensDFS(queenChar,colIndex+1);
queenChar[colIndex][i]='.';
}else{
continue;
}
}
}
public boolean isLegal(char[][]queenChar,int colIndex,int rowIndex){
//upper
for(int i=colIndex-1;i>=0;i--){
if(queenChar[i][rowIndex]=='Q'){
return false;
}
}
//top left corner
for(int i=colIndex-1,j=rowIndex-1;i>=0&&j>=0;i--,j--){
if(queenChar[i][j]=='Q'){
return false;
}
}
//Upper right corner
for(int i=colIndex-1,j=rowIndex+1;i>=0&&j<queenChar.length;i--,j++){
if(queenChar[i][j]=='Q'){
return false;
}
}
return true;
}
public List<String> arrayToList(char [][]queenChar){
List<String> result=new ArrayList<String>();
for(char [] tempChar:queenChar){
String s=new String(tempChar);
result.add(s);
}
return result;
}
}Full Permutation [backtracking algorithm]
👉 [LeetCode through train]: 46 full arrangement (medium) [59]
Problem solution
class Solution {
List<List<Integer>> result=new ArrayList<List<Integer>>();
public List<List<Integer>> permute(int[] nums) {
if(nums==null||nums.length==0){
return new ArrayList();
}
permuteDFS(nums,new ArrayList<Integer>(),new boolean [nums.length]);
return result;
}
public void permuteDFS(int []nums,List<Integer> tempList,boolean[]used){
if(tempList.size()==nums.length){
result.add(new ArrayList(tempList));
return;
}
for(int i=0;i<nums.length;i++){
if(used[i]){
continue;
}
tempList.add(nums[i]);
used[i]=true;
permuteDFS(nums,tempList,used);
used[i]=false;
tempList.remove(tempList.size()-1);
}
}
}Bracket generation [backtracking algorithm]
👉 [LeetCode through train]: 22 bracket generation (medium) [60]
Problem solution
class Solution {
List<String> list = new ArrayList<>();
public List<String> generateParenthesis(int n) {
if(n==0){
return new ArrayList();
}
generateParenthesisDFS(n,0,0,"");
return list;
}
public void generateParenthesisDFS(int n,int l,int right,String tempStr){
if(l==right&&l==n){
list.add(tempStr);
}
if(l<n){
generateParenthesisDFS(n,l+1,right,tempStr+"(");
}
if(right<l){
generateParenthesisDFS(n,l,right+1,tempStr+")");
}
}
}Restore IP address [backtracking algorithm]
👉 [LeetCode through train]: 93 restore IP address (medium) [61]
Problem solution
class Solution {
List<String> result=new ArrayList<String>();
public List<String> restoreIpAddresses(String s) {
if(s==null||s.length()==0){
return new ArrayList();
}
restoreIpAddressesDFS(0,s,4,"");
return result;
}
public void restoreIpAddressesDFS(int beginIndex,String s,int stillNum,String tempStr){
if(stillNum==0&&beginIndex==s.length()){
result.add(tempStr);
}
if(stillNum==0){
return;
}
if(beginIndex==s.length()){
return;
}
char firstChar=s.charAt(beginIndex);
if(firstChar=='0'){
int endIndex=beginIndex+1;
if(!"".equals(tempStr)){
tempStr+=".";
}
tempStr+=firstChar;
restoreIpAddressesDFS(endIndex,s,stillNum-1,tempStr);
}else{
for(int i=1;i<4;i++){
int endIndex=beginIndex+i;
if(endIndex>s.length()){
return;
}
int curNum=Integer.valueOf(s.substring(beginIndex,endIndex));
if(curNum<=255){
if(!"".equals(tempStr)){
tempStr+=".";
}
restoreIpAddressesDFS(endIndex,s,stillNum-1,tempStr+curNum);
if(!"".equals(tempStr)&&tempStr.charAt(tempStr.length()-1)=='.'){
tempStr=tempStr.substring(0,tempStr.length()-1);
}
}
}
}
}
}Subset [backtracking algorithm]
👉 [LeetCode through train]: 78 subsets (medium) [62]
Problem solution
class Solution {
List<List<Integer>> result=new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
if(nums==null||nums.length==0){
return new ArrayList<List<Integer>>();
}
subsetsDFS(nums,0,new ArrayList<Integer>());
return result;
}
public void subsetsDFS(int []nums,int start,List<Integer> tempList){
result.add(new ArrayList(tempList));
for(int i=start;i<nums.length;i++){
int curNum=nums[i];
tempList.add(curNum);
subsetsDFS(nums,i+1,tempList);
tempList.remove(tempList.size()-1);
}
}
}Welfare at the end of the article
Recommend a very helpful website for brushing algorithm problems, labuladong's algorithm sketch [63], identify high-frequency problems through routine, and go directly to big factories; This book has been published, and the corresponding Github warehouse [64] also has 86.2K Star, and the author is still updated frequently, which is very worth learning!
❤️ thank you
Previous Jingwen
-
Byte beat favorite front-end interview question: JavaScript foundation [65] 2696 👍
-
Byte beat favorite front-end interview question: CSS foundation [66] 687 👍
-
Byte beat favorite front-end interview question: Fundamentals of computer network [67] 761 👍
Welcome to the official account: Tuque community . If you want to learn a technology from scratch in a practical way, or want to do a relatively complete project to prepare for the interview, I believe the content of "Tuque community" can help you and become the compass on your growth path when you are new to the front end.
Original is not easy
It's not easy to be original if you like. Give me some encouragement ❤️ Don't forget to share, like and watch the third company ~.
reference material
[1]
[LeetCode through train]: 234 palindrome linked list (simple): https://leetcode-cn.com/problems/palindrome-linked-list/
[2]
[LeetCode through train]: 206 reverse linked list (simple): https://leetcode-cn.com/problems/reverse-linked-list/
[3]
[LeetCode through train]: 23 merge K ascending linked lists (difficult): https://leetcode-cn.com/problems/merge-k-sorted-lists/
[4]
[LeetCode through train]: turn over the linked list in groups of 25 K (difficult): https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
[5]
[LeetCode through train]: 141 circular linked list (simple): https://leetcode-cn.com/problems/linked-list-cycle/
[6]
[LeetCode through train]: 148 sorting linked list (medium): https://leetcode-cn.com/problems/sort-list/
[7]
[LeetCode through train]: 160 intersection linked list (simple): https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
[8]
[LeetCode through train]: 5 longest palindrome substring (medium): https://leetcode-cn.com/problems/longest-palindromic-substring/
[9]
[LeetCode through train]: 14 longest public prefix (simple): https://leetcode-cn.com/problems/longest-common-prefix/
[10]
[LeetCode through train]: 3 longest substring without repeated characters (medium): https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[11]
[LeetCode through train]: 76 minimum coverage substring (difficult): https://leetcode-cn.com/problems/minimum-window-substring/
[12]
[LeetCode through train]: 354 Russian Doll envelope problem (difficult): https://leetcode-cn.com/problems/russian-doll-envelopes/
[13]
[LeetCode through train]: 674 longest continuous increasing sequence (simple): https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
[14]
[LeetCode through train]: 128 longest continuous sequence (difficult): https://leetcode-cn.com/problems/longest-consecutive-sequence/
[15]
[LeetCode through train]: 11 containers with the most water (medium): https://leetcode-cn.com/problems/container-with-most-water/
[16]
[LeetCode through train]: 4 find the median of two positive arrays (difficult): https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[17]
[LeetCode through train]: 26 delete duplicates in the ordered array (simple): https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
[18]
[LeetCode through train]: the largest area of 695 Islands (medium): https://leetcode-cn.com/problems/max-area-of-island/
[19]
[LeetCode through train]: subarray with 560 and K (medium): https://leetcode-cn.com/problems/subarray-sum-equals-k/
[20]
[LeetCode through train]: 1 sum of two numbers (simple): https://leetcode-cn.com/problems/two-sum/
[21]
[LeetCode through train]: 167 sum of two numbers II - input ordered array (simple): https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
[22]
[LeetCode through train]: 15 sum of three (medium): https://leetcode-cn.com/problems/3sum/
[23]
[LeetCode through train]: 18 sum of four numbers (medium): https://leetcode-cn.com/problems/4sum/
[24]
[LeetCode through train]: 42 rainwater connection (difficult): https://leetcode-cn.com/problems/trapping-rain-water/
[25]
[LeetCode through train]: 55 jumping game (medium): https://leetcode-cn.com/problems/jump-game/
[26]
[LeetCode through train]: 45 jumping game II (medium): https://leetcode-cn.com/problems/jump-game-ii/
[27]
[LeetCode through train]: the nearest common ancestor of 236 binary tree (simple): https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
[28]
[LeetCode through train]: search in 700 binary search tree (simple): https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
[29]
[LeetCode through train]: 450 delete nodes in binary search tree (medium): https://leetcode-cn.com/problems/delete-node-in-a-bst/
[30]
[LeetCode through train]: 222 number of nodes of complete binary tree (medium): https://leetcode-cn.com/problems/count-complete-tree-nodes/
[31]
[LeetCode through train]: zigzag sequence traversal of 103 binary tree (medium): https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
[32]
[LeetCode through train]: 452 detonate the balloon with the minimum number of arrows (medium): https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/
[33]
[LeetCode through train]: 56 consolidation interval (medium): https://leetcode-cn.com/problems/merge-intervals/
[34]
[LeetCode through train]: 4 find the median of two positive arrays (difficult): https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[35]
[LeetCode through train]: 392 judgment subsequence (simple): https://leetcode-cn.com/problems/is-subsequence/
[36]
[LeetCode through]: 34 find the first and last positions of elements in the sorting array (medium): https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[37]
[LeetCode through train]: 300 longest increasing subsequence (medium): https://leetcode-cn.com/problems/longest-increasing-subsequence/
[38]
[LeetCode through train]: 322 change (medium): https://leetcode-cn.com/problems/coin-change/
[39]
[LeetCode through train]: 1143 longest common subsequence (medium): https://leetcode-cn.com/problems/longest-common-subsequence/
[40]
[LeetCode through train]: 72 edit distance (difficult): https://leetcode-cn.com/problems/edit-distance/
[41]
[LeetCode through train]: 516 longest palindrome subsequence (medium): https://leetcode-cn.com/problems/longest-palindromic-subsequence/
[42]
[LeetCode through train]: 53 maximum subsequence sum (simple): https://leetcode-cn.com/problems/maximum-subarray/
[43]
[LeetCode through train]: 121 the best time to buy and sell stocks (simple): https://leetcode-cn.com/problems/container-with-most-water/
[44]
[LeetCode through train]: 122 the best time to buy and sell stocks II (simple): https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
[45]
[LeetCode through train]: 123 the best time to buy and sell stocks III (difficulty): https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
[46]
[LeetCode through train]: 188 the best time to buy and sell stocks IV (difficulty): https://leetcode-cn.com/problems/container-with-most-water/
[47]
[LeetCode through train]: the best time to buy and sell stocks in 309, including freezing period (medium): https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[48]
[LeetCode through train]: 714 the best time to buy and sell stocks, including handling fee (medium): https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
[49]
[LeetCode through train]: 752 open the turntable lock (medium): https://leetcode-cn.com/problems/open-the-lock/
[50]
[LeetCode through train]: 111 minimum depth of binary tree (simple): https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
[51]
[LeetCode through train]: 155 minimum stack (simple): https://leetcode-cn.com/problems/min-stack/submissions/
[52]
[LeetCode through train]: 496 next bigger element I (simple): https://leetcode-cn.com/problems/next-greater-element-i/
[53]
[LeetCode through train]: 503 next bigger Element II (medium): https://leetcode-cn.com/problems/next-greater-element-ii/
[54]
[LeetCode through train]: 20 valid brackets (medium): https://leetcode-cn.com/problems/valid-parentheses/
[55]
[LeetCode through train]: 71 simplified path (medium): https://leetcode-cn.com/problems/simplify-path/
[56]
[LeetCode through train]: the largest area of 695 Islands (medium): https://leetcode-cn.com/problems/max-area-of-island/
[57]
[LeetCode through train]: 100 same tree (simple): https://leetcode-cn.com/problems/same-tree/
[58]
[LeetCode through train]: 51 N Queen (difficult): https://leetcode-cn.com/problems/n-queens/
[59]
[LeetCode through train]: 46 full arrangement (medium): https://leetcode-cn.com/problems/permutations/
[60]
[LeetCode through train]: 22 bracket generation (medium): https://leetcode-cn.com/problems/generate-parentheses/
[61]
[LeetCode through train]: 93 restore IP address (medium): https://leetcode-cn.com/problems/restore-ip-addresses/
[62]
[LeetCode through train]: 78 subsets (medium): https://leetcode-cn.com/problems/subsets/
[63]
Labuladong's algorithm sketch: https://www.yuque.com/tuture/interview/labuladong : https
[64]
Github warehouse: https://github.com/labuladong/fucking-algorithm
[65]
Favorite front-end interview question: JavaScript Foundation: https://juejin.cn/post/6934500357091360781
[66]
Favorite front-end interview question: CSS Foundation: https://juejin.cn/post/6936913689115099143
[67]
Favorite front-end interview question: Fundamentals of computer network: https://juejin.cn/post/6939691851746279437
Front end technology optimization
Select high-quality technical blogs in the front-end field for you. Welcome to pay attention.
61 original content
official account