每日一练 — 2022.02.20

一，快乐数

1，程序简介

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

「快乐数」定义为：

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

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

示例 1：

• 输入：19
• 输出：true
• 解释：
  12 + 92 = 82
  82 + 22 = 68
  62 + 82 = 100
  12 + 02 + 02 = 1

示例 2：

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

提示：

• $1<=n<=2^{31}-1$

2，程序代码

# -*- coding: utf-8 -*-
"""
Created on Sun Feb 20 12:31:04 2022
Function: 快乐数
@author: 小梁aixj
"""
class Solution(object):def isHappy(self, n):""":type n: int:rtype: bool"""d = {}while True:l = list(map(int, list(str(n))))m = 0for i in l:m += i ** 2if m in d:print(d)return Falseif m == 1:print(d)return Trued[m] = mn = m

二，单词拆分 II

1，程序简介

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

• 分隔时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

示例 1：

• 输入:
  s = "
  catsanddog
  "
  wordDict =
  [“cat”, “cats”, “and”, “sand”, “dog”]

• 输出:
  [
  “cats and dog”,
  “cat sand dog”
  ]

示例 2：

• 输入:
  s = “pineapplepenapple”
  wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]
• 输出:
  [
  “pine apple pen apple”,
  “pineapple pen apple”,
  “pine applepen apple”
  ]
• 解释: 注意你可以重复使用字典中的单词。

示例 3：

• 输入:
  s = “catsandog”
  wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
• 输出:
  []

2，程序代码

# -*- coding: utf-8 -*-
"""
Created on Sun Feb 20 12:31:37 2022
Function: 单词拆分 II
@author: 小梁aixj
"""
class Solution(object):def dfs(self, low, length, s, res, vaild, path=[]):if low == length:res.append(" ".join(path))returnfor i in range(low, length):if vaild[low][i]:self.dfs(i + 1, length, s, res, vaild, path + [s[low : i + 1]])def wordBreak(self, s, wordDict):""":type s: str:type wordDict: List[str]:rtype: List[str]"""length = len(s)vaild = [[False] * length for _ in range(length)]dp = [False for _ in range(length + 1)]dp[0] = TruewordDict = set(wordDict)for i in range(1, length + 1):for j in range(i + 1):word = s[j:i]if dp[j] and word in wordDict:dp[i] = Truevaild[j][i - 1] = Trueres = []if dp[-1]:self.dfs(0, length, s, res, vaild)return res

三，相交链表

1，程序简介

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

• 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
• 输出：Intersected at ‘8’
• 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
  从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
  在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

• 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
• 输出：Intersected at ‘2’
• 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
  从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
  在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

• 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
• 输出：null
• 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
  由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
  这两个链表不相交，因此返回 null 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• $0<=m,n<=3\ast 10^4$
• $1<=Node.val<=10^5$
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

进阶:

• 你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

2，程序代码

# -*- coding: utf-8 -*-
"""
Created on Sun Feb 20 12:31:50 2022
Function: 相交链表
@author: 小梁aixj
"""
class ListNode:def __init__(self, x):self.val = xself.next = None
class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:if not headA or not headB:return Nonewei_A = []while headA:wei_A.append(headA)headA = headA.nextwei_A = wei_A[::-1]wei_B = []while headB:wei_B.append(headB)headB = headB.nextwei_B = wei_B[::-1]count = -1lA = len(wei_A)lB = len(wei_B)if lA < lB:copy = wei_Bwei_B = wei_Awei_A = copylA, lB = lB, lAfor i in range(lB):if wei_A[i] == wei_B[i]:count += 1else:breakif count != -1:return wei_A[count]else:return None