编程能力提升_15

淡淡的烟草味﹌ 2022-02-23 11:38 589阅读 0赞

**目录**

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

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

3.给定一个未经排序的整数数组，找到最长且连续的的递增序列。

4.给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

5.给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数，使得字符串B成为叠加后的字符串A的子串，如果不存在则返回 -1。

6.给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。

7.给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

8.给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

9.有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。

--------------------

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

**示例 1:**

输入:
    [[1,1,1],
     [1,0,1],
     [1,1,1]]
    输出:
    [[0, 0, 0],
     [0, 0, 0],
     [0, 0, 0]]
    解释:
    对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
    对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
    对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0

class Solution:
        def imageSmoother(self, M: List[List[int]]) -> List[List[int]]:
            ring=len(M)
            col=len(M[0])
            m=[[0]*col for i in range(ring)]
            for i in range(ring):
                for j in range(col):
                    sums=0
                    count=0
                    for kx in range(-1,2):
                        for ky in range(-1,2):
                            if 0<=j+ky and j+ky<=col-1 and 0<=i+kx and i+kx<=ring-1:
                                sums+=M[i+kx][j+ky]
                                count+=1
                    m[i][j]=sums//count
            return m

class Solution:
        def imageSmoother(self, M):
            """
            :type M: List[List[int]]
            :rtype: List[List[int]]
            """
            copyM=[]
            for x in range(len(M)):
                copyM.append([0]*len(M[0]))
            
            row=len(M)
            col=len(M[0])
            
            for i in range(row):
                for j in range(col):
                    num=1
                    count=M[i][j]
                    # 找八个
                    #上一行
                    if i-1>=0: 
                        num+=1
                        count+=M[i-1][j]
                        if j-1>=0:
                            num+=1
                            count+=M[i-1][j-1]
                        if j+1<=col-1:
                            num+=1
                            count+=M[i-1][j+1]
                    #本行
                    if j-1>=0:
                        num+=1
                        count+=M[i][j-1]
                    if j+1<col:
                        num+=1
                        count+=M[i][j+1]
                    #下一行
                    if i+1<=row-1:
                        num+=1
                        count+=M[i+1][j]
                        if j-1>=0:
                            num+=1
                            count+=M[i+1][j-1]
                        if j+1<col:
                            num+=1
                            count+=M[i+1][j+1]
                    
                    copyM[i][j]=count//num
                            
            
            return copyM

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

我们是这样定义一个非递减数列的： 对于数组中所有的 `i` (1 <= i < n)，满足 `array[i] <= array[i + 1]`。

**示例 1:**

输入: [4,2,3]
    输出: True
    解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

**示例 2:**

输入: [4,2,1]
    输出: False
    解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

class Solution:
        def checkPossibility(self, nums: List[int]) -> bool:
            if len(nums)<=2:
                return True
            # 先让前两个有序,对于前两个数来说，最佳选择就是吧 a[0] 变小
            #因为要让整体变动次数变少，所以尽可能让前面的数越小越好
            count=0
            if nums[0]>nums[1]:
                nums[0]=nums[1]
                count+=1
            #如果出现 a[i] > a[i+1]   改变一个数 就面临两种选择，目的使改变次数最少
            #1. 把a[i]变小 2. 把a[i+1] 变大
            #1,6,2->使当前6变为1即可，如果使2变为6虽然可以，但可能导致2之后的数字仍小于6
            #1,6,0->使当前0变为6即可，保证之前的数据已经按照从小到大排好了序
            for i in range(1,len(nums)-1):
                if nums[i]>nums[i+1]:
                    count+=1
                    if count>=2:
                        return False
                    if nums[i+1]<nums[i-1]:
                        nums[i+1]=nums[i]
                    else:
                        nums[i]=nums[i-1]
            
            return True

超时：

