It's the Xinrui Ma

Blog

Tag: Math

204. Count Primes

Posted by in LeetCode on

Count the number of prime numbers less than a non-negative number, n.

Example:

Key idea is to constructure an array, which at array[i], indicate number i is prime or not.
1. We init the array, and assume all the numbers are prime at first.
2. We start from i = 2, loop through 2 to n
3. Inside every loop, we set the mutiple of i (represent as J) to false. we can set J at j = i * i;

The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n. But don’t let that name scare you, I promise that the concept is surprisingly simple.


Sieve of Eratosthenes: algorithm steps for primes below 121. “Sieve of Eratosthenes Animation” by SKopp is licensed under CC BY 2.0.

We start off with a table of n numbers. Let’s look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, … must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. What does this tell you? Should you mark off all multiples of 4 as well?

4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible by 2 and were already marked off. So we can skip 4 immediately and go to the next number, 5. Now, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, … can be marked off. There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off?

In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, … Now what should be the terminating loop condition?

It is easy to say that the terminating loop condition is p < n, which is certainly correct but not efficient. Do you still remember Hint #3? Yes, the terminating loop condition can be p < √n, as all non-primes ≥ √n must have already been marked off. When the loop terminates, all the numbers in the table that are non-marked are prime. Solution 1:

Solution 2:

122. Best Time to Buy and Sell Stock II

Posted by in LeetCode on

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Example 2:

Example 3:


 Solution:
A simple one, just add every possible gain in these days, you will have your profit maximum.
Proof: If you buy at Day 1 and hold to sell until Day 3, your profit will be Profit 3
If you buy at Day 1 and sell at day 2, and buy at day 2 and sell at day 3, your profit will be Profit 1 + Profit 2
Profit 1 + Profit 2 > Profit 3
Answer in JavaScript:

 

121. Best Time to Buy and Sell Stock

Posted by in LeetCode on

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Solution:

Think in your head a line, one end of the line is the lowest price, the other end is the highest price, the length of this line is profi. Find every lowest point of stock price, and compute the profit in the following days, if they find another lowest price, change the lowest price to the new value and calculate the maxprofit based on that, loop through the array, compare the maxProfit you find, return the max one.

Why you should change the lowest price and then calcuate the maxProfit? Because the maxProfit by nautre, could comes from the lowest price of stack,you can prove this by drawing a picutre….

Trust me, draw a picture, you will understand…

 

Solution in JavaScript:

476. Number Complement

Posted by in LeetCode on

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:
The given integer is guaranteed to fit within the range of a 32-bit signed integer.
You could assume no leading zero bit in the integer’s binary representation.
Example 1:
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

415. Add Strings — LeetCode

Posted by in LeetCode on

Given two non-negative numbers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

The length of both num1 and num2 is < 5100. Both num1 and num2 contains only digits 0-9. Both num1 and num2 does not contain any leading zero. You must not use any built-in BigInteger library or convert the inputs to integer directly. Solution: Very similar to the add linked list together, from the very end of the string ,add them together, check when one of the string is count to the beginning, and then append the rest to the beginning of the result string. Nothing much to say.

171. Excel Sheet Column Number My Submissions Question

Posted by in LeetCode on

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

Solution in Java: