刷题笔记
链表¶
203. 移除链表元素 - 力扣（LeetCode）¶
- 非递归解法
-
```Java /**
- 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 removeElements(ListNode head, int val) {
// 删除头节点
while(head != null && head.val == val){
// 当head的值相匹配的时候，head就会被更新，头节点就会被改动
// 当head的值不匹配的时候，head停止更新，则不执行该while循环，不再对头节点进行更新
head = head.next; // head = head.next head代表头节点指针，head.next代表头节点的下一个指针 // 使用头节点指针指向头节点的下一个节点，则原头节点被next节点的内容覆盖 } // 如果删除的不是头节点 ListNode temp = head; // 对象引用 // 如果修改的是val,那么这两个都会发生变化 // 如果是类似 temp = temp.next 那么不会影响head，因为修改的是temp的引用，此时temp指向了temp.next曾指向的内存区域 while(temp != null && temp.next != null){ // if(temp.val == val){ // temp = temp.next // 实现的是相邻替换 // } // 上述已经在前面的头节点处理了 if(temp.next.val == val){ // 判断头节点的子节点 temp.next = temp.next.next; // 这是用于更新新的链表 }else{ temp = temp.next; // 这个引用的改变只是用于移动 } // 上述两个引用的改变本质都是用于移动，假设 A B C D的顺序 // 如果A = head A = B , B = C , C = D,D = NULL，那么head得到的还是A B C D的顺序结果 // 如果A = head A = B B = D, D = null， 那么head得到的就是A B D的结果 } return head;} }
- 递归解法 -Python /** * 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 removeElements(ListNode head, int val) { if(head == null) // 如果链表为空（head==null），返回null return null; // 考虑当前节点和剩余链表（即head.next） if(head.val == val){ // 如果当前节点head的值等于val // 那么跳过当前节点，直接返回对head.next递归的结果（即相当于删除了当前节点） head = removeElements(head.next,val); }else{ // 否则，保留当前节点，但将当前节点的next指针指向对head.next递归后的结果 head.next = removeElements(head.next,val); } return head; } } // head和head.next都是一种指针，head指向当前的内存空间，head.next即当前内存空间的指针指向的下一个内存空间 ```
-
JSON 初始链表： ┌───┐ ┌───┐ ┌───┐ │ 1 │──►│ 2 │──►│ 3 │──► null └───┘ └───┘ └───┘ 假设 val = 2 第一次进入方法： head == 1 != 2,进入else 则将2传入方法：head.next = removeElements(2,val); (回溯) head.next = [3->null] return [1->3->null] (回溯到递归的最外层即得到最终的结果为[1->3->null]) 第二次进入方法： head == 2 == 2,进入if 则将3传入方法，head = removeElements(3,val); (回溯) head = [3->null] return [3->null] 第三次进入方法： head == 3 ！= 2,进入else 则将null传入方法，head.next = removeElements(null,val); (回溯) head.next = null return [3->null] 第四次进入方法： head == null == null (回溯) return null
707. 设计链表 - 力扣（LeetCode）¶
- 单链表法
-
```Java class MyLinkedList { // 单链表
// 子类：链表节点类 class ListNode { int val; // 值空间 ListNode next; // 子节点指针空间 // 节点初始化 ListNode(int val) { this.val=val; } } //size存储链表元素的个数 private int size; //注意这里记录的是虚拟头结点 private ListNode head; // 初始化链表 public MyLinkedList() { this.size = 0; this.head = new ListNode(0); } //获取第index个节点的数值，注意index是从0开始的，第0个节点就是虚拟头结点 public int get(int index) { //如果index非法，返回-1 if (index < 0 || index >= size) {return -1;} ListNode cur = head; //第0个节点是虚拟头节点，所以查找第 index+1 个节点 for (int i = 0; i <= index; i++) { // 当index = 0,则cur = cur.next 即 返回index +1 的位置 cur = cur.next; } return cur.val; } // 指定插入 // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。 // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点。 // 如果 index 大于链表的长度，则返回空 public void addAtIndex(int index, int val) { if (index < 0 || index > size) { return; // 非法下标 } //找到要插入节点的前驱 ListNode pre = head; for (int i = 0; i < index; i++) { pre = pre.next; // 通过循环递归，将新节点的前驱节点找到 } ListNode newNode = new ListNode(val); newNode.next = pre.next; // 新节点的子节点 = 前驱节点的旧子节点 pre.next = newNode; // 前驱节点的新子节点 = 新节点 size++; } // 头部插入 public void addAtHead(int val) { ListNode newNode = new ListNode(val); newNode.next = head.next; // 新节点的子节点 = 0节点的子节点 head.next = newNode; // 0节点的子节点 = 新节点 size++; // 数量增加 // 在链表最前面插入一个节点，等价于在第0个元素前添加 // addAtIndex(0, val); } public void addAtTail(int val) { ListNode newNode = new ListNode(val); ListNode cur = head; while (cur.next != null) { cur = cur.next; // 快速循环迭代到末端 } cur.next = newNode; // 末端的子节点 = 新节点 size++; // 在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加 // addAtIndex(size, val); } public void deleteAtIndex(int index) { if (index < 0 || index >= size) { return; } //因为有虚拟头节点，所以不用对index=0的情况进行特殊处理 ListNode pre = head; for (int i = 0; i < index ; i++) { pre = pre.next; // 直接循环到对应的前驱节点 } pre.next = pre.next.next; // 将前驱节点的子节点（即要替换的节点），更新为被替换节点的子节点 size--; }}
/** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList obj = new MyLinkedList(); * int param_1 = obj.get(index); * obj.addAtHead(val); * obj.addAtTail(val); * obj.addAtIndex(index,val); * obj.deleteAtIndex(index); */ ``` - 双链表法
//双链表
class MyLinkedList {
class ListNode{
int val;
ListNode next, prev;
ListNode(int val){
this.val = val;
}
}
//记录链表中元素的数量
private int size;
//记录链表的虚拟头结点和尾结点
private ListNode head, tail;
public MyLinkedList() {
//初始化操作
this.size = 0;
this.head = new ListNode(0);
this.tail = new ListNode(0);
//这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！
this.head.next = tail; // 头尾节点互相对应
this.tail.prev = head;
}
public int get(int index) {
//判断index是否有效
if(index < 0 || index >= size){
return -1;
}
ListNode cur = head;//判断是哪一边遍历时间更短
if(index >= size / 2){
//tail开始
cur = tail;
for(int i = 0; i < size - index; i++){
cur = cur.prev;
}
}else{
for(int i = 0; i <= index; i++){
cur = cur.next;
}}
return cur.val;
}
public void addAtIndex(int index, int val) {
//判断index是否有效
if(index < 0 || index > size){
return;
}
//找到前驱
ListNode pre = head;
for(int i = 0; i < index; i++){
pre = pre.next;
}
//新建结点
ListNode newNode = new ListNode(val); // 新建节点 2，原链表为1<->3
newNode.next = pre.next; // 新节点的子节点是前驱的旧子节点，现在状态为 1<-3 , 2->3
pre.next.prev = newNode; // 前驱的旧子节点的前驱指针是新节点，现在状态为 1,2<->3
newNode.prev = pre; // 新节点的前驱指针是前驱，现在状态为 1<-2<->3
pre.next = newNode; // 前驱的子节点是新节点，现在状态为 1<->2<->3
size++;
}
public void addAtHead(int val) {
//等价于在第0个元素前添加
addAtIndex(0, val);
}
public void addAtTail(int val) {
//等价于在最后一个元素(null)前添加
addAtIndex(size, val);
}
public void deleteAtIndex(int index) {
//判断index是否有效
if(index < 0 || index >= size){
return;
}
//删除操作
ListNode pre = head;
for(int i = 0; i < index; i++){
pre = pre.next;
}
pre.next.next.prev = pre;
pre.next = pre.next.next;
size--;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
206. 反转链表 - 力扣（LeetCode）¶
-
双链表法
-
Java class Solution { public ListNode reverseList(ListNode head) { ListNode temp; // 保存cur的下一个节点 ListNode cur = head; ListNode pre = null; while(cur != null) { temp = cur.next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next cur.next = pre; // 翻转操作 /* 此时 第三个值被temp指向 cur->next指向pre也就是第一个值 这就执行了翻转操作 */ // 更新pre 和 cur指针 pre = cur; // 此时的pre只代表本次的第一位值，cur代表上一次移动时的第二位值 cur = temp; // 此时的cur只代表本次的第二位值，temp代表上一次移动时的第三位值 // 所以 pre = cur,cur = temp 表示指针向后移动 } return pre; } } -
- 时间复杂度: O(n)
- 空间复杂度: O(1)
-
递归
-
Java // 递归 class Solution { public ListNode reverseList(ListNode head) { return reverse(null, head); } // 假设传入 1 2 3 4 private ListNode reverse(ListNode prev, ListNode cur) { if (cur == null) { return prev; } ListNode temp = null; temp = cur.next;// 先保存下一个节点 cur.next = prev;// 反转 // 更新prev、cur位置 // prev = cur; // cur = temp; return reverse(cur, temp); } } // 第一层 prev = null cur = [1]-2-3-4 temp = (2)-3-4 得到 1-null cur` = 2-3-4 // 第二层 prev = 1-null cur = [2]-3-4 temp = (3)-4 得到 2-1-null cur` = 3-4 // 第三层 prev = 2-1-null cur = [3]-4 temp = (4) 得到 3-2-1-null cur` = 4 // 第四层 prev = 3-2-1-null cur = [4] temp = null 得到 4-3-2-1-null cur` = null // 第五层 prev = 4-3-2-1-null cur = null 直接返回prev 如上，全部通过return回溯得到最终结果为 4-3-2-1-null,反转完毕 -
从后往前递归
// 从后向前递归
class Solution {
ListNode reverseList(ListNode head) {
// 边缘条件判断
if(head == null) return null;
if (head.next == null) return head;
// 递归调用，翻转第二个节点开始往后的链表
ListNode last = reverseList(head.next);
// 翻转头节点与第二个节点的指向
head.next.next = head;
// 此时的 head 节点为尾节点，next 需要指向 NULL
head.next = null;
return last;
}
}
24. 两两交换链表中的节点 - 力扣（LeetCode）¶
- 循环
- ```Java
/**
- 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 dumyhead = new ListNode(-1); // 设置一个虚拟头结点
dumyhead.next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
ListNode cur = dumyhead; // 用于指向 “当前” 的指针
ListNode temp; // 临时节点，保存两个节点后面的节点
ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
while (cur.next != null && cur.next.next != null) {
temp = cur.next.next.next; // 第一次时，cur指向虚拟头，于是 next 指向第一个，next.next 指向第二个,next.next.next指向第三个
// 可以理解为4个部分
// 虚拟头、交换节点1、交换节点2、不变节点 这四个算一个整体来进行分析
firstnode = cur.next;
secondnode = cur.next.next;
cur.next = secondnode; // 步骤一：虚拟头 -> 交换2
secondnode.next = firstnode; // 步骤二：交换2 -> 交换1
// 步骤一、二执行了2 1 之间的交换
firstnode.next = temp; // 步骤三：恢复 不变节点的连接
cur = firstnode; // cur移动，准备下一轮交换
}
return dumyhead.next;
} } ```
- 循环改良版
- ```Java
/**
- 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 { // 将步骤 2,3 交换顺序，这样不用定义 temp 节点 public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0, head); ListNode cur = dummy; while (cur.next != null && cur.next.next != null) { ListNode node1 = cur.next;// 第 1 个节点 ListNode node2 = cur.next.next;// 第 2 个节点 cur.next = node2; // 步骤 1 : 虚拟头 -> 交换2 node1.next = node2.next;// 步骤 3 ： 恢复链接，此时将不变节点 与 交换节点1 先进行连接 // 这样就少了一个temp去存储不变节点 node2.next = node1;// 步骤 2：再将交换1和交换2进行连接：交换2 -> 交换1 cur = cur.next.next; // 直接跳过cur(虚拟头)、交换2(已被交换)、于是cur指向了交换1（已被交换）那么下一次交换的就是 交换1后面的两个节点 } return dummy.next; } } ```
- 递归
-
```Python /**
- 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) {
// base case 退出提交
if(head == null || head.next == null) return head;
// 获取当前节点的下一个节点
ListNode next = head.next;
// 进行递归
ListNode newNode = swapPairs(next.next);
// 这里进行交换
next.next = head;
head.next = newNode;
return next;} }
假设链表[1 2 3 null] // 第一次 head = 1 next = 2 newNode = swap(3) -> newNode == 3 -> next.next 原为3 现为 1 =》 2 -> 1 -> head.next 原为 2 现为 3 =》 1 -> 3 -> return [2 1 3] // 第二次 head = 3 next = null return 3
最终结果就是 2 1 3(应当注意是 “两两交换”而不是逐个交换，所以3没有被改变) ```
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）¶
- 循环
- ```Java
/**
- 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) {
//新建一个虚拟头节点指向head
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
//快慢指针指向虚拟头节点
ListNode fastIndex = dummyNode;
ListNode slowIndex = dummyNode;
// 只要快慢指针相差 n 个结点即可 for (int i = 0; i <= n; i++) { fastIndex = fastIndex.next; } while (fastIndex != null) { fastIndex = fastIndex.next; slowIndex = slowIndex.next; } // 此时 slowIndex 的位置就是待删除元素的前一个位置。 // 检查 slowIndex.next 是否为 null，以避免空指针异常 if (slowIndex.next != null) { slowIndex.next = slowIndex.next.next; // 此处的作用就是将 被删除节点后的 不变节点 与 slow 指针指向的被删除节点的前一个节点进行连接 } // 假设删除的是头节点，那么当执行完for循环的时候，slow指向虚拟头节点且fast = null // 于是将虚拟头结点的子节点 与 子节点（即头节点）的子节点 进行替换 // 从而实现删除 特定节点 // 所以返回的dummyNode.next 就会是 新的头节点内容了 return dummyNode.next;} } ``` - 递归
/**
* 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 s = new ListNode(-1, head);
// 递归调用remove方法，从哑节点开始进行删除操作
remove(s, n);
// 返回新链表的头（去掉可能的哑节点）
return s.next;
// ----这部分的逻辑和循环法差不多
}
public int remove(ListNode p, int n) {
// 递归结束条件：如果当前节点为空，返回0
if (p == null) {
return 0;
}
// 递归深入到下一个节点
int net = remove(p.next, n);
// 如果当前节点是倒数第n个节点，进行删除操作
if (net == n) {
p.next = p.next.next; // 同理 前节点的子节点（即当前被删节点）与被删节点的子节点 进行替换，从而实现删除特定节点操作
}
// 返回当前节点的总深度
return net + 1; // 目的是在递归时确定当前递归对链表的移动到了哪个位置
}
}
面试题 02.07. 链表相交 - 力扣（LeetCode）¶
简单来说，就是求两个链表交点节点的指针。 交点不是数值相等，而是指针相等
- 求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置
-
就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点
-
(版本一)先行移动长链表实现同步移动
-
```Java /**
- 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) { ListNode curA = headA; // 先定义两个用于移动的指针，指向两个链表的开头 ListNode curB = headB; int lenA = 0, lenB = 0; while (curA != null) { // 求链表A的长度 lenA++; curA = curA.next; } while (curB != null) { // 求链表B的长度 lenB++; curB = curB.next; } // 由于cur在计算长度的时候发生了移动，所以下面重置cur的位置 curA = headA; curB = headB; // 让curA为最长链表的头，lenA为其长度 if (lenB > lenA) { //1. swap (lenA, lenB); int tmpLen = lenA; lenA = lenB; lenB = tmpLen;
//2. swap (curA, curB); ListNode tmpNode = curA; curA = curB; curB = tmpNode; } // 上面这三行的代码的处理是为了 gap = lenA - lenB 、 while(gap-- >0) 这些代码的一致性 // 避免因为链表长度的变化而导致代码的赘余 // 求长度差 int gap = lenA - lenB; // 让curA和curB在同一起点上（末尾位置对齐） while (gap-- > 0) { curA = curA.next; } // 遍历curA 和 curB，遇到相同则直接返回 while (curA != null) { if (curA == curB) { return curA; } curA = curA.next; curB = curB.next; } return null; }}
- (版本二) 合并链表实现同步移动 -Java public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // p1 指向 A 链表头结点，p2 指向 B 链表头结点 ListNode p1 = headA, p2 = headB; while (p1 != p2) { // p1 走一步，如果走到 A 链表末尾，转到 B 链表 if (p1 == null) p1 = headB; else p1 = p1.next; // p2 走一步，如果走到 B 链表末尾，转到 A 链表 if (p2 == null) p2 = headA; else p2 = p2.next; } return p1; } } ``` -
这段代码的思路是基于链表交叉的补偿，可以理解为假设链表A长度为m，链表B的长度为n，那么对于链表A和B来说，假设完全不存在交叉的点，那么二者要遍历的路径都为m+n长度。如果存在交叉的点，那么必然要求在m+n的长度内，A和B存在相等的时候，那么返回其中一点即可。
-
例如A = 1 2 3 4 ,B = 3 4 那么对于A的路径就是 1 2 3 4 3 4，对应B的路径为 3 4 1 2 3 4，二者对比即可发现A和B在3的时候发生交叉。
142. 环形链表 II - 力扣（LeetCode）¶
- 如何判断有环
可以使用快慢指针，定义一个fast指针，每次走2个节点，定义一个slow指针，每次走1个节点，那么如果存在环，那么他们必然在环内发生相遇。相当于环绕跑步，跑的快的会在某一圈的时候从后面追赶上跑得慢的，这其实是一个环内的追及问题。但是应当注意，并非是fast节点追及slow节点才是相遇，而是fast节点比slow节点恰好多走一个节点的时候，被slow节点追及，此时二者相遇的节点才是正确的相遇节点。
- 有环如何判断入口
当有环时，快慢指针必然在环内相遇，所以存在一个相遇节点，那么假设从头节点到环入口节点的距离为x个节点，从环入口到相遇节点的距离为y个节点，从相遇节点再到环入口的距离为z个节点。
经过检验可以得到：
- 当fast恰好走到slow前一个节点位置（即相遇节点），然后slow节点与fast节点在相遇节点相遇。那么slow节点所走过的节点数即为 x + y
- 那么fast走过的节点数是多少呢？可以这样理解，头节点到fast与slow相遇节点的距离固定为x + y，可以认为“理论上fast和slow应当在此处相遇”，然而实际上当fast第一次走到相遇节点的时候，slow节点还没走到相遇节点，所以此时，fast节点就会开始循环（从相遇节点开始直到与slow节点在相遇节点发生相遇），那么假设fast节点循环了n次才和slow节点相遇，所以fast走过的节点数为 x + y + n(z + y)
- 由于fast比slow快2个节点，即fast走过的节点数是slow走过的节点数的两倍，所以存在
- (x + y) * 2 = x + y + n(z + y)
综上所述，可以得到头结点到入口节点的距离 x = (n - 1)(y + z) + z
分析可知，当n=1即只转一圈就发生了相遇的情况，此时x = z，意味着从相遇节点到入口节点和从头节点到入口节点的距离是一样的。那么可以分别在相遇节点和头节点定义指针，每次移动一个节点，那么当他们相遇的时候就是环形入口的节点。
/**
* 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) {
ListNode slow = head; // 定义快慢指针，从头部开始
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next; // 快指针比慢指针多走一步
// 对于指针的相等即代表内存空间的指向是一致的
if (slow == fast) {// 有环
ListNode index1 = fast;
ListNode index2 = head;
// 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
// 不存在环则返回null
return null;
}
}
哈希表¶
红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。
-
常见的三种哈希结构
-
数组
- 数组就是简单的哈希表，但是数组的大小可不是无限开辟的
- 注意，使用数组来做哈希的题目，是因为题目都限制了数值的大小
- 如果题目没有限制数值的大小，就无法使用数组来做哈希表了
- 如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
- set （集合）
- 此时就要使用另一种结构体了，set ，在java中，其类型即为HashSet
- 直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。所以才要具体情况具体分析
- map(映射)
242. 有效的字母异位词 - 力扣（LeetCode）¶
/**
* 242. 有效的字母异位词 字典解法
* 时间复杂度O(m+n) 空间复杂度O(1)
*/
class Solution {
public boolean isAnagram(String s, String t) {
int[] record = new int[26];
for (int i = 0; i < s.length(); i++) {
record[s.charAt(i) - 'a']++;
// 首先，已知只会出现小写字母，而且由于26个小写字母对应的ASCII码是连续的数字
// 所以，可以假设以 a 为 索引 0 ，z 为 索引 26
// 则，使用 s.charAt(i) - 'a' 可以 得到各个字母相对于a的位置，也就是对应在数组中的索引
// 则 record[s.charAt(i) - 'a']++ 即是指record的对应位置的值++，即可得到该字符串中，字母出现的次数
}
for (int i = 0; i < t.length(); i++) {
record[t.charAt(i) - 'a']--;
}
for (int count: record) {
if (count != 0) { // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
return false;
}
}
return true;
// record数组所有元素都为零0，说明字符串s和t是字母异位词
// 意思是 s 和 t字母的类型和数量是一致的，只是排列不同
}
}
383. 赎金信 - 力扣（LeetCode）¶
在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以数组更加简单直接有效！
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
// shortcut
if (ransomNote.length() > magazine.length()) {return false;}
// 加一个判断，避免浪费时间
int[] record = new int[26];
for (int i = 0; i < magazine.length(); i++) {
record[magazine.charAt(i) - 'a']++;
}
for (int i = 0; i < ransomNote.length(); i++) {
record[ransomNote.charAt(i) - 'a']--;
}
for (int count: record) {
if (count < 0) {
return false;
}
}
return true;
}
/**
这道题的解题思路和异位词的思路是一致的，区别就是 异位词要求 两个字符串的字母的 类型和数量要一致
而 这道题的思路要求 第二个的字母类型和数量比第一个相等或者多就行了
因此只需要将第二个maganize的字符串转为一个字典，再用这个字典请计算ransomNote中的字符是否想匹配即可
至于 “不可重复使用” 的要求，本方法默认每个字符只会使用一次*/
}
49. 字母异位词分组 - 力扣（LeetCode）¶
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String,ArrayList<String>> map = new HashMap<>();// 重点1：懂得使用java的hashmap来存储数据
// 重点2：hashmap的类型应该为以string为键，返回的数组为值
for(String s: strs){
char[] chars = s.toCharArray();// 重点3：toCharArray方法
Arrays.sort(chars);
String key = Arrays.toString(chars);
if(!map.containsKey(key)){
map.put(key,new ArrayList<String>());
}
map.get(key).add(s);
}
return new ArrayList<>(map.values());// 重点4：将map的values转为数组的方法
}
}
本题的解法要点关键是要想到 字母异位词实际上就是相同类型和数量的字母的排列组合，因此它们的重排序必然是相同的，所以用于做键，而由于返回的内容要求的是数组存储数组，所以想到map的值可以是一个数组，存放同排列组合类型的不同字符串，然后再通过map的values和list之间的互转来得到最终想要的结果。
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）¶
class Solution {
public List<Integer> findAnagrams(String s, String p) {
if(p.length() > s.length()){return new ArrayList<>();}
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0;i < s.length()-p.length() + 1;i++){
int[] map2 = new int[26];
for(int j = 0;j < p.length();j++){
map2[p.charAt(j) - 'a']++;
}
boolean flag = true;
for(int j = 0;j < p.length();j++){
map2[s.charAt(i+j) - 'a']--;
}
for(int j = 0;j < p.length();j++){
if(map2[s.charAt(i+j) - 'a'] != 0){
flag = false;
}
}
if(flag){
list.add(i);
}
}
return list;
}
}
349. 两个数组的交集 - 力扣（LeetCode）¶
- HashSet
-
```Java // 时间复杂度O(n+m+k) 空间复杂度O(n+k) // 其中n是数组nums1的长度，m是数组nums2的长度，k是交集元素的个数 // 分别对应的是第一次for循环获得字典，第二次for循环获得结果数组，第三次for循环（或Stream流）获得int[] 数组
import java.util.HashSet; import java.util.Set;
class Solution { public int[] intersection(int[] nums1, int[] nums2) { // 首先先确保传入的两个数组不为null且内部存在元素 if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) { return new int[0]; } // 交集 所求的就是 两个数组中都有 且不重复 的部分 Set
set1 = new HashSet<>();// set可以去重、hashset底层是哈希表，所以不要求有序 Set resSet = new HashSet<>(); //遍历数组1 for (int i : nums1) { set1.add(i); } //遍历数组2的过程中判断哈希表中是否存在该元素 for (int i : nums2) { if (set1.contains(i)) { resSet.add(i); } } // 使用两个for循环，一个用于添加形成字典，一个用于判断形成结果集合 //方法1：将结果集合转为数组 return resSet.stream().mapToInt(Integer::intValue).toArray(); // stream,mapToInt(Integer::intValue),toArray /** * 将 Set<Integer> 转换为 int[] 数组： * 1. stream() : Collection 接口的方法，将集合转换为 Stream<Integer> * 2. mapToInt(Integer::intValue) : * - 中间操作，将 Stream<Integer> 转换为 IntStream * - 使用方法引用 Integer::intValue，将 Integer 对象拆箱为 int 基本类型 * 3. toArray() : 终端操作，将 IntStream 转换为 int[] 数组。 */ //方法2：另外申请一个数组存放setRes中的元素,最后返回数组 // int[] arr = new int[resSet.size()]; // int j = 0; // for(int i : resSet){ // arr[j++] = i; // } // return arr; }}
- 数组 -Java class Solution { public int[] intersection(int[] nums1, int[] nums2) { int[] hash1 = new int[1002];// 使用有限长度的数组 int[] hash2 = new int[1002]; for(int i : nums1)// 获取的是数组内的值 hash1[i]++;// 使数组内的值作为的新数组下标对应位置进行++ // 这样，对应下标的数组值就说明该下标值在原数组中出现的次数 for(int i : nums2) hash2[i]++; ListresList = new ArrayList<>(); for(int i = 0; i < 1002; i++) if(hash1[i] > 0 && hash2[i] > 0)// 同样的值则是交集 resList.add(i); int index = 0; int res[] = new int[resList.size()]; for(int i : resList) res[index++] = i; return res; } } ```
350. 两个数组的交集 II - 力扣（LeetCode）¶
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
// 首先先确保传入的两个数组不为null且内部存在元素
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
return new int[0];
}
if (nums1.length > nums2.length) {
// 加一个内部调用，是为了降低时间复杂度，如果nums1长度大于nums2的话
return intersect(nums2, nums1);
}
Map<Integer,Integer> map = new HashMap<>();
// 形成字典
for(int num:nums1){
int count = map.getOrDefault(num, 0) + 1;// map的判断是否存在的方法是 getOrDefault()
map.put(num, count);// 填入对应的值使用的是put(key,value) 方法
}
// 对照
int[] intersection = new int[nums1.length]; // 定义一个数组
int index = 0;
for(int num:nums2){
int count = map.getOrDefault(num, 0);
// 获取集合中的键值
if (count > 0) {
// 向数组中逐步添加，index是用于移动数组指针的
intersection[index++] = num;
count--;
if (count > 0) {
map.put(num, count);
} else {
// 如果值已经不满足则移除该数
map.remove(num);
}
}
}
return Arrays.copyOfRange(intersection, 0, index);
// 复制长度的数组返回，index是有交集的最大长度位置
}
}
202. 快乐数 - 力扣（LeetCode）¶
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。
判断这个sum是否重复出现
class Solution {
// 题目分析：
// 1、通过循环，计算得到的结果会再进入计算
// 2、如果出现了重复出现的结果，就说明这个原来的数没机会得到1，所以失败
public boolean isHappy(int n) {
Set<Integer> record = new HashSet<>();
while (n != 1 && !record.contains(n)) { // 判断是否到1，以及结果是否已经出现过
record.add(n);// 没出现过则填入
n = getNextNumber(n);// 然后进行计算得到一个sum
}
return n == 1;
}
private int getNextNumber(int n) {
int res = 0;// 这就是最终返回的结果
while (n > 0) {
int temp = n % 10;// 通过循环来降低位数
// 如果是3位数则循环3次
res += temp * temp;
n = n / 10;
}
return res;
}
}
1. 两数之和 - 力扣（LeetCode）¶
很明显暴力的解法是两层for循环查找，时间复杂度是O(n^2)。
这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标
对于这道题来说，就是确定一个值后，去map里面查询另一个匹配的值是否存在
- 哈希表
Go class Solution { //使用哈希表 public int[] twoSum(int[] nums, int target) { int[] res = new int[2]; // 如果数组为空则直接退出 if(nums == null || nums.length == 0){ return res; } Map<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++){ int temp = target - nums[i]; // 遍历当前元素，并在map中寻找是否有匹配的key if(map.containsKey(temp)){ res[1] = i; res[0] = map.get(temp);// 这里就是满足了匹配下，从map中获取到对应的下标，于是可以被res返回 break; } map.put(nums[i], i); // 如果没找到匹配对，就把已经访问过的元素和下标加入到map中 // 因为后面查询到的元素会回头向前匹配，这样就避免了使用两次for循环的暴力解法 } // 之所以要用（数组值，数组下标）这样的结构以及map来实现，是因为最终要返回的不是所求得的值，而是值在数组中所对应的下标 return res; } }- 哈希表简化
Java class Solution { //使用哈希表方法2 public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> indexMap = new HashMap<>(); // 本质上也是减少了“从后往前”的二次查询的复杂度 // 因为暴力解法之所以麻烦的原因是因为，代码不清楚之前所访问过的元素是否满足和当前元素搭配的情况 // 所以才需要每个元素都重复访问一次全组 // 而HashMap的优化就免去了冗余的重复访问，直接将访问过的元素存入map，等到后面查询的时候直接查询map即可 for(int i = 0; i < nums.length; i++){ int balance = target - nums[i]; // 记录当前的目标值的余数 if(indexMap.containsKey(balance)){ // 查找当前的map中是否有满足要求的值 return new int []{i, indexMap.get(balance)}; // 如果有，返回目标值 } else{ indexMap.put(nums[i], i); // 如果没有，把访问过的元素和下标加入map中 } } return null; } }