1. 前言

上述两个题目位于leetcode75中，难度为中等，虽然对于大佬而言，可能很简单，但是对于我而言，可能说还是有一些挑战性的。最后提交效率不怎么高，希望各位谅解。

2. 1657. 确定两个字符串是否接近

标签: 哈希表、字符串、排序
题目如下：
如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：

• 操作 1：交换任意两个 现有 字符。
  例如，abcde -> aecdb
• 操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。
  例如，aacabb -> bbcbaa（所有 a 转化为 b ，而所有的 b 转换为 a ）
  你可以根据需要对任意一个字符串多次使用这两种操作。

给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近 ，就返回 true ；否则，返回 false 。
示例如下：

算法思路(Python)：对于无论多么复杂的word1，如果能通过上述两种操作转换为word2。首先先把word1、word2用两个哈希表map1、map2分别用来统计两个字符串中各个字符的个数。先处理操作1，即遍历map1中的key，如果key也在map2中，且map1[key]==map2[key]，那么说明word1、word2中字符key中个数相同，可以证明的是在word1中字符key无论在字符串word1哪些位置上，都可以通过操作1转换到word2中key对应位置(虽然不知道怎样证明)，记下这些key，遍历完map1之后，删除map1和map2中的这些key。进行完这些操作之后，如果两个哈希表全为空，那么说明word1转换为word2只需操作1即可，返回True。如果两个哈希表中键的个数不相等，直接返回False；如果两个哈希表中键不一一对应，那么也返回False(即如果键a在map1中，那么键a也需在map2中)；(进行操作2)之后将两个哈希表中值得到，用list1、list2分别进行存储，对list1、list2进行排序，然后比较list1、list2中值是否相同，只要其中一个不同，那么False，否则最后返回True。

参考代码如下：

class Solution(object):def closeStrings(self, word1, word2):""":type word1: str:type word2: str:rtype: bool"""m = len(word1)n = len(word2)if m != n:return Falsemap1 = {}map2 = {}for c in word1:map1[c] = map1.get(c,0) + 1for c in word2:map2[c] = map2.get(c,0) + 1arr = []for key in map1:if not map2.get(key,None):return Falseelse:if map2[key] == map1[key]:arr.append(key)for key in arr:map1.pop(key)map2.pop(key)if len(map1.keys()) == 0 and len(map2.keys()) == 0:print('第一种情况')return Trueprint(map1,map2)if len(map1.keys()) != len(map2.keys()):return Falsecount = 0n2=  len(map1.keys())for key in map1:if map2.get(key,None):count += 1if count != n2:return Falselist1 = list(map1.values())list2 = list(map2.values())list1.sort()list2.sort()print(list1,list2)for i in range(n2):if list1[i] != list2[i]:return Falsereturn Truea = Solution()
print(a.closeStrings(word1 = "abbzzca", word2 = "babzzcz"))

运行结果：

3. 1004. 最大连续1的个数 III

标签:双指针、滑动窗口、数组
题目描述如下：
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
示例如下：

算法思路：应用双指针(left、right)、滑动窗口。这一题中，用一个变量count用于统计当前滑动窗口中的0的个数，如果count小于或者等于k，那么此时连续1的最大个数为right-left+1,如果count大于k，(如果nums[left] == 0,count个数减1)，left++。
画出示例1的运行示意图如下：

nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
left=0,right=0,1,count=0,res=1
left=0,right=1,11,count=0,res=2
left=0,right=2,111,count=0,res=3
left=0,right=3,1110,count=1,res=4
left=0,right=4,11100,count=2,res=5
left=1,right=5,11000,count=3,res=5
left=2,right=6,10001,count=3,res=5
left=2,right=6,10001,count=3,res=5
left=3,right=7,00011,count=3,res=5
left=4,right=8,00111,count=2,res=5
left=4,right=9,001111,count=2,res=6
left=4,right=10,0011110,count=3,res=6

黄色部分表示滑动串口窗口中的字符串。
参考代码如下：

class Solution(object):def longestOnes(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""n = len(nums)left,right=0,0count = 0res = -1while left < n and right < n:if count > k:if nums[left] == 0:count -= 1left += 1if nums[right] == 0:count += 1if count <= k:res = max(res,right-left)right += 1return res + 1a = Solution()
print(a.longestOnes([1,1,1,0,0,0,1,1,1,1,0],2))

运行结果：

4. 总结

总的来说，题目还算简单(想明白的话，哈哈！)，至于效率不怎么高，和使用编程语言和提交代码时间段还是有一定关联的。