Posts published in September 2018

花花酱 LeetCode 16. 3Sum Closest

By zxi on September 19, 2018

Problem

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Solution: Sorting + Two Pointers

Similar to 花花酱 LeetCode 15. 3Sum

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua, 8 ms

class Solution {

public:

int threeSumClosest(vector<int> &num, int target) {

int n = num.size();

int d = INT_MAX;

int ans = target;

sort(num.begin(), num.end());

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

int s = i + 1, t = n - 1;

while (s < t) {

int sum = num[i] + num[s] + num[t];

if (sum == target)

return target;

int diff = abs(sum - target);

if (diff < d) {

d = diff;

ans = sum;

}

if (sum > target) --t;

else ++s;

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

public int threeSumClosest(int[] nums, int target) {

Arrays.sort(nums);

int n = nums.length;

int ans = 0;

int d = Integer.MAX_VALUE;

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

int s = i + 1;

int t = n - 1;

while (s < t) {

int sum = nums[i] + nums[s] + nums[t];

if (sum == target) return target;

int diff = Math.abs(sum - target);

if (diff < d) {

d = diff;

ans = sum;

}

if (sum > target) --t;

else ++s;

}

return ans;

}

Python3

# Author: Huahua

class Solution:

def threeSumClosest(self, nums, target):

nums.sort()

n = len(nums)

d = 2**32

ans = 0

for i in range(n - 2):

s, t = i + 1, n - 1

while s < t:

sum3 = nums[i] + nums[s] + nums[t]

if sum3 == target: return target

diff = abs(sum3 - target)

if diff < d: ans, d = sum3, diff

if sum3 > target:

t -= 1

else:

s += 1

return ans

花花酱 LeetCode 14. Longest Common Prefix

By zxi on September 19, 2018

Problem

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Solution: Brute Force

Time complexity: O(mk), where k the length of common prefix.

Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

string longestCommonPrefix(vector<string>& strs) {

if (strs.empty()) return "";

string ans;

for (int i = 0; i < strs[0].size(); ++i) {

for (const string& s : strs)

if (s.length() <= i || s[i] != strs[0][i]) return ans;

ans += strs[0][i];

}

return ans;

}

};

Java

Time complexity: (mk + k^2)

// Author: Huahua

class Solution {

public String longestCommonPrefix(String[] strs) {

if (strs.length == 0) return "";

String ans = new String();

for (int i = 0; i < strs[0].length(); ++i) {

char c = strs[0].charAt(i);

for (String s : strs)

if (s.length() <= i || s.charAt(i) != c) return ans;

ans += c;

}

return ans;

}

Python3

# Author: Huahua

class Solution:

def longestCommonPrefix(self, strs):

if not strs: return ""

ans = ""

for i in range(len(strs[0])):

for s in strs:

if len(s) <= i or s[i] != strs[0][i]: return ans

ans += strs[0][i]

return ans

花花酱 LeetCode 13. Roman to Integer

By zxi on September 19, 2018

Problem

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: C = 100, L = 50, XXX = 30 and III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Solution

accumulate the value of each letter.

If the value of current letter is greater than the previous one, deduct twice of the previous value.

e.g. IX, 1 + 10 – 2 * 1 = 9 instead of 1 + 10 = 11

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int romanToInt(string s) {

map<char, int> m{{'I', 1}, {'V', 5},

{'X', 10}, {'L', 50},

{'C', 100}, {'D', 500},

{'M', 1000}};

int ans = 0;

for (int i = 0; i < s.length(); i++) {

ans += m[s[i]];

if (i > 0 && m[s[i]] > m[s[i - 1]])

ans -= 2 * m[s[i - 1]];

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

private int v(char R) {

switch (R) {

case 'I' : return 1;

case 'V' : return 5;

case 'X' : return 10;

case 'L' : return 50;

case 'C' : return 100;

case 'D' : return 500;

case 'M' : return 1000;

default: break;

}

return 0;

}

public int romanToInt(String s) {

int ans = 0;

for (int i = 0; i < s.length(); i++) {

ans += v(s.charAt(i));

if ( i > 0 && v(s.charAt(i)) > v(s.charAt(i - 1)))

ans -= 2 * v(s.charAt(i - 1));

}

return ans;

}

Python3

class Solution:

def romanToInt(self, s):

m = {'I' : 1, 'V': 5, 'X': 10, 'L' : 50,

'C' : 100, 'D': 500, 'M': 1000}

ans = m[s[0]]

for c, p in zip(s[1:], s[0:-1]):

ans += m[c]

if m[c] > m[p]: ans -= 2 * m[p]

return ans

花花酱 LeetCode 223. Rectangle Area

By zxi on September 19, 2018

Problem

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Example:

Input: A = -3, B = 0, C = 3, D = 4, E = 0, F = -1, G = 9, H = 2
Output: 45

Note:

Assume that the total area is never beyond the maximum possible value of int.

Solution:

area1 + area2 – overlapped area

Time complexity: O(1)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {

int area1 = (C - A) * (D - B);

int area2 = (G - E) * (H - F);

int x1 = max(A, E);

int x2 = max(x1, min(C, G));

int y1 = max(B, F);

int y2 = max(y1, min(D, H));

return area1 + area2 - (x2 - x1) * (y2 - y1);

}

};

Java

// Author: Huahua

class Solution {

public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {

int area1 = (C - A) * (D - B);

int area2 = (G - E) * (H - F);

int x1 = Math.max(A, E);

int x2 = Math.max(x1, Math.min(C, G));

int y1 = Math.max(B, F);

int y2 = Math.max(y1, Math.min(D, H));

return area1 + area2 - (x2 - x1) * (y2 - y1);

}

Python3

# Author: Huahua

class Solution:

def computeArea(self, A, B, C, D, E, F, G, H):

area1 = (C - A) * (D - B);

area2 = (G - E) * (H - F);

x1 = max(A, E);

x2 = max(x1, min(C, G));

y1 = max(B, F);

y2 = max(y1, min(D, H));

return area1 + area2 - (x2 - x1) * (y2 - y1)

花花酱 Amortized Analysis 均摊分析 SP7

By zxi on September 17, 2018

Amortized Analysis

Amortized analysis can help us understand the actual cost of n operations on a data structure. Since some operations can be really fast e.g. O(1), but some operations can be really slow e.g. O(n). We could say the time complexity of that operation is O(n). However, it does not reflect the actual performance. And turns out, we can prove that certain operations have an amortized cost of O(1) while they can take O(n) in the worst case.

均摊分析可以帮助我们了解对一个数据结构进行n次操作的真实代价。对于相同的操作，有时候可以非常快，例如在O(1)时间内完成，而有时候则需要O(n)。我们当然可以说这个操作最坏情况下的时间复杂度是O(n)，但是这并不能真实反映它的实际复杂度。通过均摊分析，我们可以证明，尽管有些操作在最坏情况下是O(n)的时间复杂度，但是均摊下来只需要O(1)。

Dynamic Array

dynamic array doubles its size when it’s full which could take O(i) time where i is the number of elements in the array. Otherwise just store the element which only cost O(1). We can use aggregate method to compute the amortized cost of dynamic array.

动态数组在容量满时将容量翻翻，这一步需要O(i)时间，i是当前数组中的元素个数。如果没有满，只需要将元素存储下来即可，只需要花费O(1)时间。我们可以使用聚合法来计算均摊成本。

((1 + 1) + (1 + 2) + (1) + (1 + 4) + (1) + (1) + (1) + (1+8) + … + (1+n)) / n, assuming n is 2^k.

= (1 * n + (1 + 2 + 4 + 8 + … + n)) / n = (n + 2n – 1) / n = 3. O(1)

C++

#include <iostream>

#include <algorithm>

using namespace std;

class DynamicArray {

public:

DynamicArray() {

data_ = new int[1];

capcity_ = 1;

}

void add(int x) {

data_[size_++] = x;

++total_cost_;

if (size_ == capcity_) {

capcity_ *= 2;

total_cost_ += size_;

int* new_data = new int[capcity_];

copy(data_, data_ + size_, new_data);

swap(new_data, data_);

delete [] new_data;

}

int totalCost() const { return total_cost_; }

private:

int total_cost_ = 0;

int size_ = 0;

int capcity_;

int* data_;

};

int main() {

DynamicArray arr;

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

arr.add(i);

cout << i << " average cost: " << arr.totalCost() / static_cast<float>(i) << endl;

}

Output

1 average cost: 2

2 average cost: 2.5

3 average cost: 2

4 average cost: 2.75

5 average cost: 2.4

6 average cost: 2.16667

7 average cost: 2

8 average cost: 2.875

9 average cost: 2.66667

10 average cost: 2.5

11 average cost: 2.36364

12 average cost: 2.25

13 average cost: 2.15385

14 average cost: 2.07143

15 average cost: 2

16 average cost: 2.9375

[Finished in 0.4s]

Monotonic Stack

例子2: 单调栈

往单调栈push一个元素的时候，会删除上所有小于等于它的元素。这步操作在最优情况下是O(1)时间，如果它比栈顶元素要小。在最坏情况下是O(i)时间，栈上有i个元素，它比这i个元素都要大，所以一共要pop i次。

聚合法：

由于每个元素都会被push到栈上去1次，最多会被pop1次，所以总的操作数 <= 2n。 2n / n = 2 O(1)。

会计法：

每次push之前先存k块钱，k=2, 一块钱用于push自己，一块钱留着用于pop自己。

push的时候扣除1块钱，pop的时候再扣除1块钱。但不管怎样，我的账户上的钱永远>=0。这样我们可以说push的均摊成本是k=2。同样是O(1)，尽管它的worst case是O(n)。

C++

#include <iostream>

#include <algorithm>

#include <stack>

using namespace std;

class MonotonicStack {

public:

void push(int x) {

while (!data_.empty() && x > data_.top()) {

this->pop();

}

++total_cost_;

data_.push(x);

}

int pop() {

++total_cost_;

int t = data_.top();

data_.pop();

return t;

}

int totalCost() const { return total_cost_; }

private:

int total_cost_ = 0;

stack<int> data_;

};

int main() {

srand(1);

MonotonicStack s;

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

s.push(rand());

cout << i << " average cost: " << s.totalCost() / static_cast<float>(i) << endl;

}

Output

1 average cost: 1

2 average cost: 1.5

3 average cost: 1.66667

4 average cost: 1.5

5 average cost: 1.6

6 average cost: 1.5

7 average cost: 1.42857

8 average cost: 1.75

9 average cost: 1.77778

10 average cost: 1.9

11 average cost: 1.81818

12 average cost: 1.83333

13 average cost: 1.84615

14 average cost: 1.78571

15 average cost: 1.8

16 average cost: 1.8125

17 average cost: 1.82353

18 average cost: 1.77778

19 average cost: 1.78947

20 average cost: 1.75

21 average cost: 1.80952

22 average cost: 1.86364

23 average cost: 1.82609

24 average cost: 1.91667

25 average cost: 1.88

26 average cost: 1.84615

27 average cost: 1.81481

28 average cost: 1.85714

29 average cost: 1.82759

30 average cost: 1.86667

31 average cost: 1.90323

32 average cost: 1.875

[Finished in 0.5s]

Posts published in September 2018

花花酱 LeetCode 16. 3Sum Closest

Problem

Solution: Sorting + Two Pointers

C++

Java

Python3

花花酱 LeetCode 14. Longest Common Prefix

Problem

Solution: Brute Force

C++

Java

Python3

花花酱 LeetCode 13. Roman to Integer

Problem

Solution

C++

Java

Python3

花花酱 LeetCode 223. Rectangle Area

Problem

Solution:

C++

Java

Python3

花花酱 Amortized Analysis 均摊分析 SP7

Amortized Analysis

Dynamic Array

C++

Output

Monotonic Stack

C++

Output

Related Problem