Boo-BKing.

下雨 最爱听的旋律

发表于 更新于 分类于
本文字数： 752 阅读时长 ≈ 1 分钟

题目描述

给定一个链表，每 k 个结点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果结点总数不是 k 的整数倍，那么请将最后剩余的结点保持原有顺序。

1
2
3
4
5
样例
给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明

你的算法只能使用常数的额外空间。
你不能只是单纯的改变结点内部的值，而是需要实际进行结点交换。

算法

  1. 看代码即可

时间复杂度

仅遍历一遍所有结点，所以是 O(L)。

空间复杂度

仅使用常数的额外空间。

python code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = prev = ListNode(0)
        dummy.next = head
        cur = head
        lens = 0
        while head:
            lens += 1
            head = head.next
        m = lens // k
        for i in range(m):
            for j in range(k-1):
                tmp = cur.next
                cur.next = tmp.next
                tmp.next = prev.next
                prev.next = tmp
            prev = cur
            cur = prev.next
        return dummy.next

发表于 更新于 分类于
本文字数： 752 阅读时长 ≈ 1 分钟

题目描述

给定一个链表，每 k 个结点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果结点总数不是 k 的整数倍，那么请将最后剩余的结点保持原有顺序。

1
2
3
4
5
样例
给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明

你的算法只能使用常数的额外空间。
你不能只是单纯的改变结点内部的值，而是需要实际进行结点交换。

算法

  1. 看代码即可

时间复杂度

仅遍历一遍所有结点，所以是 O(L)。

空间复杂度

仅使用常数的额外空间。

python code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = prev = ListNode(0)
        dummy.next = head
        cur = head
        lens = 0
        while head:
            lens += 1
            head = head.next
        m = lens // k
        for i in range(m):
            for j in range(k-1):
                tmp = cur.next
                cur.next = tmp.next
                tmp.next = prev.next
                prev.next = tmp
            prev = cur
            cur = prev.next
        return dummy.next

发表于 更新于 分类于
本文字数： 900 阅读时长 ≈ 1 分钟

题目描述

给定一个含有正整数和负整数的环形数组 nums。 如果某个索引中的数 k 为正数，则向前移动 k 个索引。相反，如果是负数 (-k)，则向后移动 k 个索引。因为数组是环形的，所以可以假设最后一个元素的下一个元素是第一个元素，而第一个元素的前一个元素是最后一个元素。

确定 nums 中是否存在循环（或周期）。循环必须在相同的索引处开始和结束并且循环长度 > 1。此外，一个循环中的所有运动都必须沿着同一方向进行。换句话说，一个循环中不能同时包括向前的运动和向后的运动。

示例 1：

1
2
3
输入：[2,-1,1,2,2]
输出：true
解释：存在循环，按索引 0 -> 2 -> 3 -> 0 。循环长度为 3 。

示例 2：

1
2
3
输入：[-1,2]
输出：false
解释：按索引 1 -> 1 -> 1 ... 的运动无法构成循环，因为循环的长度为 1 。根据定义，循环的长度必须大于 1 。

示例 3:

1
2
3
输入：[-2,1,-1,-2,-2]
输出：false
解释：按索引 1 -> 2 -> 1 -> ... 的运动无法构成循环，因为按索引 1 -> 2 的运动是向前的运动，而按索引 2 -> 1 的运动是向后的运动。一个循环中的所有运动都必须沿着同一方向进行。

提示：

  1. -1000 ≤ nums[i] ≤ 1000
  2. nums[i] ≠ 0
  3. 0 ≤ nums.length ≤ 5000

python code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        n = len(nums)
        Base = 10000
        for i in range(n):
            if nums[i] >= Base: continue
            k = i 
            S = Base + i
            last = -1
            t = nums[k] > 0
            while (t ^ (nums[k] > 0)) == 0 and nums[k] < Base:
                p = (nums[k] + k) % n
                last = nums[k]
                nums[k] = S
                k = p
                if k == i: break
            if (last % n) and nums[k] == S: return True
        return False

发表于 更新于 分类于
本文字数： 521 阅读时长 ≈ 1 分钟

题目描述

