billryan/algorithm-exercise

Data Structure and Algorithm notes. 数据结构与算法/leetcode/lintcode题解/

Data Structure and Algorithm/leetcode/lintcode

This book is notes about learning data structure and algorithm. It was written in Simplified Chinese but other languages such as English and Traditional Chinese are also working in progress. Contributions are welcome!

• English, rarely updated
• 简体中文, frequently updated
• 繁體中文, rarely updated

Introduction

1. Part I is some brief introduction of basic data structures and algorithm, such as linked lists, stack, queues, trees, sorting.
2. Part II is the analysis and summary of programming problems, and most of the programming problems come from https://leetcode.com/, http://www.lintcode.com/, http://www.geeksforgeeks.org/, http://hihocoder.com/, https://www.topcoder.com/.
3. Part III is the appendix of resume and other supplements.

This project is hosted on https://github.com/billryan/algorithm-exercise and rendered by GitBook. You can star the repository on the GitHub to keep track of updates. Another choice is to subscribe channel #github_commit via Slack https://ds-algo.slack.com/messages/github_commit/.

Feel free to access http://slackin4ds-algo.herokuapp.com with Slack invite automation.

You can view/search this document online or offline, feel free to read it. :)

• Online(Rendered by GitBook): https://algorithm.yuanbin.me
  • Site Search via Google: keywords site:algorithm.yuanbin.me
  • Site Search via Algolia: Click Type to search on the top left corner of webpages
• Offline(Compiled by GitBook on Travis-CI): ePub, PDF, MOBI

License

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License. To view a copy of this license, please visit http://creativecommons.org/licenses/by-sa/4.0/

To Do

• add multiple languages support
• add implementations of Python, C++, Go and Java code
• add time and space complexity analysis
• add proper Chinese fonts for PDF output

algorithm-exercise's Issues

rename zh-cn with zh-hans

According to GitbookIO/gitbook#926, the $lang zh-cn have been removed from Gitbook, we should use zh-hans instead.
zh-tw should be zh-hant but gitbook does not support now.

• Why use the language attribute?
• Language tags in HTML and XML

bug

链表中的快慢指针有问题，fast = fast.next.next吧，而不是fast = fast.next

使用一个指针的快排，代码分析部分有个问题

笔记：basics_sorting/quick_sorting.md

比较alist[i]和alist[l]时只能使用<而不是<=! 因为只有取<才能进入收敛条件，<=则可能会出现死循环，因为在=时第一个元素可能保持不变进而产生死循环。

我分析写 <= 并不会出现死循环，用这种方式提交了 leetcode 215 题 Kth Largest Element in an Array, 也能通过～

I was planned to do similar thing, but ...

看了 lz 的 repo，觉得我的可以不用弄了，逐渐把我笔记和代码里有用的东西搬运过来。

Error 404 for some pages in https://algorithm.yuanbin.me/zh-hans

The following pages are returning 404 errors.
https://algorithm.yuanbin.me/zh-hans/linked_list/delete_node_in_the_middle_of_singly_linked_list
https://algorithm.yuanbin.me/zh-hans/basics_algorithm/counting_problem
https://algorithm.yuanbin.me/zh-hans/dynamic_programming/egg_dropping_puzzle
https://algorithm.yuanbin.me/zh-hans/data_structure/kth_smallest_number_in_sorted_matrix
https://algorithm.yuanbin.me/zh-hans/problem_misc/n_queens
https://algorithm.yuanbin.me/zh-hans/problem_misc/n_queens_ii
https://algorithm.yuanbin.me/zh-hans/appendix_ii_system_design

add unicode font family and webfonts in gitbook web version

The font family used in gitbook web version are unfriendly to unicode fonts such as Chinese character.

The font-family is set by default as

font-family:"Open Sans","Clear Sans","Helvetica Neue",Helvetica,Arial,sans-serif;

which looks ugly on Windows platform. I should use some extra plugin to solve this problem.

简单来讲就是目前的 Gitbook 网页版生成的中文字体显示效果不好，OS X/Linux 下还算可以，Windows 下的渲染效果则惨不忍睹。

另外对于非中文的字体，计划使用 Webfont 来解决，尤其是代码部分，使用source code pro等字型将大大提高代码的可读性和观赏性。Reference 中的 yahei 还算凑合，不过我想将它扩充到支持 Windows/Linux/OS X/Android/iOS 等多个平台，而不仅仅只是对 Windows 用户用好。嗯，这样的话就得写 js 插件了，过些天找好实习了就来 fork 一个，有略懂前端的小伙伴愿意协作的咩？

Reference

• zhangzhb3/gitbook-plugin-yahei
• setkyar/gitbook-plugin-unicodecss
• sofish/typo.css - 一致化浏览器排版效果，构建最适合中文阅读的网页排版
• Create a plugin | Gitbook - 发布插件用

zh-hans/Summary 路径错误

zh-hans/faq 中已经没有 contributors.md ，建议 Summary 中删除

add shared-files for Multilingual

Gitbook do not render the files outside language folders now, a workaround for this issue is found in GitbookIO/gitbook#744.

Now you can refer an image or docs like this:

![Queen](../../shared-files/images/8-queens.png)

The workaround is broken for EPUB/PDF/MOBI, replace with

![Queen](https://raw.githubusercontent.com/billryan/algorithm-exercise/master/shared-files/images/8-queens.png)

add site search by swiftype

I wrote a site search plugin for gitbook, which can be found in https://github.com/billryan/gitbook-plugin-swiftype. It works well when loading a new page or refreshing the old page, but it does not work for 'page.change' event in Gitbook. Anyone can give a hint?

Misspelling of exercise!

Misspelling of exercise, the repo name algorithm-excercise should be algorithm-exercise. %>_<%

use hugo instead, gitbook is too slow to build

Long term schedule

repository size becomes too large[900MB+]

I did use bfg to shrink the size of this repo local, but it seems like it did not work at all in the GitHub side. Anyone has a clue? Do I need remove this repo and create another new one based on my local history?

P.S. 我明天放寒假回家，上网和收发邮件不太方便，其他 Collaborator 可以将合适的 Pull Request 合并到 master。

sitemap generation

Sitemap.xml is an optimization for search engine. Gitbook does not provide sitemap support now. I have little knowledge about Javascript, so I wrote a sitemap generation helper with Python.

Implementation details

1. git ls-tree and git log, we can get the files in git repo and its latest modified time.
2. filter .md source files and exclude/replace some special markdown files.
3. replace .md with .html.
4. generate sitemap.xml with Jinja2 template

algorithm-exercise/sitemap_gen.py

我错了

咱两的思路不一样
class NewNode:
def init(self, val):
self.value = val
self.next = next

def judge_circle(self, head):
    slow = head
    fast = head
    while slow and fast:
        fast = fast.next.next
        slow = slow.next
        if fast == slow:
            break
    if fast and slow and (fast == slow):
        return True
    else:
        return False

我的就直接 fast = fast.next.next了

add proper Chinese fonts for PDF

The Chinese fonts used in PDF version is unreadable. Proper Chinese fonts such as [文泉驿]([Habitat: MicroHei]%28http://wenq.org/wqy2/index.cgi?MicroHei%29) would be better. I do not find the way how to modify the Chinese fonts rendered for PDF, anybody can give a hint?

目前的 PDF 版字体巨丑无比，简直不忍直视！最好的办法就是等官方更新他们的系统字体了，本地测试生成的字体还不错。如果要离线查看本文档，目前还是比较推荐 epub 和离线的 html。

目前已使用 travis-ci.org 生成PDF/EPUB/HTML/MOBI，可以自行添加字体。将生成的 PDF/EPUB/MOBI/HTML 自动同步到七牛上，方便下载。

Reference

• 開源的免費中文字型－文泉驛和思源黑體 | MagicLen
• Habitat: MicroHei
• Broken Unicode Font in PDF version · Issue #532 · GitbookIO/gitbook

add sections automatically for gitbook SUMMARY.md from *.md source files

Add new sections by GitbookIO editor is quite simple, but sometimes you may forget to add sections in SUMMARY.md.

It is easy to parse the title of source .md files and add it to the appropriate chapter position. I will implement this feature with Python.

add new problem with markdown

I implemented this feature via Flask ==> https://github.com/billryan/heroku4ds-algo

You can access it via https://heroku4ds-algo.herokuapp.com/

add multilingual selection plugin for gitbook

Since https://github.com/GitbookIO/plugin-versions rely on GitBook API and is more suitable for multi-version software API, we need a multilingual selection plugin for gitbook pages.

Some JS or CSS we can refer:

• GitbookIO/plugin-versions
• rtCamp/gitbook-plugin-edit-link - make use of gitbook.toolbar.createButton API
• site/header.styl - hexojs/site - CSS for lang-select
• Plugins | GitBook Developers

deploy static files(PDF, EPUB, MOBI) in GitHub and GitCafe

Static files such as PDF are deployed in Gitbook and my DigitalOcean VPS, but it is a bit complex to maintain the scripts and difficult to access from mainland China.

The new architecture will be:

• GitHub: source markdown files and static files output(another branch)
• Travis CI: compile and deploy server
• GitCafe: mirror of GitHub(speed up for mainland China)
• Gitbook: html webpages

目前的 PDF 静态文件是通过自己的 VPS 和 Travis 编译输出的，实测自己的 VPS 性能还是比不过 Travis. 使用思源黑体后 PDF 占用字节空间达30MB+, 国内用户访问这些国外网站速度都非常慢，放在七牛云存储上的文件因为流量太大把我的免费额度快用完了... 因此想将静态文件直接放到 GitHub(主要用于国外用户) 和 GitCafe(镜像 GitHub 并主要用于服务国内用户)，为避免污染 master 分支，这些静态文件输出都将放到另一个分支。

Reference

• Migrating from legacy to container-based infrastructure - Travis CI
• hexo-deployer-git/deployer.js

add tabs-navigation?

有没有必要加个tab navigation? 类似九章上面的，http://www.jiuzhang.com/solutions/anagrams/。
把C++、python、java代码分tab显示， 我觉得这样会让页面更简洁一点

RSS feed for update

Currently you can subscribe https://github.com/billryan/algorithm-exercise/commits/master.atom for updates. Since the atom feed only shows commits title without the page contents, I decided developing a simple GitHub RSS feed generator for diff and full-text. You can refer Updates - Data Structure and Algorithm for more details.

GitHub RSS project: https://github.com/billryan/github-rss

Undefined names: ‘title’ and ‘metadata’ in ojhtml2markdown.py

flake8 testing of https://github.com/billryan/algorithm-exercise on Python 3.7.1

$ flake8 . --count --select=E901,E999,F821,F822,F823 --show-source --statistics

./scripts/ojhtml2markdown.py:22:26: F821 undefined name 'title'
        content = '# ' + title
                         ^
./scripts/ojhtml2markdown.py:23:36: F821 undefined name 'metadata'
        yaml_content = YamlContent(metadata, content)
                                   ^
2     F821 undefined name 'title'
2

vote for book cover

It is a long time since I decided to design this ebook cover. After some discussion with @niangaotuantuan , I designed 4 different cover pictures for this useful algorithm notes. @kokdemo contributed his new design(No.1). Which one do you like best? I prefer the second one. :)

No.1 - Cover without characters

No.2 - Cover with transparent binary bits

No.3 - handwritten fonts with black

Serious and Powerful.

No.4 - handwritten fonts with blue

Graceful and vivid.

No.5 - artbrush fonts with black

Heavy.

No.6 - artbrush fonts with blue

how did you sync to qiniu?

我看了 travis 文件，没有看到同步七牛的部分……整个 repo 里有一个 qiniu_sync.json，但是里面的密钥肯定不能用。特别想知道你怎么把自动同步到了七牛 😄 。

add problem description automatically from url link

It is a new feature about writing style of problem description. Add problem description is a tedious work.
As a programmer, we should avoid writing monotonous, repetitive tasks. Here it comes! parse_source.py

The new writing style of problem can be found in Gray Code.

Usage

python scripts/parse_source.py problem_url

You can redirect the standard output to your clipboard or pbcopy or some file in your disk.

Example

python scripts/parse_source.py http://www.lintcode.com/en/problem/word-ladder/

You will get the following text from the standard output.

Given two words (_start_ and _end_), and a dictionary, find the length of
shortest transformation sequence from _start_ to _end_, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

#### Example

Given:  
_start_ = `"hit"`  
_end_ = `"cog"`  
_dict_ = `["hot","dot","dog","lot","log"]`  

As one shortest transformation is `"hit" -> "hot" -> "dot" -> "dog" -> "cog"`,  
return its length `5`.

#### Note

  * Return 0 if there is no such transformation sequence.
  * All words have the same length.
  * All words contain only lowercase alphabetic characters.

Paste or redirect to your markdown file, have fun with this new feature. 👍