[leetcode]第十部分(054-060)

54-Spiral Matrix

问题描述

给定一个m*n个元素的矩阵(m行,n列),以螺旋状的形式返回矩阵的所有元素.

示例1

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

示例2

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

解题思路

螺旋状,是一圈一圈地遍历的,可以使用分治法看待这个问题,对于每一圈(假设为第k圈):

  • 从起点(i=k,j=k)开始,j向右移动,直到m-k-1为止
  • i向下移动,直到i=n-k-1为止
  • j向左移动,直到j=k为止
  • i向上移动,直到i=k+1为止

k=k+1继续下一圈,一共遍历(n+1)/2(m+1)/2圈(选择mn中较小的那一个).

注意:特别需要注意四个边界节点,不要重复添加.

代码

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        n = len(matrix)
        if n == 0:
            return []
        m = len(matrix[0])
        ans = list()
        total_rnd = (n+1)/2
        if n > m:
            total_rnd = (m+1)/2
        for i in range(total_rnd):
            self.spiralKRound(matrix, i, m, n, ans)
        return ans


    def spiralKRound(self, matrix, k, m, n, ans):
        i = k
        j = k
        while j <= m-k-1:
            ans.append(matrix[i][j])
            j += 1
        j = m - k - 1
        if i == n - k - 1:
            return
        i = k + 1
        while i <= n-k-1:
            ans.append(matrix[i][j])
            i += 1
        i = n - k - 1
        if j == k:
            return
        j = m - k - 2
        while j >= k:
            ans.append(matrix[i][j])
            j -= 1
        j = k
        if i == k:
            return
        i = n - k - 2
        while i > k:
            ans.append(matrix[i][j])
            i -= 1

55-Jump Game

问题描述

给定一个非负整数,我们最开始的时候在数组的第一个索引处.
数组中的每个元素都表示在该位置可以跳的最大步数.
判断我们是否可以调到最后一个索引.

示例1

Input: [2,3,1,1,4]
Output: true
解释: 第一步从索引0跳到索引1,然后跳3步到最后的位置

示例2

Input: [3,2,1,0,4]
Output: false
解释: 无论如何,我们总会跳到索引3的位置.而其最大的跨度为0,使得无法跳到最后一个索引.

解题思路

从题干中注意到:数组为非负数组,那么无法跳到最后一个索引只有一种情况:无论如何都会跳转到位置为0的点.因此,从前向后遍历,遇到第一个为0的元素则停止,记录当前的索引位置,继续向前遍历,判断前面的位置是否能跳过该位置,如果可以,则放弃该标识;继续向前遍历,否则直接返回false.时间复杂度为O(n*m),其中nnums数组的长度,m为数组中0的个数.

特别注意:对于nums=[0]的情况,已经到最末尾了,所以只需要返回true即可.

代码

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        for i in range(len(nums)-1):
            if nums[i] == 0:
                zero_idx = i
                j = zero_idx - 1
                while j >= 0:
                    if nums[j] > zero_idx - j:
                        break
                    j -= 1
                if j == -1:
                    return False
        return True

56-Merge Intervals

问题描述

给定一个区间的集合,合并所有重合的区间.

示例1

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
解释: 由于区间 [1,3] 和[2,6] 重合, 将其合并为 [1,6].

示例2

Input: [[1,4],[4,5]]
Output: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 有重合.

解题思路

从前往后遍历intervals数组,将第一个区间直接加入ans,从第二个区间(假设为[j_1, j_2])开始,与ans中的区间([i_1,i_2])比较:

  • 如果j_2<i_1,那么直接将其插入到i的位置
  • 如果j_1>i_2,那么i=i+1,直到到达ans的末尾为止,插入len(ans)
  • 否则,合并为[min(i_1,j_1), max(i_2,j_2)].将当前区间从ans中删除,然后迭代插入合并后的区间

