编程能力进阶_1

你的名字 2022-02-19 05:11 340阅读 0赞

**目录**

1.给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

2.给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

3.给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

4.将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

5.给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

6.给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

7.给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

8.给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

9.给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

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

### 1.给出两个 **非空** 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 **逆序** 的方式存储的，并且它们的每个节点只能存储 **一位** 数字。 ###

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

**示例：**

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 0 -> 8
    原因：342 + 465 = 807

class Solution(object):
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            str1=''
            str2=''
            while l1:
                str1+=str(l1.val)
                l1=l1.next
            while l2:
                str2+=str(l2.val)
                l2=l2.next
            result=str(int(str1[::-1])+int(str2[::-1]))[::-1]
            for i in range(len(result)):
                if i==0:
                    retr=ListNode(int(result[i]))
                    r=retr
                else:
                    r.next=ListNode(int(result[i]))
                    r=r.next
            return retr

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            re = ListNode(0)
            r=re
            carry=0
            while(l1 or l2):
                x= l1.val if l1 else 0
                y= l2.val if l2 else 0
                s=carry+x+y
                carry=s//10
                r.next=ListNode(s%10)
                r=r.next
                if(l1!=None):l1=l1.next
                if(l2!=None):l2=l2.next
            if(carry>0):
                r.next=ListNode(1)
            return re.next

### 2.给定一个字符串，请你找出其中不含有重复字符的 **最长子串** 的长度。 ###

**示例 1:**

输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

**示例 2:**

输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            maxlen=0
            start=0
            count={}
            for i in range(len(s)):
                if s[i] in count:
                    #start不能选取发生重复数字，首个重复数字之前的数
                    #start选取最靠前且之后到i为止没有重复数字出现
                    start=max(count[s[i]],start)
                
                count[s[i]]=i+1
                maxlen=max(maxlen,i-start+1)
            return maxlen

### 3.给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。 ###

**示例 1：**

输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。

**示例 2：**

输入: "cbbd"
    输出: "bb"

class Solution:
        def longestPalindrome(self, s: str) -> str:
            res=''
            for i in range(len(s)):
                #第一种情况，中心为一个单独的数
                k=i
                m=i
                while k>=0 and m<=len(s)-1 and s[k]==s[m]:
                    k-=1
                    m+=1
                if len(res)<m-k+1-2:#因为跳出循环时k与m都已不符合条件
                    res=s[k+1:m]
                #第二种情况，中心为两个相同的数
                k=i
                m=i+1
                while k>=0 and m<=len(s)-1 and s[k]==s[m]:
                    k-=1
                    m+=1
                if len(res)<m-k+1-2:#因为跳出循环时k与m都已不符合条件
                    res=s[k+1:m]  
                
            return res

### 4.将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。 ###

比如输入字符串为 `"LEETCODEISHIRING"` 行数为 3 时，排列如下：

L   C   I   R
    E T O E S I I G
    E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：`"LCIRETOESIIGEDHN"`。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

**示例 1:**

输入: s = "LEETCODEISHIRING", numRows = 3
    输出: "LCIRETOESIIGEDHN"

**示例 2:**

输入: s = "LEETCODEISHIRING", numRows = 4
    输出: "LDREOEIIECIHNTSG"
    解释:
    
    L     D     R
    E   O E   I I
    E C   I H   N
    T     S     G

class Solution:
        def convert(self, s: str, numRows: int) -> str:
            #分2个部分，竖线部分，排队存入out[i]中，斜线部分，从倒数第二个数倒数到第二个数，倒数排队进去。
            #两部分完成一个循环，直到字符串都录入
            out=['' for i in range(numRows)]
            t=0
            while t<len(s):
                for i in range(0,numRows):
                    out[i]+=s[t]
                    t+=1
                    if t==len(s):
                        break
                if t == len(s):
                    break
                for i in range(numRows-2,0,-1):
                    out[i]+=s[t]
                    t+=1
                    if t==len(s):
                        break
            res=''.join(out)
            return res

class Solution:
        def convert(self, s, numRows):
            """
            :type s: str
            :type numRows: int
            :rtype: str
            """
            #第一层 和 最后一层 每次更新 (nums - 1) * 2
            #中间层按照奇偶要么更新 （nums - 1 - i）* 2 要么更新 i*2
            end = ''
            n = len(s)
            # 针对只有一行时，其原序列即为新序列
            if numRows <= 1:
                return s
            # 依次遍历第i行
            for i in range(numRows):
                # 初始化每行第一个元素索引
                j = i
                while j < n:
                    # 处理特殊行数。第一行和最后一行中间没有数，元素索引关系为
                    # next = now + 2 * (numRows - 1)
                    if i == 0 or i == numRows - 1:
                        end += s[j]
                        j += 2 * (numRows - 1)
                    # 当行数不是第一行或最后一行时，中间会有一个数
                    else:
                        # 首先读取第一个数
                        end += s[j]
                        # 计算出中间数的索引值，关系为：
                        # next = now + (numRows - i - 1) * 2
                        j +=(numRows - i - 1) * 2
                        # 检测是否越界，若未越界，则添加到新字符串中
                        if j < n:
                            end += s[j]
                            # 计算中间数后的字符索引，关系为
                            # next = now + 2 * i
                            j += 2 * i
            return end

