ARST打卡第116周[116/521]

Algorithm

lc-1743_从相邻元素对还原数组

思路

想到的是直接遍历,然后用set找出只出现过一次的两个数,并记录下标,然后选择一个数开始连接

每次都遍历找出一个的,复杂度达到了O(n^2),所以记录相邻表,然后就可以降低到O(n)

官方题解也是如此

自己没有动手实现,真懒,下不为例

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
class Solution {
public:
vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
unordered_map<int, vector<int>> mp;
for (auto& adjacentPair : adjacentPairs) {
mp[adjacentPair[0]].push_back(adjacentPair[1]);
mp[adjacentPair[1]].push_back(adjacentPair[0]);
}

// 数组中的值除了首尾都出现了两次,那么再让首尾组成一队,再出现一次
// 这样的adjacentPairs的size就和原数组size一致了,所以是+1
int n = adjacentPairs.size() + 1;
vector<int> ret(n);
for (auto& [e, adj] : mp) {
// 找到首尾中的一个,就找只有一个邻接元素的
if (adj.size() == 1) {
ret[0] = e;
break;
}
}

ret[1] = mp[ret[0]][0];
for (int i = 2; i < n; i++) {
auto& adj = mp[ret[i - 1]];
// 找到相邻中的另一个
ret[i] = ret[i - 2] == adj[0] ? adj[1] : adj[0];
}
return ret;
}
};

Review

阅读smbprotocol的部分源码

发现几个基础,但有很经典实用的点

利用子类比父类先调用构造函数,在父类构造函数中给子类赋值父指针为self

smbprotocol/open.py /

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
class SMB2CreateRequest(Structure):
"""
[MS-SMB2] v53.0 2017-09-15
2.2.13 SMB2 CREATE Request
The SMB2 Create Request packet is sent by a client to request either
creation of or access to a file.
"""
COMMAND = Commands.SMB2_CREATE

def __init__(self):
# pep 80 char issues force me to define this here
create_con_req = SMB2CreateContextRequest
self.fields = OrderedDict([
('structure_size', IntField(
size=2,
default=57,
)),
('security_flags', IntField(size=1)),
('requested_oplock_level', EnumField(
size=1,
enum_type=RequestedOplockLevel
)),
('impersonation_level', EnumField(
size=4,
enum_type=ImpersonationLevel
)),
('smb_create_flags', IntField(size=8)),
('reserved', IntField(size=8)),
('desired_access', IntField(size=4)),
('file_attributes', IntField(size=4)),
('share_access', FlagField(
size=4,
flag_type=ShareAccess
)),
('create_disposition', EnumField(
size=4,
enum_type=CreateDisposition
)),
('create_options', FlagField(
size=4,
flag_type=CreateOptions
)),
('name_offset', IntField(
size=2,
default=120 # (header size 64) + (structure size 56)
)),
('name_length', IntField(
size=2,
default=lambda s: self._name_length(s)
)),
('create_contexts_offset', IntField(
size=4,
default=lambda s: self._create_contexts_offset(s)
)),
('create_contexts_length', IntField(
size=4,
default=lambda s: len(s['buffer_contexts'])
)),
# Technically these are all under buffer but we split it to make
# things easier
('buffer_path', BytesField(
size=lambda s: self._buffer_path_size(s),
)),
('padding', BytesField(
size=lambda s: self._padding_size(s),
default=lambda s: b"\x00" * self._padding_size(s)
)),
('buffer_contexts', ListField(
size=lambda s: s['create_contexts_length'].get_value(),
list_type=StructureField(
structure_type=create_con_req
),
unpack_func=lambda s, d: self._buffer_context_list(s, d)
))
])
super(SMB2CreateRequest, self).__init__()

smbprotocol/structure.py /

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
class Structure(object):

def __init__(self):
# Now that self.fields is set, loop through it again and set the
# metadata around the fields and set the value based on default.
# This must be done outside of the OrderedDict definition as set_value
# relies on the full structure (self) being available and error
# messages use the field name to be helpful
for name, field in self.fields.items():
field.structure = self
field.name = name
field.set_value(field.default)

def __str__(self):
struct_name = self.__class__.__name__
raw_hex = _bytes_to_hex(self.pack(), True, hex_per_line=0)
field_strings = []

for name, field in self.fields.items():
# the field header is slightly different for a StructureField
# remove the leading space and put the value on the next line
if isinstance(field, StructureField):
field_header = "%s =\n%s"
else:
field_header = "%s = %s"

field_string = field_header % (field.name, str(field))
field_strings.append(_indent_lines(field_string, TAB))

field_strings.append("")
field_strings.append(_indent_lines("Raw Hex:", TAB))
hex_wrapper = textwrap.TextWrapper(
width=33, # set to show 8 hex values per line, 33 for 8, 56 for 16
initial_indent=TAB + TAB,
subsequent_indent=TAB + TAB
)
field_strings.append(hex_wrapper.fill(raw_hex))

string = "%s:\n%s" % (to_native(struct_name), '\n'.join([to_native(s) for s in field_strings]))

return string

def __setitem__(self, key, value):
field = self._get_field(key)
field.set_value(value)

def __getitem__(self, key):
return self._get_field(key)

def __delitem__(self, key):
self._get_field(key)
del self.fields[key]

def __len__(self):
length = 0
for field in self.fields.values():
length += len(field)
return length

def pack(self):
data = b""
for field in self.fields.values():
field_data = field.pack()
data += field_data

return data

def unpack(self, data):
mem = memoryview(data)
for key, field in self.fields.items():
mem = field.unpack(mem)
return bytes(mem) # remaining data

def _get_field(self, key):
field = self.fields.get(key, None)
if field is None:
raise ValueError("Structure does not contain field %s" % key)
return field

构造函数中的匿名表达式在pack()使用时确定实际值

smbprotocol/structure.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def _get_calculated_value(self, value):
"""
Get's the final value of the field and runs the lambda functions
recursively until a final value is derived.

:param value: The value to calculate/expand
:return: The final value
"""
if isinstance(value, types.LambdaType):
expanded_value = value(self.structure)
return self._get_calculated_value(expanded_value)
else:
# perform one final parsing of the value in case lambda value
# returned a different type
return self._parse_value(value)

Tips

zsh & oh-my-zsh 的配置与使用

python匿名函数

Share

美化zsh,以及配置时间戳显示