力扣爆刷第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);*/