编程能力提升_13

蔚落 2022-02-24 18:44 364阅读 0赞

**目录**

1.现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：

2.给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

3.给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。

4.给定一个整数，将其转化为7进制，并以字符串形式输出。

5.对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。

6.斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

7.给定一个单词，你需要判断单词的大写使用是否正确。

8.给定两个字符串，你需要从这两个字符串中找出最长的特殊序列。最长特殊序列定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。

9.给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.

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

### 1.现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求： ###

1. 你设计的矩形页面必须等于给定的目标面积。
    
    2. 宽度 W 不应大于长度 L，换言之，要求 L >= W 。
    
    3. 长度 L 和宽度 W 之间的差距应当尽可能小。

你需要按顺序输出你设计的页面的长度 L 和宽度 W。

**示例：**

输入: 4
    输出: [2, 2]
    解释: 目标面积是 4， 所有可能的构造方案有 [1,4], [2,2], [4,1]。
    但是根据要求2，[1,4] 不符合要求; 根据要求3，[2,2] 比 [4,1] 更能符合要求. 所以输出长度 L 为 2， 宽度 W 为 2。

class Solution(object):
        def constructRectangle(self, area):
            """
            :type area: int
            :rtype: List[int]
            """
            w=int(area**0.5)
            for i in range(w,0,-1):
                if i*int(area/i)==area:
                    return [area//i,i]

### 2.给定两个**没有重复元素**的数组 `nums1` 和 `nums2` ，其中`nums1` 是 `nums2` 的子集。找到 `nums1` 中每个元素在 `nums2` 中的下一个比其大的值。 ###

`nums1` 中数字 **x** 的下一个更大元素是指 **x** 在 `nums2` 中对应位置的右边的第一个比 **x** 大的元素。如果不存在，对应位置输出-1。

**示例 1:**

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
    输出: [-1,3,-1]
    解释:
        对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
        对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
        对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。

**示例 2:**

输入: nums1 = [2,4], nums2 = [1,2,3,4].
    输出: [3,-1]
    解释:
        对于num1中的数字2，第二个数组中的下一个较大数字是3。
        对于num1中的数字4，第二个数组中没有下一个更大的数字，因此输出 -1。

**注意:**

1.  `nums1`和`nums2`中所有元素是唯一的。
2.  `nums1`和`nums2` 的数组大小都不超过1000。

class Solution(object):
        def nextGreaterElement(self, nums1, nums2):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: List[int]
            """
            retr=[]
            for i in nums1:
                index=nums2.index(i)
                for j in range(index,len(nums2)):
                    if nums2[j]>i:
                        retr.append(nums2[j])
                        break
                    if j==len(nums2)-1:
                        retr.append(-1)
            return retr

在当前值的右边，找到数值上紧挨着当前值的值

class Solution(object):
        def nextGreaterElement(self, nums1, nums2):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: List[int]
            """
            temp=float('inf')
            retr=[]
            for i in nums1:
                index=nums2.index(i)
                if index==len(nums2)-1:
                    retr.append(-1)
                else:
                    for j in range(index+1,len(nums2)):
                        if i<nums2[j]<temp:
                            temp=nums2[j]
                    if temp==float('inf'):
                        retr.append(-1)
                    else:
                        retr.append(temp)                        
            return retr

### 3.给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。 ###

**示例：**

输入: ["Hello", "Alaska", "Dad", "Peace"]
    输出: ["Alaska", "Dad"]

**注意：**

1.  你可以重复使用键盘上同一字符。
2.  你可以假设输入的字符串将只包含字母。

class Solution(object):
        def findWords(self, words):
            """
            :type words: List[str]
            :rtype: List[str]
            """
            set1 = set('qwertyuiop')
            set2 = set('asdfghjkl')
            set3 = set('zxcvbnm')
            res = []
            for i in words:
                x = i.lower()
                setx = set(x)
                if setx<=set1 or setx<=set2 or setx<=set3:
                    res.append(i)
            return res

### 4.给定一个整数，将其转化为7进制，并以字符串形式输出。 ###

**示例 1:**

输入: 100
    输出: "202"

**示例 2:**

输入: -7
    输出: "-10"

class Solution(object):
        def convertToBase7(self, num):
            """
            :type num: int
            :rtype: str
            """
            num_7=''
            if num<0:
                retr='-'
                num=abs(num)
            elif num>0:
                retr=''
            elif num==0:
                return '0'        
            while num!=0:
                num_7+=str(num%7)
                num=num//7
            num_7=num_7[::-1]
            return retr+num_7

### 5.对于一个 **正整数**，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。 ###

给定一个 **正整数** `n`， 如果他是完美数，返回 `True`，否则返回 `False`

**示例：**

输入: 28
    输出: True
    解释: 28 = 1 + 2 + 4 + 7 + 14

class Solution(object):
        def checkPerfectNumber(self, num):
            """
            :type num: int
            :rtype: bool
            """
            retr=1
            if num<=0:
                return False
            for i in range(2,int(num**0.5)+1):
                if (num//i)*i==num:
                    retr=retr+i+num//i
            if (int(num**0.5))**2==num:
                retr-=num**0.5
            return retr==num

### 6.**斐波那契数**，通常用 `F(n)` 表示，形成的序列称为**斐波那契数列**。该数列由 `0` 和 `1` 开始，后面的每一项数字都是前面两项数字的和。也就是： ###

F(0) = 0,   F(1) = 1
    F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 `N`，计算 `F(N)`。

class Solution(object):
        def fib(self, N):
            """
            :type N: int
            :rtype: int
            """
            a,b=0,1
            for i in range(N):
                a,b=b,a+b
            return a

### 7.给定一个单词，你需要判断单词的大写使用是否正确。 ###

我们定义，在以下情况时，单词的大写用法是正确的：

1.  全部字母都是大写，比如"USA"。
2.  单词中所有字母都不是大写，比如"leetcode"。
3.  如果单词不只含有一个字母，只有首字母大写， 比如 "Google"。

否则，我们定义这个单词没有正确使用大写字母。

**示例 1:**

输入: "USA"
    输出: True

**示例 2:**

输入: "FlaG"
    输出: False

class Solution(object):
        def detectCapitalUse(self, word):
            """
            :type word: str
            :rtype: bool
            """
            count=0
            for i in word:
                if i==i.upper():
                    count+=1
            if count==0 or count==len(word):
                return True
            elif count==1 and word[0].upper()==word[0]:
                return True
            return False

class Solution:
        def detectCapitalUse(self, word: str) -> bool:
            return word.upper()==word or word.lower()==word or word.title()==word

### 8.给定两个字符串，你需要从这两个字符串中找出最长的特殊序列。最长特殊序列定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。 ###

**子序列**可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。

输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。

**示例 :**

输入: "aba", "cdc"
    输出: 3
    解析: 最长特殊序列可为 "aba" (或 "cdc")

class Solution:
        def findLUSlength(self, a: str, b: str) -> int:
            if a == b :
                return -1
            return max(len(a),len(b))

### 9.给定一个整数数组和一个整数 **k**, 你需要在数组里找到**不同的** k-diff 数对。这里将 **k-diff** 数对定义为一个整数对 (i, j), 其中 **i** 和 **j** 都是数组中的数字，且两数之差的绝对值是 **k**. ###

**示例 1:**

输入: [3, 1, 4, 1, 5], k = 2
    输出: 2
    解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
    尽管数组中有两个1，但我们只应返回不同的数对的数量。

**示例 2:**

输入:[1, 2, 3, 4, 5], k = 1
    输出: 4
    解释: 数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。

**示例 3:**

输入: [1, 3, 1, 5, 4], k = 0
    输出: 1
    解释: 数组中只有一个 0-diff 数对，(1, 1)。

**注意:**

1.  数对 (i, j) 和数对 (j, i) 被算作同一数对。

class Solution:
        def findPairs(self, nums: List[int], k: int) -> int:
            nums.sort()
            count=[]
            for i in range(len(nums)-1):
                for j in range(i+1,len(nums)):
                    if abs(nums[i]-nums[j])==k:
                        count.append((min(nums[i],nums[j]),max(nums[i],nums[j]))) 
                        break
                    #排序之后，如果nums[j]已经比nums[i]大，那么继续增大j只会使结果继续增大
                    if abs(nums[i]-nums[j])>k:
                        break                    
            return len(set(count))