给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。
输入：
1 | "abc","adc",5,3,2 |
返回值：
1 | 2 |
输入：
1 | "abc","adc",5,3,100 |
返回值：
1 | 8 |
$1 \leq |str_1|, |str_2| \leq 50001≤∣str1∣,∣str2∣≤5000$
$1 \leq ic, dc, rc \leq 100001≤ic,dc,rc≤10000$
1 | import java.util.*; |
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
示例 1：
1 | 输入：word1 = "horse", word2 = "ros" |
示例 2：
1 | 输入：word1 = "intention", word2 = "execution" |
提示：
0 <= word1.length, word2.length <= 500word1 和 word2 由小写英文字母组成1 | class Solution { |
一个缓存结构需要实现如下功能。
但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；
如果调用次数最少的key有多个，上次调用发生最早的key被删除
这就是LFU缓存替换算法。实现这个结构，K作为参数给出
[要求]
set和get方法的时间复杂度为O(1)
若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，输出一个答案
输入：
1 | [[1,1,1],[1,2,2],[1,3,2],[1,2,4],[1,3,5],[2,2],[1,4,4],[2,1]],3 |
返回值：
1 | [4,-1] |
说明：在执行”1 2 4”后，”1 1 1”被删除。因此第二次询问的答案为-1
$1 \leq k \leq n \leq 10^5$
$-2 \times 10^9 \leq x,y \leq 2 \times 10^9$
import java.util.*;
public class Solution {
/**
* lfu design
* @param operators int整型二维数组 ops
* @param k int整型 the k
* @return int整型一维数组
*/
class LFUCache{
class Node{
int k;
int val;
int freq;
public Node(){}
public Node(int k, int val, int freq){
this.k = k;
this.val = val;
this.freq = freq;
}
}
private int capacity;
private Map<Integer, Node> map = new HashMap<>();
private Map<Integer, LinkedList<Node>> freqMap = new HashMap<>();
private int minFreq;
public LFUCache(int capacity){
this.capacity = capacity;
this.minFreq = 1;
}
public void update(Node node){
LinkedList<Node> list = freqMap.get(node.freq);
list.remove(node);
if (list.isEmpty() && node.freq == minFreq){
minFreq++;
}
node.freq++;
if (!freqMap.containsKey(node.freq)){
freqMap.put(node.freq, new LinkedList<>());
}
freqMap.get(node.freq).addLast(node);
}
public int get(int k){
if (!map.containsKey(k)){
return -1;
}
Node node = map.get(k);
update(node);
return node.val;
}
public void put(int k, int val){
if (map.containsKey(k)){
Node node = map.get(k);
node.val = val;
update(node);
map.put(k, node);
return;
}
if (map.size() == capacity){
Node node = freqMap.get(minFreq).removeFirst();
map.remove(node.k);
}
Node node = new Node(k, val, 1);
map.put(k, node);
if (!freqMap.containsKey(1)){
freqMap.put(1, new LinkedList<>());
}
freqMap.get(1).addLast(node);
minFreq = 1;
}
}
public int[] LFU (int[][] operators, int k) {
// write code here
LFUCache cache = new LFUCache(k);
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < operators.length; i++){
if (operators[i][0] == 1){
cache.put(operators[i][1], operators[i][2]);
}else{
res.add(cache.get(operators[i][1]));
}
}
int[] ans = new int[res.size()];
for (int i = 0; i < ans.length; i++){
ans[i] = res.get(i);
}
return ans;
}
}
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
示例 1：
1 | 输入：root = [1,2,2,3,4,4,3] |
示例 2：
1 | 输入：root = [1,2,2,null,3,null,3] |
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出：
4
/ \
7 2
/ \ / \
9 6 3 1
示例 1：
1 | 输入：root = [4,2,7,1,3,6,9] |
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1：
1 | 输入：A = [1,2,3], B = [3,1] |
示例 2：
1 | 输入：A = [3,4,5,1,2], B = [4,1] |
限制：
1 | 0 <= 节点个数 <= 10000 |
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
1 | 输入：1->2->4, 1->3->4 |
限制：
1 | 0 <= 链表长度 <= 1000 |
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
1 | 输入: 1->2->3->4->5->NULL |
限制：
1 | 0 <= 节点个数 <= 5000 |
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
1 | 给定一个链表: 1->2->3->4->5, 和 k = 2. |
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
1 | 输入：nums = [1,2,3,4] |
提示：
0 <= nums.length <= 500001 <= nums[i] <= 10000