其他类型题目

78. 子集
  题目概述：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

class Solution {public List> subsets(int[] nums) {/* 1.第一种方案递归result = 第一个元素 + 剩下元素的子集*/List> res = new ArrayList<>();int length = nums.length;if (length == 1) {List temp = new ArrayList<>();temp.add(nums[0]);res.add(temp);res.add(new ArrayList<>());} else {List> prevList = subsets(Arrays.copyOfRange(nums, 1, length));res.addAll(prevList);for (List list : prevList) {List temp = new ArrayList<>();for (int value : list) {temp.add(value);}temp.add(nums[0]);res.add(temp);}}return res;/* 2.第二种方案，参考的题解使用回溯的方法*/List> res = new ArrayList<>();res.add(new ArrayList<>());for (int i = 0; i < nums.length; i++) {List> tempRes = new ArrayList<>();for (List list : res) {List temp = getNewList(list);temp.add(nums[i]);tempRes.add(temp);}res.addAll(tempRes);}return res;}public List getNewList(List list) {List res = new ArrayList<>();for (int val : list) {res.add(val);}return res;}
}

33. 搜索旋转排序数组
  题目概述：整数数组 nums 按升序排列，数组中的值 互不相同 。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

class Solution {public int search(int[] nums, int target) {/* 1.第一种方案使用二分查找，参考的题解比较中间和两边的值，可以将数组分为一个有序数组和一个无序数组对于有序数组，使用二分查找对于无序数组，递归调用本函数*/return searchHelper(nums, target, 0, nums.length - 1);}public int searchHelper(int[] nums, int target, int startIdx, int endIdx) {int mid = startIdx + (endIdx - startIdx + 1) / 2;int res = -1;if (startIdx > endIdx) {return res;} else if (nums[mid] == target) {return mid;} else if (nums[mid] > nums[startIdx]) {int temp = searchHelper(nums, target, mid + 1, endIdx);res = temp != -1 ? temp : res;temp = searchInOrder(nums, target, startIdx, mid);res = temp != -1 ? temp : res;} else {int temp = searchHelper(nums, target, startIdx, mid - 1);res = temp != -1 ? temp : res;temp = searchInOrder(nums, target, mid, endIdx);res = temp != -1 ? temp : res;}return res;}public int searchInOrder(int[] nums, int target, int startIdx, int endIdx) {int mid;while (startIdx <= endIdx) {mid = startIdx + (endIdx - startIdx + 1) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {startIdx = mid + 1;} else {endIdx = mid - 1;}}return -1;}
}

34. 在排序数组中查找元素的第一个和最后一个位置
  题目概述：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

