# LeetCode Solution(Easy.61-64)

## c/c++，python，for work

Views:  times Posted by elmagnifico on December 16, 2015

## 61.Count Primes

Description:

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

Credits:

Special thanks to @mithmatt for adding this problem and creating all test cases.

Hint:

1.Let’s start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n. The runtime complexity of isPrime function would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better?

2.As we know the number must not be divisible by any number > n / 2, we can immediately cut the total iterations half by dividing only up to n / 2. Could we still do better?

3.Let’s write down all of 12’s factors:

2 × 6 = 12
3 × 4 = 12
4 × 3 = 12
6 × 2 = 12


As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n.

Our total runtime has now improved to O(n1.5), which is slightly better. Is there a faster approach?

public int countPrimes(int n) {
int count = 0;
for (int i = 1; i < n; i++) {
if (isPrime(i)) count++;
}
return count;
}

private boolean isPrime(int num) {
if (num <= 1) return false;
// Loop's ending condition is i * i <= num instead of i <= sqrt(num)
// to avoid repeatedly calling an expensive function sqrt().
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}


4.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.

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?

5.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?

6.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?

7.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?

8.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.

The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n). For the more mathematically inclined readers, you can read more about its algorithm complexity on Wikipedia.

public int countPrimes(int n) {
boolean[] isPrime = new boolean[n];
for (int i = 2; i < n; i++) {
isPrime[i] = true;
}
// Loop's ending condition is i * i < n instead of i < sqrt(n)
// to avoid repeatedly calling an expensive function sqrt().
for (int i = 2; i * i < n; i++) {
if (!isPrime[i]) continue;
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) count++;
}
return count;
}


### 61.Count Primes-Solution-C/C++

class Solution {
public:
int countPrimes(int n)
{
vector<int> num;
if(n<2)
return 0;
num.push_back(2);
int i=3,j=2;
for(i=3;i<n;i++)
{
for(j=1;j<=sqrt(i);j++)
{
if(i%(j+1)==0)
break;
else
{
if(j+1>=sqrt(i))
{
num.push_back(i);
}
}
}
}
return num.size();

}
};


class Solution {
public:
int countPrimes(int n) {
bool num[n];
int i=0,j=0;
for(i=2;i<n;i++)
{
num[i]=true;
}
for(i=2;i*i<n;i++)
{
if(num[i]==false)
continue;
for(j=i*i;j<n;j=j+i)
{
num[j]=false;
}
}
int count=0;
for(i=2;i<n;i++)
{
if(num[i]==true)
count++;
}

return count;
}
};


### 61.Count Primes-Solution-Python

python的代码竟然用了1600ms 而上面的C++采用了56ms 而且leetcode的python有bug 时而提示能通过时而提示超时

class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
num=[]
for i in range(n):
num.append(True)
i=2
while i*i<n:
if num[i]==False:
i=i+1
continue
j=i*i
while j<n:
num[j]=False
j=j+i
i=i+1
count=0
for i in range(2,n):
if num[i]==True:
count=count+1
return count


## 62.Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return [“0->2”,”4->5”,”7”].

### 62.Summary Ranges-Solution-C/C++

class Solution
{
public:
vector<string> summaryRanges(vector<int>& nums)
{
if(nums.size()==0)
return (vector<string>)0;
int i=0;
string sline="";
stringstream s;
vector<int>line;
vector<string> ret;
for(i=0;i<nums.size();i++)
{
if(line.size()==0)
{
line.push_back(nums[i]);
}
else if(line.size()==1)
{
if((nums[i]-line[0])==1)
line.push_back(nums[i]);
else
{
//不相同的情况下，把第一个值加入到返回区中
s<<line[0];
s>>sline;
s.clear();
line.clear();
line.push_back(nums[i]);
ret.push_back(sline);
}
}
else
{
if((nums[i]-line[1])==1)
line[1]=nums[i];
else
{
//不相同的情况下，两个值加入到返回区中
s<<line[0]<<"->"<<line[1];
s>>sline;
s.clear();
line.clear();
line.push_back(nums[i]);
ret.push_back(sline);
}
}
}
if(line.size()==1)
s<<line[0];
else
s<<line[0]<<"->"<<line[1];
s>>sline;
s.clear();
ret.push_back(sline);
return ret;
}
};


### 62.Summary Ranges-Solution-Python

