力扣刷题记录

链表、双指针

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//如果其中一个链表为空，则返回另外一条链if(l1==null){return l2;}if(l2==null){return l1;}//创建两条链ListNode h1 = l1;ListNode h2 = l2;//创建一个虚拟链头ListNode head = new ListNode(-1);ListNode tmpL = head;//定义一个进位数int carry = 0;while(h1!=null||h2!=null){int sum=carry;if(h1!=null){sum+=h1.val;h1 = h1.next;}if(h2!=null){sum+=h2.val;h2 = h2.next;}//计算进位数carry = sum /10;//相加结果int val = sum%10;tmpL.next = new ListNode(val);tmpL = tmpL.next;}//如果有进位，则创建一个新的节点存储if (carry!=0){tmpL.next = new ListNode(carry);}// 返回虚拟头return head.next;}
}

思路：先判断两个链的数据，但凡有一条链为空则返回另外一条链作为相加结果，创建一个虚拟链用于记录相加的结果，遍历两条链，使用双指针指向两条链的节点，记录进位数和相加结果，以此构造新链的数据，最后如果有进位，则创建一个新的节点存储，最后返回指向虚拟链的头节点。

数组、滑动窗口、双指针

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:m = 0  # 用于记录最长不同字串dic = {} # 用于存放字符出现的位置i = -1 # 左指针初始位置for j in range(len(s)): # 逐个遍历字符if s[j] in dic:# 如果说字符重复出现i = max(dic[s[j]],i) # 这里为什么取最大的，因为要确保两个相同字符之间没有相同的字符dic[s[j]] =j # 将字符放入字典中,或者记录字符出现的位置m = max(m,j-i)return m

思路：定义两个指针，一个指针用于指向上次字符出现的位置，一个指针指向最新出现的位置，求两个指针之间的距离，使用字典记录字符和对应位置，出现相同字符的时候就计算位置之差，判断最大距离之差。

数组、逐级递减法

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if not strs:return ""prefix = strs[0]for s in strs[1:]:while not s.startswith(prefix):prefix = prefix[:-1]if not prefix:return ""return prefix

思路：将第一个字符串作为前缀，依次遍历剩下的所有字符，判断是否是以该字符串作为前缀，若出现不以它作为前缀的，则去掉字符串中最后一个字符，重新遍历，以此类推，最后得到的一定是所有字符都包含的前缀。

数组、双指针

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""# 当nums1本身没有元素时，直接替换为nums2if m == 0:nums1[:] = nums2returna, b, c = m-1, n-1, m+n-1# 从后往前合并两个数组while a >= 0 and b >= 0:if nums1[a] >= nums2[b]:nums1[c] = nums1[a]a -= 1else:nums1[c] = nums2[b]b -= 1c -= 1# 处理剩余元素（只有一个数组会有剩余）if b >= 0:nums1[:c+1] = nums2[:b+1]

思路：从后往前双指针，分别取两个数组的最后一个元素，肯定都是最大的，那么取两个之间最大的放数组一的最后面，然后取前面一个做比较，如果数组一先用完，那么数组二里面的肯定是最小的几个，直接放数组一的最前面就行，如果数组二先用完，那么数组一里面的就是最小的几个，不用变，所以最后只需要判断数组二里面的元素是否都用完了。

数组、双指针

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

class Solution:def removeElement(self, nums: List[int], val: int) -> int:# 双指针m = len(nums)n = 0for i in nums:if i !=val:nums[n]=in=n+1return n

思路：遍历每个元素，如果当前元素不是目标值，就把当前元素放在nums[n]的位置，然后n+1，遍历下个元素，跳过当前元素是目标值的，最后前n个元素均不是目标值，而n就是非目标值的元素个数。

数组、双指针

给你一个 非严格递增排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k

class Solution:def removeDuplicates(self, nums: List[int]) -> int:# 双指针，与正确位置的元素比k=0for i in nums[1:]:if i!=nums[k]:k+=1nums[k]=ireturn k+1# 双指针，与前一位置元素比# m=1# for n in range(1,len(nums)):#     if nums[n]!=nums[n-1]:#         nums[m]=nums[n]#         m+=1# return m

思路：遍历数组，使用双指针，p指向第一个元素，q指向第二个元素，对比两个元素，若不同，则p+1，且将P+1指向位置的元素改为q指向的元素，跳过相同项，不管是否相同，操作之后q+1。注：力扣中对于变量名i和k识别较快，同一套代码，将变量名换成m和n，运行时间显著增加。

数组、双指针

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

class Solution:def removeDuplicates(self, nums: List[int]) -> int:if len(nums)<3:return len(nums)i = 0k=0for j in nums[1:]:# 如果和前面一样，且k小于1，记录数量并修改if j==nums[i]:# 数量小于1，直接修改if k<1:i+=1nums[i]=jk+=1# 如果不一样，k清零，直接修改else:k=0i+=1nums[i]=jreturn i+1

我的思路：双指针，一个指针记录数组元素位置，另外一个指针指向遍历序列中的元素，同时定义一个变量记录重复数，遍历元素与p指针元素对比，若一致先判断重复数，重复数小于1则q指针增加，然后修改，不管怎样重复数都+1，可以将重复数理解为步长。如果不一致，k清零，直接修改。

class Solution:def removeDuplicates(self, nums: List[int]) -> int:s = 0 for f in range(len(nums)):if s <2 or nums[f] != nums[s-2]:nums[s] = nums[f]s += 1return s

别人思路：前两个不用比较，直接修改，即使重复也没事，p指针逐个位置增加，q指针指向遍历的元素，拿遍历到的元素和p指针的前面两位的元素比较，不一致则修改p指向的元素，并且p指向下一位，然后q继续遍历，相当于步长为2的元素遍历。

数组、哈希表法

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution:def majorityElement(self, nums: List[int]) -> int:num = {}n=int(len(nums)/2)if n==0:return nums[0]for i in nums:if i in num:num[i]+=1if num[i]>n:return ielse:num[i]=1

我的思路：遍历元素，用字典记录每个元素出现的个数，若元素个数超过n/2直接返回元素。

class Solution:def majorityElement(self, nums: List[int]) -> int:counts = collections.Counter(nums)return max(counts.keys(), key=counts.get)

官解思路：先用计数器生成计数键值对，然后用max函数根据value取最大的返回key，和我的思路一样。

其他方法：

数组排序法:在一个排序后的数组中，多数元素必定出现在数组的中间位置。这是因为题目中明确多数元素的定义是 "出现次数大于⌊n/2⌋的元素"，也就是说它在数组中出现的次数超过一半。当数组排序后，这个元素必然会占据数组的中间位置。
class Solution:def majorityElement(self, nums: List[int]) -> int:nums.sort()return nums[len(nums) // 2] 摩尔投票法（Boyer-Moore Majority Vote Algorithm）的核心思想是票数正负抵消：
设定一个候选元素和一个计数器
遍历数组时，如果遇到与候选元素相同的元素，计数器加 1，否则减 1
当计数器变为 0 时，更换候选元素为当前元素，并将计数器重置为 1
最终剩下的候选元素就是多数元素
class Solution:def majorityElement(self, nums: List[int]) -> int:count = 1candidate = nums[0]for num in nums[1:]:if num == candidate:count += 1else:count -= 1if count == 0:candidate = numcount = 1return candidate