Boo-BKing.

下雨 最爱听的旋律

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

电子游戏 “辐射4” 中，任务“通向自由”要求玩家到达名为 “Freedom Trail Ring” 的金属表盘，并使用表盘拼写特定关键词才能开门。给定一个字符串 ring，表示刻在外环上的编码；给定另一个字符串 key，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

阅读全文 »

发表于 更新于 分类于
本文字数： 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

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

题目描述

给定一个整数数组和一个整数 **k**，你需要在数组里找到不同的 **k-diff 数对，并返回不同的 **k-diff 数对 的数目。

这里将 k-diff 数对定义为一个整数对 (nums[i], nums[j])，并满足下述全部条件：

  • 0 <= i, j < nums.length
  • i != j
  • |nums[i] - nums[j]| == k

注意，|val| 表示 val 的绝对值。

阅读全文 »

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

题目描述

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

阅读全文 »

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

题目描述

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

1
2
3
4
5
样例
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
输入: [3,3,7,7,10,11,11]
输出: 10

注意

您的解法仅能使用 O(logn)时间复杂度和 O(1) 空间复杂度。

算法

二分（左右指针）

python code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        l = 0
        r = len(nums) - 1
        while l < r:
            mid = l + r >> 1
            if nums[mid] == nums[mid-1]:
                if (mid - l) % 2 == 0:
                    r = mid - 2
                else:
                    l = mid + 1
            elif nums[mid] == nums[mid+1]:
                if (r - mid) % 2 == 0:
                    l = mid + 2
                else:
                    r = mid - 1
            else:
                return nums[mid]
        return nums[l]

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

题目描述

给定一个 24 小时制（小时:分钟）的时间列表，找出列表中任意两个时间的最小时间差并已分钟数表示。

1
2
3
样例
输入: ["23:59","00:00"]
输出: 1

注意

列表大小在 220000 之间。
每个时间取值在 00:0023:59 之间。

算法

(排序) O(nlogn)
将原数组按照小时，分钟从小到大排序。
排序后，末尾再添加一个时间为最早的时间加24小时。
然后从第二个时间开始和前一个时间对比找最小值即可。

时间复杂度

排序后，仅需要线性扫描，故时间复杂度为 O(n)。

python code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        if len(timePoints) > 1440: return 0
        s = set()
        for c in timePoints:
            time = int(c[:2]) * 60 + int(c[3:])
            if time in s:
                return 0
            s.add(time)
        s = sorted(s)
        s.append(s[0] + 1440)
        res = min(s[i] - s[i-1] for i in range(1, len(s)))
        return res