“Live up to the time, the creation of non-stop, this article is participating in 2021 year-end summary essay competition”
A week later, we came to the final. We played fairly well in the early stage, with no head-to-head battles, and the economy was slightly ahead of the opponents. In the 42nd minute, I was squatted by the opponents for looking in the grass in my own field, which ended the match directly. In the evening, the school post bar was frying again, and there was a lot of talk about my wave of orangutan operation and senseless chicken dishes… Although I know it was my mistake that led to the loss of the game, but the taste of being sprayed is really not good…. At about ten o ‘clock, I received a message from her: Although I lost the game, you played very well. Everyone made mistakes… Instantly filled my heart with warmth. We have been out of touch for several months. She said that she didn’t want to make us strangers because of the last confession. She hoped that we could continue to be friends. I quickly pidianpidian agreed, this is I always want to say but dare not say, since the last confession was rejected, I have been avoiding her, I miss her, but I can not face her, always feel a little embarrassed (you failed to confess her will be how you feel? . Our relationship suddenly went back to where it was before MY confession, which gave me the illusion that MAYBE I had a chance. We talked so much that night that losing the game and getting yelled at didn’t matter at all. The ash of the small motorcycle was wiped by me ber bright, once wanted to sell but not willing to give up, after all, it is full of memories, although not how beautiful. I don’t bring her breakfast like I used to, maybe once or twice a week. I think it would be more relaxed and natural. Time quietly elapses, turned in the blink of an eye to two years, two years began to sign up for some optional courses, I wanted to sign up for the same with her, but what she chooses is ballet…. Then I chose to travel, I really want to go out and see mountains and rivers of the motherland, conditions do not allow ah, elective course for the first time, I early came to the classroom, sat in the middle position, the classmates and teachers are also coming to, when the teacher is preparing for a class, a dress fashionable girl slowly walked into the classroom, it attracted the attention of everyone, She’s about 5 ‘6, so she’s kind of sweet and cute. She looked down the classroom, walked towards me here and sat down….
Dynamic programming: The feeling is to find patterns
Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.
A subarray is a contiguous part of an array
Example 1:
Enter nums = [-2.1, -3.4, -1.2.1, -5.4] output:6Continuous subarrays [4, -1.2.1] and maximum, for6 。
Copy the codeAnswer key:
var maxArr = function(nums) {
let maxVal = nums[0];
let sum = 0;
for(let num of nums) {
if(sum + num > num){
sum = sum + num;
} else {
sum = num;
}
maxVal = Math.max(maxVal, sum);
};
return maxVal;
};
Copy the codeSum =num=-2 sum=num=-2 maxVal=-2 Sum =-2 num=1 maxVal=1 Sum =sum+num=-2 maxVal=1 Sum = 2 num=4 sum=num=4 maxVal=4 Sum = 2 num=4 maxVal=4 maxVal=4
It has to be said that dynamic programming is really difficult, the above example belongs to simple….. in force buckle
Greedy algorithms: Always make the best choice for the moment when solving a problem
The container that holds the most water
Give you n non-negative integers A1, A2… Each number represents a point in the coordinates (I, ai). Draw n vertical lines in the coordinates, and the two endpoints of vertical line I are (I, AI) and (I, 0). Find the two lines that together with the X-axis will hold the most water.
Note: You cannot tilt the container.
Input:1.8.6.2.5.4.8.3.7] output:49Explanation: The vertical lines represent the input array [1.8.6.2.5.4.8.3.7]. In this case, the maximum amount of water the container can hold (shown in blue) is49.Copy the codeAnswer key:
var maxArea = function(height) {
let i = 0, j = height.length-1;
let square, max = 0;
while(j-i >= 1) {if(height[i]>height[j]){
square = height[j] * (j-i);
j--;
}else{
square = height[i] * (j-i);
i++;
}
max = Math.max(square,max);
}
return max;
};
Copy the codeUsing greedy + two-pointer analysis:
- We use two Pointers in the array, one at the beginning and one at the end.
- In each step, we move the pointer to the shorter segment toward the longer segment;
- Also, we record the maximum area of all steps: maxSquare.
- M and n represent the front and back Pointers, H[m] represents the height at position M, and N is the length of input data. S(m,n) = min(H[m],H[n]) * (n-m) is the area of (m,n) pairs. H [m,n] represents the tree height of the current position, h = n-m
Divide and conquer: divide and conquer, solve the sub-problem first, and then combine the solutions of the sub-problem to find the original problem.
Merge sort, for example
Answer key:
const mergeSort = function(arr) {
const len = arr.length;
if (len > 1) {
// Split in half
const middle = Math.floor(len / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle, len);
let i = 0;
let j = 0;
let k = 0;
// Sort left and right separately
mergeSort(left);
mergeSort(right);
while(i < left.length && j < right.length) {
if (left[i] < right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
// Check the remaining items
while(i < left.length) {
arr[k] = left[i];
i++;
k++;
}
while(j < right.length) { arr[k] = right[j]; j++; k++; }}return arr;
}
Copy the codeBacktracking: When it is found that the solution condition is not satisfied, it “backtracking” back to try another path
[Alphabetic combination of telephone numbers]
Given a string containing only the numbers 2-9, return all the letter combinations it can represent. The answers can be returned in any order.
The mapping of numbers to letters is given as follows (same as a telephone key). Note that 1 does not correspond to any letter.
Enter: digits ="23"Output:"ad"."ae"."af"."bd"."be"."bf"."cd"."ce"."cf"]
Copy the codeAnswer key:
const letterCombinations = (digits) = > {
if (digits.length == 0) return [];
const res = [];
const map = { '2': 'abc'.'3': 'def'.'4': 'ghi'.'5': 'jkl'.'6': 'mno'.'7': 'pqrs'.'8': 'tuv'.'9': 'wxyz' };
// DFS: the string currently constructed is curStr, now "translate" to the i-th digit, and continue "translate" from there.
const dfs = (curStr, i) = > { // curStr is the current string, and I is the scanned pointer
if (i > digits.length - 1) { // Pointer out of bounds, recursive exit
res.push(curStr); // Push the solution into res
return; // End the current recursive branch
}
const letters = map[digits[i]]; // The letter corresponding to the current number
for (const letter of letters) { // A letter is a selection, corresponding to a recursive branch
dfs(curStr + letter, i + 1); // Select letter to generate a new string, move I pointer right to continue translation (recursive)}}; dfs(' '.0); // A recursive entry, starting with string '', translated from subscript 0
return res;
};
Copy the codeAnalysis: Backtracking is essentially a brute force search, using DFS (depth-first search).
Thinking about
[3,5,1,9,2,0,8,4,7,6] 0-9 what is the lowest time complexity for sorting 10 numbers?
The algorithm sounds fancy, and it’s really hard, and the entry-level requirements are actually fine.