Huahua’s Tech Road

C++ 11 Smart Pointers 智能指针

By zxi on June 10, 2020

Example code

C++

// Author: Huahua

#include <iostream>

#include <memory>

class Entity {

public:

Entity() { puts("Entity created!"); }

~Entity() { puts("Entity destroyed!"); }

};

void ex1() {

puts("--------");

puts("Entering ex1");

{

puts("Entering ex1::scope1");

auto e1 = std::make_unique<Entity>();

puts("Leaving ex1::scope1");

}

puts("Leaving ex1");

}

void foo(std::unique_ptr<Entity>) {

puts("Entering foo");

puts("Leaving foo");

}

void ex2() {

puts("--------");

puts("Entering ex2");

auto e1 = std::make_unique<Entity>();

foo(std::move(e1));

// e1 was destoried.

puts("Leaving ex2");

}

void ex3() {

puts("--------");

puts("Entering ex3");

auto e1 = std::make_shared<Entity>();

std::cout << e1.use_count() << std::endl;

{

puts("Entering ex3::scope1");

auto e2 = e1; // use_count ++

std::cout << e1.use_count() << std::endl;

auto e3 = std::move(e2); // use_count remains

std::cout << e1.use_count() << std::endl;

puts("Leaving ex3::scope1");

}

std::cout << e1.use_count() << std::endl;

puts("Leaving ex3");

}

void observe(std::weak_ptr<Entity> ew) {

if (std::shared_ptr<Entity> spt = ew.lock()) {

std::cout << spt.use_count() << std::endl;

std::cout << "entity still alive!" << std::endl;

} else {

std::cout << "entity was expired :(" << std::endl;

}

void ex4() {

puts("--------");

puts("Entering ex4");

std::weak_ptr<Entity> ew;

{

puts("Entering ex4::scope1");

auto e1 = std::make_shared<Entity>();

std::cout << e1.use_count() << std::endl;

ew = e1; // use_count remains

std::cout << e1.use_count() << std::endl;

observe(ew);

puts("Leaving ex4::scope1");

}

observe(ew);

puts("Leaving ex4");

}

int main(int argc, char** argv) {

ex1();

ex2();

ex3();

ex4();

return 0;

}

Output

--------

Entering ex1

Entering ex1::scope1

Entity created!

Leaving ex1::scope1

Entity destroyed!

Leaving ex1

--------

Entering ex2

Entity created!

Entering foo

Leaving foo

Entity destroyed!

Leaving ex2

--------

Entering ex3

Entity created!

Entering ex3::scope1

Leaving ex3::scope1

Leaving ex3

Entity destroyed!

--------

Entering ex4

Entering ex4::scope1

Entity created!

entity still alive!

Leaving ex4::scope1

Entity destroyed!

entity was expired :(

Leaving ex4

花花酱 LeetCode 1473. Paint House III

By zxi on June 7, 2020

There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that has been painted last summer should not be painted again.

A neighborhood is a maximal group of continuous houses that are painted with the same color. (For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods [{1}, {2,2}, {3,3}, {2}, {1,1}]).

Given an array houses, an m * n matrix cost and an integer target where:

houses[i]: is the color of the house i, 0 if the house is not painted yet.
cost[i][j]: is the cost of paint the house i with the color j+1.

Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods, if not possible return -1.

Example 1:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

Example 2:

Input: houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 11
Explanation: Some houses are already painted, Paint the houses of this way [2,2,1,2,2]
This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}]. 
Cost of paint the first and last house (10 + 1) = 11.

Example 3:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
Output: 5

Example 4:

Input: houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
Output: -1
Explanation: Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.

Constraints:

m == houses.length == cost.length
n == cost[i].length
1 <= m <= 100
1 <= n <= 20
1 <= target <= m
0 <= houses[i] <= n
1 <= cost[i][j] <= 10^4

Solution: DP

dp[k][i][c] := min cost to form k neighbors with first i houses and i-th house is in color c.

dp[k][i][c] := min{dp[k-(c != cj)][j][cj] for cj in 1..n} + 0 if houses[i] == c else cost[i][c]

init: dp[0][0][*] = 0 otherwise inf
ans = min(dp[target][m])

Time complexity: O(T*M*N^2)
Space complexity: O(T*M*N) -> O(M*N)

C++

// Author: Huahua

// Author: Huahua， 104ms, 17.9MB

class Solution {

public:

int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {

constexpr int kInf = 1e9 + 7, s = 1;

// dp[k][i][c] := min cost to form k neighbors with first i houses and end with color c.

vector<vector<vector<int>>> dp(target + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, kInf)));

fill(begin(dp[0][0]), end(dp[0][0]), 0);

for (int k = 1; k <= target; ++k)

for (int i = k; i <= m; ++i) {

const int hi = houses[i - 1];

const int hj = i >= 2 ? houses[i - 2] : 0;

const auto& [si, ei] = hi ? tie(hi, hi) : tie(s, n);

const auto& [sj, ej] = hj ? tie(hj, hj) : tie(s, n);

for (int ci = si; ci <= ei; ++ci) {

const int v = ci == hi ? 0 : cost[i - 1][ci - 1];

for (int cj = sj; cj <= ej; ++cj)

dp[k][i][ci] = min(dp[k][i][ci], dp[k - (ci != cj)][i - 1][cj] + v);

}

const int ans = *min_element(begin(dp[target][m]), end(dp[target][m]));

return ans >= kInf ? -1 : ans;

}

};

