题意整理 设计一个缓存结构，实现set、get功能。 set(key, value)：将记录(key, value)插入该结构。get(key)：返回key对应的value值。 缓存结构中最多存放k条记录，如果超过k条记录，则根据策略删掉一条记录。 删除策略为：删掉调用次数最少的记录，如果调用次数最少的记录有多条，则删掉上次调用发生最早的key。 方法一（双哈希表） 1.解题思路 首先定义两个Map，分别记为cache和freqMap。cache用于存储缓存，键为缓存的键，值为key、value组成的Node，freqMap用于存储频次，键为某个Node调用次数，值为对应频次的双向链表。...

题意整理 编写一个函数来验证输入的字符串是否是有效的IPv4或IPv6地址。 IPv4地址由4个十进制数表示，它们之间用"."隔开，每个数的范围在0-255。并且非0整数，不能以0开头。 IPv6地址由8组16进制的数字来表示，每组表示16比特。这些组数字通过":"隔开。不能存在某一组为空，或者等于0，但是却不止一个0. 方法一（模拟） 1.解题思路 首先需要根据分隔符，对输入字符串进行分割。含有"."的，判断是否是IPv4地址。含有":"的，判断是否是IPv6地址。 对于IPv4的判断，分割之后，如果不是4组，返回"Neither"。如果某一组的字符不是全部由'0'-'9'范围内字符组...

题意整理 写一个函数StrToInt，实现把字符串转换成整数的功能。 不能直接使用库函数。 字符串可能以空格+正负号+字符串表达式（数字、字母、负号、空格）+空格的形式出现。 方法一（模拟） 1.解题思路 首先去掉首尾空格。 然后转化为字符数组，便于后续遍历。定义一个变量用于标记第一个位置是否为负号。 接着开始遍历字符数组，只要当前字符不在'0'-'9'范围内，直接终止循环。每次都将对应字符加在结果上，如果大于边界值，返回最大的Integer型整数或最小的Integer型整数。（这里对越界的处理看似没有考虑最小的Integer型整数，其实这种情况对应也会返回最小的Integer型整数，只...

题意整理 给定一个1到n的排列和一个栈，并按照排列顺序入栈。 在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列。 方法一（动态规划） 1.解题思路 首先新建一个栈，用于存放按顺序入栈的元素。 再新建一个dpdpdp数组，dp[i]dp[i]dp[i]表示当前元素以及后面出现元素中的最大值。逆向遍历原序列，给dpdpdp数组赋值。 然后正向遍历dpdpdp数组，将当前元素入栈，只要栈顶元素比后面所有元素都大，则直接出栈，保证大的值尽量在序列前面。 最后还在栈中的元素，按先进后出的顺序赋给结果数组。 图解展示： 2.代码实现 import java.util....

