LeetCode简单题目(#203 #204 # #205 #206 #217 #219)-6道（序列、数字）

今天药忘吃喽~ 2023-06-16 12:59 4阅读 0赞

> leetcode题库中共有350道简单题目。  
> 本文记录已解决的题目和代码。  
> 本文中的序号是leetcode题目中的真实序号。

### 文章目录 ###

*  203 移除链表元素
 *   *  描述
     *  代码
     *  大神代码-递归
 *  204 计数质数
 *   *  描述
     *  代码-厄拉多塞筛法
     *  大神代码
 *  205 同构字符串
 *   *  描述
     *  代码
 *  206 反转链表
 *   *  描述
     *  代码
     *  大神代码
     *  两种方法
 *  217 存在重复元素
 *   *  描述
     *  代码
 *  219 存在重复元素 II
 *   *  描述
     *  代码

# 203 移除链表元素 #

## 描述 ##

删除链表中等于给定值 val 的所有节点。  
示例:

输入: 1->2->6->3->4->5->6, val = 6  
输出: 1->2->3->4->5

## 代码 ##

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    # 参考网站
    # https://leetcode-cn.com/problems/remove-linked-list-elements/solution/dong-hua-yan-shi-203-yi-chu-lian-biao-yuan-su-by-u/
    class Solution:
        def removeElements(self, head: ListNode, val: int) -> ListNode:
            temp_node = ListNode(-1)
            temp_node.next = head
            p = temp_node
            
            while temp_node.next:
                if temp_node.next.val == val:
                    temp_node.next = temp_node.next.next
                else:
                    temp_node = temp_node.next
            
            return p.next

## 大神代码-递归 ##

> 作者：powcai  
> 链接：https://leetcode-cn.com/problems/remove-linked-list-elements/solution/di-gui-he-die-dai-by-powcai-6/

class Solution:
        def removeElements(self, head: ListNode, val: int) -> ListNode:  
            if not head: return 
            head.next = self.removeElements(head.next, val)
            return head.next if head.val == val else head

# 204 计数质数 #

## 描述 ##

统计所有小于非负整数 n 的质数的数量。  
示例:

输入: 10  
输出: 4  
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

## 代码-厄拉多塞筛法 ##

class Solution:
        def countPrimes(self, n: int) -> int:
            count = 0
            isPrime_list = [True]*n
            i = 2
            while i*i < n:
                if isPrime_list[i]:
                    for j in range(i*i,n,i):
                        isPrime_list[j] = False
                i += 1
            
            for i in range(2,n):
                if isPrime_list[i]:
                    count += 1
            return count

## 大神代码 ##

> java版  
> https://leetcode-cn.com/problems/count-primes/solution/ru-he-gao-xiao-pan-ding-shai-xuan-su-shu-by-labula/  
> python版  
> https://leetcode-cn.com/problems/count-primes/solution/qiu-zhi-shu-chao-guo-90-by-powcai/

# 205 同构字符串 #

## 描述 ##

给定两个字符串 s 和 t，判断它们是否是同构的。  
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。  
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。  
示例 1:

输入: s = “egg”, t = “add”  
输出: true  
示例 2:  
输入: s = “foo”, t = “bar”  
输出: false  
示例 3:  
输入: s = “paper”, t = “title”  
输出: true  
说明:  
你可以假设 s 和 t 具有相同的长度

## 代码 ##

> 同构表示两个字符串每个位置上的字符首次出现的索引相同

class Solution:
        def isIsomorphic(self, s: str, t: str) -> bool:
    #         s_list = self.strNumber(s)
    #         t_list = self.strNumber(t)
            
    #         if s_list == t_list:
    #             return True
    #         else:
    #             return False
            
            # https://leetcode-cn.com/problems/isomorphic-strings/solution/1-xing-python-by-knifezhu-5/
            # return list(map(s.index,s)) == list(map(t.index,t))   
            return [s.index(i) for i in s] == [t.index(i) for i in t]   #更快
        
        def strNumber(self,s):
            p = 1
            s_list = [1]
            for i in range(1,len(s)):
                if s[i] in s[:i]:
                    s_list.append(s_list[s[:i].index(s[i])])
                else:
                    s_list.append(1+p)
                    p += 1
            return s_list

# 206 反转链表 #

## 描述 ##

反转一个单链表。  
示例:

输入: 1->2->3->4->5->NULL  
输出: 5->4->3->2->1->NULL  
进阶:  
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

## 代码 ##

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def reverseList(self, head: ListNode) -> ListNode:
            if not head:
                return head
            p = ListNode(head.val)
            p.next = None
            while head.next:
                node = ListNode(head.next.val)
                node.next = p
                p = node
                head = head.next
            return p

## 大神代码 ##

> https://leetcode-cn.com/u/gaussic/

class Solution:
        def reverseList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            p, rev = head, None
            while p:
                rev, rev.next, p = p, rev, p.next
            return rev

## 两种方法 ##

> https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/

# 递归解法
    class Solution(object):
        def reverseList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            # 递归终止条件是当前为空，或者下一个节点为空
            if(head==None or head.next==None):
                return head
            # 这里的cur就是最后一个节点
            cur = self.reverseList(head.next)
            # 这里请配合动画演示理解
            # 如果链表是 1->2->3->4->5，那么此时的cur就是5
            # 而head是4，head的下一个是5，下下一个是空
            # 所以head.next.next 就是5->4
            head.next.next = head
            # 防止链表循环，需要将head.next设置为空
            head.next = None
            # 每层递归函数都返回cur，也就是最后一个节点
            return cur

# 217 存在重复元素 #

## 描述 ##

给定一个整数数组，判断是否存在重复元素。  
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。  
示例 1:

输入: \[1,2,3,1\]  
输出: true  
示例 2:  
输入: \[1,2,3,4\]  
输出: false  
示例 3:  
输入: \[1,1,1,3,3,4,3,2,4,2\]  
输出: true

## 代码 ##

class Solution:
        def containsDuplicate(self, nums: List[int]) -> bool:
            if not nums:
                return False
            count_dic = {
        }
            for i in nums:
                if i not in count_dic:
                    count_dic[i] = 0
                else:
                    return True
            return False

# 219 存在重复元素 II #

## 描述 ##

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，  
使得 nums \[i\] = nums \[j\]，并且 i 和 j 的差的绝对值最大为 k。(题目描述不准确，应该是最大不超过k)  
示例 1:  
输入: nums = \[1,2,3,1\], k = 3  
输出: true  
示例 2:  
输入: nums = \[1,0,1,1\], k = 1  
输出: true  
示例 3:  
输入: nums = \[1,2,3,1,2,3\], k = 2  
输出: false

## 代码 ##

class Solution:
        def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: 
            nums_dic = {
        }
            for i in range(len(nums)):
                if nums[i] not in nums_dic:
                    nums_dic[nums[i]] = i
                elif (i-nums_dic[nums[i]]) <= k :
                    return True
                else:
                    nums_dic[nums[i]] = i
            return False