每日归档： 2022年1月23日

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

动态规划：dp[i][j]表示从00到ij的所有可能的路径数量（一般dp数组就表示我们要求的结果）

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:

        m, n = len(obstacleGrid), len(obstacleGrid[0])
        if m == 1 and n == 1:
            if obstacleGrid[0][0] == 1: return 0
            else: return 1
        
        dp = [[0] * n for _ in range(m)]

        for i in range(m):
            if obstacleGrid[i][0] == 1: break
            dp[i][0] = 1
        
        for j in range(n):
            if obstacleGrid[0][j] == 1: break
            dp[0][j] = 1
        
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[-1][-1]

一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

思路：将该问题转换为：走m-1 步1，走n-1步0，所有的排列组合：

即 m-1 个A和 n-1个B的排列组合数：

采用推导法：已知 m-1 个A和 n-1个B的排列组合数 ，那么根据 m-1 个A和 n-1个B的排列组合数 推导m个A，n个B的排列组合数。

(1) 当有m个A和n个B时，总的排列数为(m+n)!/m!/n!;

(2) 由于不知道m和n哪个大，故两个值都减1，最后知道m和n中其中一个为0；

(3) 当有m-1个A和n-1个B时，总的排列数为(m+n-2)!/(m-1)!/(n-1)!;

(4)这样两个的关系为：fun(m,n) = fun(m-1,n-1)(m+n)(m+n-1)/m/n;

# @lc app=leetcode.cn id=62 lang=python3
#
# [62] 不同路径
#

# @lc code=start
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        m=m-1
        n=n-1
        def subuniquePaths(m,n):
            if m==0 or n==0:
                return 1
            else:
                return int(subuniquePaths(m - 1 , n - 1)*(m + n)*(m+n-1)/m/n)
        return subuniquePaths(m,n)

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

代码：

# @lc app=leetcode.cn id=61 lang=python3
#
# [61] 旋转链表
#

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        def lenlink(head):
            i=0
            while head != None:
                head=head.next
                i=i+1
            return i
        lens=lenlink(head)
        if lens==0:
            return head
        k=k%(lens) 
        newlist=ListNode(0,None)
        newcur=newlist
        cur1 = head
        cur2 = head
        for i in range(lens-k):
            cur1=cur1.next
            #print(cur1.val)
        for i in range(lens):
            if i < k:
               newcur.val= cur1.val
               print(newcur.val)
               cur1=cur1.next
               newcur.next=ListNode(0,None)
               newcur=newcur.next
            
            else:
               newcur.val= cur2.val
               #print(cur2.val)
               cur2=cur2.next
               if i<lens-1:
                    newcur.next=ListNode(0,None)
               newcur=newcur.next 
        return newlist

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

给定 n 和 k，返回第 k 个排列。

示例 1：

输入：n = 3, k = 3
输出："213"

示例 2：

输入：n = 4, k = 9
输出："2314"

示例 3：

输入：n = 3, k = 1
输出："123"

提示：

• 1 <= n <= 9
• 1 <= k <= n!

# @lc app=leetcode.cn id=60 lang=python3
#
# [60] 排列序列
#

# @lc code=start
class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        nums=[i for i in range(1,n+1)]

        def subgetPermutation(N,k,nums,str1): 
          import math
            #print(k)
          while 1:
            if k<0 or len(nums)==1: 
                str1=str1+str(nums[0])
                return str1
            x=math.factorial(N-1)
            for i in range(1,len(nums)+1):
                if i*x>=k:    
                    k=k-(i-1)*x if k-(i-1)*x>0 else k
                    N=N-1
                    #print(i,k,N,nums)

                    str1=str1+str(nums[i-1])
                    #print(str1)
                    nums.remove(nums[i-1])
                    #print(nums)
                    break
        return subgetPermutation(n,k,nums,"")
# @lc code=end

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

示例 3：

输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]

示例 4：

输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]

示例 5：

输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]

提示：

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= intervals[i][0] <= intervals[i][1] <= 105
• intervals 根据 intervals[i][0] 按 升序 排列
• newInterval.length == 2
• 0 <= newInterval[0] <= newInterval[1] <= 105

代码实现：

#
# [57] 插入区间
#

# @lc code=start
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        intervals.append(newInterval)
        import copy
        x=intervals
        y=copy.deepcopy(intervals) 
        lens=len(y)
        x.sort(key=lambda x: (x[0], -x[1]))
        y.sort(key=lambda x: (x[1], -x[0]))
        #print(x,y)

        i=x.index(newInterval)
        j=y.index(newInterval)
        if i>0 and x[i][0]<=x[i-1][1]:
            i=i-1
        if j<lens-1 and y[j][1]>=y[j+1][0]:
            j=j+1
        #print(i)
        return x[0:i]+[[x[i][0],y[j][1]]]+y[j+1:]

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 20

# @lc app=leetcode.cn id=59 lang=python3
#
# [59] 螺旋矩阵 II
#

# @lc code=start
from calendar import c


class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        rev=[[0]*n for i in range(n)]
        rstart=0
        cstart=0
        rend=n-1
        cend=n-1
        mid=1
        while cend>=cstart and rstart<=rend:
            for l in range(cstart,cend+1):
                rev[rstart][l]=mid
                mid=mid+1
            #rev.extend(matrix[rstart][cstart:cend+1])
            for l in range(rstart+1,rend):
                rev[l][cend]=mid   
                mid=mid+1
            for l in range(cend,cstart-1,-1):
                rev[rend][l]=mid   
                mid=mid+1
            #rev.extend(matrix[rend][cstart:cend+1][::-1])
            for l in range(rend-1,rstart,-1):
                rev[l][cstart]=mid   
                mid=mid+1
            cend=cend-1
            cstart=cstart+1
            rstart=rstart+1
            rend=rend-1
        if n//2!=n/2:
            rev[n//2][n//2]=n*n
        return rev