LC283. 移动零
import java.util.*;
public class Main283 {
public static void main(String[] args) {
int[] nums = {0, 1, 0, 3, 12}; // 1 3 12 0 0
// int[] nums = {0};
moveZeroes(nums);
for (int num : nums) {
System.out.print(num);
System.out.print (" ");
}
}
private static void moveZeroes(int[] nums) {
int k = 0;
for (int x : nums) {
if (x != 0) nums[k ++] = x;
}
while (k < nums.length) nums[k ++] = 0;
}
}
LC287. 寻找重复数
import java.util.*;
public class Main287 {
public static void main(String[] args) {
int[] nums = {1, 3, 4, 2, 2}; // 2
// int[] nums = {3, 1, 3, 4, 2}; // 3
int res = findDuplicate(nums);
System.out.println(res);
}
public static int findDuplicate(int[] nums) {
int a = 0, b = 0;
while (true) {
a = nums[a];
b = nums[nums[b]];
if (a == b) {
a = 0;
while (a != b) {
a = nums[a];
b = nums[b];
}
return a;
}
}
// return -1;
}
}
LC295. 数据流的中位数
// 代码结果有问题
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main295 {
Main() {}
public static void main(String[] args) {
addNum(1);
addNum(2);
double res1 = findMeidan();
System.out.println(res1);
addNum(3);
double res2 = findMeidan();
System.out.println(res2);
}
public static PriorityQueue<Integer> minheap = new PriorityQueue<>();
public static PriorityQueue<Integer> maxheap = new PriorityQueue<>(new maxComparator());
public static double findMeidan() {
if ((minheap.size() + maxheap.size() & 1) != 0) return maxheap.peek();
return (minheap.peek() + maxheap.peek()) / 2.0;
}
public static void addNum(int num) {
if (maxheap.isEmpty() || num <= maxheap.peek()) {
maxheap.add(num);
if (maxheap.size() - minheap.size() > 1) {
minheap.add(maxheap.peek());
maxheap.poll();
} else {
minheap.add(num);
if (minheap.size() > maxheap.size()) {
maxheap.add(minheap.peek());
minheap.poll();
}
}
}
}
private static class maxComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o1 >= o2 ? -1 : 1;
}
}
}
LC312. 戳气球
import java.util.*;
public class Main312 {
public static void main(String[] args) {
int[] nums = {3, 1, 5, 8}; // 167
// int[] nums = {1, 5}; // 10
int res = maxCoins(nums);
System.out.println(res);
}
public static int maxCoins(int[] nums) {
int n = nums.length;
int[] a = new int[n + 2];
for (int i = 0; i < n + 2; i ++) a[i] = 1;
for (int i = 1 ; i <= n; i ++) a[i] = nums[i - 1];
int[][] f = new int[n + 2][n + 2];
for (int len = 3; len <= n + 2; len ++)
for (int i = 0; i + len - 1 <= n + 1; i ++) {
int j = i + len - 1;
for (int k = i + 1; k < j; k ++)
f[i][j] = Math.max(f[i][j], f[i][k] + f[k][j] + a[i] * a[k] * a[j]);
}
return f[0][n + 1];
}
}
LC318. 最大单词长度乘积
import java.util.*;
public class Main318 {
public static void main(String[] args) {
String[] words = {"abcw", "baz", "foo", "bar", "xtfn", "abcdef"}; // 16
// String[] words = {"a","ab","abc","d","cd","bcd","abcd"}; // 4
// String[] words = {"a","aa","aaa","aaaa"}; // 0
int res = maxProduct(words);
System.out.println(res);
}
public static int maxProduct(String[] words) {
List<Integer> state = new ArrayList<>();
for (String word : words) {
int s = 0;
for (int i = 0; i < word.length(); i ++) {
s |= 1 << (word.charAt(i) - 'a');
}
state.add(s);
}
int res = 0;
for (int i = 0; i < words.length; i ++)
for (int j = i + 1; j < words.length; j ++) {
if ((state.get(i) & state.get(j)) == 0)
res = Math.max(res, (int)(words[i].length() * words[j].length()));
}
return res;
}
}
LC322. 零钱兑换
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main322 {
public static void main(String[] args) {
int[] coins = {1, 2, 5};
int amount = 11; // 3
/*int[] coins = {2};
int amount = 3;*/ // -1 // 这个样例 输出的是 -2147483648
/*
int[] coins = {1};
int amount = 0; // 0
*/
int res = coinChange(coins, amount);
System.out.println(res);
}
public static int coinChange(int[] coins, int amount) {
int[] f = new int[amount + 1];
for (int i = 0; i < amount + 1; i ++) f[i] = (int) Math.pow(10, 8);
f[0] = 0;
for (int v : coins)
for (int j = v; j <= amount; j ++) {
f[j] = Math.min(f[j], f[j - v] + 1);
}
if (f[amount] == Math.pow(10, 8)) return -1;
return f[amount];
}
}
LC326. 3的幂
import java.util.*;
public class Main326 {
public static void main(String[] args) {
// int n = 27; // true
// int n = 0; // false
int n = 9; // true
// int n = 45; // false
boolean res = isPowerOfThree(n);
System.out.println(res);
}
// 方式一:
public static boolean isPowerOfThree(int n) {
while (n != 0 && n % 3 == 0) n /= 3;
return n == 1;
}
/* // 方式二:
public static boolean isPowerOfThree(int n) {
return (n > 0 && 1162261467 % n == 0);
}*/
}
LC342. 4的幂
import java.util.*;
public class Main342 {
public static void main(String[] args) {
int n = 16; // true
// int n = 5; // false
// int n = 1; // true
boolean res = isPowerOfFour(n);
System.out.println(res);
}
public static boolean isPowerOfFour(int n) {
if (n <= 0) return false;
int r = (int) Math.sqrt(n);
if (r * r != n) return false;
// return (n & -n) == n;
return (1 << 30) % n == 0;
}
}
LC343. 整数拆分
import java.util.*;
public class Main343 {
public static void main(String[] args) {
int n = 2; // 1
// int n = 10; // 36
int res = integerBreak(n);
System.out.println(res);
}
// 写法一:
/* public static int integerBreak(int n) {
if (n <= 3) return 1 * (n - 1);
int res = 1;
while (n >= 5) {
n -= 3;
res *= 3;
}
return res * n;
}*/
// 写法二:
public static int integerBreak(int n) {
if (n <= 3) return 1 * (n - 1);
int res = 1;
if (n % 3 == 1) {
res = 4;
n -= 4;
} else if (n % 3 == 2) {
res = 2;
n -= 2;
}
while (n != 0) {
res *= 3;
n -= 3;
}
return res;
}
}
LC344. 反转字符串
import java.util.*;
public class Main344 {
public static void main(String[] args) {
// char[] s = {'h','e','l','l','o'};
char[] s = {'H','a','n','n','a','h'};
for (char c : s) {
System.out.print(c);
System.out.print(" ");
}
System.out.println();
reverseString(s);
for (char c : s) {
System.out.print(c);
System.out.print(" ");
}
}
public static void reverseString(char[] s) {
for (int i = 0, j = s.length - 1; i < j; i ++, j --)
swap(s, i, j);
}
private static void swap(char[] s, int i, int j) {
char temp;
temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
LC349. 两个数组的交集
import java.util.*;
public class Main349 {
public static void main(String[] args) {
int[] nums1 = {1, 2, 2, 1}, nums2 = {2, 2}; // 2
// int[] nums1 = {4, 9, 5}, nums2 = {9, 4, 9, 8, 4};
int[] res = intersection(nums1, nums2); // 9 4
for (int r : res) {
System.out.println(r);
}
}
public static int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> S = new HashSet<>();
for (int x : nums1) {
S.add(x);
}
List<Integer> res = new ArrayList<>();
for (int x : nums2) {
if (S.contains(x)) res.add(x);
S.remove(x);
}
int n = res.size();
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = res.get(i);
}
return ans;
}
}
LC371. 两整数之和
import java.util.*;
public class Main371 {
public static void main(String[] args) {
// int a = 1, b = 2; // 3
int a = 2, b = 3; // 5
int res = getSum(a, b);
System.out.println(res);
}
private static int getSum(int a, int b) {
while (b != 0) {
int sum = a ^ b;
int carry = (a & b) << 1;
a = sum;
b = carry;
}
return a;
}
}
LC374. 猜数字大小
import java.util.*;
public class Main374 {
public static int pick;
public static void main(String[] args) {
// int n = 10, _pick = 6; // 6
// int n = 1, _pick = 1; // 1
int n = 2, _pick = 1; // 1
pick = _pick;
int res = guessNumber(n);
System.out.println(res);
}
public static int guessNumber(int n) {
long l = 1, r = n;
while (l < r) {
int mid = (int) ((long) l + r + 1 >> 1);
if (guess(mid) >= 0) l = mid;
else r = mid - 1;
}
return (int) r;
}
private static int guess(int num) {
if (num > pick) return -1;
else if (num < pick) return 1;
return 0;
}
}
LC387. 字符串中的第一个唯一字符
import java.util.*;
public class Main387 {
public static void main(String[] args) {
String s = "leetcode"; // 0
// String s = "loveleetcode"; // 2
// String s = "aabb"; // -1
int res = firstUniqChar(s);
System.out.println(res);
}
// 方法1:使用哈希表
/*
private static int firstUniqChar(String s) {
HashMap<Character, Integer> hash = new HashMap<>();
for (int i = 0; i < s.length(); i ++) {
hash.put(s.charAt(i), hash.getOrDefault(s.charAt(i), 0) + 1);
}
for (int i = 0; i < s.length(); i++) {
if (hash.get(s.charAt(i)) == 1) return i;
}
return -1;
}
*/
// 方法2:使用数组
private static int firstUniqChar(String s) {
int[] nums = new int[26];
for (int i = 0; i < nums.length; i++) {
nums[i] = 0;
}
for (int i = 0; i < s.length(); i ++) {
nums[s.charAt(i) - 'a'] ++;
}
for (int i = 0; i < s.length(); i ++) {
if (nums[s.charAt(i) - 'a'] == 1) return i;
}
return -1;
}
}
LC389. 找不同
import java.util.*;
public class Main389 {
public static void main(String[] args) {
String s = "abcd", t = "abcde"; // e
// String s = "", t = "y"; // y
char res = findTheDifference(s, t);
System.out.println(res);
}
// 方法1:使用异或
private static char findTheDifference(String s, String t) {
int x = 0;
for (int i = 0; i < s.length(); i ++) {
x = x ^ s.charAt(i);
}
for (int i = 0; i < t.length(); i ++) {
x = x ^ t.charAt(i);
}
return (char)x;
}
// 方法2:使用哈希表
/* private static char findTheDifference(String s, String t) {
HashMap<Character, Integer> cnt = new HashMap<>();
for (int i = 0; i < t.length(); i ++) {
cnt.put(t.charAt(i), cnt.getOrDefault(t.charAt(i), 0) + 1);
}
for (int i = 0; i < s.length(); i ++) {
cnt.put(s.charAt(i), cnt.getOrDefault(s.charAt(i), 0) - 1);
}
*//*遍历哈希表*//*
*//*暂时没写*//*
return 0;
}*/
// 方法3:求和
/*private static char findTheDifference(String s, String t) {
int as = 0, at = 0;
for (int i = 0; i < s.length(); i ++) as += s.charAt(i);
for (int i = 0; i < t.length(); i ++) at += t.charAt(i);
return (char) (at - as);
}*/
// 方法4:使用排序
/*
private static char findTheDifference(String s, String t) {
char[] cs = s.toCharArray();
char[] ct = t.toCharArray();
Arrays.sort(cs);
Arrays.sort(ct);
int len = s.length();
for (int i = 0; i < len; i ++) {
if (cs[i] != ct[i]) return ct[i];
}
return ct[len];
}
*/
}
LC400. 第N位数字
import java.util.*;
public class Main400 {
public static void main(String[] args) {
int n = 3; // 3
// int n = 11; // 0
int res = findNthDigit(n);
System.out.println(res);
}
private static int findNthDigit(int n) {
long digit = 1, start = 1, count = 9;
while (n > count) {
n -= count;
start *= 10;
digit += 1;
count = 9 * start * digit;
}
long num = start + (n + digit - 1) / digit - 1;
n = (int) ((n % digit != 0) ? n % digit : digit);
String res = num + "";
return res.charAt(n - 1) - '0';
}
}
LC405. 数字转换为十六进制数
import java.util.*;
public class Main405 {
public static void main(String[] args) {
int num = 26; // 1a
// int num = -1; // ffffffff
String res = toHex(num);
System.out.println(res);
}
/*
* >>= 右移赋值
>>>= 右移赋值,左边空出的位以0填充
“>>>”运算符所作的是无符号的位移处理,
它不会将所处理的值的最高位视为正负符号,
所以作位移处理时,会直接在空出的高位填入0
* */
private static String toHex(int num) {
if (num == 0) return "0";
String res = "", nums = "0123456789abcdef";
while (num != 0) {
res += nums.charAt(num & 0xf);
num >>>= 4;
}
StringBuffer ans = new StringBuffer(res);
return ans.reverse().toString();
}
}
LC412. Fizz Buzz
import java.util.*;
public class Main412 {
public static void main(String[] args) {
int n = 3; // 1 2 Fizz
// int n = 5; // 1 2 Fizz 4 Buzz
// int n = 15; // "1","2","Fizz","4","Buzz","Fizz","7","8",
// "Fizz","Buzz","11","Fizz","13","14","FizzBuzz"
List<String> res = fizzBuzz(n);
System.out.println(res);
}
private static List<String> fizzBuzz(int n) {
List<String> res = new ArrayList<>();
for (int i = 1; i <= n; i ++) {
if (i % 3 == 0 && i % 5 == 0) res.add("FizzBuzz");
else if (i % 3 == 0) res.add("Fizz");
else if (i % 5 == 0) res.add("Buzz");
else res.add(i + "");
}
return res;
}
}
LC414. 第三大的数
import java.util.*;
public class Main414 {
public static void main(String[] args) {
int[] nums = {3, 2, 1}; // 1
// int[] nums = {1, 2}; // 2
// int[] nums = {2, 2, 3, 1}; // 1
int res = thirdMax(nums);
System.out.println(res);
}
private static int thirdMax(int[] nums) {
long INF = (long) Math.pow(10, 10);
long a = -INF, b = -INF, c = -INF, s = 0;
for (int x : nums) {
if (x > a) {
s ++;
c = b;
b = a;
a = x;
} else if (x < a && x > b) {
s ++;
c = b;
b = x;
} else if (x < b && x > c) {
s ++;
c = x;
}
}
if(s < 3) return (int) a;
return (int) c;
}
}
LC415. 字符串相加
import java.util.*;
public class Main415 {
public static void main(String[] args) {
String num1 = "11", num2 = "123"; // 134
// String num1 = "456", num2 = "77"; // 533
// String num1 = "0", num2 = "0"; // 0
String res = addStrings(num1, num2);
System.out.println(res);
}
private static String addStrings(String a, String b) {
List<Integer> A = new ArrayList<>(), B = new ArrayList<>();
for (int i = a.length() - 1; i >= 0; i --) A.add(a.charAt(i) - '0');
for (int i = b.length() - 1; i >= 0; i --) B.add(b.charAt(i) - '0');
List C = add(A, B);
String c = "";
for (int i = C.size() - 1; i >= 0; i --) c += (C.get(i) + "");
return c;
}
private static List<Integer> add(List<Integer> A, List<Integer> B) {
List<Integer> C = new ArrayList<>();
for (int i = 0, t = 0; i < A.size() || i < B.size() || t != 0; i ++) {
if (i < A.size()) t += A.get(i);
if (i < B.size()) t += B.get(i);
C.add(t % 10);
t /= 10;
}
return C;
}
}
LC419. 甲板上的战舰
import java.util.*;
public class Main419 {
public static void main(String[] args) {
char[][] board = {
{'X', '.', '.', 'X'},
{'.', '.', '.', 'X'},
{'.', '.', '.', 'X'}
}; // 2
// char[][] board = {{'.'}};
int res = countBattleships(board);
System.out.println(res);
}
private static int countBattleships(char[][] board) {
int res = 0;
for (int i = 0; i < board.length; i ++) {
for (int j = 0; j < board[i].length; j ++) {
if (i > 0 && board[i - 1][j] == 'X') continue;
if (j > 0 && board[i][j - 1] == 'X') continue;
if (board[i][j] == 'X') res ++;
}
}
return res;
}
}
LC434. 字符串中的单词数
import java.util.*;
public class Main434 {
public static void main(String[] args) {
String s = "Hello, my name is John";
int res = countSegments(s);
System.out.println(res);
}
private static int countSegments(String s) {
int res = 0;
for (int i = 0; i < s.length(); i ++) {
if (s.charAt(i) == ' ') continue;
int j = i + 1;
while (j < s.length() && s.charAt(j) != ' ') j ++;
res ++;
i = j; // 或者 i = j - 1; 都行
}
return res;
}
}
LC453. 最小操作次数使数组元素相等
import java.util.*;
public class Main453 {
public static void main(String[] args) {
int[] nums = {1, 2, 3}; // 3
// int[] nums = {1, 1, 1}; // 0
int res = minMoves(nums);
System.out.println(res);
}
private static int minMoves(int[] nums) {
int minv = Integer.MAX_VALUE;
for (int x : nums) {
minv = Math.min(minv, x);
}
int res = 0;
for (int x : nums) {
res += (x - minv);
}
return res;
}
}
LC461. 汉明距离
import java.util.*;
public class Main461 {
public static void main(String[] args) {
// int x = 1, y = 4; // 2
int x = 3, y = 1; // 1
int res = hammingDistance(x, y);
System.out.println(res);
}
private static int hammingDistance(int x, int y) {
int res = 0;
while (x != 0 || y != 0) {
res += (x & 1) ^ (y & 1);
x >>= 1;
y >>= 1;
}
return res;
}
}
LC476. 数字的补数
import java.util.*;
public class Main476 {
public static void main(String[] args) {
// int num = 5; // 2
int num = 1; // 0
int res = findComplement(num);
System.out.println(res);
}
private static int findComplement(int num) {
if (num == 0) return 1;
int cnt = 0;
for (int x = num; x != 0; x >>= 1) cnt ++;
return (int) (~num & (long) (1 << cnt) - 1);
}
}
LC485. 最大连续1的个数
import java.util.*;
public class Main485 {
public static void main(String[] args) {
int[] nums = {1, 1, 0, 1, 1, 1}; // 3
// int[] nums = {1, 0, 1, 1, 0, 1}; // 2
int res = findMaxConsecutive(nums);
System.out.println(res);
}
private static int findMaxConsecutive(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) continue;
int j = i + 1;
while (j < nums.length && nums[j] == 1) j ++;
res = Math.max(res, j - i);
i = j;
}
return res;
}
}
LC404. 左叶子之和
import java.util.*;
public class Main404 {
public static void main(String[] args) {
TreeNode root = new TreeNode(3,
new TreeNode(9, null, null),
new TreeNode(20,
new TreeNode(15),
new TreeNode(7)));
int res = sumOfLeftLeaves(root);
System.out.println(res);
} // 24
public static int res = 0;
public static int sumOfLeftLeaves(TreeNode root) {
dfs(root);
return res;
}
private static void dfs(TreeNode root) {
if (root == null) return ;
if (root.left != null) {
if (root.left.left == null && root.left.right == null) res += root.left.val;
}
dfs(root.left);
dfs(root.right);
}
public static class TreeNode {
public int val;
TreeNode left, right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}
LC429. N叉树的层序遍历
// 有bug 只能输出根节点的children
import java.util.*;
public class Main429 {
/*
* 可以尝试另一种建树方式:全部放到List<TreeNode> 中再 逐个关联起来
* */
public static void main(String[] args) {
TreeNode b1 = new TreeNode(3);
TreeNode b2 = new TreeNode(2);
TreeNode b3 = new TreeNode(4);
List<TreeNode> child1 = new ArrayList<>();
child1.add(b1);
child1.add(b2);
child1.add(b3);
TreeNode A = new TreeNode(1, child1);
TreeNode c1 = new TreeNode(5);
TreeNode c2 = new TreeNode(6);
List<TreeNode> child2 = new ArrayList<>();
child2.add(c1);
child2.add(c2);
TreeNode B = new TreeNode(A.children.get(0).val, child2);
List<List<Integer>> res = levelOrder(A);
for (List<Integer> r : res) {
for (Integer i : r) {
System.out.print(i);
System.out.print(" ");
}
System.out.println();
}
}
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (q.size() != 0) {
int len = q.size();
List<Integer> line = new ArrayList<>();
while (len -- != 0) {
TreeNode t = q.poll();
line.add(t.val);
if (t.children != null) {
for (TreeNode c : t.children) {
q.add(c);
}
}
}
res.add(line);
}
return res;
}
public static class TreeNode {
public int val;
public List<TreeNode> children;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, List<TreeNode> children) {
this.val = val;
this.children = children;
}
}
}
LC328. 奇偶链表
import java.util.*;
public class Main328 {
public static void main(String[] args) {
ListNode head = new ListNode(1, new ListNode(2,
new ListNode(3, new ListNode(4, new ListNode(5)))));
print(head); // 1 2 3 4 5
ListNode res = oddEventList(head);
System.out.println();
print(res); // 1 3 5 2 4
}
private static ListNode oddEventList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode oh = head, ot = oh;
ListNode eh = head.next, et = eh;
for (ListNode p = head.next.next; p != null; ) {
ot = ot.next = p;
p = p.next;
if (p != null) {
et = et.next = p;
p = p.next;
}
}
ot.next = eh;
et.next = null;
return oh;
}
public static void print(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
System.out.print(p.val);
System.out.print(" ");
}
}
public static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
}
LC300. 最长递增子序列
import java.util.*;
public class Main300 {
public static void main(String[] args) {
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18}; // 4
// int[] nums = {0, 1, 0, 3, 2, 3}; // 4
// int[] nums = {7, 7, 7, 7, 7, 7, 7}; // 1
int res = lengthOfLTS(nums);
System.out.println(res);
}
// 方法1:DP
/*
private static int lengthOfLTS(int[] nums) {
int n = nums.length;
int[] f = new int[n];
for (int i = 0; i < n; i++) {
f[i] = 1;
for (int j = 0; j < i; j ++)
if (nums[j] < nums[i])
f[i] = Math.max(f[i], f[j] + 1);
}
int res = 0;
for (int i = 0; i < n; i++) {
res = Math.max(res, f[i]);
}
return res;
}
*/
// 方法2:二分
private static int lengthOfLTS(int[] nums) {
int n = nums.length;
List<Integer> q = new ArrayList<>();
for (int x : nums) {
if (q.isEmpty() || x > q.get(q.size() - 1)) q.add(x);
else {
if (x <= q.get(0)) q.set(0, x);
else {
int l = 0, r = q.size() - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (q.get(mid) < x) l = mid;
else r = mid - 1;
}
q.set(r + 1, x);
}
}
}
return q.size();
}
}
LC303. 区域和检索-数组不可变
import java.util.*;
public class Main303 {
int[] nums = {-2, 0, 3, -5, 2, -1}; // 4
public static List<Integer> S = new ArrayList<>();
Main303(int[] nums) {
for (int i = 1; i <= nums.length; i++) {
S.set(i, S.get(i - 1) + nums[i - 1]);
}
}
public static int SumRange(int i, int j) {
++ i; ++ j;
return S.get(j) - S.get(i - 1);
}
public static void main(String[] args) {
System.out.println(SumRange(0, 2));
System.out.println(SumRange(2, 5));
System.out.println(SumRange(0, 5));
}
}
LC329. 矩阵中的最长递增路径
// 有bug 空指针异常
import java.util.*;
public class Main329 {
public static int n, m;
public static int[][] f = new int[n][m];
public static int[][] w = new int[n][m];
public static int[] dx = {-1, 0, 1, 0};
public static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) {
int[][] matrix = {
{9, 9, 4},
{6, 6, 8},
{2, 1, 1},
}; // 4
int res = longestIncreasingPath(matrix);
System.out.println(res);
}
public static int dp(int x, int y) {
int v = f[x][y];
if (v != -1) return v;
v = 1;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && w[x][y] < w[a][b])
v = Math.max(v, dp(a, b) + 1);
}
return v;
}
private static int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return 0;
w = matrix;
n = w.length;
m = w[0].length;
for (int i = 0; i < f.length; i++) {
for (int j = 0; j < f[i].length; j++) {
f[i][j] = -1;
}
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
res = Math.max(res, dp(i, j));
}
}
return res;
}
}
LC331. 验证二叉树的前序序列化
import java.util.*;
public class Main331 {
public static int k;
public static String s = "9,3,4,#,#,1,#,#,2,#,6,#,#"; // true
// public static String s = "1,#"; // false
// public static String s = "9,#,#,1"; // false
public static void main(String[] args) {
boolean res = isValidSerialization(s);
System.out.println(res);
}
private static boolean isValidSerialization(String _s) {
k = 0;
s = _s + ',';
if (!dfs()) return false;
return k == s.length();
}
public static boolean dfs() {
if (k == s.length()) return false;
if (s.charAt(k) == '#') {
k += 2;
return true;
}
while (s.charAt(k) != ',') k ++;
k ++;
return dfs() && dfs();
}
}
LC334. 递增的三元子序列
import java.util.*;
public class Main334 {
public static void main(String[] args) {
// int[] nums = {1, 2, 3, 4, 5}; // true
// int[] nums = {5, 4, 3, 2, 1}; // false
int[] nums = {2, 1, 5, 0, 4, 6}; // true
boolean res = increasingTriplet(nums);
System.out.println(res);
}
private static boolean increasingTriplet(int[] nums) {
int[] q = new int[2];
q[0] = Integer.MAX_VALUE;
q[1] = Integer.MAX_VALUE;
for (int a : nums) {
int k = 2;
while (k > 0 && q[k - 1] >= a) k --;
if (k == 2) return true;
q[k] = a;
}
return false;
}
}
LC337. 打家劫舍III
import java.util.*;
public class Main337 {
public static void main(String[] args) {
TreeNode root = new TreeNode(3, new TreeNode(2,
null, new TreeNode(3)), new TreeNode(3,
null, new TreeNode(1))); // 7
int res = rob(root);
System.out.println(res);
}
private static int rob(TreeNode root) {
int[] f = dfs(root);
return Math.max(f[0], f[1]);
}
private static int[] dfs(TreeNode u) {
if (u == null) return new int[]{0, 0};
int[] x = dfs(u.left);
int[] y = dfs(u.right);
return new int[]{Math.max(x[0], x[1]) + Math.max(y[0], y[1]), x[0] + y[0] + u.val};
}
static class TreeNode {
int val;
TreeNode left, right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}
LC345. 反转字符串中的元音字母
// 笔记中的代码有问题,for(i ++, j --)应该去掉
import java.util.*;
public class Main345 {
public static void main(String[] args) {
String s = "hello"; // holle
// String s = "leetcode"; // leotcede
String res = reverseVowels(s);
System.out.println(res);
}
private static String reverseVowels(String s) {
int n = s.length();
char[] arr = s.toCharArray();
for (int i = 0, j = n - 1; i < j; ) {
while (i < j && !check(arr[i])) i ++;
while (i < j && !check(arr[j])) j --;
if (i < j) {
swap(arr, i, j);
i ++;
j --;
}
}
/* for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}*/
return new String(arr);
}
public static boolean check(char c) {
return "aeiouAEIOU".indexOf(c) >= 0;
}
public static void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
LC347. 前K个高频元素
// 有bug,不能输出内容,代码写的太复杂了 ,必须重新写
import java.util.*;
public class Main347 {
public static void main(String[] args) {
int[] nums = {1, 1, 1, 2, 2, 3};
int k = 2;
int[] res = topKFrequent(nums, k);
for (int r : res) {
System.out.print(r);
System.out.print(" ");
}
}
public static int[] topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> cnt = new HashMap<>();
/* 遍历 Map<Integer, Integer>
先把Map集合转换成Set集合,Set集合中每个元素都是键值对实体类型了。
遍历Set集合,然后提取键以及提取值。
*/
Set<Map.Entry<Integer, Integer>> hash = cnt.entrySet(); //
for (int x : nums) {
cnt.put(x, cnt.getOrDefault(x, 0) + 1);
}
int m = 0;
int n = nums.length;
int[] s = new int[n + 1];
for (Map.Entry<Integer, Integer> c : hash) {
int key = c.getKey();
int val = c.getValue();
s[val] ++;
if (val > n) m ++;
}
int i = n, t = 0;
while (t < k) t += s[i --];
int[] res = new int[m];
for (int j = 0; j < m; j ++) {
for (Map.Entry<Integer, Integer> c : hash) {
int key = c.getKey();
int val = c.getValue();
if (val > i) res[j] = key;
}
}
return res;
}
}
LC350. 两个数组的交集II
import java.util.*;
public class Main350 {
public static void main(String[] args) {
int[] nums1 = {1, 2, 2, 1}, nums2 = {2, 2};
// int[] nums1 = {4, 9, 5}, nums2 = {9, 4, 9, 8, 4};
int[] res = intersect(nums1, nums2);
for (int r : res) {
System.out.print(r);
System.out.print(" ");
}
}
/*
这里也给出用unordered_map的写法,notability上使用unordered_multiset<int>
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> map;
vector<int> res;
for (auto c : nums1) map[c] ++;
for (auto c : nums2) {
if (map[c]) {
res.push_back(c);
map[c] --;
}
}
return res;
}
*/
// java的代码
public static int[] intersect(int[] nums1, int[] nums2) {
// 使用元素较少的数组建查找表
if (nums1.length > nums2.length) return intersect(nums2, nums1);
// 使用 hashmap 注册 nums1 中所有数字
HashMap<Integer, Integer> freq = new HashMap<>(); // <num, times>
for (int num : nums1) freq.put(num, freq.getOrDefault(num, 0) + 1);
// 遍历 nums2 中数字,找到交集存入 list
List<Integer> ans = new ArrayList<>();
for (int num : nums2) {
if (freq.containsKey(num) && freq.get(num) != 0) {
ans.add(num);
freq.put(num, freq.get(num) - 1);
}
}
int[] ret = new int[ans.size()];
int idx = 0;
for (int num : ans) ret[idx++] = num;
return ret;
}
}
LC357. 统计各位数字都不同的数字个数
import java.util.*;
public class Main357 {
public static void main(String[] args) {
int n = 2; // 91
int res = countNumbersWithUniqueDigits(n);
System.out.println(res);
}
private static int countNumbersWithUniqueDigits(int n) {
if (n == 0) return 1;
int[] f = new int[n + 1];
f[0] = 1;
f[1] = 9;
for (int i = 2; i <= n; i ++) {
f[i] = f[i - 1] * (11 - i);
}
int res = 0;
for (int x : f) {
res += x;
}
return res;
}
}
LC367. 有效的完全平方数
import java.util.*;
public class Main367 {
public static void main(String[] args) {
int num = 16; // true
// int num = 14; // false
boolean res = isPerfectSquare(num);
System.out.println(res);
}
private static boolean isPerfectSquare(int num) {
int l = 1, r = num;
while (l < r) {
int mid = (int) ((long) (l + 1 + r) >> 1);
if (mid <= num / mid) l = mid;
else r = mid - 1;
}
return r * r == num;
}
}
LC383. 赎金信
import java.util.*;
public class Main383 {
public static void main(String[] args) {
// String a = "a", b = "b"; // false
// String a = "aa", b = "ab"; // false
String a = "aa", b = "aab"; // true
boolean res = canConstruct(a, b);
System.out.println(res);
}
private static boolean canConstruct(String a, String b) {
HashMap<Character, Integer> hash = new HashMap<>();
char[] cb = b.toCharArray();
char[] ca = a.toCharArray();
for (char c : cb) {
hash.put(c, hash.getOrDefault(c, 0) + 1);
}
for (char c : ca) {
if (hash.getOrDefault(c, 0) == 0) return false;
else hash.put(c, hash.get(c) - 1);
}
return true;
}
}
LC386. 字典序排数
// 可以简化一下,return int[]的时候,需要把ArrayList转成int[],这样能不能简化下
import java.util.*;
public class Main386 {
public static List<Integer> res = new ArrayList<>();
public static void main(String[] args) {
// int n = 13; // 1 10 11 12 13 2 3 4 5 6 7 8 9
int n = 2; // 1 2
int[] ans = lexiCalOrder(n);
for (int a : ans) {
System.out.print(a);
System.out.print(" ");
}
}
private static int[] lexiCalOrder(int n) {
for (int i = 1; i <= 9; i ++) dfs(i, n);
int[] ans = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
ans[i] = res.get(i);
}
return ans;
}
private static void dfs(int cur, int n) {
if (cur <= n) res.add(cur);
else return ;
for (int i = 0; i <= 9; i ++) dfs(cur * 10 + i, n);
}
}
LC390. 消除游戏
import java.util.*;
public class Main390 {
public static void main(String[] args) {
int n = 9; // 6
int res = lastRemaining(n);
System.out.println(res);
}
private static int lastRemaining(int n) {
if (n == 1) return 1;
return 2 * (n / 2 + 1 - lastRemaining(n / 2));
}
}
LC392. 判断子序列
import java.util.*;
public class Main392 {
public static void main(String[] args) {
String s = "abc", t = "ahbgdc"; // true
// String s = "axc", t = "ahbgdc"; // false
boolean res = isSubSequence(s, t);
System.out.println(res);
}
private static boolean isSubSequence(String s, String t) {
int k = 0;
for (int i = 0; i < t.length(); i ++) {
if (k < s.length() && t.charAt(i) == s.charAt(k))
k ++;
}
return k == s.length();
}
}
LC394. 字符串解码
import java.util.*;
public class Main394 {
public static void main(String[] args) {
// String s = "3[a]2[bc]"; // aaabcbc
// String s = "3[a2[c]]"; // accaccacc
String s = "2[abc]3[cd]ef"; // abcabccdcdcdef
String res = decodeString(s);
System.out.println(res);
}
private static int u = 0;
private static String decodeString(String s) {
// int u = 0;
return dfs(s);
}
private static String dfs(String s) {
String res = "";
while (u < s.length() && s.charAt(u) != ']') {
if (s.charAt(u) >= 'a' && s.charAt(u) <= 'z'
|| s.charAt(u) >= 'A' && s.charAt(u) <= 'Z') res += s.charAt(u ++);
else if (s.charAt(u) >= '0' && s.charAt(u) <= '9') {
int k = u;
while (s.charAt(k) >= '0' && s.charAt(k) <= '9') k ++;
int x = Integer.parseInt(s.substring(u, k));
u = k + 1;
String y = dfs(s);
u ++;
while (x -- != 0) res += y;
}
}
return res;
}
}
LC396. 旋转函数
import java.util.*;
public class Main396 {
public static void main(String[] args) {
int[] nums = {4, 3, 2, 6}; // 26
int res = maxRotateFunction(nums);
System.out.println(res);
}
private static int maxRotateFunction(int[] A) {
long sum = 0, cur = 0;
for (int c : A) {
sum += c;
}
int n = A.length;
for (int i = 0; i < n; i++) {
cur += i * A[i];
}
long res = cur;
for (int i = n - 1; i >= 0; i --) {
cur += sum - (long) (n * A[i]);
res = Math.max(res, cur);
}
return (int) res;
}
}
LC397. 整数替换
// 只转换了一种代码方式
import java.util.*;
public class Main397 {
public static void main(String[] args) {
// int n = 8; //3
int n = 7; // 4
int res = integerReplacement(n);
System.out.println(res);
}
private static int integerReplacement(int n) {
return f(n);
}
private static int f(int n) {
if (n == 1) return 0;
if (n % 2 == 0) return f(n / 2) + 1;
return Math.min(f(n + 1), f(n - 1)) + 1;
}
}
LC409. 最长回文串
import java.util.*;
public class Main409 {
public static void main(String[] args) {
String s = "abccccdd"; // 7
// String s = "a"; // 1
// String s = "bb"; // 2
int res = longestPalindrome(s);
System.out.println(res);
}
private static int longestPalindrome(String s) {
HashMap<Character, Integer> hash = new HashMap<>();
for (int i = 0; i < s.length(); i ++) {
hash.put(s.charAt(i), hash.getOrDefault(s.charAt(i), 0) + 1);
}
int res = 0;
for (int val : hash.values()) {
res += val / 2 * 2;
}
if (res < s.length()) res ++;
return res;
}
}
LC413. 等差数列划分
import java.util.*;
public class Main413 {
public static void main(String[] args) {
// int[] nums = {1, 2, 3, 4}; // 3
int[] nums = {1}; // 0
int res = numberOfArithmeticSlices(nums);
System.out.println(res);
}
private static int numberOfArithmeticSlices(int[] A) {
for (int i = A.length - 1; i > 0; i --) A[i] -= A[i - 1];
int res = 0;
for (int i = 1; i < A.length; i ++) {
int j = i;
while (j < A.length && A[j] == A[i]) j ++;
int k = j - i;
res += k * (k - 1) / 2;
i = j - 1;
}
return res;
}
}
LC416. 分割等和子集
// 有问题,优化后的代码不知道怎么转?
import java.util.*;
public class Main416 {
public static void main(String[] args) {
int[] nums = {1, 5, 11, 5}; // true
// int[] nums = {1, 2, 3, 5}; // false
boolean res = canPartition(nums);
System.out.println(res);
}
// 优化前
private static boolean canPartition(int[] nums) {
int n = nums.length, m = 0;
for (int x : nums) {
m += x;
}
if (m % 2 != 0) return false;
m /= 2;
int[] f = new int[m + 1];
f[0] = 1;
for (int x : nums) {
for (int j = m; j >= x; j --)
f[j] |= f[j - x];
}
return f[m] != 0;
}
// 优化后的代码 不知道怎么转成java,bitset<10001> f怎么转成java对应的
}
LC433. 最小基因变化
// 有bug,输出的结果不对
import java.util.*;
public class Main433 {
public static void main(String[] args) {
String start = "AACCGGTT", end = "AACCGGTA";
String[] bank = {"AACCGGTA"};
int res = minMutation(start, end, bank);
System.out.println(res);
}
private static int minMutation(String start, String end, String[] bank) {
HashSet<String> S = new HashSet<>();
for (String s : bank) {
S.add(s);
}
HashMap<String, Integer> dist = new HashMap<>();
Queue<String> q = new LinkedList<>();
q.add(start);
dist.put(start, 0);
char[] chrs = {'A', 'T', 'C', 'G'};
while (q.size() != 0) {
String t = q.poll();
for (int i = 0; i < t.length(); i ++) {
String s = t;
for (char c : chrs) {
s.replace(s.charAt(i), c);
if (S.contains(s) && dist.get(s) == 0) {
dist.put(s, dist.getOrDefault(t, 0) + 1);
if (s == end) return dist.get(s);
q.add(s);
}
}
}
}
return -1;
}
}
LC437. 路径总和III
import java.util.*;
public class Main437 {
public static HashMap<Integer, Integer> cnt = new HashMap<>();
public static int res = 0;
public static void main(String[] args) {
TreeNode root = new TreeNode(10,
new TreeNode(5, new TreeNode(3,
new TreeNode(3), new TreeNode(-2)),
new TreeNode(2, null, new TreeNode(1))),
new TreeNode(-3,
null,
new TreeNode(11))); // 3
int targetSum = 8;
int res = pathSum(root, targetSum);
System.out.println(res);
}
public static int pathSum(TreeNode root, int sum) {
cnt.put(0, 1);
dfs(root, sum, 0);
return res;
}
private static void dfs(TreeNode root, int sum, int cur) {
if (root == null) return ;
cur += root.val;
res += cnt.getOrDefault(cur - sum, 0);
cnt.put(cur, cnt.getOrDefault(cur, 0) + 1);
dfs(root.left, sum, cur);
dfs(root.right, sum, cur);
cnt.put(cur, cnt.getOrDefault(cur, 0) - 1);
}
public static class TreeNode {
public int val;
TreeNode left, right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}
LC438. 找到字符串中所有字母异位词
// 有bug,输出的结果不对
import java.util.*;
public class Main438 {
public static void main(String[] args) {
String s = "cbaebabacd", p = "abc"; // 0 6
// String s = "abab", p = "ab"; // 0 1 2
int[] res = findAnagrams(s, p);
for (int r : res) {
System.out.println(r);
}
}
private static int[] findAnagrams(String s, String p) {
HashMap<Character, Integer> cnt = new HashMap<>();
for (int i = 0; i < p.length(); i ++) {
cnt.put(p.charAt(i), cnt.getOrDefault(p.charAt(i), 0) + 1);
}
List<Integer> res = new ArrayList<>();
int tot = cnt.size();
for (int i = 0, j = 0, satisfy = 0; i < s.length(); i ++) {
int t = cnt.getOrDefault(s.charAt(i), 0);
if (-- t == 0) satisfy ++;
while (i - j + 1 > p.length()) {
if (cnt.getOrDefault(s.charAt(j), 0) == 0) satisfy --;
cnt.put(s.charAt(j), cnt.getOrDefault(s.charAt(j), 0) + 1);
j ++;
}
if (satisfy == tot) res.add(j);
}
int[] ans = new int[res.size()];
for (int i = 0; i < ans.length; i ++) {
ans[i] = res.get(i);
}
return ans;
}
}
LC441. 排列硬币
import java.util.*;
public class Main441 {
public static void main(String[] args) {
// int n = 5; // 2
int n = 8; // 3
int res = arrangeCoins(n);
System.out.println(res);
}
private static int arrangeCoins(int n) {
return (int) (-1 + Math.sqrt(1 + 8.0 * n)) / 2;
}
}
LC442. 数组中重复的数据
import java.util.*;
public class Main442 {
public static void main(String[] args) {
int[] nums = {4, 3, 2, 7, 8, 2, 3, 1}; // 2 3
// int[] nums = {1, 1, 2}; // 1
int[] res = findDuplicates(nums);
for (int r : res) {
System.out.print(r);
System.out.print(" ");
}
}
private static int[] findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<>();
for (int x : nums) {
int p = Math.abs(x) - 1;
nums[p] *= -1;
if (nums[p] > 0) res.add(Math.abs(x));
}
int[] ans = new int[res.size()];
for (int i = 0; i < ans.length; i ++) {
ans[i] = res.get(i);
}
return ans;
}
}
LC443. 压缩字符串
import java.util.*;
public class Main443 {
public static void main(String[] args) {
// char[] chars = {'a', 'a', 'b', 'b', 'c', 'c', 'c'}; // 6
char[] chars = {'a','b','b','b','b','b','b','b','b','b','b','b','b'}; // 4
int res = compress(chars);
System.out.println(res);
}
private static int compress(char[] s) {
int k = 0;
for (int i = 0; i < s.length; i ++) {
int j = i + 1;
while (j < s.length && s[j] == s[i]) j ++;
int len = j - i;
s[k ++] = s[i];
if (len > 1) {
int t = k;
while (len != 0) {
s[t ++] = (char) ('0' + len % 10);
len /= 10;
}
reverse(s, k, t);
k = t;
}
i = j - 1;
}
return k;
}
private static void reverse(char[] s, int k, int t) {
for (int i = k, j = t; i < j; i ++, j --) {
swap(s, i, j);
}
}
private static void swap(char[] s, int i, int j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
LC445. 两数相加II
import java.util.*;
public class Main445 {
public static void main(String[] args) {
ListNode l1 = new ListNode(7, new ListNode(2, new ListNode(4, new ListNode(3))));
ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
print(l1);
System.out.println();
print(l2);
ListNode res = addTwoNumbers(l1, l2);
System.out.println();
print(res); // 1 3 5 2 4
}
// 第一种写法:只翻转2次链表
/* private static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l1 = reverse(l1);
l2 = reverse(l2);
ListNode head = new ListNode(-1);
int t = 0;
while (l1 != null || l2 != null || t != 0) {
if (l1 != null) {
t += l1.val;
l1 = l1.next;
}
if (l2 != null) {
t += l2.val;
l2 = l2.next;
}
ListNode cur = new ListNode(t % 10);
t /= 10;
cur.next = head.next;
head.next = cur;
}
return reverse(head.next);
}*/
// 第二种写法:翻转3次链表
private static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l1 = reverse(l1);
l2 = reverse(l2);
ListNode dummy = new ListNode(-1), cur = dummy;
int t = 0;
while (l1 != null || l2 != null || t != 0) {
if (l1 != null) {
t += l1.val;
l1 = l1.next;
}
if (l2 != null) {
t += l2.val;
l2 = l2.next;
}
cur = cur.next = new ListNode(t % 10);
t /= 10;
}
return reverse(dummy.next);
}
public static ListNode reverse(ListNode head) {
ListNode a = head, b = a.next;
while (b != null) {
ListNode c = b.next;
b.next = a;
a = b; b = c;
}
head.next = null;
return a;
}
public static void print(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
System.out.print(p.val);
System.out.print(" ");
}
}
public static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
}
LC448. 找到所有数组中消失的数字
import java.util.*;
public class Main448 {
public static void main(String[] args) {
int[] nums = {4, 3, 2, 7, 8, 2, 3, 1}; // 5 6
// int[] nums = {1, 1}; // 2
int[] res = findDisappearedNumbers(nums);
for (int r : res) {
System.out.print(r);
System.out.print(" ");
}
}
private static int[] findDisappearedNumbers(int[] nums) {
for (int x : nums) {
x = Math.abs(x);
if (nums[x - 1] > 0) nums[x - 1] *= -1;
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0)
res.add(i + 1);
}
int[] ans = new int[res.size()];
for (int i = 0; i < ans.length; i ++) {
ans[i] = res.get(i);
}
return ans;
}
}
LC450. 删除二叉搜索树中的节点
import java.util.*;
public class Main450 {
public static void main(String[] args) {
TreeNode root = new TreeNode(5,
new TreeNode(3, new TreeNode(2, null, null), new TreeNode(4, null, null)),
new TreeNode(6,
null,
new TreeNode(7, null, null)));
/*2 3 4 5 6 7
2 4 4 5 6 7 结果不正确,结果多了个4 */
int key = 3;
inorder(root);
for (Integer r : res) {
System.out.print(r);
System.out.print(" ");
}
System.out.println();
res = new ArrayList<>();
root = deleteNode(root, key);
inorder(root);
for (Integer r : res) {
System.out.print(r);
System.out.print(" ");
}
System.out.println();
}
public static TreeNode deleteNode(TreeNode root, int key) {
del(root, key);
return root;
}
public static void del(TreeNode root, int key) {
if (root == null) return ;
if (key == root.val) {
if (root.left == null && root.right == null) root = null;
else if (root.left == null) root = root.right;
else if (root.right == null) root = root.left;
else {
TreeNode p = root.right;
while (p.left != null) p = p.left;
root.val = p.val;
del(root.right, p.val);
}
}
else if (key < root.val) del(root.left, key);
else del(root.right, key);
}
public static List<Integer> res = new ArrayList<>();
public static void inorder(TreeNode root) {
if (root == null) return ;
inorder(root.left);
if (root != null) res.add(root.val);
inorder(root.right);
}
public static class TreeNode {
public int val;
TreeNode left, right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}
LC454. 四数相加II
import java.util.*;
public class Main454 {
public static void main(String[] args) {
int[] nums1 = {1, 2}, nums2 = {-2, -1}, nums3 = {-1, 2}, nums4 = {0, 2}; // 2
// int[] nums1 = {0}, nums2 = {0}, nums3 = {0}, nums4 = {0}; // 1
int res = fourSumCount(nums1, nums2, nums3, nums4);
System.out.println(res);
}
private static int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
HashMap<Integer, Integer> cnt = new HashMap<>();
for (int c : C) {
for (int d : D) {
cnt.put(c + d, cnt.getOrDefault(c + d, 0) + 1);
}
}
int res = 0;
for (int a : A) {
for (int b : B) {
res += cnt.getOrDefault(-(a + b), 0);
}
}
return res;
}
}
LC462. 最少移动次数使数组元素相等II
import java.util.*;
public class Main462 {
public static void main(String[] args) {
int[] nums = {1, 2, 3}; // 2
// int[] nums = {1, 10, 2, 9}; // 16
int res = minMoves2(nums);
System.out.println(res);
}
private static int minMoves2(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int res = 0;
for (int i = 0; i < n; i++) {
res += Math.abs(nums[i] - nums[n / 2]);
}
return res;
}
}
LC463. 岛屿的周长
import java.util.*;
public class Main463 {
public static void main(String[] args) {
int[][] grid = new int[][] {
{0, 1, 0, 0},
{1, 1, 1, 0},
{0, 1, 0, 0},
{1, 1, 0, 0}
}; // 16
int res = islandPerimeter(grid);
System.out.println(res);
}
private static int islandPerimeter(int[][] grid) {
int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
int res = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
for (int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) res ++;
else if (grid[x][y] == 0) res ++;
}
}
}
}
return res;
}
}
LC474. 一和零
import java.util.*;
public class Main474 {
public static void main(String[] args) {
String[] strs = {"10", "0001", "111001", "1", "0"};
int m = 5, n = 3; // 4
/*
String[] strs = {"10", "0", "111001", "1"};
int m = 1, n = 1; // 2
*/
int res = findMaxForm(strs, m, n);
System.out.println(res);
}
private static int findMaxForm(String[] strs, int m, int n) {
int[][] f = new int[m + 1][n + 1];
for (String str : strs) {
int a = 0, b = 0;
for (int i = 0; i < str.length(); i ++) {
if (str.charAt(i) == '0') a ++;
else b ++;
}
for (int i = m; i >= a; i --) {
for (int j = n; j >= b; j --) {
f[i][j] = Math.max(f[i][j], f[i - a][j - b] + 1);
}
}
}
return f[m][n];
}
}
LC475. 供暖器
import java.util.*;
public class Main475 {
public static void main(String[] args) {
int[] houses = {1, 2, 3}, heaters = {2}; // 1
// int[] houses = {1, 2, 3, 4}, heaters = {1, 4}; // 1
int res = findRadius(houses, heaters);
System.out.println(res);
}
private static int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int l = 0, r = Integer.MAX_VALUE;
while (l < r) {
int mid = (int) ((long) (l + r) >> 1);
if (check(mid, houses, heaters)) r = mid;
else l = mid + 1;
}
return r;
}
private static boolean check(int mid, int[] houses, int[] heaters) {
for (int i = 0, j = 0; i < houses.length; i ++) {
while (j < heaters.length && Math.abs(heaters[j] - houses[i]) > mid) j ++;
if (j >= heaters.length) return false;
}
return true;
}
}
LC477. 汉明距离总和
import java.util.*;
public class Main477 {
public static void main(String[] args) {
int[] nums = {4, 14, 2}; // 6
// int[] nums = {4, 14, 4}; // 4
int res = totalHammingDistance(nums);
System.out.println(res);
}
private static int totalHammingDistance(int[] nums) {
int res = 0;
for (int i = 0; i <= 30; i++) {
int x = 0, y = 0;
for (int c : nums) {
if ((c >> i & 1) != 0) y ++;
else x ++;
}
res += x * y;
}
return res;
}
}
LC482. 密钥格式化
// 有bug,输出的e居然是小写,不知道哪里有问题!
import java.util.*;
public class Main482 {
public static void main(String[] args) {
String S = "5F3Z-2e-9-w";
int k = 4;
String res = licenseKeyFormatting(S, k);
System.out.println(res);
}
private static String licenseKeyFormatting(String S, int k) {
String s = "";
for (int i = 0; i < S.length(); i ++) {
if (S.charAt(i) != '-') s += S.charAt(i);
}
String res = "";
for (int i = 0; i < s.length() % k; i ++) res += S.charAt(i);
res.toUpperCase();
for (int i = s.length() % k; i < s.length(); ) {
if (res.length() != 0) res += '-';
for (int j = 0; j < k; j ++) {
res += s.charAt(i);
i ++;
}
}
res.toUpperCase();
return res;
}
}
LC486. 预测赢家
import java.util.*;
public class Main486 {
public static void main(String[] args) {
int[] nums = {1, 5, 2}; // false
boolean res = predictTheWinner(nums);
System.out.println(res);
}
private static boolean predictTheWinner(int[] nums) {
int n = nums.length;
int[][] f = new int[n][n];
for (int len = 1; len <= n; len ++) {
for (int i = 0; i + len - 1 < n; i ++) {
int j = i + len - 1;
if (len == 1) f[i][j] = nums[i];
else {
f[i][j] = Math.max(nums[i] - f[i + 1][j], nums[j] - f[i][j - 1]);
}
}
}
return f[0][n - 1] >= 0;
}
}