花花酱 LeetCode 800. Simple RGB Color

By zxi on March 17, 2018

Problem

In the following, every capital letter represents some hexadecimal digit from 0 to f.

The red-green-blue color "#AABBCC" can be written as "#ABC" in shorthand. For example, "#15c" is shorthand for the color "#1155cc".

Now, say the similarity between two colors "#ABCDEF" and "#UVWXYZ" is -(AB - UV)^2 - (CD - WX)^2 - (EF - YZ)^2.

Given the color "#ABCDEF", return a 7 character color that is most similar to #ABCDEF, and has a shorthand (that is, it can be represented as some "#XYZ"

Example 1:
Input: color = "#09f166"
Output: "#11ee66"
Explanation:  
The similarity is -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73.
This is the highest among any shorthand color.

Note:

color is a string of length 7.
color is a valid RGB color: for i > 0, color[i] is a hexadecimal digit from 0 to f
Any answer which has the same (highest) similarity as the best answer will be accepted.
All inputs and outputs should use lowercase letters, and the output is 7 characters.

Solution: Brute Force

R, G, B are independent, find the closest color for each channel separately.

Time complexity: O(3 * 16)

Space complexity: O(1)

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

string similarRGB(string color) {

const string hex{"0123456789abcdef"};

vector<int> rgb(3, 0);

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

rgb[i] = hex.find(color[2 * i + 1]) * 16 + hex.find(color[2 * i + 2]);

string ans(7, '#');

for (int i = 0; i < 3; ++i) {

int best = INT_MAX;

for (int j = 0; j < 16; ++j) {

int diff = abs(j * 16 + j - rgb[i]);

if (diff >= best) continue;

best = diff;

ans[2 * i + 1] = ans[2 * i + 2] = hex[j];

}

return ans;

}

};

Problem

Given two non-negative integers 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: Brute Force

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

string addStrings(string num1, string num2) {

if (num1.length() < num2.length()) swap(num1, num2);

num1 = "0" + num1;

int l1 = num1.length();

int l2 = num2.length();

for (int i = 0; i < l1 - 1; ++i) {

if (i < l2) num1[l1 - i - 1] += (num2[l2 - i - 1] - '0');

if (num1[l1 - i - 1] > '9') {

num1[l1 - i - 1] -= 10;

++num1[l1 - i - 2];

}

return (num1[0] != '0') ? num1 : num1.substr(1);

}

};

花花酱 LeetCode 414. Third Maximum Number

By zxi on March 17, 2018

Problem

https://leetcode.com/problems/third-maximum-number/description/

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

Solution: Set

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int thirdMax(vector<int>& nums) {

set<int> s;

for (int num : nums) {

s.insert(num);

if (s.size() > 3) s.erase(s.begin());

}

return s.size() != 3 ? *s.rbegin() : *s.begin();

}

};

Python3

"""

Author: Huahua

Running time: 52 ms

"""

class Solution:

def thirdMax(self, nums):

s = set()

for num in nums:

s.add(num)

if len(s) > 3: s.remove(min(s))

return min(s) if len(s) == 3 else max(s)

花花酱 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);

Posts tagged as “easy”

花花酱 LeetCode 800. Simple RGB Color

Problem

Note:

Solution: Brute Force

花花酱 LeetCode 415. Add Strings

Problem

Solution: Brute Force

花花酱 LeetCode 414. Third Maximum Number

Problem

Solution: Set

花花酱 LeetCode 401. Binary Watch

Problem:

Solution 1:

花花酱 LeetCode 383. Ransom Note

Posts tagged as “easy”

花花酱 LeetCode 800. Simple RGB Color

Problem

Note:

Solution: Brute Force

花花酱 LeetCode 415. Add Strings

Problem

Solution: Brute Force

花花酱 LeetCode 414. Third Maximum Number

Problem

Solution: Set

花花酱 LeetCode 401. Binary Watch

Problem:

<img src="https://upload.wikimedia.org/wikipedia/commons/8/8b/Binary_clock_samui_moon.jpg" height="300"/>

Solution 1:

花花酱 LeetCode 383. Ransom Note