class Solution(object):
def summaryRanges(self, nums):
"""
:type nums: List[int]
:rtype: List[str]
"""
if nums==[]:
return []
ret=[]
line=[]
for i in range(len(nums)):
if len(line)==0:
#当前层没有数据，那么就加入
line.append(nums[i])
elif len(line)==1:
if (nums[i]-line[0])==1:
#当前层有一个数据，判断新数据是否连续
line.append(nums[i])
else:
#数据不连续,加入到返回区
ret.append(line)
#新数据入行
line=[]
line.append(nums[i])
elif len(line)==2:
if (nums[i]-line[1])==1:
#当前层有一个数据，判断新数据是否连续
line[1]=nums[i]
else:
#数据不连续,加入到返回区
ret.append(line)
#新数据入行
line=[]
line.append(nums[i])
ret.append(line)
s=''
sret=[]
for i in range(len(ret)):
if len(ret[i])==1:
s=str(ret[i][0])
sret.append(s)
else:
s=str(ret[i][0])+"->"+str(ret[i][1])
#+"->"+''.join(ret[i][1])
sret.append(s)
return sret


You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

// Forward declaration of isBadVersion API.

class Solution {
public:
{

//二分法查找
int low=1,high=n,mid=low+(high-low)/2;
while(low<high)
{
{
high=mid;

}
else
{
low=mid+1;
}
mid=low+(high-low)/2;//防止越界
}
return mid;
}
};


# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool

class Solution(object):
"""
:type n: int
:rtype: int
"""
low=1
high=n
mid=low+(high-low)/2
while low<high:
high=mid
else:
low=mid+1
mid=low+(high-low)/2
return mid


## 64.Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) – Push element x onto stack.
• pop() – Removes the element on top of the stack.
• top() – Get the top element.
• getMin() – Retrieve the minimum element in the stack.

### 64.Min Stack-Analysis

标准栈 3 11 3 9 0 9 0



### 64.Min Stack-Solution-C/C++

class MinStack
{
public:
stack<int> sd;
stack<int> min;
void push(int x)
{
sd.push(x);
if(min.size()==0||x<=min.top())
min.push(x);
}

void pop()
{
if(min.top()==sd.top())
min.pop();
sd.pop();
}

int top()
{
return sd.top();
}

int getMin()
{
return min.top()<sd.top()?min.top():sd.top();
}
};


### 64.Min Stack-Solution-Python

class MinStack(object):
def __init__(self):
"""
"""
self.minstack=[]
self.sdstack=[]

def push(self, x):
"""
:type x: int
:rtype: nothing
"""
for i in range(len(self.minstack)):
if x>self.minstack[len(self.minstack)-1-i]:
self.minstack.insert(len(self.minstack)-i,x)
if len(self.minstack)==0:
self.minstack.append(x)
self.sdstack.append(x)

def pop(self):
"""
:rtype: nothing
"""
x=self.sdstack[-1]
del self.sdstack[-1]
for i in range(len(self.minstack)):
if x==self.minstack[i]:
del self.minstack[i]
break;

def top(self):
"""
:rtype: int
"""
return self.sdstack[-1]

def getMin(self):
"""
:rtype: int
"""
if len(self.minstack)!=0:
return self.minstack[0]
else:
return None


class MinStack(object):
def __init__(self):
"""
"""
self.minstack=[]
self.sdstack=[]

def push(self, x):
"""
:type x: int
:rtype: nothing
"""
if len(self.minstack)==0:
self.minstack.append(x)
elif x<=self.minstack[-1]:
self.minstack.append(x)
self.sdstack.append(x)

def pop(self):
"""
:rtype: nothing
"""
x=self.sdstack[-1]
del self.sdstack[-1]
if len(self.minstack)>0 and x==self.minstack[-1]:
del self.minstack[-1]

def top(self):
"""
:rtype: int
"""
return self.sdstack[-1]

def getMin(self):
"""
:rtype: int
"""
if len(self.minstack)!=0:
return min(self.minstack[-1],self.sdstack[-1])
else:
return 0


## Quote

http://blog.csdn.net/xudli/article/details/48286081

http://my.oschina.net/Tsybius2014/blog/505462

http://m.shangxueba.com/jingyan/2926615.html

http://www.cnblogs.com/x1957/p/4086448.html