Summer vacation is here… Speaking as an algorithmic douche bag
It is necessary to start the algorithm up the hill!
This article is used to record every step on the road
~ The kind that doesn’t take pictures
Adhere to periodic updates (3 Easy, 2 Mid and 1 Hard papers a day)
To lay the foundation for myself to be interviewed after graduation in two years
Forge ahead! Less to play…
Tip: Each problem has examples, solution ideas, solution codes and execution results
If you have help enlighten a small praise oh ~ hope your algorithm road, also have my company ~
Day 1-07.08
Remember: Today is the last day of the college entrance examination… Hope the examinees live up to their efforts
Easy
1. Sum of two numbers 2. Integer reversal 3
The sum of two Numbers
Given an array of integers nums and a target value target, find the two integers in the array and the target values and return their array subscripts. You can assume that there is only one answer for each type of input. However, the same element in an array cannot be used twice.Copy the codeThe instance
Given nums = [2, 7, 11, 15], target = 9Copy the codeAnswer ideas
1. The key is target- the remaining value of the current array, which is equal to some 2 in the remaining value of the array. Use the object key as the value and value as the subscript
To solve the code
var twoSum = function(nums, target) {
const prevNums = {}; // Store the object
for (let i = 0; i < nums.length; i++) {
const curNum = nums[i]; // The current array value
const targetNum = target - curNum; // Current remaining value
const targetNumIndex = prevNums[targetNum]; // If key is the current value of the storage object -> get value subscript
if(targetNumIndex ! = =undefined) { // When the stored object has the subscript
return [targetNumIndex, i]; // Return the target index and the current index
}
prevNums[curNum] = i; // Otherwise store value -> subscripts and key -> values}}Copy the codeCode execution results
Input: [2,7,11,15] 9
The output of [0, 1]
Expected results [0,1]
Integer inversion
Given a 32 - bit signed integer, you need to invert each digit of the integer. Note the possibility of integer overflow after inversion -> returns 0Copy the codeThe instance
Example 1: Input: 123 Output: 321 Example 2: Input: -123 Output: -321 Example 3: Input: 120 Output: 21Copy the codeAnswer ideas
1. Invert the integer one bit to the left and add the last bit of the original integer to the left until the original integer is 0 2. Note that the inverted integer needs to be converted to a 32-bit signed integer 3. If overflow -> inverted integer is not equal to itself -> overflow is Infinity
To solve the code
var reverse = function(x) {
let reverseNumber = 0 // Invert the integer to 0
while(x) {
reverseNumber = reverseNumber * 10 + x % 10 // Invert the integer one to the left plus the last digit of x
x = (x / 10) | 0 Remove the last digit / / the original integer x | 0 - > cast to a 32-bit signed integer
}
return (reverseNumber | 0) === reverseNumber ? reverseNumber : 0
// Reverse integer coercion to 32-bit signed integer -> if not equal to itself -> Determine overflow -> value 0
};
Copy the codeCode execution results
Enter 12345
The output of 54321
Expected Result 54321
Convert Roman numerals to integers
Roman numerals contain the following seven characters: I, V, X, L, C, D and M. Character value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, the Roman numeral 2 is written as II, which is the parallel 1. Write XII as X + II. Write XXVII as XX + V + II. Usually, the smaller Roman numerals are to the right of the larger numerals. But there are exceptions, for example, 4 is not written as IIII, it's written as IV. The number 1 is to the left of the number 5 and represents the number 4 when the larger number 5 decreases by 1. Similarly, the number 9 represents IX. This particular rule applies only to the following six cases: I can be placed to the left of V (5) and X (10) to represent 4 and 9. X can be placed to the left of L (50) and C (100) to represent 40 and 90. C can be put to the left of D (500) and M (1000) to represent 400 and 900. Given a Roman numeral, convert it to an integer. Make sure the input is in the range of 1 to 3999.Copy the codeThe instance
Example 1: Input: "IX" Output: 9 Example 2: Input: "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3. Example 3: Input: "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90, IV = 4.Copy the codeAnswer ideas
1. Create a Roman character object -> corresponding character corresponding value 2. Greedy thought -> convert from the largest character to the smallest character one by one 3. The current Roman character < right Roman character -> integer minus the value of the current Roman character otherwise plus 4. Traversing the entire Roman character is complete
To solve the code
var romanToInt = function(s) {
const roman = { // Create a Roman character object
'I': 1.'V': 5.'X': 10.'L': 50.'C': 100.'D': 500.'M': 1000,}const length = s.length // The length of the Roman string
let result = 0 // Convert integers
for(let i = 0; i < s.length; i++ ) {
const currentNum = roman[s[i]] // When Roman characters correspond to numeric values
if(i < length - 1 && currentNum < roman[s[i+1]]) { // Is judged to be the penultimate string and the current Roman value is less than the right-hand value
result -= currentNum // Subtract the current value
} else {
result += currentNum // Add the current value instead}}return result // Return the converted integer
};
Copy the codeCode execution results
Input “MCMXCIV”
The output of 1994
Expected Results 1994
Day 2-07.09
Remember before: wrote for a long time small program, go out for a walk with little sister
Mid
1. Add two numbers. 2
The two together
Give two non-empty linked lists to represent two non-negative integers. Their respective bits are stored in reverse order, and each node can store only one digit. If we add these two numbers together, a new linked list is returned to represent their sum.Copy the codeThe instance
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Cause: 342 + 465 = 807Copy the codeAnswer ideas
1. Add the first digit of L1 and L2 to the list -> sum 3. If sum >= 10 -> next + 1
To solve the code
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}* /
var addTwoNumbers = function(l1, l2) {
let node = new ListNode('head'); // table header (top ListNode method)
let temp = node; // The current pointer to the table header
let add = 0; // Whether to enter one
let sum = 0; // The current total value is
while(l1 || l2){ // Iterate until the longest list is empty
If l1+ L2 > 10 -> +1 is required
sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + add;
temp.next = new ListNode(sum % 10); // The current sum is mod to the new list
temp = temp.next; // point to the next list
add = sum >= 10 ? 1 : 0; // Check whether the sum >= 10
l1 && (l1 = l1.next); // l1 points to the next list
l2 && (l2 = l2.next); // l2 points to the next list
}
// When the last add exists -> add >= 10 -> save it to the new list
add && (temp.next = new ListNode(add));
return node.next; // Returns the next result of the new list
};
Copy the codeCode execution results
Input [2, 3],6,4 [5]
Output,0,8 [7]
Expected results [7,0,8]
The oldest string without repeating characters
Given a string, find the length of the smallest string that does not contain repeating characters.Copy the codeThe instance
Example 1: Input: "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3. Example 2: Input: "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1. Example 3: Input: "pwwkew" Output: 3 Explanation: Since the oldest string without repeating characters is "wke", its length is 3. Note that your answer must be the length of the substring, "pwke" is a subsequence, not a substring.Copy the codeAnswer ideas
1. Iterate over each character in the string 2. Store each character in an array 3. Judge Max to take the longest length of the whole process
To solve the code
var lengthOfLongestSubstring = function(s) {
let arr = [], max = 0 // The maximum length of a character to be stored in an array
for(let i = 0; i < s.length; i++) { // Iterate over each character
let index = arr.indexOf(s[i]) // Whether the array has the current character
if(index ! = = -1) {
arr.splice(0, index+1); // If it already exists -> Clear the character before the existing character
}
arr.push(s.charAt(i)) // Store the current character -> is at least 1 in length
max = Math.max(arr.length, max) // Determine the current array length and Max size
}
return max // Returns the maximum length
};
Copy the codeCode execution results
Input “DVDF”
The output of 3
Expected Result 3
Day 3-07.10
Previous note: hit the game, difficult questions liver fast 3 hours, or not quite clear the official practice…
Hard
1. Match regular expressions
Regular expression matching
Given a string s and a character rule P, implement a regular expression match that supports '.' and '*'. '.' matches any single character.' *' matches zero or more of the preceding elements. Note: s may be empty and contains only lowercase letters from A to Z. P may be empty and contains only lowercase letters from A to Z, as well as the characters. And *. Do not use JS regular expressions. This problem will be meaninglessCopy the codeThe instance
Example 1: Input: s = "aa" p = "a" Output: false Description: "A" cannot match the entire string "aa". Example 2: input: s = "ab" p = ". * "output: true explanation:" * "said can match zero or more (' * ') any character ('. '). Example 3: Input: s = "aab" p = "c*a*b" Output: true Explanation: Because '*' means zero or more, here 'c' is zero and 'a' is repeated once. So it matches the string "aab". Example 4: Input: s = "Mississippi" p = "mis*is*p*." output: falseCopy the codeAnswer ideas
1. Define the basic return condition. If the length of p is 0, the length of S is 0, indicating a match; if the length of S is not 0, indicating a mismatch 2. Define the matching state match, which is the comparison of the first character, true 3 if it is equal or p[0] is ‘.’. When p has no mode, we will return according to the state of match. If match is false, we will directly return false. If it is true, then we will proceed to the next judgment. When P has a pattern, there are two cases: GetIsMactch (s, p.ice (2)) matches 0 characters; getIsMactch(s, p.ice (2)) matches 1 character; Then getIsMactch(s.ice (1), p). 5. Return the matching result
To solve the code
var isMatch = function (s, p) {
let getIsMactch = (s, p) = > {
// If the length of p passed in is 0, then s must also be 0 to return true
if (p.length === 0) {
return! s.length }// Determine if the first character is equal
let match = false
if (s.length > 0 && (s[0] === p[0] || p[0= = ='. ')) {
match = true
}
//p has a pattern
if (p.length > 1 && p[1= = ="*") {
// If there is an "*" character, backtrace the character
// The first case: s* matches 0 characters
// The second case: s* matches 1 character, recursively, is used to indicate that s* matches multiple s*
return getIsMactch(s, p.slice(2)) || (match && getIsMactch(s.slice(1), p))
} else {
return (match && getIsMactch(s.slice(1), p.slice(1)))}}return getIsMactch(s, p) // Returns the result of the final call method match
}
/** * official solution code */
var isMatch = function(s, p) {
function matches(s, p, i, j) {
if (i == 0) {
return false;
}
if (p.charAt(j - 1) = = ='. ') {
return true;
}
return s[i - 1] === p[j - 1];
}
let m = s.length
let n = p.length
let f = []
for (let i = 0; i <= m; i++) {
f.push(new Array(n + 1).fill(false))
}
f[0] [0] = true
for (let i = 0; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
if (p[j - 1] = =The '*') {
f[i][j] = f[i][j - 2];
if (matches(s, p, i, j - 1)) {
f[i][j] = f[i][j] || f[i - 1][j]; }}else {
if (matches(s, p, i, j)) {
f[i][j] = f[i - 1][j - 1]; }}}}return f[m][n]
}
Copy the codeCode execution results
Input “Mississippi” “misisp *.”
Output is false
Expected result False
Day 4-07.11
Remember before: oh ho ho ho ho ho ho ho, wrote a day small program. Wait for the little white boat
Easy
Palindromes 2. Longest common prefix 3. Valid parentheses
The sum of two Numbers
Checks whether an integer is a palindrome. Palindromes are integers that read in positive (left to right) and backward (right to left) order.Copy the codeThe instance
Example 1: Input: 121 Output: true Example 2: Input: -121 Output: false Description: The value is -121 read from left to right. Read from right to left, 121-. So it's not a palindrome number. Example 3: Input: 10 Output: false Description: Read from right to left. The value is 01. So it's not a palindrome number.Copy the codeAnswer ideas
1. Convert an integer into a string 2. Invert the string 3
To solve the code
var isPalindrome = function(x) {
const reserveStr = x.toString().split("").reverse().join("")
return reserveStr === x.toString()
}
Copy the codeCode execution results
Enter: 121 9
The output of true
Expected result True
Longest public prefix
Write a function to find the longest public prefix in an array of strings. Returns the empty string "" if no public prefix exists.Copy the codeThe instance
Example 1: input: [" flower ", "flow", "flight"] output: "fl" example 2: input: [" dog ", "racecar", "car"] output: "" explanation: the input that there is no public prefix. Note: All inputs contain only lowercase letters A-Z.Copy the codeAnswer ideas
1. Initialize any array string (principle: public prefix is less than any string) 2. Start traversing and comparing string arrays -> if the public prefix is not equal to the current one -> intercept the previous public prefix 3. After traversal, public prefix is returned -> If public prefix is null -> early
To solve the code
var longestCommonPrefix = function(strs) {
if(strs.length == 0) // If the character array is an empty array -> returns empty
return "";
let ans = strs[0]; // Initializes the public prefix for the first array string
for(let i = 1; i < strs.length; i++) { // Iterate over the character array
let j = 0;
// The public prefix is less than the initial string length and less than the current string length
for(; j < ans.length && j < strs[i].length; j++) {// Public prefix characters and current array string characters are not equal -> break
if(ans[j] ! = strs[i][j])break;
}
// Intercepts currently equal public prefixes
ans = ans.substr(0, j);
if(ans === "") // If the public prefix is empty -> returns directly without traversal
return ans;
}
return ans; // When traversal is complete, return the public prefix
};
Copy the codeCode execution results
Input (” flower “, “flow”, “flight”]
Output “fl”
Expected result “FL”
Valid parentheses
Given a string containing only '(', ')', '{', '}', '[', ']', check whether the string is valid. A valid string must meet the following requirements: The left parenthesis must be closed with the same type of the right parenthesis. The left parentheses must be closed in the correct order. Note that an empty string can be considered a valid string.Copy the codeThe instance
Example 1: input: "() [] {}" output: true example 2: input: "[]" output: false example 3: input: "([]" output: false example 4: input: "{[]}" output: trueCopy the codeAnswer ideas
1. Because an empty string can be considered a valid string -> only the parenthesis character 2 is extracted using the key and value of the object. Using the stack idea -> close before out principle -> here the parenthesis characters are defined as open and close 3. If open characters -> Store the corresponding closed characters in the stack 4. If closed characters -> Remove the top character of the stack -> Check whether the same 5. If not equal -> return false/if the stack is empty after traversal -> return true
To solve the code
var isValid = function(s) {
// Bracket characters can be on or off
const brackets = { // define parenthesis objects -> key for open and value for closed
'(': ') '.'{': '} '.'[': '] '
}
let stack = [] // Define an empty stack
let top = undefined / / stack
for(let char of s) { // Iterate over characters
let value
if((value = brackets[char])) { // If the open character of the object key -> is assigned to value
stack.push(value) // Put the corresponding closed character in the stack
} else { // If closed
top = stack.pop() // Remove the top of the stack
if(top ! == char) {// Check whether the top of the stack equals the current closed character
return false // If not equal -> return false}}}return stack.length === 0 // Traversal ends, stack is empty -> returns true
};
Copy the codeCode execution results
Input (” []”
Output is false
Expected result False
Day 5-07.13
Ex: EMMM was a bit lazy this summer
Mid
1. Longest substring of a text 2.Z transform
The two together
Given a string s, find the longest subroutine in s. You can assume that the maximum length of s is 1000.Copy the codeThe instance
Example 1: Input: "babad" Output: "bab" Note: "ABA" is also a valid answer. Example 2: Input: "CBBD" Output: "bb"Copy the codeAnswer ideas
1. Find the longest palindrome string -> Use dynamic programming. 2. Stretch from one character to the other -> and both strings are palindrome strings -> still mark true
To solve the code
var longestPalindrome = function(s) {
// babad
// tag : dp
if(! s || s.length ===0) return "";
let res = s[0]; // If not empty, initialize the substring to be the first one
const dp = [];
// Iterate backwards to simplify operations. The reason for doing so is dp[I][..] Dependent on dp[I + 1][..]
for (let i = s.length - 1; i >= 0; i--) {
dp[i] = [];
for (let j = i; j < s.length; j++) {
// If the first character -> is marked true
if (j - i === 0) dp[i][j] = true;
// If the second character is equal -> is marked true
else if (j - i === 1 && s[i] === s[j]) dp[i][j] = true;
// If a string is a palindrome string and both strings are palindrome strings, then it must be a palindrome string
else if (s[i] === s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
}
// The flag bit is true and the length is greater than the substring length of the live text
if (dp[i][j] && j - i + 1 > res.length) {
// Update the truncated text substring
res = s.slice(i, j + 1); }}}return res;
};
Copy the codeCode execution results
Input “babad”
Output “aba”
Expected result “BAB”
Z transformation
Arranges a given string in a zigzagging pattern from top to bottom and left to right according to the given number of lines. For example, if the input string is "LEETCODEISHIRING" on 3 rows, it will be arranged like this: L C IR ET O E S I I G E D H N Your output will need to be read line by line from left to right to produce a new string, for example: "LCIRETOESIIGEDHN".Copy the codeThe instance
Example 1: Enter: S = "LEETCODEISHIRING", numRows = 3 Output: "LCIRETOESIIGEDHN" Example 2: Enter: S = "LEETCODEISHIRING", numRows = 4 Output: LDREOEIIECIHNTSGCopy the codeAnswer ideas
NewStr -> newStr -> newStr -> newStr -> newStr -> newStr -> newStr You can move the array subscript (up or down) depending on the number of input lines -> store the character 3 corresponding to the same row. Finally concatenate each string in the array -> new Z-transform
To solve the code
var convert = function(s, numRows) {
// Returns a string of 1 lines
if(numRows === 1) return s
// Determine whether the length of a character is greater than the number of lines
const len = Math.min(s.length, numRows)
// Array of strings per line
let rowStr=[]
// Initialize the string array to an empty string
for(let i = 0; i < len; i++) {
rowStr[i] = ""
}
// Define index and position as up or down
let index = 0, down = false
// Iterate over the string
for (const c of s) {
rowStr[index] += c
// If at the top or at the bottom -> replace the label
if(index === 0 || index === numRows - 1) down = ! down// Index changes
index += down ? 1 : -1
}
// Extract each line of string -> concatenate a new string
let res = ""
for(const str of rowStr) {
res += str
}
return res
};
Copy the codeCode execution results
Input “PAYPALISHIRING” 3
Output “PAHNAPLSIIGYIR”
Expected result “PAHNAPLSIIGYIR”
Day 6-07.14
Previous note: TODAY, I saw the advertisement on the Nuggets and thought about it all day. I applied for the summer camp of Bytedance for the first time. I was a little excited! I hope I can be lucky
Hard
1. Merge K sorted linked lists
Merge K sorted linked lists
Merge k sorted lists and return the merged sorted lists. Analyze and describe the complexity of the algorithm.Copy the codeThe instance
Example 1: input: [1 - > 4 - > 5, 1 - > 3 - > 4, 2 - > 6] output: 1 - > 1 - > 2 - > 3 - > 4 - > 4 - > 5 - > 6Copy the codeAnswer ideas
1. Notice that there are k sorted lists -> you can use violence to walk through the whole list into the array -> array sort value -> array becomes merged sorted list 2. A +b = new -> new+ C = new -> new+ D = new -> new+ D = new -> complete traversal
To solve the code
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode[]} lists
* @return {ListNode}* /
var mergeKLists = function(lists) {
let len = lists.length; // List length
if(len == 0) return null; / / if empty
if(len == 1) return lists[0]; // If there is only one (no need to merge)
let heap = new ListNode(); // Create a new list
heap.next = lists[0]; // point to the first list
for(let i = 1; i < len; i++){ // Iterate over the list
let origh = heap; // Initializes the new merged list
let cur1 = heap.next; // Next of the newly merged linked list
let cur2 = lists[i]; // lists Next linked list
while(cur1 ! =null&& cur2 ! =null) {// Are not empty time
// origh points to small values and moves next of cur1 or cur2
if(cur1.val >= cur2.val) {
origh.next = cur2;
cur2 = cur2.next;
}else{
origh.next = cur1;
cur1 = cur1.next;
}
// Move the merge list next
origh = origh.next;
}
// If there is the largest value in the list
if(cur1) origh.next = cur1;
if(cur2) origh.next = cur2;
}
return heap.next; // When traversal is complete -> return to next for the merged list
};
/** * a heap list -> space complexity O(1) * time complexity -> if there are n elements in each K list -> O(kn) */
Copy the codeCode execution results
Input [].enlighened by [1 4], [2, 6]]
Output,1,2,3,4,4,5,6 [1]
Expected results [1,1,2,3,4,4,5,6]
Day 7-07.16
Remember before: today the small program resume to the end, I plan to give an article about it
Easy
1. Merge two ordered lists. 2. Remove duplicates from sorted arrays. 3
Merges two ordered lists
Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.Copy the codeThe instance
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4Copy the codeAnswer ideas
2. As usual, the linked list can be iterated 3. There will be a maximum left at the end, so make sure next goes in
To solve the code
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}* /
var mergeTwoLists = function(l1, l2) {
const list = new ListNode(-1) // Initializes the first number of the merged list -1
let merge = list / / shallow copy
while(l1 && l2) { // if both l1 and L2 chains have values
if(l1.val >= l2.val) {
merge.next = l2 // merge the list next to point to a smaller value
l2 = l2.next
} else {
merge.next = l1
l1 = l1.next
}
merge = merge.next // Move the merged list pointer
}
merge.next = l1 === null ? l2 : l1 // There will be a maximum at the end
return list.next // Return next for the list
};
Copy the codeCode execution results
Input: [1,2,4]
Output,1,2,3,4,4 [1]
Expected results [1,1,2,3,4,4]
Removes duplicates from the sorted array
Given a sorted array, you need to remove duplicate elements in place so that each element appears only once, returning the new length of the removed array. Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space.Copy the codeThe instance
Example 1: Given the array nums = [1,1,2], the function should return a new length of 2, and the first two elements of the original array nums are changed to 1,2. Example 2: Given nums = [0,0,1,1,1,2,2,3,3,4], the function should return a new length of 5, and the first five elements of the original nums array are modified to 0,1, 2,3, 4.Copy the codeAnswer ideas
1. Use indexOf to determine if the first occurrence of an element’s index is not equal to the current occurrence, delete it 2. Delete array length minus 1, so the subscript moves forward one bit
To solve the code
/ * * *@param {number[]} nums
* @return {number}* /
var removeDuplicates = function(nums) {
for(let i = 0; i < nums.length; i++) {
if(nums.indexOf(nums[i]) ! == i) { nums.splice(i,1)
i --
}
}
return nums.length
};
Copy the codeCode execution results
Input,0,1,1,1,2,2,3,3,4 [0]
Output,1,2,3,4 [0]
Expected results [0,1,2,3,4]
Remove elements
Given an array of nums and a value of val, you remove all elements equal to val in place and return the new length of the array. Instead of using extra array space, you must only use O(1) extra space and modify the input array in place.Copy the codeThe instance
Example 1: Given nums = [3,2,2,3] and val = 3, the function should return a new length of 2 and the first two elements in nums are both 2. Example 2: Given nums = [0,1,2,2,3,0,4,2], val = 2, the function should return a new length of 5, and the first five elements in nums are 0,1, 3,0,4. Notice that these five elements can be in any order.Copy the codeAnswer ideas
Splice = nums.splice = nums.splice = nums.splice = nums.splice None -> Returns the length of the new array
To solve the code
var removeElement = function(nums, val) {
let i // Define the return index
while(nums.indexOf(val) ! = = -1) { // If the value exists in the array
i = nums.indexOf(val)
nums.splice(i, 1) // Remove the value
}
return nums.length // Returns the length
};
Copy the codeCode execution results
Input,2,2,3 [3] 3
The output (2, 2]
Expected results [2,2]
Day 8-07.17
Previous note: Today is also the day of summoner canyon
Mid
1. String conversion integer (AToi) 2. Container that holds the most water
String conversion to integer (atoi)
Implement an AToi function that converts a string to an integer. First, the function discards useless leading whitespace characters as needed until the first non-whitespace character is found. In any case, if the function cannot perform a valid conversion, return 0.Copy the codeThe instance
Example 1: Input: "42" Output: 42 Example 2: Input: "4193 with words" Output: 4193 Explanation: Conversion ends at the number '3' because its next character is not a number. Example 3: Input: "Words and 987" Output: 0 Explanation: The first non-empty character is 'w', but it is not a number or a plus or minus sign. Therefore, a valid transformation cannot be performed. Example 4: Input: "-91283472332" Output: -2147483648 Description: Number "-91283472332" exceeds the range of 32-bit signed integers. So INT_MIN (−231) is returned.Copy the codeAnswer ideas
1. Use the Js parseInt() function -> ignore the leading space -> return the signed integer -> ignore the character 2 after the integer part. We need to determine that -> range is within 32 bits (inclusive) -> otherwise return 0
To solve the code
var myAtoi = function(str) {
const number = parseInt(str, 10);
if(isNaN(number)) { // Return 0 in other cases
return 0;
}
// Determine to be within 32 bits
return result = number <= Math.pow(-2.31)?Math.pow(-2.31) : number >= Math.pow(2.31)?Math.pow(2.31) - 1 : number
}
Copy the codeCode execution results
Input “+ – 3241 aac22”
0
Expected Result 0
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, and the value of n is at least 2.Copy the code
The vertical lines in the figure 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) is 49.Copy the codeThe instance
Example 1: Input: [1,8,6,2,5,4,8,3,7] Output: 49Copy the codeAnswer ideas
1. Double pointer -> indicates the beginning and end 2. When the beginning pointer > the end pointer -> traversal ends 3. 4. Compare the current volume with the highest volume and assign a value
To solve the code
var maxArea = function (height) {
let res = 0, i = 0, j = height.length - 1, cur = 0;
while (i < j) { // I is the left pointer, j is the right pointer
// The height is the shorter side on both sides
let h = height[i] < height[j] ? height[i] : height[j];
cur = h * (j - i); // Current volume
res = cur > res ? cur : res; // Determine the maximum volume
if (height[i] < height[j]) { // Move the short pointer
i++;
} else{ j--; }}return res; // Return the maximum volume
};
Copy the codeCode execution results
Input,8,6,2,5,4,8,3,7 [1]
The output of 49
Expected Result 49
Day 9-07.18
Note: TODAY I attended codeJump’s summer camp written test, but I didn’t check my email!! Waiting for a text message… Results the last 40 minutes to see the text messages of the test alas overall are the topic of the algorithm, or weak… And 150 minutes, I’m late, only 40 minutes for the written test. Give yourself a wake-up call, not only to see the official website application process and SMS, but also look at the mailbox
Hard
1. Find the median of two positive ordinal groups
Find the median of two positive ordinal groups
Given two positively ordered (from small to large) arrays of size m and n, nums1 and nums2. Find the median of the two groups of positive Ordinal Numbers, and the time complexity of the algorithm is order (log(m + n)). You can assume that nums1 and nums2 are not null at the same time.Copy the codeThe instance
Example 1: nums1 = [1, 3] Nums2 = [2] The median is 2.0. Example 2: nums1 = [1, 2] Nums2 = [3, 4] The median is (2 + 3)/2 = 2.5Copy the codeAnswer ideas
1. Violence algorithm -> merge -> sort -> judge even -> return (time complexity O(m+n) -> do not fit the 题 干) 2. Dichotomy (time complexity O(log(min(m, n))) -> I thought about it for a few hours but still didn’t understand, so I could only refer to the code to put 3. Annotate your own understanding of the code
To solve the code
/** * violent solution * time complexity O(m+n) * space complexity O(0) */
var findMedianSortedArrays = function(nums1, nums2) {
// Merge -> sort -> avoid negative numbers
let nums3 = nums1.concat(nums2).sort((a,b) = >a-b);
let length = nums3.length;
if(length%2= =0) {return (nums3[length/2-1] + nums3[length/2) /2
}else{
return nums3[Math.floor(length/2)]}};/** * dichotomy * Time complexity O(log(min(m, n))) * space complexity O(0) */
var findMedianSortedArrays = function(nums1, nums2) {
// Ensure that m is the shortest array length
if (nums1.length > nums2.length) {
[nums1, nums2] = [nums2, nums1]
}
const m = nums1.length
const n = nums2.length
let low = 0
let high = m
while(low <= high) {
const i = low + Math.floor((high - low) / 2) // a pointer to nums1
const j = Math.floor((m + n + 1) / 2) - i // A pointer to nums2
// The array is out of bounds
const maxLeftA = i === 0 ? -Infinity : nums1[i-1]
const minRightA = i === m ? Infinity : nums1[i]
const maxLeftB = j === 0 ? -Infinity : nums2[j-1]
const minRightB = j === n ? Infinity : nums2[j]
if (maxLeftA <= minRightB && minRightA >= maxLeftB) {
return (m + n) % 2= = =1 // Determine parity
? Math.max(maxLeftA, maxLeftB)
: (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2
} else if (maxLeftA > minRightB) { // The left nums1 digit is greater than the right nums2 digit
high = i - 1 // Move the high pointer one bit to the left
} else {
low = low + 1 // Move the low pointer one bit to the right}}};Copy the codeCode execution results
Input [3] [- 2-1]
Output – 1.0 –
Expected Result -1.0
Day 10-07.19
Summary: feel this record algorithm is very cumbersome 20 questions about to pull a very long or decide to liberate other places -> every 50 algorithms send a train of thought with a link to solve the problem
Easy
1. Implement strStr() 2. Search for insertion position 3
Day 11-07.20
Note before: Want to escape from life all this
Mid
1. Sum of three numbers 2. Letter combination of a telephone number
Day 12-07.21
Note before: drip drip drip
Hard
1. Missing the first positive number
Day 13-07.22
Previous note: Sleep for a long time – recently like to read shuang Wen novels, I go
Easy
1. Maximum suborder sum 2. Add one 3. Square root of x 4
Day 14-07.23
Note before: handsome boy add quantity don’t add price oh
Mid
1. Delete the NTH node from the list 2. Generate parentheses 3
Day 15-07.24
Before: tomorrow I will go to Huizhou with a friend for a few days
Hard
1. Receiving rain water 2. Matching wildcard
Day 16-07.30
Previously note: I’m back! After a few days in Huizhou, I felt that I wanted to make money
Easy
1. Merge two ordered arrays 2. Symmetric binary tree 3
Day 17-07.31
Previous note: Keep going
Mid
1. Search the rotation sorted array 2. Find the first and last positions of elements in the sorted array 3. Valid sudoku
Day 18-08.01
Previous note: August hello! Please be nice to me haha ~ keep trying to go to Dachang
Hard
1. Minimum coverage substring
Stern said
Hang a tail speech in advance xi xi ~ will adhere to continuous update, may do the topic direction is not quite right when you big guys also hope not stingy give advice! ✨ take photos, small make up photography light thief
Welcome to the cabin anytime ~ also welcome your suggestions