Posted on | In |

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        #未出现的节点存入res，result用于记录头节点
        res = ListNode()
        result = res
        #遍历链表中所有元素，并存入集合，如果集合长度未变则出现过，反之则未出现过
        item = set()
        while head:
            lens = len(item)
            item.add(head.val)
            new_lens = len(item)
            if lens != new_lens:
                res.next = ListNode(head.val)
                res = res.next
            head = head.next
        return result.next

Posted on | In |

如果一个正方形矩阵满足下述 全部 条件，则称之为一个 X 矩阵 ：矩阵对角线上的所有元素都 不是 0，矩阵中所有其他元素都是 0。
给你一个大小为 n x n 的二维整数数组 grid ，表示一个正方形矩阵。如果 grid 是一个 X 矩阵 ，返回 true ；否则，返回 false 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/check-if-matrix-is-x-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题干中的grid是嵌套的列表，第一时间就想到了把这个列表转成np.array()然后再通过矩阵相关的方法去处理，用时150ms，然后在评论区发现有人用Java答题的思路跟我一样，但是他只需要1ms甚至0ms。
找耗时长的过程中发现，虽然我把列表转换成了np.array，但是这种转换并没有带来任何方便，然后我就直接在原始列表上操作数据，时间从150ms降到了70-80ms，但这与1ms仍差距甚远，
然后发现虽然我去掉了np.array的转换操作。。。但是import np的语句我没删掉。。去掉引包语句之后时间降到了30ms。。。引包的耗时还是挺长的。。。
可是可是可是，为什么相同的解题思路python要30ms，Java只要1ms甚至0ms呢？
还有更奇怪的，下面最后一个，也就是第四个代码块的实现方式理论上遍历的次数要比代码块3要少。但是代码块3只要30ms，而代码块4要将近70？？因为测试用例中True的情况比较多？False的情况比较少?
为啥Java比python快那么多？为啥硬遍历比计算diff还要快？？我不理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import numpy as np
class Solution(object):
    def checkXMatrix(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: bool
        """
		matrix = np.array(grid)        
        shape = matrix.shape[0]
        for i in range(shape):
            diff = shape - i - 1
            if matrix[i,i] == 0 or matrix[i,diff] == 0:
                return False
            for j in range(shape):
                if j != i and j != diff:
                    if matrix[i,j] != 0:
                        return False
        return True    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import numpy as np
class Solution(object):
    def checkXMatrix(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: bool
        """
        matrix = np.array(grid)        
        shape = matrix.shape[0]
        for i in range(shape):
            for j in range(shape):
                if i == j or ((i + j) == (shape - 1) ):
                    if matrix[i,j] == 0:
                        return False
                else:
                    if matrix[i,j] != 0:
                        return False
        print(matrix)
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def checkXMatrix(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: bool
        """  
        shape = len(grid)
        for i in range(shape):
            for j in range(shape):
                if i == j or ((i + j) == (shape - 1) ):
                    if grid[i][j] == 0:
                        return False
                else:
                    if grid[i][j] != 0:
                        return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def checkXMatrix(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: bool
        """  
        shape = len(grid)
        for i in range(shape):
            diff = shape - i - 1
            if grid[i][i] == 0 or grid[i][diff] == 0:
                return False
            for j in range(shape):
                if j != i and j != diff:
                    if grid[i][j] != 0:
                        return False
        return True

Posted on | In |

给你字符串 key 和 message ，分别表示一个加密密钥和一段加密消息。解密 message 的步骤如下：
使用 key 中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。
将替换表与普通英文字母表对齐，形成对照表。
按照对照表 替换 message 中的每个字母。
空格 ‘ ‘ 保持不变。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/decode-the-message
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def decodeMessage(self, key, message):
        """
        :type key: str
        :type message: str
        :rtype: str
        """
        #统一存ASCII码，用chr()将ASCII转换为字母，空格符ASCII码是32
        mapping_dict = dict({" ":32})
        start_index = 97
        for i in key:
            if i not in mapping_dict:
                mapping_dict[i] = start_index
                start_index += 1 
        decode = str()
        for i in message:
            decode += chr(mapping_dict[i])
        return decode

Posted on | In |

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。
如果小镇法官真的存在，那么：
小镇法官不会信任任何人。
每个人（除了小镇法官）都信任这位小镇法官。
只有一个人同时满足属性 1 和属性 2 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-town-judge
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个代码没有通过测试，因为碰到两个测试用例我觉得与题意相悖。题目输入包括n和trust，其数据格式如代码块中注释所示。有一个测试用例n=1，trust=[]。按照题干来说，法官要有人信他他才是法官，只有一个人时我个人理解他并不能算是法官。
第二个案例就是n=4，trust=[[1,3],[1,4],[2,3]]，答案为3。但4并未相信3，为什么3能为法官？这个案例哪怕脱离题干中“法官”的情景应该也过不去吧?

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
class Solution(object):
    def findJudge(self, n, trust):
        """
        :type n: int
        :type trust: List[List[int]]
        :rtype: int
        """
        trust_dict = {i:[] for i in range(1,n+1)}
        trust_valid = list()
        for lst in trust:
            person_id,trusted_id = lst[0],lst[1]
            trust_dict[person_id].append(trusted_id)
        for i in trust_dict.values():
            trust_valid.extend(i)
        judger_id_maybe = min(trust_dict,key = trust_dict.get)
        
        if len(trust_dict[judger_id_maybe]) == 0 and len(trust_valid):
            for id,trust in trust_dict.items():
                if id == judger_id_maybe:
                    continue
                else:
                    if judger_id_maybe not in trust:
                        return -1
                    else:
                        return judger_id_maybe
        else:
            return -1

官方提供的代码如下，可是能过，呵呵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def findJudge(self, n, trust):
        """
        :type n: int
        :type trust: List[List[int]]
        :rtype: int
        """
        n = 4
        trust = [[1,3],[1,4],[2,3],[4,3]]
        inDegrees = Counter(y for _, y in trust)
        outDegrees = Counter(x for x, _ in trust)
        print(inDegrees)
        print("==============")
        print(outDegrees)
        return next((i for i in range(1, n + 1) if inDegrees[i] == n - 1 and outDegrees[i] == 0), -1)

Posted on | In |

有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-coloring-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
写的第一版，超时了，嘿嘿。

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def btreeGameWinningMove(self, root, n, x):
        """
        :type root: TreeNode
        :type n: int
        :type x: int
        :rtype: bool
        """
        def searching(root):
            _foreach = deque([root])
            node_nums = 0
            while _foreach:
                for _ in range(len(_foreach)):
                    _current_node = _foreach.pop()
                    node_nums += 1
                    for node in [_current_node.left,_current_node.right]:
                        if node:
                            _foreach.appendleft(_current_node)
            return node_nums

        foreach = deque([root])
        while foreach:
            for _ in range(len(foreach)):
                current_node = foreach.pop()
                if current_node.val == x:
                    # if current_node.left:
                    left_num = searching(current_node.left) 
                    if current_node.right:
                        right_num = searching(current_node.left) 
                    if left_num and right_num:
                        return True
                    else:
                        return False
                if current_node.left.val == x:
                    left_num = searching(current_node.left)
                    right_num = searching(current_node.right)
                    if right_num > left_num:
                        return True
                    else:
                        return False
                if current_node.right.val == x:
                    left_num = searching(current_node.left)
                    right_num = searching(current_node.right)
                    if left_num > right_num:
                        return True
                    else:
                        return False

后来发现searching写的有问题，不应该写循环，可是还是没通过，嘿嘿。

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def btreeGameWinningMove(self, root, n, x):
        """
        :type root: TreeNode
        :type n: int
        :type x: int
        :rtype: bool
        """
        def searching(root):
            node_nums = 0
            if root:
                node_nums += 1
                left_num = searching(root.left)
                right_num = searching(root.right)
                node_nums += left_num + right_num
            return node_nums

        foreach = deque([root])
        while foreach:
            for _ in range(len(foreach)):
                current_node = foreach.pop()
                if current_node.val == x:
                    print("current:")
                    # if current_node.left:
                    left_num = searching(current_node.left) 
                    right_num = searching(current_node.right)
                    print(left_num,right_num)
                    # if left_num > (n - 1)  or right_num > (n - 1) :
                    if left_num > (right_num + 1) or right_num > (left_num + 1) :
                        return True
                    else:
                        return False
                if current_node.left and current_node.left.val == x:
                    print("left:")
                    left_num = searching(current_node.left)
                    right_num = searching(current_node.right)
                    print(left_num,right_num,left_num>right_num)
                    if (right_num + 1) > left_num:
                        return True
                    else:
                        return False
                if current_node.right and current_node.right.val == x:
                    print("right:")
                    left_num = searching(current_node.left)
                    right_num = searching(current_node.right)
                    print(left_num,right_num)
                    if (left_num + 1) > right_num:
                        return True
                    else:
                        return False
                if current_node.left:
                    foreach.appendleft(current_node.left)
                if current_node.right:
                    foreach.appendleft(current_node.right)

贴一个评论区的解决方案，没太看懂，嘿嘿。

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
class Solution {
public:
int Lcnt;
int Rcnt;
int count(TreeNode* root)
{
    int cnt = 0;
    if(root)
    {
        cnt++;
        int Lc = count(root->left);
        int Rc = count(root->right);
        cnt += Lc + Rc;
    }
    return cnt;
}
void dfs(TreeNode* root,int x)
{
    if(root)
    {
        if(root->val == x)
        {
            Lcnt = count(root->left);
            Rcnt = count(root->right);
        }
        else
        {
            dfs(root->left,x);
            dfs(root->right,x);
        }
    }
}
bool btreeGameWinningMove(TreeNode* root, int n, int x) 
{
    dfs(root,x);
    if(n > 2 * (Lcnt + Rcnt + 1))return true;
    if(2 * Lcnt > n)return true;
    if(2 * Rcnt > n)return true;
    return false;
}
};

Posted on | In |

在一个有向图中，节点分别标记为 0, 1, …, n-1。图中每条边为红色或者蓝色，且存在自环或平行边。
red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地，blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向边。
返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shortest-path-with-alternating-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算是接触的第一到图题，很多相关概念都忘记了，题干也没太看懂，重新整理了一下图的相关概念后，在评论区找了一段代码，题的思路和广度优先遍历弄明白了一些，但是也没完全弄懂。

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(object):
    def shortestAlternatingPaths(self, n, redEdges, blueEdges):
        """
        :type n: int
        :type redEdges: List[List[int]]
        :type blueEdges: List[List[int]]
        :rtype: List[int]
        """
        g = defaultdict(list)
        for a, b in redEdges:
            g[a].append(-b)
        for a, b in blueEdges:
            g[-a].append(b)
        print(g)
        ret = [-1] * n
        vis = set()
        q = deque([0])
        vis.add(0)
        s = 0
        while q:
            for _ in range(len(q)):
                p = q.pop()
                if ret[abs(p)] == -1:
                    ret[abs(p)] = s
                for x in g[p]:
                    if x not in vis:
                        q.appendleft(x)
                        vis.add(x)
            s += 1
        return ret

Posted on | In |

有一个无向的 星型 图，由 n 个编号从 1 到 n 的节点组成。星型图有一个 中心 节点，并且恰有 n - 1 条边将中心节点与其他每个节点连接起来。
给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间存在一条边。请你找出并返回 edges 所表示星型图的中心节点。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-center-of-star-graph
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def findCenter(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: int
        """
        degree_status = defaultdict(int)
        for edge in edges:
            degree_status[edge[1]] += 1
        return max(degree_status,key=degree_status.get)

Posted on | In |

给你一个 有向无环图 ， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，其中 edges[i] = [fromi, toi] 表示一条从点 fromi 到点 toi 的有向边。

找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。

你可以以任意顺序返回这些节点编号。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-number-of-vertices-to-reach-all-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

最开始的想法中，vertext并未转换为set类型，判断edge[1]是否在vertex中，如果在则删除，但是超时了。后来换成把入度非0的节点和vertex都换成集合就过了。。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def findSmallestSetOfVertices(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        vertex = set(list(range(n)))
        indegree = set()
        for edge in edges:
            indegree.add(edge[1])
        return list(vertex - indegree)

Posted on | In |

给你一棵 完整二叉树 的根，这棵树有以下特征：

叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。
非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。
计算 一个节点的值方式如下：
如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。
否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/evaluate-boolean-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def evaluateTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        def dfs(node):
            if node.val == 2 :  
                return dfs(node.left) or dfs(node.right)
            elif node.val == 3 :
                return dfs(node.left) and dfs(node.right)
            else:
                return node.val == 1
        return dfs(root)

Posted on | In |

力扣公司的员工都使用员工卡来开办公室的门。每当一个员工使用一次他的员工卡，安保系统会记录下员工的名字和使用时间。如果一个员工在一小时时间内使用员工卡的次数大于等于三次，这个系统会自动发布一个 警告 。
给你字符串数组 keyName 和 keyTime ，其中 [keyName[i], keyTime[i]] 对应一个人的名字和他在 某一天 内使用员工卡的时间。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

先把keytime处理成int，然后用np.argsort返回keytime的升序索引，下面遍历的时候直接用这个升序索引访问name和time。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from numpy import argsort
class Solution(object):
    def alertNames(self, keyName, keyTime):
        """
        :type keyName: List[str]
        :type keyTime: List[str]
        :rtype: List[str]
        """
        keyTime = [int(k.replace(":","")) for k in keyTime]
        sequence = argsort(keyTime)
        result = set()
        order = defaultdict(list)

        for index in sequence:
            name = keyName[index]
            order[name].append(keyTime[index])
            if len(order[name]) >= 3:
                if (int(order[name][-1]) - int(order[name][-3])) <= 100 :
                    result.add(name)
        result = list(result)
        result.sort()
        return result