LeetCode OJ – 第44页 – 柳婼の blog

LeetCode 204. 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:

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?

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?

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?

class Solution {
public:
    int countPrimes(int n) {
        vector<int> book(n, 1);
        for(int i = 2; i * i < n; i++) {
            if(book[i] == 1)
                for(int j = i * i; j < n; j = j + i)
                    book[j] = 0;
        }
        int cnt = 0;
        for(int i = 2; i < n; i++) {
            if(book[i] == 1)
                cnt++;
        }
        return cnt;
    }
};

class Solution {

public:

int countPrimes(int n) {

vector<int> book(n, 1);

for(int i = 2; i * i < n; i++) {

if(book[i] == 1)

for(int j = i * i; j < n; j = j + i)

book[j] = 0;

}

int cnt = 0;

for(int i = 2; i < n; i++) {

if(book[i] == 1)

cnt++;

}

return cnt;

}

};

LeetCode 238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> v(nums.size());
        int right = 1;
        v[0] = 1;
        //左边所有数字的乘积
        for(int i = 1; i < nums.size(); i++) {
           v[i] = nums[i - 1] * v[i - 1]; 
        }
        for(int i = nums.size() - 2; i >= 0; i--) {
            right = right * nums[i + 1];
            v[i] = v[i] * right;
        }
        return v;
    }
};

class Solution {

public:

vector<int> productExceptSelf(vector<int>& nums) {

vector<int> v(nums.size());

int right = 1;

v[0] = 1;

//左边所有数字的乘积

for(int i = 1; i < nums.size(); i++) {

v[i] = nums[i - 1] * v[i - 1];

}

for(int i = nums.size() - 2; i >= 0; i--) {

right = right * nums[i + 1];

v[i] = v[i] * right;

}

return v;

}

};

LeetCode 121. Best Time to Buy and Sell Stock

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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minvalue = 99999999;
        int ans = 0;
        for(int i = 0; i < prices.size(); i++) {
            if(minvalue > prices[i]) {
                minvalue = prices[i];
            }
            prices[i] = prices[i] - minvalue;
            if(ans < prices[i]) {
                ans = prices[i];
            }
        }
        return ans;
    }
};

class Solution {

public:

int maxProfit(vector<int>& prices) {

int minvalue = 99999999;

int ans = 0;

for(int i = 0; i < prices.size(); i++) {

if(minvalue > prices[i]) {

minvalue = prices[i];

}

prices[i] = prices[i] - minvalue;

if(ans < prices[i]) {

ans = prices[i];

}

return ans;

}

};

LeetCode 122. Best Time to Buy and Sell Stock II

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 (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

分析：贪心算法，在每一小段上升序列中最大差值累加得到结果。就是说在股票价格处于上升期的时候，在最低点买入，在最高点卖出。而且可知，每一小段的最大差值就是这段序列的最后一个点的价格减去这段序列第一个点的价格，与每一次从第一个点与第二点的差值一直累加所得结果相同：ans += prices[i] – prices[i – 1];

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 1; i < prices.size(); i++) {
            if(prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
};

class Solution {

public:

int maxProfit(vector<int>& prices) {

int ans = 0;

for(int i = 1; i < prices.size(); i++) {

if(prices[i] > prices[i - 1])

ans += prices[i] - prices[i - 1];

}

return ans;

}

};

LeetCode 1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> v(2);
        for(int i = 0; i < nums.size(); i++) {
            for(int j = i + 1; j < nums.size(); j++) {
                if(nums[i] + nums[j] == target) {
                    v[0] = i;
                    v[1] = j;
                }
            }
        }
        return v;
    }
};

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

vector<int> v(2);

for(int i = 0; i < nums.size(); i++) {

for(int j = i + 1; j < nums.size(); j++) {

if(nums[i] + nums[j] == target) {

v[0] = i;

v[1] = j;

}

return v;

}

};

LeetCode 2. Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *h = new ListNode(0);
        ListNode *p = h;
        int temp = 0;
        while(l1 != NULL && l2 != NULL) {
            p->next = new ListNode((temp + l1->val + l2->val) % 10);
            temp = (temp + l1->val + l2->val) / 10;
            p = p->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        while(l1 != NULL) {
            p->next = new ListNode((temp + l1->val) % 10);
            temp = (temp + l1->val) / 10;
            p = p->next;
            l1 = l1->next;
        }
        while(l2 != NULL) {
            p->next = new ListNode((temp + l2->val) % 10);
            temp = (temp + l2->val) / 10;
            p = p->next;
            l2 = l2->next;
        }
        if(temp) {
            p->next = new ListNode(1);
        }
        return h->next;
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

ListNode *h = new ListNode(0);

ListNode *p = h;

int temp = 0;

while(l1 != NULL && l2 != NULL) {

p->next = new ListNode((temp + l1->val + l2->val) % 10);

temp = (temp + l1->val + l2->val) / 10;

p = p->next;

l1 = l1->next;

l2 = l2->next;

}

while(l1 != NULL) {

p->next = new ListNode((temp + l1->val) % 10);

temp = (temp + l1->val) / 10;

p = p->next;

l1 = l1->next;

}

while(l2 != NULL) {

p->next = new ListNode((temp + l2->val) % 10);

temp = (temp + l2->val) / 10;

p = p->next;

l2 = l2->next;

}

if(temp) {

p->next = new ListNode(1);

}

return h->next;

}

};