1472. Design Browser History. ---M

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.

A:

关键核心是curCount的定义。 一开始我定义成了pos， 就导致对比res.size()的时候，需要各种加减1.   那样容易出错

class BrowserHistory {

public:

BrowserHistory(string homepage) {

res.clear();

res.push_back(homepage);

curCount = 1;

}

void visit(string url) {

if (curCount < res.size()) {

res.erase(res.begin() + curCount, res.end());

}

res.push_back(url);

curCount++;

}

string back(int steps) {

steps = min(steps, curCount - 1);

curCount -= steps;

return res[curCount - 1];

}

string forward(int steps) {

if (steps > res.size() - curCount) {

steps = res.size() - curCount;

}

curCount += steps;

return res[curCount - 1];

}

private:

vector<string> res;

int curCount; // current valid history count. (use count, to better compare

// with res.size() )

};

/**

* Your BrowserHistory object will be instantiated and called as such:

* BrowserHistory* obj = new BrowserHistory(homepage);

* obj->visit(url);

* string param_2 = obj->back(steps);

* string param_3 = obj->forward(steps);

*/

27. Remove Element Easy

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

 

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

 

Constraints:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

A:

就是挨个拷贝过去

class Solution {

public:

int removeElement(vector<int>& nums, int val) {

int idx = 0;

for(auto num : nums){

if(num != val){

nums[idx++] = num;

}

}

return idx;

}

}; 

968. Binary Tree Cameras （hard）

 You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

Return the minimum number of cameras needed to monitor all nodes of the tree.

 

Example 1:

Input: root = [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

 

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• Node.val == 0

A：

就是每个node， 看是否用了，  如果用了。就跳到

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

int minCameraCover(TreeNode* root) {

M[nullptr] = 0;

return min(noPlaceOnRoot(root), placeOnRoot(root));

}

private:

int noPlaceOnRoot(TreeNode* root){

if(!root)

return 0;

if(!root->left && ! root->right) // no child, impossible

return INT_MAX;

if(!root->left){

return placeOnRoot(root->right);

}else if(!root->right){

return placeOnRoot(root->left);

}else{ // both are not null

int useLeftChild = placeOnRoot(root->left) + minCameraCover(root->right);

int useRightChild = placeOnRoot(root->right) + minCameraCover(root->left);

return min(useLeftChild, useRightChild);

}

}

// if root is placed a camera,

int placeOnRoot(TreeNode* root){

if(!root)

return INT_MAX;

if(M.find(root) != M.end()){

return M.find(root)->second;

}

int l = 0, r = 0;

if(root->left)

l = minCameraCover(root->left->left) + minCameraCover(root->left->right);

if(root->right)

r= minCameraCover(root->right->left) + minCameraCover(root->right->right);

M[root] = 1 + l + r;

return M[root];

}

//the minimum # of cameras in binary tree if placed at root

unordered_map<TreeNode*, int> M; // insert nullptr, to avoid checking

};

NOTE：  这里，LC的test case感觉是错的

[0,null,0,null,0,null,0,null,0,0,0,null,null,0,0]

我的输出是4， 他说expect 3. 但是我画了图，感觉4 才对