215. Kth Largest Element in an Array ----- M !!!!!

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

 

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

 

Constraints:

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

A:

--------用minHeap  ---------O(n+k*log(k))-----------------

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // Internally, priority_queue uses a max-heap with operator<, so:
    // If a < b, then b has higher priority
        priority_queue<int, vector<int>, greater<int>> queue;
        for(auto v : nums){
            queue.push(v);
            if(queue.size() > k){
                queue.pop();
            }
        }
        return queue.top();
    }
};

QuickSelect
(这道题的关键点在于 当值全部大于（或小于）pivot点的时候的处理方式。--》 因此要把pivot点swap到中间的操作。

核心是要数 midVal的个数。 这样方便砍掉

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // half of the quick sort
        int n = nums.size();
        if (k == 1) {
            auto max_iter = max_element(nums.begin(), nums.end()); // get max
            return *max_iter;
        }
        int mid =
            (nums.front() + nums.back()) / 2; // first get mid of first and last
        vector<int> bigger, smaller;
        int midCount = 0;
        for (const auto& val : nums) {
            if (val > mid) {
                bigger.push_back(val); // move to new and pop it out
            } else if (val == mid) {
                midCount++;
            } else {
                smaller.push_back(val);
            }
        }
        if (bigger.size() >= k) {
            return findKthLargest(bigger, k);
        } else if (bigger.size() + midCount >= k) {
            return mid;
        } else {
            return findKthLargest(smaller, k - bigger.size() - midCount);
        }
    }
};

这个题目，自己第一次做的时候， 没有做把end的值swap到mid位置的操作，因此会出现死循环。

——————————第三遍————————————
quick sort 思路。 

就是本地数组操作，避免了copy 一个新的数组

class Solution {

public:

int findKthLargest(vector<int>& nums, int k) {

// since more familiar with count from small to large

return helper(nums, 0, nums.size(), nums.size() + 1 - k);

}

private:

int helper(vector<int>& nums, int start, int end, int k) {

int pivot = nums[start], cPivot = 0;

int latestSmall = start - 1, latestBigger = end;

for (int i = start; i < latestBigger; i++) {

if (nums[i] > pivot) {

--latestBigger;

if (i != latestBigger) {

swap(nums[latestBigger], nums[i]);

i--;

}

} else if (nums[i] == pivot) {

cPivot++;

} else {

swap(nums[++latestSmall], nums[i]); // no need to i--

}

}

int l = latestSmall - start + 1;

int r = end - latestBigger;

if (k <= l) { // use left part

return helper(nums, start, latestSmall + 1, k);

} else if (k > l + cPivot) {

return helper(nums, latestBigger, end, k - l - cPivot);

} else {

return pivot;

}

}

};

Mistakes:
1:   当k ==1的时候，还是要继续分下去。     而基础条件应该是 start == end
2:

double pivot = (A[start] + A[end])/2;

 这里，当A[start] == 1, A[end]==2的 时候，pivot 的结果是1.   ！！！！！
 因此要除以 2.0


------------------------排序-------  但是对于太大的数组，不适合--------------------

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()-k];
    }
};

213. House Robber II -------------M

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

A:
递归，with memory

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> V(n, vector<int>(n,-1));
        return helper(nums,0,n-1, V);
    }
private:
    int helper(vector<int> & nums, int start, int end, vector<vector<int>> & V){
        if(start>end)
            return 0;
        if(V[start][end]>=0)
            return V[start][end];
        int withStart = nums[start] + helper(nums, start+2, end - (start==0?1:0), V);
        int noStart = helper(nums, start+1, end, V);
        
        int res = max(withStart, noStart);
        V[start][end] = res;
        return res;
    }
};

思路很简单，就是每次不取  头  或者不取尾。

class Solution {
public:
    int rob(vector<int>& nums) {        
        int n = nums.size();
        if(n==1)
            return nums[0];
        // two cases, with, or without first element
        return max(helper(nums,0, n-2), helper(nums, 1, n-1) );
    }
private:
    int helper(vector<int> & nums, int start, int end){
        //DP, each time, we jump or not jump
        int cur = 0, pre = 0; // current maxSum, or preMaxSum
        for(int i =start; i<= end; i++){
            int newMax = max(cur, pre+nums[i]);
            pre = cur;
            cur = newMax;
        }
        return cur;
    }
};

Mistakes:

忘记了当只有一个的情况，要单独列出来

House Robber

Q:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

A:
就是简单的 记录之前的两个位置.  每次加如一个新的值

class Solution {
public:
    int rob(vector<int>& nums) {
        int cur = 0, pre = 0; // max rob after using current value 
        for(int i =0; i<nums.size(); ++i)
        {
            int newCur = max(nums[i]+pre, cur);
            pre = cur;
            cur = newCur;
        }
        return cur;
    }
};

Mistakes:

212. Word Search II ----H ~~~~~~~~

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

 

Example:

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

 

Note:

1. All inputs are consist of lowercase letters a-z.
2. The values of words are distinct.

A:
就是用Trie了， 自己建Trie要麻烦些罢了。
然后用DFS即可。

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> res;
        int m = board.size();
        if(m== 0)
            return res;
        int n = board[0].size();
        Node* root = buildTrie(words);
        unordered_set<string> resSet;// to avoid duplicates
        vector<vector<bool>> visited(m,vector<bool>(n, false));
        for(int i =0;i<m;i++){
            for(int j = 0; j<n;j++){
                dfs(board, i,j,root->kids[board[i][j]], resSet, visited);
            }
        }
        res.assign(resSet.begin(),resSet.end());
        return res;
    }
