正文
python -- leetcode 刷题之路
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
第一题
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
暴力法， 通用写法 vs 列表推导式, 看到 leetcode 上的 耗时 时快时慢，也是茫然。。。 这两种方法耗时均为 O(n2)
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i,v in enumerate(nums):
for j in range(i+1,len(nums)):
if v+nums[j] == target:
return [i,j]
else:
raise ValueError('未找到这样的数字')
# return [[i,j] for i,v in enumerate(nums) for j in range(i+1,len(nums)) if v+nums[j] == target ]
nums = [2, 7, 11, 15]
target = 9
s = Solution()
s.twoSum(nums,target)
# 列表推导式
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
return [[i,j] for i,v in enumerate(nums) for j in range(i+1,len(nums)) if v+nums[j] == target ]
nums = [2, 7, 11, 15]
target = 9
s = Solution()
s.twoSum(nums,target)
# 根据阅读提示，改写为 字典 查找法 (两遍遍历哈希表) 缩短 算法耗时 O(n)
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
d = {}
[d.update({v:i}) for i,v in enumerate(nums)]
for i,v in enumerate(nums):
if (target - v) in d and i!= d[target - v]:
return [i,d[target - v]]
nums = [2, 7, 11, 15]
target = 9
s = Solution()
s.twoSum(nums,target)
# 根据提示，遍历一遍 哈希表方法
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
d = {}
for i,v in enumerate(nums):
value = target - v
if value in d and d[value] != i:
return [d[value],i]
d.update({v:i})
nums = [2, 7, 11, 15]
target = 9
s = Solution()
s.twoSum(nums,target)
总结 ， 可以看到算法依次是 暴力法(嵌套for 两次） O(n2) --》 两遍遍历哈希表(O(n)) --》一遍遍历哈希表 O(n)
第二题
# 在找到第一个非空字符之前，需要移除掉字符串中的空格字符。如果第一个非空字符是正号或负号，选取该符号，并将其与后面尽可能多的连续的数字组合起来，这部分字符即为整数的值。如果第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
# 字符串可以在形成整数的字符后面包括多余的字符，这些字符可以被忽略，它们对于函数没有影响。
# 当字符串中的第一个非空字符序列不是个有效的整数；或字符串为空；或字符串仅包含空白字符时，则不进行转换。
# 若函数不能执行有效的转换，返回 0。
import re
import math
class Solution:
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
pattern = re.compile(r'(-?\d+)')
res = pattern.search(str)
if not res:
raise TypeError('Error')
else:
res = int(res.group(1))
if res < math.pow(-2,31) or res > math.pow(2,31):
raise ValueError('超出范围啦！')
return res
s = Solution()
print(s.myAtoi('42'))
print(s.myAtoi('-42'))
print(s.myAtoi('4193 with words'))
print(s.myAtoi('words and 987'))
s.myAtoi('-91283472332')
ps: 要想通过 leetcode 的 检测呢。。。还是用下面的吧，虽然，都是些 煞笔错误造成不通过
# 在找到第一个非空字符之前，需要移除掉字符串中的空格字符。如果第一个非空字符是正号或负号，选取该符号，并将其与后面尽可能多的连续的数字组合起来，这部分字符即为整数的值。如果第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
# 字符串可以在形成整数的字符后面包括多余的字符，这些字符可以被忽略，它们对于函数没有影响。
# 当字符串中的第一个非空字符序列不是个有效的整数；或字符串为空；或字符串仅包含空白字符时，则不进行转换。
# 若函数不能执行有效的转换，返回 0。
import re
import math
class Solution:
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
str = str.strip()
if not str:
return 0
pattern = re.compile(r'(^([-|+]?|\d)\d+)')
res = pattern.search(str)
if not res:
return 0 #raise TypeError('Error')
else:
res = int(res.group(1))
if res < math.pow(-2,31):
res = int(math.pow(-2,31)) # raise ValueError('超出范围啦！')
if res >= math.pow(2,31):
res = int(math.pow(2,31))-1
return res
s = Solution()
s.myAtoi(' -42')
第三题
给定一个 32 位有符号整数，将整数中的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。
import re
import math
class Solution:
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
if str(x)[0] == '-':
s = str(x)[1:]
x = int('-'+s[::-1])
if math.pow(-2,31) -1 <= int(x) <= math.pow(2,31):
return x
else:
return 0
else:
s = str(x)[::-1]
x = int(s)
if math.pow(-2,31) -1 <= int(x) <= math.pow(2,31):
return x
else:
return 0
分治法应用， 快排
package com.utils;
public class Demo {
public static void main(String [] args){
int [] array = {3,2,1,4,8,7,6,9};
printArray(array);
quickSort(array,0,array.length-1);
printArray(array);
}
public static void printArray(int [] array){
System.out.print("[");
for(int i=0;i<=array.length-1;i++){
if(i == array.length-1){
System.out.println(array[i]+"]");
}
else{
System.out.print(array[i]+",");
}
}
}
public static int [] quickSort(int [] array,int low,int high){
if(low<high){
int l = low;
int r = high;
int base = array[l]; // 确定 每次排序的基准值
// 右到左，寻找比基准值小的，如果没有r指针一直左移
while(l<r && array[r]>=base){
r--;
}
// 跳出了上面的循环从右到左找到了比基准值 base 小的第一个值
if(l<r){
array[l++] = array[r];
}
// 左到右，寻找比基准值大的，如果没有 l 指针一直右移
while(l<r && array[l]<=base){
l++;
}
// 跳出了上面紧挨着的循环意味着 找到了第一个比基准值大的第一个值
if(l<r){
// 这里考虑边界问题
array[r--] = array[l];
// 为何 r 要左移，因为这个坑已经被确定当然继续往前找啦
}
// 当上面所有操作都已完成意味着 第一趟排序完成，那么最后要把基准值填入array[l]
array[l] = base;
// 递归调用快排，分别对base 分成的两个区进行同样操作
quickSort(array,low,l-1);
quickSort(array,r+1,high);
}
return array;
}
}
二分法 查找 前提 列表有序
nums = [1,2,3,4,5,6,7,8,9,10]
def bisearch(n,nums):
low, high = 0,len(nums)-1
while low<=high:
mid = (low + high) //2
# print(low,'--',mid,'--',high)
if n>nums[mid]:
low = mid+1
elif n<nums[mid]:
high = mid -1
else:
return mid
return 'Not Found!'
[bisearch(i,nums) for i in range(1,11)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# 在找到第一个非空字符之前，需要移除掉字符串中的空格字符。如果第一个非空字符是正号或负号，选取该符号，并将其与后面尽可能多的连续的数字组合起来，这部分字符即为整数的值。如果第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
# 字符串可以在形成整数的字符后面包括多余的字符，这些字符可以被忽略，它们对于函数没有影响。
# 当字符串中的第一个非空字符序列不是个有效的整数；或字符串为空；或字符串仅包含空白字符时，则不进行转换。
# 若函数不能执行有效的转换，返回 0。
import re
import math
class Solution:
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
pattern = re.compile(r'(-?\d+)')
res = pattern.search(str)
if not res:
raise TypeError('Error')
else:
res = int(res.group(1))
if res < math.pow(-2,31) or res > math.pow(2,31):
raise ValueError('超出范围啦！')
return res
s = Solution()
print(s.myAtoi('42'))
print(s.myAtoi('-42'))
print(s.myAtoi('4193 with words'))
print(s.myAtoi('words and 987'))
s.myAtoi('-91283472332')
ps: 要想通过 leetcode 的 检测呢。。。还是用下面的吧，虽然，都是些 煞笔错误造成不通过
# 在找到第一个非空字符之前，需要移除掉字符串中的空格字符。如果第一个非空字符是正号或负号，选取该符号，并将其与后面尽可能多的连续的数字组合起来，这部分字符即为整数的值。如果第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
# 字符串可以在形成整数的字符后面包括多余的字符，这些字符可以被忽略，它们对于函数没有影响。
# 当字符串中的第一个非空字符序列不是个有效的整数；或字符串为空；或字符串仅包含空白字符时，则不进行转换。
# 若函数不能执行有效的转换，返回 0。
import re
import math
class Solution:
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
str = str.strip()
if not str:
return 0
pattern = re.compile(r'(^([-|+]?|\d)\d+)')
res = pattern.search(str)
if not res:
return 0 #raise TypeError('Error')
else:
res = int(res.group(1))
if res < math.pow(-2,31):
res = int(math.pow(-2,31)) # raise ValueError('超出范围啦！')
if res >= math.pow(2,31):
res = int(math.pow(2,31))-1
return res
s = Solution()
s.myAtoi(' -42')
给定一个 32 位有符号整数，将整数中的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。
import re
import math
class Solution:
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
if str(x)[0] == '-':
s = str(x)[1:]
x = int('-'+s[::-1])
if math.pow(-2,31) -1 <= int(x) <= math.pow(2,31):
return x
else:
return 0
else:
s = str(x)[::-1]
x = int(s)
if math.pow(-2,31) -1 <= int(x) <= math.pow(2,31):
return x
else:
return 0
分治法应用， 快排
package com.utils;
public class Demo {
public static void main(String [] args){
int [] array = {3,2,1,4,8,7,6,9};
printArray(array);
quickSort(array,0,array.length-1);
printArray(array);
}
public static void printArray(int [] array){
System.out.print("[");
for(int i=0;i<=array.length-1;i++){
if(i == array.length-1){
System.out.println(array[i]+"]");
}
else{
System.out.print(array[i]+",");
}
}
}
public static int [] quickSort(int [] array,int low,int high){
if(low<high){
int l = low;
int r = high;
int base = array[l]; // 确定 每次排序的基准值
// 右到左，寻找比基准值小的，如果没有r指针一直左移
while(l<r && array[r]>=base){
r--;
}
// 跳出了上面的循环从右到左找到了比基准值 base 小的第一个值
if(l<r){
array[l++] = array[r];
}
// 左到右，寻找比基准值大的，如果没有 l 指针一直右移
while(l<r && array[l]<=base){
l++;
}
// 跳出了上面紧挨着的循环意味着 找到了第一个比基准值大的第一个值
if(l<r){
// 这里考虑边界问题
array[r--] = array[l];
// 为何 r 要左移，因为这个坑已经被确定当然继续往前找啦
}
// 当上面所有操作都已完成意味着 第一趟排序完成，那么最后要把基准值填入array[l]
array[l] = base;
// 递归调用快排，分别对base 分成的两个区进行同样操作
quickSort(array,low,l-1);
quickSort(array,r+1,high);
}
return array;
}
}
二分法 查找 前提 列表有序
nums = [1,2,3,4,5,6,7,8,9,10]
def bisearch(n,nums):
low, high = 0,len(nums)-1
while low<=high:
mid = (low + high) //2
# print(low,'--',mid,'--',high)
if n>nums[mid]:
low = mid+1
elif n<nums[mid]:
high = mid -1
else:
return mid
return 'Not Found!'
[bisearch(i,nums) for i in range(1,11)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
package com.utils;
public class Demo {
public static void main(String [] args){
int [] array = {3,2,1,4,8,7,6,9};
printArray(array);
quickSort(array,0,array.length-1);
printArray(array);
}
public static void printArray(int [] array){
System.out.print("[");
for(int i=0;i<=array.length-1;i++){
if(i == array.length-1){
System.out.println(array[i]+"]");
}
else{
System.out.print(array[i]+",");
}
}
}
public static int [] quickSort(int [] array,int low,int high){
if(low<high){
int l = low;
int r = high;
int base = array[l]; // 确定 每次排序的基准值
// 右到左，寻找比基准值小的，如果没有r指针一直左移
while(l<r && array[r]>=base){
r--;
}
// 跳出了上面的循环从右到左找到了比基准值 base 小的第一个值
if(l<r){
array[l++] = array[r];
}
// 左到右，寻找比基准值大的，如果没有 l 指针一直右移
while(l<r && array[l]<=base){
l++;
}
// 跳出了上面紧挨着的循环意味着 找到了第一个比基准值大的第一个值
if(l<r){
// 这里考虑边界问题
array[r--] = array[l];
// 为何 r 要左移，因为这个坑已经被确定当然继续往前找啦
}
// 当上面所有操作都已完成意味着 第一趟排序完成，那么最后要把基准值填入array[l]
array[l] = base;
// 递归调用快排，分别对base 分成的两个区进行同样操作
quickSort(array,low,l-1);
quickSort(array,r+1,high);
}
return array;
}
}
nums = [1,2,3,4,5,6,7,8,9,10]
def bisearch(n,nums):
low, high = 0,len(nums)-1
while low<=high:
mid = (low + high) //2
# print(low,'--',mid,'--',high)
if n>nums[mid]:
low = mid+1
elif n<nums[mid]:
high = mid -1
else:
return mid
return 'Not Found!'
[bisearch(i,nums) for i in range(1,11)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