代码

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        if len(intervals) == 0:
            return list()
        ans = list()
        for j in range(len(intervals)):
            cur_int = intervals[j]
            ans = self.mergeSort(ans, cur_int)
        return ans

    def mergeSort(self, ans, cur_int):
        if len(ans) == 0:
            return [cur_int]
        cur_start, cur_end = cur_int.start, cur_int.end
        for i in range(len(ans)):
            now_ans = ans[i]
            now_start, now_end = now_ans.start, now_ans.end
            if cur_end < now_start:
                ans.insert(i, cur_int)
                return ans
            if cur_start > now_end:
                continue
            new_start = cur_start if cur_start <= now_start else now_start
            new_end = cur_end if cur_end >= now_end else now_end
            new_int = Interval(new_start, new_end)
            ans = ans[:i] + ans[i+1:]
            return self.mergeSort(ans, new_int)
        ans.append(cur_int)
        return ans

57-Insert Interval

问题描述

给定一个非重合的区间列表,向该列表中插入一个新区间(在必要的情况下进行合并).

可以假设区间是基于起点升序排列的.

示例1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

示例2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
解释: 由于新区间 [4,8] 与 [3,5],[6,7],[8,10]等区间重合.

解题思路

类似于上一题的思路,针对每一个待插入的区间([j_1,j_2]): 与intervals中的区间([i_1,i_2])比较:

  • 如果j_2<i_1,那么直接将其插入到i的位置
  • 如果j_1>i_2,那么i=i+1,直到到达intervals的末尾为止,插入len(intervals)
  • 否则,合并为[min(i_1,j_1), max(i_2,j_2)].将当前区间从intervals中删除,然后迭代插入合并后的区间

Alt text 结果…超内存了,忧伤…想想别的办法.

感觉超内存的原因使用了递归,因此我们需要思考下能不能去掉递归…

按照上面的想法,前两种情况不变…
遇到第三种情况的时候:
– 如果i_2<j_2,说明i的末位置需要更新,记录当前start_i=i,然后i+=1,直到数组末尾或者i_1>j_2为止,删除start_iend_i的值,修改为[min(i_1,j_1), max(i_2,j_2)]

代码

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        cur_start, cur_end = newInterval.start, newInterval.end
        for i in range(len(intervals)):
            now_ans = intervals[i]
            now_start, now_end = now_ans.start, now_ans.end
            if cur_end < now_start:
                intervals.insert(i, newInterval)
                return intervals
            if cur_start > now_end:
                continue
            if now_end >= cur_end:
                new_start = now_start if now_start < cur_start else cur_start
                intervals[i] = Interval(new_start, now_end)
                return intervals
            else:
                start_now = i
                while i < len(intervals) and now_start <= cur_end:
                    i += 1
                    if len(intervals) > i:
                        now_ans = intervals[i]
                        now_start = now_ans.start
                end_now = i
                new_start = intervals[start_now].start if intervals[start_now].start < cur_start else cur_start
                new_end = intervals[end_now-1].end if intervals[end_now-1].end > cur_end else cur_end
                del intervals[start_now: end_now]
                intervals.insert(start_now, Interval(new_start, new_end))
                return intervals
        intervals.append(newInterval)
        return intervals

58-Length of Last Word

问题描述

给定一个由大写/小写字母以及空字符' '构成的字符串s,返回字符串中最后一个单词的长度.如果最后一个单词不存在,返回0.

注意:一个单词的定义为-只包含非空字符的字符序列.

示例

Input: "Hello World"
Output: 5

解题思路

返回最后一个单词的长度,结合单词的定义,我们不难想到:从后往前遍历,从第一个非空字符开始算起,遇到非空字符或者字符串的头部为止,返回当前的字符串长度.

代码

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        i = len(s) - 1
        isLast = False
        ans = 0
        while i >= 0:
            if s[i] == " ":
                if not isLast:
                    i -= 1
                    continue
                else:
                    return ans
            else:
                ans += 1
                isLast = True
            i -= 1
        return ans

