title: leetcodedate: 2021-02-20 22:56:55
tags: leetcode
category: leetcode
summary: leetcode-重要题记
top: false
cover: true
author: 张文军

Java快速开发学习

锁清秋

LRU

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

  1. class LRUCache {
  2.     private Map<Integer, DoubleNode> map;
  3.     private Integer capacity;
  5.     public LRUCache(int capacity) {
  6.       this.capacity = capacity;
  7.       this.map = new HashMap<>(capacity);
  8.       this.head = new DoubleNode(-1, -1);
  9.       this.tail = new DoubleNode(-1, -1);
  10.       head.next = tail;
  11.       tail.pre = head;
  12.     }
  14.     public int get(int key) {
  15.       if (!map.containsKey(key)) {
  16.         return -1;
  17.       }
  18.       DoubleNode doubleNode = map.get(key);
  19.       updateNode(doubleNode);
  20.       return doubleNode.val;
  21.     }
  23.     public void put(int key, int value) {
  24.       if (map.containsKey(key)) {
  25.         DoubleNode doubleNode = map.remove(key);
  26.         doubleNode.val = value;
  27.         updateNode(doubleNode);
  28.         map.put(key, doubleNode);
  29.         return;
  30.       }
  31.       DoubleNode node = new DoubleNode(key, value);
  32.       if (capacity <= map.size()) {
  33.         map.remove(tail.pre.key);
  34.         removeNode(tail.pre);
  35.       }
  36.       map.put(key, node);
  37.       addNode(node);
  38.     }
  40.     private class DoubleNode {
  41.       private DoubleNode pre, next;
  42.       private Integer key;
  43.       private Integer val;
  45.       public DoubleNode(Integer key, Integer val) {
  46.         this.key = key;
  47.         this.val = val;
  48.       }
  49.     }
  51.     private DoubleNode head, tail;
  53.     private void addNode(DoubleNode node) {
  54.       node.next = head.next;
  55.       head.next.pre = node;
  56.       node.pre = head;
  57.       head.next = node;
  58.     }
  60.     private void removeNode(DoubleNode node) {
  61.       node.pre.next = node.next;
  62.       node.next.pre = node.pre;
  63.     }
  65.     private void updateNode(DoubleNode node) {
  66.       removeNode(node);
  67.       addNode(node);
  68.     }
  69.   }

和为K的子数组

前缀和思想 + map(添加时查看是否包含，将双重循环变为一重)

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

输入:nums = [1,1,1], k = 2，输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

  1. class Solution {
  2.   public int subarraySum(int[] nums, int k) {
  3.     int count = 0;
  4.     int sum = 0;
  5.     // 前缀和 : 出现次数
  6.     final HashMap<Integer, Integer> map = new HashMap<>();
  7.     map.put(0, 1);
  8.     for (int i = 0; i < nums.length; i++) {
  9.       sum += nums[i];
  10.       if (map.containsKey(sum - k)) count += map.get(sum - k);
  12.       if (map.containsKey(sum)) map.put(sum, map.get(sum) + 1);
  13.       else map.put(sum, 1);
  14.     }
  15.     return count;
  16.   }
  17. }

并查集

  1. /** 并查集 */
  2. private class UnionFind {
  3.   private int[] parent;
  5.   public UnionFind(int size) {
  6.     parent = new int[size];
  7.     for (int i = 0; i < parent.length; i++) parent[i] = i;
  8.   }
  10.   /**
  11.    * 连接两个元素
  12.    *
  13.    * @param p index
  14.    * @param q index
  15.    */
  16.   void union(int p, int q) {
  17.     if (parent[p] == parent[q]) return;
  18.     for (int i = 0; i < parent.length; i++)
  19.       // 可先不改变p，在遍历完后再改变
  20.       if (i != p && parent[i] == parent[p]) parent[i] = parent[q];
  21.     parent[p] = parent[q];
  22.   }
  24.   /**
  25.    * 判断 是否相连
  26.    *
  27.    * @param p index
  28.    * @param q index
  29.    * @return
  30.    */
  31.   Boolean isUnion(int p, int q) {
  32.     return parent[p] == parent[q];
  33.   }
  34. }

回溯算法

优质博客：一文学会回溯算法解题技巧

回溯法可以理解为通过选择不同的岔路口寻找目的地，一个岔路口一个岔路口的去尝试找到目的地。如果走错了路，继续返回来找到岔路口的另一条路，直到找到目的地。

模板：
回溯算法

  1. void dfs(已选解集合,每个阶段可选解) {
  2.     if (已选解集合满足条件) {
  3.         结果集.add(已选解集合);
  4.         return;
  5.     }
  7.     // 遍历每个阶段的可选解集合
  8.     for (可选解 in 每个阶段的可选解) {
  10.         // 选择此阶段其中一个解,将其加入到已选解集合中
  11.         已选解集合.add(可选解)
  13.         // 进入下一个阶段
  14.         dfs(已选解集合,下个阶段可选的空间解)
  16.         // 「回溯」换个解再遍历
  17.         已选解集合.remove(可选解)
  19.     }
  20. }

动态规划(DP)

动态规划题目类型

image-20210304142140940

一、 最值型动态规划：
动态规划组成部分:
1.确定状态

  • 最后一步(最优策略中使用的最后一 枚硬币ak )
  • 化成子问题(最少的硬币拼出更小的面值27-aK )

2.转移方程

  • f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}

3.初始条件和边界情况

  • f[O] = 0,如果不能拼出Y , f[Y]=正无穷

4.计算顺序（倒着来）

  • f[0], f[1], f[2]

例1

  1. // Java：零钱兑换 : 322
  2. public int coinChange(int[] coins, int amount) {
  3.   if (amount == 0) return 0;
  4.   /** 
  5.    * f(n): 数量；n:金额 ；
  6.    * f(n) = [f(n-X0),...,f(n-Xn)]min
  7.    * */
  8.   final int[] f = new int[amount + 1];
  9.   f[0] = 0;
  10.   for (int i = 1; i < f.length; i++) {
  11.     f[i] = Integer.MAX_VALUE;
  12.     for (int j = 0; j < coins.length; j++)
  13.       /** 处理 金额比面值小得情况 和 f[i - coins[j]] == Integer.MAX_VALUE 时，+1 会溢出的问题 */
  14.       if (i >= coins[j] && f[i - coins[j]] != Integer.MAX_VALUE)
  15.         f[i] = Math.min(f[i], f[i - coins[j]] + 1);
  16.   }
  17.   return f[amount] == Integer.MAX_VALUE ? -1 : f[amount];
  18. }

例2

  1. class Solution {
  2.   //    跳跃游戏 : 55
  3.   public boolean canJump(int[] nums) {
  4.     if (nums == null || nums.length == 0) {
  5.       return true;
  6.     }
  7.     int l = nums.length;
  8.     boolean[] f = new boolean[l]; // 是否能跳到 i
  9.     f[0] = true;
  10.     /*判断是否能从 j 跳到 i */
  11.     for (int i = 1; i < nums.length; i++) {
  12.       for (int j = 0; j < i; j++) {
  13.         if (f[j] && j + nums[j] >= i) {
  14.           f[i] = true;
  15.           break;
  16.         }
  17.       }
  18.     }
  19.     return f[l - 1];
  20.   }
  21. }

总结：
image-20210304172333730

常见排序算法

image-20210306032223402