领扣–引领新时尚

1. 两数之和问题

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

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

示例:

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

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

解法1–暴力解法

思路:

给定一个数组和一个特定的目标值,对每一个数进行遍历,然后利用两层循环遍历的值进行if条件判断,如果相等,则返回下标;否则返回None.

具体实现:

class Solution:
def twoSum(self, nums,target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i]+nums[j] == target:
return [i, j]
else:
continue

nums = [2,7,11,15]
target = 9
solution = Solution()
print(solution.twoSum(nums,target))

缺点:过于暴力,两层循环使得时间代价过高。

时间复杂度:O(n^2^)

解法2–较优化算法

思路:

相比于暴力解法,此法优化了双层循环

一次循环遍历,然后用目标值减去数组中的每一个值,然后判断减去得到的值是否在数组中,进而再判断小标问题;

具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
> class Solution:
> def twoSum(self, nums, target):
> for i in range(0, len(nums)):
> a = target - nums[i]
> if a in nums:
> b = nums.index(a)
> if b != i:
> return [i, b]
>
> nums = [2, 7, 11, 15]
> target = 9
> solution = Solution()
> print(solution.twoSum(nums, target))
>

解法3–优化算法 <来源于网络,怪自己 :sweat:···>

思路:

优解:创建一个字典,通过循环把 target - nums[x]作为键,x作为值存入字典,边存边检查当前正在处理的nums[x]是否存在于字典中,存在:返回字典中nums[x]的值,和当前正在使用的x的值。

具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
> class Solution:
> def twoSum(self, nums, target):
> dic = {}
> for x in range(len(nums)):
> if target - nums[x] in dic:
> result = [dic[target - nums[x]], x]
> return result
> dic[nums[x]] = x
>
> nums = [2, 7, 11, 15]
> target = 9
> solution = Solution()
> print(solution.twoSum(nums, target))
>

2. 回文数问题

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

示例 1:

1
2
输入: 121
输出: true

示例 2:

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

示例 3:

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

解法1–较优化解法

思路:

将所给数字转化为字符串,因为回文数是具有对称性的,所以比较字符串的第一位和最后一位、第一次位和末尾次位 ······但是由于一位数以及负数和末尾为0的数的特殊性,应该加以判断。

由于对称性,所以考虑字符长度,奇偶数:通过模2判断只需要判断一般就可以了。

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
> class Solution(object):
>
> def isPalindrome(self, x):
> n = str(x)
> print(n)
> m = len(n)
> count = 0
> if m == 1:
> return True
> elif n[0] == "-" or n[m-1] == '0':
> return False
> elif m % 2 == 0:
> for i in range(int(m/2)):
> if n[i] == n[m-1-i]:
> count += 1
> else:
> return False
> else:
> for i in range(int((m+1)/2)):
> if n[i] == n[m-1-i]:
> count += 1
> else:
> return False
> if count == int(m/2) or count == int((m+1)/2):
> return True
>
>
> X = 0
> solution = Solution()
> print(solution.isPalindrome(X))
>

时间复杂度为 O(n)

执行代码,运行时间108 ms