IP地址划分 问题陈述 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。 12输入：s = "25525511135"输出：["255.255.11.135","255.255.111.35"] 思路分析 12345678910111213141516171819202122232425262728293031323334353637public class Solution{ //主函数 public List<Integer> restoreIPAdress(String s){ List<String> address=new ArrayList<>(); StringBuilder res=new StringBuilder(); doRestore(0,add ...

LRU缓存机制 问题陈述 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。 获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。 你是否可以在 O(1) 时间复杂度内完成这两种操作？ 思路分析 要让put和get操作的时间复杂度为O(1)，我们可以总结出 cache 这个数据结构必要的条件：查找快，插入快，删除快，有顺序之分。 通常哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表。 LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样： 代码实现 1、首先我们设计双链表的结点类，假定key和val都 ...

乘积最大子数组 问题陈述 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 思路分析 我们只要记录前i的最小值, 和最大值, 那么 dp[i] = max(nums[i] * pre_max, nums[i] * pre_min, nums[i]), 这里0 不需要单独考虑, 因为当相乘不管最大值和最小值,都会置0 代码实现 代码实现 1234567891011121314class Solution{ public int maxProduct(int[] nums){ int preMin=nums[0],preMax=nums[0],res=nums[0]; int temp1=0,temp2=0; for(int i=1;i<nums.length;i++){ temp1=preMin*nums[i];//若之前为负数，当前数也为负数 temp2=preMax*num ...

打家劫舍 问题陈述 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路分析 首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。 如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第k (k>2) 间房屋，有两个选项： 1、偷窃第 k间房屋，那么就不能偷窃第 k-1 间房屋，偷窃总金额为前 k-2间房屋的最高总金额与第 k 间房屋的金额之和。 2、不偷窃第 k间房屋，偷窃总金额为前 k-1间房屋的最高总金额。 在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。 用 dp[i]表示前 i 间房屋能偷窃到的最高总金 ...

岛屿数量 问题陈述 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 输入: [ [‘1’,‘1’,‘0’,‘0’,‘0’], [‘1’,‘1’,‘0’,‘0’,‘0’], [‘0’,‘0’,‘1’,‘0’,‘0’], [‘0’,‘0’,‘0’,‘1’,‘1’] ] 输出: 3 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。 12345678910111213141516171819202122class Solution{ public int numsIslands(char[][] grid){ int count=0; for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ if(gr ...

环形链表 问题陈述 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 方法一：（哈希表） 1234567891011121314class Solution{ public ListNode detectCycle(ListNode head){ Set<ListNode> visited=new HashSet<>(); ListNode node=head; while(node!=null){ if(visited.contains(node)){ return node; } visited.add(node); node=node ...

排序链表 问题陈述 思路分析 递归实现链表归并排序 1、分割 找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）； 我们使用 fast,slow 快慢双指针法，链表有奇数个节点找到中点，偶数个节点找到中心左边的节点。 找到中点 slow 后，执行 slow.next = None 将链表切断。 递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。 cut 递归终止条件： 当head.next == None时，说明只有一个节点了，直接返回此节点。 2、合并 将两个排序链表合并，转化为一个排序链表 双指针法合并，建立辅助ListNode h 作为头部。 设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。 返回辅助ListNode h 作为头部的下个节点 h.next。 时间复杂度 O(l + r)，l, r 分别代表两个链表长度。 代码实现 1234567891011121314 ...

旋转链表 问题陈述 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 示例 1: 1234567输入: 0->1->2->NULL, k = 4输出: 2->0->1->NULL解释://每次右旋，相当于把末尾元素移到前面来。向右旋转 1 步: 2->0->1->NULL向右旋转 2 步: 1->2->0->NULL向右旋转 3 步: 0->1->2->NULL向右旋转 4 步: 2->0->1->NULL 思路分析 我们的直觉是先把链表闭合成环，然后找到相应的位置断开，确定新的头尾。 新的链表头位置：(n - k % n) 新的链表尾位置：(n - k % n - 1) 代码实现 12345678910111213141516171819202122class Solution{ public ListNode rotateRight(ListNode head,int k){ if(head== ...

子集 问题陈述 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 **说明：**解集不能包含重复的子集。 示例： 123456789101112输入: nums = [1,2,3]输出:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []] 思路实现 回溯 123456789101112131415161718192021public class Solution{ public List<List<Integer>> subSet(int[] nums){ List<List<Integer>> subsets=new ArrayList<>(); List<Integer> curSubset=new ArrayList<>(); for(int size=0;size<nums.length;size++){//对每个s ...

最大正方形 问题陈述 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 输出: 4 思路分析 动态规划的思想，你能想明白吗哈哈 我们用 dp(i, j)表示以 (i, j) 为右下角，且只包含 1 的正方形的边长最大值。如果我们能计算出所有 dp(i, j) 的值，那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。 那么，怎么确定dp(i, j)呢 如果该位置的值是 0，则 dp(i, j) = 0，因为当前位置不可能在由 1组成的正方形中； 如果该位置的值是 1，则 dp(i, j) 的值由其上方、左方和左上方的三个相邻位置的 dp值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下： dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1 别忘了考虑边界情况 虑边界条件。如果 i 和 j 中至少有一个为 0，也就是第一行和 ...