0%

[3] Longest Substring Without Repeating Characterss

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.util.Set;

/*
* @lc app=leetcode id=3 lang=java
*
* [3] Longest Substring Without Repeating Characters
*
* https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
*
* algorithms
* Medium (29.66%)
* Likes: 8021
* Dislikes: 492
* Total Accepted: 1.4M
* Total Submissions: 4.6M
* Testcase Example: '"abcabcbb"'
*
* Given a string, find the length of the longest substring without repeating
* characters.
*
*
* Example 1:
*
*
* Input: "abcabcbb"
* Output: 3
* Explanation: The answer is "abc", with the length of 3.
*
*
*
* Example 2:
*
*
* Input: "bbbbb"
* Output: 1
* Explanation: The answer is "b", with the length of 1.
*
*
*
* Example 3:
*
*
* Input: "pwwkew"
* Output: 3
* Explanation: The answer is "wke", with the length of 3.
* ⁠ Note that the answer must be a substring, "pwke" is a
* subsequence and not a substring.
*
*
*
*
*
*/

// @lc code=start
class Solution {
public int lengthOfLongestSubstring(String s) {
int slow = 0;
int fast = 0;
Set<Character> charSet = new HashSet();
int res = 0;

if (s == null || s.length() == 0) {
return res;
}

while (fast < s.length()) {
char fChar = s.charAt(fast);
if (charSet.contains(fChar)) {
char sChar = s.charAt(slow);
charSet.remove(sChar);
slow++;
} else {
charSet.add(fChar);
res = Math.max(res, fast - slow + 1);
fast++;
}
}

return res;
}
}
// @lc code=end

[1382] Balance a Binary Search Tree

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import java.util.List;
/*
* @lc app=leetcode id=1382 lang=java
*
* [1382] Balance a Binary Search Tree
*
* https://leetcode.com/problems/balance-a-binary-search-tree/description/
*
* algorithms
* Medium (74.37%)
* Likes: 62
* Dislikes: 12
* Total Accepted: 6K
* Total Submissions: 8K
* Testcase Example: '[1,null,2,null,3,null,4,null,null]'
*
* Given a binary search tree, return a balanced binary search tree with the
* same node values.
*
* A binary search tree is balanced if and only if the depth of the two
* subtrees of every node never differ by more than 1.
*
* If there is more than one answer, return any of them.
*
*
* Example 1:
*
*
*
*
* Input: root = [1,null,2,null,3,null,4,null,null]
* Output: [2,1,3,null,null,null,4]
* Explanation: This is not the only correct answer, [3,1,4,null,2,null,null]
* is also correct.
*
*
*
* Constraints:
*
*
* The number of nodes in the tree is between 1 and 10^4.
* The tree nodes will have distinct values between 1 and 10^5.
*
*/

// @lc code=start
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

/**
* 1. traverse the tree, in-order 2. rebuild the tree
*/
class Solution {
List<Integer> inOrderList = new ArrayList();

public TreeNode balanceBST(TreeNode root) {
inOrderTraverseNode(root);
return buildBalancedTree(0, inOrderList.size() - 1);
}

public void inOrderTraverseNode(TreeNode current) {
if (current == null) {
return;
}
inOrderTraverseNode(current.left);
inOrderList.add(current.val);
inOrderTraverseNode(current.right);
}

public TreeNode buildBalancedTree(int start, int end) {
if (start > end) {
return null;
}
int mid = start + ( end - start ) / 2;
// Note that (start + end) / 2 might cause some integer overflow issue
TreeNode currentNode = new TreeNode(inOrderList.get(mid));
currentNode.left = buildBalancedTree(start, mid - 1);
currentNode.right = buildBalancedTree(mid + 1, end);
return currentNode;
}
}
// @lc code=end

Segment Tree

线段树是一棵二叉树, 树中的每一个非叶子结点表示了一个区间[a,b].
该节点的左儿子表示区间[a,(a+b)/2], 右儿子表示[(a+b)/2+1,b].

Feature

  • 是一个满二叉树(Full Binary Tree), 及每个节点的子节点个数为0或2.
  • 是一个平衡树, 深度不超过log(L), L是区间长度
  • 非叶子节点长度>1, 叶子节点长度=1

Application

线段树主要用于高效解决连续区间的动态查询问题. 比如某些数据可以按区间进行划分, 按区间动态进行修改, 而且还需要按区间多次进行查询, 那么使用线段树可以达到较快查询速度.

例如

  • 对区间求sum
  • 对区间求Max/Min
  • 对区间求Count
Read more »

用hashmap和双向链表实现的LRU.

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class LRUCache {
Map<Integer, DListNode> map;
DListNode head;
DListNode tail;
int cap;
public LRUCache(int capacity) {
cap = capacity;
map = new HashMap<>();
head = new DListNode(0,0);
tail = new DListNode(0,0);
head.next = tail;
tail.prev = head;
}

public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
DListNode listNode = map.get(key);
remove(listNode);
addHead(listNode);
return listNode.val;
}

public void put(int key, int value) {
if (map.containsKey(key)) {
DListNode listNode = map.get(key);
listNode.val = value;
remove(listNode);
addHead(listNode);
} else {
DListNode listNode = new DListNode(key, value);
addHead(listNode);
if (map.size() == cap) {
map.remove(tail.prev.key);
remove(tail.prev);
}
map.put(key, listNode);
}
}

private void remove(DListNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}

private void addHead(DListNode listNode) {
DListNode tmp = head.next;
head.next = listNode;
listNode.next = tmp;
tmp.prev = listNode;
listNode.prev = head;
}
}

class DListNode {
int key;
int val;
DListNode next;
DListNode prev;
public DListNode(int k, int v) {
key = k;
val = v;
}
}

Topological sort

定义: 对一个有向无环图(DAG)G进行拓扑排序, 是将G中所有顶点排成一个线性序列, 使得图中任意一对顶点u和v, 若边(u,v)∈E(G), 则u在线性序列中出现在v之前.

DFS Solution

用dfs的搜索的方法, 维护一个linkedlist和visited set, 保证每次加入到list中时, 可访问的节点都已经在list中.

Read more »

图的表示

LeetCode上给出了一个链接, 可以参考一下. 这里讲两个最常见的表示方法, Adjacency Matrices和Adjacency Lists.

Adjacency Matrices

Adjacency Matrices用一个二维矩阵A[][]表示, 在无向图中, A[i][j] = -1表示节点i和j之间无edge, A[i][j] = 1表示有边, 无向图中矩阵是对称的. 在有向图中, A[i][j] = 1表示从i到j存在有向边. 在weighted edge list中, A[i][j] = k用具体的数字表示从i到j的边的权重.

Read more »

K Sum 系列

通用模型:
给定一个数组长度为N, 找出其中K个数字使得和为S, 求出所有可能且不重复的组合.
给定一个数组长度为N, 找出其中K个数字使得和尽可能接近S, 求出最接近的组合.

sum系列的实质是dfs + backtrack, 只是在特性的环境下面(K = 2,3,4)可以使用诸如hashmap和two pointer的技巧来解决.

Read more »

REST = REpresentational State Transfer.
REST API is resource based rather than action based.

Constrains for REST Architecture

Client-Server

RESTful architecture is a client-server architecture. A client won’t always have direct connections with the server, assets or resources.

Uniform Interface

using noun as the resources and using http verbs as the actions on the resources.

Here are frequently used HTTP Requests:

GET
Read a specific resource (by an identifier) or a collection of resources.

POST
Create a new resource. Also a catch-all verb for operations that don’t fit into the other categories.

PUT
Update a specific resource (by an identifier) or a collection of resources. Can also be used to create a specific resource if the resource identifier is known before-hand.

DELETE
Remove/delete a specific resource by an identifier.

Stateless

the server contains no client states, which means, each request has enough

Cacheable

Server responses or representations are cacheable. So the response must implicitly or explicitly define themselves as cacheable.

Layered System

Array Duplication

在线性结构中, 如果要检测duplication, 最基本的方法是检测两个数字是否相等, 这里可以用到很多的技巧来判断例如hash, two pointer, bit manipulation等等. 下面针对不同的Duplication使用不同的方法进行讨论.

注意点: 相等的概念, == 和 equals 以及如何判断两个object是否相等.

Read more »

Reverse a LinkedList

Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static ListNode reverse(ListNode head) {
if (head == null) {
return head;
}
ListNode prev = null;
ListNode curr = head;
ListNode next = head.next;
while (next != null) {
ListNode nextNext = next.next;
curr.next = prev;
next.next = curr;
prev = curr;
curr = next;
next = nextNext;
}
return curr;
}

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}

ListNode lastEnd = head.next;
ListNode lastStart = reverseList(head.next);
lastEnd.next = head;
head.next = null;

return lastStart;
}