2019-09-08 5.4k

Leetcode Primary Class

#1 two-sum 两数之和

Question

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

Example

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

Solution

方法一

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for index, value in enumerate(nums):
        	left = target-value
        	if left in nums[(index+1):]:
        		left_index = nums.index(left)
        		if index == left_index:
        			left_index = left_index + nums[left_index+1:].index(left) + 1
        		return [index, left_index]
        return []

方法二

参考了大神们的解法，通过哈希来求解，这里通过字典来模拟哈希查询的过程。
个人理解这种办法相较于方法一其实就是字典记录了 num1 和 num2 的值和位置，而省了再查找 num2 索引的步骤。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashmap = {}
        for key, value in enumerate(nums):
        	hashmap[value] = key
        for i, num in enumerate(nums):
            j = hashmap.get(target - num)
            if j is not None and j != i:
                return [i, j]

#7 reverse-integer 整数反转

Question

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

注意:

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

Example

示例 1:

1 2	输入: 123 输出: 321

示例 2:

1 2	输入: -123 输出: -321

示例 3:

1 2	输入: 120 输出: 21

Solution

方法一

首先想到的肯定是将int类型转换成str类型，逆置后再转换成int类型。

class Solution(object):
        
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x > 0:
            x = int(str(x)[::-1])
        else:
            x= int('-' + str(abs(x))[::-1])
        
        if x < 2**31 and x > -2**31:
            return x
        else:
            return 0

这个代码最巧妙的地方就在于使用了切片这种特性来直接逆置字符串。

方法二

我们想重复“弹出” x的最后一位数字，并将它“推入”到 rev 的后面。最后，rev 将与 x相反。

要在没有辅助堆栈 / 数组的帮助下 “弹出” 和 “推入” 数字，我们可以使用数学方法。

//pop operation:
pop = x % 10;
x /= 10;

//push operation:
temp = rev * 10 + pop;
rev = temp;

Extra

数值交换：x, y = y, x
int to list：l = [int(x) for x in str(num)]
list to int：
- 使用列表生成器：
  1
  2
  s = [str(i) for i in list]
  res = int(''.join(s))
- 使用map函数：res = int(''.join(map(str, list)))

#9 palindrome-number 回文数

Question

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

Example

示例 1:
1
2
3
输入: 121
输出: true
示例 2:

示例2：

1
2
3

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例3：

1
2
3

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

Solution

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x > 0:
            y = int(str(x)[::-1])
            if x == y:
                return True
        elif x == 0:
            return True
        else:
            return False

#13_roman-to-integer 罗马数字转整数

Question

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

Example

示例 1:

1 2	输入: "III" 输出: 3

示例 2:

1 2	输入: "IV" 输出: 4

示例 3:

1 2	输入: "IX" 输出: 9

示例 4:

1
2
3

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

1
2
3

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

Solution

方法一

思路：从左往右一位一位的看，如果这一位数字比它右边一位的数字大或与其相等，则加上这一位代表的值，如果它比右边一位小，则减去这一位代表的数字。

例如： ‘MMCMLXIV’: 第一位是M，它的后一位也是M，所以 num = 0 + 1000，之后 M > C, num = num + 1000 =2000,之后到特殊值，因为C<M，所以num=num-C =2000-100=1900,之后再加上1000得到 num=2900……以此类推进行下去，最后可得到 num = 2964

需要注意的是，位与后一位的比较只需进行到倒数第二位即可，因为最后一位没有比它小的一位能够进行比较，直接加上最后一位代表的值即可。

判断到倒数第二位时，如果最后一个数比前一个数大，程序就会直接减去倒数第二个数，然后直接加上最后一个数就行了。所以最后一个数不管比前面的数大还是小都会直接加上它的值。

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman_dict = {'M': 1000, 'D': 500, 'C': 100, 'L': 50, 'X': 10, 'V': 5, 'I': 1}
        sum = 0

        for i in range(len(s) - 1):
        	if roman_dict.get(s[i]) >= roman_dict.get(s[i+1]):
        		sum += roman_dict.get(s[i])
        	else:
        		sum -= roman_dict.get(s[i])

        last_num = s[len(s) - 1]
        sum += last_num
        return sum

方法二

思路：

构建一个字典记录所有罗马数字子串，注意长度为2的子串记录的值是**（实际值 - 子串内左边罗马数字代表的数值）**。
这样一来，遍历整个 s 的时候判断当前位置和前一个位置的两个字符组成的字符串是否在字典内，如果在就记录值，不在就说明当前位置不存在小数字在前面的情况，直接记录当前位置字符对应值。

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman_dict = {'M': 1000, 'D': 500, 'C': 100, 'L': 50, 'X': 10, 'V': 5, 'I': 1, 'IV': 3, 'IX': 8, 'XL': 30, 'XC': 80, 'CD': 300, 'CM': 800}

        return sum(roman_dict.get(s[max(i-1, 0): i+1], roman_dict[n]) for i, n in enumerate(s))

Extra

sum(iterable, [start]) -> number

生成器（generator）

