持续更新中
1、26_删除有序数组中的重复项2、58_最后一个单词的长度3、35_搜索插入的位置4、67_二进制求和5、167_两数之和II-输入有序数组6、125_验证回文串7、88_合并两个有序数组8、136_只出现一次的数字9、704_二分查找10、977_有序数组的平方11、1768_交替合并字符串12、20_有效的括号13、1047_删除字符串中所有相邻重复项14、66_加一15、150_逆波兰表达式求值16、1550_存在连续三个奇数之和17、9_回文数18、389_找不同19、239_滑动窗口最大值20、209_长度最小的子数组21、347_前K个高频元素22、1502_判断能否形成等差数组23、3056_分割数组24、3069_将元素分配到两个数组中 I25、459_重复的子字符串26、27_移除元素27、242_有效的字母异位词28、349_两个数组的交集29、14_最长公共前缀30、283_移动零31、1_两数之和32、15_三数之和33、18_四数之和34、2235_两整数之和35、454_四数相加 II36、268_丢失的数字37、1882_数组元素积的符号38、3074_重新分装苹果38、231_2的幂39、326_3的幂40、342_4的幂
二叉树1、144_二叉树的前序遍历2、145_二叉树的后序遍历3、94_二叉树的中序遍历4、102_二叉树的层序遍历
回溯1、77_组合2、216_组合总和 III3、17_电话号码的字母组合4、39_组合总和5、40_组合总和 II6、131_分割回文串7、93_复原IP地址8、78_子集9、90_子集 II10、491_非递减子序列11、46_全排列12、47_全排列 II13、48_N皇后14、37_解数独
矩阵1、59_螺旋矩阵 II2、54_螺旋矩阵
动态规划1、70_爬楼梯2、509_斐波那契数3、746_使用最小话费爬楼梯
贪心1、455_分发饼干2、376_摆动序列3、53_最大子数组和4、122_买卖股票的最佳时机 II5、55_跳跃游戏6、45_跳跃游戏 II
1、26_删除有序数组中的重复项
方法一
class Solution {
public int removeDuplicates(int[] nums) {
int index = 0;
for(int i = 1; i < nums.length; i ++) {
if(nums[i] != nums[index])
nums[++ index] = nums[i];
}
return index + 1;
}
}
方法二 双指针
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 0, fast = 1;
if(nums.length == 0)
return 0;
while(fast < nums.length){
if(nums[slow] != nums[fast]){
slow++;
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast];
}
fast++;
}
// 数组长度为索引 + 1
return slow + 1;
}
}
2、58_最后一个单词的长度
从后往前，遇到空格跳过，遇到字符统计
class Solution {
public int lengthOfLastWord(String s) {
int len = s.length() - 1;
while(s.charAt(len) == ' ' && len >= 0)
len --;
int cnt = 0;
while(len >= 0 && s.charAt(len) != ' ') {
len --;
cnt ++;
}
return cnt;
}
}
3、35_搜索插入的位置
二分法
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while(l <= r) {
int mid = l + (r - l) / 2;
if(target < nums[mid])
r = mid - 1;
else if(target > nums[mid])
l = mid + 1;
else
return mid;
}
return l;
}
}
4、67_二进制求和
从后往前加进位，最后判断是否有进位1
class Solution {
public String addBinary(String a, String b) {
StringBuffer s = new StringBuffer();
int n = Math.max(a.length(), b.length());
int carry = 0;
for(int i = 0; i < n; i ++) {
carry += i < a.length() ? a.charAt(a.length() - 1 - i) - '0' : 0;
carry += i < b.length() ? b.charAt(b.length() - 1 - i) - '0' : 0;
s.append(carry % 2);
carry /= 2;
}
if(carry > 0)
s.append(1);
s.reverse();
return s.toString();
}
}
5、167_两数之和II-输入有序数组
在非递减顺序数组中找两元素之和等于target，下标从1开始
缩减搜索空间的思想，非递减顺序数组
class Solution {
public int[] twoSum(int[] numbers, int target) {
int l = 0, r = numbers.length - 1;
while(l < r) {
int sum = numbers[l] + numbers[r];
if(sum == target)
return new int[]{l + 1, r + 1};
else if(sum > target)
r --;
else
l ++;
}
return null;
}
}
6、125_验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
方法一 使用StringBuffer
class Solution {
public boolean isPalindrome(String s) {
StringBuffer ns1 = new StringBuffer();
for(int i = 0; i < s.length(); i ++) {
if(Character.isLetterOrDigit(s.charAt(i)))
ns1.append(Character.toLowerCase(s.charAt(i)));
}
StringBuffer ns2 = new StringBuffer(ns1).reverse();
return ns1.toString().equals(ns2.toString());
}
}
方法二 双指针 在原字符串上直接判断
class Solution {
public boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while(l < r) {
while(l < r && !Character.isLetterOrDigit(s.charAt(l)))
l ++;
while(l < r && !Character.isLetterOrDigit(s.charAt(r)))
r --;
if(l < r && Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
return false;
l ++;
r --;
}
return true;
}
}
7、88_合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列
方法一
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1, p2 = n - 1, p = m + n - 1;
while (p2 >= 0) { // nums2 还有要合并的元素
// 如果 p1 < 0，那么走 else 分支，把 nums2 合并到 nums1 中
if (p1 >= 0 && nums1[p1] > nums2[p2]) {
nums1[p--] = nums1[p1--]; // 填入 nums1[p1]
} else {
nums1[p--] = nums2[p2--]; // 填入 nums2[p1]
}
}
}
}
把 nums1 的数字移到另一个空位，又产生了一个新的空位，空位个数不变，所以总是有空位可以让 nums2 的数字填入。
方法二
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int x = m - 1, y = n - 1, z = m + n - 1;
int t;
while(x > -1 || y > -1) {
if(x == -1)
nums1[z --] = nums2[y --];
else if(y == -1)
nums1[z --] = nums1[x --];
else if(nums1[x] < nums2[y])
nums1[z --] = nums2[y --];
else
nums1[z --] = nums1[x --];
}
}
}
8、136_只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
异或 一个数和 0 做 XOR 运算等于本身：a⊕0 = a 一个数和其本身做 XOR 运算等于 0：a⊕a = 0 XOR 运算满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b
class Solution {
public int singleNumber(int[] nums) {
int sum = 0;
for(int i : nums)
sum ^= i;
return sum;
}
}
9、704_二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target
如果目标值存在返回下标，否则返回 -1。
class Solution {
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length;
while(l < r) {
int mid = l + (r - l) / 2;
if(target < nums[mid])
r = mid;
else if(target > nums[mid])
l = mid + 1;
else
return mid;
}
return -1;
}
}
10、977_有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
中间数字最小，两边大
class Solution {
public int[] sortedSquares(int[] nums) {
int[] a = new int[nums.length];
int l = 0, r = nums.length - 1, k = nums.length - 1;
while(l <= r) {
if(nums[l] * nums[l] > nums[r] * nums[r]) {
a[k --] = nums[l] * nums[l];
l ++;
}
else {
a[k --] = nums[r] * nums[r];
r --;
}
}
return a;
}
}
11、1768_交替合并字符串
给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。
如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。
class Solution {
public String mergeAlternately(String word1, String word2) {
String s = "";
for(int i = 0; i < word1.length() || i < word2.length(); i ++) {
if(i < word1.length())
s += word1.charAt(i);
if(i < word2.length())
s += word2.charAt(i);
}
return s;
}
}
12、20_有效的括号
1、遇到左括号，就把右括号存进去 2、遇到右括号，栈不为空并且栈顶等于右括号就弹出
方法一
class Solution {
public boolean isValid(String s) {
if (s.length() % 2 != 0)
return false;
Map
Deque
map.put('(', ')');
map.put('{', '}');
map.put('[', ']');
for(int i = 0; i < s.length(); i ++) {
char ch = s.charAt(i);
if(map.containsKey(ch))
stack.push(map.get(ch));
else if(!stack.isEmpty() && ch == stack.peek())
stack.pop();
else
return false;
}
return stack.isEmpty();
}
}
方法二
class Solution {
public boolean isValid(String s) {
if(s.length() % 2 != 0)
return false;
Deque
for(int i = 0; i < s.length(); i ++) {
if(s.charAt(i) == '(')
stack.push(')');
else if(s.charAt(i) == '{')
stack.push('}');
else if(s.charAt(i) == '[')
stack.push(']');
else if(!stack.isEmpty() && stack.peek() == s.charAt(i))
stack.pop();
else
return false;
}
return stack.isEmpty();
}
}
13、1047_删除字符串中所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
方法一 栈
class Solution {
public String removeDuplicates(String s) {
ArrayDeque
for(Character ch : s.toCharArray()) {
if(stack.isEmpty() || ch != stack.peek())
stack.push(ch);
else
stack.pop();
}
StringBuffer str = new StringBuffer();
for(Character ch : stack)
str.append(ch);
return str.reverse().toString();
}
}
方法二 数组模拟栈
class Solution {
public String removeDuplicates(String S) {
char[] s = S.toCharArray();
int top = -1;
for (int i = 0; i < S.length(); i++) {
if (top == -1 || s[top] != s[i]) {
s[++top] = s[i];
} else {
top--;
}
}
//从下标 0 开始的 top + 1 个元素转String
return String.valueOf(s, 0, top + 1);
}
}
14、66_加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
不是9就+1，是9就改为0 最后如果全进位，则数组长度+1，且第一位元素设置为1
class Solution {
public int[] plusOne(int[] digits) {
for(int i = digits.length - 1; i >= 0; i --) {
if(digits[i] != 9) {
digits[i] ++;
return digits;
}
else
digits[i] = 0;
}
digits = new int[digits.length + 1];
digits[0] = 1;
return digits;
}
}
15、150_逆波兰表达式求值
后缀表达式 没遇到操作符就存数字，遇到操作符就从栈弹出两个元素进行运算再存进栈里，最后栈只有一个元素就是结果 用到equals() 和 Integer.parseInt();
class Solution {
public int evalRPN(String[] tokens) {
ArrayDeque
for(int i = 0; i < tokens.length; i ++) {
if("+".equals(tokens[i]) || "-".equals(tokens[i]) || "*".equals(tokens[i]) || "/".equals(tokens[i])) {
int num1 = stack.pop();
int num2 = stack.pop();
if("+".equals(tokens[i]))
stack.push(num2 + num1);
else if("-".equals(tokens[i]))
stack.push(num2 - num1);
else if("*".equals(tokens[i]))
stack.push(num2 * num1);
else
stack.push(num2 / num1);
}
else
stack.push(Integer.parseInt(tokens[i]));
}
return stack.peek();
}
}
16、1550_存在连续三个奇数之和
方法一 三个奇数相乘必定为奇数 只要其中有一个数为偶数则积为偶数 考虑 i 的范围
方法二
双指针
left 和 right 都从0开始判断，如果arr[right]不是奇数，left = right + 1
public boolean threeConsecutiveOdds(int[] arr) {
if(arr.length < 3)
return false;
int len = arr.length;
int left = 0;
for (int right = 0; right < len; right++) {
//如果这个数不为奇数，就让left跳过这个数
//来到right右边的这个数
if (arr[right] % 2 != 1) {
left = right + 1;
}
if (right - left + 1 == 3)
return true;
}
return false;
}
}
17、9_回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
考虑 x < 0 和 个尾为0并且不等于0
class Solution {
public boolean isPalindrome(int x) {
if((x % 10 == 0 && x != 0) || x < 0)
return false;
int sum = 0;
while(x > sum) {
sum = sum * 10 + x % 10;
x /= 10;
}
return sum == x || sum / 10 == x;
}
}
18、389_找不同
给定两个字符串 s 和 t ，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
方法一 位运算
class Solution {
public char findTheDifference(String s, String t) {
int sum = 0;
for(char ch : s.toCharArray())
sum ^= ch;
for(char ch : t.toCharArray())
sum ^= ch;
return (char)sum;
}
}
方法二 求和
方法三 数组
class Solution {
public char findTheDifference(String s, String t) {
int[] a = new int [26];
for(char c : s.toCharArray())
a[c - 'a'] ++;
for(char c : t.toCharArray())
a[c - 'a'] --;
for(int i = 0; i < 26; i ++)
if(a[i] != 0)
return (char)(i + 'a');
return ' ';
}
}
19、239_滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque
int n = nums.length;
//最大值个数为 n- k + 1
int[] ans = new int[n - k + 1];
for(int i = 0; i < n; i ++) {
//每次遍历元素，维护单调性，第一个必须是最大的
while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i])
deque.pollLast();
deque.offerLast(i);
//超过k位，最大值可能变化
if(i - deque.peekFirst() >= k)
deque.pollFirst();
//记录最大值
if(i >= k - 1)
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
}
20、209_长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。
如果不存在符合条件的子数组，返回 0 。
当sum >= target 满足，就减去nums[left]，缩减长度 当sum >= target 不满足，就加上nums[right]，增加长度
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, min = Integer.MAX_VALUE, sum = 0;
for(int right = 0; right < nums.length; right ++) {
sum += nums[right];
while(sum >= target) {
min = min < right - left + 1 ? min : right - left + 1;
sum -= nums[left];
left ++;
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}
21、347_前K个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
当向PriorityQueue中添加元素时，根据Comparator中定义的规则，新加入的元素会被放置到合适的位置以保持队列的顺序性。通常情况下，在添加元素时，PriorityQueue会自动调整元素的顺序，确保队首元素是最小（或最大）的元素。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
HashMap
for(int num : nums){
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
// 遍历map，用最小堆保存频率最大的k个元素
PriorityQueue
@Override
public int compare(Integer a, Integer b) {
return map.get(a) - map.get(b);
}
});
for(Integer key : map.keySet()) {
if(pq.size() < k) {
pq.add(key);
} else if(map.get(key) > map.get(pq.peek())) {
pq.remove();
pq.add(key);
}
}
// 取出最小堆中的元素
int[] res = new int[k];
for (int i = 0; i < k; i++)
res[i] = pq.poll();
return res;
}
}
22、1502_判断能否形成等差数组
1、排序，首元素和尾元素是否相同 2、判断公差是否为整数，若是整数，求出公差 d 3、建立 has 数组用于标记已经出现过的等差数列元素。 4、从第二个元素开始遍历是否与第一个元素成倍数关系(an = a1 + (n-1)d)
class Solution {
public boolean canMakeArithmeticProgression(int[] arr) {
Arrays.sort(arr);
int len = arr.length;
int min = arr[0], max = arr[len - 1];
if(max == min)
return true;
if((max - min) % (len - 1) != 0)
return false;
int d = (max - min) / (len - 1);
boolean[] has = new boolean[len];
for(int i = 1; i < len; i ++) {
if((arr[i] - min) % d != 0)
return false;
int index = (arr[i] - min) / d;
if(has[index])
return false;
has[index] = true;
}
return true;
}
}
23、3056_分割数组
给你一个长度为 偶数 的整数数组 nums 。你需要将这个数组分割成 nums1 和 nums2 两部分，要求：
nums1 应包含 互不相同 的元素。
nums2也应包含 互不相同 的元素。
如果能够分割数组就返回 true ，否则返回 false 。
方法一
class Solution {
public boolean isPossibleToSplit(int[] nums) {
Map
for(int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
if(map.get(num) >= 3)
return false;
}
return true;
}
}
方法二
class Solution {
public boolean isPossibleToSplit(int[] nums) {
int[] cnt = new int[110];
for(int i = 0; i < nums.length; i ++) {
cnt[nums[i]] ++;
if(cnt[nums[i]] >= 3)
return false;
}
return true;
}
}
24、3069_将元素分配到两个数组中 I
给你一个下标从 1 开始、包含 不同 整数的数组 nums ，数组长度为 n 。
你需要通过 n 次操作，将 nums 中的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中，将 nums[1] 追加到 arr1 。在第二次操作中，将 nums[2] 追加到 arr2 。之后，在第 i 次操作中：
如果 arr1 的最后一个元素 大于 arr2 的最后一个元素，就将 nums[i] 追加到 arr1 。否则，将 nums[i] 追加到 arr2 。
通过连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。
返回数组 result 。
class Solution {
public int[] resultArray(int[] nums) {
List
List
a.add(nums[0]);
b.add(nums[1]);
for(int i = 2; i < nums.length; i ++) {
if(a.get(a.size() - 1) > b.get(b.size() - 1))
a.add(nums[i]);
else
b.add(nums[i]);
}
a.addAll(b);
int k = 0;
for(int num : a)
nums[k ++] = num;
return nums;
}
}
25、459_重复的子字符串
class Solution {
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
for (int i = 1; i <= n / 2; i++) {
if (n % i == 0) {
boolean t = true;
for (int j = i; j < n; j++) {
if(s.charAt(j) != s.charAt(j - i)) {
t = false;
break;
}
}
if(t == true)
return true;
}
}
return false;
}
}
26、27_移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
class Solution {
public int removeElement(int[] nums, int val) {
int l = 0, r = nums.length - 1;
while(l <= r) {
if(nums[l] == val) {
nums[l] = nums[r];
r --;
}
else
l ++;
}
return l;
}
}
27、242_有效的字母异位词
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
Map
for(int i : s.toCharArray())
map1.put(i, map1.getOrDefault(i, 0) + 1);
for(int i : t.toCharArray()) {
map1.put(i, map1.getOrDefault(i, 0) - 1);
if(map1.get(i) < 0)
return false;
}
return true;
}
}
28、349_两个数组的交集
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set
Set
for(int i : nums1)
t1.add(i);
for(int i : nums2) {
if(t1.contains(i))
t2.add(i);
}
int[] result = new int[t2.size()];
int index = 0;
for(int i : t2)
result[index ++] = i;
return result;
}
}
29、14_最长公共前缀
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs == null)
return "";
String ans = strs[0];
for(int i = 1; i < strs.length; i ++) {
int j = 0;
for(; j < ans.length() && j < strs[i].length(); j ++) {
if(ans.charAt(j) != strs[i].charAt(j))
break;
}
ans = ans.substring(0, j);
}
return ans;
}
}
30、283_移动零
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length, l = 0, r = 0;
while(r < n) {
if(nums[r] != 0) {
int t = nums[r];
nums[r] = nums[l];
nums[l ++] = t;
}
r ++;
}
}
}
31、1_两数之和
class Solution {
public int[] twoSum(int[] nums, int target) {
Map
for(int i = 0; i < nums.length; i ++) {
if(map.containsKey(target - nums[i]))
return new int[] {map.get(target - nums[i]), i};
map.put(nums[i], i);
}
return new int[0];
}
}
32、15_三数之和
class Solution {
public List
List
int n = nums.length;
if(n < 3)
return ans;
Arrays.sort(nums);
for(int i = 0; i < n; i ++) {
if(nums[i] > 0)
break;
if(i > 0 && nums[i] == nums[i - 1])
continue;
int l = i + 1;
int r = n - 1;
while(l < r) {
int sum = nums[i] + nums[l] + nums[r];
if(sum > 0)
r --;
else if(sum < 0)
l ++;
else {
ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
while(l < r && nums[l] == nums[l + 1])
l ++;
while(l < r && nums[r] == nums[r - 1])
r --;
l ++;
r --;
}
}
}
return ans;
}
}
33、18_四数之和
class Solution {
public List
List
if(nums.length < 4)
return result;
Arrays.sort(nums);
for(int i = 0; i <= nums.length - 4; i ++) {
if(nums[i] > 0 && nums[i] > target)
return result;
if(i > 0 && nums[i] == nums[i - 1])
continue;
for(int j = i + 1; j <= nums.length - 3; j ++) {
if(j > i + 1 && nums[j] == nums[j - 1])
continue;
int l = j + 1;
int r = nums.length - 1;
while(l < r) {
long sum = (long) nums[i] + nums[j] + nums[l] + nums[r];
if(sum < target)
l ++;
else if(sum > target)
r --;
else {
result.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
while(l < r && nums[l] == nums[l + 1])
l ++;
while(l < r && nums[r] == nums[r - 1])
r --;
l ++;
r --;
}
}
}
}
return result;
}
}
34、2235_两整数之和
class Solution {
public int sum(int num1, int num2) {
while(num2 != 0) {
int carry = (num1 & num2) << 1;
num1 = num1 ^ num2;
num2 = carry;
}
return num1;
}
}
35、454_四数相加 II
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
HashMap
int i, j, sum = 0;
for(i = 0; i < nums1.length; i ++)
for(j = 0; j < nums2.length; j ++)
map1.put(nums1[i] + nums2[j], map1.getOrDefault((nums1[i] + nums2[j]), 0) + 1);
for(i = 0; i < nums3.length; i ++)
for(j = 0; j < nums4.length; j ++) {
int res = - (nums3[i] + nums4[j]);
if(map1.get(res) != null)
sum += map1.get(res);
}
return sum;
}
}
36、268_丢失的数字
class Solution {
public int missingNumber(int[] nums) {
HashSet
int[] a = new int[nums.length];
Arrays.sort(nums);
for(int i = 0; i < nums.length; i ++) {
has.add(nums[i]);
if(has.contains(i) == false)
return i;
}
return nums.length;
}
}
37、1882_数组元素积的符号
class Solution {
public int arraySign(int[] nums) {
int f = 1;
for(int x : nums) {
if(x == 0)
return 0;
else if(x < 0)
f = -f;
}
return f;
}
}
38、3074_重新分装苹果
class Solution {
public int minimumBoxes(int[] apple, int[] capacity) {
Arrays.sort(capacity);
int cnt = 0;
int sum = 0;
for(int i = 0; i < apple.length; i ++)
sum += apple[i];
for(int i = capacity.length - 1; i >= 0; i --) {
sum -= capacity[i];
cnt ++;
if(sum <= 0)
break;
}
return cnt;
}
}
38、231_2的幂
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}
39、326_3的幂
class Solution {
public boolean isPowerOfThree(int n) {
while(n != 0 && n % 3 == 0)
n /= 3;
return n == 1;
}
}
40、342_4的幂
class Solution {
public boolean isPowerOfFour(int n) {
if(n <= 0)
return false;
int x = (int)Math.sqrt(n);
return (x * x == n) && (x & -x) == x;
}
}
二叉树
1、144_二叉树的前序遍历
//递归遍历
class Solution {
public List
List
preorder(root, res);
return res;
}
static void preorder(TreeNode root, List
if(root == null)
return;
res.add(root.val);
preorder(root.left, res);
preorder(root.right, res);
}
}
//非递归遍历
class Solution {
public List
List
Deque
if(root == null)
return res;
stack.push(root);
while(!stack.isEmpty()) {
TreeNode node = stack.poll();
if(node != null)
res.add(node.val);
else
continue;
if(node.right != null)
stack.push(node.right);
if(node.left != null)
stack.push(node.left);
}
return res;
}
}
2、145_二叉树的后序遍历
//递归遍历
class Solution {
public List
List
preorder(root, res);
return res;
}
static void preorder(TreeNode root, List
if(root == null)
return;
preorder(root.left, res);
preorder(root.right, res);
res.add(root.val);
}
}
//非递归遍历
class Solution {
public List
//先序是：中左右 如果将先序代码中 左右子节点访问顺序互换，得到的结果其实是 中右左
//然后将结果做一个reverse（），即得：左右中 也就是后序遍历的结果
List
Deque
Deque
if(root == null)
return ress;
stack.push(root);
while(!stack.isEmpty()) {
TreeNode node = stack.poll();
if(node != null)
res.push(node.val);
else
continue;
if(node.left != null)
stack.push(node.left);
if(node.right != null)
stack.push(node.right);
}
while(!res.isEmpty())
ress.add(res.pop());
return ress;
}
}
3、94_二叉树的中序遍历
//递归遍历
class Solution {
public List
List
preorder(root, res);
return res;
}
static void preorder(TreeNode root, List
if(root == null)
return;
preorder(root.left, res);
res.add(root.val);
preorder(root.right, res);
}
}
//非递归遍历
class Solution {
public List
List
Deque
while (root != null || !stk.isEmpty()) {
while (root != null) {
stk.push(root);
root = root.left;
}
root = stk.pop();
res.add(root.val);
root = root.right;
}
return res;
}
}
4、102_二叉树的层序遍历
//迭代遍历
class Solution {
public List
List
Deque
if(root == null)
return ans;
node.add(root);
while(!node.isEmpty()) {
List
int n = node.size();
while(n -- != 0) {
TreeNode t = node.poll();
list.add(t.val);
if(t.left != null)
node.add(t.left);
if(t.right != null)
node.add(t.right);
}
ans.add(list);
}
return ans;
}
}
回溯
1、77_组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
class Solution {
public List
List
Deque
dfs(n, k, 1, path, res);
return res;
}
public void dfs(int n, int k, int begin, Deque
if(path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
//剪枝 k个元素，已经选了path.size()个
for(int i = begin; i <= n - (k - path.size()) + 1; i ++) {
path.push(i);
dfs(n, k, i + 1, path, res);
path.pop();
}
}
}
2、216_组合总和 III
class Solution {
List
Deque
public List
dfs(n, k, 1, 0);
return res;
}
public void dfs(int target, int k, int begin, int sum) {
//剪枝
if(sum > target)
return;
if(path.size() == k && sum == target) {
res.add(new ArrayList<>(path));
return;
}
//剪枝
for(int i = begin; i <= 9 - (k - path.size()) + 1; i ++) {
path.push(i);
sum += i;
dfs(target, k, i + 1, sum);
path.pop();
sum -= i;
}
}
}
3、17_电话号码的字母组合
dfs(digits, num, pos + 1); 每次都是 pos + 1找下一个串
class Solution {
List
StringBuffer s = new StringBuffer();
public List
if (digits == null || digits.length() == 0) {
return list;
}
String[] num = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
dfs(digits, num, 0);
return list;
}
public void dfs(String digits, String[] num, int pos) {
if(pos == digits.length()) {
list.add(s.toString());
return;
}
int d = digits.charAt(pos) - '0';
String str = num[d];
for(int i = 0; i < str.length(); i ++) {
s.append(str.charAt(i));
dfs(digits, num, pos + 1);
s.deleteCharAt(s.length() - 1);
}
}
}
4、39_组合总和
class Solution {
List
public List
//排序
Arrays.sort(candidates);
dfs(candidates, target, 0, 0, new ArrayList<>());
return res;
}
public void dfs(int[] candidates, int target, int pos, int sum, List
if(sum == target) {
res.add(new ArrayList<>(list));
return;
}
for(int i = pos; i < candidates.length; i ++) {
//剪枝
if(sum + candidates[i] > target)
break;
sum += candidates[i];
list.add(candidates[i]);
dfs(candidates, target, i, sum, list);
sum -= candidates[i];
list.remove(list.size() - 1);
}
}
}
5、40_组合总和 II
class Solution {
List
public List
Arrays.sort(candidates);
boolean[] f = new boolean[candidates.length];
dfs(candidates, new ArrayList<>(), target, 0, 0, f);
return res;
}
public void dfs(int[] candidates, List
if(sum == target) {
res.add(new ArrayList<>(list));
return;
}
for(int i = pos; i < candidates.length; i ++) {
if (sum + candidates[i] > target)
break;
//前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]
//例如1 1 2 第一个1的情况包含了第二个1的所有情况，所以在第二个树层即第二个1时，判断第一个树层即第一个1是否被使用过
//若f[i - 1] == false 说明第一个1已经遍历过，第二个1再次遍历出现重复组合，应该continue
if(i > 0 && candidates[i] == candidates[i - 1] && f[i - 1] == false)
continue;
sum += candidates[i];
list.add(candidates[i]);
f[i] = true;
dfs(candidates, list, target, i + 1, sum, f);
sum -= candidates[i];
list.remove(list.size() - 1);
f[i] = false;
}
}
}
6、131_分割回文串
class Solution {
List
public List
dfs(s, res, new ArrayList<>(), 0);
return res;
}
public void dfs(String s, List
if(pos >= s.length()) {
res.add(new ArrayList<>(list));
return;
}
for(int i = pos; i < s.length(); i ++) {
String str = s.substring(pos, i + 1);
String reverse = new StringBuffer(str).reverse().toString();
if(str.equals(reverse))
list.add(str);
else
continue;
dfs(s, res, list, i + 1);
list.remove(list.size() - 1);
}
}
}
7、93_复原IP地址
class Solution {
List
StringBuilder sb = new StringBuilder();
public List
if(s.length() > 12 || s.length() < 4) return res; // 提前剪枝
dfs(0, 0, s);
return res;
}
// start: 从哪里开始截取字符串
// cur: 当前是第几段 IP (第 0 段、第 1 段、第 2 段、第 3 段)
void dfs(int start, int cur, String s) {
if(cur == 4) {
// 进到这说明 cur = 0、1、2、3 的这前四层都处理完毕，形式为 XXX.XXX.XXX.XXX. (特别注意最后还有一个 .)
if(start == s.length()) { // 判断是否用完字符串 s
sb.deleteCharAt(sb.length()-1); // 去掉最后一个 "."
res.add(sb.toString());
sb.append("."); // 记得把最后一个 "." 补上，回溯到上一层会自动再去掉
}
return;
}
// 每一层递归截取 1 ~ 3 个字母
for(int i = 1; i <= 3; i++) {
if(start+i > s.length())
break; // 下标越界
if(s.charAt(start) == '0' && i != 1)
continue; // 含有前导 0；但允许只有一个 0
String IP = s.substring(start, start+i); // 截取 1 ~ 3 个字母作为 IP 段
if(Integer.parseInt(IP) > 255)
continue; // 数值不符合 IP 规则
sb.append(IP);
sb.append('.');
dfs(start + i, cur + 1, s);
sb.deleteCharAt(sb.length()-1);
sb.delete(sb.length()-i, sb.length());
}
}
}
8、78_子集
class Solution {
List
List
public List
dfs(nums, 0, new ArrayList<>());
return res;
}
public void dfs(int[] nums, int start, List
res.add(new ArrayList(list));
if(start >= nums.length)
return;
for(int i = start; i < nums.length; i ++) {
list.add(nums[i]);
dfs(nums, i + 1, list);
list.remove(list.size() - 1);
}
}
}
9、90_子集 II
class Solution {
List
public List
//排序
Arrays.sort(nums);
boolean[] f = new boolean[nums.length];
dfs(nums, f, 0, new ArrayList<>());
return res;
}
public void dfs(int[] nums, boolean[] f, int start, List
res.add(new ArrayList<>(list));
if(start >= nums.length) {
return;
}
for(int i = start; i < nums.length; i ++) {
//树层去重 每次f数组会回溯变成false 比如1 2 2 i = 1 执行完后，执行到 i = 2 那么f[2-1]变成false，把第二个2去重
if(i > 0 && nums[i] == nums[i - 1] && f[i - 1] == false)
continue;
list.add(nums[i]);
f[i] = true;
dfs(nums, f, i + 1, list);
list.remove(list.size() - 1);
f[i] = false;
}
}
}
10、491_非递减子序列
class Solution {
List
public List
dfs(nums, 0, new ArrayList<>());
return res;
}
public void dfs(int[] nums, int start, List
if(list.size() >= 2)
res.add(new ArrayList<>(list));
if(start >= nums.length)
return;
//set定义在外面
//每次递归调用 dfs 方法时都会创建一个新的 HashSet 对象
HashSet
for(int i = start; i < nums.length; i ++) {
if(!list.isEmpty() && list.get(list.size() - 1) > nums[i] || set.contains(nums[i]))
continue;
set.add(nums[i]);
list.add(nums[i]);
dfs(nums, i + 1, list);
list.remove(list.size() - 1);
}
}
}
11、46_全排列
class Solution {
List
public List
boolean[] f = new boolean[nums.length];
dfs(nums, f, new ArrayList<>());
return res;
}
public void dfs(int[] nums, boolean[] f, List
if(list.size() >= nums.length) {
res.add(new ArrayList<>(list));
return;
}
for(int i = 0; i < nums.length; i ++) {
//判断当前这个下标的元素是否被用过
if(f[i])
continue;
f[i] = true;
list.add(nums[i]);
dfs(nums, f, list);
f[i] = false;
list.remove(list.size() - 1);
}
}
}
12、47_全排列 II
class Solution {
List
public List
boolean[] f = new boolean[nums.length];
Arrays.sort(nums);
dfs(f, nums, new ArrayList<>());
return res;
}
public void dfs(boolean[] f, int[] nums, List
if(list.size() == nums.length) {
res.add(new ArrayList<>(list));
return;
}
for(int i = 0; i < nums.length; i ++) {
// used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
// used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
// 如果同⼀树层nums[i - 1]使⽤过则直接跳过
if(i > 0 && nums[i] == nums[i - 1] && f[i - 1] == false)
continue;
//同⼀树⽀nums[i]被使用过，跳过
if(f[i] == true)
continue;
f[i] = true;
list.add(nums[i]);
dfs(f, nums, list);
list.remove(list.size() - 1);
f[i] = false;
}
}
}
13、48_N皇后
class Solution {
List
public List
char[][] chessboard = new char[n][n];
for (char[] c : chessboard)
Arrays.fill(c, '.');
dfs(n, 0, chessboard);
return res;
}
public void dfs(int n, int row, char[][] chessboard) {
if (row == n) {
List
for(char[] c : chessboard)
list.add(String.valueOf(c));
res.add(list);
return;
}
for(int col = 0; col < n; col ++) {
if(is(row, col, n, chessboard)) {
chessboard[row][col] = 'Q';
dfs(n, row + 1, chessboard);
chessboard[row][col] = '.';
}
}
}
public boolean is(int row, int col, int n, char[][] chessboard) {
// 检查列
for (int i = 0; i < row; i ++)
if (chessboard[i][col] == 'Q')
return false;
// 检查45度对角线
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i --, j --)
if (chessboard[i][j] == 'Q')
return false;
// 检查135度对角线
for (int i = row - 1, j = col + 1; i >= 0 && j <= n-1; i --, j ++)
if (chessboard[i][j] == 'Q')
return false;
return true;
}
}
14、37_解数独
class Solution {
public void solveSudoku(char[][] board) {
dfs(board);
}
public boolean dfs(char[][] board) {
for(int i = 0; i < board.length; i ++) {
for(int j = 0; j < board[i].length; j ++) {
if(board[i][j] != '.')
continue;
for(char k = '1'; k <= '9'; k ++) {
if(is(i, j, k, board)) {
board[i][j] = k;
// 如果找到合适一组立刻返回
if(dfs(board))
return true;
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
public boolean is(int row, int col, char val, char[][] board) {
// 同行是否重复
for (int i = 0; i < 9; i++){
if (board[row][i] == val){
return false;
}
}
// 同列是否重复
for (int j = 0; j < 9; j++){
if (board[j][col] == val){
return false;
}
}
// 9宫格里是否重复
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++){
for (int j = startCol; j < startCol + 3; j++){
if (board[i][j] == val){
return false;
}
}
}
return true;
}
}
矩阵
1、59_螺旋矩阵 II
class Solution {
public int[][] generateMatrix(int n) {
int i, j;
int row = 0, col = 0, p = 1, m = n / 2, cnt = 1;
int res[][] = new int [n][n];
while(m -- != 0) {
for(j = col; j < n - p; j ++)
res[row][j] = cnt ++;
for(i = row; i < n - p; i ++)
res[i][j] = cnt ++;
for(; j > p - 1; j --)
res[i][j] = cnt ++;
for(; i > p - 1; i --)
res[i][j] = cnt ++;
row ++;
col ++;
p ++;
}
if(n % 2 == 1)
res[n / 2][n / 2] = n * n;
return res;
}
}
2、54_螺旋矩阵
class Solution {
public List
if (matrix.length == 0)
return new ArrayList
int l = 0, t = 0, k = 0, r = matrix[0].length - 1, b = matrix.length - 1;
Integer[] ans = new Integer[(r + 1) * (b + 1)];
while(true) {
for(int i = l; i <= r; i ++)
ans[k ++] = matrix[t][i];
if(++ t > b)
break;
for(int i = t; i <= b; i ++)
ans[k ++] = matrix[i][r];
if(--r < l)
break;
for(int i = r; i >= l; i --)
ans[k ++] = matrix[b][i];
if(-- b < t)
break;
for(int i = b; i >= t; i --)
ans[k ++] = matrix[i][l];
if(++ l > r)
break;
}
// return Arrays.asList(ans);
List
return result;
}
}
动态规划
1、70_爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
最后一步可能跨了一级台阶，也可能跨了两级台阶。dp[n]=dp[n−1]+dp[n−2] n = 2 跨一步，跨两步，有两种方法 根据 dp[n]=dp[n−1]+dp[n−2] 可知 n = 0 和 n = 1 可以设为 1
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2];
return dp[n];
}
}
或者不通过数组存放
class Solution {
public int climbStairs(int n) {
int l = 1, r = 1, p = 1;
for(int i = 2; i <= n; i ++) {
p = l + r;
l = r;
r = p;
}
return p;
}
}
2、509_斐波那契数
class Solution {
public int fib(int n) {
int a = 0, b = 1, c = 0;
if(n <= 1)
return n;
for(int i = 2; i <= n; i ++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
3、746_使用最小话费爬楼梯
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length + 1];
dp[0] = dp[1] = 0;
for(int i = 2; i < dp.length; i ++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[cost.length];
}
}
贪心
1、455_分发饼干
大饼干尽量给胃口大的小孩吃
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int cnt = 0;
int k = s.length - 1;
int t = g.length - 1;
while(k >= 0 && t >= 0)
if(s[k] >= g[t]) {
cnt ++;
t --;
k --;
}
else
t --;
return cnt;
}
}
2、376_摆动序列
class Solution {
public int wiggleMaxLength(int[] nums) {
int l = 0, cnt = 1;
if(nums.length <= 1)
return nums.length;
if(nums.length == 2) {
int n = nums[0] == nums[1] ? 1 : 2;
return n;
}
for(int i = 1; i < nums.length; i ++) {
int r = nums[i] - nums[i - 1];
if(l <= 0 && r > 0 || l >= 0 && r < 0) {
cnt ++;
l = r;
}
}
return cnt;
}
}
3、53_最大子数组和
class Solution {
public int maxSubArray(int[] nums) {
int result = Integer.MIN_VALUE, sum = 0;
for(int i = 0; i < nums.length; i ++) {
sum += nums[i];
if(sum > result)
result = sum;
if(sum < 0)
sum = 0;
}
return result;
}
}
4、122_买卖股票的最佳时机 II
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
for(int i = 1; i < prices.length; i ++)
if(prices[i] - prices[i - 1] > 0)
res += prices[i] - prices[i - 1];
return res;
}
}
5、55_跳跃游戏
class Solution {
public boolean canJump(int[] nums) {
int cover = 0;
if(nums.length == 1)
return true;
for(int i = 0; i <= cover; i ++) {
cover = Math.max(i + nums[i], cover);
if(cover >= nums.length - 1)
return true;
}
return false;
}
}
6、45_跳跃游戏 II
class Solution {
public int jump(int[] nums) {
if(nums.length == 1)
return 0;
int end = 0, step = 0, maxpos = 0;
for(int i = 0; i < nums.length - 1; i ++) {
maxpos = Math.max(i + nums[i], maxpos);
if(i == end) {
end = maxpos;
step ++;
}
}
return step;
}
}
好文推荐
发表评论