ARST打卡第116周[116/521]

发表于 分类于 阅读次数：
lc-1743_从相邻元素对还原数组 阅读smbprotocol的部分源码 zsh & oh-my-zsh 的配置与使用 python匿名函数 美化zsh，以及配置时间戳显示

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，以及配置时间戳显示