Leetcode 1 - 10

I am now working on solving all the questions from leetcode. I will write a short description for each question and all the code can be found on https://github.com/Jeky/leetcode.

1. Two Sum

The simple answer is for each number, we try to find another number such that they add up to a specific target. This algorithm is O(n^2). I used an O(n) algorithm which is for each number, we first try to find if there is another number such that they can be summed to target. If there is this number, we return the indexes of these two numbers, otherwise we check next number. The finding step is O(1) based on a set searching (The worst case of this is O(n)).

Code

2. Add two numbers

This question is so easy if using recursion. We need to be careful of 1. the end of linked list; 2. carry when adding.

Code

3. Longest Substring Without Repeating Characters

This problem is to find the longest substring without repeating. So we can go through the string, adding each characters into an array. Once we find there is a character that has already been added in the array, we save the current length of array and remove characters from the array till current character has been removed.

In the answer, I converted all the characters into integers to speed up comparison.

Code

4. Median of Two Sorted Arrays

This is the first question marked as HARD. In fact I didn’t solve this question all by myself. I followed this answer which gave really awesome anwser and explanation of this question.

Code

5. Longest Palindromic Substring

Another simple question about substring. All you need is to search longest palindromic substrings starting at each location on string. Make sure that the length of palidromic substring can be either even or odd.

Code

6. ZigZag Conversion

The example of this question is misleading. If you can convert the example into the following format,

P   A   H   N
 A P L S I I G
  Y   I   R

then you can find the relation between the index before converting and the converted index.

1      5      9         13
 2 4    6 8    10  12     14
  3      7       11

Code

7. Reverse Integer

This is the easiest one in the first 10 questions. Just be careful about negitive value and overflow.

Code

8. String to Integer (atoi)

Another easy question. Try to think about every possible input case, including blanks and letters. Overflow need to be checked as well. (However, I solved all the questions in Python, in which overflow of an integer is not possible.)

Code

9. Palindrome Number

Another integer reversion quesion.

Code

10. Regular Expression Matching

A hard one. At first I tried to solve this problem by recursion and forward searching. It turned out to be time exceeding on some regular expressions.

a*a*a*a*a*a*a*a*

This is because for each wildcard, we will create two leaves for different matching.

Then I converted the recursion into stack because I thought this is just because recursion is really slow in Python. After converting the problem remained same. So I found another way, changing searching direction into backward, to speed up the algorithm.

Code

Read More

Bash on Windows

I recently bought a new PC and changed my programming environment from Mac to Ubuntu. Since Microsoft announced Linux Subsystem for Windows in March, which can now be used in the previous build of Win 10, I think it is the time to move back to Windows now.

Install Bash on Windows 10

To get started, you first need to enroll windows insider program and choose fast ring. After you get your latest update installed, you will find a new feature named Windows Subsystem for Linux (Beta) in Control Panel - Programs and Features - Windows Features.

Select to install bash on windows

After restart, you can search for “bash” and install your bash on windows. Several minutes after downloading, you can type your username and password and your bash on windows is ready.

Type your username and password

Is it really nice?

It seems quite wonderful at first glance because this is actually a Linux (Ubuntu) running on Windows. You can use apt-get to install packages, run your python or compile c++ project using g++ and cmake. Somebody even achieved to run GUI based Linux applications. I tried to switch from bash to zsh and succeeded installing oh-my-zsh.

Oh My Zsh

It seems like we can now delete Ubuntu and only use Windows. However, I found that this subsystem is still a toy with bugs everywhere. I listed the problems I have encountered below.

  • It is hard to install JDK 8. It seems like the latest version of 1.8 cannot work on this subsystem, so try JDK 7 or JDK 8u5. You can follow install Oracle JDK 8 to install JDK 8u5. You may need use sudo in some steps to solve the permission problems.

  • You cannot use ping/ifconfig because of socket problem.

  • NodeJS can be installed but npm cannot work due to shasum problem. (This problem has been fixed in latest preview version).

  • Cuda cannot be installed. (Cuda Issue)

By now I can only say Python works pretty good on this subsystem. I am not sure if there are some problems when using numpy/scipy/sklearn/theano and other machine learning/deep learning libraries. And if you are still interested in Bash on Windows after reading all this blog, you can visit issues for more details of issues and support the features you want by vote for features.

Read More

A Brand New Start

I have just graduated and earned my master degree. This is a brand new start for me. It took a little longer time to finish my study because I changed my thesis topic in the second year.

Now I have a lot of time which can be spent on what I really want to do.

Read More