LeetCode刷题记录

主要记录LEETCODE刷题的感想和总结~

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]

示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

###思路分析：使用双栈实现队列，队列要求先进先出，所以一个栈用于进，另一个栈倒置用于出，在python中可以使用append()方法添加元素，使用pop()弹出元素
class CQueue(object):

    #初始化双栈
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

        return None

    #添加元素，在第一个栈中添加元素
    def appendTail(self, value):
        """
        :type value: int
        :rtype: None
        """
        self.stack1.append(value)
        return None

	#删除最先进去的元素
    def deleteHead(self):
        """
        :rtype: int
        """
        #当第二个栈不为空，则可以直接弹出
        #否则需要将第一个栈中的元素弹入第二个栈
        if len(self.stack2) == 0:
            if len(self.stack1) == 0:
                return -1
            #将第一个栈中的元素全部弹出装入第二个栈中
            #达到的效果就是第一个栈最先进去的元素在第二个栈的顶部
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        #第二个栈顶端的元素就是队列删除的最先进去的元素
        return self.stack2.pop()

# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

剑指 Offer 30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.
 

提示：
各函数的调用总次数不超过 20000 次

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        #初始化两个栈，一个栈正常存储，另一个栈存储最小值
        self.stack = []
        self.minStack = []

    def push(self, x):2
        """
        :type x: int
        :rtype: None
        """
        #第一个栈正常存储
        self.stack.append(x)
        #第二个栈比较是否出现更小的值，如果出现，添加到最小栈
        if not self.minStack or x <= self.minStack[-1]:
            self.minStack.append(x)

    def pop(self):
        """
        :rtype: None
        """
        #第一个栈正常弹出，第二个栈比较是否弹出最小值，如果是，第二个栈也弹出
        if self.stack.pop() == self.minStack[-1]:
            self.minStack.pop()


    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1]


    def min(self):
        """
        :rtype: int
        """
        #最小值即最小栈最后一个值
        return self.minStack[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
 
限制：
0 <= 链表长度 <= 10000

# 递归法
# [1,2,3,4,5]
# [2,3,4,5]
# [3,4,5]
# [4,5]
# [5]
# []
# [5,4,3,2,1]
class Solution(object):
    def reversePrint(self, head):
        if head is None:
            return []
        return self.reversePrint(head.next) + [head.val]

# 普通做法
# 遍历链表使用一个list存储链表
# 反转链表
class Solution(object):
    def reversePrint(self, head):
        resList = []
        while head:
            resList.append(head.val)
            head = head.next
        return resList[::-1]
# list的[]中有三个参数，用冒号分割
# list[param1:param2:param3]
# param1，相当于start_index，可以为空，默认是0
# param2，相当于end_index，可以为空，默认是list.size
# param3，步长，默认为1。步长为-1时，返回倒序原序列

剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：
0 <= 节点个数 <= 5000

#定义指针 pre，cur 分别指向 null 和头节点。
#遍历链表，将 cur.next 临时保存到 t 中，然后改变指针 cur 指向的节点的指向，将其指向 pre 指针指向的节点，即 cur.next = pre。然后 pre 指针指向 cur，cur 指针往前走。
#当遍历结束后，返回 pre 指针即可。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head
        while cur:
            t = cur.next
            cur.next = pre
            pre = cur
            cur = t
        return pre

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
 
限制：
0 <= s 的长度 <= 10000

class Solution(object):
    def replaceSpace(self, s):
        """
        :type s: str
        :rtype: str
        """
        return s.replace(" ","%20")

# Python replace()方法

# 描述
# Python replace() 方法把字符串中的 old（旧字符串） 替换成 new(新字符串)，如果指定第三个参数max，则替换不超过 max 次。

# replace()方法语法：

str.replace(old, new[, max])
# 参数
# old -- 将被替换的子字符串。
# new -- 新字符串，用于替换old子字符串。
# max -- 可选字符串, 替换不超过 max 次
# 返回值
# 返回字符串中的 old（旧字符串） 替换成 new(新字符串)后生成的新字符串，如果指定第三个参数max，则替换不超过 max 次。

# 实例
str = "this is string example....wow!!! this is really string";
print str.replace("is", "was");
print str.replace("is", "was", 3);
# 以上实例输出结果如下：
thwas was string example....wow!!! thwas was really string
thwas was string example....wow!!! thwas is really string

剑指 Offer 58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
 
限制：
1 <= k < s.length <= 10000

class Solution(object):
    def reverseLeftWords(self, s, n):
        """
        :type s: str
        :type n: int
        :rtype: str
        """
        return s[n:]+s[0:n]

## Python字符串运算符

下表实例变量 a 值为字符串 "Hello"，b 变量值为 "Python"：

操作符	描述	实例
+	字符串连接	>>>a + b ‘HelloPython’
*	重复输出字符串	>>>a * 2 ‘HelloHello’
[]	通过索引获取字符串中字符	>>>a[1] ‘e’
[ : ]	截取字符串中的一部分	>>>a[1:4] ‘ell’
in	成员运算符 - 如果字符串中包含给定的字符返回 True	>>>”H” in a True
not in	成员运算符 - 如果字符串中不包含给定的字符返回 True	>>>”M” not in a True
r/R	原始字符串 - 原始字符串：所有的字符串都是直接按照字面的意思来使用，没有转义特殊或不能打印的字符。 原始字符串除在字符串的第一个引号前加上字母”r”（可以大小写）以外，与普通字符串有着几乎完全相同的语法。	>>>print r’\n’ \n >>> print R’\n’ \n
%	格式字符串

## Python 的字符串内建函数

字符串方法是从 Python1.6 到 2.0 慢慢加进来的 —— 它们也被加到了Jython 中。

这些方法实现了 string 模块的大部分方法，如下表所示列出了目前字符串内建支持的方法，所有的方法都包含了对 Unicode 的支持，有一些甚至是专门用于 Unicode 的。

方法	描述
string.capitalize()	把字符串的第一个字符大写
string.center(width)	返回一个原字符串居中,并使用空格填充至长度 width 的新字符串
string.count(str, beg=0, end=len(string))	返回 str 在 string 里面出现的次数，如果 beg 或者 end 指定则返回指定范围内 str 出现的次数
string.decode(encoding=’UTF-8’, errors=’strict’)	以 encoding 指定的编码格式解码 string，如果出错默认报一个 ValueError 的 异 常 ， 除非 errors 指 定 的 是 ‘ignore’ 或 者’replace’
string.encode(encoding=’UTF-8’, errors=’strict’)	以 encoding 指定的编码格式编码 string，如果出错默认报一个ValueError 的异常，除非 errors 指定的是’ignore’或者’replace’
string.endswith(obj, beg=0, end=len(string))	检查字符串是否以 obj 结束，如果beg 或者 end 指定则检查指定的范围内是否以 obj 结束，如果是，返回 True,否则返回 False.
string.expandtabs(tabsize=8)	把字符串 string 中的 tab 符号转为空格，tab 符号默认的空格数是 8。
string.find(str, beg=0, end=len(string))	检测 str 是否包含在 string 中，如果 beg 和 end 指定范围，则检查是否包含在指定范围内，如果是返回开始的索引值，否则返回-1
string.format()	格式化字符串
string.index(str, beg=0, end=len(string))	跟find()方法一样，只不过如果str不在 string中会报一个异常.
string.isalnum()	如果 string 至少有一个字符并且所有字符都是字母或数字则返回 True,否则返回 False
string.isalpha()	如果 string 至少有一个字符并且所有字符都是字母则返回 True,否则返回 False
string.isdecimal()	如果 string 只包含十进制数字则返回 True 否则返回 False.
string.isdigit()	如果 string 只包含数字则返回 True 否则返回 False.
string.islower()	如果 string 中包含至少一个区分大小写的字符，并且所有这些(区分大小写的)字符都是小写，则返回 True，否则返回 False
string.isnumeric()	如果 string 中只包含数字字符，则返回 True，否则返回 False
string.isspace()	如果 string 中只包含空格，则返回 True，否则返回 False.
string.istitle()	如果 string 是标题化的(见 title())则返回 True，否则返回 False
string.isupper()	如果 string 中包含至少一个区分大小写的字符，并且所有这些(区分大小写的)字符都是大写，则返回 True，否则返回 False
string.join(seq)	以 string 作为分隔符，将 seq 中所有的元素(的字符串表示)合并为一个新的字符串
string.ljust(width)	返回一个原字符串左对齐,并使用空格填充至长度 width 的新字符串
string.lower()	转换 string 中所有大写字符为小写.
string.lstrip()	截掉 string 左边的空格
string.maketrans(intab, outtab)	maketrans() 方法用于创建字符映射的转换表，对于接受两个参数的最简单的调用方式，第一个参数是字符串，表示需要转换的字符，第二个参数也是字符串表示转换的目标。
max(str)	返回字符串 str 中最大的字母。
min(str)	返回字符串 str 中最小的字母。
string.partition(str)	有点像 find()和 split()的结合体,从 str 出现的第一个位置起,把 字 符 串 string 分 成 一 个 3 元 素 的 元 组 (string_pre_str,str,string_post_str),如果 string 中不包含str 则 string_pre_str == string.
string.replace(str1, str2, num=string.count(str1))	把 string 中的 str1 替换成 str2,如果 num 指定，则替换不超过 num 次.
string.rfind(str, beg=0,end=len(string) )	类似于 find() 函数，返回字符串最后一次出现的位置，如果没有匹配项则返回 -1。
string.rindex( str, beg=0,end=len(string))	类似于 index()，不过是返回最后一个匹配到的子字符串的索引号。
string.rjust(width)	返回一个原字符串右对齐,并使用空格填充至长度 width 的新字符串
string.rpartition(str)	类似于 partition()函数,不过是从右边开始查找
string.rstrip()	删除 string 字符串末尾的空格.
string.split(str=””, num=string.count(str))	以 str 为分隔符切片 string，如果 num 有指定值，则仅分隔 num+1 个子字符串
[string.splitlines(keepends])	按照行(‘\r’, ‘\r\n’, ‘\n’)分隔，返回一个包含各行作为元素的列表，如果参数 keepends 为 False，不包含换行符，如果为 True，则保留换行符。
string.startswith(obj, beg=0,end=len(string))	检查字符串是否是以 obj 开头，是则返回 True，否则返回 False。如果beg 和 end 指定值，则在指定范围内检查.
[string.strip(obj])	在 string 上执行 lstrip()和 rstrip()
string.swapcase()	翻转 string 中的大小写
string.title()	返回”标题化”的 string,就是说所有单词都是以大写开始，其余字母均为小写(见 istitle())
string.translate(str, del=””)	根据 str 给出的表(包含 256 个字符)转换 string 的字符,要过滤掉的字符放到 del 参数中
string.upper()	转换 string 中的小写字母为大写
string.zfill(width)	返回长度为 width 的字符串，原字符串 string 右对齐，前面填充0

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 
 
限制：
2 <= n <= 100000

# 排序
# 先排序，将相同的数字聚集到一起。
# 再遍历，当位于 i 与 i + 1 的数字相等时，返回该数字。
class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sorted_nums = sorted(nums)
        for i in range(len(nums)):
            if sorted_nums[i] == sorted_nums[i+1]:
                return sorted_nums[i]   
        return -1

# 哈希表
# 记录数字在数组中的数量，当数量为 2 时，返回即可。
class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sorted_nums = sorted(nums)
        hash_map = dict()
        for i, number in enumerate(sorted_nums):
            if number in hash_map:
                return number
            hash_map[number] = i
        return -1

Python enumerate() 函数

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

语法
以下是 enumerate() 方法的语法:

enumerate(sequence, [start=0])
参数
sequence -- 一个序列、迭代器或其他支持迭代对象。
start -- 下标起始位置的值。
返回值
返回 enumerate(枚举) 对象。

实例
以下展示了使用 enumerate() 方法的实例：

>>> seasons = ['Spring', 'Summer', 'Fall', 'Winter']
>>> list(enumerate(seasons))
[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]
>>> list(enumerate(seasons, start=1))       # 下标从 1 开始
[(1, 'Spring'), (2, 'Summer'), (3, 'Fall'), (4, 'Winter')]

普通的 for 循环
>>> i = 0
>>> seq = ['one', 'two', 'three']
>>> for element in seq:
...     print i, seq[i]
...     i += 1
...
0 one
1 two
2 three

for 循环使用 enumerate
>>> seq = ['one', 'two', 'three']
>>> for i, element in enumerate(seq):
...     print i, element
...
0 one
1 two
2 three

Python sorted() 函数

描述
sorted() 函数对所有可迭代的对象进行排序操作。

sort 与 sorted 区别：
sort 是应用在 list 上的方法，sorted 可以对所有可迭代的对象进行排序操作。
list 的 sort 方法返回的是对已经存在的列表进行操作，无返回值，而内建函数 sorted 方法返回的是一个新的 list，而不是在原来的基础上进行的操作，原列表不发生变化。

sorted 语法：
sorted(iterable, cmp=None, key=None, reverse=False)
参数说明：

iterable -- 可迭代对象。
cmp -- 比较的函数，这个具有两个参数，参数的值都是从可迭代对象中取出，此函数必须遵守的规则为，大于则返回1，小于则返回-1，等于则返回0。
key -- 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
reverse -- 排序规则，reverse = True 降序 ， reverse = False 升序（默认）。

返回值
返回重新排序的列表。

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
    
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
 
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:
输入: [0,1,3]
输出: 2

示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
 
限制：
1 <= 数组长度 <= 10000