Leetcode

领扣–引领新时尚

1. 两数之和问题

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

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

示例:

给定 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–较优化算法

思路：

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

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

具体实现：

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的值。

具体实现：

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:

输入: 121
输出: true

示例 2:

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

示例 3:

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

解法1–较优化解法

思路：

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

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

实现：

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

3. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [0]
输出：0

示例 4：

输入：nums = [-1]
输出：-1

思路：

给定一个数组，对其进行遍历，用两个变量，其中一个用来存储最大的和，一个用来记录当前的和。
代码如下

class Solution:
    def maxSubArray(nums):
        sums = nums[0]
        maxs = nums[0]
        for i in range(1, len(nums)):
            if sums > 0:
                sums += nums[i]
            else:
                sums = nums[i]
            maxs = sums if sums > maxs else maxs
        return maxs

nums = [-1, 2, -1, 3, -2]
print(Solution.maxSubArray(nums))

4. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

思路
解法1：位运算
使用抑或运算XOR来解答较为简单，对数组的元素进行抑或运算，相同为1，不同为0，即可判断只出现呢一次的数字了。
代码实现

# 位运算xor
from functools import reduce
class Solution:
    def singleNumber(snums):
        return reduce(lambda x, y: x^y, nums)

resfun = Solution
nums = [1, 1, 2, 2, 4, 4, 5]
print(resfun.singleNumber(nums))

解法2：通用解法
对于数组中的元素进行次数计算，如果有出现一次的即可返回结果。
代码实现

class Solution:
    def singleNumber(nums):
        for i in nums:
            c = nums.count(i)
            if c == 1:
                return i

nums = [1, 1, 2, 3, 2]
print(Solution.singleNumber(nums))

注：count函数计算你次数，因为数组中只存在一个出现次数为1的，所以只要返回值为1，即可得到该元素。

Leetcode

1. 两数之和问题

2. 回文数问题

3. 最大子序和

4. 只出现一次的数字

谢谢老板~