Data Structure
dict
| Concept | Java (HashMap) |
Python (dict) |
|---|---|---|
| Create | Map<String, Integer> m = new HashMap<>(); |
d = {} |
| Put | m.put("a", 1); |
d["a"] = 1 |
| Get | m.get("a") |
d["a"] |
| Get default | m.getOrDefault("a", 0) |
d.get("a", 0) |
| Contains key | m.containsKey("a") |
"a" in d |
| Remove | m.remove("a") |
d.pop("a") |
| Size | m.size() |
len(d) |
| computeIfAbsent | m.computeIfAbsent(k, key -> new ArrayList<>()).add(v) |
d.setdefault(k, []).append(v) |
Array
String
Sort
list sort
# in original list
a = [3, 1, 2]
a.sort()
print(a) # [1, 2, 3]
# in new sorted list
a = [3, 1, 2]
b = sorted(a)
print(b) # [1, 2, 3]
print(a) # keep the same
sort parameters
Using Timsort, which is a combination of insertion sort(small runs) and merge sort(merge sorted runs)
- time = best O(n), avg and worst O(nlogn)
- space = O(n)
# descending sort
a.sort(reverse=True)
a = [(1, 3), (2, 1), (4, 2)]
a.sort(key=lambda x: x[1]) # by second variable
a = [(1, 3), (1, 2), (2, 1)]
a.sort(key=lambda x: (x[0], x[1])) # by sort first variable and then second variable
a.sort(key=lambda x: (x[0], -x[1]))
Binary Search
Find the index of the first appearance (nums[index] <= target)
import bisect
a = [1, 2, 4, 4, 5]
print(bisect.bisect_left(a, 4)) # 2
Find the index of the first larger appearance ((nums[index] > target)
import bisect
a = [1, 2, 4, 4, 5]
print(bisect.bisect_right(a, 4)) # 4
