当前位置: 首页 > news >正文

leetcode hot100(2)

11.200.岛屿数量

本题是图论中经典的连通分量问题,可以用bfs/dfs解决。

class Solution {int[][] directions = new int[][]{{-1,0},{0,-1},{1,0},{0,1}};public int numIslands(char[][] grid) {boolean visited[][] = new boolean[grid.length][grid[0].length];int result = 0 ;for(int i = 0 ; i < grid.length ; i++){for(int j = 0 ; j < grid[0].length ; j++){if(grid[i][j] == '1' && !visited[i][j]){visited[i][j] = true;result++;dfs(i,j,grid,visited);}}}return result;}public void dfs(int x , int y , char[][] grid , boolean[][] visited){for(int i = 0 ; i < 4 ; i++){int nextX = x + directions[i][0];int nextY = y + directions[i][1];if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;if(grid[nextX][nextY] == '1' && !visited[nextX][nextY]){visited[nextX][nextY] = true;dfs(nextX,nextY,grid,visited);}}}
}

使用bfs的话要注意一点:在加入队列的时候做visited标记,而不是在出队列时,否则会造成重复入队。

int[][] directions = new int[][]{{-1,0},{0,-1},{1,0},{0,1}};public int numIslands(char[][] grid) {boolean visited[][] = new boolean[grid.length][grid[0].length];int result = 0 ;for(int i = 0 ; i < grid.length ; i++){for(int j = 0 ; j < grid[0].length ; j++){if(grid[i][j] == '1' && !visited[i][j]){visited[i][j] = true;result++;bfs(i,j,grid,visited);}}}return result;}public void bfs(int x, int y , char[][] grid, boolean[][] visited){Deque<int[]> queue = new ArrayDeque<>();visited[x][y] = true;queue.add(new int[]{x,y});while(!queue.isEmpty()){int[] node = queue.poll();int nodeX = node[0];int nodeY = node[1];for(int i = 0 ; i < 4 ; i++){int nextX = nodeX + directions[i][0];int nextY = nodeY + directions[i][1];if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;if(grid[nextX][nextY] == '1' && !visited[nextX][nextY]){visited[nextX][nextY] = true;queue.add(new int[]{nextX,nextY});}}}}

12.198.打家劫舍

本题是动态规划问题,回顾动态规划五部曲:

(1)确定dp数组及下标含义

(2)确定递推方程

(3)确定如何初始化

(4)确定遍历顺序

(5)dp模拟

(1)dp[i] : 考虑前i家,所能盗取的最大金额

(2)递推方程:结合递推顺序,从前往后递推,dp[i]应该来源于前面已经计算出来的。又因为不能偷盗相邻的房屋,因此对于当前的第i间房屋,分成两种情况考虑:

        不偷,那么最大金额为dp[i-1]

        偷,那么最大金额为dp[i-2] + nums[i]

二者取最大值,dp[i] = Math.max(dp[i-1] , dp[i-2] + nums[i])

(3)确定如何初始化:根据递推方程,需要初始化dp[0]和dp[1]

根据定义,dp[0] = num[0] , dp[1] = Math.max(dp[0],dp[1])

(4)确定遍历顺序 从前往后遍历

(5)dp模拟

public int rob(int[] nums){int[] dp = new int[nums.length];if(nums.length == 1) return nums[0];dp[0] = nums[0];dp[1] = Math.max(nums[0],nums[1]);for(int i = 2 ; i < nums.length ; i++){dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i]);}return dp[nums.length-1];}

13.169.多数元素

(1)简单的统计

public int majorityElement(int[] nums) {int border = nums.length/2;int result = 0;Map<Integer,Integer> map = new HashMap<>();for (int num : nums) {map.put(num,map.getOrDefault(num,0)+1);}for (Map.Entry<Integer, Integer> entry : map.entrySet()) {int num = entry.getKey();int cnt = entry.getValue();if(cnt > border){result = num;}}return result;}

(2)排序

(3)随机化算法

(4)分治

(5)Boyer-Moore 投票算法

该算法做到了时间复杂度O(n),空间复杂度O(1)

class Solution {public int majorityElement(int[] nums) {int count = 0;Integer candidate = null;for(int num : nums){if(count == 0){candidate = num;}count += (num == candidate) ? 1  :  -1;}return candidate;}
}

