Posts published in January 2018

花花酱 LeetCode 264. Ugly Number II

By zxi on January 7, 2018

题目大意：让你找到第n个丑数。

Problem:

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

Solution:

C++ / O(n)

// Author: huahua

// Running time: 6 ms

class Solution {

public:

int nthUglyNumber(int n) {

static vector<int> nums{1};

static int i2 = 0;

static int i3 = 0;

static int i5 = 0;

while (nums.size() < n) {

const int next2 = nums[i2] * 2;

const int next3 = nums[i3] * 3;

const int next5 = nums[i5] * 5;

const int next = min(next2, min(next3, next5));

if (next == next2) ++i2;

if (next == next3) ++i3;

if (next == next5) ++i5;

nums.push_back(next);

}

return nums[n - 1];

}

};

C++ /query * O(NlogN)

// Author: Huahua

// Running time: 89 ms

class Solution {

public:

int nthUglyNumber(int n) {

vector<int> nums;

for (long a = 1; a <= INT_MAX; a *= 2)

for (long b = a; b <= INT_MAX; b *= 3)

for (long c = b; c <= INT_MAX; c *= 5)

nums.push_back(c);

std::sort(nums.begin(), nums.end());

return nums[n - 1];

}

};

C++ / static variables O(NlogN) + query*O(1)

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

int nthUglyNumber(int n) {

static vector<int> nums;

if (nums.empty()) {

for (long a = 1; a <= INT_MAX; a *= 2)

for (long b = a; b <= INT_MAX; b *= 3)

for (long c = b; c <= INT_MAX; c *= 5)

nums.push_back(c);

std::sort(nums.begin(), nums.end());

}

return nums[n - 1];

}

};

C++ / table O(1)
leetcode_264_table.cc

Solution 1: Simulation

Time complexity: O(V*n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

vector<int> pourWater(vector<int>& heights, int V, int K) {

while (V--) drop(heights, K);

return heights;

}

private:

void drop(vector<int>& heights, int K) {

int best = K;

for (int d = -1; d <= 1; d += 2) {

int i = K + d;

while (i >= 0 && i < heights.size()

&& heights[i] <= heights[i - d]) {

if (heights[i] < heights[best]) best = i;

i += d;

}

if (best != K) break;

}

++heights[best];

}

};

Java

// Author: Huahua

// Running time: 12 ms

class Solution {

public int[] pourWater(int[] heights, int V, int K) {

while (V-- > 0) {

dropWater(heights, K);

}

return heights;

}

private void dropWater(int[] heights, int K) {

int best = K;

for (int d = -1; d <= 1; d += 2) {

int i = K + d;

while (i >= 0 && i < heights.length && heights[i] <= heights[i - d]) {

if (heights[i] < heights[best]) best = i;

i += d;

}

if (best != K) break;

}

++heights[best];

}

Python3

"""

Author: Huahua

Running time: 207 ms

"""

class Solution:

def pourWater(self, heights, V, K):

def drop(h, K):

best = K

for d in (-1, 1):

i = K + d

while i >= 0 and i < len(h) and h[i] <= h[i - d]:

if h[i] < h[best]:

best = i

i += d

if best != K:

break

heights[best] += 1

for _ in range(V):

drop(heights, K)

return heights

花花酱 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

By zxi on January 6, 2018

题目大意：给你每天的股价，没有交易次数限制，但是卖出后要休息一天才能再买进。问你最大收益是多少？

Say you have an array for which the i^th 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) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]

maxProfit = 3

transactions = [buy, sell, cooldown, buy, sell]

Idea:

Solution:

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int maxProfit(vector<int>& prices) {

int sold = 0;

int rest = 0;

int hold = INT_MIN;

for (const int price : prices) {

int prev_sold = sold;

sold = hold + price;

hold = max(hold, rest - price);

rest = max(rest, prev_sold);

}

return max(rest, sold);

}

};

Related Problems:

花花酱 LeetCode 121. Best Time to Buy and Sell Stock

Posts published in January 2018

花花酱 LeetCode 264. Ugly Number II

Related Problems:

花花酱 LeetCode 263. Ugly Number

花花酱 LeetCode 167. Two Sum II – Input array is sorted

花花酱 LeetCode 755. Pour Water

Solution 1: Simulation

C++

Java

Python3

花花酱 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown