2020-06-25

王阳明诗十二首

你未看此花时，此花与汝心同归于寂。
你来看此花时，则此花颜色一时明白起来，便知此花不在你的心外。
Before you see the flower, both you and the flower are in a state of isolation. When you see the flower its color and shape become clearer to you — which means that knowledge of the flower cannot exist apart from mind.

答人问道

饥来吃饭倦来眠，只此修行玄更玄。
说与世人浑不信，却从身外觅神仙。

中秋

去年中秋阴复晴，今年中秋阴复阴。
百年好景不多遇，况乃白发相侵寻。
吾心自有光明月，千古团圆永无缺。
山河大地拥情辉，赏心何必中秋节。

王门四句教

无善无恶心之体，有善有恶意之动。
知善知恶是良知，为善去恶是格物。

赠阳伯

阳伯即伯阳，伯阳竟安在？
大道即人心，万古未尝改。
长生在求仁，金丹非外待。
谬矣三十年，于今吾始悔。

书汪进之太极岩

始信心非明镜台，须知明镜亦尘埃。
人人有个圆圈在，莫向蒲团坐死灰。

溪水

年华若流水，一去无回停。
悠悠百年内，吾道终何成！

咏良知四首示诸生

个个人心有仲尼，自将闻见苦遮迷。
而今指与真头面，只是良知更莫疑。

问君何事日憧憧？烦恼场中错用功。
莫道圣门无口诀，良知两字是参同。

人人自有定盘针，万化根源总在心。
却笑从前颠倒见，枝枝叶叶外头寻。

无声无臭独知时，此是乾坤万有基。
抛却自家无尽藏，沿门持钵效贫儿。

示诸生

尔身各各自天真，不问求人更问人。
但致良知成德业，谩从故纸费精神。
乾坤是易原非尽，心性何形得有尘？
莫道先生学禅语，此言端的为君陈。

啾啾吟

智者不惑仁不忧，君胡戚戚眉双愁？
信步行来皆坦道，凭天判下非人谋。

2020-06-24

贈衛八處士 - Meeting With an Old Friend

贈衛八處士

杜甫

人生不相見，動如參與商。今夕複何夕，共此燈燭光！
少壯能幾時，鬓發各已蒼！訪舊半爲鬼，驚呼熱中腸。
焉知二十載，重上君子堂。昔別君未婚，兒女忽成行。
怡然敬父執，問我來何方？問答乃未已，驅兒羅酒漿。
夜雨剪春韭，新炊間黃粱。主稱會面難，壹舉累十觞。
十觞亦不醉，感子故意長。明日隔山嶽，世事兩茫茫。

Meeting With an Old Friend

Thomson

In life, friends seldom are brought near;
Like stars, each one shines in its sphere.
To-night, oh! what a happy night!
We sit beneath the same lamplight.
Our youth and strength last but a day.
You and I ah! our hairs are grey.
Friends! Half are in a better land,
With tears we grasp each other’s hand.
Twenty more years, short, after all,
I once again ascend your hall.
When we met, you had not a wife;
Now you have children, such is life!
Beaming, they greet their father’s chum;
They ask me from where I have come.
Before our say, we each have said,
The table is already laid.
Fresh salads from the garden near,
Rice mixed with millet, frugal cheer.
When shall we meet? ‘tis hard to know.
And so let the wine freely flow.
This wine, I know, will do no harm.
My old friend’s welcome is so warm.
To-morrow I go, to be whirled.
Again into the wide, wide world.

2020-06-19

Stray Birds

by Rabindranath Tagore

6
IF you shed tears when you miss the sun, you also miss the stars.

18
WHAT you are you do not see, what you see is your shadow.

20
I CANNOT choose the best.
The best chooses me.

22
THAT I exist is a perpetual surprise which is life.

24
REST belongs to the work as the eyelids to the eyes.

25
MAN is a born child, his power is the power of growth.

40
DO not blame your food because you have no appetite.

48
The stars are not afraid to appear like fireflies.

51
YOUR idol is shattered in the dust to prove that God’s dust is greater than your idol.

52
MAN does not reveal himself in his history, he struggles up through it.

56
LIFE is given to us, we earn it by giving it.

65
TINY grass, your steps are small, but you possess the earth under your tread.

75
WE read the world wrong and say that it deceives us.

79
MAN barricades against himself.

82
LET life be beautiful like summer flowers and death like autumn leaves.

84
IN death the many becomes one; in life the one becomes many.
Religion will be one when God is dead.

90
IN darkness the One appears as uniform; in the light the One appears as manifold.

99
DEATH’S stamp gives value to the coin of life; making it possible to buy with life what is truly precious.

117
THE grass-blade is worth of the great world where it grows.

130
IF you shut your door to all errors truth will be shut out.

134
THE roots below the earth claim no rewards for making the branches fruitful.

139
TIME is the wealth of change, but the clock in its parody makes it mere change and no wealth.

149
THE world has opened its heart of light in the morning.
Come out, my heart, with thy love to meet it.

167
THE world has kissed my soul with its pain, asking for its return in songs.

176
THE water in a vessel is sparkling; the water in the sea is dark.
The small truth has words that are clear; the great truth has great silence.

193
A MIND all logic is like a knife all blade.
It makes the hand bleed that uses it.

203
THE day, with the noise of this little earth, drowns the silence of all worlds.

204
THE song feels the infinite in the air, the picture in the earth, the poem in the air and the earth;
For its words have meaning that walks and music that soars.

206
LET me not put myself wrongly to my world and set it against me.

211
GOD’s right hand is gentle, but terrible is his left hand.

217
THE service of the fruit is precious, the service of the flower is sweet, but let my service be the service of the leaves in its shade of humble devotion.

222
THE world does not leak because death is not a crack.

225
THE fountain of death makes the still water of life play.

231
SET bird’s wings with gold and it will never again soar in the sky.

242
THIS life is the crossing of a sea, where we meet in the same narrow ship.
In death we reach the shore and go to our different worlds.

248
MAN is worse than an animal when he is an animal.

252
AROUND the sunny island of Life swells day and night death’s limitless song of the sea.

268
DEATH belongs to life as birth does. The walk is in the raising of the foot as in the laying of it down.

279
WE live in this world when we love it.

282
I SHALL die again and again to know that life is inexhaustible.

284
LOVE is life in its fulness like the cup with its wine.

300
GOD waits for man to regain his childhood in wisdom.

307
LET me not shame thee, Father, who displayest thy glory in thy children.

313
WE shall know some day that death can never rob us of that which our soul has gained, for her gains are one with herself.

316
LET me live truly, my Lord, so that death to me become true.

323
I HAVE suffered and despaired and known death and I am glad that I am in this great world.

Stray Birds By Rabindranath Tagore

2020-06-14

HackerRank - Regex - Assertions

Positive Lookahead

regex_1(?=regex_2)

The positive lookahead (?=) asserts regex_1 to be immediately followed by regex_2. The lookahead is excluded from the match. It does not return matches of regex_2. The lookahead only asserts whether a match is possible or not.

For Example

c(?=o)

is matched with chocolate

Task

gooooo!

o(?=oo)

Negative Lookahead

regex_1(?!regex_2)

The negative lookahead (?!) asserts regex_1 not to be immediately followed by regex_2. Lookahead is excluded from the match (do not consume matches of regex_2), but only assert whether a match is possible or not.

For Example

c(?!o)

is matched with chocolate

Task

If S =goooo, then regex should match goooo. Because the first g is not follwed by g and the last o is not followed by o.

gooooo

1	(\S)(?!\1)

Positive Lookbehind

(?<=regex_2)regex_1

The positive lookbehind (?<=) asserts regex_1 to be immediately preceded by regex_2. Lookbehind is excluded from the match (do not consume matches of regex_2), but only assert whether a match is possible or not.

For Example

1	(?<=[a-z])[aeiou]

is matched with helo

Task

123Go!

1	(?<=[13579])\d

Negative Lookbehind

(?<!regex_2)regex_1

The negative lookbehind (?<!) asserts regex_1 not to be immediately preceded by regex_2. Lookbehind is excluded from the match (do not consume matches of regex_2), but only assert whether a match is possible or not.

For Example

1	(?<![a-z])[aeiou]

is matched with helo

Task

1o1s

1	(?<![aeiuoAEIOU]).

Resources

Regex - Subdomains - Assertions

2020-06-09

LeetCode - Algorithms - 793. Preimage Size of Factorial Zeroes Function

Problem

793. Preimage Size of Factorial Zeroes Function

Relevant problem

An easy problem as 172. Factorial Trailing Zeroes and its solutions: https://hezhigang.github.io/2020/06/06/LeetCode-Algorithms-factorial-trailing-zeroes/

Java

Binary Search strategy

Binary search, also known as half-interval search, logarithmic search, or binary chop, is a general algorithm for linearly ordered data structure, and There are numerous variations of binary search.

Let $ f(x) $ be the number of zeroes at the end of $x!$. We can observe that $ f(x) $ rise when $ x \equiv 0 \hspace{2mm} (mod \hspace{1mm} 5) $,
and $ f(5k)=f(5k+1)=f(5k+2)=f(5k+3)=f(5k+4) $.
$ f(x)=\lfloor \frac{x}{5} \rfloor + \lfloor \frac{x}{25} \rfloor + \cdots + \lfloor \frac{x}{5^n} \rfloor $ where $ \lfloor \frac{x}{5^n} \rfloor \geq 1 $
This geometric sequence with common ratio $ r = \frac{1}{5} $ has a limit that can be computed from the finite sum formula $ \sum_{k=1}^{\infty} \frac{x}{5^k} = \lim_{n \to \infty}\sum_{k=1}^{n} \frac{x}{5^k} = \frac{\frac{x}{5}}{1-\frac{1}{5}} = \frac{x}{4} $, so, there is a inequality that $ \frac{x}{5} < f(x) < \frac{x}{4} $, which gives a small upper and lower bound for binary search algorithm.

class Solution {
    public int preimageSizeFZF(int K) {
        int count = 0;
        long r = search_rank(K);
        count = r==-1?0:5;
        return count;
    }
    
    private long search_rank(long K) {
        long lo = 4*K;
        long hi = 5*K;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            long y = f(mid);
            if (K < y)
                hi = mid - 1;
            else if (K > y)
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }

    private long f(long x) {
        long count = 0;
        for (long i = 5; i <= x; i *= 5)
            count += x / i;
        return count;
    }
}

Submission Detail

44 / 44 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Preimage Size of Factorial Zeroes Function.
Memory Usage: 35.6 MB, less than 100.00% of Java online submissions for Preimage Size of Factorial Zeroes Function.

Complexity Analysis

Time Complexity

$ O(NlogN) $ where N is the input integer such that $ f(x)=N $

Space Complexity

$ O(1) $ as there is no extra space other than local varibles.

2020-06-07

HackerRank - Regex - Backreferences

Matching Same Text Again & Again

\group_number

This tool (\1 references the first capturing group) matches the same text as previously matched by the capturing group.

For Example

(\d)\1

It can match 00, 11, 22, 33, 44, 55, 66, 77, 88 or 99.

Task

ab #1?AZa$ab #1?AZa$

1	^([a-z])(\w)(\s)(\W)(\d)(\D)([A-Z])([a-zA-Z])([aeiouAEIOU])(\S)\1\2\3\4\5\6\7\8\9\10$

Backreferences To Failed Groups

Backreference to a capturing group that match nothing is different from backreference to a capturing group that did not participate in the match at all.

Capturing group that match nothing

(b?)o\1

is matched with o

Here, b? is optional and matches nothing.
Thus, (b?) is successfully matched and capture nothing.
o is matched with o and \1 successfully matches the nothing captured by the group.

Capturing group that didn’t participate in the match at all

(b)?o\1

is not matching o

In most regex flavors (excluding JavaScript), (b)?o\1 fails to match o.

Here, (b) fails to match at all. Since, the whole group is optional the regex engine does proceed to match o.
The regex engine now arrives at \1 which references a group that did not participate in the match attempt at all.
Thus, the backreference fails to match at all.

Task

12-34-56-78

12345678

1

1	^\d{2}(-?)\d{2}\1\d{2}\1\d{2}$

2

1	^\d{2}(-?)(\d{2}\1){2}\d{2}$

Branch Reset Groups

NOTE - Branch reset group is supported by Perl, PHP, Delphi and R.

(?|regex)

A branch reset group consists of alternations and capturing groups. (?|(regex1)|(regex2))
Alternatives in branch reset group share same capturing group.

1	(?\|(Haa)\|(Hee)\|(bye)\|(k))\1

is mathched with HaaHaa and kk

Task

12-34-56-78

12:34:56:78

12---34---56---78

12.34.56.78

1	/^\d{2}(?\|(-)\|(:)\|(---)\|(\.)\|){1}(\d{2}\1){2}\d{2}$/

Forward References

NOTE - Forward reference is supported by JGsoft, .NET, Java, Perl, PCRE, PHP, Delphi and Ruby regex flavors.

Forward reference creates a back reference to a regex that would appear later.
Forward references are only useful if they’re inside a repeated group.
Then there may arise a case in which the regex engine evaluates the backreference after the group has been matched already.

1	(\2amigo\|(go!))+

is matched with go!go!amigo

Task

tactactic

tactactictactic

1	^(\2tic\|(tac))+$

Resources

Regex - Subdomains - Backreferences

2020-06-06

LeetCode - Algorithms - 172. Factorial Trailing Zeroes

Problem

172. Factorial Trailing Zeroes

Java

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        for (long i = 5; i <= n; i *= 5)
            count += n / i;
        return count;
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 36.6 MB, less than 31.99% of Java online submissions for Factorial Trailing Zeroes.

my solution

Accepted until 4th submission.

class Solution {
    public int trailingZeroes(int n) {
        if (n == 0)
            return 0;
        Double d = Math.floor((Math.log(n)) / (Math.log(5)));
        int m = d.intValue();
        int x = 0;
        for (int i = 1; i <= m; i++) {
            x += n / Math.pow(5, i);
        }
        return x;
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 1 ms, faster than 20.14% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 36.6 MB, less than 39.00% of Java online submissions for Factorial Trailing Zeroes.

my solution - 2

class Solution {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        int m = logarithm(n,5);
        int x = 0;
        for (int i = 1; i <= m; i++) {
            x += n / Math.pow(5, i);
        }
        return x;
    }
    
    private int logarithm(int n, int r) {
        return (n > r - 1) ? 1 + logarithm(n / r, r) : 0;
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 1 ms, faster than 19.86% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 38.6 MB, less than 5.16% of Java online submissions for Factorial Trailing Zeroes.

my solution - 3

class Solution {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        long x = 0;
        long p = 5;
        while (n >= p) {
            x += n / p;
            p *= 5;
        }
        Long l = new Long(x);
        return l.intValue();
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 1 ms, faster than 19.86% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 36 MB, less than 94.80% of Java online submissions for Factorial Trailing Zeroes.

my solution - 4

class Solution {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        int x = 0;
        for (long p = 5; n >= p; ) {
            x += n / p;
            p *= 5;
        }
        return x;
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 2 ms, faster than 19.86% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 38.1 MB, less than 10.66% of Java online submissions for Factorial Trailing Zeroes.

2020-06-05

LeetCode - Algorithms - 169. Majority Element

There are many solutions to an easy problem.

Problem

169. Majority Element

Java

sorting

import java.util.*;

class Solution {
    public int majorityElement(int[] nums) {
        final int len = nums.length;
        Arrays.sort(nums);
        return nums[len >> 1];
    }
}

Submission Detail

46 / 46 test cases passed.
Runtime: 1 ms, faster than 99.67% of Java online submissions for Majority Element.
Memory Usage: 42.9 MB, less than 72.59% of Java online submissions for Majority Element.

brute force

class Solution {
    public int majorityElement(int[] nums) {
        int half = nums.length >> 1;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i : nums) {
            Integer k = new Integer(i);
            if (map.containsKey(k)) {
                map.put(k, map.get(k)+1);
            }
            else {
                map.put(k, 1);
            }
        }
        int major = nums[0];
        for(Map.Entry<Integer, Integer> e : map.entrySet()) {
            if (e.getValue()>half) {
                major = e.getKey();
                break;
            }
        }
        return major;        
    }
}

Submission Detail

46 / 46 test cases passed.
Your runtime beats 37.72 % of java submissions.
Your memory usage beats 14.52 % of java submissions.

Boyer-Moore Voting Algorithm

class Solution {
    public int majorityElement(int[] nums) {
        int count=0;
        int candidate = nums[0];
        for(int num : nums) {
            if (count==0)
                candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;        
    }
}

Submission Detail

46 / 46 test cases passed.
Runtime: 1 ms, faster than 99.67% of Java online submissions for Majority Element.
Memory Usage: 42.2 MB, less than 99.93% of Java online submissions for Majority Element.

2020-06-01

The Rainbow

by Christina Rossetti

Boats sail on the rivers,
And ships sail on the seas;
But clouds that sail across the sky
Are prettier than these.

There are bridges on the rivers,
As pretty as you please;
But the bow that bridges heaven,
And overtops the trees,
And builds a road from earth to sky,
Is prettier far than these.

2020-05-30

HackerRank - Regex - Grouping and Capturing

Matching Word Boundaries

\b assert position at a word boundary.

Three different positions qualify for word boundaries :

Before the first character in the string, if the first character is a word character.
Between two characters in the string, where one is a word character and the other is not a word character.
After the last character in the string, if the last character is a word character.

Task

Found any match?

1	\b[aeiouAEIOU][a-zA-Z]*\b

Capturing & Non-Capturing Groups

()

Parenthesis () around a regular expression can group that part of regex together. This allows us to apply different quantifiers to that group. This allows us to apply different quantifiers to that group.

These parenthesis also create a numbered capturing. It stores the part of string matched by the part of regex inside parentheses.

These numbered capturing can be used for backreferences.

(?:)

(?:) can be used to create a non-capturing group. It is useful if we do not need the group to capture its match.

For Example

12 34 567 9

1	\s{1}(?=\d+)

Task

okokok! cya

1	(?:ok){3,}

Alternative Matching

Alternations, denoted by the | character, match a single item out of several possible items separated by the vertical bar. When used inside a character class, it will match characters; when used inside a group, it will match entire expressions (i.e., everything to the left or everything to the right of the vertical bar). We must use parentheses to limit the use of alternations.

Task

Mr.DOSHI

1	^(Mr\.\|Mrs\.\|Ms\.\|Dr\.\|Er\.)[a-zA-Z]{1,}$

Resources

Regex - Subdomains - Grouping and Capturing

贈衛八處士

Meeting With an Old Friend

Positive Lookahead

For Example

Task

Negative Lookahead

For Example

Task

Positive Lookbehind

For Example

Task

Negative Lookbehind

For Example

Task

Resources

Problem

Relevant problem

Java

Binary Search strategy

Submission Detail

Complexity Analysis

Time Complexity

Space Complexity

Matching Same Text Again & Again

For Example

Task

Backreferences To Failed Groups

Capturing group that match nothing

Capturing group that didn’t participate in the match at all

Task

1

2

Branch Reset Groups

Task

Forward References

Task

Resources

Problem

Java

solution of geeksforgeeks © Count trailing zeroes in factorial of a number

Submission Detail

my solution

Submission Detail

my solution - 2

Submission Detail

my solution - 3

Submission Detail

my solution - 4

Submission Detail

Problem

Java

sorting

Submission Detail

brute force

Submission Detail

Boyer-Moore Voting Algorithm

Submission Detail

Matching Word Boundaries

Task

Capturing & Non-Capturing Groups

()

(?:)

For Example

Task

Alternative Matching

Task

Resources