本文最后更新于2021年9月21日,已超过 9 个月没更新!
April
4月30日
只出现一次的数字II
⚡ 哈希表O(N) O(N)
class Solution {
public int singleNumber(int[] nums) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
if (entry.getValue() == 1) return entry.getKey();
}
return -1;
}
}
⚡ 依次确定每一个二进制位 O(N) O(1)
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < 32; ++i) {
int count = 0;
for (int num : nums) {
count += (num >> i) & 1;
}
if (count % 3 != 0) {
ans |= 1 << i;
}
}
return ans;
}
}
4月29日
青蛙过河⭐
⚡ 动态规划
class Solution {
public boolean canCross(int[] stones) {
int n = stones.length;
//dp[i][j] 表示从上一个石头用j跳,是否可以跳到stones[i]石头上
boolean[][] dp = new boolean[n][n];
dp[0][0] = true;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
int k = stones[i] - stones[j];
if (k <= j + 1) { //在stones[j]表示的石头上最多可向前跳j + 1步
dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1]; //判断是否有石子在k - 1到k + 1跳范围内, 可跳到stones[j]上
}
}
}
for (int i = 1; i < n; ++i) {
if (dp[n - 1][i]) return true;
}
return false;
}
}
⚡ 动态规划(优化)
class Solution {
public boolean canCross(int[] stones) {
int n = stones.length;
//初步去掉一些显然不可到达的情况
for (int i = 1; i < n; ++i) {
//两个石头所在实际位置之差不可大于后者的数组索引值
if (stones[i] - stones[i - 1] > i) return false;
}
//动态规划求解是否可到达最后一个石头
// dp[i][k] 表示从上一个石头用k跳,是否可以跳到stones[i]石头上
boolean[][] dp = new boolean[n][n];
dp[0][0] = true;
for (int i = 1; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
int k = stones[i] - stones[j];
// 在stones[j]表示的石头上最多可向前跳j + 1步
if (k > j + 1) break; //"剪枝",出现不满足条件的情况即可跳出此次循环
//判断是否有石子在k - 1到k + 1跳范围内, 可跳到stones[j]上
dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
if (i == n - 1 && dp[i][k]) return true;
}
}
return false;
}
}
可获得的最大点数
⚡ 滑动窗口
class Solution {
public int maxScore(int[] cardPoints, int k) {
//剩余的卡牌必然是连续的
//求得长度为 length - k 的最小自序和即可
//滑动窗口
int i = 0, j = cardPoints.length - k;
int tmpSum = 0;
for (int c = i; c < j; ++c) tmpSum += cardPoints[c];
int ans = tmpSum;
while (j < cardPoints.length) {
tmpSum = tmpSum - cardPoints[i++] + cardPoints[j++];
ans = Math.min(ans, tmpSum);
}
return Arrays.stream(cardPoints).sum() - ans;
}
}
4月28日
平方数之和
⚡ 双指针O(sqrt(c))
class Solution {
public boolean judgeSquareSum(int c) {
int a = 0, b = (int) Math.sqrt(c);
while (a <= b) {
int tmp = c - b * b;
if (tmp > a * a) ++a;
else if (tmp < a * a) --b;
else return true;
}
return false;
}
}
排序链表⭐
⚡ 归并排序O(nlogn)
class Solution {
//递归
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
//找到中间结点
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//中间截断链表
ListNode head2 = slow.next;
slow.next = null;
//递归
ListNode left = sortList(head);
ListNode right = sortList(head2);
//归并两个有序段
ListNode res = new ListNode(0);
ListNode h = res;
while (left != null && right != null) {
if (left.val > right.val) {
h.next = right;
right = right.next;
}
else {
h.next = left;
left = left.next;
}
h = h.next;
}
h.next = (left == null ? right : left);
return res.next;
}
}
4月27日
二叉搜索树的范围和⭐
⚡ DFS先序遍历
class Solution {
//递归
public int rangeSumBST(TreeNode root, int low, int high) {
if (root == null) return 0;
if (root.val > high) {
return rangeSumBST(root.left, low, high);
}
if (root.val < low) {
return rangeSumBST(root.right, low, high);
}
return root.val + rangeSumBST(root.right, low, high) + rangeSumBST(root.left, low, high);
}
}
class Solution {
//迭代 先序遍历
public int rangeSumBST(TreeNode root, int low, int high) {
int sum = 0;
Deque<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
if (node.val < low) {
stack.push(node.right);
}
else if (node.val > high) {
stack.push(node.left);
}
else {
sum += node.val;
stack.push(node.left);
stack.push(node.right);
}
}
return sum;
}
}
⚡ BFS层序遍历
class Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
int sum = 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode tmpNode = queue.poll();
if (tmpNode == null) {
continue;
}
if (tmpNode.val > high) {
queue.offer(tmpNode.left);
}
else if (tmpNode.val < low) {
queue.offer(tmpNode.right);
}
else {
sum += tmpNode.val;
queue.offer(tmpNode.left);
queue.offer(tmpNode.right);
}
}
return sum;
}
}
对链表进行插入排序⭐
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null) return head;
ListNode dummyNode = new ListNode(0); //空头结点
dummyNode.next = head;
ListNode lastSort = head; //已经排好序部分的尾结点
ListNode cur = head.next; //当前指向的结点
while (cur != null) {
if (lastSort.val <= cur.val) {
lastSort = lastSort.next;
}
else {
ListNode p = dummyNode;
while (p.next.val <= cur.val) {
p = p.next;
}
lastSort.next = cur.next;
cur.next = p.next;
p.next = cur;
}
cur = lastSort.next;
}
return dummyNode.next;
}
}
4月26日
在D天内送达包裹的能力⭐
⚡ 二分法
class Solution {
public int shipWithinDays(int[] weights, int D) {
//确定左右边界
int left = Arrays.stream(weights).max().getAsInt();
int right = Arrays.stream(weights).sum();
while (left < right) {
int mid = left + right >> 1;
int day = 1, cur = 0;
for (int weight : weights) {
cur += weight;
if (cur > mid) {
++day;
cur = weight;
}
}
//本题要最小的载重量
//因此即使等于D,right也要继续左移,保证同等天数下的载重量最小
//官方第一个案例中15、16均可满足要求,但最后答案只能是15
if (day <= D) {
right = mid;
}else {
left = mid + 1;
}
}
return left;
}
}
4月25日
递增顺序搜索树
⚡ DFS
class Solution {
public TreeNode idxNode;
public TreeNode increasingBST(TreeNode root) {
TreeNode ans = new TreeNode(-1);
idxNode = ans;
inorder(root);
return ans.right;
}
private void inorder (TreeNode node) {
if (node == null) return;
inorder(node.left);
idxNode.right = new TreeNode(node.val);
idxNode = idxNode.right;
//在原树上操作
//idxNode.right = node;
//node.left = null;
//idxNode = node;
inorder(node.right);
}
}
4月24日
组合总和Ⅳ
⚡ 动态规划
class Solution {
public int combinationSum4(int[] nums, int target) {
//dp[i]表示组合为i的方案数
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (int num : nums) {
if (num <= i) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
注意: 顺序不同的序列被视作不同的组合。(和零钱兑换II进行区分)
4月23日
最大整除子集
⚡ 动态规划
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
//动态规划找出最大子集的个数、最大子集中的最大整数
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxSize = 0;
int maxVal = nums[0];
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] % nums[j] == 0) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
if (maxSize < dp[i]) {
maxVal = nums[i];
maxSize = dp[i];
}
}
}
//倒推获得最大子集
List<Integer> list = new ArrayList<Integer>();
if (maxSize == 0) {
list.add(nums[0]);
return list;
}
for (int i = n - 1; i >= 0 && maxSize > 0; --i) {
if (dp[i] == maxSize && maxVal % nums[i] == 0) {
list.add(nums[i]);
maxVal = nums[i];
--maxSize;
}
}
return list;
}
}
4月22日
矩形区域不超过K的最大数值和
⚡ 暴力 + 动态规划
class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int ans = Integer.MIN_VALUE;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
int[][] dp = new int[m + 1][n + 1];
dp[i][j] = matrix[i - 1][j - 1];
for (int ii = i; ii <= m; ++ii) {
for (int jj = j; jj <= n; ++jj) {
dp[ii][jj] = dp[ii - 1][jj] + dp[ii][jj - 1] - dp[ii - 1][jj - 1] + matrix[ii - 1][jj - 1];
if (dp[ii][jj] > ans && dp[ii][jj] <= k) ans = dp[ii][jj];
}
}
}
}
return ans;
}
}
⚡ 数组滚动⭐
class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int max = Integer.MIN_VALUE;
for (int i = 0; i < m; ++i) { //枚举上边界
int[] sum = new int[n];
for (int j = i; j < m; ++j) { //枚举下边界
for (int c = 0; c < n; ++c) {
sum[c] += matrix[j][c]; //更新每列元素的和
}
//化为一维问题求解
max = Math.max(max, findMax(sum, k));
}
}
return max;
}
//求一维数组中不超过k的最大数值和
public static int findMax (int[] arr, int k) {
int n = arr.length;
int max = Integer.MIN_VALUE;
int sum = 0;
//先求数组的最大自序和
for (int i = 0; i < n; ++i) {
sum = Math.max(sum + arr[i], arr[i]);
max = Math.max(max, sum);
}
//如果最大自序和不超过k则返回其值
if (max <= k) return max;
max = Integer.MIN_VALUE;
//若最大自序和大于k,则开始暴力求解
for (int i = 0; i < n; ++i) {
sum = 0;
for (int j = i; j < n; ++j) {
sum += arr[j];
if (sum > max && sum <= k) {
max = sum;
}
}
}
return max;
}
}
4月21日
解码方法
⚡ 动态规划
class Solution {
public int numDecodings(String s) {
int len = s.length();
//dp[i]表示0到i-1字符的解码方法数量
int[] dp = new int[len + 1];
dp[0] = 1;
//注意边界条件的判断
for (int i = 1; i <= len; ++i) {
if (s.charAt(i - 1) != '0') {
dp[i] += dp[i - 1];
}
if (i > 1) {
int num = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
if (s.charAt(i - 2) != '0' && num <= 26) {
dp[i] += dp[i - 2];
}
}
}
return dp[len];
}
}
4月19日
移除元素
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
int slow = 0, fast = 0;
while (fast < n) {
if (nums[fast] != val) {
nums[slow++] = nums[fast++];
}
else ++fast;
}
return slow;
}
}
4月18日
删除有序数组中的重复项
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
int slow = 0, fast = 1;
while (fast < n) {
if (nums[slow] != nums[fast]) {
nums[++slow] = nums[fast++];
}
else ++fast;
}
return slow + 1;
}
}
注:与4月6日同类型
4月17日
存在重复元素III
⚡ 滑动窗口 & 有序集合
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int n = nums.length;
TreeSet<Long> set = new TreeSet<Long>();
//维护一个nums中i - k 到 i 的有序元素集合,找到有元素介于nums[i] - t , nums[i] + t之间返回true
for (int i = 0; i < n; ++i) {
//set.ceiling(e)在方法调用返回比至少元素大于或等于e或null,如果不存在这样的元素。
Long ceiling = set.ceiling((long)nums[i] - (long)t);
if (ceiling != null && ceiling <= ((long)nums[i] + (long)t)) {
return true;
}
set.add((long)nums[i]);
if (i >= k) {
set.remove((long)nums[i - k]);
}
}
return false;
}
}
4月16日
扰乱字符串🌟
⚡ 动态规划 & 递归
class Solution {
//记忆化搜索储存状态数组
//-1表示false
//1表示true
//0表示未计算
int[][][] memo;
String s1, s2;
public boolean isScramble(String s1, String s2) {
int len = s1.length();
this.memo = new int[len][len][len + 1];
this.s1 = s1;
this.s2 = s2;
return dfs(0, 0, len);
}
//判断输入两个字符串是否和谐
public boolean dfs (int i1, int i2, int length) {
if (memo[i1][i2][length] != 0) {
return memo[i1][i2][length] == 1;
}
//判断两个字串是否相等
if (s1.substring(i1, i1 + length).equals(s2.substring(i2, i2 + length))) {
memo[i1][i2][length] = 1;
return true;
}
//判断是否存在子串c在两段字符中出现次数不同
if (!checkIfSimilar(i1, i2, length)) {
memo[i1][i2][length] = -1;
return false;
}
//枚举不同的分割位置
for (int i = 1; i < length; ++i) {
//分割子串不交换位置
if (dfs(i1, i2, i) && dfs(i1 + i, i2 + i, length - i)) {
memo[i1][i2][length] = 1;
return true;
}
//分割子串交换位置
if (dfs(i1, i2 + length - i, i) && dfs(i1 + i, i2, length - i)) {
memo[i1][i2][length] = 1;
return true;
}
}
memo[i1][i2][length] = -1;
return false;
}
//检查两子串中相同字符出现次数是否相同
public boolean checkIfSimilar (int i1, int i2, int length) {
HashMap<Character, Integer> freq = new HashMap<Character, Integer>();
//对应键值加1
for (int i = i1; i < i1 + length; ++i) {
//getOrDefault() 方法获取指定 key 对应对 value,如果找不到 key ,则返回设置的默认值。
//key - 键
//defaultValue - 当指定的key并不存在映射关系中,则返回的该默认值
char c = s1.charAt(i);
freq.put (c, freq.getOrDefault(c, 0) + 1);
}
//对应键值减1
for (int i = i2; i < i2 + length; ++i) {
char c = s2.charAt(i);
freq.put(c, freq.getOrDefault(c, 0) - 1);
}
//遍历整个HashMap
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
//不为零则两字串中对应字符出现次数不同
if (entry.getValue() != 0) return false;
}
return true;
}
}
4月15日
打家劫舍 II
⚡ 动态规划
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
if (n == 1) return nums[0];
if (n == 2) return Math.max(nums[0], nums[1]);
int[] dp1 = new int[n];
int[] dp2 = new int[n];
//1到n
dp1[1] = nums[1];
dp1[2] = Math.max(nums[1], nums[2]);
for (int i = 3; i < n; ++i) {
dp1[i] = Math.max(dp1[i - 2] + nums[i], dp1[i - 1]);
}
//0到n-1
dp2[0] = nums[0];
dp2[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n - 1; ++i) {
dp2[i] = Math.max(dp2[i - 2] + nums[i], dp2[i - 1]);
}
return Math.max(dp1[n - 1], dp2[n - 2]);
}
}
打家劫舍
⚡ 动态规划
class Solution {
public int rob(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; ++i) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[n - 1];
}
}
4月14日
实现 Trie (前缀树)
class Trie {
private Trie[] children;
private boolean isEnd;
/** Initialize your data structure here. */
public Trie() {
children = new Trie[26];
isEnd = false;
}
/** Inserts a word into the trie. */
public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); ++i) {
int idx = word.charAt(i) - 'a';
if (node.children[idx] == null) {
node.children[idx] = new Trie();
}
node = node.children[idx];
}
node.isEnd = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
//查找指定字符串是否在字典树中存在,并返回最后一个字母所在节点
public Trie searchPrefix(String prefix) {
Trie node = this;
for (int i = 0; i < prefix.length(); ++i) {
int idx = prefix.charAt(i) - 'a';
if (node.children[idx] == null) {
return null;
}
node = node.children[idx];
}
return node;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
岛屿数量⭐
⚡ DFS深度优先遍历
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
//当是陆地时,进入递归,递归结束时岛屿数量加1
if (grid[i][j] == '1') {
gridDfs (grid, i, j);
++count;
}
}
}
return count;
}
public void gridDfs (char[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
return;
}
//标记已访问,当原图不能改时可以用visited数组代替
grid[i][j] = '0';
//递归周边其他节点
gridDfs (grid, i + 1, j);
gridDfs (grid, i, j + 1);
gridDfs (grid, i - 1, j);
gridDfs (grid, i, j - 1);
}
}
⚡ DFS广度优先遍历
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
//当是陆地时,进入递归,递归结束时岛屿数量加1
if (grid[i][j] == '1') {
grid[i][j] = '0';
gridBfs (grid, i, j);
++count;
}
}
}
return count;
}
//广度优先遍历
public void gridBfs (char[][] grid, int i, int j) {
int n = grid.length;
int m = grid[0].length;
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(i * m + j);
while (!queue.isEmpty()) {
int cur = queue.poll();
i = cur / m; j = cur % m;
//入队前先判断防止重复入队浪费资源
if ((i - 1) >= 0 && grid[i - 1][j] == '1') {
grid[i - 1][j] = '0';
queue.offer((i - 1) * m + j);
}
if ((i + 1) < n && grid[i + 1][j] == '1') {
grid[i + 1][j] = '0';
queue.offer((i + 1) * m + j);
}
if ((j - 1) >= 0 && grid[i][j - 1] == '1') {
grid[i][j - 1] = '0';
queue.offer(i * m + j - 1);
}
if ((j + 1) < m && grid[i][j + 1] == '1') {
grid[i][j + 1] = '0';
queue.offer(i * m + j + 1);
}
}
}
}
BFS遍历方法的另一种写法:
public void gridBfs (char[][] grid, int i, int j) {
Queue<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] {i, j});
while (!queue.isEmpty()) {
int[] cur = queue.remove();
i = cur[0]; j = cur[1];
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
continue;
}
grid[i][j] = '0';
//未判断会出现重复入队
queue.add(new int[] {i + 1, j});
queue.add(new int[] {i, j + 1});
queue.add(new int[] {i - 1, j});
queue.add(new int[] {i, j - 1});
}
}
- offer,add 区别:
- 一些队列有大小限制,因此如果想在一个满的队列中加入一个新项,多出的项就会被拒绝。这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常,而只是得到由 offer() 返回的 false。
- poll,remove 区别:
- remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似, 但是新的 poll() 方法在用空集合调用时不是抛出异常,只是返回 null。因此新的方法更适合容易出现异常条件的情况。
- peek,element区别:
- element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似,在队列为空时, element() 抛出一个异常,而 peek() 返回 null。
4月13日
二叉搜索树节点最小距离
⚡ 对二叉搜索树进行中序遍历,将遍历的值保存到list中,再判断元素之间最小差值
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDiffInBST(TreeNode root) {
List<Integer> list = new ArrayList<>();
inorder (root, list);
int min = Integer.MAX_VALUE;
for (int i = 1; i < list.size(); ++i) {
min = Math.min(list.get(i) - list.get(i - 1), min);
}
return min;
}
//中序遍历
private void inorder (TreeNode node, List<Integer> res) {
if (node == null) return;
inorder (node.left, res);
res.add(node.val);
inorder (node.right, res);
}
}
⚡ 上述方法优化
class Solution {
int ans = Integer.MAX_VALUE;
int pre = -1;
public int minDiffInBST(TreeNode root) {
return inorder(root);
}
//中序遍历
private int inorder (TreeNode node) {
if (node == null) return ans;
inorder(node.left);
if (pre == -1) pre = node.val;
else {
ans = Math.min(ans, node.val - pre);
pre = node.val;
}
inorder (node.right);
return ans;
}
}
4月12日
最大数⭐
class Solution {
public String largestNumber(int[] nums) {
int n = nums.length;
//Arrays类提供的函数中,没有方法对int[]数组进行排序。
//sort函数可以有第二个参数: Comparator参数,但此参数仅支持引用类型。
//int并非引用类型,无法对int[]数组进行排序,因此需要把数组复制进Integer[]数组中。
Integer[] numsArr = new Integer[n];
for (int i = 0; i < n; ++i) {
numsArr[i] = nums[i];
}
//使用lambda表达式重写Comparator比较器
//返回值小于0时,排序x在y的前面;返回值大于0时,排序x在y的后面;
Arrays.sort(numsArr, (x, y) -> {
long sx = 10, sy = 10;
while (sx <= x) sx *= 10;
while (sy <= y) sy *= 10;
return (int) (sx * y + x - sy * x - y);
});
//上述步骤结束后numsArr里元素已经按照要求排序完成
//首先判断是否元素都为0
if (numsArr[0] == 0) return "0";
//以下进行数组结果字符串输出
StringBuilder ret = new StringBuilder();
for (int num : numsArr) ret.append(num);
return ret.toString();
}
}
4月11日
丑数II⭐
⚡ 动态规划
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
int p2 = 1, p3 = 1, p5 = 1;
for (int i = 2; i <= n; ++i) {
int num2 = dp[p2] * 2;
int num3 = dp[p3] * 3;
int num5 = dp[p5] * 5;
dp[i] = Math.min(Math.min(num2, num3), num5);
if (dp[i] == num2) ++p2;
if (dp[i] == num3) ++p3;
if (dp[i] == num5) ++p5;
}
return dp[n];
}
}
4月10日
丑数
⚡ 丑数就是只包含质因数2、3、5 的正整数
class Solution {
public boolean isUgly(int n) {
if (n <= 0) return false;
while (n % 2 == 0) n /= 2;
while (n % 3 == 0) n /= 3;
while (n % 5 == 0) n /= 5;
if (n == 1) return true;
else return false;
}
}
4月9日
寻找旋转排序数组中的最小值II⭐
⚡ 二分法
class Solution {
public int findMin(int[] nums) {
int low = 0, high = nums.length - 1;
while (low < high) {
int mid = (low + high) / 2;
if (nums[mid] < nums[high]) {
high = mid;
}
else if (nums[mid] > nums[high]) {
low = mid + 1;
}
else --high;
}
return nums[low];
}
}
4月8日
寻找旋转排序数组中的最小值
⚡ 利用规律线性查找
class Solution {
public int findMin(int[] nums) {
for (int i = 1; i < nums.length; ++i) {
if (nums[i] < nums[i - 1]) return nums[i];
}
return nums[0];
}
}
⚡ 二分法
class Solution {
public int findMin(int[] nums) {
int low = 0, high = nums.length - 1;
while (low < high) {
int mid = (low + high) / 2;
if (nums[mid] < nums[high]) {
high = mid;
}
//不可能会有等于的情况
else if (nums[mid] > nums[high]) {
low = mid + 1;
}
}
return nums[low];
}
}
4月7日
搜索旋转排序数II⭐
⚡ 利用规律线性查找
class Solution {
public boolean search(int[] nums, int target) {
int n = nums.length;
if (nums[0] == target || nums[n - 1] == target) return true;
for (int i = 0; i < n - 1; ++i) {
if (target > nums[i] && target < nums[i + 1]) {
return false;
}
else if (target == nums[i]) {
return true;
}
}
return false;
}
}
⚡ 二分法
class Solution {
public boolean search(int[] nums, int target) {
int n = nums.length;
if (n == 0) return false;
if (n == 1) return nums[0] == target;
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) return true;
if (nums[mid] == nums[low] && nums[mid] == nums[high]) {
++low;
--high;
}
else if (nums[low] <= nums[mid]) {
//这里由于上面已经判断过了target == nums[mid]因此可以不需要做等于判断。
if (target >= nums[low] && target < nums[mid]) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
else {
if (target > nums[mid] && target <= nums[high]) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
}
return false;
}
}
搜索旋转排序数组
⚡ 二分法
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0) return -1;
if (n == 1) return nums[0] == target ? 0 : -1;
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) return mid;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) high = mid - 1;
else low = mid + 1;
}
else {
if (nums[mid] < target && target <= nums[n - 1]) low = mid + 1;
else high = mid - 1;
}
}
return -1;
}
}
验证回文串
class Solution {
public boolean isPalindrome(String s) {
int n = s.length();
int low = 0, high = n - 1;
while (low < high) {
while (low < high && !Character.isLetterOrDigit(s.charAt(low))) ++low;
while (low < high && !Character.isLetterOrDigit(s.charAt(high))) --high;
if(low < high) {
if (Character.toLowerCase(s.charAt(low)) != Character.toLowerCase(s.charAt(high))) {
return false;
}
++low;
--high;
}
}
return true;
}
}
- Character.toLowerCase()方法用于将大写字符转换为小写。
- Character.isLetterOrDigit()方法确定指定字符(Unicode代码点)是一个字母或数字。
4月6日
删除有序数组中的重复项II
class Solution {
public int removeDuplicates(int[] nums) {
int len = nums.length;
if (len <= 2) return len;
int slow = 2, fast = 2;
while (fast < len) {
if(nums[slow - 2] != nums[fast]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
}
4月5日
合并两个有序数组
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1;
int k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
}
else {
nums1[k--] = nums2[j--];
}
}
}
}
二分查找
class Solution {
public int search(int[] nums, int target) {
int low = 0, high = nums.length - 1;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
if (nums[mid] > target) {
high = mid - 1;
}
else if (nums[mid] < target) {
low = mid + 1;
}
else return mid;
}
return -1;
}
}
截断句子
class Solution {
public String truncateSentence(String s, int k) {
StringBuilder ans = new StringBuilder();
for (String i : s.split("\\s+")) {
if (k-- > 0)
ans = ans.append(i).append(' ');
}
ans.setLength(ans.length() - 1);
return ans.toString();
}
}
- split("\s+") 按空格,制表符,等进行拆分,也就是说它是按空白部分进行拆分,不管这个空白使用什么操作留下的(如空格键 tab键);
- split(" +") 按空格进行拆分,也就是说只有按空格键流出来的空白才会是拆分的一句。
4月4日
森林中的兔子
class Solution {
public int numRabbits(int[] answers) {
Map<Integer, Integer> count = new HashMap<Integer, Integer>();
for (int y : answers) {
//getOrDefault()方法获取指定key对应对value,如果找不到key,则返回设置的默认值。
count.put(y, count.getOrDefault(y, 0) + 1);
}
int ans = 0;
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
int y = entry.getKey(), x = entry.getValue();
// (x + y) / (y + 1)用来向上取整求共有多少组兔子
ans += (x + y) / (y + 1) * (y + 1);
}
return ans;
}
}
万一兔子说谎了呢?
排序数组
⚡ 快速排序
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length-1);
return nums;
}
public static void quickSort(int[] arr, int start, int end) {
int mid = partition(arr, start, end); //数组分区
quickSort(arr, start, mid - 1); //左边快排
quickSort(arr, mid + 1, end); //右边快排
}
public static int partition(int[] arr, int start, int end) {
int pivot = arr[0];
while (start < end) {
while (start < end && arr[end] >= pivot) --end;
arr[start] = arr[end];
while (start < end && arr[start] <= pivot) ++start;
arr[end] = arr[start];
}
arr[start] = pivot;
return start;
}
}
4月3日
最长公共子序列
4月2日
直方图的水量⭐
⚡ 动态规划 Time: O(n) Space: O(n)
class Solution {
public int trap(int[] height) {
int n = height.length;
if(n == 0) return 0;
int leftMax[] = new int[n];
int rightMax[] = new int[n];
//动态规划两个表示某一元素左右两边最大值的数组
leftMax[0] = height[0];
rightMax[n - 1] = height[n - 1];
for (int i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
for (int j = n-2; j >= 0; --j) {
rightMax[j] = Math.max(rightMax[j + 1], height[j]);
}
//利用求出的两个数组求水量
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}
⚡ 双指针法 Time: O(n) Space: O(1)
class Solution {
public int trap(int[] height) {
int ans = 0;
int low = 0, high = height.length - 1;
int lowMax = 0, highMax = 0;
while (low < high) {
lowMax = Math.max(lowMax, height[low]);
highMax = Math.max(highMax, height[high]);
if(height[low] < height[high]) {
ans += lowMax - height[low];
++low;
}
else {
ans += highMax - height[high];
--high;
}
}
return ans;
}
}
4月1日
笨阶乘
⚡ 栈模拟
class Solution {
public int clumsy(int N) {
Deque<Integer> stack = new LinkedList<Integer>();
stack.push(N--);
int index = 0;
while(N > 0) {
if(index % 4 == 0) stack.push(stack.pop() * N);
else if(index % 4 == 1) stack.push(stack.pop() / N);
else if(index % 4 == 2) stack.push(N);
else stack.push(-N);
--N; ++index;
}
int sum = 0;
while(!stack.isEmpty()) {
sum += stack.pop();
}
return sum;
}
}
删除有序数组中的重复项
⚡ 双指针法
class Solution {
public int removeDuplicates(int[] nums) {
if(nums == null) return 0;
int i = 0, j = 1;
while(j < nums.length) {
if(nums[i] == nums[j]) ++j;
else nums[++i] = nums[j++];
}
return i + 1;
}
}
旋转数组
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length-1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
private void reverse(int[] nums, int low, int high) {
while(low < high) {
int temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
++low; --high;
}
}
}
March
3月31日
子集⭐
⚡ 回溯算法(递归)
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(0, nums, res, new ArrayList<Integer>());
return res;
}
private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> temp){
res.add(new ArrayList<>(temp));
for(int j = i; j < nums.length; ++j) {
temp.add(nums[j]);
backtrack(j + 1, nums, res, temp);
temp.remove(temp.size() - 1);
}
}
}
子集II⭐
⚡ 回溯算法
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums); //对有重复元素的数组先进行排序
backtrack(0, nums, res, new ArrayList<Integer>());
return res;
}
private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> temp){
res.add(new ArrayList<>(temp));
for(int j = i; j < nums.length; ++j) {
if(j != i && nums[j] == nums[j-1]) continue; //当出现重复元素进行剪枝
temp.add(nums[j]);
backtrack(j + 1, nums, res, temp);
temp.remove(temp.size() - 1);
}
}
}
搜索二维矩阵II
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length - 1, n = 0;
while(m >= 0 && n < matrix[0].length) {
if(matrix[m][n] > target) --m;
else if(matrix[m][n] < target) ++n;
else return true;
}
return false;
}
}
3月30日
搜索二维矩阵
⚡ 单次二分查找
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int low = 0, high = m * n - 1;
while(low <= high) {
int mid = (low + high) / 2;
int x = matrix[mid / n][mid % n];
if(x < target) low = mid + 1;
else if (x > target) high = mid - 1;
else return true;
}
return false;
}
}
二叉树的深度⭐
⚡ DFS后序遍历
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
⚡ BFS层序遍历
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int res = 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int currentLevelSize = queue.size();
for(int i = 0; i < currentLevelSize; ++i) {
TreeNode node = queue.poll();
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
res++;
}
return res;
}
}
平衡二叉树⭐
⚡ DFS自底向上
class Solution {
public boolean isBalanced(TreeNode root) {
return dfs(root) != -1;
}
private int dfs(TreeNode root) {
if(root == null) return 0;
int left = dfs(root.left);
if(left == -1) return -1;
int right = dfs(root.right);
if(right == -1) return -1;
return Math.abs(left - right) <= 1 ? Math.max(left, right) + 1 : -1;
}
}
⚡ 自顶向下
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int maxDepth(TreeNode root) {
if(root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
3月29日
颠倒二进制位
⚡ 逐位颠倒
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int ret = 0;
for(int i = 0; i < 32; ++i) {
ret |= (n & 1) << (31 - i);
n >>>= 1;
}
return ret;
}
}
⚡ 位运算分治
public class Solution {
// you need treat n as an unsigned value
private static final int M1 = 0x55555555;
private static final int M2 = 0x33333333;
private static final int M4 = 0x0f0f0f0f;
private static final int M8 = 0x00ff00ff;
public int reverseBits(int n) {
n = (n >>> 1 & M1) | ((n & M1) << 1);
n = (n >>> 2 & M2) | ((n & M2) << 2);
n = (n >>> 4 & M4) | ((n & M4) << 4);
n = (n >>> 8 & M8) | ((n & M8) << 8);
return n >>> 16 | (n << 16);
}
}
注:>>>表示不带符号向右移动二进制数,位运算优先级高于逻辑运算可去掉部分括号。
反转链表
⚡ 迭代法
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while(curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
}
⚡ 递归法
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode newhead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newhead;
}
}
3月28日
二叉搜索树迭代器
class BSTIterator {
private int index;
private List<Integer> arr;
public BSTIterator(TreeNode root) {
index = 0;
arr = new ArrayList<Integer>();
inorderTraversal(root, arr);
}
public int next() {
return arr.get(index++);
}
public boolean hasNext() {
return index < arr.size();
}
private void inorderTraversal(TreeNode root, List<Integer> arr) {
if (root == null) return;
inorderTraversal(root.left, arr);
arr.add(root.val);
inorderTraversal(root.right, arr);
}
}
3月27日
旋转链表
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(k==0 || head==null || head.next==null) {
return head;
}
int n = 1;
ListNode q = head;
while(q.next != null){
q = q.next;
n++;
}
int add = n - k%n;
if(add == n) return head;
q.next = head;
while(add-- > 0) q = q.next;
ListNode ret = q.next;
q.next = null;
return ret;
}
}
二叉树的层序遍历⭐
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if(root == null) return ret;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> level = new ArrayList<Integer>();
int currentLevelSize = queue.size();
for(int i = 0; i < currentLevelSize; ++i) {
TreeNode node = queue.poll();
level.add(node.val);
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
ret.add(level);
}
return ret;
}
}
二叉树的中序遍历⭐
⚡ 递归
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
inorder(root, list);
return list;
}
private void inorder (TreeNode node, List<Integer> list) {
if (node == null) return;
inorder (node.left, list);
list.add(node.val);
inorder (node.right, list);
}
}
⚡ 迭代⭐
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
res.add(root.val);
root = root.right;
}
return res;
}
}
二叉树的后序遍历⭐
⚡ 迭代⭐
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == prev) {
list.add(root.val);
prev = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return list;
}
}
二叉树的前序遍历
⚡ 迭代⭐
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
list.add(node.val);
stack.push(node.right);
stack.push(node.left);
}
}
return list;
}
}
3月26日
删除排序链表中的重复元素
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return head;
ListNode q = head;
while(q.next != null) {
if(q.val == q.next.val) {
q.next = q.next.next;
}
else q = q.next;
}
return head;
}
}
3月25日
删除排序链表中的重复元素II⭐
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode p = dummy;
while (p.next != null && p.next.next != null) {
if (p.next.val == p.next.next.val) {
int x = p.next.val;
while (p.next != null && p.next.val == x) {
p.next = p.next.next;
}
}
else {
p = p.next;
}
}
return dummy.next;
}
}
3月24日
132模式⭐
⚡ 单调栈
class Solution {
public boolean find132pattern(int[] nums) {
int n = nums.length;
Stack<Integer> candidateK = new Stack<>();
candidateK.push(nums[n - 1]);
int maxK = Integer.MIN_VALUE;
for (int i = n - 2; i >= 0; --i) {
if (nums[i] < maxK) return true;
while (!candidateK.isEmpty() && nums[i] > candidateK.peek()) {
maxK = candidateK.pop();
}
if (nums[i] > maxK) {
candidateK.push(nums[i]);
}
}
return false;
}
}