leetcode 1.04-1.10

2021-01-10

剑指offer22 链表中倒数第k个节点
1015 可被K整除的最小整数

剑指offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：快慢指针

AC代码：

class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        tail = head
        ret = head
        loop = 0
        while loop < k and tail != None:
            tail = tail.next
            loop += 1
        while tail != None:
            ret = ret.next
            tail = tail.next
        return ret

1015. 可被K整除的最小整数

给定正整数 K，你需要找出可以被 K 整除的、仅包含数字 1 的最小正整数 N。

返回 N 的长度。如果不存在这样的 N，就返回 -1。

示例 1：

输入：1
输出：1
解释：最小的答案是 N = 1，其长度为 1。

示例 2：

输入：2
输出：-1
解释：不存在可被 2 整除的正整数 N 。

示例 3：

输入：3
输出：3
解释：最小的答案是 N = 111，其长度为 3。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-integer-divisible-by-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：N是完全由1组成的数字，那么必然不能被2和5整除，所以首先把这两种情况排除。之后逐步增大N，判断能否整除K即可。需要注意N可能会超出int表示范围，详情见官方题解数学证明。

AC代码：

class Solution(object):
    def smallestRepunitDivByK(self, K):
        """
        :type K: int
        :rtype: int
        """
        if K % 2 is 0 or K % 5 is 0:
            return -1
        N = 1
        ret = 1
        while N % K != 0:
            N = N * 10 + 1
            ret += 1
        return ret