242.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true

示例 2: 输入: s = “rat”, t = “car” 输出: false

说明: 你可以假设字符串只包含小写字母。

思路：

  • 原假设中只包含26个字母，使用数组来记录s中字母出现的次数
  • 对t字符串进行遍历，由此对数组值来进行减操作
  • 判断数组值是否全为0，若是则s与t为字母异位符

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def isAnagram( s, t):
        record=[0]*26
        for i in s:
            record[ord(i)-ord('a')]+=1
        for j in t:
            record[ord(j)-ord('a')]-=1
        for k in record:
            if k!=0:
                return False
        return True


a=Solution
print(a.isAnagram('aaabbbcdf','cdfaabab'))

383. 赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true

思路：

  • 和字母异位符类似，用26长度的数组来存储magazine里面的字符出现的次数

  • 对ransom字符串进行遍历，由此对数组值来进行减操作

  • 判断数组值是否出现负数，如果出现负数则不构成

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def canConstruct(ransomNote, magazine):
        record=[0]*26
        for i in ransomNote:
            record[ord(i)-ord('a')]+=1
        for j in magazine:
            record[ord(j)-ord('a')]-=1
        for k in record:
            if k<0:
                return False
        return True

a=Solution
print(a.canConstruct('aaabbbcdf','cdfaabab'))

49.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

1
2
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

1
2
输入: strs = [""]
输出: [[""]]

示例 3:

1
2
输入: strs = ["a"]
输出: [["a"]]

思路：

测试案例：[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

使用record字典来记录strs中的各个元素是否被分组，初始值设置为-1表示都没被分组

遍历strs数组，如果record键值对应的为-1表明没有分组，进行操作

往后遍历，进行字母异位符对比，当为字母异位符时，对其修改键值为index结果为{‘eat’: 0, ‘tea’: 0, ‘tan’: 2, ‘ate’: 0, ‘nat’: 2, ‘bat’: 5}

对record进行提取，拥有相同的键值存为一个数组，结果为[[‘eat’, ‘tea’, ‘ate’], [‘tan’, ‘nat’], [‘bat’]]

代码：

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
32
33
34
class Solution(object):
    def groupAnagrams( strs):
        record={}
        for i in strs:
            record[i]=-1
        for index,j in enumerate(strs):
            if record[j]==-1:
                record[j]=index
                for k in range(index+1,len(strs)):
                    flag=0
                    jilu = [0] * 26
                    for n in strs[index]:
                        jilu[ord(n)-ord('a')]+=1
                    for m in strs[k]:
                        jilu[ord(m)-ord('a')]-=1
                    for a in jilu:
                        if a!=0:
                            flag=1
                            break
                    if not flag:
                        record[strs[k]]=index
        result=[]
        for j in record:
            tmp=[]
            aaa=record[j]
            for k in record:
                if record[k]==aaa and record[k]!=-2:
                    tmp.append(k)
                    record[k]=-2
            if len(tmp)!=0:
                result.append(tmp)
        return result
a=Solution
print(a.groupAnagrams(["a"]))

438.找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

1
2
3
4
5
6
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

思路：

采用窗口的思想，每个窗口的大小为len(p)，判断该窗口大小的字符串是否和p为字母异位符

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def findAnagrams( s, p):
        lenp=len(p)
        result=[]

        lists=list(s)
        listp=list(p)
        record=[0]*26
        for j in p:
            record[ord(j)-ord('a')]+=1
        for slow in range(len(s)-lenp+1):
            flag=0
            tmprecord=record[:]
            for i in range(lenp):
                tmprecord[ord(lists[slow+i])-ord('a')]-=1
            for k in tmprecord:
                if k!=0:
                    flag=1
                    break
            if flag==0:
                result.append(slow)
        return result

349.两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

1
2
3
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

思路：

使用字典来存储nums1数组出现的元素，用键值1来标记是否出现

遍历nums2，判断nums2中的元素是否出现在字典中，如果出现，键值标记为0，防止继续统计

代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def intersection(nums1, nums2):
        dict1={}
        result=[]
        for i in nums1:
            dict1[i]=1
        for j in nums2:
            if  j in dict1.keys() and dict1[j]==1:
                result.append(j)
                dict1[j]=0
        return result

350.两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

1
2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

思路：

与上一题的区别是最终结果考虑到交集的次数

由此字典中键值需要根据次数来增加

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def intersect( nums1, nums2):
        dict1 = {}
        result = []
        for i in nums1:
            if i in dict1.keys():
                dict1[i]+=1
            else:
                dict1[i] = 1
        for j in nums2:
            if j in dict1.keys() and dict1[j] >= 1:
                result.append(j)
                dict1[j] -= 1
        return result

202.快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

1
2
3
4
5
6
7
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

1
2
输入：n = 2
输出：false

思路：

需要定义一个函数来计算一个数各个位的平方和

用一个集合来存储所计算的平方和，如果集合中有重复数据，那么计算结果是无限的，返回false

如果结果为1返回true

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def isHappy( n):
        def calcul(n):
            sum_=0
            while n:
                sum_+=(n%10)**2
                n=n//10
            return sum_
        record=set()
        while True:
            n=calcul(n)
            if n==1:
                return True
            if n in record:
                return False
            else:
                record.add(n)

1.两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

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

思路：

用字典来记录元素以及所对应的下标

判断target-value是否出现在字典中如果出现，返回下标

如果没有出现，存储value值与下标

1
2
3
4
5
6
7
8
9
class Solution(object):
    def twoSum( nums, target):
        record={}
        for index,value in enumerate(nums):
            if target-value in record.keys():
                return [record[target-value],index]
            else:
                record[value]=index
        return []

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：

1
2
3
4
5
6
输入：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：

1
2
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

思路：

  • 这边的四数相加跟两数相加差不多
  • 将四数切分为2+2的组合 就是两数相加

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def fourSumCount( nums1, nums2, nums3, nums4):
        record={}
        result=0
        for i in nums1:
            for j in nums2:
                if i + j in record:
                    record[i+j]+=1
                else:
                    record[i+j]=1
        for m in nums3:
            for n in nums4:
                if -(n+m) in record.keys():
                    result+=record[-n-m]
        return result

15.三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

1
2
3
4
5
6
7
8
输入：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：

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

示例 3：

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

思路：

  • 首先需要对该数组进行排序

  • 这个主要考虑双指针的解法

  • 同时注意去重的问题 left和right可以归为一类

  • slow要单独考虑

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
class Solution(object):
    def threeSum( nums):
        record=[]
        nums=sorted(nums)

        for slow in range(len(nums)-2):

            if slow>=1 and nums[slow]==nums[slow-1]:
                continue

            left=slow+1
            right=len(nums)-1
            while left<right:

                sum = nums[slow] + nums[left] + nums[right]
                if sum<0:
                    left+=1
                    continue
                elif sum>0:
                    right-=1
                    continue
                else:
                    record.append([nums[slow],nums[left],nums[right]])
                    while left != right and nums[left] == nums[left + 1]:
                        left += 1
                    while left != right and nums[right] == nums[right - 1]:
                        right -= 1
                    left+=1
                    right-=1
        return record

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：

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

示例 2：

1
2
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

思路：

  • 四数之和相比于三数之和
  • 多套了一层for循环
  • 多加了一次去重

代码：

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
class Solution:
    def fourSum(self, nums, target):
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]: continue  # 对nums[i]去重
            for k in range(i + 1, n):
                if k > i + 1 and nums[k] == nums[k - 1]: continue  # 对nums[k]去重
                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]])
                        # 对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