class Solution(object):
        def checkPossibility(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            if sorted(nums)==nums:
                return True
            for i in range(len(nums)):
                nums_copy=nums[:]
                nums_copy.pop(i)
                if sorted(nums_copy)==nums_copy:
                    return True
            return False

### 3.给定一个未经排序的整数数组，找到最长且**连续**的的递增序列。 ###

**示例 1:**

输入: [1,3,5,4,7]
    输出: 3
    解释: 最长连续递增序列是 [1,3,5], 长度为3。
    尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。

**示例 2:**

输入: [2,2,2,2,2]
    输出: 1
    解释: 最长连续递增序列是 [2], 长度为1。

class Solution:
        def findLengthOfLCIS(self, nums: List[int]) -> int:
            if nums==[]:
                return 0
            count=1
            maxcount=1
            for i in range(1,len(nums)):
                if nums[i]>nums[i-1]:
                    count+=1
                else:
                    maxcount=max(count,maxcount)
                    count=1
            maxcount=max(count,maxcount)
            return maxcount

方法二：

class Solution(object):
        def findLengthOfLCIS(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if nums==[]:
                return 0
            start=0
            end=0
            maxsub=1
            for i in range(1,len(nums)):
                if nums[i]>nums[i-1]:
                    end+=1
                else:
                    if end+1-start>maxsub:
                        maxsub=end+1-start
                    start=i
                    end=i
                if i==len(nums)-1 and end+1-start>maxsub:
                        maxsub=end+1-start
                    
            return maxsub

### 4.给定一个非空字符串 `s`，**最多**删除一个字符。判断是否能成为回文字符串。 ###

**示例 1:**

输入: "aba"
    输出: True

**示例 2:**

输入: "abca"
    输出: True
    解释: 你可以删除c字符。

class Solution(object):
        def validPalindrome(self, s):
            """
            :type s: str
            :rtype: bool
            """
            i, j = 0, len(s)-1
            while i < j and s[i]==s[j]:
                i+=1
                j-=1
            if i==j:
                return True
            else:
                return s[i+1:j+1]==s[i+1:j+1][::-1] or s[i:j]==s[i:j][::-1]

class Solution:
        def validPalindrome(self, s: str) -> bool:
            n = len(s)
            i = 0
            while i <= n//2-1 and s[i] == s[-(i+1)]:
                i += 1
            tmp = s[i:n-i]
            return tmp[1:] == tmp[1:][::-1] or tmp[:-1] == tmp[:-1][::-1]

### 5.给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数，使得字符串B成为叠加后的字符串A的子串，如果不存在则返回 -1。 ###

举个例子，A = "abcd"，B = "cdabcdab"。

答案为 3， 因为 A 重复叠加三遍后为 “abcdabcdabcd”，此时 B 是其子串；A 重复叠加两遍后为"abcdabcd"，B 并不是其子串。

class Solution:
        def repeatedStringMatch(self, A: str, B: str) -> int:
            if len(set(A))<len(set(B)):
                return -1
            for i in range(max(len(B)//len(A),1),len(B)//len(A)+2+1):
                if B in A*i:
                    return i
            return -1

### 6.给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。 ###

**示例 1:**

输入: 5
    输出: True
    解释:
    5的二进制数是: 101

**示例 3:**

输入: 11
    输出: False
    解释:
    11的二进制数是: 1011

**示例 4:**

输入: 10
    输出: True
    解释:
    10的二进制数是: 1010

class Solution(object):
        def hasAlternatingBits(self, n):
            """
            :type n: int
            :rtype: bool
            """        
            '''* 如果n是交替的101，对于它右移一位后得到的m,10，
            * 存在n跟m在二进制下必然是0和1对应的（对位）。异或运算必定都是1；
            * 举个栗子：5=101 5>>1=10,5^(5>>1)=111 (这是伪代码)
            * 其他情况都不会满足这个特征。所以temp=n^(n>>1)必定满足temp=2^N-1;111
            * 而temp+1后是N+1位二进制数2^N。1000
            * 所以temp&(temp+1)==0；
            * 如果满足这个等式就是就是交替位二进制数
            '''
            temp=n^(n>>1)
            return temp&(temp+1)==0

class Solution:
        def hasAlternatingBits(self, n: int) -> bool:
            num2=list(map(int,bin(n)[2:]))
            for i in range(1,len(num2)):
                if num2[i]^num2[i-1]==0:
                    return False
            return True

### 7.给定一个非空且只包含非负数的整数数组 `nums`, 数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是找到与 `nums` 拥有相同大小的度的最短连续子数组，返回其长度。 ###

**示例 1:**

输入: [1, 2, 2, 3, 1]
    输出: 2
    解释: 
    输入数组的度是2，因为元素1和2的出现频数最大，均为2.
    连续子数组里面拥有相同度的有如下所示:
    [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
    最短连续子数组[2, 2]的长度为2，所以返回2.

**示例 2:**

输入: [1,2,2,3,1,4,2]
    输出: 6

class Solution(object):
        def findShortestSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            a={}
            for i in range(len(nums)):
                if nums[i] not in a:
                    a[nums[i]]=[i]
                else:
                    a[nums[i]].append(i)
            du=max([len(a[i]) for i in a])
            length=len(nums)
            for i in a:
                if len(a[i])==du:
                    length=min(length,a[i][-1]-a[i][0]+1)
            return length

### 8.给定一个 `n` 个元素有序的（升序）整型数组 `nums` 和一个目标值 `target` ，写一个函数搜索 `nums` 中的 `target`，如果目标值存在返回下标，否则返回 `-1`。 ###

**示例 1:**

输入: nums = [-1,0,3,5,9,12], target = 9输出: 4
    解释: 9 出现在nums中并且下标为 4

class Solution:
        def search(self, nums: List[int], target: int) -> int:
            low=0
            high=len(nums)-1
            while low<=high:#while循环要包含等于的情况
                mid=low+(high-low)//2
                if target==nums[mid]:
                    return mid
                elif target>nums[mid]:
                    low=mid+1
                else:
                    high=mid-1
            return -1

### 9.有两种特殊字符。第一种字符可以用一比特`0`来表示。第二种字符可以用两比特(`10` 或 `11`)来表示。 ###

现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。

**示例 1:**

输入: 
    bits = [1, 0, 0]
    输出: True
    解释: 
    唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。

**示例 2:**

输入: 
    bits = [1, 1, 1, 0]
    输出: False
    解释: 
    唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。

class Solution:
        def isOneBitCharacter(self, bits: List[int]) -> bool:
            #遇到 1 索引+2，遇到 0 索引+1，最后比较索引与列表长度即可
            i=0
            while i<=len(bits)-2:
                if bits[i]==1:
                    i+=2
                else:
                    i+=1
            if i>=len(bits):
                return False
            return True