题意整理 给出一个长度为n的，仅包含字符'('和')'的字符串，计算最长的格式正确的括号子串的长度。 格式正确的括号子串是指每一个左右括号都能相互抵消掉。 方法一（栈） 1.解题思路 首先新建一个栈，用于存放出现左括号字符对应的下标。 遍历字符串，如果当前是左括号，直接将下标入栈。如果是右括号，弹出栈顶元素，此时栈不为空的化，更新格式正确的括号子串长度，取较大者；如果为空，则重置子串起点。 图解展示： 2.代码实现 import java.util.*; public class Solution { /** * * @param s string字符...

题意整理 给定一个十进制数M，将M转换为N进制数。 N大于10时，应在结果中使用大写字母表示大于10的一位，如'A'表示此位为10。 如果M为负数，结果中要保留负号。 方法一（利用库函数） 1.解题思路 首先利用java自带的库函数，将M转化为N进制数。 由于结果中大于10的部分是以小写字母表示的，再通过toUpperCase函数转化为大写字母形式。 2.代码实现 import java.util.*; public class Solution { /** * 进制转换 * @param M int整型 给定整数 * @param N int整...

题意整理 给定一棵树，求出这棵树的直径，即树上最远两点的距离。 方法一（dfs） 1.解题思路 首先初始化邻接表，以边的起点为索引，将对应的边的终点以及边的权值放在该索引对应的list里。 先从0号节点进入递归，通过递归找到当前节点所能到达的最远节点，跟新最远节点的规则是路径权值和大于之前的权值和。 然后再从最远节点处继续进入递归体，寻找最大路径权值和。 动图展示： 2.代码实现 import java.util.*; /* * public class Interval { * int start; * int end; * } */ public class...

题意整理 给定一个整数数组，找出数组中第 k 大的数。 方法一（利用小顶堆） 1.解题思路 首先定义一个小顶堆。 然后将前k个元素直接加入到小顶堆。 遍历后续每一个元素，如果比堆顶元素大，则可能是前k大的元素，加入小顶堆，并弹出堆顶元素。否则，直接跳过。 2.代码实现 import java.util.*; public class Solution { public int findKth(int[] a, int n, int K) { //定义一个小顶堆 PriorityQueue<Integer> queue=new Pri...

题意整理 给定一个数组arr，求arr数组的最长上升子序列。 可能存在多个最长上升子序列，取字典序最小的那一个。 方法一（动态规划） 1.解题思路 状态定义：dp[i]dp[i]dp[i]表示以i位置元素结尾的最长上升子序列长度。 状态初始化：以每个位置结尾的上升子序列长度至少为1。 状态转移：遍历arr数组，假设当前位置为i，比较当前位置i之前的每一个元素与当前位置元素的大小，如果小于当前位置元素arr[i]arr[i]arr[i]，说明可以接在arr[i]arr[i]arr[i]前面。即dp[i]=Math.max(dp[i],dp[j]+1)dp[i]=Math.max(dp[i]...

题意整理 给定整数n作为楼层数，再给定整数k作为棋子数。 如果想找到棋子不会摔碎的最高层数，考虑最差的情况下，至少需要扔多少次棋子。 方法一（暴力递归） 1.解题思路 递归终止条件：0层时，不需要确定，返回0次；一枚棋子时，需要一个一个地试，返回n。 递归如何推进：假设当前为第i层，要么棋子碎了，需要扔dfs(i-1,k-1)+1次,要么棋子没碎，需要扔dfs(n-i,k)+1次，取较大者。并且统计所有层的情况，取最小的次数。 每一层返回什么：返回当前层的最小次数。 当层数n较大时，这种方法会报栈深度溢出的错误。 2.代码实现 import java.util.*; pu...

题意整理 给定一个有序矩阵mat和待查找元素x，矩阵的行和列都是从小到大有序的。 求x在矩阵中的位置，以二元数组的形式返回。 方法一（二分） 1.解题思路 遍历所有行，对每一行所有元素进行二分查找。 如果找到，直接返回。如果小于x，则排除左边所有元素。如果大于x，则排除右边所有元素。 2.代码实现 import java.util.*; public class Solution { public int[] findElement(int[][] mat, int n, int m, int x) { //遍历所有行 for(int i=0;...

题意整理 已知一只青蛙一次可以跳上1级台阶，也可以跳上2级。 求该青蛙跳上一个n级的台阶总共有多少种跳法。 方法一（迭代） 1.解题思路 本题是一个基本的递归问题，假设跳上n级台阶有f(n)f(n)f(n)中跳法，则跳上n-1级、n-2级分别有f(n−1)f(n-1)f(n−1)、f(n−2)f(n-2)f(n−2)种跳法。青蛙既可以从n-1级台阶跳到n级，也可以从n-2级台阶跳到n级，所以有f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2)f(n)=f(n−1)+f(n−2)。使用递归很容易实现，但是当n很大时，递归栈的深度也会很大，可能报栈深度溢出的错误。并且中间...

题意整理 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。 方法一（递归） 1.解题思路 由于二叉搜索树的中序遍历是从小到大依次输出的，所以可以利用中序遍历，在遍历的过程中，逐个改变当前节点的指向。 预先定义一个pre指针，指向当前节点的前一个节点。以及一个head指针指向头节点。 当pre为空时，可以确定当前节点为双向链表的头节点head。其它情况下则可以将pre的后继指向当前节点cur。 遍历过程中，对于每一个cur，都应将其前驱指向pre。同时不断跟新pre。最后返回head即可。 图解展示： 2.代码实现 /** public class TreeNode { ...

题意整理 输入一组整数序列I和一组规则整数序列R。 根据条件找出满足规则Ri的I，并按指定格式输出。 需要预先对R进行排序和去重，然后对于每一个Ri，找出所有包含Ri的I，依次输出I的个数、I的索引以及I。最后需要在输出结果之前，先输出结果中包含多少整数。 方法一（TreeSet） 1.解题思路 首先对规则序列进行排序和去重，处理后的数据放在set中。 遍历整个set，对于每一个Ri，记录满足条件的I的个数，以及记录满足条件的I的索引和I。如果I的个数大于0，则将对应的规则数字Ri、I的个数、索引、I加入到res。 最后统计整个结果有多少个整数输出。按顺序输出整数个数和res。 图解展...