2. Binary Search
3. DFS (recursive)
4. BFS
5. Priority Queue
6. DP
7. Linked List
8. Bitwise Operation
9. Tree
10. Two Pointer
11. Greedy
12. Stack
13. Priority Queue / Heap
14. Sliding Window
Note:
1. Linked List 實作特別弱。
2024年6月15日 星期六
2022年8月24日 星期三
Note
import sys import bisect
import math
def Lcm(a, b):
return abs(a*b) // math.gcd(a, b)
def find_lt(a, x):
'Find rightmost value less than x'
i = bisect.bisect_left(a, x)
if i:
return a[i - 1]
return 0
def find_gt(a, x):
'Find leftmost value greater than x'
i = bisect.bisect_right(a, x)
if i != len(a):
return a[i]
return a[len(a) - 1]
if __name__ == "__main__":
llp = int(sys.argv[1])
ulp = int(sys.argv[2])
llt = [i*llp for i in range(Lcm(llp, ulp) // llp + 1)]
ult = [i*ulp for i in range(Lcm(llp, ulp) // ulp + 1)]
via_size = int(sys.argv[3])
prl = int(sys.argv[4])
print(llt)
print(ult)
res = []
space_list = []
vios = 0
vios_list = []
for t in ult[:-1]:
left_bnd = find_lt(llt, t)
right_bnd = find_gt(llt, t)
left_dis = t - left_bnd - via_size
right_dis = right_bnd - t - via_size
space_list.append((left_dis, right_dis))
res.append((left_bnd, right_bnd))
if left_dis < prl:
vios = vios + 1
vios_list.append(left_dis)
if right_dis < prl:
vios = vios + 1
vios_list.append(right_dis)
vios_list.sort()
print(res)
print(space_list)
print("upper tracks: ", len(ult) - 1)
print("vios: ", vios)
print("vios_list: ", vios_list)
2022年8月14日 星期日
Modify multiple lines after matching lines in Vim
Just note down issues i faced in vim.
Problem: (How to add prefix "#" before ever lines between "#For testing" and " ; ?)
Command:
insert # prefix :g/^# For testing/+1,/^"/ norm! I#
remove # prefix :g/^# For testing/+1,/#^"/ norm! ^x
power g: :g/Pattern/cmd
pattern here is "^# For testing"
cmd here is +1, /^"/ norm! I#, where +1, /^"/ is a ranges command which means that from next line of current line to line of matching pattern (which is ^" here).
norm! I# means that insert "#" at each lines in normal mode.
norm! ^x means that remove first character at each lines in normal mode . (^: begin of a line, x: delete character)
2022年7月15日 星期五
Search selected text in vim
Just note down issues i faced in vim.
Search word under the cursor - * or # for backward/forward, respectively.
Search selected text in visual mode -
y (yank the selected text into " register by default)
/ (enter search mode)
(\ V) (can skill, it's optional. enter "very no magic" mode*)
Ctrl + r " (paste text from " register)
Enter (go!)
Reference: https://superuser.com/questions/41378/how-to-search-for-selected-text-in-vim
2022年2月24日 星期四
Script Note
import sys
import re
from itertools import combinations_with_replacement as rcb
from itertools import combinations as cb
if __name__ == '__main__':
all_vt = set()
group_list = {}
i = 0
with open('vt.txt') as f:
lines = f.readlines()
for line in lines:
group_list[i] = {}
p_list = []
n_list = []
for l in str(line).split():
if re.search('P', l):
p_list.append(l)
else:
n_list.append(l)
all_vt.add(l)
group_list[i]['P'] = p_list
group_list[i]['N'] = n_list
i = i + 1
print(group_list)
for vt in all_vt:
vt_type = 'P'
adj_type = 'N'
if re.search('N', vt):
vt_type = 'N'
adj_type = 'P'
adj_vt = re.sub(vt_type, adj_type, vt)
for key in group_list:
print(group_list[key])
group = group_list[key]
if adj_vt not in group[adj_type]:
continue
if vt in group[vt_type]:
continue
risk_types = list(rcb(group[vt_type], 2))
for risk_type in risk_types:
if vt in risk_type:
continue
if re.sub(vt_type, adj_type, risk_type[0]) in group[adj_type] and re.sub(vt_type, adj_type, risk_type[1]) in group[adj_type]:
continue
print("Violate Group: ", adj_vt, risk_type)
2022年2月8日 星期二
LeetCode 258. Add Digits [Easy] [C++] 解題筆記
Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.
Example 1:
Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
Since 2 has only one digit, return it.
Example 2:
Input: num = 0
Output: 0
想法: 這題就是直接照著題目給的方式實作就好，問題是 follow up 要求用 O(1) 的時間來完成。
老實說 i have no idea，看了別人的作法原來是要用數學解阿! 原來題目描述的這個東西叫做 Digital root，我們可以用 num mod 9 來檢查 num 的 digital root 是多少。舉例而言 12345 可以拆解為:12345 = 1 x 10000 + 2 x 1000 + 3 x 100 + 4 x 10 + 5 = 1 x (9999 + 1) + 2 x (999 + 1) + 3 x (99 + 1) + 4 x (9 + 1) + 5= (1 x 9999 + 2 x 999 + 3 x 99 + 4 x 9) + (1 + 2 + 3 + 4 + 5) 可以看出前面的括弧可以被 9 整除，因此 12345 除以 9 的餘數就會來自後面的括弧剛好就是 digital root 的定義(所以位數相加且<10)所以 num 的 digital root 就會等於 num % 9 唯一的例外是 9，其實也不算是例外，只是說在 mod 9 中 9 剛好是等於 0的因此遇到 num % 9 == 0 時需要把結果替換成 9。
完整程式碼:解法一:class Solution {
public:
int addDigits(int num) {
int sum = num;
while (num >= 10) {
sum = 0;
while (num) {
sum += num % 10;
num = num / 10;
}
num = sum;
}
return sum;
}
};
解法二(數學解):class Solution {
public:
int addDigits(int num) {
if (num == 0) { return 0; }
if (num % 9 == 0) { return 9; }
return num % 9;
}
};
2021年8月12日 星期四
LeetCode 148. Sort List [Medium] [C++] 解題筆記
Given the head of a linked list, return the list after sorting it in ascending order.
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Example 1:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Example 2:
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Example 3:
Input: head = []
Output: []
Constraints:
- The number of nodes in the list is in the range
[0, 5 * 104]. -105 <= Node.val <= 105
2021年6月24日 星期四
const map access element using [] operator [C++]
這篇主要想記錄一下 const map 想要利用 [] operator 存取元素時會遇到的問題與解決方式。
2021年4月26日 星期一
LeetCode 200. Number of Islands [Medium] [C++] 解題筆記
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
2021年4月20日 星期二
LeetCode 198. House Robber [Medium] [C++] 解題筆記
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.
2021年4月19日 星期一
LeetCode 169. Majority Element [Easy] [C++] 解題筆記
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Constraints:
n == nums.length1 <= n <= 5 * 104-231 <= nums[i] <= 231 - 1
Follow-up: Could you solve the problem in linear time and in
O(1) space?
2021年4月18日 星期日
LeetCode 160. Intersection of Two Linked Lists [Easy] [C++] 解題筆記
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
For example, the following two linked lists begin to intersect at node c1:
It is guaranteed that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
Example 2:
Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
Constraints:
- The number of nodes of
listAis in them. - The number of nodes of
listBis in then. 0 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= nintersectValis0iflistAandlistBdo not intersect.intersectVal == listA[skipA + 1] == listB[skipB + 1]iflistAandlistBintersect.
Follow up: Could you write a solution that runs in
O(n) time and use only O(1) memory?
2021年4月11日 星期日
LeetCode 155. Min Stack [Easy] [C++] 解題筆記
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack()initializes the stack object.void push(val)pushes the elementvalonto the stack.void pop()removes the element on the top of the stack.int top()gets the top element of the stack.int getMin()retrieves the minimum element in the stack.
Example 1:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0 minStack.getMin(); // return -2
訂閱：
文章 (Atom)