每日归档： 2022年1月24日

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序排列

# @lc app=leetcode.cn id=83 lang=python3
#
# [83] 删除排序链表中的重复元素
#

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        head0=head
        end=head
        while end!=None:
            if end.next!=None and head.val==end.next.val:
                end=end.next
            elif end.next!=None and head.val!=end.next.val:
                head.next=end.next
                head=head.next
                end=head
            elif end.next==None and head.val==end.val:
                head.next=None
                end=end.next
            else:
                return head0

        return head0
# @lc code=end

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]

提示：

• 1 <= s.length <= 104
• s 由小写英文字母组成
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 由小写英文字母组成

挨个匹配：

# @lc app=leetcode.cn id=30 lang=python3
#
# [30] 串联所有单词的子串
#

# @lc code=start
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        import copy
        ls=len(s)
        lw=len(words)
        wordlen=len(words[0])
        dicts=dict()
        res=[]
        for i in range(lw):
            if words[i] in  dicts:
                dicts[words[i]]=dicts[words[i]]+1
            else:
                dicts[words[i]]=1
        for i in range(ls-wordlen*lw+1):
            new=copy.copy(dicts)
            rev=1
            for j in range(i,i+wordlen*lw,wordlen):
                if s[j:j+wordlen] in new and new[s[j:j+wordlen]]!=0:
                    new[s[j:j+wordlen]]-=1
                else:
                    rev=0
                    break
            if rev==1:
                res.append(i)
        return res




# @lc code=end

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

法 一：只交换值

# [25] K 个一组翻转链表
#
#法1 ：只交换值
# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        head1=head
        fhead= ListNode(0,head)
        head2=fhead
        end=0
        while head1!= None:
            nums=list()
            for i in range(k):
                head2=head2.next
                if head2==None:
                    end=1
                    break 
                #print(head2.val)   
                nums.append(head2.val)
            if end==0:
                for i in range(k):
                    head1.val=nums[k-1-i]
                    head1=head1.next
            else:
                for i in range(len(nums)):
                    head1.val=nums[i]
                    head1=head1.next
        return  fhead.next   
# @lc code=end

进阶：

• 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
• 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

法二：节点交换（不只是单纯改变值） 代做。。

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

代码：

# [24] 两两交换链表中的节点
#

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        # head0 = ListNode(0,head)
        if head==None or head.next==None:
            return head
        head0=head
        headr=head.next

        while head0!=None:
            head1=head0
            head2=head0.next
            head3=head2.next
            #print(head3.val)
            head2.next=head1
            if head3==None:    
                head1.next=None
                #print("is 1")
                return headr
            if head3.next==None:
                head1.next=head3
                #print("is 2")

                return headr
            else:
                head1.next=head3.next
                #print(head3.val)
                #print("is 0")

                head0=head3
                #print(head0.val)
        return headr

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

二分法求解：

# @lc app=leetcode.cn id=69 lang=python3
#
# [69] Sqrt(x)
#
#二分法
# @lc code=start
class Solution:
    def mySqrt( self,x: int) -> int:
        mid=x//2
        end=x
        start=0
        if x==1:
            return 1
        while end>start+1:
            l=mid**2            
            if  l==x:
                return mid
            if  l<x :
                start=mid
                mid = (mid+end)//2
                continue
            if  l>x:
                end=mid
                mid = (mid)//2
                continue
        return start

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

动态规划 or 递归

# @lc app=leetcode.cn id=70 lang=python3
#
# [70] 爬楼梯
#

# @lc code=start
class Solution:
    def climbStairs(self, n: int) -> int:
        dp=[0 for i in range(n)]
        
        for i in range(n):
            if i == 0:
                dp[0]=1
                continue
            if i == 1:
                dp[1]=2
                continue
            dp[i]=dp[i-1]+dp[i-2]
        return dp[n-1]

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

提示：

• 每个字符串仅由字符 '0' 或 '1' 组成。
• 1 <= a.length, b.length <= 10^4
• 字符串如果不是 "0" ，就都不含前导零。

代码：

# @lc app=leetcode.cn id=67 lang=python3
#
# [67] 二进制求和
#

# @lc code=start
from calendar import c


class Solution:
    def addBinary(self,a: str, b: str) -> str:
        def Binary(i,j,carry=0):
            i=int(i)
            j=int(j)
            carry=int(carry)
            carrys=(i+j+carry)//2
            n=(i+j+carry)%2
            return str(n),str(carrys)
        lena=len(a)
        lenb=len(b)
        rev=""
        if lena<lenb:
            c=a
            a=b
            b=c
        carry=0
        lens=max(lena,lenb)
        b="0"*abs(lena-lenb)+b
        for i in range(lens-1,-1,-1):
            #print(a[i],b[i],carry)
            n,carry=Binary(a[i],b[i],carry)
            rev=n+rev
        if carry=="1":
             rev=carry+rev
        return rev

有效数字（按顺序）可以分成以下几个部分：

1. 一个 小数 或者 整数
2. （可选）一个 'e' 或 'E' ，后面跟着一个 整数

小数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（'+' 或 '-'）
2. 下述格式之一：
   1. 至少一位数字，后面跟着一个点 '.'
   2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
   3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（'+' 或 '-'）
2. 至少一位数字

部分有效数字列举如下：

• ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下：

• ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。

解法1:(官方答案)

确定有限状态自动机

#
# @lc app=leetcode.cn id=65 lang=python3
#
# [65] 有效数字
#

# @lc code=start
from enum import Enum

class Solution:
    def isNumber(self, s: str) -> bool:
        State = Enum("State", [
            "STATE_INITIAL",
            "STATE_INT_SIGN",
            "STATE_INTEGER",
            "STATE_POINT",
            "STATE_POINT_WITHOUT_INT",
            "STATE_FRACTION",
            "STATE_EXP",
            "STATE_EXP_SIGN",
            "STATE_EXP_NUMBER",
            "STATE_END"
        ])
        Chartype = Enum("Chartype", [
            "CHAR_NUMBER",
            "CHAR_EXP",
            "CHAR_POINT",
            "CHAR_SIGN",
            "CHAR_ILLEGAL"
        ])

        def toChartype(ch: str) -> Chartype:
            if ch.isdigit():
                return Chartype.CHAR_NUMBER
            elif ch.lower() == "e":
                return Chartype.CHAR_EXP
            elif ch == ".":
                return Chartype.CHAR_POINT
            elif ch == "+" or ch == "-":
                return Chartype.CHAR_SIGN
            else:
                return Chartype.CHAR_ILLEGAL
        
        transfer = {
            State.STATE_INITIAL: {
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT,
                Chartype.CHAR_SIGN: State.STATE_INT_SIGN
            },
            State.STATE_INT_SIGN: {
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT
            },
            State.STATE_INTEGER: {
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_EXP: State.STATE_EXP,
                Chartype.CHAR_POINT: State.STATE_POINT
            },
            State.STATE_POINT: {
                Chartype.CHAR_NUMBER: State.STATE_FRACTION,
                Chartype.CHAR_EXP: State.STATE_EXP
            },
            State.STATE_POINT_WITHOUT_INT: {
                Chartype.CHAR_NUMBER: State.STATE_FRACTION
            },
            State.STATE_FRACTION: {
                Chartype.CHAR_NUMBER: State.STATE_FRACTION,
                Chartype.CHAR_EXP: State.STATE_EXP
            },
            State.STATE_EXP: {
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER,
                Chartype.CHAR_SIGN: State.STATE_EXP_SIGN
            },
            State.STATE_EXP_SIGN: {
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER
            },
            State.STATE_EXP_NUMBER: {
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER
            },
        }

        st = State.STATE_INITIAL
        for ch in s:
            typ = toChartype(ch)
            if typ not in transfer[st]:
                return False
            st = transfer[st][typ]
        
        return st in [State.STATE_INTEGER, State.STATE_POINT, State.STATE_FRACTION, State.STATE_EXP_NUMBER, State.STATE_END]
# @lc code=end

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

思路：动态规划

# @lc app=leetcode.cn id=64 lang=python3
#
# [64] 最小路径和
#
#动态规划 dp[i][j]时到i,j的最小路径和
# @lc code=start
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])
        dp=[[0]*col for i in range(row)]
        for i in range(row):
            for j in range(col):
                if i == 0 and j!=0:
                    dp[i][j]=dp[i][j-1]+grid[i][j]
                elif j == 0 and i!=0:
                    dp[i][j]=dp[i-1][j]+grid[i][j]
                elif i==0 and j==0:
                    dp[i][j]=grid[0][0]
                else :
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
        return dp[row-1][col-1]