以上若干解法在本题的leetcode官方题解中有详细介绍

14.238.除自身以外数组的乘积

本题不允许使用除法,同时除法也无法解决0的问题。

(1)前后缀之积

和前面和后面元素有关系的问题,考虑使用前后缀(和接雨水有点神似)

分别用两个数组计算出前缀之积和后缀之积,再相乘,就得到了结果。

这种解法时间上进行了三次顺序遍历,空间上使用了2长度为nums.length的数组,时间复杂度为   O(n),空间复杂度为O(n)

public int[] productExceptSelf(int[] nums) {int[] pre = new int[nums.length];int[] sur = new int[nums.length];pre[0] = 1;for(int i = 1 ; i < nums.length ; i++){pre[i] = pre[i-1] * nums[i-1];}sur[nums.length-1] = 1;for(int i = nums.length-2 ; i >= 0; i++){sur[i] = sur[i+1]*nums[i+1];}int[] res = new int[nums.length];for(int i = 0; i < nums.length ;i++){res[i] = pre[i] * sur[i];}return res;}

进阶要求:在常数空间复杂度内完成题目

前后缀实际上用完了就不再需要了,可以即时地计算使用。

时间复杂度O(n),空间复杂度除了返回结果以外,为O(1)

class Solution {public int[] productExceptSelf(int[] nums){int[] res = new int[nums.length];res[0] = 1;int pre = 1;for(int i = 1 ; i < nums.length ; i++){pre *= nums[i-1];res[i] = pre;}int sur = 1;for(int i = nums.length-2 ; i >= 0 ; i--){sur *= nums[i+1];res[i] *= sur;}return res;}
}

或者理解为,在第一轮中直接将pre存储到ans里,第二轮倒着的时候ans直接乘sur。(更进一步的话,pre和sur其实可以用一个变量表示)

15.155.最小栈

(1)使用辅助栈

定义数据栈支持基本的push、pop、top操作

定义辅助栈支持常数时间内确定最小值操作