59-Spiral Matrix II

问题描述

给定一个正整数n,以螺旋的顺序使用从1n^2的元素填满生成的方阵.

示例

Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

解题思路

感觉是之前题目的简化版,只需要考虑需要旋转的圈数即可((n+1)/2),第i圈的起始位置为i,i(分别使用ij表示横纵坐标)

  • j向右移动,直到n-1-i为止
  • i=i+1,j=n-1-i,i向下移动,直到n-1-i为止
  • i=n-1-i,j=n-1-i-1,j向左移动,直到i为止
  • i=n-1-i-1,j=i,i向上移动,直到i+1为止

开始第二圈…时间复杂度为O(n/2*n),代码提交之后居然是前100%…开心.

代码

class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        cir_num = (n+1) / 2
        ans = [[0 for _ in range(n)] for _ in range(n)]
        num = 1
        for now_cir in range(cir_num):
            i, j = now_cir, now_cir
            while j <= n - 1 - now_cir:
                ans[i][j] = num
                num += 1
                j += 1
            i += 1
            j = n - 1 - now_cir
            while i <= n - 1 - now_cir:
                ans[i][j] = num
                num += 1
                i += 1
            j -= 1
            i = n - 1 - now_cir
            while j >= now_cir:
                ans[i][j] = num
                num += 1
                j -= 1
            i -= 1
            j = now_cir
            while i >= now_cir + 1:
                ans[i][j] = num
                num += 1
                i -= 1
        return ans

60-Permutation Sequence

问题描述

集合[1,2,3,...,n]包含一共n!个不重复的遍历.

通过按顺序列举和标记所有的遍历,在n=3时可以得到下面的序列:

"123"
"132"
"213"
"231"
"312"
"321

给定nk,返回第k个遍历序列.

注意
– 给定的n将会在19之间
– 给定的k将会在1n!之间

示例1

Input: n = 3, k = 3
Output: "213"

示例2

Input: n = 4, k = 9
Output: "2314"

解题思路

参考之前遍历的做法,从后往前遍历,碰到升序的就停止,将其替换成i+1,再将后面的数字升序排列即可.

然后,果然时间超了…
于是乎,得想其它的办法,是不是没有必要从i开始呢?毕竟只需要得到第k个遍历.我们不难发现,以每个数字开头的遍历均有(n-1)!种,先用k/(n-1)就可以知道从第几个数字开头了,然后再计算k%(n-1)即可.

代码

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        n_seq = 1
        for i in range(1, n):
            n_seq *= i
        start_num = (k-1) / n_seq + 1
        new_k = k - (start_num - 1) * n_seq
        idx = 1
        seq_list = list()
        for i in range(1, n+1):
            if i != start_num:
                seq_list.append(i)
        while idx < new_k:
            seq_list = self.getNextPermutation(seq_list)
            idx += 1
        ans = ""
        if start_num > 0:
            ans += str(start_num)
        for i in seq_list:
            ans += str(i)
        return ans


    def getNextPermutation(self, seq_list):
        for i in range(len(seq_list)-1, -1, -1):
            if i >= 1 and seq_list[i] < seq_list[i-1]:
                continue
            seq_list = seq_list[:i-1] + self.insertVal(seq_list[i-1:])
            return seq_list
        return seq_list

    def insertVal(self, sub_list):
        if len(sub_list) <= 1:
            return sub_list
        pivot = sub_list[0]
        for i in range(len(sub_list)-1, 0, -1):
            if pivot > sub_list[i]:
                continue
            else:
                sub_list[0], sub_list[i] = sub_list[i], sub_list[0]
                break
        interval = (len(sub_list) - 1)/2
        for i in range(1, interval+1):
            sub_list[i], sub_list[len(sub_list)-i] =  sub_list[len(sub_list)-i], sub_list[i]
        return sub_list
打赏

mickey

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