Bowen's Tech Blog

Overview

Queue and stack are just like a store. You just want to put and pick the items one by one. The time complexity of put and pick is O(1)

Python makes queue and stack easier because we can use list to finish the functions of queue and stack.

1
2
3
4
5
6
7
8
9

my_queue = []
my_queue.append(4)
my_queue.append(5)
print(my_queue.pop(0))    # we get 4

my_stack = []
my_stack.append(4)
my_stack.append(5)
print(my_stack.pop())    # we get 5

Samples

Travel the tree

No.94 - Binary Tree Inorder Traversal

No.103 - Binary Tree Zigzag Level Order Traversal

Pair Match

No.20 - Valid Parentheses

Store the data in order[Some special questions]

No.42 - Trapping Rain Water

To be continued…

Overview

1
2
3
4

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

• Add a node into LinkedList is O(1).
• Remove a node from LinkedList is O(1) but search it is O(n).

Samples

Traversing and merge

No.2 - Add Two Numbers
Two pointers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    p1, p2 = l1, l2
    carry = 0
    ans = ListNode(0)
    p = ans
    while p1 != None and p2 != None:
        sum_ = p1.val + p2.val + carry
        carry = 1 if sum_ >= 10 else 0
        sum_ = sum_ if sum_ < 10 else sum_ - 10
        p.next = ListNode(sum_)
        p, p1, p2 = p.next, p1.next, p2.next
    
    p1 = p1 if p1 != None else p2

    while p1 != None and carry:
        sum_ = p1.val + carry
        carry = 1 if sum_ >= 10 else 0
        sum_ = sum_ if sum_ < 10 else sum_ - 10
        p.next = ListNode(sum_)
        p, p1 = p.next, p1.next
    
    p.next = p1
    if carry == 1:
        p.next = ListNode(1)
    
    return ans.next

No.21 - Merge Two Sorted Lists
Several pointers.

No.23 - Merge k Sorted Lists
Priority queue

No.328 - Odd Even Linked List

Other basic function

No.237 - Delete Node in a Linked List

1
2
3
4
5
6
7

def deleteNode(self, node):
    """
    :type node: ListNode
    :rtype: void Do not return anything, modify node in-place instead.
    """
    node.val = node.next.val
    node.next = node.next.next

No.138 - Copy List with Random Pointer
Deep Copy

Recursively

No.206 - Reverse Linked List

No.234 - Palindrome Linked List

Combine with other data strucure

No.19 - Remove Nth Node From End of List
With List

No.206 - Reverse Linked List
Stack

No.141 - LinkeList List Cycle
HashTable

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

def hasCycle(self, head):
    """
    :type head: ListNode
    :rtype: bool
    """
    p = head
    se = set()
    while(p != None):
        if(p in se):
            return True
        else:
            se.add(p)
            p = p.next
    return False

No.160 - Intersection of Two Linked Lists
HashTable

No.138 - Copy List with Random Pointer
HashTable

Data structure of string.

Overview

There are 7 main sorting algorithm, which are also connected with other conceptions. Will be finished in the future.

Insert sort

$O(n^2)$

• Insert the value into a sorted list - swap with element of bottom one by one

Hill sort

$O(nlog(n))$

Select sort

$O(n^2)$

• Choose the smallest/largest element and put into the sorted array

Heap sort

$O(nlog(n))$

• Put items into heap, and pop one by one out
• Use heap can find the top K values easily. Create a heap with length of K, put items into it one by one

Bubble sort

$O(n^2)$

• Choose a value, if it is larger than the next one, replace them, until this value arrive the boundary of end
• Update the boundary of end, do the previous choosing and moving steps again

Quick sort (binary sort)

$O(nlog(n))$

• Choose a pivot, put all values smaller than pivot into left, all values larger than pivot into right
• Do quick sort for left and right
• Connect left, pivot and right

Merge sort

$O(nlog(n))$

• Divide a list into left and right
• Do the merge sort for left and right
• Put the sorted left and right together

Some functions in Python

• sorted(a, key=lambda x:x[0])

Some samples

• Find the 0-Kth largeset elements
  • Heap O(klong(n))
• Find the Kth largeset element
  • Move the smaller elements to left, larger elemetns to right, until the right part only have K elements

Reference

[1] https://www.cnblogs.com/ktao/p/7800485.html

Some common used docker commands.

Tree is a basic data structure. The most popular tree is the binary tree, which has a left child and a right child. The exercise usually gives you the root node of the tree. The basic method to solve a tree problem is recursive.

Traverse the tree

Iteration

1
2
3
4
5
6

openlist = [root]
while len(openlist) > 0:
    node = openlist.pop()	# openlist.pop(0) if you want BFS 
    check(node) 
    openlist.append(node.left)
    openlist.append(node.right)

Recursive

1
2
3
4

def check_tree(node):
    if node:
        check_tree(node.left)
        check_tree(node.right)

The above two ara both DFS(Deep First Search), in order to achieve the BFS(Breadth First Search), in other means, traverse the tree layer by layer, we need to use a dictionary to store the node

1
2
3
4
5
6
7
8
9
10

dic_tree = {}

def check_tree_breadth(node, depth=1):
    if node:
        if depth not in dic_tree:
            dic_tree[depth] = [node.val]
        else:
            dic_tree[depth].append(node.val)
        check_tree_breadth(node.left, depth+1)
        check_tree_breadth(node.right, depth+1)

Check the leaf

1
2
3
4
5
6
7
8
9

leafs = []

def check_leaf(node):
    if node:
        if not node.left and not node.right:
            leafs.append(node.val)
        else:
            check_leaf(node.left)
            check_leaf(node.right)

Calculate the depth

Iteration

Establish a list to collect the tuple like (node: depth)

Recursive

1
2
3
4
5

def get_depth(node):
    if node:
        return 1 + max(get_depth(node.left), get_depth(node.right))
    else:
        return 0

Check the path

1
2
3
4
5
6
7
8
9

paths = []

def check_path(node, path=[]):
    if node:
        path.append(node.val)
        check_path(node.left, path.copy())
        check_path(node.right, path.copy())
    else:
        paths.append(path)

Fenwick Tree

Fenwick tree is also called Binary Indexed Tree. This kind of data structure can do the calculation of sum from 0 to ith of a list very efficiently.

It can also be used to calculate the frequency. Below is a code used to calculate the number of values from 0 to i.

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

class fenwickTree:
    def __init__(n):
        self.array = [0] * n

    def add(i):
        while i < len(self.array):
            self.array[i] += 1
            i += i & -i

    def query(i):
        ans = 0
        while i >= 0:
            ans += self.array[i]
            i -= i & -i
        return ans

Relevant application is in Leetcode No.315.

Heap

Heap is a useful data structure which can store the elements in order. In Python, there is a built in heap library called Heapq.

No.253 - Meeting Room

• Make the start time of meeting in order
• Use heap to store the end time of each meeting
• When the meeting with earliest end time is smaller than the coming meeting with earliest start time, pop that meeting, otherwise not. Then heappush the new end time of the new coming meeting.

本文将简述.NET（包括.NET Framework, .NET Core等）和编程语言C#之间的关系。

Basic Information of .NET

Features of .NET

.NET的命名就是因为.net是互联网中比较通用的一个域名后缀，因此.NET本身也是和通用相关的。

• 跨语言：即只要是面向.NET平台的编程语言((C#、Visual Basic.NET、C++/CLI、Eiffel、F#、IronPython、IronRuby、PowerBuilder、Visual COBOL 以及 Windows PowerShell))，用其中一种语言编写的类型可以无缝地用在另一种语言编写的应用程序中的互操作性。
• 跨平台：一次编译，不需要任何代码修改，应用程序就可以运行在任意有.NET框架实现的平台上，即代码不依赖于操作系统，也不依赖硬件环境。

.NET Technical Framework System

.NET是一个微软搭造的开发者平台，它主要包括：

1. 支持(面向)该平台的编程语言(如C#、Visual, Basic、C++/CLI、F#、IronPython、IronRuby…)
2. 用于该平台下开发人员的技术框架体系(.NET Framework、.NET Core、Mono等)，
   1. 定义了通用类型系统，庞大的CTS体系
   2. 用于支撑.NET下的语言运行时的环境：CLR
   3. NET体系技术的框架库FCL
3. 用于支持开发人员开发的软件工具(即SDK，如VS2017、VS Code等)

Common Type System (CTS)

在.NET的三部分内容中，编程语言和软件工具我们都比较清楚，那么技术框架体系中的具体内容都是什么呢？

• CLS: (Common Language Specification) 公共语言规范, 在面向.NET开发中，语言互操作的标准规范
• CTS: (Common Type System) 公共类型系统, 包含：
  • 建立用于跨语言执行的框架。
  • 提供面向对象的模型，支持在 .NET 实现上实现各种语言。
  • 定义处理类型时所有语言都必须遵守的一组规则(CLS)。
  • 提供包含应用程序开发中使用的基本基元数据类型（如 Boolean、Byte、Char 等）的库。
  • 支持CTS，那么我们就称它为面向.NET平台的语言
    CLI（Common Language Infrastructure），是微软将CTS等内容提交给国际组织计算机制造联合会ECMA的一个工业标准。

Common Language Runtime (CLR)

• CLR：.NET虚拟机
  • CLR是.NET类型系统的基础，所有的.NET技术都是建立在此之上
  • 在我们执行托管代码之前，总会先运行这些运行库代码，通过运行库的代码调用，从而构成了一个用来支持托管程序的运行环境，进而完成诸如不需要开发人员手动管理内存，一套代码即可在各大平台跑的这样的操作。
  • 这套环境及体系之完善，以至于就像一个小型的系统一样，所以通常形象的称CLR为”.NET虚拟机”。那么，如果以进程为最低端，进程的上面就是.NET虚拟机(CLR)，而虚拟机的上面才是我们的托管代码。换句话说，托管程序实际上是寄宿于.NET虚拟机中
  • C# 编写的程序如果想运行就必须要依靠.NET提供的CLR环境来支持
• CLR宿主进程：容纳.NET虚拟机的进程，该程序称之为运行时主机

下图是代码编译和运行的流程

Framework Class Library (FCL)

框架库是一些用于描述数据类型的基础类型。比如Object不仅是C#语言的类型根、还是VB等所有面向.NET的语言的类型根，它是整个FCL的类型根。同时.NET的框架库有单继承的特点。

• BCL(Base Class Library)基础类库
  • 通过.NET语言下编写的一些类库
  • 多都包含在System命名空间下。
  • 包含：基本数据类型，文件操作，集合，自定义属性，格式设置，安全属性，I/O流，字符串操作，事件日志等的类型
• FCL(Framework Class Library)框架类库
  • FCL中大部分类都是微软通过C#来编写的。
  • 用于网站开发技术的 ASP.NET类库，该子类包含webform/webpage/mvc，
  • 用于桌面开发的 WPF类库、WinForm类库
  • 用于通信交互的WCF、asp.net web api、Web Service类库等等

.NET Implementations

• .NET Framework
  • A .NET implement coupled with Windows System
  • Only support different version of Windows
• .NET Core
  • A open source .NET implementation for several desktop OS including Windows, macOS, and Linux, but NOT support mobile OS like Android or iOS.
  • Include a cross-platform CoreCLR
  • Implement subset of the .NET Framework library (decouple with Windows), and add new features (for common usage of different OS)
    • e.g. Not include WPF which coupled with Windows
    • UWP: Specific for Windows System
      • Cross Devices but only runs in Windows.
  • Better in the functions than Mono
• Xamarin
  • A open source .NET implementation by for several OS including Android、IOS and macOS
  • It is based on Mono BCL. Unity3d adopts this framework. It will compile the C# code to IL, and compile to naive code according to the target platform
  • Higher efficiency than .NET Core
• .NET Standard
  • A set of fundamental APIs that all.NET implementations should implement
  • Cannot build the real program, but serve as the library for .NET implementations above

C# and .NET

C# is the programming language targeted to .NET. The version of C# is updated with the update of .NET implementations.

Reference

[1] https://www.cnblogs.com/1996V/p/9037603.html
[2] https://blog.csdn.net/MePlusPlus/article/details/76242330
[3] .NET Standard

Overview

1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
2. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
3. Combine the solutions to the subproblems into the solution for the original problem.

Samples and exercise

Binary search

Decrease the time from $O(n)$ to $O(log(n))$

No.4 Median of Two Sorted Arrays
This exercise need we use binary search to find the proper value.

Majority elements

If an element is the majority element(appears more than n/2 times), it should be the majority element in the left half sequence or in the right sequence, otherwise it cannot be the majority element.

Quick sort

Binary sort.

Merge sort

Merge two in-order sequence to a whole sequence. The best time is $O(nlog(n))$

No.23 Merge k Sorted Lists

Number of inverse pairs

Reference

[1] https://blog.csdn.net/xlinsist/article/details/79198842
[2] https://blog.csdn.net/qq_29793171/article/details/80057088

Summary for some exercise.