import java.util.*; public class Solution { /** * 把数字翻译成字符串 * 有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。 * 现在给一串数字，返回有多少种可能的译码结果 * <p> * 思路： * <p> * 对于普通数组1-9，译码方式只有一种，但是对于11-19，21-26，译码方式有可选择的两种方案，因此我们使用动态规划将两种方案累计。 * <p> * 具体做法： * <p> * step 1：用辅助数组dp表示前i个数的译码方法...

import java.util.*; public class Solution { /** * 矩阵的最小路径和 * 动态规划，问题拆解： * 1.确定状态：dp[i][j]表示到达(i,j)的最小路径和, 状态转移方程：dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + matrix[i][j] * 2.初始化： * if i ==0 && j ==0 dp[0][0] = matrix[0][0]; * if i == 0 dp[i][j] = dp[i-1][j] + matrix[i][j] ; * if j == 0 dp[i...

import java.util.*; public class Solution { // LFU缓存 Map<Integer, Element> lfuMap = new HashMap<>(); //频次对应的链表，链表的头结点为最热结点，尾结点为最不热结点 Map<Integer, LinkedList<Element>> freqMap = new HashMap<>(); //最小频次,用来定位需要删除的缓存 int minFrequency = 1; public int[] LFU(int[][] operators,...

import java.util.*; public class Solution { /** * 定义 dp[i][j] 表示 str1前 i 个字符 和 str2前 j 个字符的公共子序列长度 * 分解：1. str1[i] = str2[j] 的情况，即 dp[i][j] = dp[i - 1][j - 1] + 1 * 2. str1[i] != str2[j] 的情况，即 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) * 然后回溯子序列，从两个串的最后一个字符开始 * 如果 str1[i] = str2[j]，则包含在子序列里，向左上角移动 *...

import java.util.*; public class Solution { /** * 最长公共子串, 动态规划 * 定义 dp[i][j]表示以 str1[i] 和 str2[j] 结尾的最长公共子串的长度, * 如果str1[i] != str2[j], 那么 dp[i][j] = 0; 否则 dp[i][j] = dp[i-1][j-1] + 1; * 在计算的过程中记录最大公共子串的长度，并记录最大子串的结束位置 */ public String LCS(String str1, String str2) { int[][] dp = new int[str1.length...

import java.util.*; public class Solution { /** * 到达第 n 级台阶的花费有两种情况 1.从第 n-1级台阶来，费用等于到达 n-1级台阶的花费 + cost[n-1];2.从第 n-2 级台阶来，费用等于到达 n-2 级台阶的花费 + cost[n-2],求两者最小值 * minCost(n) = Math.min(minCost(n-1) + cost(n-1),minCost(n-2) + cost(n-2))，所以可以递归求解 * <p> * 另外可以使用一个数组来记录已经计算过的值，避免重复计算 * arr[0] = 0、...

import java.util.*; public class Solution { /** * 跳 n 级台阶的方法数 等于跳 n-1级台阶方法数 + 跳 n-2 级台阶方法数 * 我们可以用递归求解，也可以用动态规划求解 * 递归就是 f(n) = f(n-1) + f(n-2) * 动态规划就是维护一个数组来保存中间结果，从 n=1 开始，到 n=number 结束 */ public int jumpFloor(int number) { if (number <= 1) { return 1; } int[] arr = new int[50]; arr[0] = 1; ar...

import java.util.*; public class Solution { /** * 先求跳两级台阶最多的次数，对应跳一级台阶最少的次数，这个时候求一个组合数 * 接着减少跳两级台阶的次数，跳一级台阶的次数就增加 2，这个时候再求一个组合数 * 直到跳两级台阶的次数为 0，就一种组合 * 将以上所有组合数相加就是 结果 */ public int jumpFloor(int number) { int maxTwoJumpNum = number / 2; int minOneJumpNum = number - maxTwoJumpNum * 2; Long total = 0...

import java.util.*; public class Solution { int[] arr = new int[50]; public int Fibonacci(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } arr[0] = 0; arr[1] = 1; arr[2] = 1; for (int i = 2; i <= n; i++) { arr[i] = arr[i - 1] + arr[i - 2]; } return arr[n]; } }

import java.util.*; public class Solution { int[] arr = new int[50]; public int Fibonacci(int n) { if (n == 1 || n == 2) { return 1; } arr[n - 1] = Fibonacci(n - 1); arr[n - 2] = Fibonacci(n - 2); return arr[n - 1] + arr[n - 2]; } }

import java.util.*; public class Solution { /** * 1 2 3 * 4 5 6 * 7 8 9 * <p> * 7 4 1 * 8 5 2 * 9 6 3 * <p> * 旋转矩阵，实际是将(i,j)位置的元素放到了新位置(j,n-1-i) */ public int[][] rotateMatrix(int[][] mat, int n) { int[][] newMat = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n;...

import java.util.*; public class Solution { Map<Integer, KeyOperate> lfuMap; LinkedList<KeyOperate> keyOperateList; int size; public Solution(int capacity) { // write code here lfuMap = new HashMap<>(capacity); keyOperateList = new LinkedList<>(); size = capacity; } public in...

import java.util.*;public class Solution {//设置节点结构static class Node{int freq;int key;int val;//初始化public Node(int freq, int key, int val) {this.freq = freq;this.key = key;this.val = val;}}//频率到双向链表的哈希表private Map<Integer, LinkedList<Node> > freq_mp = new HashMap<>();//key到节点的哈希表pri...

import java.util.*; public class Solution { /** * 贪心算法 * <p> * 不要将开始时间和结束时间作为一个整体看，先将开始时间和结束时间分开 * 将开始时间和结束时间分开并排序 * 先固定一个结束时间，遍历开始时间，如果开始时间小于结束时间，主持人就加 1 * 如果开始时间大于结束时间，就可以重复使用一个主持人，主持人数不变，将结束时间后移一个，接着遍历开始时间 */ public int minmumNumberOfHost(int n, int[][] startEnd) { if (n == 0 || startEnd ==...