二刷hot100，坚持每天打卡3道题！！！Today：2023-09-08
// 先求差，再查哈希表
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i<nums.length;i++){
int key = target - nums[i];
if(map.containsKey(key)){
return new int[]{map.get(key),i};
}
map.put(nums[i],i);
}
return new int[0];
}
// 对应位置相加，记录进位，然后链表尾插法即可
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int flag = 0,lv1,lv2;
ListNode answer = null,target = null;
while (l1 != null || l2 != null){
lv1 = l1 == null ? 0:l1.val;
lv2 = l2 == null ? 0:l2.val;
l1 = l1 == null ? null:l1.next;
l2 = l2 == null ? null:l2.next;
int sum = lv1+lv2+flag;
flag = sum / 10;
ListNode listNode = new ListNode(sum % 10);
if (target == null){
target = listNode;
answer = target;
}else {
target.next = listNode;
target = target.next;
}
}
if (flag >0){
target.next = new ListNode(flag);
}
return answer;
}
// 滑动窗口
public int lengthOfLongestSubstring(String s){
Set<Character> set = new HashSet<>();
int start = 0,end = 0,answer=0;
while (end < s.length()){
if (set.contains(s.charAt(end))){
set.remove(s.charAt(start++));
}else {
set.add(s.charAt(end++));
answer = Math.max(answer,end - start);
}
}
return answer;
}
// 动态规划
public String longestPalindrome(String s) {
if (s == null || s.length() < 2) {
return s;
}
int strLen = s.length();
int maxStart = 0; //最长回文串的起点
int maxEnd = 0; //最长回文串的终点
int maxLen = 1; //最长回文串的长度
boolean[][] dp = new boolean[strLen][strLen];
for (int r = 1; r < strLen; r++) {
for (int l = 0; l < r; l++) {
if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
dp[l][r] = true;
if (r - l + 1 > maxLen) {
maxLen = r - l + 1;
maxStart = l;
maxEnd = r;
}
}
}
}
return s.substring(maxStart, maxEnd + 1);
}
/*
总体思路：模拟合并数组，合并到中位数停止
时间：1ms， 击败 100.00%使用 Java 的用户
内存：42.03mb 击败 63.77%使用 Java 的用户
*/
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int num = 0; // 偶数中位数数字，奇数中位数右侧数字
int len = nums1.length + nums2.length;
boolean b = len % 2 == 0; // 是否为偶数
len /= 2; // 偶数中位数位置，奇数中位数右侧位置
if (nums1.length + nums2.length == 0) return 0; // 空数组返回0
if (nums1.length == 0) return b ? (nums2[len - 1] + nums2[len]) / 2.0 : nums2[len]; // 数组1为空返回数组2中位数
if (nums2.length == 0) return b ? (nums1[len - 1] + nums1[len]) / 2.0 : nums1[len]; // 数组2为空返回数组1中位数
int i = 0,j = 0;
int oldNum = num; // 奇数中位数左侧数字
while (i + j != len + 1) { // 判断是否循环至中位数
oldNum = num;
if (i >= nums1.length || (j < nums2.length && nums1[i] > nums2[j])) num = nums2[j++];
else num = nums1[i++];
}
return b ? (num + oldNum) / 2.0 : num; // 返回中位数
}
// 动态规划
public boolean isMatch(String s, String p) {
//此处为length+1的目的是放入一个额外的为空的字符情况，以便于判断当*时，添加的字符情况
boolean table[][]=new boolean[s.length()+1][p.length()+1];
table[0][0]=true;
for(int i =1;i<table[0].length;i++){
char ch=p.charAt(i-1);
if(i>1){
//若ch=='*'，则看同一行内回退两格的boolean值：
//（因为相当于若回退两格为true，即在选择添加该字符时可以选择数量为0（因为是'*'））
if(ch=='*'){
table[0][i]=table[0][i-2];
}
//因为第0行的s字符为空，所以和除了*以外的都不匹配，直接false
else table[0][i]=false;
}
else {
//如果填第一个空格，且字符为*，则赋值为true（因为*的匹配可以选择0个字符）
if(ch=='*') table[0][i]=true;
}
}
//接下来按照行优先的顺序填充表格
for(int j =1;j<table.length;j++){
char ch01=s.charAt(j-1);
for(int h =1;h<table[j].length;h++){
char ch02=p.charAt(h-1);
//如果行和列对应的字符相等 || 列的字符为'.'，则当前位置的值由左斜上方的值确定
if(ch02==ch01||ch02=='.'){
table[j][h]=table[j-1][h-1];
}
//如果列的字符为'*'
else if(ch02=='*'){
if(h>1){
//按照规则，先在同一行回退两格，若该值为true则直接赋值true
if(table[j][h-2]==true) table[j][h]=true;
else {
//若不为true，则比较当前行的字符（s里的）与当前列-1的字符（p里的）是否相等
char prev=p.charAt(h-2);
//若相等 || 当前列-1的字符（p里的）为'.'，将当前位置上方的值赋给当前位置
if(ch01==prev||prev=='.') table[j][h]=table[j-1][h];
}
}
}
}
}
//返回table表的最右下方元素，即为整个字符串的匹配结果
return table[s.length()][p.length()];
}
/**
* 高往低走，长度变小、高度变小、面积一定变小
* 低往高走，长度变小、高度可能变大、面积可能变大
*/
public int maxArea(int[] height) {
int i = 0, j = height.length - 1, res = 0;
while(i < j) {
res = height[i] < height[j]
? Math.max(res, (j - i) * height[i++])
: Math.max(res,(j - i) * height[j--]);
}
return res;
}
/*
思路：排序 + 双指针
-4,1,2,3
当前元素(target)的下一个元素(left)为起点、最后一个元素(right)为终点进行计算
情况1：target + left + right == 0 》 正确
情况2：target + left + right > 0 》 说明 right 数值太大，right--
情况3：target + left + right < 0 》 说明 left 数值太小，left++
*/
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < nums.length ; i++) {
// 当前元素>0 后面的所有元素肯定都>0，所以提前结束
if(nums[i] > 0) break;
// 当前元素和前一个元素相同，说明发现重复数字，无需再次计算
if(i > 0 && nums[i] == nums[i-1]) continue;
int left = i+1;
int right = nums.length-1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[left],nums[right]));
// [-2,0,0,2,2] 跳过相同数字，去重
while (left<right && nums[left] == nums[left+1]) left++;
// [-2,0,0,2,2] 跳过相同数字，去重
while (left<right && nums[right] == nums[right-1]) right--;
left++;
right--;
}
else if (sum < 0) left++;
else right--;
}
}
return ans;
}
private StringBuilder sb = new StringBuilder();
private List<String> answer = new ArrayList<>();
/*
思路：获取对应字母的字符串，递归组合
*/
public List<String> letterCombinations(String digits) {
if(digits.equals("")) return new ArrayList<>();
String[] nums = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> list = new ArrayList<>(4);
for (int i = 0; i < digits.length(); i++) list.add(nums[Integer.parseInt(digits.charAt(i)+"")]);
assemble(list,0);
return answer;
}
private void assemble(List<String> list, int index) {
if (index == list.size()){
answer.add(sb.toString());
return;
}
String numChars = list.get(index);
for (int i = 0; i < numChars.length(); i++) {
// 组装
sb.append(numChars.charAt(i));
assemble(list,index+1);
// 回溯
sb.deleteCharAt(index);
}
}
/*
思路：双指针，start，end
start定位正数第n个结点，然后end和start循环后移，当start指向最后一个元素时，end就指向了要删除元素的前一个结点
注意：删除头结点或尾结点时会存在问题，所以新建一个空的前驱结点做为头结点
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre = new ListNode(0);
pre.next = head;
ListNode start = pre, end = pre;
while(n != 0) {
start = start.next;
n--;
}
while(start.next != null) {
start = start.next;
end = end.next;
}
end.next = end.next.next;
return pre.next;
}
/*
配对问题，优先考虑栈
*/
public boolean isValid(String s) {
final Map<Character,Character> map = new HashMap<Character,Character>(){{
put('{','}'); put('[',']'); put('(',')');
}};
Stack<Character> stack = new Stack<Character>();
// 保证栈不为空，如果第一个字符为 }]) 中的一种会出现 空栈pop
stack.push('1');
for(Character c : s.toCharArray()){
if(map.containsKey(c)) stack.push(c);
else if(map.get(stack.pop()) != c) return false;
}
return stack.size() == 1;
}
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode node = new ListNode(),head = node;
while (true){
if (list1 == null && list2 == null){
return head.next;
}else if (list1 == null){
node.next = new ListNode(list2.val);
list2 = list2.next;
}else if (list2 == null){
node.next = new ListNode(list1.val);
list1 = list1.next;
}else {
if (list1.val > list2.val){
node.next = new ListNode(list2.val);
list2 = list2.next;
}else {
node.next = new ListNode(list1.val);
list1 = list1.next;
}
}
node = node.next;
}
}
/*
回溯： 左括号的数量 < n那，加'('
右括号的数量 < 左括号的数量,加')'
StringBuilder的元素长度== n 结束
*/
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
dfs(n, 0, 0,res,sb);
return res;
}
public void dfs(int n, int left, int right,List<String> res,StringBuilder sb) {
if (sb.length() == n*2){
res.add(sb.toString());
return;
}
if(left < n){
sb.append("(");
dfs(n,left+1,right,res,sb);
sb.deleteCharAt(sb.length()-1);
}
if (right < left){
sb.append(")");
dfs(n,left,right+1,res,sb);
sb.deleteCharAt(sb.length()-1);
}
}
//-----------------------------解法1----------------------------------------
// （不推荐）：暴力求解，获取所有元素排序后生成
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> list = new ArrayList<>();
for (ListNode node : lists) {
while (node != null){
list.add(node.val);
node = node.next;
}
}
list.sort(Comparator.comparingInt(o -> o));
ListNode listNode = new ListNode(0),p = listNode;
for (Integer val : list) {
p.next = new ListNode(val);
p = p.next;
}
return listNode.next;
}
//-----------------------------解法2----------------------------------------
// 解法2：获取每个链表中的最小值
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
ListNode head = new ListNode(0),p = head;
while (true) {
int minIndex = -1,minVal = Integer.MAX_VALUE;
for (int i = 0; i < k; i++) {
if (lists[i] == null) {
continue;
}
if (lists[i].val < minVal) {
minVal = lists[i].val;
minIndex = i;
}
}
if (minVal == Integer.MAX_VALUE) {
break;
}
lists[minIndex] = lists[minIndex].next;
p.next = new ListNode(minVal);
p = p.next;
}
return head.next;
}
/*
思路： 1. 倒叙遍历，找到大于前一个元素的元素，为了好理解这里称 pre为前一个元素，current为当前元素
2. 将当前元素及后续元素进行升序排序，用于确保是最小序列。1,3,2=>1,2,3
3. 查询比pre大的那个最小元素并交换 1,2,3 => 1,3,2
*/
public void nextPermutation2(int[] nums) {
int len = nums.length;
for (int i = len - 1; i > 0; i--) {
if (nums[i] > nums[i - 1]) {
Arrays.sort(nums, i, len);
for (int j = i; j <len; j++) {
if (nums[j] > nums[i - 1]) {
swap(nums,i-1,j);
return;
}
}
}
}
// 降序排列数组
Arrays.sort(nums);
}
// 交换数组元素
public void swap(int[] nums,int i,int j){
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
/*
第11题升级版，在11题的基础上修改成下标存储，下标计算长度
*/
public int longestValidParentheses(String s) {
LinkedList<Integer> st = new LinkedList<>();
int ans = 0;
for(int i = 0 ,start = 0;i < s.length();i ++){
if( s.charAt(i) == '(') {
st.addFirst(i);
}else if(!st.isEmpty()){
st.pop();
ans = st.isEmpty() ? Math.max(ans,i - start + 1) : Math.max(ans,i - st.peek());
}else{
start = i + 1;
}
}
return ans;
}
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1, mid = 0;
while (l <= r) {
mid = l + (r - l) / 2;
if (nums[mid] == target) {
return mid;
}
// 先根据 nums[mid] 与 nums[l] 的关系判断 mid 是在左段还是右段
if (nums[mid] >= nums[l]) {
// 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 lo 和 hi
if (target >= nums[l] && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[r]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
/*
1. 二分查找左侧边界
2. 二分查找右侧边界
*/
public int[] searchRange(int[] nums, int target) {
int leftIdx = binarySearch(nums, target, true);
int rightIdx = binarySearch(nums, target, false) - 1;
if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
return new int[]{leftIdx, rightIdx};
}
return new int[]{-1, -1};
}
/**
* @param nums 源数组
* @param target 目标元素
* @param flag 方向标志：true左 false右
*/
public int binarySearch(int[] nums, int target, boolean flag) {
int left = 0, right = nums.length - 1, ans = nums.length;
while (left <= right) {
int mid = (left + right) >> 1;
if (nums[mid] > target || (flag && nums[mid] == target)) {
right = mid - 1;
ans = mid;
}else{
left = mid + 1;
}
}
return ans;
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// 排序用于提前剪枝
Arrays.sort(candidates);
List<List<Integer>> listAnswer = new ArrayList<>();
dfs(candidates,0,target,0,new LinkedList<>(),listAnswer);
return listAnswer;
}
public void dfs(int[] candidates,int beginIndex,int target,int sum,LinkedList<Integer> path,List<List<Integer>> listAnswer){
if (target == sum){
listAnswer.add(new ArrayList<>(path)) ;
return;
}
for (int i = beginIndex; i < candidates.length; i++) {
// 在数组升序的情况下，如果 sum+当前元素> target 那么sum+当前元素之后的任意元素也大于target，所以提前break剪枝
if (sum + candidates[i] > target)
break;
path.addLast(candidates[i]);
dfs(candidates,i,target,sum+candidates[i],path,listAnswer);
path.removeLast();
}
}
/*
按列求，当前列的存水量取决于，min = Math.min(左侧最大值,右侧最大值)，分三种情况：
1. min > 当前列：存水量为 min-当前列
2. min = 当前列：存水量为0
3. min < 当前列：存水量为0
即：只有 min>当前列的时候才会存水
*/
public int trap(int[] height) {
int sum = 0;
for (int i = 1; i < height.length; i++) {
int maxLeft = 0,maxRight = 0;
for (int j = i-1; j >= 0; j--) {
maxLeft = Math.max(maxLeft,height[j]);
}
for (int j = i+1; j < height.length; j++) {
maxRight = Math.max(maxRight,height[j]);
}
int min = Math.min(maxLeft, maxRight);
if (min > height[i]){
sum += min-height[i];
}
}
return sum;
}
/*
不存在重复元素的全排列，优先使用 递归法
存在重复元素的全排列，优先使用 抓取法
*/
private void swap(int[] nums,int i,int j){
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
public List<List<Integer>> permute(int[] nums) {
ArrayList<List<Integer>> answer = new ArrayList<>();
dfs(nums,0, answer);
return answer;
}
public void dfs(int[] nums,int k,List<List<Integer>> answer){
// 边界
if (k == nums.length){
ArrayList<Integer> list = new ArrayList<>();
for (int num : nums)
list.add(num);
answer.add(list);
return;
}
for (int i = k; i < nums.length; i++) {
swap(nums,i,k);
dfs(nums,k+1,answer); // 递归
swap(nums,i,k); // 回溯
}
}
/*
由外到内原地交换
*/
public void rotate(int[][] matrix) {
int n = matrix.length;
int len = (n + 1) >>> 1;
for (int i = 0; i < n/2; i++) {
for (int j = 0; j < len; j++) {
int temp = matrix[i][j]; // 左上角
matrix[i][j] = matrix[n - 1 - j][i]; // 左上角等于左下角
matrix[n - 1 - j][i] = matrix[n-1-i][n-1-j];// 左下角等于右下角
matrix[n-1-i][n-1-j] = matrix[j][n-1-i]; // 右下角等于右上角
matrix[j][n-1-i] = temp; // 右上角等于左上角
}
}
}
/*
方法1：groupingBy分组
*/
public List<List<String>> groupAnagrams(String[] strs) {
return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(e->{
char[] chars = e.toCharArray();
Arrays.sort(chars);
return new String(chars);
})).values());
}
/*
方法2：stream 对字符串排序，这样只需要一行代码即可
*/
public List<List<String>> groupAnagrams(String[] strs) {
// str -> intstream -> sort -> collect by StringBuilder
return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> str.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString())).values());
}
/*
方法3：对字符串排序，使用字符串分割排序
*/
public List<List<String>> groupAnagrams(String[] strs) {
return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(s-> Stream.of(s.split("")).sorted().collect(Collectors.joining()))).values());
}
/*
动态规划：子问题为 求两个数的和（正向）
分为两种情况：
1. currentSum + nums[i] < nums[i];
2. currentSum + nums[i] >= nums[i];
*/
public int maxSubArray(int[] nums) {
int currentSum = 0,maxSum = nums[0];
for (int i = 0; i < nums.length; i++) {
currentSum = Math.max(currentSum + nums[i], nums[i]);
maxSum = Math.max(currentSum,maxSum);
}
return maxSum;
}
/*
第一次使用递归，但是超时了
第二次思路：
1. 如果不存在 0，那么一定会跳跃到最后
2. 如果存在 0，判断一下0之前的元素能不能跳过当前位置
*/
public boolean canJump(int[] nums) {
int maxIndex = 0; // 可以跳到的最远位置
for (int i = 0; i < nums.length; i++) {
// 如果当前位置超过了可以跳到的最远位置，直接false
if (i > maxIndex) return false;
// 最远位置=当前位置+当前可到达的最远位置
maxIndex = Math.max(maxIndex,i+nums[i]);
}
return true;
}
/*
{{1,3},{2,6},{8,10},{15,18}}
在区间有序的情况下
当前数组的最大元素 >= 下一个数组的最小元素 ： 结束位置取最大
当前数组的最大元素 < 下一个数组的最小元素 ： 添加新区间
*/
public int[][] merge(int[][] intervals) {
// 根据区间的开始位置进行排序
Arrays.sort(intervals, Comparator.comparingInt(v -> v[0]));
int[][] res = new int[intervals.length][2];
res[0] = intervals[0];
int index = 0;
for (int i = 1; i < intervals.length; i++) {
if (res[index][1] < intervals[i][0]) {
res[++index] = intervals[i];
} else {
res[index][1] = Math.max(res[index][1], intervals[i][1]);
}
}
return Arrays.copyOf(res, index+1);
}
// 动态规划入门题型
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int i = 0; i < n; i++) dp[0][i] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
// 动态规划入门题
public int minPathSum(int[][] grid) {
int m = grid.length,n = grid[0].length;
// 行
for (int i = 1; i < n; i++) grid[0][i] += grid[0][i-1];
// 列
for (int i = 1; i < m; i++) grid[i][0] += grid[i-1][0];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);
}
}
return grid[m - 1][n - 1];
}
/*
动态规划入门题
设有 f(n) 种爬法，因为一次可以爬 1 或 2 个台阶
当剩余一个台阶的时候，有 f(n-1) 种爬法
当剩余两个台阶的时候，有 f(n-2) 种爬法
即：f(n) = f(n-1) + f(n-2)
*/
public int climbStairs(int n) {
if (n <= 2) return n;
int a = 1,b = 2,c;
for (int i = 3; i <= n; i++) {
c = b;
b += a;
a = c;
}
return b;
}
/*
动态规划：解题思路
1. 定义一个二维数组dp，其中dp[i][j]表示序列s1的前i个字符和序列s2的前j个字符的最长公共子序列的长度。
2. 初始化dp数组的第一行和第一列，即dp[0][j]和dp[i][0]均为0，表示空序列与任意序列的最长公共子序列长度为0。
3. 遍历序列s1和s2，有两种情况
1) 如果s1[i-1]等于s2[j-1]，dp[i][j]等于dp[i-1][j-1] + 1，表示当前字符是最长公共子序列的一部分
2) 不等于的话，dp[i][j]等于dp[i-1][j]和dp[i][j-1]的较大值，表示当前字符不是最长公共子序列的一部分。
4. 最后，dp[m][n]即为序列s1和s2的最长公共子序列的长度，其中m和n分别为序列s1和s2的长度。
*/
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (text1.charAt(i-1) == text2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] +1;
}else {
dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
}
}
}
return dp[n][m];
}
/*
动态规划：
dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
1. 当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
2. 当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
*/
public int minDistance (String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// 第一行
for (int j = 1; j <= n; j++) dp[0][j] = dp[0][j - 1] + 1;
// 第一列
for (int i = 1; i <= m; i++) dp[i][0] = dp[i - 1][0] + 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
}
}
return dp[m][n];
}
/*
双指针：start表示0的起始位置，end表示2的位置，三种情况
1. nums[i] == 0，交换 start和0，start后移一位
2. nums[i] == 2，交换 end和2，end前移一位
3. nums[i] == 1，不用管，因为1就是在中间位置
结束条件：i>end，即元素已全部遍历
*/
public void sortColors(int[] nums) {
int start = 0,end = nums.length-1,i = 0;
while (i <= end){
if (nums[i] == 0){
swap(nums,start++,i++);
}else if (nums[i] == 2){
swap(nums,end--,i);
}else {
i++;
}
}
}
/*
滑动窗口
*/
public String minWindow(String s, String t) {
int[] need = new int[128],had = new int[128];
for (int i = 0; i < t.length(); i++) {
need[t.charAt(i)]++;
}
int l = 0, r = -1,minLen = s.length()+1, ansL = -1, ansR = -1;
int sLen = s.length();
while (r++ < sLen) {
if (r < sLen && need[s.charAt(r)] > 0)
had[s.charAt(r)]++;
while (check(need,had) && l <= r) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
ansL = l;
ansR = l + minLen;
}
// 去除重复的字符
if (need[s.charAt(l)] > 0)
had[s.charAt(l)]--;
++l;
}
}
return ansL == -1 ? "" : s.substring(ansL, ansR);
}
private boolean check(int[] need, int[] have) {
for (int i = 0; i < need.length; i++) {
if (need[i] >have[i]) return false;
}
return true;
}
// 递归
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> temp = new LinkedList<>();
dfs(nums,0,res,temp);
return res;
}
void dfs(int[] nums,int k,List<List<Integer>> list,LinkedList<Integer> temp){
list.add(new ArrayList<>(temp));
for (int i = k; i < nums.length; i++) {
temp.add(nums[i]);
dfs(nums,i+1,list,temp);
temp.removeLast();
}
}
/*
思路：
递归深搜，每个元素都可以为起点
每个起点都面临上下左右四种选择，所以要判断一下边界和是否访问
剪枝：记录下标，只对那些满足要求的元素进行移动
*/
public boolean exist(char[][] board, String word) {
char[] wordChars = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board,i,j,0,wordChars)) return true;
}
}
return false;
}
public boolean dfs(char[][] board,int r,int c,int k,char[] wordChars){
// 边界
if (r < 0 || r>= board.length || c < 0 || c >= board[0].length || board[r][c] != wordChars[k]){
return false;
}
if (k == wordChars.length-1){
return true;
}
// 修改已访问
board[r][c] = '.';
// 上下左右移动
boolean answer = dfs(board,r-1,c,k+1,wordChars) || dfs(board,r+1,c,k+1,wordChars) ||
dfs(board,r,c-1,k+1,wordChars) || dfs(board,r,c+1,k+1,wordChars);
// 回溯
board[r][c] = wordChars[k];
return answer;
}
public int largestRectangleArea(int[] heights) {
int n = heights.length;
// 保存左侧下标
int[] left = new int[n];
// 保存右侧下标
int[] right = new int[n];
Arrays.fill(right, n);
Deque<Integer> mono_stack = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
// 栈不为空并且上一个元素大于当前元素
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
right[mono_stack.peek()] = i;
mono_stack.pop();
}
left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
mono_stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
/*
定位中间元素，拆分左右先序和中序数组进行递归
*/
private static int find(int[] array, int v){
for (int i=0;i<array.length;i++){
if (array[i] == v){
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length==0){
return null;
}
//1、根据前序，找到根的值，并且创建根节点
int rootValue = preorder[0];
TreeNode root = new TreeNode(rootValue);
//2、在中序中找到根的值所在的下标
int leftIndex = find(inorder,rootValue);
//3、切出左子树的前序和中序
int[] leftPreorder = Arrays.copyOfRange(preorder,1,1+leftIndex);
int[] leftInorder = Arrays.copyOfRange(inorder,0,leftIndex);
root.left = buildTree(leftPreorder,leftInorder);
//4、切出右子树的前序和中序
int[] rightPreorder = Arrays.copyOfRange(preorder,1+leftIndex,preorder.length);
int[] rightInorder = Arrays.copyOfRange(inorder,leftIndex+1,preorder.length);
root.right = buildTree(rightPreorder,rightInorder);
return root;
}
// 不会
// 1. 递归法
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
void inorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
inorder(root.left, list);
list.add(root.val);
inorder(root.right, list);
}
// 2. 迭代法
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (stack.size() >0 || root != null){
if (root != null){
stack.push(root);
root = root.left;
}else {
TreeNode node = stack.pop();
res.add(node.val);
root = node.right;
}
}
return res;
}
/*
中序遍历：二叉搜索树中序遍历为升序，所以比较上个元素的值和当前元素的值即可
*/
long longMin = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (!isValidBST(root.left)) return false;
if (longMin >= root.val) return false;
longMin = root.val;
return isValidBST(root.right);
}
/*
思路：直接递归判断左右结点的值是否相同，需要注意的是当 结点为null的时候有两种情况
1. 两个结点都为null，返回 true
2. 两个结点其中一个为null，返回false
*/
public boolean isSymmetric(TreeNode node) {
return checkSymmetric(node.left, node.right);
}
private boolean checkSymmetric(TreeNode left, TreeNode right) {
if (left == null || right == null) return left == right;
if (left.val != right.val) return false;
return checkSymmetric(left.right, right.left) && checkSymmetric(left.left, right.right);
}
/*
宽搜即可，注意返回结果每层为一个集合，所以记录一下每层结点的数量用for循环去处理
*/
public List<List<Integer>> levelOrder(TreeNode root) {
ArrayList<List<Integer>> answer = new ArrayList<>();
if (root == null){
return answer;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
List<Integer> item = new ArrayList<>();
int currentSize = queue.size();
for (int i = 0; i < currentSize; i++) {
TreeNode node = queue.poll();
if (node == null) continue;
item.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
answer.add(item);
}
return answer;
}
// 递归
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.right),maxDepth(root.left))+1;
}
/* 解法1：
暴力解：先序遍历，将所有元素保存到集合中，遍历集合设置左节点为 null
树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100
*/
public void flatten(TreeNode root) {
// 为空判断
if (root == null || (root.left == null && root.right == null)){
return;
}
LinkedList<TreeNode> result = new LinkedList<>();
// 先序遍历添加到result中
getFirst(root,result);
TreeNode head = result.get(0);
for (int i = 1; i < result.size(); i++) {
head.left = null;
head.right = result.get(i);
head = head.right;
}
}
private void getFirst(TreeNode root, LinkedList<TreeNode> result) {
// 结束
if (root == null) return;
result.add(root);
if (root.left != null) getFirst(root.left,result);
if (root.right != null) getFirst(root.right,result);
}
// 解法2，将左子结点转移到右子节点
public void flatten(TreeNode root) {
if(root == null){
return ;
}
flatten(root.left);
flatten(root.right);
TreeNode temp = root.right;
root.right = root.left;
//记得要将左边置空
root.left = null;
//找到树的最右边的节点
while(root.right != null) root = root.right;
//把右边的链表接到刚才树的最右边的节点
root.right = temp;
}
public int maxProfit(int[] prices){
int maxAnswer = 0,minTarget = prices[0];
for (int i = 1; i < prices.length; i++) {
minTarget = Math.min(minTarget,prices[i]);
maxAnswer = Math.max(prices[i] - minTarget,maxAnswer);
}
return maxAnswer;
}
/*
递归计算每个结点的贡献度
*/
public int maxPathSum(TreeNode root) {
dfs(root);
return maxSum;
}
private void dfs(TreeNode node){
if (node == null){
return;
}
dfs(node.left);
dfs(node.right);
// 左子结点贡献值
int left = node.left == null?0:node.left.val;
// 右子节点贡献值
int right = node.right == null ? 0 : node.right.val;
// 计算当前最大值
maxSum = Math.max(node.val + left + right,maxSum);
// 当前结点的值为 max(0，当前结点，当前结点+左子结点，当前结点+右子节点)
node.val = Math.max(node.val,node.val+Math.max(left,right));
node.val = Math.max(0, node.val);
}
public int longestConsecutive(int[] nums) {
if (nums.length < 1){
return 0;
}
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int currentLen = 0,maxLen = 0;
for (Integer num : set) {
// 去重
if (!set.contains(num-1)){
while (set.contains(num+1)){
num += 1;
currentLen++;
maxLen = Math.max(currentLen,maxLen);
}
currentLen = 0;
}
}
return maxLen+1;
}
// 异或运算，相同为0，不同为1
public int singleNumber(int[] nums) {
int num = 0;
for (int i : nums) {
num ^= i;
}
return num;
}
// 第一时间想到的就是递归，但是时间超了
public boolean wordBreak(String s, List<String> wordDict) {
for (int i = 0; i < wordDict.size(); i++) {
String str = wordDict.get(i);
// 确定开头字符串
if (dfs(str,wordDict,s,0)){
return true;
}
}
return false;
}
private boolean dfs(String result,List<String> wordDict,String s,int index){
// 边界
if (result.equals(s)){
return true;
}
if (s.startsWith(result) && index < wordDict.size()){
for (int i = index; i < wordDict.size(); i++) {
String nowStr = result+wordDict.get(i);
if (dfs(nowStr,wordDict,s,index) || dfs(result,wordDict,s,index+1)){
return true;
}
}
}
return false;
}
// 2. 修改为动态规划，截取字符串并使用哈希表判断包不包含截取的字符串
public boolean wordBreak(String s, List<String> wordDict){
Set<String> set = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for (int r = 1; r <= s.length(); r++) {
for (int l = 0; l < r; l++) {
if (dp[l] && set.contains(s.substring(l,r))){
dp[r] = true;
}
}
}
return dp[s.length()];
}
// 1. 双指针
public boolean hasCycle(ListNode head) {
ListNode slow = head,fast = head;
while (slow != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if (slow == fast){
return true;
}
}
return false;
}
// 2. hash表
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
while (head!=null){
set.add(head);
ListNode next = head.next;
if (next != null && set.contains(next)){
return true;
}
head = next;
}
return false;
}
// 1. 和上题一样，但空间复杂度为 O(n)
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
while (head!=null){
set.add(head);
ListNode next = head.next;
if (next != null && set.contains(next)){
return true;
}
head = next;
}
return false;
}
// 2. 双指针，虽然简单，但是一下子没想出来
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while (true) {
if (fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
/*
LRU：最少最近使用
LFU：最少频率使用
*/
class LRUCache {
class ListNode {
int key;
int val;
ListNode next;
ListNode() {
}
ListNode(int key,int val) {
this.val = val;
this.key = key;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
private ListNode listNode;
private int capacity;
private int size = 0;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public ListNode getNode(int key) {
if (listNode == null) return null;
ListNode current = listNode.next,pre = listNode;
if (pre.key == key) return pre;
while (current != null){
if (current.key == key){
pre.next = current.next;
current.next = listNode;
listNode = current;
return current;
}
pre = current;
current = current.next;
}
return null;
}
public int get(int key){
ListNode node = getNode(key);
return node == null ? -1 : node.val;
}
public void put(int key, int value) {
ListNode node = getNode(key);
if (node != null){
node.val = value;
return;
}
size++;
ListNode newNode = new ListNode(key,value);
if (listNode == null){
listNode = newNode;
}else {
newNode.next = listNode;
listNode = newNode;
}
if (size == capacity+1){
size = capacity;
// 删除尾结点
ListNode pre = listNode,current = listNode.next;
while (current.next != null){
pre = current;
current = current.next;
}
pre.next = null;
}
}
}
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(tmp);
ListNode h = new ListNode(0);
ListNode res = h;
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
}
/* 动态规划
记录乘积最大值和最小值
两种情况：
1. 当前值 < 0，最小值变最大值
2. 当前值 >= 0，不变
*/
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE, imax = 1, imin = 1;
for(int i=0; i<nums.length; i++){
if(nums[i] < 0){
int tmp = imax;
imax = imin;
imin = tmp;
}
imax = Math.max(imax*nums[i], nums[i]);
imin = Math.min(imin*nums[i], nums[i]);
max = Math.max(max, imax);
}
return max;
}
// 辅助栈
public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> min_stack;
public MinStack() {
stack = new Stack<>();
min_stack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if(min_stack.isEmpty() || x <= min_stack.peek())
min_stack.push(x);
}
public void pop() {
if(stack.pop().equals(min_stack.peek()))
min_stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min_stack.peek();
}
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA, B = headB;
while (A != B) {
A = A != null ? A.next : headB;
B = B != null ? B.next : headA;
}
return A;
}
/*
方法1：排序，直接返回中间下标元素
方法2：计数，摩尔投票法，票数正负抵消
*/
public int majorityElement(int[] nums) {
int result = 0,answer = 0;
for (int num : nums) {
if (result == 0) answer = num;
result += num == answer ? 1 : -1;
}
return answer;
}
/*
动态规划：[1,2,3,1]
设可以偷到的最大金额为 f(n)
1. 当数组只有一个元素时，即 f(1) = 1
2. 当数组只有两个元素时，即 f(2) = 2
3. ...，f(3) = max(3+1，f(1))
n. ...，f(n) = max(n + f(n-2)，f(n-1))
*/
public int rob(int[] nums) {
int[] dp = new int[nums.length+1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= nums.length; i++) {
dp[i] = Math.max(nums[i-1]+dp[i-2],dp[i-1]);
}
return dp[nums.length];
}
/*
深搜往死搜就完了
每一个位置只会出现 '0' '1'，也就意味着出现了 ‘1’肯定就会出现岛屿
所以对为‘1’位置的元素进行连通性检测并把检测到的'1'改为 '0',
*/
public int numIslands(char[][] grid) {
int answer = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1'){
dfs(grid,i,j);
answer++;
}
}
}
return answer;
}
void dfs(char[][] grid,int i,int j){
if (i < 0 || i>=grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
grid[i][j] = '0';
dfs(grid,i+1,j);
dfs(grid,i-1,j);
dfs(grid,i,j+1);
dfs(grid,i,j-1);
}
public ListNode reverseList(ListNode head) {
ListNode p = null,current = head;
while (current != null) {
ListNode temp = current.next;
current.next = p;
p = current;
current = temp;
}
return p;
}
/*
拓扑排序
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> list = new ArrayList<>(numCourses);
for (int i = 0; i < numCourses; i++) {
list.add(new ArrayList<>());
}
// 设置路径
for (int i = 0; i < prerequisites.length; i++) {
list.get(prerequisites[i][1]).add(prerequisites[i][0]);
}
int[] flag = new int[numCourses];
for (int i = 0; i < list.size(); i++) {
if (!f(list,flag,i)){
return false;
}
}
return true;
}
public boolean f(List<List<Integer>> list,int[] flag,int index){
if (flag[index] == -1) return true;
if (flag[index] == 1) return false;
flag[index] = 1;
for (Integer j : list.get(index)) {
if (!f(list,flag,j)){
return false;
}
}
flag[index] = -1;
return true;
}
// 1.（不推荐）哈希表暴力直接过
import java.util.HashSet;
import java.util.Set;
class Trie {
private static Set<String> set;
public Trie() {//初始化前缀树对象。
set = new HashSet<>();
}
public void insert(String word) {//向前缀树中插入字符串 word 。
set.add(word);
}
public boolean search(String word) {//如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
return set.stream().filter(e -> e.equals(word)).count() > 0;
}
public boolean startsWith(String prefix) {//如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
return set.stream().filter(e -> e.startsWith(prefix)).count() > 0;
}
}
// --------------------------方法2-----------------------------
/*
记录插入的每一个字符，isEnd记录结束位置，查询时判断每个字符是否存在
*/
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
public void insert(String word) {
Trie node = this;
// aab 001
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private Trie searchPrefix(String prefix) {
Trie node = this;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
}
// 1. 暴力：直接排序返回第k个大的元素
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length-k];
}
// ---------------------方法2-----------------------------
/*
快速选择：快排思想的改进
1. 将元素分为三部分：大于基点的元素，小于基点的元素，等于基点的元素
2. 遍历每一个元素，添加到对应的集合中
3. 递归调用
*/
private int quickSelect(List<Integer> nums, int k) {
// 随机选择基准数
Random rand = new Random();
int pivot = nums.get(rand.nextInt(nums.size()));
// 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中
List<Integer> big = new ArrayList<>();
List<Integer> equal = new ArrayList<>();
List<Integer> small = new ArrayList<>();
// O(n)
for (int num : nums) {
if (num > pivot)
big.add(num);
else if (num < pivot)
small.add(num);
else
equal.add(num);
}
// 第 k 大元素在 big 中，递归划分
if (k <= big.size())
return quickSelect(big, k);
// 第 k 大元素在 small 中，递归划分
if (nums.size() - small.size() < k)
return quickSelect(small, k - nums.size() + small.size());
// 第 k 大元素在 equal 中，直接返回 pivot
return pivot;
}
public int findKthLargest(int[] nums, int k) {
List<Integer> numList = new ArrayList<>();
for (int num : nums) {
numList.add(num);
}
return quickSelect(numList, k);
}
/*
动态规划：dp[i][j]：以matrix[i][j]为右下角的最大的正方形边长
两种情况：
matrix[i][j] 为 0时，最大变成边长为0，即dp[i][j] = 0
marrix[i][j] 不为0，最大边长为 左上方，上方，左方，三个最大的边长+1
即状态转移方程为：dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
*/
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0) {
return 0;
}
int M = matrix.length;
int N = matrix[0].length;
int[][] dp = new int[M+1][N+1];
int result = 0;
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= N; j++) {
if (matrix[i-1][j-1] == '0') {
continue;
}
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
result = Math.max(result, dp[i][j]);
}
}
return result*result;
}
// 递归
public TreeNode invertTree(TreeNode root) {
resveser(root);
return root;
}
private void resveser(TreeNode root){
if (root == null) return;
TreeNode left = root.left;
root.left = root.right;
root.right = left;
invertTree(root.left);
invertTree(root.right);
}
// 方法1：存到集合中，然后双指针
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<>();
// 将链表的值复制到数组中
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
int l = 0;
int r = vals.size() - 1;
while (l < r) {
if (!vals.get(l).equals(vals.get(r))) {
return false;
}
l++;
r--;
}
return true;
}
// 方法2：递归
private ListNode headNode;
public boolean isPalindrome(ListNode head) {
headNode = head;
return recursivelyCheck(head);
}
// 递归判断当前结点和头部结点是否相同
private boolean recursivelyCheck(ListNode current) {
// 非空判断并且移动道尾结点
if (current != null){
if (!recursivelyCheck(current.next)) return false;
if (current.val != headNode.val) return false;
//头结点后移
headNode = headNode.next;
}
// 为null或者满足条件返回true
return true;
}
/*
三种情况：
1. p,q在root的两边，root为最近公共祖先
2. p在q的下边，q为最近公共祖先
3. q在p的下面，p为最近公共祖先
思路：先序遍历，查找左右结点是否存在p、q
情况1：root.left != null && root.right != null return root
情况1：root.left != null && root.right == null return root.left
情况2：root.left == null && root.right ！= null return root.right
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 边界检查
if (root == null) return null;
if (root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if (left != null && right != null) return root;
if (left != null && right == null) return left;
if (left == null && right != null) return right;
return null;
}
/*
思路：分别计算当前元素的左右乘积，先算左后算右
*/
public int[] productExceptSelf(int[] nums) {
if (nums.length == 0){
return new int[0];
}
int[] ans = new int[nums.length];
ans[0] = 1;
for (int i = 1; i < nums.length; i++) {
ans[i] = ans[i - 1] * nums[i - 1];
}
int tmp = 1;
for (int i = nums.length - 2; i >= 0; i--) {
tmp *= nums[i + 1];
ans[i] *= tmp;
}
return ans;
}
/*
思路：单调列表
*/
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0) return new int[0];
int[] answer = new int[nums.length - k + 1];
LinkedList<Integer> list = new LinkedList<>();
// 先计算第一个滑动窗口
for (int i = 0; i < k; i++) {
// 删除小于当前元素的所有元素
while (!list.isEmpty() && list.peekLast() < nums[i]){
list.removeLast();
}
// 添加当前最大元素
list.addLast(nums[i]);
}
int max = list.peek(),index = 0;
answer[index++] = max;
// 移动滑动窗口，重新计算最大值
for (int i = k; i < nums.length; i++) {
// 如果最大元素为上一个窗口的开头，那么删除头部元素
if (!list.isEmpty() && list.peek() == nums[i-k]){
list.removeFirst();
}
// 删除小于当前元素的所有元素
while (!list.isEmpty() && list.peekLast() < nums[i]){
list.removeLast();
}
list.addLast(nums[i]);
answer[index++] = list.peek();
}
return answer;
}
public boolean searchMatrix(int[][] matrix, int target) {
int i = matrix.length - 1, j = 0;
while(i >= 0 && j < matrix[0].length)
{
if(matrix[i][j] > target) i--;
else if(matrix[i][j] < target) j++;
else return true;
}
return false;
}
/*
方法1：递归
i从1开始平方，获取 n/i^2 + n%i^2需要的最小完全平方数的数量
*/
public int numSquares(int n) {
if (n == 0) return 0;
int ans = Integer.MAX_VALUE;
for (int i = 1; i * i < n; i++){
int sqrt = i*i,temp = n % sqrt;
ans = Math.min(ans, n / sqrt + numSquares(temp));
}
return ans;
}
// 记录下标，非0元素前移，下标以后全部元素设置为0
public void moveZeroes(int[] nums) {
int index = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
index++;
nums[index] = nums[i];
}
}
for (int i = index+1; i < nums.length; i++) {
nums[i] = 0;
}
}
// 方法1：哈希表
public int findDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length-1; i++){
if (set.contains(nums[i])) return nums[i];
set.add(nums[i]);
}
return -1;
}
/*
方法2：原地交换
提示：nums[i] <= n 可以推出，数组中的所有元素都是小于长度的，因此可以使用下标代替
交换以 nums[i]和i下标的元素，判断是否相同，有两种情况
1. nums[i] 和 i 相同，如 0 1 2 查找0，直接跳过
2. nums[i] 和 nums[nums[i]] 相同，返回
*/
public int findDuplicate(int[] nums) {
int i = 0;
while (i < nums.length){
if (i == nums[i]){
i++;
continue;
}
if (nums[i] == nums[nums[i]])
return nums[i];
swap(nums,i,nums[i]);
}
return -1;
}