花花酱 LeetCode 401. Binary Watch

By zxi on March 17, 2018

Problem:

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

The order of output does not matter.
The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

Solution 1:

Time complexity: O(11*59*n)

C++

// Author: Huahua

// Running time: 2 ms (beats 100%)

class Solution {

public:

vector<string> readBinaryWatch(int num) {

vector<string> ans;

for (int i = 0; i <= num; ++i)

for (int h : nums(i, 12))

for (int m : nums(num - i, 60))

ans.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));

return ans;

}

private:

// Return numbers in [0,r) that has b 1s in their binary format.

vector<int> nums(int b, int r) {

vector<int> ans;

for (int n = 0; n < r; ++n)

if (__builtin_popcount(n) == b) ans.push_back(n);

return ans;

}

};

花花酱 LeetCode 383. Ransom Note

By zxi on March 15, 2018

题目大意：给你一个字符串，问能否用它其中的字符组成另外一个字符串，每个字符只能使用一次。

Problem:

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

Solution: HashTable

Time complexity: O(n + m)

Space complexity: O(128)

C++

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

bool canConstruct(string ransomNote, string magazine) {

vector<int> counts(128, 0);

for (const char c : magazine)

++counts[c];

for (const char c : ransomNote)

if (--counts[c] < 0) return false;

return true;

}

};

// Author: Huahua

// Running time: 9 ms (beats 100%)

static int x=[](){

std::ios::sync_with_stdio(false);

cin.tie(NULL);

return 0;

}();

class Solution {

public:

bool canConstruct(const string& ransomNote, const string& magazine) {

vector<int> counts(128, 0);

for (const char c : magazine)

++counts[c];

for (const char c : ransomNote)

if (--counts[c] < 0) return false;

return true;

}

};

Python3

"""

Author: Huahua

Running time: 64 ms

"""

class Solution:

def canConstruct(self, ransomNote, magazine):

return not collections.Counter(ransomNote) - collections.Counter(magazine);

花花酱 LeetCode 278. First Bad Version

By zxi on March 15, 2018

题目大意：给你一个API查询版本是否坏了，让你找出第一个坏掉的版本。

Problem:

https://leetcode.com/problems/first-bad-version/description/

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.

Solution 1: Brute Force

Time Complexity: O(n) TLE

Space Complexity: O(1)

Solution 2: Binary Search

Time Complexity: O(logn)

Space Complexity: O(1)

// Forward declaration of isBadVersion API.

bool isBadVersion(int version);

// Author: Huahua

// Running time: 2 ms

class Solution {

public:

int firstBadVersion(int n) {

int l = 1;

int r = n;

while (l < r) {

int m = l + (r - l) / 2;

if (isBadVersion(m))

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 225. Implement Stack using Queues

By zxi on March 13, 2018

题目大意：用队列来实现栈。

Problem:

https://leetcode.com/problems/implement-stack-using-queues/description/

Implement the following operations of a stack using queues.

push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
empty() — Return whether the stack is empty.

Notes:

You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Idea:

Using a single queue, for every push, shift the queue (n – 1) times such that the last element becomes the first element in the queue.

e.g.

push(1): q: [1]

push(2): q: [1, 2] -> [2, 1]

push(3): q: [2, 1, 3] -> [1, 3, 2] -> [3, 2, 1]

push(4): q: [3, 2, 1, 4] -> [2, 1, 4, 3] -> [1, 4, 3, 2] -> [4, 3, 2, 1]

Solution:

Time complexity:

Push: O(n)

Pop/top/empty: O(1)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 3 ms

class MyStack {

public:

/** Initialize your data structure here. */

MyStack() {}

/** Push element x onto stack. */

void push(int x) {

q_.push(x);

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

q_.push(q_.front());

q_.pop();

}

/** Removes the element on top of the stack and returns that element. */

int pop() {

int top = q_.front();

q_.pop();

return top;

}

/** Get the top element. */

int top() {

return q_.front();

}

/** Returns whether the stack is empty. */

bool empty() {

return q_.empty();

}

private:

queue<int> q_;

};

Posts tagged as “easy”

花花酱 LeetCode 401. Binary Watch

Problem:

Solution 1:

花花酱 LeetCode 383. Ransom Note

花花酱 LeetCode 278. First Bad Version

花花酱 LeetCode 203. Remove Linked List Elements

花花酱 LeetCode 225. Implement Stack using Queues