力扣爆刷第167天之TOP200五连刷101-105（二叉树序列化、验证IP、LFU）
力扣爆刷第167天之TOP200五连刷101-105（二叉树序列化、验证IP、LFU）
文章目录
一、224. 基本计算器
题目链接：https://leetcode.cn/problems/basic-calculator/description/
思路：实现计算器，这也是一个经典题目了，是逐步进阶的，比如只有加减法，有加减乘除，有括号，这是一步一步升级来的，对于只有加减乘除的题来说，使用一个栈来分情况吧数值压入栈中进行处理，需要提前维护一个符号位，是当前数值的前一个符号位，当再次遇到符号时，就是把前一个数压栈的时机，加减就压正负数，乘除需要出栈然后与当前数进行运算再压栈。对于有括号类型的题目，只需要遇到左括号直接递归，遇到右括号退出递归。此外要注意边界条件，如压栈的时机，排除空格以后，只要不是数值就得压栈，如果元素空了抵达字符串尾部了也需要压栈处理了，因为等不到下一个非数值符号了。
具体的可以参考拉不拉东：https://labuladong.online/algo/data-structure/implement-calculator/
class Solution {
public int calculate(String s) {
Deque<Character> queue = new LinkedList<>();
for(int i = 0; i < s.length(); i++) {
if(s.charAt(i) == ' ') continue;
queue.add(s.charAt(i));
}
return helper(queue);
}
int helper(Deque<Character> queue) {
int num = 0;
char sign = '+';
Deque<Integer> stack = new LinkedList<>();
while(!queue.isEmpty()) {
char c = queue.poll();
if(c >= '0' && c <= '9') num = num * 10 + (c - '0');
if(c == '(') num = helper(queue);
if(c < '0' || c > '9' || queue.isEmpty()){
if(sign == '+') stack.push(num);
else if(sign == '-') stack.push(-num);
else if(sign == '*') stack.push(stack.pop() * num);
else if(sign == '/') stack.push(stack.pop() / num);
num = 0;
sign = c;
}
if(c == ')') break;
}
int res = 0;
while(!stack.isEmpty()) {
res += stack.pop();
}
return res;
}
}
二、297. 二叉树的序列化与反序列化
题目链接：https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description/
思路：要求对二叉树进行序列化和反序列化，其实我们只需要按照任意一种遍历顺序，遍历一遍记录下来，当然要记录下来节点和null节点，转成字符串这就是序列化，然后再按照遍历的顺序再遍历一遍，在遍历的过程中构建树即可，就完成了反序列化。关键点是对于null节点的记录。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
StringBuilder builder = new StringBuilder();
String[] list;
int i = 0;
public String serialize(TreeNode root) {
traverse(root);
return builder.toString();
}
public TreeNode deserialize(String data) {
list = data.split(",");
return create(list);
}
void traverse(TreeNode root) {
if(root == null) {
builder.append("#,");
return;
}
builder.append(root.val + ",");
traverse(root.left);
traverse(root.right);
}
TreeNode create(String[] list) {
if(i == list.length || list[i].equals("#")) {
i++;
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(list[i++]));
node.left = create(list);
node.right = create(list);
return node;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
三、283. 移动零
题目链接：https://leetcode.cn/problems/move-zeroes/description/
思路：移动零也是很经典的题，可以通过双指针来做，但凡右指针遇到非零数就与左指针交换，然后左指针向右移动一下即可。
class Solution {
public void moveZeroes(int[] nums) {
int k = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] == 0) k++;
else {
int t = nums[i-k];
nums[i-k] = nums[i];
nums[i] = t;
}
}
}
}
四、468. 验证IP地址
题目链接：https://leetcode.cn/problems/validate-ip-address/description/
思路：验证是IPv4还是IPv6本身没有什么就要考虑的边界条件太多了，思路很简单。
1、首先通过".“和”:“的数量来判断是进行IPv4的判断还是进行IPv6的判断。
2、对于IPv4来说要从多个角度进行判断，包括用”.“分割后的字符串数量，单个字符串的长度，是否有前导零，是否数值超出255.
3、对于IPv6来说也是从多个角度判断，包括用”:"分割后的字符串的数量，单个字符串的长度，是否超出ffff或者FFFF。
class Solution {
public String validIPAddress(String queryIP) {
int a = 0, b = 0;
for(int i = 0; i < queryIP.length(); i++) {
if(queryIP.charAt(i) == '.') a++;
if(queryIP.charAt(i) == ':') b++;
if(a != 0 && b != 0) return "Neither";
}
if(a == 3) return isIPv4(queryIP);
else if(b == 7) return isIPv6(queryIP);
else return "Neither";
}
String isIPv4(String queryIP) {
String[] list = queryIP.split("\\.");
if(list.length < 4) return "Neither";
for(String s : list) {
if(s.length() > 1 && s.charAt(0) == '0' || s.length() == 0 || s.length() > 3) return "Neither";
int num = 0;
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(c < '0' || c > '9') return "Neither";
num = num * 10 + (c - '0');
}
if(num > 255) return "Neither";
}
return "IPv4";
}
String isIPv6(String queryIP) {
String[] list = queryIP.split(":");
if(list.length < 8) return "Neither";
for(String s : list) {
if(s.length() > 4 || s.length() == 0) return "Neither";
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if((c > 'f' && c <= 'z') || c > 'F' && c <= 'Z') return "Neither";
}
}
return "IPv6";
}
}
五、460. LFU 缓存
题目链接：https://leetcode.cn/problems/lfu-cache/description/
思路：对于LFU和LRU。
LRU是最近最少使用，容量满了会丢弃最早访问的元素，所以需要维护一个访问的顺序，这个模拟LinkedHashMap就可以实现。
LFU是最不经常使用，容量满了会丢弃使用频率最低的元素，如果有多个使用频率相同的元素，要丢弃最早添加的元素。所以LFU相对来说麻烦一些。
要使用LFU，需要几个条件：
1、记录key和value，使用hashmap：ktv;
2、记录key对应的频率，使用hashmap：ktf；
3、记录频率对应的有序元素集合，使用hashmap<Integer, LinkedHashSet> ： ftk。
维护好这三个集合即可。
class LFUCache {
HashMap<Integer, Integer> ktv = new HashMap<>();
HashMap<Integer, Integer> ktf = new HashMap<>();
HashMap<Integer, LinkedHashSet<Integer>> ftk = new HashMap<>();
int cap = 0;
int midFre = 0;
public LFUCache(int capacity) {
cap = capacity;
}
public int get(int key) {
if (!ktv.containsKey(key)) {
return -1;
}
int v = ktv.get(key);
up(key);
return v;
}
void up(int key) {
int f = ktf.get(key);
ktf.put(key, f+1);
ftk.get(f).remove(key);
ftk.putIfAbsent(f+1, new LinkedHashSet());
ftk.get(f+1).add(key);
if(ftk.get(f).isEmpty()) {
ftk.remove(f);
if(midFre == f) midFre++;
}
}
public void put(int key, int value) {
if(ktv.containsKey(key)) {
ktv.put(key, value);
up(key);
return;
}
if(ktv.size() == cap) {
int k = ftk.get(midFre).iterator().next();
ftk.get(midFre).remove(k);
if(ftk.get(midFre).isEmpty()) ftk.remove(midFre);
ktv.remove(k);
ktf.remove(k);
}
ktv.put(key, value);
midFre = 1;
ktf.put(key, 1);
ftk.putIfAbsent(1, new LinkedHashSet());
ftk.get(1).add(key);
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
原文地址：https://blog.csdn.net/qq_43511039/article/details/140633358
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！