不好分类
1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
解答
hash表存储，一次遍历法
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
return new int[]{i, map.get(nums[i])};
} else {
map.put(target - nums[i], i);
}
}
return new int[]{-1, -1};
}
2.两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (null == l1 && null == l2) {
return null;
}
if (null == l1) {
return l2;
}
if (null == l2) {
return l1;
}
ListNode root = l1;
ListNode l1Pre = null;
int plus = 0;
while (l1 != null && l2 != null){
int sum = l1.val + l2.val + plus;
l1.val = sum % 10;
plus = sum / 10;
l1Pre = l1;
l1 = l1.next;
l2 = l2.next;
}
if(l1 == null){
l1Pre.next = l2;
l1 = l2;
}
while(l1 != null && plus != 0){
int sum = plus + l1.val;
l1.val = sum % 10;
plus = sum / 10;
l1Pre = l1;
l1 = l1.next;
}
if(plus != 0){
l1Pre.next = new ListNode(plus);
}
return root;
}
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
题目解答
哈希表存每个字符最近的index
public int lengthOfLongestSubstring(String s) {
if(null == s) {
return 0;
}
char[] sc = s.toCharArray();
Map<Character, Integer> lastIndexMap = new HashMap<>();
int stIndex = 0;
int max = 0;
int curLen = 0;
for (int i = 0; i < sc.length; i++) {
char cur = sc[i];
//该未出现过或出现在stIndex之前的场景，直接往后即可
if(!lastIndexMap.containsKey(cur) || lastIndexMap.get(cur) < stIndex){
curLen++;
} else {
int lastIndex = lastIndexMap.get(cur);
stIndex = lastIndex + 1;
curLen = i - stIndex + 1;
}
lastIndexMap.put(cur, i);
if(curLen > max){
max = curLen;
}
}
return max;
}
15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
解答
排序 + hashMap twosum
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
int last = nums[0] - 1;
for (int i = 0; i < nums.length; i++) {
int target = nums[i];
if(target == last){
continue;
} else {
last = target;
}
List<List<Integer>> twoSumResult = twoSums(nums, i + 1, -target);
for (List<Integer> integers : twoSumResult) {
integers.add(nums[i]);
}
result.addAll(twoSumResult);
}
return result;
}
public List<List<Integer>> twoSums(int[] nums, int start, int target) {
List<List<Integer>> results = new ArrayList<>();
HashSet<Integer> resultFirSet = new HashSet<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = start; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
List<Integer> result = new ArrayList<>();
if(!resultFirSet.contains(nums[i])) {
result.add(nums[i]);
result.add(nums[map.get(nums[i])]);
results.add(result);
resultFirSet.add(nums[i]);
}
} else {
map.put(target - nums[i], i);
}
}
return results;
}
排序双指针two sum
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
//与上一个相等不处理
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int j = i + 1;
int k = nums.length - 1;
int target = -nums[i];
//小了就增大j, 大了就减小k
//如果相等下一个j，j大了就必定会减小k，原本遍历过的k(更大的）不可能满足
while (j < k) {
//避免重复(j > i + 1 && nums[j] == nums[j - 1])
if ((j > i + 1 && nums[j] == nums[j - 1]) || (nums[j] + nums[k] < target)) {
j++;
continue;
}
if (nums[j] + nums[k] > target) {
k--;
continue;
}
if (nums[j] + nums[k] == target) {
List<Integer> newResult = new ArrayList<>();
newResult.add(nums[i]);
newResult.add(nums[j]);
newResult.add(nums[k]);
result.add(newResult);
j++;
}
}
}
return result;
}
48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
题目解答
public void rotate(int[][] matrix) {
rotate(matrix, 0, matrix.length - 1);
}
private void rotate(int[][] matrix, int st, int ed) {
//=为中心元素，>则已旋转完闭
if (st >= ed) {
return;
}
int length = ed - st;
//旋转当圈
int[] tmp = new int[length];
for (int i = 0; i < length; i++) {
tmp[i] = matrix[st + i][st];
}
for (int i = 0; i < length; i++) {
matrix[st + i][st] = matrix[ed][st + i];
}
for (int i = 0; i < length; i++) {
matrix[ed][st + i] = matrix[ed - i][ed];
}
for (int i = 0; i < length; i++) {
matrix[ed - i][ed] = matrix[st][ed - i];
}
//这一列原始没了，从tmp中取
for (int i = 0; i < length; i++) {
matrix[st][ed - i] = tmp[i];
}
//旋转下一圈
rotate(matrix, st + 1, ed - 1);
}
优化了一下，但其实思路不太一样的，上面一条一条转，两个方法虽然递归了，但其实也没必要递归，只是代表思路
public void rotate(int[][] matrix) {
rotate(matrix, 0, matrix.length - 1);
}
private void rotate(int[][] matrix, int st, int ed) {
//=为中心元素，>则已旋转完闭
if (st >= ed) {
return;
}
int length = ed - st;
//旋转当圈
for (int i = 0; i < length; i++) {
int tmp = matrix[st + i][st];
matrix[st + i][st] = matrix[ed][st + i];
matrix[ed][st + i] = matrix[ed - i][ed];
matrix[ed - i][ed] = matrix[st][ed - i];
matrix[st][ed - i] = tmp;
}
//旋转下一圈
rotate(matrix, st + 1, ed - 1);
}
简洁清晰的迭代
public void rotate(int[][] matrix) {
int st = 0, ed = matrix.length - 1;
while (st < ed) {
//旋转当圈
for (int i = 0; i < ed - st; i++) {
int tmp = matrix[st + i][st];
matrix[st + i][st] = matrix[ed][st + i];
matrix[ed][st + i] = matrix[ed - i][ed];
matrix[ed - i][ed] = matrix[st][ed - i];
matrix[st][ed - i] = tmp;
}
//下一圈
st++;
ed--;
}
}
49. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
解答
直观的排序比对法，效率很低
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> results = new ArrayList<>();
List<String> templates = new ArrayList<>();
for (String s : strs) {
char[] sc = s.toCharArray();
Arrays.sort(sc);
String sortedStr = new String(sc);
boolean find = false;
for (int i = 0; i < templates.size(); i++) {
String template = templates.get(i);
if(template.equals(sortedStr)){
results.get(i).add(s);
find = true;
}
}
if(!find) {
templates.add(sortedStr);
List<String> result = new ArrayList<>();
result.add(s);
results.add(result);
}
}
return results;
}
应该找个替代的模版，减少排序的消耗
int[] 时间更长了
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> results = new ArrayList<>();
List<int[]> templates = new ArrayList<>();
for (String s : strs) {
char[] sc = s.toCharArray();
boolean find = false;
for (int i = 0; i < templates.size(); i++) {
int[] template = templates.get(i);
if (match(template, sc)) {
results.get(i).add(s);
find = true;
}
}
if (!find) {
templates.add(newTemplate(sc));
List<String> result = new ArrayList<>();
result.add(s);
results.add(result);
}
}
return results;
}
private boolean match(int[] template, char[] str) {
int[] tmpTemplate = Arrays.copyOf(template, template.length);
for (char sc : str) {
tmpTemplate[sc - 'a']--;
}
return Arrays.stream(tmpTemplate).allMatch(sNum -> sNum == 0);
}
private int[] newTemplate(char[] str) {
int[] template = new int[26];
for (char c : str) {
template[c - 'a']++;
}
return template;
}
在第一个方法上用hash表存储排序字符串与结果数组的关系，比较快O(nklogk)，n个数，k字符串最大长度。
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> results = new ArrayList<>();
Map<String, Integer> templateIndexMap = new HashMap<>();
for (String s : strs) {
char[] sc = s.toCharArray();
Arrays.sort(sc);
String sortedStr = new String(sc);
if (templateIndexMap.containsKey(sortedStr)) {
results.get(templateIndexMap.get(sortedStr)).add(s);
} else {
List<String> result = new ArrayList<>();
result.add(s);
results.add(result);
templateIndexMap.put(sortedStr, results.size() - 1);
}
}
return results;
}
int[]数组做模版，然后使用hash表 O(n(k+26))，字符串越长优势越明显
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> templateIndexMap = new HashMap<>();
for (String s : strs) {
char[] sc = s.toCharArray();
int[] cCount = new int[26];
for (char c : sc) {
cCount[c - 'a']++;
}
StringBuilder sb = new StringBuilder();
for(int i : cCount){
sb.append(i);
sb.append("-");
}
String curTemplate = sb.toString();
if (templateIndexMap.containsKey(curTemplate)) {
templateIndexMap.get(curTemplate).add(s);
} else {
List<String> result = new ArrayList<>();
result.add(s);
templateIndexMap.put(curTemplate, result);
}
}
return new ArrayList<>(templateIndexMap.values());
}
合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
解答
还没做完
75.颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
题目解答
计数排序
public void sortColors(int[] nums) {
int[] counts = new int[3];
for (int num : nums) {
counts[num]++;
}
int cur = 0;
int curNum = 0;
for (int count : counts) {
while(count > 0){
nums[cur++] = curNum;
count--;
}
curNum++;
}
}
56.合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
题目解答
按区间左界排序，依次合并，使合并的过程是确定的，即如果当前区间不能合并了，那么后续所有的区间都不影响当前合并了的区间。
private int[][] merge(int[][] intervals) {
if(null == intervals || 0 == intervals.length){
return new int[0][2];
}
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
List<int[]> merged = new ArrayList<>();
for (int[] interval : intervals) {
int L = interval[0], R = interval[1];
if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
merged.add(new int[]{L, R});
} else {
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
}
}
return merged.toArray(new int[merged.size()][]);
}
128. 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
题目解答
- hash set保存所有的数，按数字遍历，如果存在num++，就一直找。
- O(n)的保证，!num_set.contains(num - 1) 不是第一个数就不开始遍历
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<>();
for (int num : nums) {
num_set.add(num);
}
int longestStreak = 0;
for (int num : num_set) {
if (!num_set.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (num_set.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
169.多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
解答
哈希表
public int majorityElement(int[] nums) {
if(nums.length <= 1){
return nums[0];
}
Map<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {
if (countMap.containsKey(num)) {
countMap.put(num, countMap.get(num) + 1);
if (countMap.get(num) > nums.length / 2) {
return num;
}
} else {
countMap.put(num, 1);
}
}
return -1;
}
Boyer-Moore 投票算法，如果众数是1，其他数是-1，那么该数组sum>1，时间O(n)，空间O(1)
public int majorityElement(int[] nums) {
if (nums.length <= 1) {
return nums[0];
}
int count = 1;
int cur = nums[0];
for (int i = 1; i < nums.length; i++) {
if (count == 0) {
cur = nums[i];
count = 1;
continue;
}
if (cur == nums[i]) {
count++;
} else {
count--;
}
}
return cur;
}
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
题目解答
双指针，一个在非零的末尾，一个遍历整个数组，发现非零就让末尾 = nums[i]，最后移完了所有非零元素，就让后续的元素都等于0
public void moveZeroes(int[] nums) {
int lastNotZero = 0;
for (int i = 0; i < nums.length; i++) {
if(nums[i] != 0){
nums[lastNotZero] = nums[i];
lastNotZero++;
}
}
while(lastNotZero < nums.length){
nums[lastNotZero] = 0;
lastNotZero++;
}
}
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。
题目解答
辅助栈，把当前元素对应的最小值也存下来。
class MinStack {
private final Stack<Integer> min;
private final Stack<Integer> stack;
public MinStack() {
min = new Stack<>();
stack = new Stack<>();
min.push(Integer.MAX_VALUE);
}
public void push(int val) {
stack.push(val);
min.push(Math.min(min.peek(), val));
}
public void pop() {
stack.pop();
min.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min.peek();
}
}
136. 只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
题目解答
注意题目里的“其余每个元素均出现两次”，抑或，把相同的两个数给消掉了。
public int singleNumber(int[] nums) {
int a = 0;
for (int num : nums) {
a ^= num;
}
return a;
}
448. 找到所有数组中消失的数字
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
解答
主要的思路是用数组本身做hash表
不使用额外空间的交换算法，把下标和对应的数字排列整齐，最终下标不等于数字的即为空缺
public List<Integer> findDisappearedNumbers(int[] nums) {
int index = 0;
while(index < nums.length){
while(nums[index] != index + 1){
if(nums[index] != nums[nums[index] -1]) {
swap(nums, index, nums[index] - 1);
} else {
break;
}
}
index++;
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if(nums[i] != i+1){
result.add(i+1);
}
}
return result;
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
更快的方法
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int idx = (nums[i] - 1) % nums.length;
nums[idx] += nums.length;
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= nums.length) {
result.add(i + 1);
}
}
return result;
}
461. 汉明距离
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
解答
public int hammingDistance(int x, int y) {
int a = x ^ y;
int ret = 0;
//a中1的个数
while (a != 0) {
ret += a & 1;
a >>= 1;
}
return ret;
}
215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
输入: [3,2,1,5,6,4], k = 2 输出: 5
解答
堆排序其实就是max(n, klogn), k小，所以就是O(n)
public int findKthLargest(int[] nums, int k) {
if (nums.length <= 1) {
return nums[0];
}
//nlogn
buildLargeHeap(nums, nums.length);
int max = nums[0];
//klogn
for (int i = 1; i < k; i++) {
swap(nums, 0, nums.length - i);
moveSon(nums, nums.length - i, 0);
max = nums[0];
}
return max;
}
/**
* i > 2i + 1, 2i + 2
* 2i+2 = nums.length - 1 或者 2i + 1 = nums.length - 1
*
* @param nums
*/
private void buildLargeHeap(int[] nums, int heapSize) {
int st = (heapSize - 2) / 2;
for (int i = st; i >= 0; i--) {
moveSon(nums, heapSize, i);
}
}
private void moveSon(int[] nums, int heapSize, int parent) {
while (true) {
int maxSon = parent;
int leftSon = 2 * parent + 1;
int rightSon = 2 * parent + 2;
if(leftSon < heapSize && nums[leftSon] > nums[maxSon]){
maxSon = leftSon;
}
if (rightSon < heapSize && nums[rightSon] > nums[maxSon]) {
maxSon = rightSon;
}
if (maxSon != parent) {
swap(nums, parent, maxSon);
parent = maxSon;
} else {
break;
}
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
238. 除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
输入: nums = [1,2,3,4] 输出: [24,12,8,6]
解答
dp[i] = 0 - (i-1)乘积 dt[i] = i+1, nums.length
public int[] productExceptSelf(int[] nums) {
int[] dp = new int[nums.length];
int[] dt = new int[nums.length];
int[] result = new int[nums.length];
int lSum = 1;
int rSum = 1;
for (int i = 0; i < nums.length; i++) {
dp[i] = lSum;
dt[nums.length - i - 1] = rSum;
lSum *= nums[i];
rSum *= nums[nums.length - i - 1];
}
for (int i = 0; i < nums.length; i++) {
result[i] = dp[i] * dt[i];
}
return result;
}
省空间算法
public int[] productExceptSelf(int[] nums) {
int[] result = new int[nums.length];
result[0] = 1;
for (int i = 1; i < nums.length; i++) {
result[i] = result[i - 1] * nums[i - 1];
}
int rSum = 1;
for (int i = nums.length - 1; i >= 0; i--) {
result[i] = result[i] * rSum;
rSum *= nums[i];
}
return result;
}
287. 寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
解答
347.前k个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
记录+排序但其实不需要排这么多
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.compute(num, (key, value) -> value + 1);
} else {
map.put(num, 1);
}
}
List<Map.Entry<Integer,Integer>> sorted = map.entrySet().stream()
.sorted((o1, o2) -> Integer.compare(o2.getValue(), o1.getValue()))
.collect(Collectors.toList());
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = sorted.get(i).getKey();
}
return result;
}
自建最小堆
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.compute(num, (key, value) -> value + 1);
} else {
map.put(num, 1);
}
}
KHeap heap = new KHeap(k);
map.forEach((key, value) -> heap.addElement(new int[]{key, value}));
return heap.result();
}
private class KHeap {
private int[][] heap;
private int capacity;
private int size;
public KHeap(int capacity) {
this.capacity = capacity;
this.size = 0;
heap = new int[capacity][2];
}
public void addElement(int[] l) {
if (size < capacity) {
insert(l);
} else if (l[1] > heap[0][1]) {
heap[0] = l;
moveSon(0);
}
}
public int[] result() {
int[] result = new int[capacity];
for (int i = 0; i < capacity; i++) {
result[i] = heap[i][0];
}
return result;
}
private void insert(int[] ele) {
heap[size] = ele;
size++;
int parent = size / 2 - 1;
while (true) {
moveSon(parent);
if (parent <= 0) {
break;
}
parent = (parent - 1) / 2;
}
}
private void moveSon(int cur) {
if (cur < 0 || cur > capacity - 1) {
return;
}
while (true) {
int min = cur;
int l = 2 * cur + 1;
int r = 2 * cur + 2;
if (l < size && heap[l][1] < heap[min][1]) {
min = l;
}
if (r < size && heap[r][1] < heap[min][1]) {
min = r;
}
if (min != cur) {
swap(cur, min);
cur = min;
} else {
break;
}
}
}
private void swap(int i, int j) {
int[] tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
}
394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
输入：s = “3[a2[c]]” 输出：”accaccacc”
辅助栈
public String decodeString(String s) {
char[] str = s.toCharArray();
Stack<Integer> sn = new Stack<>();
Stack<String> cs = new Stack<>();
int num = 0;
for (char c : str) {
if (c >= '0' && c <= '9') {
num = num * 10 + (c - '0');
} else if (c == ']') {
int curNum = sn.pop();
LinkedList<String> linkedList = new LinkedList<>();
while (!cs.peek().equals("[")) {
linkedList.add(cs.pop());
}
cs.pop();
StringBuilder sb = new StringBuilder();
while(!linkedList.isEmpty()){
sb.append(linkedList.removeLast());
}
String curSt = sb.toString();
StringBuilder totalSb = new StringBuilder();
for (int j = 0; j < curNum; j++) {
totalSb.append(curSt);
}
cs.push(totalSb.toString());
} else {
if (num != 0) {
sn.push(num);
num = 0;
}
cs.push("" + c);
}
}
StringBuilder sb = new StringBuilder();
for (String asdas: cs.toArray(new String[1])) {
sb.append(asdas);
}
return sb.toString();
}
739.每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
O(n^2)的算法
public int[] dailyTemperatures(int[] temperatures) {
int[] result = new int[temperatures.length];
for (int i = 0; i < temperatures.length; i++) {
for (int j = i; j < temperatures.length; j++) {
if (result[i] == 0 && temperatures[j] > temperatures[i]) {
result[i] = j - i;
}
}
}
return result;
}
单调栈（如果需要找到左边或者右边第一个比当前位置的数大或者小，则可以考虑使用单调栈；单调栈的题目如矩形米面积等等）
public int[] dailyTemperatures(int[] temperatures) {
int[] result = new int[temperatures.length];
Stack<int[]> st = new Stack<>();
for (int i = 0; i < temperatures.length; i++) {
while (!st.isEmpty() && temperatures[i] > st.peek()[0]) {
int[] top = st.pop();
result[top[1]] = i - top[1];
}
st.push(new int[]{temperatures[i], i});
}
return result;
}
560. 和为k的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
输入：nums = [1,1,1], k = 2 输出：2
解答
前缀和
public int subarraySum(int[] nums, int k) {
int count = 0;
//i开始到当前的和
int[] pre = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j <= i; j++) {
if(pre[j] + nums[i] == k){
count++;
}
pre[j] += nums[i];
}
}
return count;
}
前缀和+哈希表优化 pre[i] 为 [0..i]的和
public int subarraySum(int[] nums, int k) {
int count = 0, pre = 0;
//记录和为x的连续数组个数
HashMap < Integer, Integer > mp = new HashMap<> ();
mp.put(0, 1);
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
if (mp.containsKey(pre - k)) {
count += mp.get(pre - k);
}
mp.put(pre, mp.getOrDefault(pre, 0) + 1);
}
return count;
}
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
解答
排序比对
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
char[] sc = s.toCharArray();
char[] pc = p.toCharArray();
Arrays.sort(pc);
String sorted = new String(pc);
for (int i = 0; i < s.length() - p.length() + 1; i++) {
if(same(sc, sorted, i)){
result.add(i);
}
}
return result;
}
private boolean same(char[] sc, String sorted, int scStart){
char[] curCs = Arrays.copyOfRange(sc, scStart, scStart + sorted.length());
Arrays.sort(curCs);
String scc = new String(curCs);
return scc.equals(sorted);
}
