Course Schedule

Question:

http://www.lintcode.com/en/problem/course-schedule/
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Answer:

class Solution {
public:
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: true if can finish all courses or false
     */
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        // Write your code here
        vector<vector<int>> adj(numCourses);
        vector<int> indegree(numCourses);
        for (int i = 0; i < numCourses; i++)
             indegree[i] = 0;
        for (auto pq : prerequisites) {
            adj[pq.first].push_back(pq.second);
            indegree[pq.second]++;
        }
        stack<int> st;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0)
                st.push(i);
        }
        int count = 0;
        while (!st.empty()) {
            int v1 = st.top();
            st.pop();
            count++;
            for (auto v2 : adj[v1]) {
                indegree[v2]--;
                if (indegree[v2] == 0)
                    st.push(v2);
            }
        }
        return count == numCourses;
    }
}

How to be Jesus's disciples

我是葡萄树，你们是枝子。常在我里面的，我也常在他里面，这人就多结果子；因为离了我，你们就不能作什么。 (约翰福音 15:5 和合本)
"I am the vine; you are the branches. If you remain in me and I in you, you will bear much fruit; apart from me you can do nothing. (John 15:5 NIV)
人若不常在我里面，就像枝子丢在外面枯干，人拾起来，扔在火里烧了。 (约翰福音 15:6 和合本)
If you do not remain in me, you are like a branch that is thrown away and withers; such branches are picked up, thrown into the fire and burned. (John 15:6 NIV)
你们若常在我里面，我的话也常在你们里面，凡你们所愿意的，祈求，就给你们成就。 (约翰福音 15:7 和合本)
If you remain in me and my words remain in you, ask whatever you wish, and it will be done for you. (John 15:7 NIV)
你们多结果子，我父就因此得荣耀，你们也就是我的门徒了。 (约翰福音 15:8 和合本)
This is to my Father's glory, that you bear much fruit, showing yourselves to be my disciples. (John 15:8 NIV)

Photo by Bill Williams / Unsplash

Wildcard Matching

Question:
http://www.lintcode.com/en/problem/wildcard-matching/
Implement wildcard pattern matching with support for '?' and '*'.

    '?' Matches any single character. 

    '*' Matches any sequence of characters (including the empty sequence). 

The matching should cover the entire input string (not partial).


Answer:

class Solution {
public:
    /*
     * @param s: A string 
     * @param p: A string includes "?" and "*"
     * @return: is Match?
     */
    bool isMatch(string &s, string &p) {
        if (p.empty())
            return false;
        int n = s.length();
        int m = p.length();
        bool f[n + 1][m + 1];
        memset(f, false, sizeof(f));
        f[0][0] = true;
        for (int i = 1; i <= n; i++)
            f[i][0] = false;
        for (int i = 1; i <= m; i++)
            f[0][i] = f[0][i - 1] && p[i - 1] == '*';
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i - 1][j] || f[i][j - 1];
                } else if (p[j - 1] == '?') {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1]);
                }
            }
        } 
        return f[n][m];
    }
}; 

Maximum Gap

Question:
http://www.lintcode.com/en/problem/maximum-gap/
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
Sort is easy but will cost O(nlogn) time. Try to solve it in linear time and space.
Answer:

class Solution {  
public:  
    int maximumGap(vector<int> &num) {  
       if (num.size() < 2) return 0;  
        int maxNum = num[0];  
        int minNum = num[0];  
        for (int x : num) {  
            maxNum = max(maxNum, x);  
            minNum = min(minNum, x);  
        }  
        int len = (maxNum - minNum) / num.size() + 1;  
        vector<vector<int>> buckets((maxNum - minNum) / len + 1);  
        for (int x : num) {  
            int i = (x - minNum) / len;  
            if (buckets[i].empty()) {  
                buckets[i].reserve(2);  
                buckets[i].push_back(x);  
                buckets[i].push_back(x);  
            } else {  
                if (x < buckets[i][0]) buckets[i][0] = x;  
                if (x > buckets[i][1]) buckets[i][1] = x;  
            }  
        }  
        int gap = 0;  
        int prev = 0;  
        for (int i = 1; i < buckets.size(); i++) {  
            if (buckets[i].empty()) continue;  
            gap = max(gap, buckets[i][0] - buckets[prev][1]);  
            prev = i;  
        }  
        return gap;  
    }  
};

HOW CHRIST MET A REAL NEED

第三日，在加利利的迦拿有娶亲的筵席，耶稣的母亲在那里。 (约翰福音 2:1 和合本)
On the third day a wedding took place at Cana in Galilee. Jesus' mother was there, (John 2:1 NIV)
耶稣和他的门徒也被请去赴席。 (约翰福音 2:2 和合本)
and Jesus and his disciples had also been invited to the wedding. (John 2:2 NIV)
酒用尽了，耶稣的母亲对他说："他们没有酒了。" (约翰福音 2:3 和合本)
When the wine was gone, Jesus' mother said to him, "They have no more wine." (John 2:3 NIV)
耶稣说："母亲（原文是妇人） ，我与你有什么相干？我的时候还没有到。" (约翰福音 2:4 和合本)
"Woman, why do you involve me?"Jesus replied. "My hour has not yet come." (John 2:4 NIV)
他母亲对用人说："他告诉你们什么，你们就做什么。" (约翰福音 2:5 和合本)
His mother said to the servants, "Do whatever he tells you." (John 2:5 NIV)
照犹太人洁净的规矩，有六口石缸摆在那里，每口可以盛两三桶水。 (约翰福音 2:6 和合本)
Nearby stood six stone water jars, the kind used by the Jews for ceremonial washing, each holding from twenty to thirty gallons. (John 2:6 NIV)
耶稣对用人说："把缸倒满了水。"他们就倒满了，直到缸口。 (约翰福音 2:7 和合本)
Jesus said to the servants, "Fill the jars with water"; so they filled them to the brim. (John 2:7 NIV)
耶稣又说："现在可以舀出来，送给管筵席的。"他们就送了去。 (约翰福音 2:8 和合本)
Then he told them, "Now draw some out and take it to the master of the banquet."They did so, (John 2:8 NIV)
管筵席的尝了那水变的酒，并不知道是哪里来的，只有舀水的用人知道。管筵席的便叫新郎来， (约翰福音 2:9 和合本)
and the master of the banquet tasted the water that had been turned into wine. He did not realize where it had come from, though the servants who had drawn the water knew. Then he called the bridegroom aside (John 2:9 NIV)
对他说："人都是先摆上好酒，等客喝足了，才摆上次的，你倒把好酒留到如今！" (约翰福音 2:10 和合本)
and said, "Everyone brings out the choice wine first and then the cheaper wine after the guests have had too much to drink; but you have saved the best till now." (John 2:10 NIV)
这是耶稣所行的头一件神迹，是在加利利的迦拿行的，显出他的荣耀来；他的门徒就信他了。 (约翰福音 2:11 和合本)
What Jesus did here in Cana of Galilee was the first of the signs through which he revealed his glory; and his disciples believed in him. (John 2:11 NIV)

Photo by Roberta Sorge / Unsplash

The LORD is great

愿一切寻求你的，因你高兴欢喜；愿那些喜爱你救恩的，常说：当尊　神为大！ (诗篇 70:4 和合本)
But may all who seek you rejoice and be glad in you; may those who long for your saving help always say, "The Lord is great!" (Psalms 70:4 NIV)
但我是困苦穷乏的；　神啊，求你速速到我这里来！你是帮助我的，搭救我的。耶和华啊，求你不要耽延！ (诗篇 70:5 和合本)
But as for me, I am poor and needy; come quickly to me, O God. You are my help and my deliverer; Lord , do not delay. (Psalms 70:5 NIV)

Photo by Justin Kauffman / Unsplash

Recommend text editor : Sublime Text

A sophisticated text editor for code, markup and prose