class MinStack {Deque<Integer> dataStack;Deque<Integer> minStack;public MinStack() {dataStack = new ArrayDeque<>();minStack = new ArrayDeque<>();}public void push(int val) {dataStack.push(val);minStack.push((minStack.isEmpty() || minStack.peek()> val) ? val : minStack.peek());}public void pop() {dataStack.pop();minStack.pop();}public int top() {return dataStack.peek();}public int getMin() {return minStack.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

压minStack的时候也可以简化判断逻辑,那么需要实现压入一个Integer.MAX_VALUE作为标志,以防minStack为空

class MinStack {Deque<Integer> dataStack;Deque<Integer> minStack;public MinStack() {dataStack = new ArrayDeque<>();minStack = new ArrayDeque<>();minStack.push(Integer.MAX_VALUE);}public void push(int val) {dataStack.push(val);minStack.push(( minStack.peek()> val) ? val : minStack.peek());}public void pop() {dataStack.pop();minStack.pop();}public int top() {return dataStack.peek();}public int getMin() {return minStack.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

时间复杂度O(1),空间复杂度O(n)

(2)使用一个栈,但是栈保存元素的数据结构不是基础类型,而是本身的值和对应的最小值。相当于把原来两个栈“垂直”合并了。

只需要保持一个当前的min,同时根据push和pop更新min即可。

或者:

时间复杂度O(1),空间复杂度O(n)

(3)自定义一个栈

时间复杂度O(1),空间复杂度O(n)

16.152. 乘积最大子数组

(1)暴力

时间复杂度O(n^2),会时间超限

class Solution {public int maxProduct(int[] nums) {int[] product = new int[nums.length];int res = Integer.MIN_VALUE ;for(int i = 0 ; i < nums.length ;i++){product[i] = nums[i];res = Math.max(res,product[i]);for(int j = i+1 ; j < nums.length ; j++){product[j] = product[j-1] * nums[j];res = Math.max(res,product[j]);}}return res;}
}

(2)动态规划

与最大子序和的递推方程不同的是,这里当前位置的最优解未必是由前一个位置转移得来的,原因在于乘法乘子有负数不是越乘越小的,而加法里的负数是越加越小的。

即负数的乘法具有“逆转”的可能性,基于这种逆转的可能性,我们需要维护一个未来可能逆转为最大值的负数,并且我们希望他“越小越好”(因为这样逆转之后会更大)。从这个角度出发,我们在维护max的同时还要维护一个min.

在max和min的dp方程里,他们交叉存在,这是因为基于当前数字的正负,他们随时有交换逆转的可能。

回顾动态规划五部曲:

(1)确定dp数组及下标含义

dpmax[i]:考虑以i结尾的子数组,能够达到的最大乘积

dpmin[i]:考虑以i结尾的子数组,能够达到的最小乘积

(2)递推方程

dpmax[i] = Math.max(dpmax[i-1]*nums[i],nums[i],dpmin[i-1]*nums[i])

dpmin[i] = Math.min(dp[min[i-1]*nums[i[,nums[i],dpmax[i-1]*nums[i])

(3)初始化

根据递推方程和递推顺序,dpmax[0],dpmin[0]需要初始化

根据dp数组及下标含义,dpmax[0] = dpmin[0] = nums[0];

(4)递推顺序

从前往后

(5)dp模拟

class Solution {public int maxProduct(int[] nums){int[] dpmax = new int[nums.length];int[] dpmin = new int[nums.length];dpmax[0] = dpmin[0] = nums[0];for(int i = 1 ; i < nums.length ; i++){dpmax[i] = Math.max(dpmax[i-1]*nums[i],Math.max(dpmin[i-1]*nums[i],nums[i]));dpmin[i] = Math.min(dpmin[i-1]*nums[i],Math.min(dpmax[i-1]*nums[i],nums[i]));}int res = Integer.MIN_VALUE;for (int i : dpmax) {res = Math.max(res,i);}return res;}
}

考虑空间优化的话,dpmax,dpmin数组只在从前往后推导的时候用到,并且是相邻用到的,实际上用两个变量(但是由于for循环逻辑里dp递推关系是交叉的,还要区分过去的dpmax和现在dpmax,这里容易混淆)就可以替换。

class Solution {public static int maxProduct(int[] nums){int dpmax = nums[0];int dpmin = nums[0];int res = nums[0];for(int i = 1 ; i < nums.length; i++){int dpmaxCur = Math.max(dpmax*nums[i],Math.max(dpmin*nums[i],nums[i]));int dpminCur = Math.min(dpmin*nums[i],Math.min(dpmax*nums[i],nums[i]));res = Math.max(res,dpmaxCur);dpmax = dpmaxCur;dpmin = dpminCur;}return res;}
}

17.148.排序链表

(1)纯暴力法

遍历了三次O(n),排序O(nlogn),空间复杂度O(n)

总时间复杂度O(nlogn),空间复杂度O(n)

ublic ListNode sortList(ListNode head) {ListNode node = head;List<Integer> list = new ArrayList<>();int size = 0 ;while(node != null){size++;node = node.next;}int[] arr = new int[size];node = head;int i = 0;while(node != null){arr[i++] = node.val;node = node.next;}Arrays.sort(arr);node = head;i = 0;while(node != null){node.val = arr[i++];node = node.next;}return head;}

(2)进阶要求:你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

这样就没办法复制链表到数组里排序了,只能从链表自身排序,才能够保持常数级空间复杂度。

对链表本身使用归并排序。

题目:

147.对链表进行插入排序

lastSorted.next = curr.next
curr.next = prev.next
prev.next = curr

/*** 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 insertionSortList(ListNode head) {//判断链表是否为空if(head == null) return head;//创建dummyNode 便于在头节点之前插入节点ListNode dummyNode = new ListNode();dummyNode.next = head;//原来控制循环次数的i,现在有cur != null控制//lastSorted记录有序区的位置ListNode lastSorted = head;ListNode cur = head.next;while(cur != null){if(cur.val >= lastSorted.val){lastSorted = lastSorted.next;}else{ListNode prev = dummyNode;while(prev.next.val < cur.val){prev = prev.next;}lastSorted.next = cur.next;cur.next = prev.next;prev.next = cur;}cur = lastSorted.next;}return dummyNode.next;}
}

时间复杂度O(n^2),空间复杂度O(1).

使用插入排序达到了空间复杂度的要求,但没有达到时间复杂度的要求。

用递归法实现归并排序,空间复杂度是O(nlogn);自下而上实现归并排序,空间复杂度是O(1),满足题目要求。

1.递归实现归并排序

这里使用递归法实现归并排序中,使用快慢指针找到中间节点,需要在节点数是偶数的时候选择左边的,因此需要让fast先走一步。否则找到的中间节点是右边的。

如果找到的节点是右边的,这将导致当链表节点只有两个的时候,分割得到的始终是2和0,2的一侧永远是2,无法满足递归终止条件,会StackOverFlow.

/*** 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 slow = head, fast = head.next;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}ListNode tmp = slow.next;slow.next = null;ListNode left = sortList(head);ListNode right = sortList(tmp);ListNode h = mergeTwoLists(left, right);return h;}public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newList = new ListNode();ListNode head = newList;while(list1 != null && list2 != null){if(list1.val < list2.val){head.next = list1;list1 = list1.next;}else{head.next = list2;list2 = list2.next;}head = head.next;}head.next = list1 != null ? list1 : list2;return newList.next;}
}

2.自底向上直接合并 实现归并排序,达到空间复杂度O(1)的要求

将归并排序改造成迭代实现,可以通过一个变量维护需要排序的子链表的长度,这样就知道该在哪里cut、该在哪里merge,当该变量>=链表长度时,排序完成。

class Solution {public ListNode sortList(ListNode head) {if (head == null || head.next == null) return head;// 统计链表长度int length = 0;ListNode node = head;while (node != null) {length++;node = node.next;}ListNode dummy = new ListNode(0, head);// 子链表长度,从 1 开始合并,每次翻倍。(这个 for 循环主要是增大两个合并数组的数组长度)for (int subLength = 1; subLength < length; subLength <<= 1) {ListNode prev = dummy;  // prev 用于连接合并后排序好的链表,相当于记录结果ListNode cur = dummy.next;  // cur 记录拆分链表的位置// 每次遍历整条链表,将链表拆分成若干个长度为 subLength 的子链表,然后合并。(这个 while 循环才是真正的拆分合并)while (cur != null) {// 1. 拆分subLength长度的链表1ListNode head_1 = cur;      // 第一个链表的头节点// 找到第一个链表的尾结点,拆分出长度为subLength的链表1,// cur.next != null是为了防止下面的head_2 = cur.next(cur=null报错),或者也可以像下面next一样先判断一下cur != nullfor (int i = 1; i < subLength && cur != null && cur.next != null; i++) {cur = cur.next;}// 2. 拆分subLength长度的链表2ListNode head_2 = cur.next;     // 第二个链表的头结点,即链表1尾部的nextcur.next = null;        // 断开第一个链表和第二个链表的连接cur = head_2;       // 第二个链表的头节点,重新赋给cur,继续寻找第二个链表的尾结点// 寻找第二个链表的尾结点,再拆分出长度为subLen的链表2for (int i = 1; i < subLength && cur != null && cur.next != null; i++) {cur = cur.next;}// 3. 断开第二个链表和剩下链表的连接ListNode next = null;   // next 为剩下链表的头结点(即拆分完两个链表后第二个链表结束位置的next)// 第二个链表的尾结点可能为空,不为空时才能更新next,所以不能直接 next = cur.next;if (cur != null) {next = cur.next;cur.next = null;    // 断开第二个链表和剩下链表的连接}// 到这里,已经拆分完毕了,head_1、head_2 都为一条单独的链表,next 为剩下未拆分的链表// 4. 合并两个subLength长度的有序链表ListNode merged = mergeTwoLists(head_1, head_2);prev.next = merged;     // prev.next 指向排序好的链表,连接结果// 将prev移动到subLength × 2 的位置,以连接下一次合并的结果while (prev.next != null) {prev = prev.next;}cur = next;     // 将剩余链表next赋给cur,继续下一次的拆分(循环合并剩下的链表)}}return dummy.next;}// 题21. 合并两个有序链表private ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode cur = dummy;while (l1 != null && l2 != null) {if (l1.val < l2.val) {cur.next = l1;l1 = l1.next;} else {cur.next = l2;l2 = l2.next;}cur = cur.next;}cur.next = l1 == null ? l2 : l1;return dummy.next;}
}

(该代码来自leetcode题解评论区,注释详尽)

18.146.LRU缓存

模式识别:出现键和值,且时间复杂度要求O(1),考虑使用哈希表。

为了实现O(1)时间内插入、删除,需要使用双向链表。

为了实现O(1)时间内查找,需要使用到哈希表,且哈希表的key应当存储链表的位置,便于在O(1)时间内定位。

Java中有类似的数据结构,LinkedHashMap,但面试时一般期望面试者自己实现,而不是使用已有的api

class LRUCache extends LinkedHashMap<Integer,Integer>{private final int capacity;public LRUCache(int capacity) {super(capacity,0.75F,true);this.capacity = capacity;}public int get(int key) {return super.getOrDefault(key,-1);}public void put(int key, int value) {super.put(key,value);}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

自定义链表节点实现

class LRUCache  {private int size;private int capacity;Map<Integer,DLinkedNode> cache = new HashMap<>();DLinkedNode head;DLinkedNode tail;class DLinkedNode{DLinkedNode prev;DLinkedNode next;int key;int value;DLinkedNode(){}DLinkedNode(int key,int value){this.key = key;this.value = value;}}public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}public int get(int key) {DLinkedNode node = cache.get(key);if(node == null){return -1;}else{removeNode(node);addToHead(node);return node.value;}}public void put(int key, int value) {DLinkedNode node = cache.get(key);if(node == null){DLinkedNode newNode = new DLinkedNode(key,value);cache.put(key,newNode);addToHead(newNode);size++;if(size > capacity){DLinkedNode tail = removeTail();cache.remove(tail.key);size--;}}else{node.value = value;removeNode(node);addToHead(node);}}public void removeNode(DLinkedNode node){node.prev.next = node.next;node.next.prev = node.prev;}public void addToHead(DLinkedNode node){node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}public DLinkedNode removeTail(){DLinkedNode node = tail.prev;removeNode(node);return node;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

HashMap的查找、链表的增加、删除时间复杂度均为O(1),总的时间复杂度O(1)

空间复杂度O(n)

19.环形链表II

1、使用HashMap记录所有访问到的节点,当遇到第一个重复的节点时,这个节点就是入环结点。

时间复杂度O(n),空间复杂度O(n)

2、快慢指针

快慢指针同时出发,如果有环,最终在环内相遇

假设在紫色处相遇,那么慢指针走了a+b步,快指针走了a+b+n*(b+c)步。

又由于 2*(a+b) = a+b+n*(b+c)

得到 a  = (n-1) * (b+c) + c

从相遇点到入环点的距离 再加上若干倍环长,恰好等于从出发点到入环点的距离。那么从相遇开始,派出一个慢指针2从出发点出发,最终两个慢指针会在入环点相遇。

/*** 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(fast == slow) {ListNode slow2 = head;while(slow != slow2){slow = slow.next;slow2 = slow2.next;}return slow;}}return null;}
}

20.141.环形链表

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head, slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){return true;}}return false;}}


http://www.mrgr.cn/news/62650.html

相关文章:

  • 安全日志记录的重要性
  • 基于SSM+微信小程序的汽车维修管理系统(汽车5)
  • C语言日记 2024年10月31日
  • 图书管理系统汇报
  • 代码随想录day15 二叉树(3)
  • crc16 with word byte--查表法
  • Irqbalance处理中断迁移过程
  • [c++高阶]二叉搜索树深度剖析
  • 如何进行商标注册?
  • Vivo开奖了,劝退价。。
  • 【Nextcloud】在 Ubuntu 22.04.3 LTS 上的 Nextcloud Hub 8 (29.0.0) 优化
  • 你的Mac book多久没有清洁键盘屏幕了,Mac清洁好帮手来了
  • 学习算力网络必会关键词
  • 哈希表应用(位图和布隆过滤器)
  • HTB-Cicada 靶机笔记
  • ETL处理全流程
  • Linux 命令解释器-shell
  • stm32入门教程--USART外设 超详细!!!
  • Linux:线程池
  • qt QSlider详解
  • 软设每日打卡——折半查找二叉判定树、平衡二叉树
  • 多线程案例---单例模式
  • 2024年NSSCTF秋季招新赛-WEB
  • Convolution 卷积
  • 前端笔面试查漏补缺
  • 鸿蒙系统:核心特性、发展历程与面临的机遇与挑战