# Good Problem List Summary -1-

Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target. If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|
Example
Given [1,4,2,3] and target = 1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal. Return 2.

Solution :

定义res[i][j] 表示前 i个number with 最后一个number是j，这样的minimum adjusting cost

如果第i-1个数是j, 那么第i-2个数只能在[lowerRange, UpperRange]之间，lowerRange=Math.max(0, j-target), upperRange=Math.min(99, j+target),

这样的话，transfer function可以写成：

for (int p=lowerRange; p<= upperRange; p++) {

dp[i][j] = Math.min(res[i][j], dp[i-1][p] + Math.abs(j-A.get(i-1)));

}

``````class Solution {
public:
/**
* @param A: An integer array.
* @param target: An integer.
*/
int MinAdjustmentCost(vector<int> A, int target) {
int size_A = A.size();
if(size_A == 0)  return 0;
vector<vector<int>> dp(size_A + 1, vector<int>(101, 0));
for(int i = 0; i < 101; i++) {
dp[0][i] = 0;
}

for(int i = 1; i < size_A + 1; i++) {
for(int j = 1; j < 101; j++) {
dp[i][j] = INT_MAX;
int low = max(1, j - target);
int high = min(100, j + target);
for(int k = low; k <= high; k++) {
dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(A[i-1] - j));
}
}
}

int result = INT_MAX;
for (int i = 1; i <= 100; i++) {
result = min(result, dp[size_A][i]);
}
return result;
}
};

``````

Subtree

You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

``````class Solution {
public:
/**
* @param T1, T2: The roots of binary tree.
* @return: True if T2 is a subtree of T1, or false.
*/
bool isSubtree(TreeNode *T1, TreeNode *T2) {
if (!T2) {
return true;
} else if (!T1) {  // !T1 && T2
return false;
} else {  // T1 && T2
return isSameTree(T1, T2) ||
isSubtree(T1->left, T2) ||
isSubtree(T1->right, T2);
}

}

bool isSameTree(TreeNode *T1, TreeNode *T2) {
if (!T1 && !T2) {
return true;
}

if (T1 && T2) {
return T1->val == T2->val &&
isSameTree(T1->left, T2->left) &&
isSameTree(T1->right, T2->right);
}

return false;
}
};
``````

Print Number by Recursion

``````class Solution {
public:
/**
* @param n: An integer.
* return : An array storing 1 to the largest number with n digits.
*/
vector<int> numbersByRecursion(int n) {
vector<int> result;
numbersByRecursionHelper(0, n, result);
return result;
}

// Construct the numbers by the current digit count.
void numbersByRecursionHelper(int depth, int n, vector<int>& result) {
if (depth == n) {
return;
}

if (depth == 0) {  // Initiate the result.
for (size_t d = 1; d <= 9; ++d) {
result.emplace_back(d);
}
} else {  // Construct the numbers by the previous result.
const size_t count = result.size();
for (size_t d = 1; d <= 9; ++d) {
result.emplace_back(d * pow(10, depth));
for (size_t i = 0; i < count; ++i) {
result.emplace_back(result[i] + d * pow(10, depth));
}
}
}
// Construct the numbers in the next depth.
numbersByRecursionHelper(depth + 1, n, result);
}
};
``````

Sliding Windows Maximum

Multiset based Solution

``````class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
/*** use the multiset to get the max-value ***/
multiset<int> w;
for(int i=0; i<nums.size(); i++){
/*** erase the previous top element ***/
if(i>=k)  w.erase(w.find(nums[i-k]));
w.insert(nums[i]);
/*** insert the max-value of the window ***/
if(i>=k-1) result.push_back(*w.rbegin());
}
return result;
}
};
``````

Mono-decrease based Solution

``````class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
deque<int> q;
for(int i=0; i<nums.size(); i++){
/*** remove the top element **/
if(!q.empty() && q.front()==i-k)  q.pop_front();
/*** keep the element in the queue is monotically-decreasing ***/
while(!q.empty() && nums[q.back()] < nums[i])  q.pop_back();
q.push_back(i);
if(i>=k-1)  result.push_back(nums[q.front()]);
}
return result;
}
};
``````

Sliding Windows Median

Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )

Example

For array [1,2,7,8,5], moving window size k = 3. return [2,7,7]

At first the window is at the start of the array like this

[ | 1,2,7 | ,8,5 ] , return the median 2;

then the window move one step forward.

[1, | 2,7,8 | ,5], return the median 7;

then the window move one step forward again.

[1,2, | 7,8,5 | ], return the median 7;

Solution :

``````class Solution {
public:
/**
* @param nums: A list of integers.
* @return: The median of the element inside the window at each moving
*/
vector<int> medianSlidingWindow(vector<int> &nums, int k) {
// min_bst stores the larger half seen so far.
multiset<int, less<int>> min_bst;
// max_bst stores the smaller half seen so far.
multiset<int, greater<int>> max_bst;

vector<int> ans;
for (int i = 0; i < nums.size(); ++i) {
if (i >= k) {
// Remove the element outside the window.
if (max_bst.find(nums[i - k]) != max_bst.cend()) {
max_bst.erase(max_bst.find(nums[i - k]));
} else {
min_bst.erase(min_bst.find(nums[i - k]));
}
}

// Balance smaller half and larger half.
if (max_bst.empty() || nums[i] > *max_bst.cbegin()) {
min_bst.emplace(nums[i]);
if (min_bst.size() > max_bst.size() + 1) {
max_bst.emplace(*min_bst.cbegin());
min_bst.erase(min_bst.cbegin());
}
} else {
max_bst.emplace(nums[i]);
if (max_bst.size() > min_bst.size()) {
min_bst.emplace(*max_bst.cbegin());
max_bst.erase(max_bst.cbegin());
}
}

// If window is full, get the median from 2 BST.
if (i >= k - 1) {
ans.emplace_back(min_bst.size() == max_bst.size() ?
*max_bst.cbegin() : *min_bst.cbegin());
}
}

return ans;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.