### 5.给定 *n* 个非负整数 *a*1，*a*2，...，*a*n，每个数代表坐标中的一个点 (*i*, *ai*) 。在坐标内画 *n* 条垂直线，垂直线 *i* 的两个端点分别为 (*i*, *ai*) 和 (*i*, 0)。找出其中的两条线，使得它们与 *x* 轴共同构成的容器可以容纳最多的水。 ###

**说明：**你不能倾斜容器，且 *n* 的值至少为 2。

![question_11.jpg][]

图中垂直线代表输入数组 \[1,8,6,2,5,4,8,3,7\]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

**示例:**

输入: [1,8,6,2,5,4,8,3,7]
    输出: 49

class Solution(object):
        def maxArea(self, height):
            """
            :type height: List[int]
            :rtype: int
            """
            left = 0
            right = len(height) - 1
            maxArea = 0
            while left < right:
                b = right - left
                if height[left] < height[right]:
                    h = height[left]
                    left += 1
                else:
                    h = height[right]
                    right -= 1
                area = b*h
                if maxArea < area:
                    maxArea = area
            return maxArea

### 6.给定一个包含 *n* 个整数的数组 `nums`，判断 `nums` 中是否存在三个元素 *a，b，c ，*使得 *a + b + c =* 0 ？找出所有满足条件且不重复的三元组。 ###

**注意：**答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
    
    满足要求的三元组集合为：
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            nums.sort()
            res =[]
            for i in range(len(nums)):
                if i == 0 or nums[i]!=nums[i-1]:
                    l = i+1
                    r = len(nums)-1
                    while l < r:
                        s = nums[i] + nums[l] +nums[r]
                        if s ==0:
                            res.append([nums[i],nums[l],nums[r]])
                            l +=1
                            r -=1
                            while l < r and nums[l] == nums[l-1]:
                                l += 1
                            while r > l and nums[r] == nums[r+1]:
                                r -= 1
                        elif s>0:
                            r -=1
                        else :
                            l +=1
            return res

### 7.给定一个包括 *n* 个整数的数组 `nums`和 一个目标值 `target`。找出 `nums`中的三个整数，使得它们的和与 `target` 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 ###

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
    
    与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

class Solution:
        def threeSumClosest(self, nums: List[int], target: int) -> int:
            nums.sort()
            res =float('inf')
            for i in range(len(nums)):
                if i == 0 or nums[i]!=nums[i-1]:
                    l = i+1
                    r = len(nums)-1
                    while l < r:
                        s = nums[i] + nums[l] +nums[r]
                        if s-target==0:
                            return s
                        elif s>target:
                            r-=1
                        elif s<target:
                            l+=1
                        if abs(s-target)<abs(res-target):
                            res=s
            return res

### 8.给定一个仅包含数字 `2-9` 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 ###

![200px-Telephone-keypad2.svg.png][]

**示例:**

输入："23"
    输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

class Solution:
        def letterCombinations(self, digits: str) -> List[str]:
            mapping = {'2':['a','b','c'], '3':['d','e','f'], 
                       '4':['g','h','i'], '5':['j','k','l'],
                       '6':['m','n','o'], '7':['p','q','r','s'],
                       '8':['t','u','v'], '9':['w','x','y','z']}
            curr=['']
            retr=[]
            for i in digits:
                retr=[x+y for x in curr for y in mapping[i]]
                curr=retr
            return retr

class Solution:
        def letterCombinations(self, digits):
            '''
            :type digits: str
            :rtype: List[str]
            '''
            mapping = {'2':['a','b','c'], '3':['d','e','f'], 
                       '4':['g','h','i'], '5':['j','k','l'],
                       '6':['m','n','o'], '7':['p','q','r','s'],
                       '8':['t','u','v'], '9':['w','x','y','z']}
            temp = ['']
            ans = []
            for d in digits:
                ans = []
                for char in temp:
                    for new_char in mapping[d]:
                        ans.append(char+new_char)
                temp = ans
            return ans

### 9.给定一个包含 *n* 个整数的数组 `nums` 和一个目标值 `target`，判断 `nums` 中是否存在四个元素 *a，**b，c* 和 *d* ，使得 *a* \+ *b* \+ *c* \+ *d* 的值与 `target` 相等？找出所有满足条件且不重复的四元组。 ###

**注意：**

答案中不可以包含重复的四元组。

**示例：**

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
    
    满足要求的四元组集合为：
    [
      [-1,  0, 0, 1],
      [-2, -1, 1, 2],
      [-2,  0, 0, 2]
    ]

class Solution:
        def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
            nums.sort()
            res = []
            
            for i in range(len(nums)):
                if i == 0 or nums[i]!=nums[i-1]:
                    for j in range(i+1, len(nums)):
                        if j == i+1 or nums[j]!=nums[j-1]:
                            l, r = j+1, len(nums)-1 
                            while l < r:
                                tmp = [nums[i], nums[j], nums[l], nums[r]]
                                s = sum(tmp)
                                if s == target:
                                    res.append(tmp)
                                    l += 1
                                    r -= 1
                                    while l < r and nums[l] == nums[l-1]:
                                        l += 1
                                    while r > l and nums[r] == nums[r+1]:
                                        r -= 1
                                elif s < target:
                                    l += 1
                                elif s > target:
                                    r -=1
                    
            return res

[question_11.jpg]: /images/20220219/c7fa9ab6e7f44ff492c01f2689693d37.png
[200px-Telephone-keypad2.svg.png]: /images/20220219/a300b453006d44ec83933ea254895fe0.png