class Solution {public int[] searchRange(int[] nums, int target) {/* 1.第一种方案二分查找找到对应元素后向两边扩展实际上时间复杂度并不是O(logn)如果数组中全为目标值，则其时间复杂度为O(n)*/int left = 0;int right = nums.length - 1;int mid;while (left <= right) {mid = left + (right - left) / 2;if (nums[mid] == target) {return searchIdx(nums, mid, target);} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}// return new int[]{-1, -1};/* 2.第二种方案，参考的题解二分查找分别查找左右边界*/int[] res = new int[2];res[0] = searchRangeHelper(nums, target, true);res[1] = searchRangeHelper(nums, target, false);return res;}public int searchRangeHelper(int[] nums, int target, boolean leftRange) {int left = 0;int right = nums.length - 1;int mid;if (right < left) {return -1;}while (left < right) {mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else {if (leftRange) {right = mid;} else {if (nums[mid + 1] == target) {left = mid + 1;} else {return mid;}}}}return nums[left] == target ? left : -1;}public int[] searchIdx(int[] nums, int idx, int target) {int[] res = new int[2];int left = idx;int right = idx;while ((left >= 0 && nums[left] == target) || (right < nums.length && nums[right] == target)) {if (left >= 0 && nums[left] == target) {left--;}if (right < nums.length && nums[right] == target) {right++;}}res[0] = left + 1;res[1] = right - 1;return res;}
}

287. 寻找重复数
  题目概述：给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

class Solution {public int findDuplicate(int[] nums) {/* 1.第一种方案递归检查第一个元素是否重复否则，检查剩下的元素是否重复最后超时了*/return findDuplicateHelper(nums, 0);/* 2.第二种方案，参考的题解快慢指针的思路，转换为环形链表求入口的问题*/int slow = getSlowNext(nums, 0);int fast = getFastNext(nums, 0);while (nums[fast] != nums[slow]) {slow = getSlowNext(nums, slow);fast = getFastNext(nums, fast);}fast = 0;while (nums[fast] != nums[slow]) {fast = getSlowNext(nums, fast);slow = getSlowNext(nums, slow);}return nums[slow];}public int getSlowNext(int[] nums, int curNode) {return nums[curNode];}public int getFastNext(int[] nums, int curNode) {return nums[nums[curNode]];}public int findDuplicateHelper(int[] nums, int startIdx) {if (startIdx == nums.length - 1) {return nums[startIdx];} else {if (checkSame(nums, startIdx)) {return nums[startIdx];} else {return findDuplicateHelper(nums, startIdx + 1);}}}public boolean checkSame(int[] nums, int startIdx) {for (int i = startIdx + 1; i < nums.length - 1; i++) {if(nums[i] == nums[startIdx]) {return true;}}return false;}
}

240. 搜索二维矩阵 II
  题目概述：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {/* 1.第一种方案二维二分查找初始化：三个指针分别指向矩阵的第一个元素、最后一个元素和中心元素将矩阵分为四个小矩阵，每次排除一个小矩阵有点复杂，略过*//* 2.第二种方案从右上角开始进行搜索如果当前值小于target，则舍弃当前行如果当前值大于target，则舍弃当前列*/int curRow = 0;int curCol = matrix[0].length - 1;while (checkRow(curRow, matrix.length) && checkCol(curCol, matrix[0].length)) {int curValue = matrix[curRow][curCol];if (curValue == target) {return true;} else if (curValue < target) {curRow += 1;} else {curCol -= 1;}}return false;}public boolean checkRow(int curRow, int row) {return curRow >= 0 && curRow < row;}public boolean checkCol(int curCol, int col) {return curCol >= 0 && curCol < col;}
}

48. 旋转图像
  题目概述：给定一个n×n的二维矩阵matrix表示一个图像。请你将图像顺时针旋转90度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

class Solution {public void rotate(int[][] matrix) {/* 1.第一种方案，参考的题解先转置，再镜像对称*/int row = matrix.length;int col = matrix[0].length;for (int i = 0; i < row; i++) {for (int j = i; j < col; j++) {swap(matrix, i, j, j, i);}}for (int j = 0; j < col / 2; j++) {for (int i = 0; i < row; i++) {swap(matrix, i, j, i, col - 1 - j);}}}public void swap(int[][] matrix, int rowA, int colA, int rowB, int colB) {int temp = matrix[rowA][colA];matrix[rowA][colA] = matrix[rowB][colB];matrix[rowB][colB] = temp;}
}

136. 只出现一次的数字
  题目概述：给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

class Solution {public int singleNumber(int[] nums) {/* 1.第一种方案从首个元素开始进行亦或剩下的就是只出现一次的元素*/int res = nums[0];for (int i = 1; i < nums.length; i++) {res = res ^ nums[i];}return res;}
}

338. 比特位计数
  题目概述：给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

class Solution {private HashMap map = new HashMap<>();public int[] countBits(int n) {/* 1.第一种方案计算每个i中1的个数，直接将其往右移即可*/int[] res = new int[n + 1];for (int i = 0; i <= n; i++) {res[i] = count(i);}return res;/* 2.第二种方案使用hashmap作为记忆化单元，存储以前的结果当前数字右移一位后加上map中存储的结果即可*/int[] res = new int[n + 1];for (int i = 0; i <= n; i++) {res[i] = countWithMap(i);}return res;}public int countWithMap(int num) {int res = 0;if (num % 2 != 0) {res += 1;}num /= 2;if (map.containsKey(num)) {res += map.get(num);map.put(num, res);return res;}while (num != 0) {if (num % 2 != 0) {res += 1;}num /= 2;}map.put(num, res);return res;}public int count(int num) {int res = 0;while (num != 0) {res = num % 2 != 0 ? res + 1 : res;num /= 2;}return res;}
}

