力扣每日一题

写在前面

因为疫情原因，博主早早就回家了，期末考试也延迟到下学期，实在是没事啥事情做了(无聊.jpg
然后目前在学习Python和C++，本文作为本蒟蒻的学习笔记，大佬勿喷(害怕.jpg

2023年1月23日

• 2303. 计算应缴税款总额

解题思路

暴力

class Solution:
    def calculateTax(self, brackets: List[List[int]], income: int) -> float:
        m = 0
        j = [0, 0]
        for i in brackets:
            if income >= i[0]:
                m += (i[0] - j[0]) * (i[1] / 100)
                j = i
            else:
                m += (income - j[0]) * (i[1] / 100)
                break
        return m

2023年1月10日

• 753. 破解保险箱

解题思路

欧拉回路不会，现抄

class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        def dfs(u):
            for x in range(k):
                e = u * 10 + x
                if e not in vis:
                    vis.add(e)
                    v = e % mod
                    dfs(v)
                    ans.append(str(x))

        mod = 10 ** (n - 1)
        vis = set()
        ans = []
        dfs(0)
        ans.append("0" * (n - 1))
        return "".join(ans)

2023年1月8日

• 2185. 统计包含给定前缀的字符串

解题思路

暴力遍历即可

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        ans=0
        f=0
        for word in words:
            f=0
            if len(word)>=len(pref):
                for i in range(len(pref)):
                    if word[i]!=pref[i]:
                        f=1
                if f!=1:
                    ans+=1
        return ans

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        return sum(w.startswith(pref) for w in words)

2023年1月7日

• 1658. 将 x 减到 0 的最小操作数

解题思路

前缀和，哈希表

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        x = sum(nums) - x
        vis = {0: -1}
        ans = inf
        s, n = 0, len(nums)
        for i, v in enumerate(nums):
            s += v
            if s not in vis:
                vis[s] = i
            if s - x in vis:
                j = vis[s - x]
                ans = min(ans, n - (i - j))
        return -1 if ans == inf else ans

2022年12月28日

第一题

• 1750. 删除字符串两端相同字符后的最短长度

解题思路

双指针循环遍历

class Solution:
    def minimumLength(self, s: str) -> int:
        i, j = 0, len(s) - 1
        while i < j and s[i] == s[j]:
            while i + 1 < j and s[i] == s[i + 1]:
                i += 1
            while i < j - 1 and s[j - 1] == s[j]:
                j -= 1
            i, j = i + 1, j - 1
        return max(0, j - i + 1)

第二题

• 2. 两数相加

解题思路

遍历链表相加即可

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        head = tree = ListNode()
        val = temp = 0
        while temp or l1 or l2:
            val = temp
            if l1:
                val = l1.val + val
                l1 = l1.next
            if l2:
                val = l2.val + val
                l2 = l2.next
            temp = val // 10
            val = val % 10
            tree.next = ListNode(val)
            tree = tree.next
        return head.next

第三题

• 2515. 到目标字符串的最短距离

解题思路

遍历列表，遇到target直接比较谁小即可，维护m值

class Solution:
    def closetTarget(self, words: List[str], target: str, startIndex: int) -> int:
        m = inf
        l = len(words)
        for i, value in enumerate(words):
            if target == value:
                m = min(abs(i - startIndex), m)
                if startIndex > i:
                    m = min(l - startIndex + i, m)
                if startIndex < i:
                    m = min(l - i + startIndex, m)
        return -1 if m == inf else m

2022年12月27日

小阳人

2022年12月26日

小阳人

2022年12月25日

今天状态还可以，写一写

• 1739. 放置盒子

解题思路

找规律，暴力循环即可

class Solution:
    def minimumBoxes(self, n: int) -> int:
        m, a, ans = 1, 1, 1
        while m < n:
            a = a + 1
            ans += a
            m += a * (a + 1) / 2
        while m > n:
            ans = ans - 1
            m -= a
            a = a - 1
        if m < n:
            ans = ans + 1
        return ans

2022年12月24日

阳了，发高烧，摆了

2022年12月23日

持续发高烧，寄！

2022年12月22日

持续发高烧，寄！

2022年12月21日

持续发高烧，寄！

2022年12月20日

持续发高烧，寄！

2022年12月19日

• 1971. 寻找图中是否存在路径

解题思路

我们先将 edges 转换成图 g，然后使用 DFS，判断是否存在从 source 到 destination 的路径
过程中，用数组 v 记录已经访问过的顶点，避免重复访问。
时间复杂度 O(n + m)O(n+m)，其中 nn 和 mm 分别是节点数和边数。

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        def dfs(i):
            if i == destination:
                return True
            v.add(i)
            for j in g[i]:
                if j not in v and dfs(j):
                    return True
            return False

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        v = set()
        return dfs(source)

2022年12月18日

• 14. 最长公共前缀

解题思路

依次比较两个字符串取他们相同的部分，再用相同的部分和后面的字符串比较，再取相同的部分，继续相同的工作；
若前缀为空就return字符串

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        pre = strs[0]
        l = len(strs)
        for i in range(1, l):
            pre = self.cmp(pre, strs[i])
            if not pre:
                break
        return pre

    def cmp(self, str1, str2):
        index = 0
        l_m = min(len(str1), len(str2))
        while index < l_m and str1[index] == str2[index]:
            index += 1
        return str1[:index]

2022年12月17日

第一题

• 1764. 通过连接另一个数组的子数组得到一个数组

解题思路

贪心思想，对每个子数组进行遍历，k作为nums下标，从0开始遍历，进行子数组长的切片，如果等于子数组，则k+=子数组的长，否则k+=1；边界条件是k+子数组长小于nums长
否则，return False;不然就return True

class Solution:
    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
        k=0
        for g in groups:
            while k+len(g)<=len(nums):
                if nums[k:k+len(g)]==g:
                    k+=len(g)
                    break
                k+=1
            else:
                return False
        return True
        

第二题

• 12. 整数转罗马数字

解题思路

打表即可

class Solution:
    def intToRoman(self, num: int) -> str:
        roman=[]
        l=[(1000, "M"),(900, "CM"),(500, "D"),(400, "CD"),(100, "C"),(90, "XC"),         (50, "L"),(40, "XL"),(10, "X"),(9, "IX"),(5, "V"),(4, "IV"),(1, "I")]
        for value,ch in l:
            while num>=value:
                num-=value
                roman.append(ch)
            if num==0:
                break
        return ''.join(roman)

第三题

• 189. 轮转数组

解题思路

发现新数据的位置为 (i+k)%len(nums) 用新的数组存储数据，最后赋值给元素即可

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        l = len(nums)
        n = list(range(l))
        for i in range(l):
            n[(i + k) % l] = nums[i]
        for i in range(l):
            nums[i] = n[i]

第四题

• 4. 寻找两个正序数组的中位数

解题思路

要求时间复杂度O(log (m+n));没思路，学习题解

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def getKthElement(k):
            i, j = 0, 0
            while True:
                if i == m:
                    return nums2[j + k - 1]
                if j == n:
                    return nums1[i + k - 1]
                if k == 1:
                    return min(nums1[i], nums2[j])
                newi = min(i + k // 2 - 1, m - 1)
                newj = min(j + k // 2 - 1, n - 1)
                pivot1, pivot2 = nums1[newi], nums2[newj]
                if pivot1 <= pivot2:
                    k -= newi - i + 1
                    i = newi + 1
                else:
                    k -= newj - j + 1
                    j = newj + 1

        m, n = len(nums1), len(nums2)
        l = m + n
        if l % 2 == 1:
            return getKthElement((l + 1) // 2)
        else:
            return (getKthElement(l // 2) + getKthElement(l // 2 + 1)) / 2

2022年12月16日

第一题

• 1785. 构成特定和需要添加的最少元素

解题思路

将给出的数组nums进行累加，与goat相减取绝对值，再整除limit；判断是否整除，是的话返回ans；否则返回ans+1

class Solution:
    def minElements(self, nums: List[int], limit: int, goal: int) -> int:
        s=sum(i for i in nums)
        ans=abs(s-goal)//limit
        return ans if abs(s-goal)%limit==0 else ans+1

第二题

• 278. 第一个错误的版本

解题思路

二分查找，注意是向下取整即可

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left=1
        right=n
        ans=0
        while(left<=right):
            mid=int(left+(right-left+1)/2)
            if(isBadVersion(mid)==False):
                left=mid+1
            elif(isBadVersion(mid)==True):
                right=mid-1
                ans=mid
        return ans

第三题

• 35. 搜索插入位置

解题思路

二分查找，注意没找到的边界条件即可

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left,right=0,len(nums)-1
        ans=0
        while left<=right:
            mid=int(left+(right-left)/2)
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                right=mid-1
                ans=mid
            else :
                left=mid+1
                ans=left
        return 0 if ans<0 else ans

第四题

• 977. 有序数组的平方

解题思路

思路一:sorted排序返回平方列表即可，时间复杂度O(nlogn)
思路二:双指针，找到分界点0；负数平方都是递减、正数的平方都是递增；遍历两侧，小的先放进去列表，移动指针
进行类似归并排序的操作

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(i*i for i in nums )

思路二:

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l = []
        mid = -1
        for i, num in enumerate(nums):
            if num < 0:
                mid = i
            else:
                break
        i, j = mid, mid + 1
        while i >= 0 or j < len(nums):
            if i < 0:
                l.append(nums[j] * nums[j])
                j += 1
            elif j == len(nums):
                l.append(nums[i] * nums[i])
                i -= 1
            elif nums[i] * nums[i] < nums[j] * nums[j]:
                l.append(nums[i] * nums[i])
                i -= 1
            else:
                l.append(nums[j] * nums[j])
                j += 1
        return l

2022年12月15日

第一题

• 1945. 字符串转化后的各位数字之和

解题思路

纯模拟题，按照要求转换，取数字各位相加，若小于10，直接返回

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        temp = ''
        for i in s:
            temp += str(ord(i) - 96)
        ans = 0
        num = int(temp)
        for i in range(k):
            ans=0
            if num < 10:
                ans = num
                break
            while num > 0:
                t = num % 10
                num = num // 10
                ans += t
            num = ans

        return ans

简洁代码

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        s = ''.join(str(ord(ch) - ord('a') + 1) for ch in s)
        for _ in range(k):
            t = sum(int(ch) for ch in s)
            s = str(t)
        return int(s)

第二题

• 1779. 找到最近的有相同 X 或 Y 坐标的点

解题思路

模拟即可

class Solution:
    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
        ans,mi=-1,inf
        for i ,(X,Y) in enumerate(points):
            if X==x or Y==y:
                d=abs(x-X)+abs(y-Y)
                if mi>d:
                    ans=i
                    mi=d
        return ans

2022年12月14日

• 3. 无重复字符的最长子串

解题思路

队列的思想比较好，从左边遍历，如果不在队列中就append到队尾，如果在就del队首元素，同时维护最大的长度

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        mx = 0
        dq = []
        for i in s:
            while i in dq:
                del dq[0]
            dq.append(i)
            mx = max(mx, len(dq))
        return mx

2022年12月13日

• 13. 罗马数字转整数

解题思路

字典存储，模拟即可

class Solution:
    def romanToInt(self, s: str) -> int:
        dict={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        ans=0
        n=len(s)
        for i,ch in enumerate(s):
            value=dict[ch]
            if i< n-1 and value<dict[s[i+1]]:
                ans-=value
            else:
                ans+=value
        return ans

2022年12月12日

• 1781. 所有子字符串美丽值之和

解题思路

纯暴力，双循环即可

class Solution:
    def beautySum(self, s: str) -> int:
        ans = 0
        for i in range(len(s)):
            cnt = Counter()
            mx = 0
            for j in range(i, len(s)):
                cnt[s[j]] += 1
                mx = max(mx, cnt[s[j]])
                ans += mx - min(cnt.values())
        return ans

2022年12月11日

• 1827. 最少操作使数组递增

解题思路

贪心思想,如果nums[i+1]小于等于nums[i],ans+=nums[i]-nums[i+1]+1的步数
nums[i+1]=nums[i]+1;循环返回即可

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans=0
        for i in range(0,len(nums)-1):
            if nums[i+1]<=nums[i]:
                ans=ans+nums[i]-nums[i+1]+1
                nums[i+1]=nums[i]+1
        return ans

2022年12月10日

• 9.回文数

解题思路

将数据改为字符串类型，进行字符串切片比较即可

class Solution:
    def isPalindrome(self, x: int) -> bool:
        s=str(x)
        return s==s[::-1]

2022年12月9日

• 1832. 判断句子是否为全字母句

解题思路

思路一:遍历字符串，将每个字母存入set中，最后判断set长度是否为26即可
思路二:用一个整数 ans 记录出现过的字母，其中ans的第 i位表示第 i 个字母是否出现过
最后判断ans的二进制表示中是否有 26个1，也即判断ans是否等于 2^26 -1若是，返回 true，否则返回 false

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        return len(set(sentence))==26

思路二

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        ans=0
        for i in sentence:
            ans|=1<<(ord(i)-ord('a'))
        return ans==(1<<26)-1

2022年12月8日

• 704. 二分查找

解题思路

二分法,每次取中间与目标值对比;等于返回;小于目标值right=mid-1;大与目标值left=mid+1;

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left=0
        right=len(nums)-1
        while(left<=right):
            mid = int(left + (right - left) / 2)
            if(nums[mid]==target):
                return mid
            elif (nums[mid]<target):
                left=mid+1
            elif (nums[mid]>target):
                right=mid-1
        return-1

class Solution {
public:
    int search(vector<int>& nums, int target) {
       int left = 0, right =nums.size()- 1;
    while (left <= right) {
        int mid = left +(right-left) / 2;
        if (nums[mid] == target)
            return mid;
        if (target < nums[mid])
            right = mid - 1;
        else if (target > nums[mid])
            left = mid + 1;
    }
    return -1;
    }
};

2022年12月7日

• 1.两数之和

解题思路

给出一个字典作为哈希表，target对每个元素进行相减，如果相减的值在哈希表的索引中，返回这个对应的value
和此时被减数的索引；不在的话把被减数作为索引存入哈希表中，并赋值它对应的索引

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = {}
        for i, value in enumerate(nums):
            if target - value in hashtable.keys():
                return [hashtable[target - value], i]
            else:
                hashtable[nums[i]] = i