神奇的字符串 S 只包含 ‘1’ 和 ‘2’，并遵守以下规则：

字符串 S 是神奇的，因为串联字符 ‘1’ 和 ‘2’ 的连续出现次数会生成字符串 S 本身。

字符串 S 的前几个元素如下：S = “1221121221221121122 ……”

如果我们将 S 中连续的 1 和 2 进行分组，它将变成：

1 22 11 2 1 22 1 22 11 2 11 22 ……

并且每个组中 ‘1’ 或 ‘2’ 的出现次数分别是：

1 2 2 1 1 2 1 2 2 1 2 2 ……

你可以看到上面的出现次数就是 S 本身。

给定一个整数 N 作为输入，返回神奇字符串 S 中前 N 个数字中的 ‘1’ 的数目。

注意：N 不会超过 100,000。

示例：

1
2
3
输入：6
输出：3
解释：神奇字符串 S 的前 6 个元素是 “12211”，它包含三个 1，因此返回 3。

python code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def magicalString(self, n: int) -> int:
        s = "122"
        res = 0
        k = 1
        for i in range(2, n):
            m = int(s[i])
            for j in range(m):
                s += str(k)
            k = 3 - k
        for i in range(n):
            if s[i] == '1':
                res += 1
        return res

发表于 更新于 分类于
本文字数： 1k 阅读时长 ≈ 1 分钟

题目描述

假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。

你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设总是存在一个答案。

示例 1:

1
2
3
4
5
输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2:

1
2
3
4
5
输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

提示:

  1. 两个列表的长度范围都在 [1, 1000]内。
  2. 两个列表中的字符串的长度将在[1，30]的范围内。
  3. 下标从0开始，到列表的长度减1。
  4. 两个列表都没有重复的元素。

python code

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        l1 = {list1[i]:i for i in range(len(list1))}
        l2 = {list2[i]:i for i in range(len(list2))}
        inter = set(list1) & set(list2)
        index = {i:l1[i]+l2[i] for i in inter}
        res = []
        for i in index:
            if index[i] == min(index.values()):
                res.append(i)
        return res

发表于 更新于 分类于
本文字数： 486 阅读时长 ≈ 1 分钟

题目描述

对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为 “完美数”。给定一个 正整数 n， 如果他是完美数，返回 True，否则返回 False。

阅读全文 »

发表于 更新于 分类于
本文字数： 752 阅读时长 ≈ 1 分钟

题目描述

给定一个链表，每 k 个结点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果结点总数不是 k 的整数倍，那么请将最后剩余的结点保持原有顺序。

1
2
3
4
5
样例
给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明

你的算法只能使用常数的额外空间。
你不能只是单纯的改变结点内部的值，而是需要实际进行结点交换。

算法

  1. 看代码即可

时间复杂度

仅遍历一遍所有结点，所以是 O(L)。

空间复杂度

仅使用常数的额外空间。

python code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = prev = ListNode(0)
        dummy.next = head
        cur = head
        lens = 0
        while head:
            lens += 1
            head = head.next
        m = lens // k
        for i in range(m):
            for j in range(k-1):
                tmp = cur.next
                cur.next = tmp.next
                tmp.next = prev.next
                prev.next = tmp
            prev = cur
            cur = prev.next
        return dummy.next

发表于 更新于 分类于
本文字数： 752 阅读时长 ≈ 1 分钟

题目描述

给定一个链表，每 k 个结点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果结点总数不是 k 的整数倍，那么请将最后剩余的结点保持原有顺序。

1
2
3
4
5
样例
给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明

你的算法只能使用常数的额外空间。
你不能只是单纯的改变结点内部的值，而是需要实际进行结点交换。

算法

  1. 看代码即可

时间复杂度

仅遍历一遍所有结点，所以是 O(L)。

空间复杂度

仅使用常数的额外空间。

python code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = prev = ListNode(0)
        dummy.next = head
        cur = head
        lens = 0
        while head:
            lens += 1
            head = head.next
        m = lens // k
        for i in range(m):
            for j in range(k-1):
                tmp = cur.next
                cur.next = tmp.next
                tmp.next = prev.next
                prev.next = tmp
            prev = cur
            cur = prev.next
        return dummy.next