146. LRU 缓存
  题目概述：请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现 LRUCache 类：LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

class LRUCache {private HashMap map;private int capacity;private Node head;private Node tail;class Node {private int key;private int value;private Node prevNode;private Node nextNode;public Node(int key, int value, Node prevNode, Node nextNode) {this.key = key;this.value = value;this.prevNode = prevNode;this.nextNode = nextNode;}}/* 1.第一种方案，参考的题解使用哈希表+双向链表组合*/public LRUCache(int capacity) {this.map = new HashMap<>();this.capacity = capacity;this.head = new Node(-1, 0, null, null); //在head中存储数据的数量this.tail = new Node(-1, -1, null, null);this.head.nextNode = this.tail;this.tail.prevNode = this.head;}public int get(int key) {if (this.map.containsKey(key)) {Node curNode = this.map.get(key);pickNodeInsertTail(curNode);return curNode.value;} return -1;}public void put(int key, int value) {if (this.map.containsKey(key)) {Node curNode = this.map.get(key);pickNodeInsertTail(curNode);curNode.value = value;return;} else if (this.head.value == capacity) {this.map.remove(this.head.nextNode.key);pickNodeFromList(this.head.nextNode);this.head.value -= 1;}Node curNode = new Node(key, value, this.tail.prevNode, this.tail);this.tail.prevNode.nextNode = curNode;this.tail.prevNode = curNode;this.map.put(key, curNode);this.head.value += 1;}private void pickNodeInsertTail(Node curNode) {pickNodeFromList(curNode);curNode.prevNode = this.tail.prevNode;curNode.nextNode = this.tail;this.tail.prevNode.nextNode = curNode;this.tail.prevNode = curNode;}private void pickNodeFromList(Node curNode) {curNode.prevNode.nextNode = curNode.nextNode;curNode.nextNode.prevNode = curNode.prevNode;curNode.prevNode = null;curNode.nextNode = null;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

208. 实现 Trie (前缀树)
  题目概述：Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。请你实现 Trie 类：Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

class Trie {private Node root;class Node {private char curChar;private boolean isEnd;private HashMap nextLevel;public Node(char curChar, boolean isEnd) {this.curChar = curChar;this.isEnd = isEnd;this.nextLevel = new HashMap<>();}}public Trie() {root = new Node('0', false);}public void insert(String word) {insertHelper(this.root, word, 0);}public void insertHelper(Node curNode, String word, int startIdx) {int length = word.length();char curChar = word.charAt(startIdx);if (startIdx == length - 1) {if (curNode.nextLevel.containsKey(curChar)) {Node temp = curNode.nextLevel.get(curChar);temp.isEnd = true;} else {Node temp = new Node(curChar, true);curNode.nextLevel.put(curChar, temp);}} else {if (curNode.nextLevel.containsKey(curChar)) {Node temp = curNode.nextLevel.get(curChar);insertHelper(temp, word, startIdx + 1);} else {Node temp = new Node(curChar, false);curNode.nextLevel.put(curChar, temp);insertHelper(temp, word, startIdx + 1);}}}public boolean search(String word) {return searchHelper(this.root, word, 0);}public boolean searchHelper(Node curNode, String word, int startIdx) {int length = word.length();char curChar = word.charAt(startIdx);if (startIdx == length - 1) {if (curNode.nextLevel.containsKey(curChar)) {return curNode.nextLevel.get(curChar).isEnd;}return false;} else {if (curNode.nextLevel.containsKey(curChar)) {return searchHelper(curNode.nextLevel.get(curChar), word, startIdx + 1);}return false;}}public boolean startsWith(String prefix) {return startsWithHelper(this.root, prefix, 0);}public boolean startsWithHelper(Node curNode, String prefix, int startIdx) {int length = prefix.length();char curChar = prefix.charAt(startIdx);if (startIdx == length - 1) {return curNode.nextLevel.containsKey(curChar);} else {if (curNode.nextLevel.containsKey(curChar)) {return startsWithHelper(curNode.nextLevel.get(curChar), prefix, startIdx + 1);}}return false;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/

215. 数组中的第K个最大元素
  题目概述：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

class Solution {class PriorityQueue {private int[] queue;private int size;private int tailIdx;public PriorityQueue(int size) {this.size = size;this.queue = new int[size + 1];this.queue[0] = 0; // 头节点用来存储节点的数量，方便计算this.tailIdx = 1;}public void insert(int num) {this.queue[this.tailIdx++] = num;insertHelper(this.tailIdx - 1);}private void insertHelper(int curIdx) {int parentIdx = getParentIdx(curIdx);if (parentIdx == 0) {return;}if (this.queue[parentIdx] < this.queue[curIdx]) {int temp = this.queue[parentIdx];this.queue[parentIdx] = this.queue[curIdx];this.queue[curIdx] = temp;insertHelper(parentIdx);}}private int getParentIdx(int idx) {return idx / 2;}public int poll() {int res = this.queue[1];swap(1, this.tailIdx - 1);this.tailIdx--;pollHelper(1);return res;}private void swap(int idxA, int idxB) {int temp = this.queue[idxA];this.queue[idxA] = this.queue[idxB];this.queue[idxB] = temp;}private void pollHelper(int curIdx) {if (curIdx >= this.tailIdx) {return;}int leftChildIdx = getLeftIdx(curIdx);int rightChildIdx = getRightIdx(curIdx);int maxChildIdx = getMaxChildIdx(leftChildIdx, rightChildIdx);if (maxChildIdx != -1 && this.queue[maxChildIdx] > this.queue[curIdx]) {swap(curIdx, maxChildIdx);pollHelper(maxChildIdx);}}private int getLeftIdx(int curIdx) {int leftIdx = curIdx * 2;return leftIdx < this.tailIdx ? leftIdx : -1;}private int getRightIdx(int curIdx) {int rightIdx = curIdx * 2 + 1;return rightIdx < this.tailIdx ? rightIdx : -1;}private int getMaxChildIdx(int leftIdx, int rightIdx) {int res = -1;if (leftIdx != -1 && rightIdx != -1) {res = this.queue[leftIdx] > this.queue[rightIdx] ? leftIdx : rightIdx;} else if (leftIdx != -1) {res = leftIdx;} else if (rightIdx != -1) {res = rightIdx;}return res;}}public int findKthLargest(int[] nums, int k) {/* 1.第一种方案使用优先队列（最大堆）解决最大堆一般使用完全二叉树（数组）实现，子节点的值都小于根节点的值插入-将节点插入到末尾，然后检查其值是否小于根节点的值，如果不小于则交换两个节点删除-删除root节点，一般将最末尾的节点覆盖root节点，删除叶子节点，检查新root节点是否大于左右子节点，如果小于则交换*/PriorityQueue pQueue = new PriorityQueue(nums.length);for (int num : nums) {pQueue.insert(num);}while (k > 1) {pQueue.poll();k--;}return pQueue.poll();}
}

253. 会议室 II
  题目概述：给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。

class Solution {public int minMeetingRooms(int[][] intervals) {/* 1.第一种方案，参考的题解转换为上下车问题，记录同时在车上乘客的最大数*/int length = intervals.length;int[] upCar = new int[length];int[] downCar = new int[length];init(intervals, upCar, downCar);int up = 0;int down = 0;int curNum = 0;int res = Integer.MIN_VALUE;while (up < length && down < length) {if (upCar[up] < downCar[down]) {curNum++;up++;res = res < curNum ? curNum : res;} else {curNum--;down++;}}if (up == length) {return res;} else {return res + length - up;}}private void init(int[][] intervals, int[] upCar, int[] downCar) {int idx = 0;for (int[] interval : intervals) {upCar[idx] = interval[0];downCar[idx++] = interval[1]; }Arrays.sort(upCar);Arrays.sort(downCar);}
}

347. 前 K 个高频元素
  题目概述：给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

class Solution {class HashMapDoubleLink {private HashMap map;private Node head;private Node tail;class Node {private int key;private int frequence;private Node prevNode;private Node nextNode;public Node(int key, int frequence, Node prevNode, Node nextNode) {this.key = key;this.frequence = frequence;this.prevNode = prevNode;this.nextNode = nextNode;}}public HashMapDoubleLink() {this.map = new HashMap<>();this.head = new Node(0, Integer.MAX_VALUE, null, null);this.tail = new Node(0, 0, null, null);this.head.nextNode = this.tail;this.tail.prevNode = this.head;}public void push(int num) {if (map.containsKey(num)) {Node curNode = map.get(num);curNode.frequence += 1;reOrder(curNode);} else {Node curNode = new Node(num, 1, this.tail.prevNode, this.tail);this.tail.prevNode = curNode;curNode.prevNode.nextNode = curNode;map.put(num, curNode);}}private void reOrder(Node curNode) {Node temp = curNode.prevNode;while (temp.frequence < curNode.frequence) {temp = temp.prevNode;}curNode.prevNode.nextNode = curNode.nextNode;curNode.nextNode.prevNode = curNode.prevNode;curNode.prevNode = temp;curNode.nextNode = temp.nextNode;temp.nextNode.prevNode = curNode;temp.nextNode = curNode;}public int[] getFirstKNums(int k) {int idx = 0;int[] res = new int[k];Node curNode = this.head.nextNode;while (k > 0) {res[idx++] = curNode.key;curNode = curNode.nextNode;k--;}return res;}}public int[] topKFrequent(int[] nums, int k) {/* 1.第一种方案使用LRU缓存中使用的hashMap+双链表的结构时间比较慢*/HashMapDoubleLink map = new HashMapDoubleLink();for (int num : nums) {map.push(num);}return map.getFirstKNums(k);/* 2.第二种方案使用优先队列（最小堆）处理首先使用hashmap建立num和频率的映射维护优先队列的容量为k，比较当前元素和堆顶元素的频率如果当前元素的频率较大，将元素入队，如果容量超过了k，则删除堆顶元素*/class Pair {private int value;private int frequence;public Pair(int value, int frequence) {this.value = value;this.frequence = frequence;}}HashMap map = new HashMap<>();for (int num : nums) {if (map.containsKey(num)) {map.put(num, map.get(num) + 1);} else {map.put(num, 1);}}PriorityQueue pQueue = new PriorityQueue<>(new Comparator() {@Overridepublic int compare(Pair a, Pair b) {return a.frequence - b.frequence;}});for (int key : map.keySet()) {if (pQueue.size() == k && map.get(key) > pQueue.peek().frequence) {Pair temp = new Pair(key, map.get(key));pQueue.add(temp);pQueue.remove();} else if (pQueue.size() < k) {Pair temp = new Pair(key, map.get(key));pQueue.add(temp);}}int[] res = new int[k];for (int i = k - 1; i >= 0; i--) {res[i] = pQueue.remove().value;}return res;}
}

238. 除自身以外数组的乘积
  题目概述：给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。

class Solution {public int[] productExceptSelf(int[] nums) {/* 1.第一种方案，参考的题解使用动态规划完成两个dp数组，分别表示当前元素i左侧和右侧的乘积leftDp[i] = 左侧乘积rightDp[i] = 右侧乘积leftDp[i] = nums[i - 1] * leftDp[i - 1];rightDp[i] = nums[i + 1] * rightDp[i + 1];leftDp[0] = 1;rightDp[nums.length - 1] = 1;由于不能使用除法，所以rightDp[i]从右侧开始遍历 */int length = nums.length;int[] leftDp = new int[length];int[] rightDp = new int[length];leftDp[0] = 1;rightDp[length - 1] = 1;for (int i = 1; i < length; i++) {leftDp[i] = nums[i - 1] * leftDp[i - 1];rightDp[length - 1 - i] = nums[length - i] * rightDp[length - i];}int[] res = new int[length];for (int i = 0; i < length; i++) {res[i] = leftDp[i] * rightDp[i];}return res;}
}

560. 和为 K 的子数组
  题目概述：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

class Solution {public int subarraySum(int[] nums, int k) {/* 1.第一种方案，参考的题解使用dpdp[i][j] = i->j之间数组的和dp[i][j] = dp[i + 1][j] + nums[i];dp[i][i] = nums[i];因为需要知道dp[i + 1][j]的值，所以i从高往低遍历最后超出内存限制了*/int length = nums.length;int[][] dp = new int[length][length];int res = 0;for (int i = length; i >= 0; i--) {for (int j = i; j < length; j++) {if (i == j) {dp[i][j] = nums[i];} else {dp[i][j] = dp[i + 1][j] + nums[i];}res = dp[i][j] == k ? res + 1 : res;}}return res;/* 2.第二种方案，参考的题解使用前缀和+哈希表的方式prefixSum[i] = 前i个数的和prefixSum[j] - prefixSum[i - 1] = i - j之间元素的和 == k*/HashMap map = new HashMap<>();int res = 0;int curSum = 0;map.put(0, 1);for (int i = 0; i < nums.length; i++) {curSum += nums[i];int prefixSum = curSum;if (map.containsKey(prefixSum - k)) {res += map.get(prefixSum - k);}if (map.containsKey(prefixSum)) {map.put(prefixSum, map.get(prefixSum) + 1);} else {map.put(prefixSum, 1);}}return res;}
}

581. 最短无序连续子数组
  题目概述：给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的 最短 子数组，并输出它的长度。

class Solution {public int findUnsortedSubarray(int[] nums) {/* 1.第一种方案对数组进行遍历找到错误排序的序号，存入数组中*/List errorIdx = new ArrayList<>();for (int i = 0; i < nums.length - 1; i++) {if (nums[i] > nums[i + 1]) {errorIdx.add(i);}}int size = errorIdx.size();if (size == 0) {return 0;} else {int startIdx = errorIdx.get(0);int endIdx = size == 1 ? startIdx + 1 : errorIdx.get(size - 1);int[] idx = getMaxMinIdx(nums, startIdx, endIdx);int maxIdx = idx[0];int minIdx = idx[1];endIdx = errorIdx.get(size - 1) + 1;while (endIdx < nums.length && nums[endIdx] < nums[maxIdx]) {if (nums[endIdx] < nums[minIdx]) {minIdx = endIdx;}endIdx++;}while (startIdx > 0 && nums[startIdx - 1] > nums[minIdx]) {startIdx--;}return endIdx - startIdx;}}private int[] getMaxMinIdx(int[] nums, int startIdx, int endIdx) {int curMaxValue = Integer.MIN_VALUE;int curMinValue = Integer.MAX_VALUE;int[] res = new int[]{0, 0};for (int i = startIdx; i <= endIdx; i++) {if (nums[i] > curMaxValue) {curMaxValue = nums[i];res[0] = i;}if (nums[i] < curMinValue) {curMinValue = nums[i];res[1] = i;}}return res;}
}

621. 任务调度器
  题目概述：给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。你需要计算完成所有任务所需要的 最短时间 。

class Solution {public int leastInterval(char[] tasks, int n) {/* 1.第一种方案，参考的题解计算公式为(N - 1) * (n + 1) + x其中N为桶的数量（单个任务的最大数量），n为冷却时间，x为最后一个桶任务的数量（任务数量为N的任务的个数）*/int[] count = new int[26];Arrays.fill(count, 0);int curMaxNum = Integer.MIN_VALUE;for (int i = 0; i < tasks.length; i++) {int curIdx = tasks[i] - 'A';count[curIdx] += 1;if (count[curIdx] > curMaxNum) {curMaxNum = count[curIdx];}}int x = 0;for (int i = 0; i < 26; i++) {if (count[i] == curMaxNum) {x += 1;}}int res = (curMaxNum - 1) * (n + 1) + x;return Math.max(res, tasks.length);}
}

55. 跳跃游戏
  题目概述：给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

class Solution {private int[] dp;public boolean canJump(int[] nums) {/* 1.第一种方案，使用递归从后往前遍历，找到所有可以到达最后一个下标的索引，截断数组使用递归使用当前索引-最后一个下标+当前值判断是否大于等于0思路没有问题，可惜最后超时了使用记忆化搜索节约时间*/int length = nums.length;dp = new int[length];Arrays.fill(dp, -1); // -1表示未知，0表示失败，1表示成功return canJumpHelper(nums, length - 1);}private boolean canJumpHelper(int[] nums, int endIdx) {if (endIdx == 0) {dp[0] = 1;return true;} else if (dp[endIdx] != -1) {return dp[endIdx] == 1;} else {for (int i = endIdx - 1; i >= 0; i--) {if (i - endIdx + nums[i] >= 0 && canJumpHelper(nums, i)) {dp[i] = 1;return true;}}}dp[endIdx] = 0;return false;}
}

56. 合并区间
  题目概述：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

class Solution {public int[][] merge(int[][] intervals) {/* 1.第一种方案，转换为上下车问题当车为空，将要上人时，记录该时间；当将要下人，使得车为空时，记录该时间；算法错误，怎么会有0，0这样的区间？*//* 2.第二种方法，参考的题解将数组排序，遍历区间如果当前区间的开始时间小于等于结果集中最后一个区间的结束时间，说明有交集，使用当前区间的结束时间更新结果集*/Arrays.sort(intervals, new Comparator() {@Overridepublic int compare(int[] a, int[] b) {if (a[0] == b[0]) {return a[1] - b[1];}return a[0] - b[0];}});List res = new ArrayList<>();for (int i = 0; i < intervals.length; i++) {if (res.size() == 0) {res.add(intervals[i]);} else {int[] lastInterval = res.get(res.size() - 1);if (intervals[i][0] <= lastInterval[1]) {lastInterval[1] = intervals[i][1] > lastInterval[1] ? intervals[i][1] : lastInterval[1];} else {res.add(intervals[i]);}}}return transToArray(res);}private int[][] transToArray(List list) {int[][] res = new int[list.size()][2];int idx = 0;for (int[] temp : list) {res[idx][0] = temp[0];res[idx++][1] = temp[1];}return res;}}

121. 买卖股票的最佳时机间
  题目概述：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

class Solution {public int maxProfit(int[] prices) {/* 1.直接遍历，同时记录最小值*/int curMin = Integer.MAX_VALUE;int res = 0;for (int price : prices) {int curProfit = price - curMin;res = res > curProfit ? res : curProfit;curMin = price < curMin ? price : curMin;}return res;}
}

406. 根据身高重建队列
  题目概述：假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

class Solution {public int[][] reconstructQueue(int[][] people) {/* 1.第一种方案，参考的题解对people进行排序，高的站前面，同样高的比较第二个数字然后让排序好的people出来找位置，只有高的找好位置后，低的人才能找到位置*/Arrays.sort(people, new Comparator() {@Overridepublic int compare(int[] a, int[] b) {if (a[0] == b[0]) {return a[1] - b[1];} return b[0] - a[0];}});List res = new ArrayList<>();for (int[] p : people) {res.add(p[1], p);}return transToArray(res);}private int[][] transToArray(List list) {int[][] res = new int[list.size()][2];int idx = 0;for (int[] array : list) {res[idx][0] = array[0];res[idx++][1] = array[1];}return res;}
}

其他类型总结

  总结，其他类型比较杂，复习了二分查找、桶、优先队列等知识点。