花花酱 LeetCode 396. Rotate Function

By zxi on March 16, 2018

Problem:

Given an array of integers A and let n to be its length.

Assume B_k to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * B_k[0] + 1 * B_k[1] + ... + (n-1) * B_k[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Note:
n is guaranteed to be less than 10⁵.

Example:

A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Solution 1: Brute Force

Time complexity: O(n^2) TLE

Space complexity: O(1)

Solution 2: Math

F(K)          =               0A[K] + 1A[K+1] + 2A[K+2] + ... + (n-2)A[K-2] + (n-1)A[K-1]
F(K-1)        =     0A[K-1] + 1A[K] + 2A[K+1] + 3A[K+2] + ... + (n-1)A[K-2]
F(K) - F(K-1) = (n-1)A[K-1] - 1A[K] - 1A[K+1] - 1A[K+2] - ... -     1A[K-2]
              = (n-1)A[K-1] - (1A[K] + 1A[K+1] + ... + 1A[K-2] + 1A[K-1] - 1A[K-1])
              = nA[K-1] - sum(A)
compute F(0)
F(i)          = F(i-1) + nA[i-1] - sum(A)

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 11 ms

class Solution {

public:

int maxRotateFunction(vector<int>& A) {

const int n = A.size();

int sum = 0;

int f = 0;

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

sum += A[i];

f += i * A[i];

}

int ans = f;

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

f = f + sum - n * A[n - i - 1];

ans = max(ans, f);

}

return ans;

}

};

花花酱 LeetCode 384. Shuffle an Array

By zxi on March 16, 2018

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.

int[] nums = {1,2,3};

Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.

solution.shuffle();

// Resets the array back to its original configuration [1,2,3].

solution.reset();

// Returns the random shuffling of array [1,2,3].

solution.shuffle();

C++

// Author: Huahua

// Running time: 249 ms

class Solution {

public:

Solution(vector<int> nums) {

nums_ = std::move(nums);

}

/** Resets the array to its original configuration and return it. */

vector<int> reset() {

return nums_;

}

/** Returns a random shuffling of the array. */

vector<int> shuffle() {

vector<int> output(nums_);

const int n = nums_.size();

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

int j = rand() % (n - i) + i;

std::swap(output[i], output[j]);

}

return output;

}

private:

vector<int> nums_;

};

花花酱 LeetCode 392. Is Subsequence

By zxi on March 16, 2018

题目大意：问s是不是t的子序列。

Problem:

https://leetcode.com/problems/is-subsequence/description/

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and sis a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Solution: Brute force

Time Complexity: O(|s| + |t|)

Space Complexity: O(1)

C++

// Author: Huahua

// Running time: 65 ms (beats 99.37%)

class Solution {

public:

bool isSubsequence(const string& s, const string& t) {

int i = 0;

const int n = t.length();

for (const char c : s) {

while (i < n && t[i] != c) ++i;

if (i++ == n) return false;

}

return true;

}

};

花花酱 LeetCode 337. House Robber III

By zxi on March 15, 2018

题目大意：给你一棵二叉树，不能同时取两个相邻的节点(parent/child)，问最多能取得的节点的值的和是多少。

Problem:

https://leetcode.com/problems/house-robber-iii/description/

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Maximum amount of money the thief can rob = 4 + 5 = 9.

Idea:

Compare grandparent + max of grandchildren(l.l + l.r + r.l + r.r) vs max of children (l + r)

Solution 1: Recursion w/o memorization

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 1289 ms

class Solution {

public:

int rob(TreeNode* root) {

if (root == nullptr) return 0;

int val = root->val;

int ll = root->left ? rob(root->left->left) : 0;

int lr = root->left ? rob(root->left->right) : 0;

int rl = root->right ? rob(root->right->left) : 0;

int rr = root->right ? rob(root->right->right) : 0;

return max(val + ll + lr + rl + rr, rob(root->left) + rob(root->right));

}

};

Solution 2: Recursion w/ memorization

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int rob(TreeNode* root) {

if (root == nullptr) return 0;

if (m_.count(root)) return m_[root];

int val = root->val;

int ll = root->left ? rob(root->left->left) : 0;

int lr = root->left ? rob(root->left->right) : 0;

int rl = root->right ? rob(root->right->left) : 0;

int rr = root->right ? rob(root->right->right) : 0;

return m_[root] = max(val + ll + lr + rl + rr, rob(root->left) + rob(root->right));

}

private:

unordered_map<TreeNode*, int> m_;

};

Solution 3: Recursion return children’s value

// Author: Huahua

// Running time: 10 ms (beats 97.57%)

class Solution {

public:

int rob(TreeNode* root) {

int l = 0;

int r = 0;

return rob(root, l, r);

}

private:

// return rob(root) and stores rob(root->left/right) in l/r.

int rob(TreeNode* root, int& l, int& r) {

if (root == nullptr) return 0;

int ll = 0;

int lr = 0;

int rl = 0;

int rr = 0;

l = rob(root->left, ll, lr);

r = rob(root->right, rl, rr);

return max(root->val + ll + lr + rl + rr, l + r);

}

};

Python3

"""

Author: Huahua

Running time: 64 ms (beats 93.18%)

"""

class Solution:

def rob(self, root):

def rob(root):

if not root: return 0, 0, 0

l, ll, lr = rob(root.left)

r, rl, rr = rob(root.right)

return max(root.val + ll + lr + rl + rr, l + r), l, r

return rob(root)[0]

Related Problems:

花花酱 LeetCode 198. House Robber

Posts tagged as “medium”

花花酱 LeetCode 382. Linked List Random Node

Problem:

Solution:

花花酱 LeetCode 396. Rotate Function

Problem:

Solution 1: Brute Force

Solution 2: Math

花花酱 LeetCode 384. Shuffle an Array

花花酱 LeetCode 392. Is Subsequence

Problem:

Solution: Brute force

花花酱 LeetCode 337. House Robber III