leetcode（25~29）

发表于 | 分类于 | 页面访问量 次
字数统计: 885 字 | 阅读时长 ≈ 4 分钟

菜：26（D），27（D=），28（A+/E）

中：29（B+）

死：25（B）

今日总结：

25. k个一组翻转链表（B）

分析：久违的链表题，虽然是hard难度，但是并没有需要特别在意的地方。对给定的值进行分情况讨论，翻转链表的方式也是经常使用的。链表整合时的方法还是要多熟悉一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = jump = ListNode(0)
        dummy.next = r = l = head
        
        while True:
            count = 0
            while r and count < k:      #用r来定位翻转范围
                r = r.next
                count += 1
            if count == k:
                pre, cur = r, l
                for _ in range(k):
                    cur.next, cur, pre = pre, cur.next, cur
                jump.next, jump, l = pre, l, r   #初始l的位置，然后将翻转后的链表转出。
            else:
                return dummy.next

26. 删除排序数组中的重复项（D）

分析：双指针的用法如果是第一次接触。还是觉得蛮有趣的。很好理解，慢指针记录当前不同元素个数，快指针对比寻找非重复元素（此题就是比较相邻即可），当找到非重复的赋值给慢指针对应位置即可。

这个题的引用法，还是挺有趣的。返回int。输出list。需要更改nums

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        length = 1        #length默认nums[0]不需要变化。
        for i in range(len(nums)-1):
            if nums[i] != nums[i+1]:
                nums[length] = nums[i+1]
                length = length + 1
                
        return length

27. 移除元素（D-）

分析：上同，没什么变化。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if len(nums) == 0:
            return 0
        length = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[length] = nums[i]
                length += 1
        return length

28. 实现strStr()（A+/E）

分析：还是比较有争议的一道题，涉及是否使用内置函数。如果，单纯算法角度。应该使用KMP算法。难度升高到hard。不管怎样学习一下，KMP算法。内置函数方法直接用find。太简单就省略了。

1
2
3
4
5
6
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(0, len(haystack) - len(needle) + 1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1

KMP版本（A+）该算法，会单独整理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if haystack == None or needle == None:
            return -1
        #generate next array, need O(n) time
        i, j, m, n = -1, 0, len(haystack), len(needle)
        next = [-1] * n
        while j < n - 1:  
            #needle[k] stands for prefix, neelde[j] stands for postfix
            if i == -1 or needle[i] == needle[j]:   
                i, j = i + 1, j + 1
                next[j] = i
            else:
                i = next[i]
        #check through the haystack using next, need O(m) time
        i = j = 0
        while i < m and j < n:
            if j == -1 or haystack[i] == needle[j]:
                i, j = i + 1, j + 1
            else:
                j = next[j]
        if j == n:
            return i - j
        return -1

29. 两数相除（B+）

分析：注意这道题的要求。不可以使用乘，除，mod运算符。想了一下，大概使用数位运算吧。代码还是不太会实现。借鉴一下。初次使用这种方式，还是给与重视一下。

<< 移位运算符。移位是指二进制。左移一，相当于变大一倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        positive = (dividend < 0) is (divisor < 0)   #判断符号是否相等。在结果处添加符号。
        dividend, divisor = abs(dividend), abs(divisor)
        res = 0
        while dividend >= divisor:   #限定继续迭代分化问题
            temp, i = divisor, 1          #由1倍开始计算。
            while dividend >= temp:
                dividend -= temp
                res += i
                i <<= 1        #i和temp同时变大一倍。就相当于快速缩小范围。
                temp <<= 1
        if not positive:   #此处判断符号
            res = -res
        return min(max(-2147483648, res), 2147483647)
0%
undefined