[leetcode]第十一部分(061-067)

61-Rotate List

问题描述

给定一个链式列表,将其右边的k位进行旋转,其中k是非负数.

示例1

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
解释:
将右边第一个数进行旋转: 5->1->2->3->4->NULL
将右边第二个数进行旋转: 4->5->1->2->3->NULL

示例2

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
解释:
将右边的第一个数进行旋转: 2->0->1->NULL
将右边的第二个数进行旋转: 1->2->0->NULL
将右边的第三个数进行旋转: 0->1->2->NULL
将右边的第四个数进行旋转: 2->0->1->NULL

解题思路

先遍历一遍列表,得到列表的长度,如果k>n,那么直接k=k%n即可.

然后维护一个长度为k的列表以及两个指针,第一个指针指向当前的节点(tail),第二个指针指向前k个节点的头结点(now),当tailnext指向NULL时,head.next=null,tail.next=head即可.

需要特别注意空列表和列表长度为1的情况…

代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        now = head
        list_len = 0
        while now is not None:
            list_len += 1
            now = now.next
        if list_len <= 0:
            return head
        k = k % list_len
        if list_len == 1 or k == 0:
            return head
        now, tail = head, head
        while k > 0:
            tail = tail.next
            k -= 1
        while tail.next is not None:
            tail = tail.next
            now = now.next
        tmp = now.next
        now.next = None
        tail.next = head
        return tmp

62-Unique Paths

问题描述

机器人位于m*n格子的左上角(在下图中标识为星)
在任何时候,机器人只能向下走或者向右走.机器人试图到达格子的右下角(在下图中表示为完成)

有多少种可能的路径?

Alt text
上图是一个7*3的格子,有多少种可能的唯一路径呢?

注意:mn最大为100.

示例1

Input: m = 3, n = 2
Output: 3
解释:
从左上角开始, 一共有三种方式到达右下角
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

示例2

Input: m = 7, n = 3
Output: 28

解题思路

针对m*n,总的看来,当需要向右走m-1,向下走n-1:

  • m=1或者n=1时,只有1种解法
  • 其它,一共需要走m+n-2步,选择其中的n-1步为向下走,一共是C_(m+n-2)^(n-1)

代码

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m == 0 or n == 0:
            return 0
        if m == 1 or n == 1:
            return 1
        total_path = m + n -2
        sub_path = (n - 1) if m > n else (m - 1)
        factor, upper_factor = 1, 1
        for i in range(1, sub_path + 1):
            factor *= i
            upper_factor *= (total_path - i + 1)
        return upper_factor / factor

63-Unique Paths II

问题描述

机器人位于m*n格子的左上角(在下图中标识为星)
在任何时候,机器人只能向下走或者向右走.机器人试图到达格子的右下角(在下图中表示为完成)

考虑如果在网格中增加一些障碍,有多少种可能的路径?

Alt text
分别使用10表示障碍和空格.

注意:mn最大为100.

示例1

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
解释:
上面的 3x3 网格中有1个障碍物.
有两种放你发可以到达右下角:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

解题思路

由于只可能向右走或者向下走,因此只可能从上面或者左边到达某位置,考虑在i,j处(i>=1,j>=1):

  • 如果obstacleGrid[i,j]!=1, 那么s[i,j]=s[i-1,j]+s[i,j-1]
  • 否则,s[i,j]=0

代码

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if len(obstacleGrid) == 0:
            return 0
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        s = [[1 for i in range(n)] for j in range(m)]
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    s[i][j] = 0
                else:
                    if i >= 1 and j >= 1:
                        s[i][j] = s[i-1][j] + s[i][j-1]
                    elif i >= 1:
                        s[i][j] = s[i-1][j]
                    elif j >= 1:
                        s[i][j] = s[i][j-1]
        return s[m-1][n-1]

64-Minimum Path Sum

问题描述

给定一个填充好非负数的m*n,从左上角到右下角的一条路径,最小化该路径上的所有数字和.

注意:每一次只能向下走或者向右走.

示例

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
解释: 由于路径 1→3→1→1→1 最小化和.

解题思路

由于只可能向右走或者向下走,因此只可能从上面或者左边到达某位置,考虑在i,j处:

  • 如果i>=1, j>=1,可能从i-1向右,也有可能从j-1向下,看哪个比较小:s[i,j]=grid[i,j]+min(s[i-1,j], s[i,j-1])
  • 如果i>=1, j<1,那么只能从i-1向右:s[i,j]=grid[i,j]+s[i-1,j]
  • 如果i<1, j>=1,那么只能从j-1向下:s[i,j]=grid[i,j]+s[i,j-1]

