编程能力提升_9

比眉伴天荒 2022-02-28 12:05 83阅读 0赞

**目录**

1.请判断一个链表是否为回文链表。

2.给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。

3.给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

4.编写一个程序判断给定的数是否为丑数。

5.给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

6.假设你有 n 个版本 \[1, 2, ..., n\]，你想找出导致之后所有版本出错的第一个错误的版本。

7.给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

8.给定一种 pattern(模式) 和一个字符串 str ，判断 str 是否遵循相同的模式。

9.给定一个整数，写一个函数来判断它是否是 3 的幂次方。

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

### 1.请判断一个链表是否为回文链表。 ###

**示例 1:**

输入: 1->2
    输出: false

**示例 2:**

输入: 1->2->2->1
    输出: true

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None        
    class Solution:
        def isPalindrome(self, head: ListNode) -> bool:
            list1 = []
            while head:
                list1.append(head.val)
                head = head.next
            return list1 == list1[::-1]

### 2.给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的一个字母异位词。 ###

**示例 1:**

输入: s = "anagram", t = "nagaram"
    输出: true

**示例 2:**

输入: s = "rat", t = "car"
    输出: false

class Solution:
        def isAnagram(self, s: str, t: str) -> bool:
            dic1={}
            dic2={}        
            for item in s:
                dic1[item] = dic1.get(item,0) + 1
            for item in t:    
                dic2[item] = dic2.get(item,0) + 1
            return dic1 == dic2 
            #return Counter(s) == Counter(t)

class Solution(object):
        def isAnagram(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: bool
            """
            s=[i for i in s]
            t=[i for i in t]
            return sorted(s)==sorted(t)

### 3.给定一个非负整数 `num`，反复将各个位上的数字相加，直到结果为一位数。 ###

**示例:**

输入: 38
    输出: 2 
    解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。

class Solution(object):
        def addDigits(self, num):
            """
            :type num: int
            :rtype: int
            """
            while num>=10:
                ls=[int(i) for i in str(num)]
                num=sum(ls)
            return num

方法二：

数学法：

class Solution:
        def addDigits(self, num: int) -> int:
            if num == 0:
                return 0
            return num % 9 if num % 9 != 0 else 9

### 4.编写一个程序判断给定的数是否为丑数。 ###

丑数就是只包含质因数 `2, 3, 5` 的**正整数**。

**示例 1:**

输入: 6
    输出: true
    解释: 6 = 2 × 3

**示例 2:**

输入: 14
    输出: false 
    解释: 14 不是丑数，因为它包含了另外一个质因数 7。

方法一：递归

class Solution:
        def isUgly(self, num: int) -> bool:
                if num <= 0:
                    return False
                if num%2 == 0:
                    return self.isUgly(num//2)
        
                if num%3 == 0:
                    return self.isUgly(num//3)
        
                if num%5 == 0:
                    return self.isUgly(num//5)
                if num == 1:
                    return True
                else: 
                    return False

方法二：

class Solution(object):
        def isUgly(self, num):
            """
            :type num: int
            :rtype: bool
            """
            if not num:
                return False
            while not num % 2:
                num //= 2
            while not num % 3:
                num //= 3
            while not num % 5:
                num //= 5
            
            if num == 1:
                return True
            return False

### 5.给定一个包含 `0, 1, 2, ..., n` 中 *n* 个数的序列，找出 0 .. *n* 中没有出现在序列中的那个数。 ###

**示例 1:**

输入: [3,0,1]
    输出: 2

**示例 2:**

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

class Solution:
        def missingNumber(self, nums: List[int]) -> int:
            n=0
            for i in range(len(nums)):
                n=n^i^nums[i]
            n=n^len(nums)
            return n

### 6.假设你有 `n` 个版本 `[1, 2, ..., n]`，你想找出导致之后所有版本出错的第一个错误的版本。 ###

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。你可以通过调用 `bool isBadVersion(version)` 接口来判断版本号 `version` 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

**示例:**

给定 n = 5，并且 version = 4 是第一个错误的版本。
    
    调用 isBadVersion(3) -> false
    调用 isBadVersion(5) -> true
    调用 isBadVersion(4) -> true
    
    所以，4 是第一个错误的版本。

class Solution:
        def firstBadVersion(self, n):
            """
            :type n: int
            :rtype: int
            """
            low = 1
            high = n
            while low<high:
                mid = low+(high-low) //2
                if isBadVersion(mid):
                    high = mid
                else:
                    low = mid + 1
            
            return low

### 7.给定一个数组 `nums`，编写一个函数将所有 `0` 移动到数组的末尾，同时保持非零元素的相对顺序。 ###

**示例:**

输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]

**说明**:

1.  必须在原数组上操作，不能拷贝额外的数组。
2.  尽量减少操作次数。

class Solution(object):
        def moveZeroes(self, nums):
            """
            :type nums: List[int]
            :rtype: None Do not return anything, modify nums in-place instead.
            """
            n_len = len(nums)
            j = 0
            for i in range(n_len):
                if nums[i] != 0:
                    nums[j] = nums[i]
                    j+=1
            nums[j:len(nums)] = [0 for i in range(n_len-j)]

方法二：

class Solution:
        def moveZeroes(self, nums: List[int]) -> None:
            """
            Do not return anything, modify nums in-place instead.
            """
            i=0
            #length为其索引
            length=len(nums)-1
            while i<=length:
                if nums[i]==0:
                    nums.remove(0)
                    nums.append(0)
                    length-=1
                else:
                    i+=1

### 8.给定一种 `pattern(模式)` 和一个字符串 `str` ，判断 `str` 是否遵循相同的模式。 ###

这里的**遵循**指完全匹配，例如， `pattern` 里的每个字母和字符串 `str`中的每个非空单词之间存在着双向连接的对应模式。

**示例1:**

输入: pattern = "abba", str = "dog cat cat dog"
    输出: true

**示例 2:**

输入:pattern = "abba", str = "dog cat cat fish"
    输出: false

**示例 3:**

输入: pattern = "aaaa", str = "dog cat cat dog"
    输出: false

class Solution:
        def wordPattern(self, pattern: str, str: str) -> bool:
            pattern=[x for x in pattern]
            strs=str.split()
            dict1={}
            dict2={}
            if len(pattern)!=len(strs):
                return False
            for i in range(len(pattern)):
                if pattern[i] not in dict1:
                    dict1[pattern[i]]=strs[i]
                else:
                    if dict1[pattern[i]]!=strs[i]:
                        return False 
                    
            for i in range(len(strs)):
                if strs[i] not in dict2:
                    dict2[strs[i]]=pattern[i]
                else:
                    if dict2[strs[i]]!=pattern[i]:
                        return False        
            return True

方法二：

class Solution(object):
        def wordPattern(self, pattern, str):
            """
            :type pattern: str
            :type str: str
            :rtype: bool
            """
            pattern=[x for x in pattern]
            strs=str.split()
            if len(pattern)!=len(strs):
                return False
            if len(set(pattern))==len(set(strs))==len(set(zip(pattern,strs))):
                return True
            else:
                return False

### 9.给定一个整数，写一个函数来判断它是否是 3 的幂次方。 ###

**示例 1:**

输入: 27
    输出: true

**示例 2:**

输入: 0
    输出: false

class Solution(object):
        def isPowerOfThree(self, n):
            """
            :type n: int
            :rtype: bool
            """
            while n>1:
                if n%3!=0:
                    break
                n/=3
            return n==1