hot100-141、142、148、146、136、169、75、31、287
链表
141. 环形链表（简单）
方法一、快慢指针
有环总会相遇
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode a = head,b = head;
if(head == null)return false;
do{
a = a.next;
b = b.next;
if(b!=null)b = b.next;
}while(a!=b && b != null);
return b != null;
}
}
方法二、哈希
环的特性是单指针遍历可以去看已经看过的节点
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> seen = new HashSet<ListNode>();
while (head != null) {
if (!seen.add(head)) {
return true;
}
head = head.next;
}
return false;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/linked-list-cycle/solutions/440042/huan-xing-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。方法三、暴力
无环长度最多1w，所以遍历1w+次看看
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode left = head;
int count = 0;
if(left == null){
return false;
}
while(left.next != null){
count++;
left = left.next;
if(count > 10000){
return true;
}
}
return false;
}
}142. 环形链表 II（中等）
方法一、快慢指针
先相遇，让b回原点，ab同时步长为1走
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode a = head,b = head;
if(head == null)return null;
do{
a = a.next;
b = b.next;
if(b!=null)b = b.next;
}while(a!=b && b != null);
if(b == null)return null;
b = head;
while(a != b){
a = a.next;
b = b.next;
}
return b;
}
}148. 排序链表（中等）
方法一、归并排序
此处findMid函数我有踩坑，才注意到fast指向next，然后需要判断next是不是空，因为数分奇偶，可能触发边界条件。重新学了一下merge的方式。
/**
* 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 sortList(ListNode head) {
if(head == null || head.next == null)return head;
ListNode mid = findMiddle(head);
ListNode rHead = mid.next;
mid.next = null;
ListNode left = sortList(head);
ListNode right = sortList(rHead);
return mergeList(left,right);
}
public ListNode findMiddle(ListNode head){
if(head == null)return null;
ListNode slow = head,fast = head.next;
while(fast != null && fast.next!= null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNode mergeList(ListNode l1, ListNode l2){
ListNode dummy = new ListNode(-1),temp = dummy;
while(l1 != null && l2 != null){
if(l1.val > l2.val){
temp.next = l2;
l2 = l2.next;
}else{
temp.next = l1;
l1 = l1.next;
}
temp = temp.next;
}
if (l1!=null){
temp.next = l1;
}
if (l2!=null){
temp.next = l2;
}
return dummy.next;
}
}
146. LRU 缓存（中等）
方法一、双向链表+哈希
涉及顺序则试试链表，涉及O(1)哈希，双向队列不能把中间的移到后面。其实还可以再函数模块化一点但是懒得了，代码结构不好看。
class LRUCache {
private class Node{
int key,value;
Node prev,next;
Node(int k,int v){
key = k;
value = v;
}
}
private int capacity;
private int count;
private Node dummy = new Node(-1,-1);
private HashMap<Integer,Node> keyToNode = new HashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
dummy.prev = dummy;
dummy.next = dummy;
}
public int get(int key) {
Node temp = keyToNode.get(key);
if(temp == null)return -1;
//拿走
temp.prev.next = temp.next;
temp.next.prev = temp.prev;
//放入
temp.next = dummy.next;
dummy.next.prev = temp;
temp.prev = dummy;
dummy.next = temp;
return temp.value;
}
public void put(int key, int value) {
Node temp = keyToNode.get(key);
if(temp == null){
count++;
Node temp1 = new Node(key,value);
temp1.next = dummy.next;
dummy.next.prev = temp1;
temp1.prev = dummy;
dummy.next = temp1;
keyToNode.put(key,temp1);
}else{
temp.value = value;
get(key);
}
if(capacity < count){
count--;
keyToNode.remove(dummy.prev.key);
dummy.prev.prev.next = dummy;
dummy.prev = dummy.prev.prev;
}
}
}技巧
136. 只出现一次的数字(简单)
方法一、异或
class Solution {
public int singleNumber(int[] nums) {
int n = nums.length,res = 0;
for(int i = 0;i < n;i++){
res^=nums[i];
}
return res;
}
}
169. 多数元素(简单)
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
方法一、栈
class Solution {
public int majorityElement(int[] nums) {
int n = nums.length;
if(n == 1)return nums[0];
Deque<Integer> st = new ArrayDeque<>();
for(int i = 0;i < n;i++){
if(st.isEmpty() || st.peek() == nums[i]){
st.push(nums[i]);
}else{
st.pop();
}
}
return st.peek();
}
}
方法二、摩尔投票
常数相消归零改换 本质上是不需要记录过去的数字本身 只需计数 所以栈信息量溢出
class Solution {
public int majorityElement(int[] nums) {
int n = nums.length,res = nums[0],cnt = 1;
for(int i = 1;i < n;i++){
if(res == nums[i]){
cnt++;
}else if(--cnt == 0){
res = nums[i];
cnt++;
}
}
return res;
}
}75. 颜色分类（中等）
方法一、双指针
也可以遍历一次统计数量覆盖改写
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
int x = 0,y = 0;
for(int i = 0;i < n;i++){
int t = nums[i];
nums[i] = 2;
if(t < 2)nums[x++] = 1;
if(t < 1)nums[y++] = 0;
}
}
}31. 下一个排列（中等）
方法一、两次循环
最初错误思路只考虑到交换但没有反序
倒序遍历，找到第一个降点index1，第二次遍历，找到(index1,n)中第一个大于index1的点index2。交换两位，将(index1,n)倒序。
相对代码而言，index1最初定位0，最后swap功能可以合并。不改善性能，但可以优化逻辑
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length,index1 = -1,index2 = 0;
if(n == 1)return;
for(int i = n-2;i >=0;i--){
if(nums[i] < nums[i+1]){
index1 = i;
break;
}
}
if(index1 == -1){
reverse(nums,0,n-1);
return;
}
for(int i = n-1;i > index1;i--){
if(nums[index1] < nums[i]){
index2 = i;
break;
}
}
swap(nums,index1,index2);
reverse(nums,index1+1,n-1);
}
public void reverse(int[] nums,int x,int y){
for(int i = x,j = y;i<j;i++,j--){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
public void swap (int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}287. 寻找重复数(中等)
方法一、拟成环链表
数组中的下标和数字构成一个指向
class Solution {
public int findDuplicate(int[] nums) {
int n = nums.length,slow = 0,fast = 0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){//这题必然有环
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
return nums[slow];
}
}