刷题记录与思考

双指针

001-两数之和/167. 两数之和 II - 输入有序数组

一者遍历，一者通过hash表(字典数据)，hash表所花时间反而更长？

# 28ms                
class Solution(object):
    def twoSum(self, nums, target):
        dic = dict()
        for i, num in enumerate(nums):
            if target - num in dic:
                return [dic[target - num], i]
            dic[nums[i]] = i
        return []             

167-两数之和 II - 输入有序数组

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例 1：

输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        L, R = 0, len(numbers)-1
        while L < R:
            if numbers[L] + numbers[R] == target:
                return [L+1, R+1]
            elif numbers[L] + numbers[R] > target:
                R -= 1
            else:
                L += 1

415-字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

提示：

num1 和num2 的长度都小于 5100 num1 和num2 都只包含数字 0-9 num1 和num2 都不包含任何前导零 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式

大数相加：

class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        # 返回值，是否有进位，从个位数开始计算
        res, carry, i, j = '', 0, len(num1)-1, len(num2)-1

        while 0<=i or 0<=j:
            n1 = int(num1[i]) if 0<=i else 0
            n2 = int(num2[j]) if 0<=j else 0
            res = str((n1+n2+carry)%10) + res	# 计算相加后个位值
            carry = (n1+n2+carry)//10			# 判断是否有进位
            i -= 1	# 两指针依次移动
            j -= 1
        return '1'+res if carry else res

2-两数相加/面试题 02.05. 链表求和

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

<img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/02/addtwonumber1.jpg" alt="img" style="zoom:67%;" />

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

与上一题一样：

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        res, carry = ListNode(), 0
        tmp = res
        while l1 or l2:
            n1 = l1.val if l1 else 0
            n2 = l2.val if l2 else 0
            tmp.next = ListNode((n1+n2+carry)%10)
            carry = (n1+n2+carry)//10
            tmp = tmp.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next

        if carry: tmp.next = ListNode(carry)
        return res.next

NC40 两个链表生成相加链表

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

输入：

[9,3,7],[6,3]

返回值：

{1,0,0,0}

与上一题一样，只是正向表示数值，用列表存储数值，后正常计算，再反向输出：

class Solution:
    def addInList(self , head1 , head2 ):
        # write code here
        l1, l2, carry, res, ans = [], [], 0, [], ListNode(0)
        while head1:
            l1.append(head1.val)
            head1 = head1.next
        while head2:
            l2.append(head2.val)
            head2 = head2.next
        
        while l1 or l2:
            n1 = l1.pop() if l1 else 0
            n2 = l2.pop() if l2 else 0
            res.append((n1+n2+carry)%10)
            carry = (n1+n2+carry)//10
        if carry: res.append(carry)
        tmp = ans
        while res:
            tmp.next = ListNode(res.pop())
            tmp = tmp.next
        return ans.next

43-字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3" 输出: "6" 示例 2:

输入: num1 = "123", num2 = "456" 输出: "56088" 说明：

• num1 和 num2 的长度小于110。
• num1 和 num2 只包含数字 0-9。
• num1 和 num2 均不以零开头，除非是数字 0 本身。
• 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

'''
num1的第i位(高位从0开始)和num2的第j位相乘的结果在乘积中的位置是[i+j, i+j+1]
例: 123 * 45,  123的第1位 2 和45的第0位 4 乘积 08 存放在结果的第[1, 2]位中
          index:    0 1 2 3 4  
              
                        1 2 3
                    *     4 5
                    ---------
                          1 5
                        1 0
                      0 5
                    ---------
                      0 6 1 5
                        1 2
                      0 8
                    0 4
                    ---------
                    0 5 5 3 5
        这样我们就可以单独都对每一位进行相乘计算把结果存入相应的index中 
'''

class Solution(object):
    def multiply(self, num1, num2):
        res = 0
        for i in range(1,len(num1)+1):
            for j in range(1, len(num2)+1):
                res += int(num1[-i]) * int(num2[-j]) *10**(i+j-2)
        return str(res)
    
class Solution(object):
    def multiply(self, num1, num2):
        num1_len = len(num1)
        num2_len = len(num2)
        res = [0] * (num1_len + num2_len)
        for i in range(num1_len-1, -1, -1):
            for j in range(num2_len-1, -1, -1):
                tmp = int(num1[i]) * int(num2[j]) + int(res[i+j+1])
                res[i+j+1] = tmp%10 # 余数作为当前位
                res[i+j] = res[i+j] + tmp//10 # 前一位加上，进位（商作为进位）
        res = list(map(str, res))

        for i in range(num1_len+num2_len):
            if res[i]!='0': # 找到第一个非0数字，后面就是结果
                return ''.join(res[i:])
        return '0'

989-数组形式的整数加法

对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。

给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。

示例 1：

输入：A = [1,2,0,0], K = 34 输出：[1,2,3,4] 解释：1200 + 34 = 1234

class Solution(object):
    def addToArrayForm(self, num, k):
        """
        :type num: List[int]
        :type k: int
        :rtype: List[int]
        """
        res= 0
        for it in num:
            res = 10*res+it
        res += k
        return [int(it) for it in str(res)]
    
class Solution:
    def addToArrayForm(self, A, K):
        return list(map(int, str(int(''.join(map(str, A)))+K)))

75-颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]

# 最简单为sort
class Solution(object):
    def sortColors(self, nums):
        return nums.sort()

双指针:

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        start, end, i = 0, len(nums)-1, 0
        while i <= end:
            if nums[i] == 0:	# 为0时，与前端交换
                nums[i], nums[start] = nums[start], 0
                start += 1
            elif nums[i] == 2:	# 为2时，与末端交换
                nums[i], nums[end] = nums[end], 2
                end -= 1
                i -= 1
            i += 1
        return nums

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        start, end, i = 0, len(nums)-1, 0
        while i <= end:
            if nums[i]%2 == 1:	# 为0时，与前端交换
                nums[i], nums[start] = nums[start], nums[i]
                start += 1
            elif nums[i]%2 == 0:	# 为2时，与末端交换
                nums[i], nums[end] = nums[end], nums[i]
                end -= 1
                i -= 1
            i += 1
        return nums

283-移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明:

必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。

如上题：

class Solution:
    def moveZeroes(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        end, i = len(nums)-1, 0
        while i <= end:
            if nums[i] == 0:
                nums.pop(i)
                nums.append(0)
                end -= 1
                i -= 1
            i += 1
        return nums

560-和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

前缀和思想：求数列的和时，Sn = a1+a2+a3+...an; 此时Sn就是数列的前n项和。例S5 = a1 + a2 + a3 + a4 + a5; S2 = a1 + a2，即可以通过 S5-S2 得到 a3+a4+a5 的值。

# 字典数存储，并优化
class Solution(object):
    def subarraySum(self, nums, k):
        Sum, res, cul = 0, 0, {}
        cul[0] = 1
        for i in range(len(nums)):
            Sum += nums[i]
            if Sum - k in cul: # 查找k的倍数，如果存在，加1,
                res += cul[Sum-k]
            if Sum not in cul: # 保存前缀和
                cul[Sum] = 0
            cul[Sum] += 1
        return res 

为什么我们只要查看是否含有 presum - k ，并获取到presum - k 出现的次数就行呢？见下图，所以我们完全可以通过 presum - k的个数获得 k 的个数

<img src="https://pic.leetcode-cn.com/1610773274-xuuVxS-file_1610773273681" alt="微信截图_20210115194113" style="zoom:50%;" />

325-和等于 k 的最长子数组长度

给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长子数组长度。如果不存在任意一个符合要求的子数组，则