1790. 仅执行一次字符串交换能否使两个字符串相等
2022.10.11 每日一题
题目描述
给你长度相等的两个字符串 s1 和 s2 。一次 字符串交换 操作的步骤如下：选出某个字符串中的两个下标（不必不同），并交换这两个下标所对应的字符。
如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等，返回 true ；否则，返回 false 。
示例 1：
输入：s1 = “bank”, s2 = “kanb”
输出：true
解释：例如，交换 s2 中的第一个和最后一个字符可以得到 “bank”
示例 2：
输入：s1 = “attack”, s2 = “defend”
输出：false
解释：一次字符串交换无法使两个字符串相等
示例 3：
输入：s1 = “kelb”, s2 = “kelb”
输出：true
解释：两个字符串已经相等，所以不需要进行字符串交换
示例 4：
输入：s1 = “abcd”, s2 = “dcba”
输出：false
提示：
1 <= s1.length, s2.length <= 100
s1.length == s2.length
s1 和 s2 仅由小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/check-if-one-string-swap-can-make-strings-equal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
class Solution:
def areAlmostEqual(self, s1: str, s2: str) -> bool:
# 看有几处不同，如果有两处不同且不同的字符一样，那么就可以交换
a1, a2, b1, b2 = '','','',''
count = 0
for i, c in enumerate(s1):
if c != s2[i]:
count += 1
if count == 1:
a1 = c
b1 = s2[i]
elif count == 2:
a2 = c
b2 = s2[i]
elif count > 2:
return False
#print(a1, a2, b1, b2)
if a1 == b2 and a2 == b1:
return True
else:
return False
大佬写的
class Solution:
def areAlmostEqual(self, s1: str, s2: str) -> bool:
z = [*filter(lambda x:x[0]!=x[1],zip(s1,s2))]
return len(z)==2 and z[0]==z[1][::-1] or len(z)==0
817. 链表组件
2022.10.12 每日一题
题目描述
给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。
返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。
示例 1：
输入: head = [0,1,2,3], nums = [0,1,3]
输出: 2
解释: 链表中,0 和 1 是相连接的，且 nums 中不包含 2，所以 [0, 1] 是 nums 的一个组件，同理 [3] 也是一个组件，故返回 2。
示例 2：
输入: head = [0,1,2,3,4], nums = [0,3,1,4]
输出: 2
解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。
提示：
链表中节点数为n
1 <= n <= 10^4
0 <= Node.val < n
Node.val 中所有值 不同
1 <= nums.length <= n
0 <= nums[i] < n
nums 中所有值 不同
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-components
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:
# 也就是说找到在链表中连续存在的值
# 将nums中的数放在set中，然后遍历列表，看是否在set中，
# 如果在，那么就数量加1，如果置0了，那么就res加1
res, count = 0, 0
s = set(nums)
while head:
if head.val in s:
count += 1
if count == 1:
res += 1
else:
count = 0
head = head.next
return res
769. 最多能完成排序的块
2022.10.13 每日一题，昨天帮忙做华为笔试题，有点受挫
题目描述
给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。
返回数组能分成的最多块数量。
示例 1:
输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
示例 2:
输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
提示:
n == arr.length
1 <= n <= 10
0 <= arr[i] < n
arr 中每个元素都 不同
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/max-chunks-to-make-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
其实就是一块数据的最小值和最大值和下标相同，那么就可以划分为一块
class Solution:
def maxChunksToSorted(self, arr: List[int]) -> int:
# 如果是降序的，那就不能拆开
# 才最多有10个数，所以貌似需要暴力解
# 如果一直是上升的，那么就不用管，
# 不行，因为n个数是0到n-1，所以排序后那个数必须对应位置
# 这样的话，遍历这个数组，如果当前最大值等于i，
# 那么说明前i个元素排序后肯定是和最终排序结果相同的
# 那么就可以把前i个元素划分为一块
# 继续往后遍历的过程中，也是这样处理，那么得到的一些中间区段其实也是符合条件的
mmax = -1
count = 0
for i, x in enumerate(arr):
mmax = max(mmax, x)
if i == mmax:
count += 1
return count
class Solution:
def maxChunksToSorted(self, arr: List[int]) -> int:
# 看了单调栈的思路
# 就是什么意思呢，还是找能每个区间的范围，先框定一个范围，
# 然后再遍历使这个范围扩大或者添加新的范围
# 如果遇到更大的值，那么就添加新的区块
# 如果遇到小的值，那么插入原有的区域
stack = []
for a in arr:
# 如果栈为空或者当前元素大于栈顶元素，就加入栈中
if not stack or stack[-1] < a:
stack.append(a)
else:
top = stack[-1]
# 如果栈顶元素大于a，那么就说明a这个元素在更前面，区间需要更新
while stack and stack[-1] > a:
stack.pop()
stack.append(top)
return len(stack)