【面试算法题总结14】空间换时间，时间换空间算法

HashMap保存前缀和，以及其出现次数

class Solution {public int subarraySum(int[] nums, int k) {int result=0;Map<Integer,Integer> map=new HashMap<Integer,Integer>();int sum=0;map.put(0, 1);for(int i=0;i<nums.length;++i){sum+=nums[i];int need=sum-k;if(map.containsKey(need)){result+=map.get(need);}map.put(sum,map.getOrDefault(sum,0)+1);}return result;}
}

例题2的二叉树版本：
主要学习的题解：https://leetcode-cn.com/problems/path-sum-iii/solution/dui-qian-zhui-he-jie-fa-de-yi-dian-jie-s-dey6/

1 前缀和：一个节点的前缀和就是该节点到根之间的路径和
2 HashMap的key是前缀和， value是该前缀和的节点数量，记录数量是因为有出现复数路径的可能
3 本质还是空间换时间，保存各种前缀和出现的次数。
即：要寻找的前缀和=根节点到当前节点的路径和-targetSum

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int wholeTargetSum;Map<Integer,Integer> map;public int pathSum(TreeNode root, int targetSum) {wholeTargetSum=targetSum;map=new HashMap<>();map.put(0,1);    //十分重要的一行，不然就不能从根节点开始算了return dfs(root,0);}public int dfs(TreeNode root,int pre){if(root==null){return 0;}int pathSum=pre+root.val;   //获取节点到当前节点root的路径和pathSumint needPrefix=pathSum-wholeTargetSum;  //得到需要的前缀和needPrefixint count=map.getOrDefault(needPrefix,0);   //得到needPrefix对应次数/*添加该前缀和到map中，给子节点使用这行代码不能放在 int count=map.getOrDefault(needPrefix,0); 之前，因为路径不能不包括任何节点*/map.put(pathSum,map.getOrDefault(pathSum,0)+1);    count+=dfs(root.left,pathSum);count+=dfs(root.right,pathSum);map.put(pathSum,map.get(pathSum)-1);  //去除这个前缀和对应的次数return count;}
}

如输入[1，2，3，4，5]，输出6

public static int solution(int[] A) {int n = A.length;int[] min = new int[n];min[1] = A[1];for (int i = 2; i < n; i++) {min[i] = Math.min(min[i - 1], A[i]);}int ans = Integer.MAX_VALUE;for (int i = 3; i <= n - 2; i++) {ans = Math.min(ans, A[i] + min[i - 2]);}return ans;}

这题以空间换时间，还用的是本来就有的空间，真的是省到了极值

class Solution {public int findRepeatNumber(int[] nums) {for(int i=0;i<nums.length;++i){while(nums[i]!=i){if(nums[nums[i]]==nums[i]){return nums[i];}int temp=nums[nums[i]];nums[nums[i]]=nums[i];nums[i]=temp;}}return -1;}
}

class Solution {public char firstUniqChar(String s) {Map<Character,Integer> map=new HashMap<>();for(int i=0;i<s.length();++i){map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);}for(int i=0;i<s.length();++i){if(map.get(s.charAt(i))==1){return s.charAt(i);}}return ' ';}
}

哈希链表：双向链表+map做到O(1)查找和删除添加

class LRUCache {int cap;LinkedHashMap<Integer,Integer> cache=new LinkedHashMap<>();public LRUCache(int capacity) {this.cap=capacity;}public int get(int key) {if(!cache.containsKey(key)){return -1;}//key变为最近使用makeRecently(key);return cache.get(key);}public void put(int key, int value) {if(cache.containsKey(key)){//修改key值cache.put(key,value);//将key变为最近使用makeRecently(key);return;}if(cache.size()>=this.cap){//链表头部就是最久未使用的keyint oldestKey=cache.keySet().iterator().next();cache.remove(oldestKey);}//将最新的key添加到链表尾部cache.put(key,value);}private void makeRecently(int key){int val=cache.get(key);//删除key，重新插入到队尾cache.remove(key);cache.put(key,val);}}

淘汰访问频次最低的数据，如果有多条，需要淘汰最旧的数据

class LFUCache {HashMap<Integer,Integer> keyToVal;HashMap<Integer,Integer> keyToFreq;HashMap<Integer,LinkedHashSet<Integer>> freqToKeys;//记录最小的频次int minFreq;int cap;public LFUCache(int capacity) {keyToVal=new HashMap<>();keyToFreq=new HashMap<>();freqToKeys=new HashMap<>();this.cap=capacity;this.minFreq=0;}public int get(int key) {if(!keyToVal.containsKey(key)){return -1;}//增加key对应的freqincreaseFreq(key);return keyToVal.get(key);}public void put(int key, int value) {if(this.cap<=0)return;//如果key已存在，修改对应的val即可if(keyToVal.containsKey(key)){keyToVal.put(key,value);increaseFreq(key);return;}//如果key不存在，需要插入if(this.cap<=keyToVal.size()){removeMinFreqKey();}//插入key和value，对应的freq为1keyToVal.put(key,value);keyToFreq.put(key,1);freqToKeys.putIfAbsent(1,new LinkedHashSet<>());freqToKeys.get(1).add(key);this.minFreq=1;}private void removeMinFreqKey(){//freq最小的key列表LinkedHashSet<Integer> keyList=freqToKeys.get(this.minFreq);//其中最先被插入的那个key就是该被淘汰的keyint deletedKey=keyList.iterator().next();keyList.remove(deletedKey);if(keyList.isEmpty()){freqToKeys.remove(this.minFreq);}//更新KV表keyToVal.remove(deletedKey);//更新KF表keyToFreq.remove(deletedKey);}private void increaseFreq(int key){int freq=keyToFreq.get(key);//更新KF表keyToFreq.put(key,freq+1);//更新FK表//将key从freq对应的列表中删除freqToKeys.get(freq).remove(key);//将key加入freq+1对应的列表中freqToKeys.putIfAbsent(freq+1,new LinkedHashSet<>());freqToKeys.get(freq+1).add(key);//如果freq对应的列表空了，移除这个freqif(freqToKeys.get(freq).isEmpty()){freqToKeys.remove(freq);//如果这个freq恰好是minFreq，更新minFreqif(freq==this.minFreq){++this.minFreq;}}}
}/*** 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);*/

优雅永不过时

class Solution {public int maxProfit(int[] prices) {int n=prices.length;int minNum=prices[0];int result=0;for(int i=1;i<n;++i){if(prices[i]<minNum){minNum=prices[i];}else if(result<prices[i]-minNum){result=prices[i]-minNum;}}return result;}
}

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> set=new HashSet<>();for(Integer num:nums){set.add(num);}int result=0;for(Integer num:set){if(!set.contains(num-1)){int currentNum=num;int currentResult=1;while(set.contains(currentNum+1)){++currentNum;++currentResult;}if(currentResult>result){result=currentResult;}}}return result;}
}