private:
    struct Node{
        unordered_map<char,Node*> kids; // cannot declare here. (26,nullptr);
        bool isLeaf;
        char cur;
        string curWord;
        Node(char ch):cur(ch),isLeaf(false),curWord(""){}
    };
    Node* buildTrie(vector<string> &words){
        Node* root = new Node(' ');
        for(auto word: words){
            auto pre = root; // auto & pre = root is WRONG. DO NOT reference a pointer
            for(auto ch : word){
                if(not pre->kids[ch]){
                    pre->kids[ch] = new Node(ch);
                }
                pre = pre->kids[ch];
            }
            pre->isLeaf = true;
            pre->curWord = word;
        }
        return root;
    }
    void dfs(vector<vector<char>>& board, int i, int j, const Node* root, unordered_set<string>& resSet, vector<vector<bool>>& visited){
        int m = board.size();
        int n = board[0].size();
        if(i<0 || i>=m || j<0 || j>=n || visited[i][j] || not root){
            return;
        }
        if(root->cur == board[i][j]){
            visited[i][j] = true;
            if(root->isLeaf){
                resSet.insert(root->curWord);
            }
            vector<vector<int>> Diff{ {-1,0},{1,0},{0,-1},{0,1}};
            for(auto& d : Diff){
                for(auto kid : root->kids){
                    dfs(board, i+d[0], j + d[1], kid.second, resSet,visited);
                }
            }
            visited[i][j] = false;
        }
    }
};

Mistakes:
1:  even isLeaf==true, 也需要继续找下去。  例如 words = {"the", "they" "their"}

2: 没有处理一个word被多次找到的情况。i.e.   word节点可能被多次找到，

例如输入是    {{'a'}} , {"a"}的时候。
   这样，我们就需要 每次见dfs下一层， 进去之后再检查 flag  matrix是否  valid
 但是，这样又会出现 一个位置 多次计算的问题。
 因此还是要  每次进入之前检测。
其实还是对自己的这个Trie的定义的理解问题。  代码里，我们是先到一个TrieNode之后，再检测该位置是否match，然后再试探着dfs

3： 
这个题目的关键点（for me）  就是 考虑到root的定义， 我们初始dfs的 时候，就要进入root的下一个TrieNode.

dfs(board, i,j,root->kids[board[i][j]], resSet, visited);

Contains Duplicate III ！！！！！！！！

Q:
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
A:
就是对一个 k+1的窗口  保持一个排序。同时用 最大最小 来检测。

TreeSet：  是基于TreeMap实现的。TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
TreeSet为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。
另外，TreeSet是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> set = new TreeSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            int c = nums[i];
            if ((set.floor(c) != null && c <= set.floor(c) + t)
            || (set.ceiling(c) != null && c >= set.ceiling(c) -t))
                return true;
     
            set.add(c);
            if (i >= k)
                set.remove(nums[i - k]);
        }
        return false;
    }
}

Mistakes:

219. Contains Duplicate II

Q:
Given an array of integers and an integer k, find out whether there there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
A:
就是简单的，在  k+1的长度中查询 duplicate

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet();
        for(int i =0;i< nums.length;i++){
            if(i - k - 1 >=0)   // delete first
                set.remove( nums[i-k-1]);
            
            if(set.contains(nums[i]))
                return true;
            set.add(nums[i]);
        }
        return false;
    }
}
 

Contains Duplicate

Q:
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
A:
--------Sol : 用Set    ,  use O(n) extra space   O(n) time---------

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet();
        for(int i :nums){
            if(set.contains(i))
                return true;
            set.add(i);
        }
        return false;
    }
}

-------Sol 2:   manipulate nums, ,  use O(1) space, and O(n) time ----------------
每次按照某一位的 bit分开nums[],  然后再继续分，直到最后32bit还一样，就true,否则false

223. Rectangle Area -------------M ~~~~

Q:
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.

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

A:
就是简单的找到相交的面积，再减去即可。

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        long maxLeftX = max(A,E);
        long minRightX = min(C,G);
        long width = (minRightX - maxLeftX > 0)? (minRightX -maxLeftX):0;
        long maxBottomY = max(B, F);
        long minUpY = min(D, H);
        long height = (minUpY - maxBottomY >0)? (minUpY - maxBottomY) : 0;
        return int( long(C-A)*(D-B) + long(G-E)*(H-F) - width * height);
    }
};

Mistakes:
1：  虽然结果上说， 最终面积并没有超出。但是不表示中间计算过程的结果不超出int的范围。 因此还是需要 在计算过程中 用long  类型表示。 ( 亦即 计算 length 和 height的时候，可能会溢出 )
   因此所有的中间计算结果都要用long类型

225. Implement Stack using Queues -E

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

A:

就是简单的，每次都pop()出来，再放到最后去了

class MyStack {
public:
    MyStack() {
    }
    
    void push(int x) {
        D.push_back(x);
    }
    
    int pop() {
        int n = D.size();
        for(int i =0;i<n-1;i++){
            int val = *D.begin();
            D.pop_front();
            D.push_back(val);
        }
        int res = *D.begin();
        D.pop_front();
        return res;
    }
    
    int top() {
        int val = 0;
        for(int i =0;i< D.size();i++){
            val = *D.begin();
            D.pop_front();
            D.push_back(val);
        }
        return val;
    }
    
    bool empty() {
        return D.empty();
    }
private:
    deque<int> D;
};
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

Mistakes:

1: 第一遍的时候，理解成是用2个Stack来表示Queue了    太TMD搞笑（Diu Ren)了

2: 注意， D.begin() 返回的是iterator， 需要*

226. Invert Binary Tree (easy)

Given the root of a binary tree, invert the tree, and return its root.

 

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

 

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

A:
递归

/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if (!root)
            return root;
        invertTree(root->left);
        invertTree(root->right);
        auto tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        return root;
    }
};