花花酱 LeetCode 1472. Design Browser History

By zxi on June 6, 2020

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Implement the BrowserHistory class:

BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
void visit(string url) visits url from the current page. It clears up all the forward history.
string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.

Example:

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]
Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.
browserHistory.back(2);                   // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com"
browserHistory.back(7);                   // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"

Constraints:

1 <= homepage.length <= 20
1 <= url.length <= 20
1 <= steps <= 100
homepage and url consist of ‘.’ or lower case English letters.
At most 5000 calls will be made to visit, back, and forward.

Solution: Vector

Time complexity:
visit: Amortized O(1)
back: O(1)
forward: O(1)

C++

// Author: Huahua

class BrowserHistory {

public:

BrowserHistory(string homepage) :

index_(0) {

urls_.push_back(std::move(homepage));

}

void visit(string url) {

while (urls_.size() > index_ + 1)

urls_.pop_back();

++index_;

urls_.push_back(std::move(url));

}

string back(int steps) {

index_ = max(index_ - steps, 0);

return urls_[index_];

}

string forward(int steps) {

index_ = min(index_ + steps, static_cast<int>(urls_.size()) - 1);

return urls_[index_];

}

private:

int index_;

vector<string> urls_;

};

花花酱 LeetCode 1471. The k Strongest Values in an Array

By zxi on June 6, 2020

Given an array of integers arr and an integer k.

Return a list of the strongest k values in the array. return the answer in any arbitrary order.

Median is the middle value in an ordered integer list. More formally, if the length of the list is n, the median is the element in position ((n - 1) / 2) in the sorted list (0-indexed).

For arr = [6, -3, 7, 2, 11], n = 5 and the median is obtained by sorting the array arr = [-3, 2, 6, 7, 11] and the median is arr[m] where m = ((5 - 1) / 2) = 2. The median is 6.
For arr = [-7, 22, 17, 3], n = 4 and the median is obtained by sorting the array arr = [-7, 3, 17, 22] and the median is arr[m] where m = ((4 - 1) / 2) = 1. The median is 3.

Example 1:

Input: arr = [1,2,3,4,5], k = 2
Output: [5,1]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,1,4,2,3]. The strongest 2 elements are [5, 1]. [1, 5] is also accepted answer.
Please note that although |5 - 3| == |1 - 3| but 5 is stronger than 1 because 5 > 1.

Example 2:

Input: arr = [1,1,3,5,5], k = 2
Output: [5,5]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,5,1,1,3]. The strongest 2 elements are [5, 5].

Example 3:

Input: arr = [6,7,11,7,6,8], k = 5
Output: [11,8,6,6,7]
Explanation: Median is 7, the elements of the array sorted by the strongest are [11,8,6,6,7,7].
Any permutation of [11,8,6,6,7] is accepted.

Example 4:

Input: arr = [6,-3,7,2,11], k = 3
Output: [-3,11,2]

Example 5:

Input: arr = [-7,22,17,3], k = 2
Output: [22,17]

Constraints:

1 <= arr.length <= 10^5
-10^5 <= arr[i] <= 10^5
1 <= k <= arr.length

Solution 1: quick selection + sort

Step 1: find the median element m
Step 2: Sort the array according to m
Step 3: output the first k elements of the sorted array.

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> getStrongest(vector<int>& arr, int k) {

const int n = arr.size();

const int i = (n - 1) / 2;

// sort(begin(arr), end(arr));

nth_element(begin(arr), begin(arr) + i, end(arr));

const int m = arr[i];

sort(begin(arr), end(arr), [&](const int x, const int y) {

return abs(x - m) != abs(y - m) ? abs(x - m) > abs(y - m) : x > y;

});

return {begin(arr), begin(arr) + k};

}

};

花花酱 LeetCode 1470. Shuffle the Array

By zxi on June 6, 2020

Given the array nums consisting of 2n elements in the form [x₁,x₂,...,x_n,y₁,y₂,...,y_n].

Return the array in the form [x₁,y₁,x₂,y₂,...,x_n,y_n].

Example 1:

Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x₁=2, x₂=5, x₃=1, y₁=3, y₂=4, y₃=7 then the answer is [2,3,5,4,1,7].

Example 2:

Input: nums = [1,2,3,4,4,3,2,1], n = 4
Output: [1,4,2,3,3,2,4,1]

Example 3:

Input: nums = [1,1,2,2], n = 2
Output: [1,2,1,2]

Constraints:

1 <= n <= 500
nums.length == 2n
1 <= nums[i] <= 10^3

Solution: Simulation

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> shuffle(vector<int>& nums, int n) {

vector<int> ans(n * 2);

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

ans[i] = nums[i / 2 + n * (i % 2)];

return ans;

}

};

Huahua's Tech Road

C++ 11 Smart Pointers 智能指针

C++

Output

花花酱 LeetCode 1473. Paint House III

Solution: DP

C++

花花酱 LeetCode 1472. Design Browser History

Solution: Vector

C++

花花酱 LeetCode 1471. The k Strongest Values in an Array

Solution 1: quick selection + sort

C++

花花酱 LeetCode 1470. Shuffle the Array

Solution: Simulation

C++