Kth Largest Element

Question:
http://www.lintcode.com/en/problem/kth-largest-element/
Find K-th largest element in an array.
You can swap elements in the array.

Answer:

class Solution {
public:
    /*
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    inline void qsort(vector<int> &nums, int left, int right) {
        if (left >= right)
            return;
        int mid = nums[(left + right)/2];
        int l = left;
        int r = right;
        while (l < r) {
            while(nums[l] < mid) ++l;
            while(nums[r] > mid) --r;
            if (l >= r) break;
            nums[l] = nums[l] + nums[r];
            nums[r] = nums[l] - nums[r];
            nums[l] = nums[l] - nums[r];
            ++l;
            --r;
        }
        if (l == r) l++;
        if (left < r) qsort(nums, left, l - 1);
        if (l > left) qsort(nums, r + 1, right);
    }
    int kthLargestElement(int n, vector<int> &nums) {
        // write your code here
        qsort(nums, 0, nums.size() - 1);
        return nums[nums.size() - n];
    }
};

call the Sabbath a delight and the Lord's holy day honorable

"If you keep your feet from breaking the Sabbath and from doing as you please on my holy day, if you call the Sabbath a delight and the Lord 's holy day honorable, and if you honor it by not going your own way and not doing as you please or speaking idle words, (Isaiah 58:13 NIV)
你若在安息日掉转（或译：谨慎） 你的脚步，在我圣日不以操作为喜乐，称安息日为可喜乐的，称耶和华的圣日为可尊重的；而且尊敬这日，不办自己的私事，不随自己的私意，不说自己的私话， (以赛亚书 58:13 和合本)
then you will find your joy in the Lord , and I will cause you to ride in triumph on the heights of the land and to feast on the inheritance of your father Jacob." The mouth of the Lord has spoken. (Isaiah 58:14 NIV)
你就以耶和华为乐。耶和华要使你乘驾地的高处，又以你祖雅各的产业养育你。这是耶和华亲口说的。 (以赛亚书 58:14 和合本)

Photo by Sam Goodgame / Unsplash

Send your post to your blogger via Subscribers

blogger setup

Setup your posting email in your blogger's setting.

You can chose published it immediatly or as a draft

ghost settup

Install Ghost via my hacked ghost.
Install command: ghost install --zip /path/to/Ghost-1.17.1.zip
Click here to download Ghost-1.17.1.zip

More install config please refer to ghost install --help
Enable Subscribers feature in your Ghost's Labs.

https://help.ghost.org/hc/en-us/articles/224089787-Subscribers-Beta
Subcribers is currently still a beta feature, The current version of subscribers does NOT send emails. This will come in a future version.
so I hacked into Ghost core and release it. please first install my hacked version which metioned at the beginning.
By the way, it is just a simple hack, offical ghost will support it later with significant improvements to the Subscribers feature in the future and more integration as we build out our Memberships and Subscriptions features.
If you eager to send post to your Subscribers, you can try my hacked ghost like me.:)
Add your blogger's mail as a subscriber of Ghost.

Now everything is ready.
Once this post published in my ghost, it will be published in my blogger too.

Please add your recipient's email address to authorized recipents if you are using free accounts of Mailgun

I setup mailgun with my ghost blog.
but I found I cann't send any mails out exception the mails send to errong.leng@gmail.com which is registered to create an account in mailgun.

I checked my mailgun's account's log, and I found:
Rejected: 'Errong Leng has invited you to join ACM Problem Resolving&Report' Free accounts are for test purposes only. Please upgrade or add the address to authorized recipients in Account Settings.:

Ok. I do not like to upgrade since it will require your credit card info.
I have to add the address to authorized recipients in Account Settings.

Input your recipient's address

Check your email and click "I Agree"

Confirm and clicked "Yes"

You will found the recipient verified

Ok, every thing is fine now.
Perphas I will upgrade later since you have to add each recipient one by one and wait it verified.

Hack Ghost core and release it

if you want to hack Ghost core you need to follow
https://docs.ghost.org/docs/working-with-ghost and
https://docs.ghost.org/docs/working-with-the-admin-client

Once you done all your hack job, just run grunt release command under your ghost folder.

grunt release 

Once it completed, you will get a zip file:
./.dist/release/Ghost-1.16.1.zip

Then run your hacked ghost under a new empty folder:
ghost install --zip /path/to/.dist/release/Ghost-1.16.1.zip 

 --zip              Path to Ghost release zip to install         [string]

House Robber III

Question:
http://www.lintcode.com/en/problem/house-robber-iii/
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.

Answer:
~~~c++
class Solution {
public:
    int houseRobber3(TreeNode* root) {
        unordered_map<TreeNode*, int> m;
        return dfs(root, m);
    }
    int dfs(TreeNode *root, unordered_map<TreeNode*, int> &m) {
        if (!root) return 0;
        if (m.count(root)) return m[root];
        int val = 0;
        if (root->left) {
            val += dfs(root->left->left, m) + dfs(root->left->right, m);
        }
        if (root->right) {
            val += dfs(root->right->left, m) + dfs(root->right->right, m);
        }
        val = max(val + root->val, dfs(root->left, m) + dfs(root->right, m));
        m[root] = val;
        return val;
    }
};
~~~

House Robber II

Question:
http://www.lintcode.com/en/problem/house-robber-ii/
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

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.
Answer:
~~~c++
class Solution {
public:
     /*
     * @param nums: An array of non-negative integers.
     * @return: The maximum amount of money you can rob tonight
     */
    int houseRobber2(vector<int> nums) {
        if (nums.size() <= 1)
            return nums.empty() ? 0 : nums[0];
        vector<int> nums_inf = nums;
        vector<int> nums_inl = nums;
        nums_inf.pop_back();
        nums_inl.erase(nums_inl.begin());
        return max(houseRobber(nums_inf), houseRobber(nums_inl));
    }

    /*
     * @param A: An array of non-negative integers
     * @return: The maximum amount of money you can rob tonight
     */
    long long houseRobber(vector<int> &A) {
        size_t as = A.size();
        if (as == 0)
          return 0;
        if (as == 1)
          return A[0];
        if (as == 2)
          return max(A[0], A[1]);
        vector<long long> dp(as);
        dp[0] = A[0];
        dp[1] = max(A[0], A[1]);
        for (size_t i = 2; i < as; i++)
          dp[i] = max(dp[i-1], dp[i-2] + A[i]);
        return dp[as-1];
    }
};
~~~

PS:
if houseRobber(vector<int> &A) use memory O(1) method in [house-robber](http://acm.errong.win/house-robber/),
   
~~~c++
    long long houseRobber(vector<int> &A) {
        size_t as = A.size();
        long long odd, even;
        odd = even = 0;
        for (size_t i = 0; i < as; i++)
          if (i % 2)
            odd = max(odd+A[i], even);
          else
            even = max(even + A[i], odd);
        return max(odd, even);
    }
~~~

houseRobber2 will exceed the time limit.
it seems like i%2 operation will take more time.