一、242. 有效的字母异位词
1.1题目
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram" 输出: true
示例 2:
输入: s = "rat", t = "car" 输出: false
1.2思路分析
方法1：传统方法
将字符串转换为字符数组，然后分别对两个数组进行排序，然后在调用equals方法进行比较；
方法2：哈希表
因为题目的需求是找"是否存在"的问题，因此可以考虑使用哈希表，对两个字符串中的字符作为数组的下表，其出现的频次作为数组的值，然后根据出现的频次就可以判断两个字符串是否相等。
1.3代码实现
方法1暴力求解
class Solution {
public boolean isAnagram(String s, String t) {
// 注意字符串数组在获取数组长度时调用length（）
int length1 = s.length();
int length2 = t.length();
if(length1 != length2){
return false;
}
// 调用toCharArray()方法将字符串转换为字符数组
char[] s1 = s.toCharArray();
char[] s2 = t.toCharArray();
// 调用Array.sort()方法对数组进行排序
Arrays.sort(s1);
Arrays.sort(s2);
// 使用Arrays.equals()方法对数组中的值进行比较
return Arrays.equals(s1,s2);
}
} 方法2哈希表
class Solution {
public boolean isAnagram(String s, String t) {
// 使用哈希表对字符串中的每个字符出现的频次进行统计
// 定义一个新数组
if (s.length() != t.length()) {
return false;
}
// 因为result中每个值存的是对应的字符出现的频次因此，其长度定义为26
int[] result = new int[26];
// 对字符串中的字符出现的频次进行统计
for (int i = 0; i < s.length(); i++) {
result[s.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
result[t.charAt(i) - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (result[i] != 0) {
return false;
}
}
return true;
}
} 二、349. 两个数组的交集
2.1题目
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的
2.2思路分析
该题也可以转化为是否存在问题，即当两个数组中存在相同值时，此时则可以理解为两个数组存在交集；但是输出中要求不能出现冗余，因此考虑使用HashSet。
2.3代码实现
首先判断这两个数组中是否有值，若没有值，直接返回一个空数组，然后定义两个集合，一个用于存放待判断的数组，另一个存放最后的结果，最后再将集合转化为数组返回。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
// 判断nums1与nums2中是否有值
if(nums1.length == 0 ||nums2.length== 0 || nums2 ==null ||nums1 == null){
return new int[0];
}
// 因为数组中有重复的值，因此我们使用 HashSet对数组去重
HashSet set1 = new HashSet<>();
// 定义一个结果hashset
HashSet result = new HashSet<>();
for(int i:nums1){
// 将nums1中的数值添加到set1中并去重
set1.add(i);
}
for(int i:nums2){
if(set1.contains(i)){
result.add(i);
}
}
// int [] arr = new int[result.]
return result.stream().mapToInt(x->x).toArray();
}
} 三、202. 快乐数
3.1题目
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
示例 2：
输入：n = 2 输出：false
3.2思路分析
该题的难点在于如何判断是否进入死循环，那么什么时候迭代过程会进入死循环呢，即当当前的数值在以往的迭代过程中出现过，因此该题同样可以考虑使用HashSet。
3.3代码实现
首先定义一个求和的函数；然后再根据条件迭代即可，注意：(n % 10)*(n % 10)取模的平方时需要对其带括号。
class Solution { public boolean isHappy(int n) { // 先判断该数是不是1，若是1则直接返回 if(n == 1){ return true; } // 需要判断该数是否为无限循环即存在过问题，因此可以定义一个哈希表 // 返回值是无须的因此可以使用unordered_setset(c++) 或直接使用set HashSet set1 =new HashSet <>(); //循环的条件为 判断值是否存在于hashset中且 n !=1 while(n != 1 && !set1.contains(n)){ set1.add(n); n = addsum(n); } return n == 1; } // 对n的各个位置进行平方求和 public int addsum(int n){ int temp = 0; while(n > 0){ // int res = n % 10; temp += (n % 10)*(n % 10); n = n/10; } return temp; } } 四、1. 两数之和
4.1题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
4.2思路分析
方法1：暴力求解
使用两次for循环来遍历求解
方法2：哈希表
我们可以将题目转化为寻找target-nums[1]的值是否在nums中存在的问题，又因为题目最后的返回值需要满足条件的下标，因此可以考虑使用HashMap，我们将数组中的值作为HashMap中的key，值的下标作为HashMap中的value。
4.3代码实现
方法1暴力求解
class Solution { public int[] twoSum(int[] nums, int target) { int temp = 0; // int [] k = new int[2] ; for(int i = 0; i方法2哈希表
class Solution { public int[] twoSum(int[] nums, int target) { // 因为hashmap是键值对所以其泛型的返回值由两个，并且俩个的返回类型都是Integer HashMap五、24. 两两交换链表中的节点
5.1题目
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
5.2思路分析
定义变量对链表中的节点进行交换，该题的难点在于理清楚链表的下一个节点的具体指向。
交换后：
5.3代码实现
/** * 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 swapPairs(ListNode head) { ListNode dummpy = new ListNode (-1, head); ListNode cur = dummpy; // 定义一个中间节点用于链表交换 ListNode temp1; ListNode temp2; ListNode temp3;//用于存放交换完后连接的下一个节点 while(cur.next != null && cur.next.next != null){ temp1 = cur.next; temp2 = cur.next.next; temp3 = cur.next.next.next; cur.next = temp2; temp2.next = temp1; temp1.next = temp3; cur = cur.next.next; } return dummpy.next; } }六、19. 删除链表的倒数第 N 个结点
6.1题目
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1]
6.2思路分析
定义快慢指针，让快指针先走n+1步，慢指针再走，这样就可以保证慢指针最后停留到待删除指针的前一个指针。
6.3代码实现
可以定义虚拟头指针来简化判断过程
/** * 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 removeNthFromEnd(ListNode head, int n) { ListNode dummpy = new ListNode(-1,head); // 定义虚拟头节点来处理删除头节点的情况 // 定义快慢指针求解 ListNode fast = dummpy; ListNode slow = dummpy; // 快指针走n+1步 for(int i = 0; i<=n ; i++){ fast = fast.next; } // 当快指针不为空 while(fast != null){ fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return dummpy.next; } }七、160. 相交链表
7.1题目
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
- intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
- listA - 第一个链表
- listB - 第二个链表
- skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
- skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at '2' 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [1,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 。
7.2思路分析
该题需注意当两个链表相交时需满足两个指针完全相同，而不是值相同。
7.3代码实现
首先求出两个链表各自的长度，然后求出两个链表长度的差值，并将较长链表的指针移动到与较短链表的指针末尾对其位置。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 第一步求链表A和链表B的长度 ListNode cur1 = headA; ListNode cur2 = headB; int lenA = 0; int LenB = 0; int gap = 0; while(cur1 != null){ cur1 = cur1.next; lenA ++; } while(cur2 !=null){ cur2 = cur2.next; LenB++; } cur1 = headA; cur2 = headB; ListNode temp; int tempLen = 0; gap = lenA > LenB ? (lenA-LenB):(LenB-lenA); // int tempgap = gap; // 确保A为较长链表 if(LenB > lenA){ temp = cur2; cur2 = cur1; cur1 = temp; tempLen = LenB; LenB = lenA; lenA = tempLen; } while(gap>0){ cur1 = cur1.next; gap--; } while(cur1!=null && cur2 != null){ if(cur1 == cur2){ return cur1; } cur1 = cur1.next; cur2 = cur2.next; } return null; } }八、142. 环形链表 II
8.1题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
8.2思路分析
第一步：判断链表中是否有环
定义快慢指针，让快指针以比慢指针快2倍的速度移动，若快指针可以和慢指针相遇则证明该链表有环。
第二步：找到初始相遇的节点。
假设头节点到初始相遇节点的长度为x，环入口节点到相遇节点的长度为y，相遇节点到换入口的长度为z。
则我们根据快慢指针的移动速度可以列入下表达式：
；进一步化简得
;而
，我们取个极限情况，即n=1时，此时
。因此我们可以进一步定义两个指针，一个指针由头指针开始向后运动，另一个指针由相遇位置开始移动，当两个新定义得指针再次相遇时，此时得相遇点则为快慢指针得初始相遇点。
8.3代码实现
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { // 使用快慢指针，快指针以2倍速的方式取去追赶慢指针，当快指针等于慢指针时 // 说明此时有环 ListNode fast = head; ListNode slow = head; // 因为快指针一次走两步因此需要判断fast.next是否为空，若不为空则继续循环 while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; if(slow == fast){ ListNode index1 = head; ListNode index2 = fast; while(index1 != index2){ index1 = index1.next; index2 = index2.next; } return index1; } } return null; } }