This is the 28th day of my participation in the Genwen Challenge
This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.
139. FindContinuousSequence of positive numbers and s
The label
- mathematics
- The sliding window
- simple
The title
Leetcode portal
Let’s just open leetCode.
Enter a positive integer target and print all consecutive sequences of positive integers (at least two numbers) that sum to target.
The numbers in the sequence are arranged from smallest to largest, and different sequences are arranged from smallest to largest according to the first number.
Example 1
Enter: target =9Output: [[2.3.4], [4.5]]
Copy the codeExample 2
Enter: target =15Output: [[1.2.3.4.5], [4.5.6], [7.8]]
Copy the codeThe basic idea
If a sequence of continuous positive integers is a solution, we can look for a solution and just find the left and right boundary and derive a solution.
Consider using a sliding window, so set the window pointer to the left and right, and calculate the sum of the current window, compared to target
- When curSum === target, a solution is obtained
- When curSum > target, the left pointer moves right to reduce the window
- When curSum < target, the right pointer moves right to enlarge the window
How about knowing the left and right Pointers, the current and how to evaluate, and the answer is order 1, the arithmetic summation formula
For example, if left = 1 and right = 4, the curSum is 1 + 2 + 3 + 4
Remember the lesson when Gauss was a child, Little Teacher Gauss asked them to increase from 1 to 100, and Then Gauss used (1 + 100) * 50 = 5050 (100 is the number of terms, divided by two is 50), which is actually the sum of the first and the last times the number of terms divided by two. So this is the formula for the sum of arithmetic sequences, so the tolerance d is equal to 1, so the current sum is
The left and right Pointers are left =1 , right = 4 (1.2.3.4) a total of4The number (1(first) +4(tail) *4(Number of items) /2 = 10 (1+2+3+4=10Tolerance for1This term right here4In fact, it can also be expressed simply by the left and right pointer, (4 - 1) + 1 = 4The number of// So one line of code, no loop add
let curSum = (left + right) * (right - left + 1) / 2;
Copy the codeSo let’s write it this way
Writing implement
var findContinuousSequence = function(target) {
let [res, left, right] = [[], 1.2]
// Do the pointer not beyond the right pointer
while (left < right) {
// The arithmetic sequence summation formula, analysis has derivation
let curSum = (left + right) * (right - left + 1) / 2;
// When we find equality, we add one from the left to the bounded array into the result set
if (curSum === target) {
// The starting position of a solution is stored in a temporary variable
let startNum = left
[left, right] [left, right] [left, right
res.push(
new Array(right - left + 1).fill(0).map(() = > startNum++)
);
// get a solution, the curSum is cleared, continue left++ to find the next solution
curSum = 0
left++
} else if (curSum < target) {
right++;
} else {
left++
}
}
return res
};
let target = 15
console.log(findContinuousSequence(target))
Output: [[1,2,3,4,5],[4,5,6],[7,8]]
Copy the code140. The sum of two integers
The label
- An operation
- medium
The title
Leetcode portal
Let’s just open leetCode.
Computes the sum of two integers A and b without using the operators + and -.
Example 1
Enter: a =1, b = 2Output:3
Copy the codeExample 2
Enter: a = -2, b = 3Output:1
Copy the codeThe basic idea
Instead of using the + and – operators, we need some other way to replace them.
Think bit operations.
This is the only problem I’ve written so far that is mainly bitwise. I don’t recommend bitwise if you are writing business code, it sacrifices a lot of readability, and you should think more about novices and teams. Unless you’re writing an underlying framework, which is very hidden and exposes simple interfaces, that’s a different story.
So let’s talk about some basic bit operations.
Let’s start with the addition in bitwise operations
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0(in1)Copy the codeXor seems to be the same except for carry
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
Copy the codeThe 5 ^ 6 calculation is xOR by bit
5 = 1 0 1
6 = 1 1 0^ -- -- -- -- --0 1 1= >3
console.log(5 ^ 6) / / 3
Copy the codeWe also notice that he’s not going to carry, so we need to find the point where we need to carry
And operations that satisfy this property, both 1 and carry
5 = 1 0 1
6 = 1 1 0And -- -- -- -- --1 0 0=> The point to carry is found exactlyCopy the codeBut this is the place to the left where it carries, so we have to move the and one place to the left
Left shift operator <<, left shift result is (5&6) << 1 === 8
And then you add these two things together 8 plus 3 is 11 which is the sum of 5 plus 6
Use recursion until no carry is required (end of recursion condition)
Writing implement
var getSum = function(a, b) {
// Recursive exit
if (b === 0) {
return a;
}
return getSum(a ^ b, (a & b) << 1);
};
let a = 1, b = 2
// let a = -2, b = 3
console.log(getSum(a, b))
Copy the codeIn addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series
If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions