记录LeetCode的一些练习…

728.自除数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        arr = []
        for i in range(left,right+1):
            flag = True
            lis = list(str(i))
            if '0' in lis:
                continue

            for j in lis:
                if i % int(j) != 0:
                    flag = False
                    break
            if flag == True:
                arr.append(i)
        return arr

注意除数为0的可能，范围为1-10000

评论区再次秀到了我，面向用例编程

3.无重复字符的最长子串

拉垮了，自己写了个算法，check不过呢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        counts = [0]*len(s)

        for i in range(len(s)):

            count = 0
            a = []
            
            for j in range(i,len(s)):

                if s[j] in a:
                    break
                else:
                    a.append(s[j])
                    count += 1

            counts[count] = count 
        #    strings.append("".join(a))

        ans = max(counts)
        return int(counts[ans])

正解：

官方wp链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/

这一题方法是方法是”滑动窗口”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 哈希集合，记录每个字符是否出现过
        occ = set()
        n = len(s)
        # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动一格，移除一个字符
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断地移动右指针
                occ.add(s[rk + 1])
                rk += 1
            # 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1)
        return ans

用到了python内置函数，set（）

94.二叉树中序遍历

自己写的根本通不过，虽然意思懂了……就不展示了

下面是参考其中一个题解的递归算法:

正解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root):
        res = []
        self.inOrder(root,res)
        return res
    
    def inOrder(self,root,res):
        if root == None:
            return
        self.inOrder(root.left,res)
        res.append(root.val)
        self.inOrder(root.right,res)

后面附上陈斌老师关于python数据结构的二叉树的链表实现，及其前序中序后序的递归实现:

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
class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None
 
    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t
 
    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

    def getRightChild(self):
        return self.rightChild
 
    def getLeftChild(self):
        return self.leftChild
 
    def setRootVal(self,obj):
        self.key = obj
 
    def getRootVal(self):
        return self.key
 
def preOrderTraverse(tree):
    if tree != None:
        print(tree.getRootVal())
        preOrderTraverse(tree.getLeftChild())
        preOrderTraverse(tree.getRightChild())

def postOrderTraverse(tree):
    if tree != None:
        postOrderTraverse(tree.getLeftChild())
        print(tree.getRootVal())
        postOrderTraverse(tree.getRightChild())

def inOrderTraverse(tree):
    if tree != None:
        inOrderTraverse(tree.getLeftChild())
        print(tree.getRootVal())
        inOrderTraverse(tree.getRightChild())
            
# 构造二叉树
r = BinaryTree('0')
r.insertLeft('7')
r.insertLeft('3')
r.insertLeft('1')
r.insertRight('6')
r.insertRight('2')
r.getLeftChild().getLeftChild().insertRight('8')
r.getLeftChild().insertRight('4')
r.getLeftChild().getRightChild().insertLeft('9')
r.getRightChild().insertLeft('5')

print("---preorder---")
preOrderTraverse(r)
print("---inorder---")
inOrderTraverse(r)
print("---postorder---")
postOrderTraverse(r)

把以前逆向关于二叉树遍历的题目拿出来，带入验证一下

100.相同的树

这题还是用的深度优先算法

  1. 如果两个节点都没有，那么肯定相同
  2. 如果两个节点只有一个有，那么肯定不同
  3. 比较完节点之后，开始比较节点的值，如果两个节点的值不相同，则两颗树是不同的。
  4. 后面就是bfs深度优先算法
1
2
3
4
5
6
7
8
9
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        elif not p or not q:
            return False
        elif p.val != q.val:
            return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

这篇博客讲写树算法套路框架的：

https://leetcode-cn.com/problems/same-tree/solution/xie-shu-suan-fa-de-tao-lu-kuang-jia-by-wei-lai-bu-/

112.路径总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], sum: int) -> bool:
        if not root:
            return False
        if root.val == sum and not root.right and not root.left:
            return True
        left = self.hasPathSum (root.left,sum - root.val)
        right = self.hasPathSum (root.right,sum - root.val)
        return left or right

这边还是递归，有两个限制

  1. 如果root为空，而且sum值还存在，则返回False
  2. 如果sum值正好等于当前节点的val值，且为根节点，则返回True

下面就是两个递归算法，返回值为left or right，满足一个条件为Ture即可。

113.路径总和（二）

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:

    def pathSum(self, root: Optional[TreeNode], sum: int) -> List[List[int]]:

        lis = []
        path = []

        def dfs(root,sum):
            if not root:
                return
            path.append(root.val)
            sum -= root.val
            if not root.right and not root.left and sum == 0  :
                lis.append(path[:])
            
            dfs(root.right,sum)
            dfs(root.left,sum)
            path.pop()
            
        dfs(root,sum)
        return lis

就是在上面的基础上，增加了append的功能

在dfs()算法的最后，需要加上pop()语句，用来回溯正确的值。

5.最长回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestPalindrome(self,s: str) -> str:
        length = len(s)
        max_length = 0
        max_string = ''
        for i in range(length+1):
            for j in range(i,length+1):
                if s[i:j] == s[i:j][::-1]:
                    if len(s[i:j]) > max_length:
                        max_length = len(s[i:j])
                        max_string = s[i:j]

        return max_string

自己编写的，可惜超时了，去评论区找找更好的解决方案：

对于暴力算法的改进……在第二重循环中优先判断长度，但还是超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestPalindrome(self,s: str) -> str:
        length = len(s)
        max_length = 0
        max_string = ''
        for i in range(length+1):
            for j in range(i,length+1):
                if len(s[i:j]) < max_length:
                    continue
                if s[i:j] == s[i:j][::-1]:
                    if len(s[i:j]) > max_length:
                        max_length = len(s[i:j])
                        max_string = s[i:j]

        return max_string

这边推荐使用中心扩散算法，循环字符串中的每一位个字符，并向字符两边扩散，如果两边字符都相当且不越界，则正确，返回left和right截取的字符串。

当然，也要考虑最长回文子串为偶数的情况，第二个if就是为其考虑的。

官方解题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

来源：

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

剑指 Offer 44. 数字序列中某一位的数字

自己代入的1009算的，但还是错了

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
# 0-9       9       1位
# 10-99     90      2位
# 100-999   900     3位
# 1000-9999 9000    4位

class Solution:
    def findNthDigit(self, n: int) -> int:
        length = len(str(n))
        if length == 1:
            return n
        else:
            lis = []
            for i in range(length):
                lis.append(9*(10**i))

            j = 0 #当前区段之前总的多少个数字位
            q = 1 #区段数
            while j < n and j + (lis[i-1] * q) < n:
                j = j + (lis[i-1] * q)
                q += 1

            # 之前的位数
            sum_w = 0
            for i in range(q):
                sum_w += (i+1)*lis[i]

            # 当前段中的第几位
            # q+1：当前段的字符长度
            current = (n-sum_w)/(q+1)

            sum_n = 0
            # 总的多少个数字
            for i in range(q):
                sum_n += lis[i]
            sum_n += int(current)

            # 当前数字的位数
            number = int((current-int(current))*(q+1))
            return int(str(sum_n)[number])

正解：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findNthDigit(self, n: int) -> int:
        digit, start, count = 1, 1, 9
        while n > count: # 1.
            n -= count
            start *= 10
            digit += 1
            count = 9 * start * digit
        num = start + (n - 1) // digit # 2.
        return int(str(num)[(n - 1) % digit]) # 3.

还是大佬厉害啊，俺的做法跟他差不多，就是不知道哪里错了……

275.H 指数 II

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        length = len(citations)
        if max(citations) == 0:
            return 0
        elif (length == 1 and citations[0] != 0) or (length > 1 and max(citations[:length-1]) == 0):
            return 1
        else: 
            for i in range(length-1):
                if citations[i] == (length - i) or citations[i] == (length - i -1):
                    return citations[i]

会有各种稀奇古怪的组合，得面面俱到，就和修洞一样(doge)

我就是简单的测试了以下当前的值与列表后面值得个数，以及考虑到了一些特殊情况，这边的话，就不修了……

正解

这题最好使用的方法是二分查找：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        left = 0
        right = n - 1
        while left <= right:
            mid = left + (right - left) // 2
            if citations[mid] >= n - mid:
                right = mid - 1
            else:
                left = mid + 1
        return n - left

当然看题解区也有遍历数组的解法，我和他的想法类似，就是我拉大跨罢了：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.reverse()
        flag=True
        n=len(citations)
        for i in range(1,n+1):
            if citations[i-1]<i:
                flag=False
                break
        if not flag:
            return i-1
        else:
            return n

来源：https://leetcode-cn.com/problems/h-index-ii/solution/yi-ci-bian-li-ji-ke-by-qian-li-ma-8-liyt/

1089.复写零

和paixiaoxing讨论了这题，for循环不好控制，就用的是while循环。每次遇到0，都会把k再往后加一，并且pop最后一个列表元素，保证列表的长度不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def duplicateZeros(self, List: List[int]) -> None:
        """
        Do not return anything, modify List in-place instead.
        """
        length = len(List)
        k = 0

        while k < length:
            if List[k] == 0:
                List.insert(k+1, 0)
                List.pop()
                k += 1
            k += 1

1309.解码字母到整数映射

从后往前，遇到#，就把前面两个字符转换成整形，再转换成str型；如果没有遇到#，就正常ascii+48的转换。

第一次提交就全部通过，并且成绩还不赖！！

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def freqAlphabets(self, s: str) -> str:
        flag = ''
        i = len(s) - 1
        while i >= 0:
            if ord(s[i]) == 35:
                n = int(s[i-2:i])
                flag += chr(n+96)
                i -= 2
            else:
                flag += chr(ord(s[i]) + 48)
            i -= 1
        return flag[::-1]

451.根据字符出现频率排序

自己编写，把所有可能出现的字符加入到字典中，然后循环字典统计字符出现次数，按照字典value排序，然后构建返回的flag，就是最后的思路，最后的循环可以再优化一下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def frequencySort(self, string: str) -> str:

        dic = {'a':0,'b':0,'c':0,'d':0,'e':0,'f':0,'g':0,'h':0,'i':0,'j':0,'k':0,'l':0,'m':0,'n':0,'o':0,'p':0,'q':0,'r':0,'s':0,'t':0,'u':0,'v':0,'w':0,'x':0,'y':0,'z':0,'A':0,'B':0,'C':0,'D':0,'E':0,'F':0,'G':0,'H':0,'I':0,'J':0,'K':0,'L':0,'M':0,'N':0,'O':0,'P':0,'Q':0,'R':0,'S':0,'T':0,'U':0,'V':0,'W':0,'X':0,'Y':0,'Z':0,'1':0,'2':0,'3':0,'4':0,'5':0,'6':0,'7':0,'8':0,'9':0,'0':0}

        # 遍历字符串统计次数
        for i in range(len(string)):
            dic[string[i]] += 1

        # 按字典的value进行排序
        dic2 = sorted(dic.items(), key = lambda kv:(kv[1], kv[0]), reverse = True)

        flag = ''

        for item in dic2:
        	flag += item[1]*item[0]

        return flag

我惊了，人家可以用一行代码……

原来Counter可以直接统计列表或者字符中元素出现的次数

1
2
3
4
from collections import Counter
class Solution:
    def frequencySort(self, s: str) -> str:
        return "".join([ch * cn for (ch, cn) in collections.Counter(s).most_common()])

109. 有序链表转换二叉搜索树

在这边学习一下：快慢指针+链表分裂构造二叉树

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
         if(head == null){
            return null;
        }else if(head.next == null){
            return new TreeNode(head.val);
        }

        //设置快慢节点
        ListNode fast = head;
        ListNode slow = head;
        // pre是最中间节点的前驱结点
        ListNode pre = slow;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        //利用中间节点创建二叉树根节点
        TreeNode root = new TreeNode(slow.val);

        //创建右链表
        root.right = sortedListToBST(slow.next);

        // 断开链表，slow这个节点已经用过了，前后都需要断开
        slow.next = null;
        pre.next = null;

        //创建左链表
        root.left = sortedListToBST(head);
        return root;
    }
}

快慢链表节点用来确定链表中的中间节点，pre是确定中间节点的前一个节点，扫描出中间节点来作为二叉树根节点，然后是创建左右链表，并断开左右链表的链接，把左右链表的头节点放到递归函数中。

1207. 独一无二的出现次数

根据前天的Counter写出的算法，用set()去重，对比长度即知是否重复

1
2
3
4
5
6
7
8
9
from collections import Counter
class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        times = []

        for item in Counter(arr).most_common():
            times.append(item[1])
        
        return len(set(times)) == len(times)

有点拉

在评论区学到一招：

1
Counter(arr).values()

改进：

1
2
3
4
from collections import Counter
class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:   
        return len(set(Counter(arr).values())) == len(Counter(arr).values())

8.字符串转换整数 (atoi)

这题有点变态，不能忽视任何其他字符，会有正负数，会有科学计数法，而且不能超出范围。奇葩用例：

每次python的一行做法都能惊艳到我，大佬牛逼啊，传送门

让我诧异的是关于python中关于*的使用

大佬放话了:

也就是把只有一个元素的int列表转换成int，测试：

步骤：

  1. 先将字符串空格删除

  2. re正则匹配，结果为列表类型

  3. 将匹配成功的列表”解包”

  4. 匹配成功的字符串，转换成int类型

  5. min函数(XXX，2**31-1)，确定上界限

  6. max函数(XXX，-2**31)，确定下界限

1
2
3
4
import re
class Solution:
    def myAtoi(self, s: str) -> int:
        return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)

^ 是不取的意思，[]是选择，?是出现一次或没有，\d+是出现一次或多次，\ +是因为+是特殊字符相当于转义