花花酱 LeetCode 801. Minimum Swaps To Make Sequences Increasing

By zxi on March 17, 2018

Problem

题目大意：给你两个数组A, B。问最少需要多少次对应位置元素的交换才能使得A和B变成单调递增。

https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/description/

We have two integer sequences A and B of the same non-zero length.

We are allowed to swap elements A[i] and B[i]. Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, A and B are both strictly increasing. (A sequence is strictly increasing if and only if A[0] < A[1] < A[2] < ... < A[A.length - 1].)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing. It is guaranteed that the given input always makes it possible.

Example:
Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1
Explanation: 
Swap A[3] and B[3].  Then the sequences are:
A = [1, 3, 5, 7] and B = [1, 2, 3, 4]
which are both strictly increasing.

Note:

A, B are arrays with the same length, and that length will be in the range [1, 1000].
A[i], B[i] are integer values in the range [0, 2000].

Solution: Search/DFS (TLE)

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: TLE 84/102 test cases passed.

class Solution {

public:

int minSwap(vector<int>& A, vector<int>& B) {

int ans = INT_MAX;

dfs(A, B, 0, 0, ans);

return ans;

}

private:

void dfs(vector<int>& A, vector<int>& B, int i, int c, int& ans) {

if (c >= ans) return;

if (i == A.size()) {

ans = min(ans, c);

return;

}

if (i == 0 || A[i] > A[i - 1] && B[i] > B[i - 1])

dfs(A, B, i + 1, c, ans);

if (i == 0 || A[i] > B[i - 1] && B[i] > A[i - 1]) {

swap(A[i], B[i]);

dfs(A, B, i + 1, c + 1, ans);

swap(A[i], B[i]);

}

};

Solution: DP

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int minSwap(vector<int>& A, vector<int>& B) {

const int n = A.size();

vector<int> keep(n, INT_MAX);

vector<int> swap(n, INT_MAX);

keep[0] = 0;

swap[0] = 1;

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

if (A[i] > A[i - 1] && B[i] > B[i - 1]) {

// Good case, no swapping needed.

keep[i] = keep[i - 1];

// Swapped A[i - 1] / B[i - 1], swap A[i], B[i] as well

swap[i] = swap[i - 1] + 1;

}

if (B[i] > A[i - 1] && A[i] > B[i - 1]) {

// A[i - 1] / B[i - 1] weren't swapped.

swap[i] = min(swap[i], keep[i - 1] + 1);

// Swapped A[i - 1] / B[i - 1], no swap needed for A[i] / B[i]

keep[i] = min(keep[i], swap[i - 1]);

}

return min(keep.back(), swap.back());

}

};

Python3

"""

Author: Huahua

Running time: 60 ms

"""

class Solution:

def minSwap(self, A, B):

n = len(A)

dp = [[float('inf'), float('inf')] for _ in range(n)]

dp[0][0], dp[0][1] = 0, 1

for i in range(1, n):

if A[i] > A[i - 1] and B[i] > B[i - 1]:

dp[i][0] = dp[i - 1][0]

dp[i][1] = dp[i - 1][1] + 1

if B[i] > A[i - 1] and A[i] > B[i - 1]:

dp[i][0] = min(dp[i][0], dp[i - 1][1])

dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1)

return min(dp[-1])

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

}

};

花花酱 LeetCode 415. Add Strings

By zxi on March 17, 2018

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 413. Arithmetic Slices

By zxi on March 17, 2018

题目大意：返回所有子数组中等差数列的个数。

Problem

https://leetcode.com/problems/arithmetic-slices/description/

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q – 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

Solution 0: Reduction

Reduce the problem to # of all 1 sub arrays.

B[i – 2] = is_slice(A[i], A[i+1], A[i+2])

Time Complexity: O(n)

Space Complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numberOfArithmeticSlices(vector<int>& A) {

if (A.size() < 3) return 0;

vector<int> B(A.size() - 2, 0);

for (int i = 2; i < A.size() ; ++i) {

if (A[i - 1] - A[i - 2] == A[i] - A[i - 1])

B[i - 2] = 1;

}

return all1SubArrays(B);

}

private:

// return number of arrays whose values are all ones.

int all1SubArrays(const vector<int>& A) {

int sum = 0;

int curr = 0;

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

if (A[i]) sum += ++curr;

else curr = 0;

return sum;

}

};

Solution 1: Combined

C++

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numberOfArithmeticSlices(vector<int>& A) {

int sum = 0;

int curr = 0;

for (int i = 2; i < A.size() ; ++i) {

if (A[i - 1] - A[i - 2] == A[i] - A[i - 1]) {

sum += ++curr;

} else {

curr = 0;

}

return sum;

}

};

Huahua's Tech Road

花花酱 LeetCode 801. Minimum Swaps To Make Sequences Increasing

Problem

Solution: Search/DFS (TLE)

C++

Solution: DP

C++

Python3

花花酱 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 413. Arithmetic Slices

Problem

Example:

Solution 0: Reduction

Solution 1: Combined

Related Problems: