# # Python Data Struct

## # Slicing

``````>>> s = 'bicycle'
>>> s[3:]
'ycle'
>>> s[:3]
'bic'
>>> s[::3]
'bye'
>>> s[::-1]
'elcycib'
``````

If you want to reverse a string, the last example is a choice.

• assigning to slices
``````>>> l = list(range(10))
>>> l
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> l[2:5]
[2, 3, 4]
>>> l[2:5] = [20,30]
>>> l
[0, 1, 20, 30, 5, 6, 7, 8, 9]
``````

what you can see is that [2,3,4] is replaced by [20,30]

## # List

• list of list

``````>>> board = [['_'] * 3 for i in range(3)]
>>> board
[['_', '_', '_'], ['_', '_', '_'], ['_', '_', '_']]
>>> board[1][2] = 'x'
>>> board
[['_', '_', '_'], ['_', '_', 'x'], ['_', '_', '_']]
``````

The first line is the right way to multiply it,rather than:

``````>>> wrong_board = [['_'] * 3] * 3
>>> wrong_board[1][2] = 0
>>> wrong_board
[['_', '_', 0], ['_', '_', 0], ['_', '_', 0]]
``````
• `list.sort()` & `sorted(list)`

The `list.sort()` method sorts a list in-place, that is, without making a copy.

In contrast, the built-in function `sorted(list)` creates a new list and returns it.

• 找到列表中每一行的最大元素和每一列的最大元素

``````        row = len(heights)
col = len(heights[0])

max_row = [0] * row
max_col = [0] * col

for i in range(row):
max_row[i] = max(heights[i])

for j in range(col):
for i in range(row):
max_col[j] = max(heights[i][j], max_col[j])
``````

## # sort and sorted

skill

example code

1. sorted()

descending order (降序)

``````def max_n(lst, n=1, reverse=True):
return sorted(lst, reverse=reverse)[:n]
``````
2. sort() + deepcopy()

ascending order (升序)

``````from copy import deepcopy

def min_n(lst, n=1):
numbers = deepcopy(lst)
numbers.sort()
return numbers[:n]
``````
• make list a stack or queue

The .append and .pop methods make a list usable as a stack or a queue (if you use .append and .pop(0), you get LIFO, Last in First out, behavior).

But inserting and removing from the left of a list (the 0-index end) is costly because the entire list must be shifted.

• deques and queues

``````from collections import deque
dq = deque(range(10), maxlen=10)
# dq: deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
dq.rotate(3)
# [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]
# this function rotates items from the right end
# and when dp.rotate(-3) is from the left
dq.appendleft(-1)
# [-1, 1, 2, 3, 4, 5, 6, 7, 8, 9]
dq.extend([11, 22, 33])
# [3, 4, 5, 6, 7, 8, 9, 11, 22, 33]
# default is insert from right
``````

What is different between `append()` and `extend()`? here is an example:

``````>>> dp
# deque([10, 30, 20, 10, 3, 4, 5, 6, 7, 8], maxlen=10)

>>> dp.appendleft([1, 2])
# deque([[1, 2], 10, 30, 20, 10, 3, 4, 5, 6, 7], maxlen=10)

>>> dp.extendleft([1, 2])
# deque([2, 1, [1, 2], 10, 30, 20, 10, 3, 4, 5], maxlen=10)
``````

Note that `extendleft(iter)` works by appending each successive item of the iter argument to the left of the deque, therefore the final position of the items is reversed.

## # Bisect

`#bisect: [baɪ'sɛkt]`

Bisection is the general activity of dividing a geometric figure into two equal parts

## # Set

Python 的集合是一个十分方便的对于元素可以操作的序列，除了去掉重复元素外，还可以进行稽核之间的运算。

``````student = {'Tom', 'Jim', 'Mary', 'Tom', 'Jack', 'Rose'}
print(student)   # 输出集合，重复的元素被自动去掉

b = set('alacazam')

print(a - b)     # a 和 b 的差集

print(a | b)     # a 和 b 的并集

print(a & b)     # a 和 b 的交集

print(a ^ b)     # a 和 b 中不同时存在的元素
``````

set 的集合运算十分有用，看下面的代码：

``````class Solution:
def findWords(self, words):
"""
:type words: List[str]
:rtype: List[str]
"""
a = set('qwertyuiop')
b = set('asdfghjkl')
c = set('zxcvbnm')
ans = []
for word in words:
w = set(word.lower())
if (w & a == w) or (w & b == w) or (w & c == w):
ans.append(word)
return ans
``````

### # set usage

1. 使用 set 一般用于 判断一个值是否存在其中
2. when to keep elements sorted and unique.

Example: 忽略常见单词，只对不在集合中的单词统计出现次数：

``````set<string> exclude = {"some", "words"};
//code
if(exclude.find(word) == exclude.end()) {
//code
}
``````

``````vector<string> exclude = {"some", "words"};
//code
auto is_exclude = std::binary_search(exclude.cbegin(), exclude.cend(), word);
//bool binary_search()
auto reply = is_exclude ? "excluded" : "not excluded";
``````