g = (x * x for x in range(10))
1
2
3
4
5
6
7
8
9
10
11

- 如果一个函数定义中包含`yield`关键字，那么这个函数就不再是一个普通函数，而是一个generator：

  ```python
  def fib(max):
      n, a, b = 0, 0, 1
      while n < max:
          yield b
          a, b = b, a + b
          n = n + 1
      return 'done'

#14 longest-common-prefix 最长公共前缀

Question

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

所有输入只包含小写字母 a-z 。

Example

示例1

1 2	输入: ["flower","flow","flight"] 输出: "fl"

示例2

1
2
3

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

Solutions

方法一

思路：

首先想到列表为空的情况，返回空字符串。
第一个字符串的第一位与第二个字符串的第一位比较，若相同则继续将第二个字符串的第一位和第三个字符串第一位比较，依次类推。若比较到第j和j+1个字符串的第k位不同则返回第一个字符串的前j个子串（不包括第j个字符。
若最后所有字符串都相同，则返回第一个字符串长度为strs中元素的长度最小的子串。

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
        	return ''

        min_len = min(list(map(len, [strs[i] for i in range(len(strs))])))

        for j in range(min_len):
        	for k in range(len(strs) - 1):
        		if strs[k][j] != strs[k+1][j]:
        			return strs[0][:j]
        return strs[0][:min_len] if min_len else ''

方法二

思路：

利用zip函数解包以及set判断是否相同，来对每一个单词的同一位置的字母进行比较

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        res = ""
        for tmp in zip(*strs):
            tmp_set = set(tmp)
            if len(tmp_set) == 1:
                res += tmp[0]
            else:
                break
        return res

Extra

*解包操作：

>>> def func(a,b,c):
...     print(a,b,c)

>>> func(*[1,2,3])
1 2 3
>>> func(*(1,2,3))
1 2 3
>>> func(*"abc")
a b c
>>> func(*{"a":1,"b":2,"c":3})
a b c

zip()函数

把两个或多个数组的所有元素按索引对齐，然后按索引合并成新数组。
set中不允许有重复的元素存在。

#20 valid-parentheses 有效括号

Question

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

Example

示例1

1 2	输入: "()" 输出: true

示例2

1 2	输入: "()[]{}" 输出: true

示例3

1 2	输入: "(]" 输出: false

示例4

1 2	输入: "([)]" 输出: false

示例5

1 2	输入: "{[]}" 输出: true

Solution

方法一

思路

首先空字符串返回True
栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；
需要注意的是若栈为空，且此时读取到的字符是right_par，则直接返回False

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if s == '':
        	return True

        left_par = ['(', '[', '{']
        right_par = [')', ']', '}']

        if s[0] in right_par:
        	return False

        l = []

        for i in range(len(s)):
        	if s[i] in left_par:
        		l.append(s[i])
        	elif l == [] and s[i] in right_par:
        		return False
        	else:
        		if left_par.index(l.pop(-1)) != right_par.index(s[i]):
        			return False
        if l == []:
        	return True
        else:
        	return False

方法二

其实思路是一样的，关键是用字典来替换方法一的两个初始列表

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}
        stack = ['?']
        for c in s:
            if c in dic: stack.append(c)
            elif dic[stack.pop()] != c: return False 
        return len(stack) == 1

解析

stack初始化的时候为什么要加一个?

栈 stack 为空时， stack.pop() 操作会报错；因此，我们采用一个取巧方法，给 stack 赋初值 ?，并在哈希表 dic中建立 key: '?'，value:'?'key的对应关系予以配合。此时当 stack 为空且 c 为右括号时，可以正常提前返回 false。

Extra

Python模拟栈的操作
- 压栈：list.append()
- 出栈：list.pop()
range([start,] end)：start默认是0，返回start - (end-1)的迭代器。

#21 merge-two-sorted-lists 合并两个有序链表

Question

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

Example

示例

1 2	输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

Solution

方法一

思路

要考虑到l1或l2为None的情况下，直接返回非空的链表。
将两个链表的元素中val分别存入两个列表，拼接这两个列表后进行排序，把排序后的列表中的元素组成一个新的链表。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        
        if l1 is None:
        	return l2
        if l2 is None:
        	return l1
        tmp1, tmp2 = [], []

        while l1:
        	tmp1.append(l1.val)
        	l1 = l1.next

        while l2:
        	tmp2.append(l2.val)
        	l2 = l2.next

        l3 = sorted(tmp1 + tmp2)

        l = ListNode(l3[0])
        l.next = None

        p = l

        for i in range(1, len(l3)):
        	tmp = ListNode(l3[i])
        	tmp.next = None
        	p.next = tmp
        	p = tmp

        return l

方法二

思路

首先，我们设定一个哨兵节点 prehead ，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。然后，我们重复以下过程，直到 l1 或者l2指向了 null ：如果 l1 当前位置的值小于等于 l2 ，我们就把 l1 的值接在 prev 节点的后面同时将 l1 指针往后移一个。否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都把prev 向后移一个元素。

在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        prehead = ListNode(-1)
        
        prev = prehead
        
        while l1 and l2:
            if l1.val <= l2.val:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next
            prev = prev.next
        
        prev.next = l1 if l1 is not None else l2
        
        return prehead.next

Extra

连接两个列表：list1 + list2
sort()和sorted()的区别
- sort是容器的函数：sort(cmp=None, key=None, reverse=False)
  
  sorted是python的内建函数：sorted(iterable, cmp=None, key=None, reverse=False)
  
  即：sort 是应用在 list 上的方法，sorted 可以对所有可迭代的对象进行排序操作。
- 对于一个无序的列表a，调用a.sort()，对a进行排序后返回a，sort()函数修改待排序的列表内容。
  
  而对于同样一个无序的列表a，调用sorted(a)，对a进行排序后返回一个新的列表，而对a不产生影响。
- key：用来指定一个函数，此函数在每次元素比较时被调用，此函数代表排序的规则，也就是你按照什么规则对你的序列进行排序；
  
  reverse：是用来表明是否逆序，默认的False情况下是按照升序的规则进行排序的，当reverse=True时，便会按照降序进行排序。

#26_remove-duplicates-from-sorted-array

Question

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:
1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Example

示例1

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例2

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

Solution

思路

我们可以放置两个指针i和j，其中i是慢指针，而j是快指针。只要 nums[i] = nums[j]，我们就增加j以跳过重复项。

当我们遇到nums[i] = nums[j]时，跳过重复项的运行已经结束，因此我们必须把它nums[j]的值复制到 nums[i + 1]。然后递增i，接着我们将再次重复相同的过程，直到j到达数组的末尾为止。

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        for j in range(1, len(nums)):
        	if nums[i] != nums[j]:
        		i = i+1
        		nums[i] = nums[j]

        return i+1

#27_remove-element

Question

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

Example

示例一

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

示例二

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

Solution

方法一

思路

首先遍历循环nums，并使用count来计数有多少个待删除的元素；
再执行count次remove函数删除nums中值为val的元素

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        count = 0
        for i in range(len(nums)):
            if nums[i] == val:
                count = count+1
        
        for j in range(count):
            nums.remove(val)
            
        return len(nums)

方法二

思路

这道题的思路和删除排序数组中的重复项解法类似

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        for j in range(len(nums)):
        	if nums[j] != val:
        		nums[i] = nums[j]
                i = i+1

        return i

#28_implement-strstr

Question

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

Example

示例一

1 2	输入: haystack = "hello", needle = "ll" 输出: 2

示例二

1 2	输入: haystack = "aaaaa", needle = "bba" 输出: -1

Solution

方法一

思路

若needle为空字符串，则返回0；
若needle的首字符不在haystack中，则返回-1；
循环遍历haystack，找到needle首字符在haystack的起始位置，向后比较needle_len长度的子字符串。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        needle_len = len(needle)
        if needle_len == 0:
            return 0
        char = needle[0]
        if char not in haystack:
            return -1
        else:
            for i in range(len(haystack)):
                if char == haystack[i]:
                    if haystack[i:(i+needle_len)] == needle:
                        return i             
        return -1

方法二

思路

和方法一的思路相似，只是代码写的更为简洁，但是感觉更为暴力。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack) - len(needle)+1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1

#35_search_insert_position

Question

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

Example

示例一

1 2	输入: [1,3,5,6], 5 输出: 2

示例二

1 2	输入: [1,3,5,6], 2 输出: 1

示例三

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

Solution

方法一

思路

如果target在nums中，则直接返回索引；
否则将target添加在nums列表后面，再对其进行排序，最后返回索引。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target in nums:
            return nums.index(target)
        nums.append(target)
        nums.sort()
        return nums.index(target)

这种方法其实比较取巧，而题目的意图是想要考察二分查找。

方法二

思路

二分法查找

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

编程->算法
#Leetcode #python #算法

文章归档

置顶文章

Web安全

Web安全基础

PHP相关

Writeups

靶机系列

HackTheBox

VulnHub

代码审计

PHP代码审计

大数据安全

机器学习

基础学习

Python

Python基础

Python安全

Java

Java基础

算法

Leetcode

随笔

经验

技术

Leetcode Primary Class

#1 two-sum 两数之和

Question

Example

Solution

方法一

方法二

#7 reverse-integer 整数反转

Question

Example

Solution

方法一

方法二

Extra

#9 palindrome-number 回文数

Question

Example

Solution

#13_roman-to-integer 罗马数字转整数

Question

Example

Solution

方法一

方法二

Extra

#14 longest-common-prefix 最长公共前缀

Question

Example

Solutions

方法一

方法二

Extra

#20 valid-parentheses 有效括号

Question

Example

Solution

方法一

方法二

Extra

#21 merge-two-sorted-lists 合并两个有序链表

Question

Example

Solution

方法一

方法二

Extra

#26_remove-duplicates-from-sorted-array

Question

Example

Solution

#27_remove-element

Question

Example

Solution

方法一

方法二