代码

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if len(grid) == 0:
            return 0
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if i >= 1 and j >=1:
                    grid[i][j] = grid[i][j] + (grid[i-1][j] if grid[i-1][j] < grid[i][j-1] else grid[i][j-1])
                elif i >= 1:
                    grid[i][j] = grid[i][j] + grid[i-1][j]
                elif j >= 1:
                    grid[i][j] = grid[i][j] + grid[i][j-1]
        return grid[m-1][n-1]

65-Valid Number

问题描述

判断一个给定的字符串是否能被解析为一个十进制数.
一些示例:

"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3   " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false

注意:本题目的描述非常模糊.在实现本算法之前,我们需要收集上面提到的所有所有规则.但是,下面提供了可以存在于有效十进制数字的字符:
– 数字:0-9
– 指数:e
– 正负数标识:+/-
– 小数点:.

当然,这些字符的上下文也会影响输入.

解题思路

这道题的重点应该是找出有效数字的一些规律:
– 只能包含上述字符
+/-只能出现在字符串的最前面并且最多只能出现一次(空字符不计入字符串)
– 字符串中最多只能出现一个指数e
– 指数e前面允许是小数或者整数,后面则只能是整数
– 中间不能出现空格

代码

class Solution(object):
    def isNumber(self, s):
        """
        :type s: str
        :rtype: bool
        """
        return self.isDec(s, False, False, False, False, False)

    def isDec(self, s, is_start, is_dot, is_e, is_valid, is_blank):
        num_list = [str(i) for i in range(10)]
        for i in range(len(s)):
            if s[i] == ' ':
                if is_start:
                    is_blank = True
                continue
            else:
                if is_blank:
                    return False
                if s[i] in ["+", "-"]:
                    if is_start:
                        return False
                elif s[i] == '.':
                    if is_dot or is_e:
                        return False
                    is_dot = True
                elif s[i] == 'e':
                    if not is_valid or is_e:
                        return False
                    else:
                        return self.isDec(s[i+1:], False, False, True, False, is_blank)
                elif s[i] in num_list:
                    is_valid = True
                else:
                    return False
                is_start = True
        return is_valid

66-Plus One

问题描述

给定一个非空数字数字表示一个非负的整数,将整数加1.

存储着大部分数字是的大部分有意义的数字都存储在列表的头部,数组中的每一个元素都只包含一个数字.

可以假设除了0本身之外所有整数的头部斗殴没有任何0.

示例1

Input: [1,2,3]
Output: [1,2,4]
解释: 数组表示整数 123.

示例2

Input: [4,3,2,1]
Output: [4,3,2,2]
解释: 数组表示整数4321.

解题思路

从数组的最后一个元素出发,加1,如果遇到9,则将当前元素置为0,继续向前走,加1,直到遇到数组前列为止.

代码

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        return self.plusOnePlace(digits, len(digits)-1)

    def plusOnePlace(self, digits, place):
        now_sum = digits[place] + 1
        digits[place] = now_sum % 10
        if now_sum / 10 == 1:
            if place == 0:
                digits.insert(0, 1)
                return digits
            else:
                return self.plusOnePlace(digits, place-1)
        else:
            return digits

67-Add Binary

问题描述

给定两个二进制字符串,返回它们的和(也是一个二进制字符串).
输入字符串都非空,并且只包含字符10.

示例1

Input: a = "11", b = "1"
Output: "100"

示例2

Input: a = "1010", b = "1011"
Output: "10101"

解题思路

从后往前对齐,如果相加小于2,则直接进入下一位;如果大于2,则将该位置为%2,下一位加上/2的值.

代码

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        return self.plusOnePlace(digits, len(digits)-1)

    def plusOnePlace(self, digits, place):
        now_sum = digits[place] + 1
        digits[place] = now_sum % 10
        if now_sum / 10 == 1:
            if place == 0:
                digits.insert(0, 1)
                return digits
            else:
                return self.plusOnePlace(digits, place-1)
        else:
            return digits

67-Add Binary

问题描述

给定两个二进制字符串,返回它们的和(也是一个二进制字符串).
输入字符串都非空,并且只包含字符10.

示例1

Input: a = "11", b = "1"
Output: "100"

示例2

Input: a = "1010", b = "1011"
Output: "10101"

解题思路

从后往前对齐,如果相加小于2,则直接进入下一位;如果大于2,则将该位置为%2,下一位加上/2的值.

代码

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        if len(a) < len(b):
            return self.addBinary(b, a)
        ans = ""
        idx = 0
        flag = 0
        while idx < len(b) or flag > 0:
            if idx < len(a):
                flag += int(a[len(a) - idx - 1])
            else:
                break
            if idx < len(b):
                flag += int(b[len(b) - idx - 1])
            ans = str(flag%2) + ans
            flag = flag / 2
            idx += 1
        if flag == 0:
            ans = a[:len(a) - idx] + ans
        else:
            ans = str(flag) + ans
        return ans
打赏

mickey

记录生活,写给几十年后的自己。