代码编织梦想

454.四数相加II

给你四个整数数组nums1、nums2、nums3和nums4 ,数组长度都是n ,请你计算有多少个元组(i, j, k, l)能满足:
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例1:
输入:nums1 = [1, 2], nums2 = [-2, -1], nums3 = [-1, 2], nums4 = [0, 2]
输出:2
解释:两个元组如下:
1.(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2.(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例2:
输入:nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出:1
class Solution:
    def fourSumCount(self, nums1: int, nums2: int, nums3: int, nums4: int) -> int:
        dict_num1 = {}
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                tmp = nums1[i] + nums2[j]
                if tmp not in dict_num1:
                    dict_num1[tmp] = [[i,j]]
                else:
                    dict_num1[tmp].append([i,j])
        dict_num2 = {}
        for i in range(len(nums3)):
            for j in range(len(nums4)):
                tmp = nums3[i] + nums4[j]
                if tmp not in dict_num2:
                    dict_num2[tmp] = [[i,j]]
                else:
                    dict_num2[tmp].append([i,j])
        res = 0
        for i in dict_num1:
            for j in dict_num2:
                if i + j == 0:
                    li = len(dict_num1[i])
                    lj = len(dict_num2[j])
                    tmp = li * lj
                    res += tmp
        return res

if __name__ == '__main__':
    nums1 = [1, 2]
    nums2 = [-2, -1]
    nums3 = [-1, 2]
    nums4 = [0, 2]
    tmp = Solution()
    res = tmp.fourSumCount(nums1,nums2,nums3,nums4)
    print(res)

看了一下解法,因为只需要求计数,所以可以直接count计数,这样可以少循环一次。

383.赎金信

给你两个字符串:ransomNote和magazine ,判断ransomNote能不能由magazine里面的字符构成。
如果可以,返回true ;否则返回false 。
magazine中的每个字符只能在ransomNote中使用一次。

示例1:
输入:ransomNote = "a", magazine = "b"
输出:false

示例2:
输入:ransomNote = "aa", magazine = "ab"
输出:false

示例3:
输入:ransomNote = "aa", magazine = "aab"
输出:true

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        dic = {}
        for i in ransomNote:
            if i not in dic:
                dic[i] = 1
            else:
                dic[i] += 1
        dic_mag = {}
        for j in magazine:
            if j not in dic_mag:
                dic_mag[j] = 1
            else:
                dic_mag[j] += 1
        for k, v in dic.items():
            tmp = dic_mag.get(k)
            if tmp is None or v > tmp:
                return False
        return True

if __name__ == '__main__':
    ransomNote = "aa"
    magazine = "aab"
    tmp = Solution()
    res = tmp.canConstruct(ransomNote,magazine)
    print(res)

看了一下随想录,发现python有四种解法, 麻了

15.三数之和

给你一个整数数组nums ,判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且
j != k ,同时还满足nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为0且不重复的三元组。
注意:答案中不可以包含重复的三元组。

示例1:
输入:nums = [-1, 0, 1, 2, -1, -4]
输出:[[-1, -1, 2], [-1, 0, 1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是[-1, 0, 1]和[-1, -1, 2] 。
注意,输出的顺序和三元组的顺序并不重要。

示例2:
输入:nums = [0, 1, 1]
输出:[]
解释:唯一可能的三元组和不为0 。

示例3:
输入:nums = [0, 0, 0]
输出:[[0, 0, 0]]
解释:唯一可能的三元组和为0

class Solution:
    def threeSum(self, nums):
        long = len(nums)
        res = []
        nums.sort()
        for i in range(long):
            if i == long - 2:
                break
            left = i + 1
            right = long - 1
            while left < right:
                if nums[i] + nums[left] + nums[right] > 0:
                    right -= 1
                elif nums[i] + nums[left] + nums[right] < 0:
                    left += 1
                else:
                    tmp = [nums[i], nums[left], nums[right]]
                    tmp.sort()
                    if tmp not in res:
                        res.append(tmp)
                    left += 1

        return res

if __name__ == '__main__':
    nums = [-1, 0, 1, 2, -1, -4]
    nums = [0, 1, 1]
    nums = [0, 0, 0,0]
    nums = [-2, 0, 1, 1, 2]
    tmp = Solution()
    res = tmp.threeSum(nums)
    print(res)

18. 四数之和

给你一个由n个整数组成的数组nums ,和一个目标值target 。请你找出并返回满足下述全部条件且不重复的四元
组[nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a、b、c和d互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案 。


示例1:
输入:nums = [1, 0, -1, 0, -2, 2], target = 0
输出:[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

示例2:
输入:nums = [2, 2, 2, 2, 2], target = 8
输出:[[2, 2, 2, 2]]
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]: continue
            for k in range(i+1, n):
                if k > i + 1 and nums[k] == nums[k-1]: continue
                p = k + 1
                q = n - 1

                while p < q:
                    if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
                    elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
                    else:
                        res.append([nums[i], nums[k], nums[p], nums[q]])
                        while p < q and nums[p] == nums[p + 1]: p += 1
                        while p < q and nums[q] == nums[q - 1]: q -= 1
                        p += 1
                        q -= 1
        return res

第四题需要再看看,压力好大啊,这个节奏真的快

感觉现在每天睡眠质量严重不足啊

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qyy123ise/article/details/127992898

代码随想录算法训练营第七天|454.四数相加Ⅱ、383.赎金信、15.三数之和、18.四数之和_chauncey1995的博客-爱代码爱编程

代码随想录算法训练营第七天|454.四数相加Ⅱ、383.赎金信、15.三数之和、18.四数之和 454.四数相加Ⅱ思路 383.赎金信思路 15.三数之和思路 18.四数之和思路 4

训练营0927|哈希表系列(四数相加|赎金信|三数之和|四数之和)_chrison_mu的博客-爱代码爱编程

  目录  *454.四数相加II 383.赎金信 15.三数之和 *18.四数之和 *454.四数相加II  四个数组里面寻找四个数相加和为0.巧妙的去利用hashmap判断是否存在的功能,hashmap1里面放前两个数组的和,以及这个和出现的次数 hashmap2里面放后两个数组的和(或者和的相反数)----->判断是否存在于h

【代码随想录算法训练营】d7 454.四数相加 383.赎金信 15. 三数之和 18. 四数之和_浅夏、的博客-爱代码爱编程

今日题目: 454.四数相加 383.赎金信 15. 三数之和 18. 四数之和 解题思想: 数组分组,巧用哈希表 454题四数相加,哈希表的经典题目,因为需要判断某个元素是否在表中出现过,所以自然想到哈

【代码随想录训练营】day7-哈希表_koffer-debug的博客-爱代码爱编程

代码随想录 Day7 今日任务 454.四数相加Ⅱ 383.赎金信 15.三数之和 18.四数之和 454. 四数相加Ⅱ 考点:哈希表 链接:https://leetcode.cn/problems/4sum-ii/

代码随想录算法训练营第七天|454.四数相加ii,383. 赎金信,15. 三数之和,18. 四数之和_小葱抹抹酱的博客-爱代码爱编程

代码随想录算法训练营第七天 454.四数相加II383.赎金信15.三数之和18.四数之和 454.四数相加II 给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请

代码随想录算法训练营第七天|454.四数相加ii,383.赎金信,15.三数之和,18.四数之和,总结_扭一扭.的博客-爱代码爱编程

454.四数相加II 力扣 class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { int count = 0; int sum; Map<Integer,

代码随想录算法训练营第五天|“巨燃”哈希表,本源双指针_code自留地的博客-爱代码爱编程

哈希表 哈希表总的来说有三种方式实现: 数组:适用于元素范围相对较小或者元素连续的情况链表 + 哈希函数:我习惯的是拉链法,对于给定的值,我们的目的是将其存储到相对范围较小的hash槽中。对此我们可以设计出一个哈希函数,

11.20二叉树基础题型_小白孙在路上的博客-爱代码爱编程

一.二叉树的存储 1.存储结构 存储结构:顺序存储或者是类似于链表的链式存储 二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有二叉和三叉表示方式 // 孩子表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树 Node right; /

代码随想录刷题|leetcode 343. 整数拆分 96.不同的二叉搜索树_symdunstaz的博客-爱代码爱编程

目录 343. 整数拆分 思路 整数拆分 96.不同的二叉搜索树 思路 不同的二叉搜索树 343. 整数拆分 题目链接:力扣 思路         动态规划的题目虽然说是要先确定dp数组的含义,再确定递归公式,但是总感觉这两者是相辅相成的,是一起出来的,但是到此,dp数组代表的都是我们要求取