leetcode日常总结

566，581，605，628，643，661，665

566：重塑矩阵

题目描述：

函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

思路：

判断个数一样，把原矩阵写成生成器，一个一个往外出数据，按照行列填充到新矩阵

代码：

class Solution(object):

    def matrixReshape(self, nums, r, c):

        """

        :type nums: List[List[int]]

        :type r: int

        :type c: int

        :rtype: List[List[int]]

        function(){ //XM返佣 http://www.fx61.com/brokerlist/xm.html

        """

        if r*c != len(nums)*len(nums[0]):

            return nums

        def num(nums):

            for row in nums:

                for element in row:

                    yield element

        g=num(nums)

        result=[]

        for i in range(r):

            row=[]

            for j in range(c):

                row.append(next(g))

            result.append(row)

        return result

581：最短无序连续子数组

题目描述：

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。你找到的子数组应是最短的，请输出它的长度。

思路：

从左往右遍历，如果最左位置上的数为数组中最小的值，则pop掉；从右往左遍历，如果最右位置上的数为数组中最大的值，则pop掉；最终数组长度为子数组需要排序的长度。

代码：

class Solution(object):

    def findUnsortedSubarray(self, nums):

        """

        :type nums: List[int]

        :rtype: int

        """

        if nums==sorted(nums):

            return 0

        while nums[-1]==max(nums):

            nums.pop(-1)

        while nums[0]==min(nums):

            nums.pop(0)

        return len(nums)

605：种花问题

题目描述：

假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

思路:

想添加一个数字必须是 1.开头两个0 [0,0,…] 2.结尾两个0 […,0,0] 3. 中间三个0 […,0,0,0,…]，所以前后补零处理边界看是否三个连续的位置都为0.

代码：

class Solution(object):

    def canPlaceFlowers(self, flowerbed, n):

        """

        :type flowerbed: List[int]

        :type n: int

        :rtype: bool

        """

        tmp=[0]+flowerbed+[0]

        for i in range(1,len(tmp)-1):

            if tmp[i]==0 and tmp[i-1]==0 and tmp[i+1]==0:

                tmp[i]=1

                n-=1

        if n<=0:

            return True

        else:

            return False

   628：三个数的最大乘积

题目描述：

给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

思路：

1：排序，如果没有负数则后面三个数的乘积为最大，若有负数，则可比较前两个值及最后一个最大值的乘积与最后三个值乘积谁更大。

2：求出数组中最大的三个数以及最小的两个数，因此我们可以不用排序，用线性扫描直接得出这五个数。

代码：

class Solution(object):

    def maximumProduct(self, nums):

        """

        :type nums: List[int]

        :rtype: int

        """

        nums.sort()

        return max(nums[0]*nums[1]*nums[-1],nums[-1]*nums[-2]*nums[-3])

643：子数组最大平均数Ⅰ
题目描述：
给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
思路：
找出子数组中长度为k的最大值，然后除以长度。
滑动窗口 当移动一位的时候 只需要减去前一个i - 1 加上新的一个i + k - 1

代码：

class Solution(object):

    def findMaxAverage(self, nums, k):

        """

        :type nums: List[int]

        :type k: int

        :rtype: float

        """

        ave=sum(nums[:k])

        tmp=ave

        for i in range(len(nums)-k):

            tmp=tmp-nums[i]+nums[i+k]

            if tmp>ave:

                ave=tmp

        return ave*1.0/k

661：图片平滑器

题目描述：

包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。

思路：

数组补边法消除特殊状态，将原数组周围用-1填充，构成新数组，结果i行j列的值即为该数组i行j列为左上角元素的3X3矩阵的和+加上-1的个数，再除以 9减去 -1的个数

代码：

class Solution(object):

    def imageSmoother(self, M):

        """

        :type M: List[List[int]]

        :rtype: List[List[int]]

        """

        row=len(M)

        clu=len(M[0])

        M.insert(0,[-1]*clu)

        M.append([-1]*clu)

        for i in range(len(M)):

            M[i].insert(0,-1)

            M[i].append(-1)

        res=[]

        for i in range(row):

            row=[]

            for j in range(clu):

                lst=[M[i][j],M[i][j+1],M[i][j+2],M[i+1][j],M[i+1][j+1],M[i+1][j+2],M[i+2][j],M[i+2][j+1],M[i+2][j+2]]

                n=lst.count(-1)

                item=int((sum(lst)+n)/(9-n))

                row.append(item)

            res.append(row)

        return res

665：非递减数列

题目描述：

给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。

思路：

使前一个数字小于或等于当前数字

使当前数字等于先前的数字

当找到nums[i-1] > nums[i]，采用方式一，通过改变nums[i-1]的值，这样不会影响了后续操作。还有，如果nums[i-2] > nums[i]，采用方式二，改变nums[i]的值。

代码：

class Solution(object):

    def checkPossibility(self, nums):

        """

        :type nums: List[int]

        :rtype: bool

        """

        if len(nums)<=2:

            return True

        for i in range(0,len(nums)-1):

            if i==0 and nums[i]>nums[i+1] and nums[i+1]<=nums[i+2]:

                nums[i]=nums[i+1]

                break

            elif i != 0:

                if nums[i]>nums[i+1]:

                    if nums[i+1]>=nums[i-1]:

                        nums[i]=nums[i+1]

                    else:

                        nums[i+1]=nums[i]

                    break

        for i in range(0,len(nums)-1):

            if nums[i]>nums[i+1]:

                return False

        else:

            return True