This is the 7th day of my participation in Gwen Challenge. Check out Gwen Challenge for details
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.
112. Pow(x, n) (powx-n)
The label
- Divide and conquer
- medium
The title
Leetcode portal
Let’s just open leetCode.
Implement POW (x, n), that is, compute x to the NTH power (that is, x to the n).
Example 1:
Input: x = 2.00000, n = 10 Output: 1024.00000Copy the codeExample 2:
Input: x = 2.10000, n = 3 Output: 9.26100Copy the codeExample 3:
Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25Copy the codeThe basic idea
Of course, we do not consider opportunistic methods, such as library functions or brute force multiplication.
Let’s think about the efficient way to do it, divide and conquer
Divide and conquer: “divide and conquer” – is to divide a complex problem into two or more identical or similar sub-problems, until the sub-problems can be solved directly, the solution of the original problem is the combination of the solutions of the sub-problems.
In fact, we really need to understand and apply this algorithm, and really think about whether divide-and-conquer, besides being an algorithm, can be a universal mental weapon that we can use to accomplish complex goals.
Tell a small story from a place, not specific real consideration, look at the general idea
-
Elon Musk founded SpaceX, a space exploration company. SpaceX has a goal of sending a million people to Mars.
-
The United States government once calculated that sending a man to Mars, which is possible with current technology, would cost about $10 billion.
-
If you do that, it would take $10 trillion to send a million people to Mars to achieve Musk’s goal. What is this concept? That’s the equivalent of 500 years of U.S. GDP, so expensive that even the U.S. government can’t afford it.
-
How does Musk solve this problem? First of all, his goal has changed. He is going to reduce the cost per person to $500,000, that is, a would-be immigrant who can sell a house on Earth for as much money as he can scrape together. It went from $10 billion to $500,000, which is 20,000 times lower.
-
Of course, a 20,000-fold reduction still sounds like a distant goal. So here’s where we’re going: Musk’s second step is to break 20,000 down into 20×10×100. It’s a simple math problem that Musk is working on with three priorities. (Divide-and-rule)
-
Start with “20” : The current Mars spacecraft can only carry five people at a time, but Musk’s plan is to make the rocket bigger and carry 100 people at a time, which would reduce the cost by 20 times. If you follow the news, SpaceX is actually trying to do this,
-
Then there’s “10” : Musk thinks he’s a private company, efficient, and can cut costs by a tenth. They’re working on that, too, with SpaceX’s costs now down to a fifth of those of its peers.
-
What is the last “100”? Is to recycle reusable rockets. If that were achieved, the cost of launching a rocket would be fuel alone. That’s why we’ve seen so many SpaceX test flights.
Does that make Musk’s goal seem less far-fetched than it first sounds? It is by breaking big goals down into tasks that Mr Musk is able to move a seemingly far-fetched goal forward.
We all have trouble answering big questions, but we’re good at answering small ones. We need to break it down to a point where we can’t do it mindlessly and we can land on it easily.
We can actually simplify this problem to a much simpler subproblem
// n is even 4* * * x x x x | | x x x x x * is actually two n =2 (n / 2The product of the solutions of// if n is odd, for example, n = 5X times x times x times x times x times x times x times x times even, times even divide-and-conquer x times two times n over n2The product of the solutions ofCopy the codeAnother thing to watch out for is n < 0. Look at the code
Writing implement
var myPow = function(x, n) {
if (n === 0) {
// Any number raised to the 0 power is 1
return 1
} else if (n < 0) {
// The power is less than 0, use the inverse
return 1 / myPow(x, -n)
} else if (n % 2! = =0) {
// If n is odd
return x * myPow(x, n - 1)}else {
// If n is even, divide into 2 parts recursively
return myPow(x * x, n / 2)}};console.log(myPow(2.10)) / / 1024
console.log(myPow(2, -2)) / / 0.25
Copy the codeThis algorithm is order logn in time.
113. Majority-element
The label
- Divide and conquer
- simple
The title
Leetcode portal
Let’s just open leetCode.
Given an array of size N, find most of the elements. Most elements are those that occur more than ⌊ n/2 ⌋ in the array.
You can assume that the array is non-empty and that a given array always has most elements.
An algorithm with time complexity O(n) and space complexity O(1) is designed to solve this problem.
Example 1:
Input: [3,2,3] Output: 3Copy the codeExample 2:
Input: [2,2,1,1, 2,2] Output: 2Copy the codeThe basic idea
The first thing we can think of is that if we use a Map data structure to count, we just have to go through it once to find the one with the largest count, O(n) time complexity, but the space is still O(n) complexity because of the Map structure.
There is another way, we can sort the same elements together, and then use a pointer to count, when we find a number count > n / 2, we can return the time complexity, because of sorting, the average is O(nlogn), but only O(1) space.
Is there any other way?
The idea is, you know there’s got to be some number that’s more than half the total.
-
So let’s imagine a two-person race, (assuming the total number of votes is singular and there is no tie), and there is always one person who wins by a majority of the votes.
-
So instead of just keeping track of how the votes are compared, whether we can do it in A way that offsets it, let’s say that the votes are this way [A, A, B, A, B], where A is A vote for A, and let’s start traversing
-
List = [A], list = [A], list = [A], list = [A], list = [A], list = [A], list = [A,A], list = [A,A], list = [A,A], List = [A], end, list is left with A, indicating that A must be more than B, conversely, if only B is left, B wins.
-
Similarly, we have other competitors for this problem besides B, but we know that there must be A leader let’s say A, there must be more than half, and the rest goes to B, C, D, E… So the ones that cancel each other out are more likely to stay in the list, so we can also do this problem by different cancellations, same addition
-
Time O(n) Space O(1)
Writing implement
- Sorting pointer counting method
var majorityElement = function(nums) {
// Sort first so that the same elements are adjacent
nums = nums.sort((a, b) = > a - b)
// count is the current count of I
let [res, count, max] = [nums[0].1.1]
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i - 1]) {
count++
} else {
count = 1
}
// Calculate the count and Max comparison of the numbers in this round
if (max < count) {
res = nums[i]
max = count
}
}
return res
}
console.log(majorityElement([3.2.3])) / / 3
Copy the code- Offset method
var majorityElement = function(nums) {
let [majority, listLength] = [null.0]
for(item of nums) {
// The list is empty
if (listLength === 0) {
majority = item;
}
// If you are the same as the boss, join, if you are different, cancel
if (item === majority) {
listLength++;
} else{ listLength--; }}return majority;
};
console.log(majorityElement([6.5.5]))
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
reference
- 10X programmer work method