Ywc's blog

LeetCode的一些记录

learn
Word count: 1.2kReading time: 5 min
2020/11/28

一组数数组的动态和

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
示例 1：

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
示例 2：

输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。
示例 3：

输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]
class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        for i in range(1,len(nums)):
            nums[i]=nums[i]+nums[i-1]
        return nums

寻找数组的中心索引

解题思路：先求出所有数的总和，然后遍历数组，如果遍历数的左边*2 + 遍历数 == 总和 ， 那这个数就一定是中心索引。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        S=sum(nums)
        leftnums=0
        for i in range(len(nums)):
            if leftnums *2  +  nums[i] == S:
                return i
            else:
                leftnums += nums[i]
        else:
            return -1

sum() 方法对序列进行求和计算

Reference: https://www.pythonheidong.com/blog/article/249069/53202e9ddbc9740732b4/

两数之和

方法一：使用最容易理解的遍历数组进行查找

1
2
3
4
5
6
7
8
9
10
def solution(nums,target):
	#如果列表长度小于2，则直接结束
	if len(nums) < 2:
            return
        #两次循环列表，分别对列表中的所有可能的数字进行相加
        #循环两次列表对应的时间复杂度为O(n²)
        for i in range(0, len(nums) - 1):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

方法二：使用哈希表，通过以空间换取速度的方式，可以将查找时间从 O(n)降低到 O(1)。在python中列表字典的即为哈希类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(nums,target):
	#新建立一个空字典用来保存数值及其在列表中对应的索引
	dict1 = {}
	#遍历一遍列表对应的时间复杂度为O(n)
        for i in range(0, len(nums)):
            #相减得到另一个数值
            num = target - nums[i]
            #如果另一个数值不在字典中，则将第一个数值及其的索引报错在字典中
            #因为在字典中查找的时间复杂度为O(1)，因此总时间复杂度为O(n)
            if num not in dict1:
                dict1[nums[i]] = i
            #如果在字典中则返回
            else:
                return [dict1[num], i]

整数反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def reverse(self, x: int) -> int:
        if x == 0:
            return 0
        if x > 0:
            x = str(x)
            x = x[::-1]
        else:
            x = str(x)
            x = x[1:]    #为了删除负号
            x = x[::-1]
            x = '-' + x
        x = int(x)
        if -2**31 < x < 2**31-1:    #为了不超出32位整数
            return x
        else:
            return 0

利用R = X[::-1]这种方法对X（X必须是字符串）进行一个反转复制的操作
[python 中的::-1]
彻底搞懂切片操作

回文数

1
2
3
4
5
6
7
8
9
10
class Solution:
    def isPalindrome(self, x: int) -> bool:
            if x<0:
                return False
            x=str(x)
            y=x[::-1]
            if x==y:
                return True
            else:
                return False

罗马数字转整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def romanToInt(self, s: str) -> int:
        d = {'I': 1, 'IV': 4, 'V': 5, 'IX': 9, 'X': 10, 'XL': 40, 'L': 50, 'XC': 90,  'C': 100, 'CD': 400, 'D': 500, 'CM': 900, 'M': 1000}
        result = 0
        i = 0
        while i < len(s):
            #查看当前位和下一位的字符
            str1 = s[i:i+2]
            #如果当前位置是特殊情况，那么返回其在字典中对应值，并且下一次从特殊字符之后一位开始索引
            if str1 in d:
                result += d.get(str1)
                i += 2
            #如果当前位不是特殊情况，那么只返回当前位的数值
            else:
                result += d[s[i]]
                i += 1
        return result

最长公共前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:                                        #边界条件判断，若字符串为空，则返回空
            return ""
        short_word=min(strs,key=len)                        #筛选出长度最短的单词然后进行遍历
        for i,e in enumerate(short_word):                   #遍历长度最短的单词
            for others in strs:                             #遍历列表中的其他字符串
                if others[i]!=e:                            #一旦出现非公共字符，返回公共字符
                    return short_word[:i]
        return short_word                                   #遍历结束后依然没匹配到非公共字符，则返回整个字符

enumerate
enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。

Author：V1ZkRA

Link：https://yinwc.github.io/2020/11/28/LeetCode%E7%9A%84%E4%B8%80%E4%BA%9B%E8%AE%B0%E5%BD%95/

Publish date：November 28th 2020, 4:56:40 pm

Update date：February 2nd 2023, 3:03:59 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 一组数数组的动态和
  2. 2. 寻找数组的中心索引
  3. 3. 两数之和
  4. 4. 整数反转
  5. 5. 回文数
  6. 6. 罗马数字转整数
  7. 7. 最长公共前缀
Total : 131
2023
2022
2021
2020
2019
2018
CTF 企业安全 learn python 漏洞 安全评估 前端安全 安全开发 代码审计 SRC problem 渗透测试 Crypto 应急响应 云安全 SCA
blog 漏洞 learn