Author: liyazhou
Github: li-yazhou
Repo: https://github.com/li-yazhou/algorithm-primer
email: [email protected]
- Leetcode-100
- 0001-两数之和
- 0002-两数相加
- 0003-无重复的最长子串
- 0005-最长回文子串
- 0011-盛最多水的容器
- 0015-三数之和
- 0016-最接近的三数之和
- 0017-电话号码的字母组合
- 0019-删除链表的倒数第N个节点
- 0020-有效的括号
- 0021-合并两个有序链表
- 0022-括号生成
- 0031-下一个排列
- 0033-搜索旋转排序数组
- 0034-在排序数组中查找元素的第一个和最后一个位置
- 0039-组合总和
- 0046-全排列
- 0048-旋转图像
- 0049-字母异位词分组
- 0053-最大子序和
- 0055-跳跃游戏
- 0056-合并区间
- 0062-不同路径
- 0064-最小路径和
- 0070-爬楼梯
- 0075-颜色分类
- 0079-单词搜索
- 0094-二叉树的中序遍历
- 0096-不同的二叉搜索树
- 0098-验证二叉搜索树
- 0101-对称二叉树
- 0102-二叉树的层次遍历
- 0104-二叉树的最大深度
- 0105-从前序与中序遍历序列构造二叉树
- 0110-平衡二叉树
- 0111-二叉树的最小深度
- 0114-二叉树展开为链表
- 0121-买卖股票的最佳时机
- 0124-二叉树的最大路径和
- 0136-只出现一次的数字
- 0139-单词拆分
- 0141-环形链表
- 0142-环形链表II
- 0146-最近最少使用缓存
- 0148-排序链表
- 0152-乘积最大子序列
- 0155-最小栈
- 0160-相交链表
- 0169-求众数
- 0198-打家劫舍
- 0200-岛屿数量
- 0206-反转链表
- 0207-课程表
- 0208-实现前缀树
- 0215-数组中的第K个最大元素
- 0221-最大正方形
- 0226-翻转二叉树
- 0234-回文链表
- 0236-二叉树的最近公共祖先
- 0238-除自身以外数组的乘积
- 0240-搜索二维矩阵 II
- 0257-二叉树根结点到所有叶子结点的路径
- 0279-完全平方数
- 0283-移动零
- 0287-寻找重复数
- 0300-最长的上升子序列
- 0309-最佳买卖股票时机含冷冻期
- 0322-零钱兑换
- 0337-打家劫舍III
- 0338-比特位计数
- 0347-前K个高频元素
- 0394-字符串解码
- 0406-根据身高重建队列
- 0416-分割等和子集
- 0437-路径总和III
- 0438-找到字符串中所有字母异位词
- 0448-找到所有数组中消失的数字
- 0467-汉明距离
- 0494-目标和
- 0538-把二叉搜索树转换为累加树
- 0543-二叉树的直径
- 0560-和为K的子数组
- 0581-最短无序连续子数组
- 0617-合并二叉树
- 0647-回文子串
- Leetcode-Easy
- Leetcode-Medium
- Leetcode-Hard
/**
* @level Easy
* Given an array of integers, return indices of the two numbers such that they add up to a specific target.
* You may assume that each input would have exactly one solution, and you may not use the same element twice.
*
* Example:
* Given nums = [2, 7, 11, 15], target = 9,
* Because nums[0] + nums[1] = 2 + 7 = 9,
* return [0, 1].
*/
public class _0001_TwoSum {
private static class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i ++){
int remainder = target - nums[i];
if(map.containsKey(nums[i]))
return new int[]{map.get(nums[i]), i};
map.put(remainder, i);
}
throw new IllegalArgumentException("no solution.");
}
}
}/**
* @level Medium
* You are given two non-empty linked lists representing two non-negative integers.
* The digits are stored in reverse order and each of their nodes contain a single digit.
* Add the two numbers and return it as a linked list.
*
* You may assume the two numbers do not contain any leading zero, except the number 0 itself.
*
* Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
* Output: 7 -> 0 -> 8
*/
public class _0002_AddTwoNumbers {
private static class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0); // 第二个结点是链表的头结点
int increment = 0;
ListNode currNode = dummyHead;
for (ListNode n1 = l1, n2 = l2; l1 != null || l2 != null;){
int x = l1 != null ? l1.val : 0;
int y = l2 != null ? l2.val : 0;
int result = x + y + increment;
currNode.next = new ListNode(result % 10);
increment = result / 10;
currNode = currNode.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (increment == 1){
currNode.next = new ListNode(1);
}
return dummyHead.next;
}
}
}/**
* @level Medium
* Given a string, find the length of the longest substring without repeating characters.
* Example 1:
* Input: "abcabcbb"
* Output: 3
* Explanation: The answer is "abc", with the length of 3.
*
* Example 2:
* Input: "bbbbb"
* Output: 1
* Explanation: The answer is "b", with the length of 1.
*
* Example 3:
* Input: "pwwkew"
* Output: 3
* Explanation: The answer is "wke", with the length of 3.
* Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
*/
public class _0003_LongestSubstringWithoutRepeatingCharacters {
private static class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLen = 0;
// 字符的最大索引
Map<Character, Integer> chToLatestIndexMap = new HashMap<>();
int start = 0;
for (int end = 0; end < s.length(); end ++) {
char ch = s.charAt(end);
if (chToLatestIndexMap.containsKey(ch)) {
// 若该字符出现在start之前，则start不改变
start = Math.max(start, chToLatestIndexMap.get(ch)+1);
}
chToLatestIndexMap.put(ch, end);
maxLen = Math.max(maxLen, end-start+1);
}
return maxLen;
}
}
}/**
* @level Medium
* Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
* Example 1:
* Input: "babad"
* Output: "bab"
* Note: "aba" is also a valid answer.
*
* Example 2:
* Input: "cbbd"
* Output: "bb"
*/
public class _0005_LongestPalindromicSubstring {
/**
* 方法一，暴力验证所有子串
* 方法二，中心扩展法
*/
private static class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) {
return s;
}
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i ++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i+1);
int len = Math.max(len1, len2);
if (len > end-start+1) {
start = i - (len-1)/2;
end = i + len/2;
}
System.out.println(start + ", " + end);
}
return s.substring(start, end+1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L --;
R ++;
}
return R - L - 1;
}
}
}/**
* @level Medium
* Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai).
* n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).
* Find two lines, which together with x-axis forms a container, such that the container contains the most water.
*
* Note: You may not slant the container and n is at least 2.
*
* The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7].
* In this case, the max area of water (blue section) the container can contain is 49.
*
* Example:
* Input: [1,8,6,2,5,4,8,3,7]
* Output: 49
*/
public class _0011_ContainerWithMostWater {
/**
* 左右双指针
*/
private static class Solution {
public int maxArea(int[] height) {
if (height == null || height.length <= 1) {
return 0;
}
int maxarea = 0;
for (int L = 0, R = height.length-1; L < R;) {
maxarea = Math.max(maxarea, (R - L) * Math.min(height[L], height[R]));
if (height[L] > height[R]) {
R --;
} else {
L ++;
}
}
return maxarea;
}
}
}/**
* @level Medium
* Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0?
* Find all unique triplets in the array which gives the sum of zero.
* Note:
* The solution set must not contain duplicate triplets.
* Example:
* Given array nums = [-1, 0, 1, 2, -1, -4],
* A solution set is:
* [
* [-1, 0, 1],
* [-1, -1, 2]
* ]
*/
public class _0015_3Sum {
/**
* Thought
* 方法一，暴力验证
* 方法二，排序 + 左右双指针
*/
private static class Solution {
/**
* 方法二，排序 + 左右双指针
*/
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length < 3) return result;
Arrays.sort(nums);
for (int i = 0; i < nums.length; i ++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i-1]) continue;
int L = i + 1;
int R = nums.length - 1;
while (L < R) {
int sum = nums[i] + nums[L] + nums[R];
if (sum < 0) {
L ++;
} else if (sum > 0) {
R --;
} else if (sum == 0){ // else 不通过，？？？？？
result.add(Arrays.asList(nums[i], nums[L], nums[R]));
for (; L < R && nums[L] == nums[L+1]; L ++);
for (; L < R && nums[R] == nums[R-1]; R --);
L ++;
R --;
}
}
}
return result;
}
}
}public class _0016_3SumClosest {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int result = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length; i ++) {
int head = i + 1;
int tail = nums.length - 1;
while (head < tail) {
int sum = nums[i] + nums[head] + nums[tail];
if (Math.abs(result - target) > Math.abs(sum - target)) {
result = sum;
}
int diff = sum - target;
if (diff < 0) {
head ++;
} else if (diff > 0){
tail --;
} else if (diff == 0) {
return target;
}
}
}
return result;
}
}public class _0017_LetterCombinationsOfAPhoneNumber {
/**
* Thought
* 回溯法，穷举所有可能
* Challenge
* 组合问题，剪枝操作，消除重复的解
*/
private static class Solution {
private Map<String, String> digitToLetters = initPhone();
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.isEmpty()) {
return result;
}
backtrack(result, "", digits);
return result;
}
private void backtrack(List<String> result, String solution, String nextDigits) {
if (nextDigits.isEmpty()) {
result.add(solution);
return;
} else {
String digit = nextDigits.substring(0, 1);
String letters = digitToLetters.get(digit);
for (char letter : letters.toCharArray()) {
backtrack(result, solution+letter, nextDigits.substring(1));
}
}
}
private Map<String, String> initPhone() {
Map<String, String> digitToLetters = new HashMap<>();
digitToLetters.put("2", "abc");
digitToLetters.put("3", "def");
digitToLetters.put("4", "ghi");
digitToLetters.put("5", "jkl");
digitToLetters.put("6", "mno");
digitToLetters.put("7", "pqrs");
digitToLetters.put("8", "tuv");
digitToLetters.put("9", "wxyz");
return digitToLetters;
}
}
}public class _0019_RemoveNthNodeFromEndOfList {
/**
* Thought
* 方法一，单指针遍历两次，删除第 len - n + 1 个节点
* 方法二，前后指针
*/
private static class Solution {
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode removeNthFromEnd(ListNode head, int n) {
// 本题目的关键
// 边界问题
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
int len = 0;
for (ListNode curr = dummyHead; curr != null; curr = curr.next, len ++);
ListNode prev = dummyHead;
int offset = len - n - 1;
for (; offset > 0; offset --, prev = prev.next);
// 哑结点可以保证每个结点都有前一个结点
prev.next = prev.next.next;
return dummyHead.next;
}
}
}public class _0020_ValidParentheses {
/**
* Thought
* 栈
*/
private static class Solution {
public boolean isValid(String s) {
LinkedList<Character> stack = new LinkedList<>();
for (int i = 0; i < s.length(); i ++) {
char ch = s.charAt(i);
if (ch == '(' || ch == '{' || ch == '[') {
stack.push(ch);
}
if (ch == ')') {
if (stack.isEmpty() || stack.pop() != '(') {
return false;
}
}
if (ch == '}') {
if (stack.isEmpty() || stack.pop() != '{') {
return false;
}
}
if (ch == ']') {
if (stack.isEmpty() || stack.pop() != '[') {
return false;
}
}
}
return stack.isEmpty();
}
}
}public class _0021_MergeTwoSortedLists {
/**
* Thought
* 链表
* 单向链表的标配是头哑结点
* 双向链表的标配是首、尾哑结点
*/
private static class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode prev = dummyHead;
ListNode curr = null;
ListNode p1 = l1;
ListNode p2 = l2;
while (p1 != null && p2 != null) {
if (p1.val <= p2.val) {
curr = new ListNode(p1.val);
p1 = p1.next;
} else {
curr = new ListNode(p2.val);
p2 = p2.next;
}
prev.next = curr;
prev = curr;
}
if (p1 != null) prev.next = p1;
if (p2 != null) prev.next = p2;
return dummyHead.next;
}
public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode currNode = dummyHead;
while (l1 != null && l2 != null){
if (l1.val < l2.val){
currNode.next = l1;
l1 = l1.next;
}else{
currNode.next = l2;
l2 = l2.next;
}
currNode = currNode.next;
}
if (l1 != null) currNode.next = l1;
if (l2 != null) currNode.next = l2;
return dummyHead.next;
}
}
}public class _0022_GenerateParentheses {
/**
* Thought
* 方法三，直接生成满足条件的括号
*/
private class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
int open = 0;
int close = 0;
backTrack(result, "", open, close, n);
return result;
}
private void backTrack(List<String> result, String solution, int open, int close, int n) {
if (solution.length() == n * 2) {
result.add(solution);
return;
}
if (open < n) {
backTrack(result, solution + "(", open+1, close, n);
}
if (close < open) {
backTrack(result, solution + ")", open, close + 1, n);
}
}
}
/**
* Thought
* 方法二，与方法一大致相同，改进了验证括号是否成对的方法
* 对序列全排列
* 验证每一种情况是否满足条件，即括号是否成对
*/
private class Solution2 {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
List<Character> seq = new ArrayList<>();
for (int i = 0; i < n; i ++) {
seq.add('(');
}
for (int i = 0; i < n; i ++) {
seq.add(')');
}
backtrack(result, seq, 0);
return result;
}
private void backtrack(List<String> result, List<Character> seq, int depth) {
System.out.println("depth = " + depth + "\tseq = " + seq);
if (depth == seq.size()) {
String solution = seq.stream()
.map(ch -> ch.toString())
.reduce(String::concat).orElse("");
// String solution = seq.stream()
// .map(ch -> ch.toString())
// .collect(Collectors.joining(""));
boolean isTrue = validatePairs(solution);
System.out.println("solution = " + solution + "\t" + isTrue);
if (isTrue) {
result.add(solution);
}
return;
}
for (int i = depth; i < seq.size(); i ++) {
if (i > 0 && seq.get(i).equals(seq.get(i-1))) {
System.out.print("i = " + i + "\t");
System.out.println("seq = " + seq + "\t continue");
continue;
}
Collections.swap(seq, i, depth);
backtrack(result, seq, depth+1);
Collections.swap(seq, i, depth);
}
}
/**
* 验证括号是否成对
*/
private boolean validatePairs(String solution) {
if (solution == null || solution.isEmpty()) {
return false;
}
int balance = 0;
for (char ch : solution.toCharArray()) {
if (ch == '(') {
balance ++;
} else if (ch == ')'){
balance --;
if (balance < 0) {
return false;
}
}
}
return balance == 0;
}
}
/**
* Thought
* 方法一，
* 对序列全排列
* 验证每一种情况是否满足条件，即括号是否成对
*/
private class Solution1 {
public List<String> generateParenthesis1(int n) {
Set<String> result = new HashSet<>();
List<Character> seq = new ArrayList<>();
for (int i = 0; i < n; i ++) {
seq.add('(');
seq.add(')');
}
int depth = 0;
permute(result, seq, depth);
return new ArrayList<>(result);
}
private void permute(Set<String> result, List<Character> seq, int depth) {
if (depth == seq.size()) {
boolean isTrue = validateParenthesis(seq);
if (isTrue) {
StringBuilder sbuilder = new StringBuilder();
for (Character ch: seq) {
sbuilder.append(ch);
}
result.add(sbuilder.toString());
}
}
for (int i = depth; i < seq.size(); i ++) {
Collections.swap(seq, i, depth);
permute(result, seq, depth+1);
Collections.swap(seq, i, depth);
}
}
private boolean validateParenthesis(List<Character> chars) {
LinkedList<Character> stack = new LinkedList<>();
for (Character ch : chars) {
if (ch == '(') {
stack.push(ch);
} else {
if (stack.isEmpty()) {
return false;
} else {
stack.pop();
}
}
}
return stack.isEmpty();
}
}
/**
* Thought
* 方法一，
* 对序列全排列
* 验证每一种情况是否满足条件，即括号是否成对
*/
private class Solution0 {
public List<String> generateParenthesis0(int n) {
char[] chs = new char[n*2];
for (int i = 0; i < n; i ++){
chs[i] = '(';
chs[n+i] = ')';
}
Set<String> set = new HashSet<>();
permutate(chs, 0, set);
return new ArrayList<String>(set);
}
// 字符串全排列
private void permutate(char[] chs, int start, Set<String> set){
if (start == chs.length){
boolean bool = validate(chs);
if (bool)
set.add(new String(chs));
}
for (int i = start; i < chs.length; i ++){
char temp = chs[start];
chs[start] = chs[i];
chs[i] = temp;
permutate(chs, start+1, set);
temp = chs[start];
chs[start] = chs[i];
chs[i] = temp;
}
}
private boolean validate(char[] chs){
LinkedList<Character> stack = new LinkedList<>();
for (char ch : chs){
if (ch == ')') {
if (stack.isEmpty() || stack.pop() != '(') return false;
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}
}/**
* 1,2,3 → 1,3,2
* 3,2,1 → 1,2,3
* 1,1,5 → 1,5,1
*/
public class _0031_NextPermutation {
/**
* Algorithm
* 从右向左遍历
* 记录max
* 若当前元素nums[k]小于max
* 遍历nums[k~len-1]查找到比nums[k]大的最小元素，并交换两者
* Arrays.sort(nums, k+1, nums.length)
* 若每个元素均不小于max，即序列为逆序DESC，则反转序列或者排序，将序列转换为升序序列
*/
private static class Solution {
public void nextPermutation(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int index = nums.length - 1;
int max = nums[index];
boolean desc = true;
for (int k = nums.length-1; k >= 0; k --) {
int curr = nums[k];
if (curr < max) {
int minHead = max;
int minHeadIndex = index;
for (int i = k+1; i < nums.length; i ++) {
if (nums[i] > nums[k]) {
if (minHead > nums[i]) {
minHead = nums[i];
minHeadIndex = i;
}
}
}
swap(nums, k, minHeadIndex);
Arrays.sort(nums, k+1, nums.length);
desc = false;
break;
}
if (curr > max) {
max = curr;
index = k;
}
}
if (desc) {
Arrays.sort(nums);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}public class _0033_SearchInRotatedSortedArray {
// {4, 5, 6, 7, 8, 9, 0, 1, 2, 3}
public int search(int[] nums, int target) {
if (nums == null || nums.length < 1) {
return -1;
}
int maxIndex = searchMaxIndex(nums);
System.out.println("maxIndex = " + maxIndex);
if (target >= nums[0]) {
return binarySearch(nums, 0, maxIndex, target);
} else {
return binarySearch(nums, maxIndex+1, nums.length-1, target);
}
}
private int binarySearch(int[] nums, int left, int right, int key) {
int L = left, R = right;
while (L <= R) {
int M = (L + R) / 2;
System.out.print("(L, R, M) = (" + L + ", " + R + ", " + M + ")");
System.out.println("(L, R, M) = (" + nums[L] + ", " + nums[R] + ", " + nums[M] + ")");
if (nums[M] == key) {
return M;
} else if (nums[M] > key) {
R = M - 1;
} else if (nums[M] < key) {
L = M + 1;
}
}
return -1;
}
private int searchMaxIndex(int[] nums) {
int L = 0, R = nums.length - 1;
while (L <= R) {
int M = (L + R) / 2;
if (M+1 < nums.length && nums[M] > nums[M+1]) {
return M;
} else {
if (nums[M] > nums[L]) {
L = M + 1;
} else if (nums[M] < nums[L]){
R = M - 1;
} else {
return 0;
}
}
}
return 0;
}
}/**
* Example 1:
* Input: nums = [5,7,7,8,8,10], target = 8
* Output: [3,4]
*
* Example 2:
* Input: nums = [5,7,7,8,8,10], target = 6
* Output: [-1,-1]
*/
public class _0034_FirstAndLastPositionOfElementInSortedArray {
/**
* Thought
* 折半查找
* Challenge
* 边界控制
* Algorithm
* 1. 折半查找target，确定 M，若 M 小于 0 则返回 {-1, -1}
* 2. 在 [L, M) 折半查找 target，确定 L，表示左侧第一个为 target 元素的下标
* 3. 在 (M, R] 折半查找 target，确定 R，表示右侧最后一个为 target 元素的下标
* 4. 返回 [L, R]
*/
private static class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[]{-1, -1};
}
int M = Arrays.binarySearch(nums, target);
if (M < 0) {
return new int[]{-1, -1};
}
// System.out.println("M = " + M);
int L0 = 0;
int R0 = M;
while (L0 <= R0) {
int mid = (L0 + R0) / 2;
if (nums[mid] == target) {
R0 = mid - 1;
} else if (nums[mid] < target){
L0 = mid + 1;
}
}
int L1 = M;
int R1 = nums.length - 1;
while (L1 <= R1) {
int mid = (L1 + R1) / 2;
if (nums[mid] == target) {
L1 = mid + 1;
} else if (nums[mid] > target){
R1 = mid - 1;
}
}
return new int[]{L0, R1};
}
}
}/**
* Example 1:
* Input: candidates = [2,3,6,7], target = 7,
* A solution set is:
* [
* [7],
* [2,2,3]
* ]
*
* Example 2:
* Input: candidates = [2,3,5], target = 8,
* A solution set is:
* [
* [2,2,2,2],
* [2,3,3],
* [3,5]
* ]
*/
public class _0039_CombinationSum {
/**
* Thought
* 回溯法，递归 + 重置状态 + 剪枝
* 减法求解
* 加法求解
*
* Challenge
* 避免重复的解，如 [2, 2, 3] 与 [3, 2, 2] 它们是同一种解
*
* Algorithm
* 1. 对候选项排序；
* 2. 遍历候选项
* 递归结束条件为 target == 0，此时将候选解序列添加到结果集中，并返回；
* 若当前元素大于当前目标值，则跳过；
* 若当前元素比候选解序列中的最后一个元素小，则跳过（为了避免重复解）；
* 将当前元素添加到候选解序列中，将当前目标值减去当前元素，递归；
* 将当前元素冲候选解序列中弹出来；
*/
private static class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return result;
}
// 排序，加上剪枝操作，可以避免重复的解，如 [2, 2, 3] 与 [3, 2, 2]
Arrays.sort(candidates);
backtrack(result, new Stack<>(), candidates, target);
return result;
}
private void backtrack(List<List<Integer>> result,
Stack<Integer> solution,
int[] candidates,
int target) {
if (target == 0) {
result.add(new ArrayList<>(solution));
return;
}
for (int i = 0; i < candidates.length; i ++) {
int element = candidates[i];
// 剪枝操作
// 若当前元素为比target大，则停止递进
// 若当前元素比序列中的最后一个元素小，则停止递进，
// 这种情况是为了避免重复的解，如 [2, 2, 3] 与 [3, 2, 2]
if (element > target
|| (!solution.isEmpty() && element < solution.peek())) {
continue;
}
// 递进
solution.push(element);
backtrack(result, solution, candidates, target-element);
// 恢复状态，恢复到递进前的状态
solution.pop();
}
}
}
}public class _0046_Permutations {
/**
* Thought
* 回溯法
* 递归 + 重置状态 + 剪枝
* execute
* backtrack
* reset
*
* 递归回溯的过程，是一棵树
*
* 全排列是一个基础算法，可以解决"括号生成"、"电话号码的字母组合"等问题
*
* Algorithm
* 全排列
* 固定前i个元素
* 使i+2~n索引对应的元素分别于i+1交换位置，后固定i+1个元素
*/
private static class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
// List<Integer> seq = Arrays.asList(nums);
List<Integer> seq = new ArrayList<>();
for (int num : nums) {
seq.add(num);
}
permute(result, seq, 0);
return result;
}
private void permute(List<List<Integer>> result, List<Integer> seq, Integer depth) {
if (depth == seq.size()) {
result.add(new ArrayList(seq));
return;
}
for (int i = depth; i < seq.size(); i ++) {
Collections.swap(seq, i, depth);
permute(result, seq, depth+1);
Collections.swap(seq, i, depth);
}
}
}
}/**
* Given input matrix =
* [
* [ 5, 1, 9,11],
* [ 2, 4, 8,10],
* [13, 3, 6, 7],
* [15,14,12,16]
* ],
* rotate the input matrix in-place such that it becomes:
* [
* [15,13, 2, 5],
* [14, 3, 4, 1],
* [12, 6, 8, 9],
* [16, 7,10,11]
* ]
*/
public class _0048_RotateImage {
/**
* Thought
* 数组顺时针旋转90度
* Challenge
* 数组下标控制
* Algorithm
* 1. 沿正对角线反转
* 2. 沿竖中轴线对折
*/
private static class Solution {
public void rotate(int[][] matrix) {
if (matrix == null) {
return;
}
for (int i = 0; i < matrix.length; i ++) {
for (int j = 0; j < i; j ++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for (int m = 0; m < matrix.length; m ++) {
for (int n = 0; n < matrix.length/2; n ++) {
int temp = matrix[m][n];
matrix[m][n] = matrix[m][matrix.length-1-n];
matrix[m][matrix.length-1-n] = temp;
}
}
}
private String matrixToString(int[][] matrix) {
StringBuilder toString = new StringBuilder();
for (int[] vector: matrix) {
toString.append(Arrays.toString(vector))
.append(System.lineSeparator());
}
return toString.toString();
}
}
}/**
* Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
* Output:
* [
* ["ate","eat","tea"],
* ["nat","tan"],
* ["bat"]
* ]
*/
public class _0049_GroupAnagrams {
/**
* Thought
* 方法一，直观的方法（笨拙方法）
* 对原字符串排序，并将排序后的字符串作为key，原字符串存放在key对应的List对象中，最终返回Map的values即可
*
* 方法二，善用字母（字符）的方法
* 关于字符，可以巧妙的使用数组作为字典，字符作为下标即key，方便地计算value
*
* 改进key，降低时间复杂度
* 使用数组统计字符串中的每个字符出现的次数；
* 拼接 key，拼接每个字符及出现的次数，使其作为 key，字母异位词的 key 是相同的；
* 使用 Map<String, List<String> 保存字母异位词；
* 返回 Map 的 values 即可
*/
private static class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) {
return Collections.emptyList();
}
Map<String, List<String>> groups = new HashMap<>();
int[] map = new int[26];
for (String str: strs) {
Arrays.fill(map, 0);
for (int i = 0; i < str.length(); i ++) {
char ch = str.charAt(i);
map[ch-'a'] += 1;
}
StringBuilder key = new StringBuilder();
for (int j = 0; j < map.length; j ++) {
char ch = (char)('a' + j);
int count = map[j];
key.append(ch).append(count);
}
String k = key.toString();
if (groups.containsKey(k)) {
List<String> group = groups.get(k);
group.add(str);
} else {
List<String> group = new ArrayList<>();
group.add(str);
groups.put(k, group);
}
}
return new ArrayList<>(groups.values());
}
}
}/**
* Input: [-2,1,-3,4,-1,2,1,-5,4],
* Output: 6
*/
public class _0053_MaximumSubarray {
/**
* Thought
* 动态规划
* 一维DP，每个元素表示截止到当前元素时最大的和
*/
private static class Solution {
public int maxSubArray(int[] nums) {
int energy = 0;
int start = 0;
int end = 0;
int max = nums[0];
for (int i = 0; i < nums.length; i ++) {
if (energy <= 0) {
energy = 0;
start = i;
}
energy += nums[i];
if (max < energy) {
max = energy;
end = i;
}
}
return max;
}
public int maxSubArray0(int[] nums) {
int maxSum = nums[0];
int currSum = 0;
for (int num : nums){
if (currSum < 0) currSum = 0;
currSum += num;
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
}
}
}/**
* Example 1:
* Input: [2,3,1,1,4]
* Output: true
* Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
*
* Example 2:
* Input: [3,2,1,0,4]
* Output: false
* Explanation: You will always arrive at index 3 no matter what. Its maximum
* jump length is 0, which makes it impossible to reach the last index.
*/
public class _0055_JumpGame {
/**
* Thought
* 贪心算法
*/
private static class Solution {
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int pos = nums.length - 1;
for (int i = nums.length-1; i >= 0; i --) {
int furthestPos = i + nums[i];
if (furthestPos >= pos) {
pos = i;
}
}
return pos == 0;
}
}
/**
* Note
* TIMEOUT
* Thought
* 递归回溯法
* Challenge
* 组合出所有可能的解，判断解是否有效
*/
private static class Solution1 {
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
return canJump(nums, 0);
}
private boolean canJump(int[] nums, int position) {
if (position == nums.length-1) {
return true;
}
if (position >= nums.length) {
return false;
}
for (int step = 1; step <= nums[position]; step ++) {
if (canJump(nums, position+step)) {
return true;
}
}
return false;
}
}
/**
* 改编题目
* 查找所有的跳跃路径
*/
private static class JumpPaths {
public List<List<Integer>> jumpPaths(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
paths(result, new Stack<>(), nums, 0);
return result;
}
private void paths(List<List<Integer>> result,
Stack<Integer> steps,
int[] nums,
int position) {
if (position == nums.length-1) {
result.add(new ArrayList<>(steps));
return;
}
for (int step = 1; step <= nums[position]; step ++) {
System.out.println(", step = " + step);
steps.push(step);
paths(result, steps, nums, position+step);
steps.pop();
}
}
}
}/**
* Input: [[1,3],[2,6],[8,10],[15,18]]
* Output: [[1,6],[8,10],[15,18]]
*
* Input: [[1,4],[4,5]]
* Output: [[1,5]]
*/
public class _0056_MergeIntervals {
/**
* Thought
* 排序
* Algorithm
* 1. 排序
* 2. 合并
*/
private static class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return intervals;
}
List<Interval> intervalList = new ArrayList<>();
for (int[] interval: intervals) {
intervalList.add(new Interval(interval));
}
Comparator<Interval> cmp = (intervalA, intervalB) ->
intervalA.start < intervalB.start ? -1 :
(intervalA.start > intervalB.start ? 1 : intervalA.end - intervalB.end);
intervalList.sort(cmp);
List<Interval> result = new ArrayList<>();
Interval merged = intervalList.get(0);
result.add(merged);
for (int i = 0; i < intervalList.size(); i ++) {
Interval curr = intervalList.get(i);
if (curr.start <= merged.end) {
merged.end = Math.max(merged.end, curr.end);
} else {
merged = curr;
result.add(merged);
}
}
int[][] ans = new int[result.size()][2];
for (int i = 0; i < result.size(); i ++) {
ans[i] = result.get(i).toIntArray();
}
return ans;
}
private class Interval {
int start;
int end;
Interval(int start, int end) {
this.start = start;
this.end = end;
}
Interval(int[] range) {
this.start = range[0];
this.end = range[1];
}
int[] toIntArray() {
return new int[]{this.start, this.end};
}
}
}
}/**
* Example 1:
* Input: m = 3, n = 2
* Output: 3
* Explanation:
* From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
* 1. Right -> Right -> Down
* 2. Right -> Down -> Right
* 3. Down -> Right -> Right
*
* Example 2:
* Input: m = 7, n = 3
* Output: 28
*/
public class _0062_UniquePaths {
/**
* Thought
* 一维数组
* Challenge
* 边界控制
* Algorithm
* 1. 一维数组array保存第i行位置的不同路径数，初始化为1；
* 2. 遍历2到m-1行元素，求解当前行各个位置的不同的路径数，
* 当前位置的路径等于左边元素和上边元素之和，更新到一维数组；
* 3. array[n-1] 即是解。
* Complexity
* Time, O(m*n)
* Space, min(O(m), O(n))
*/
private static class Solution {
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}
int[] array = new int[n];
Arrays.fill(array, 1);
for (int i = 1; i < m; i ++) {
for (int j = 1; j < array.length; j ++) {
array[j] = array[j-1] + array[j];
}
}
return array[n-1];
}
}
/**
* Thought
* 二维数组
* Challenge
* 边界控制
* Algorithm
* 1. 初始化"数组"的第0行、第0列，它们的值均为1；
* 2. 非第0行且非第0列的元素均等于它左边和上边元素的之和；
* 3. 第m-1行第n-1列的元素即是解
* Complexity
* Time, O(m*n)
* Space, O(m*n)
*/
private static class Solution1 {
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}
int[][] matrix = new int[m][n];
Arrays.fill(matrix[0], 1);
for (int k = 0; k < matrix.length; k ++) {
matrix[k][0] = 1;
}
for (int i = 1; i < matrix.length; i ++) {
for (int j = 1; j < matrix[0].length; j ++) {
matrix[i][j] = matrix[i][j-1] + matrix[i-1][j];
}
}
return matrix[m-1][n-1];
}
}
}/**
* Input:
* [
* [1,3,1],
* [1,5,1],
* [4,2,1]
* ]
* Output: 7
* Explanation: Because the path 1→3→1→1→1 minimizes the sum.
*/
public class _0064_MinimumPathSum {
/**
* Thought
* 一维动态规划
* 若可以修改原数组，则不需要额外的空间
* Challenge
* 边界控制
* Algorithm
* 1. 一维数组dp保存第i行位置的最小权重；
* 2. 遍历2到m-1行元素，求解当前行各个位置的最小权重，当前位置的最小权重等于左边元素和上边元素之和，更新到一维数组；
* 3. dp[n-1] 即是解。
* Complexity
* Time, O(m*n)
* Space, min(O(m), O(n))
*/
private static class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int row = grid.length;
int column = grid[0].length;
int[] dp = Arrays.copyOf(grid[0], grid[0].length);
// 第一行元素的权重，等于左侧元素的权重 + 当前元素的值
for (int k = 1; k < dp.length; k ++) {
dp[k] += dp[k-1];
}
// System.out.println("dp = " + Arrays.toString(dp));
for (int i = 1; i < row; i ++) {
for (int j = 0; j < column; j ++) {
if (j == 0) {
// 第一列元素的权重，等于上面元素的权重 + 当前元素的值
dp[j] = dp[j] + grid[i][j];
} else {
// 非0行0列的元素的权重，等于min(左侧元素的权重, 上面元素的权重) + 当前元素的权重
dp[j] = Math.min(dp[j-1], dp[j]) + grid[i][j];
}
}
// System.out.println("dp = " + Arrays.toString(dp));
}
return dp[column-1];
}
}
}/**
* Each time you can either climb 1 or 2 steps.
* In how many distinct ways can you climb to the top?
*/
public class _0070_ClimbingStairs {
private static class Solution {
/*
public int climbStairs(int n) {
if (n == 0 || n == 1 || n == 2) {
return n;
} else {
return climbStairs(n-1) + climbStairs(n-2);
}
}
*/
// public int climbStairs(int n) {
// if (n <= 2) return n;
// return climbStairs(n-1) + climbStairs(n-2);
// }
public int climbStairs0(int n) {
if (n <= 2) return n;
int result = 0;
int first = 1;
int second = 2;
for (int i = 3; i <= n; i ++) {
result = first + second;
int temp = first;
first = second;
second = second + temp;
}
return result;
}
}
}/**
* Example:
* Input: [2,0,2,1,1,0]
* Output: [0,0,1,1,2,2]
*/
public class _0075_SortColors {
/**
* Thought
* 方法一，统计0、1、2出现的次数，然后将它们按顺序及出现次数写入到原数组
* 方法二，荷兰国旗问题，使用三个指针处理，本解使用的方法
*
* Challenge
* 指针的使用
* 数组的处理艺术是元素交换，多个指针（下标）作为索引标识元素，然后对它们进行交换操作
* 本题目的关键之处，是找出0与1，1与2的边界
*
* Algorithm
* 1. p0指针指向0元素的右边界（不包括），初始值是0；
* 2. p2指针指向2元素的左边界（不包括），初始值是n-1；
* 3. curr指针小于等于p2遍历数组
* 若当前元素为0，则与p0指向的元素交换位置，并执行p0++, curr++;
* 若当前元素为2，则与p2指向的元素交换位置，并执行p2--；
* （由2换回来的元素可能是1也能是0，因此curr的位置不变）
* 若当前元素为1，则curr++，继续查找0或者2；
*
* Complexity
* Time, O(n)
* Space, O(1)
*/
private static class Solution {
public void sortColors(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int p0 = 0;
int p2 = nums.length - 1;
int curr = 0;
while (curr <= p2) {
if (nums[curr] == 0) {
swap(nums, curr ++, p0 ++);
} else if (nums[curr] == 2) {
swap(nums, curr, p2 --);
} else if (nums[curr] == 1) {
curr ++;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}/**
* Example:
* board =
* [
* ['A','B','C','E'],
* ['S','F','C','S'],
* ['A','D','E','E']
* ]
* Given word = "ABCCED", return true.
* Given word = "SEE", return true.
* Given word = "ABCB", return false.
*/
public class _0079_WordSearch {
/**
* Thought
* 回溯法
* DFS + 重置状态
* Challenge
* 递归回溯条件
* 递归递进条件
*/
private static class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0
|| word == null || word.isEmpty()) {
return false;
}
boolean[][] visited = new boolean[board.length][board[0].length];
int[][] directions = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
/* ********* 每个点都可能是字符串的起点 *********/
for (int i = 0; i < board.length; i ++) {
for (int j = 0; j < board[0].length; j ++) {
if (dfs(visited, directions, i, j, 0, board, word)) {
return true;
}
}
}
return false;
}
/* 递归求解以 i,j 为首元素，是否连续的字符序列等于目标字符串 */
private boolean dfs(boolean[][] visited, int[][] directions,
int i, int j, int start,
char[][] board, String word) {
// if (start >= word.length()) {
// return true;
// }
/* 递归回溯条件 */
if (start == word.length()-1) {
return word.charAt(start) == board[i][j];
}
System.out.println("i = " + i + ", j = " + j + ", start = " + start);
if (board[i][j] == word.charAt(start)) {
visited[i][j] = true;
for (int k = 0; k < directions.length; k ++) {
int nextI= i + directions[k][1];
int nextJ = j + directions[k][0];
/* ********* 递归递进条件 *********/
if (nextI >= 0 && nextI < board.length
&& nextJ >= 0 && nextJ < board[0].length
&& !visited[nextI][nextJ]) {
if (dfs(visited, directions, nextI, nextJ,start+1, board, word)) {
return true;
}
}
}
visited[i][j] = false;
}
return false;
}
}
}/**
* Example:
* Input: [1,null,2,3]
* 1
* \
* 2
* /
* 3
* Output: [1,3,2]
*/
public class _0094_BinaryTreeInorderTraversal {
/**
* Thought
* 莫里斯中序遍历
* 根节点右旋遍历法
* 每一步右旋之后的二叉树的中序遍历结果与原二叉树的中序遍历结果相同
* Challenge
* 指针控制
* Algorithm
* 1. 参数校验，若root为空，则返回空List；
* 2. while (root != null)
* 若根结点存在左孩子结点，则将该左孩子结点作为新的根结点，并将旧根结点作为新根结点的最右孩子结点的右孩子；
* 若根结点不存在左孩子结点，则将当前根结点保存到List中，并将当前结点的右孩子结点作为新的根结点；
* 3. 返回List，即结果集。
*/
private static class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> inorder = new ArrayList<>();
if (root == null) {
return inorder;
}
while (root != null) {
if (root.left != null) {
TreeNode oldRoot = root;
TreeNode right = oldRoot.left;
while (right.right != null) {
right = right.right;
}
right.right = oldRoot;
root = oldRoot.left;
oldRoot.left = null;
} else {
inorder.add(root.val);
root = root.right;
}
}
return inorder;
}
}
/**
* Thought
* 二叉树的中序遍历
* 递归法
* 使用栈
* 莫里斯中序遍历，需要修改树的结构
*
* Algorithm
* 莫里斯中序遍历
* 1. 若当前结点没有左孩子结点，则访问该结点
*/
private static class Solution2 {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> inorder = new ArrayList<>();
if (root == null) {
return inorder;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
inorder.add(curr.val);
curr = curr.right;
}
return inorder;
}
}
/**
* Thought
* 二叉树的中序遍历，递归法
*
* Algorithm
* 1. 若当前结点为空，则返回；
* 2. 若当前结点的左孩子结点为空，则递归递进该孩子结点；
* 3. 访问当前结点；
* 4. 若当前结点的右孩子结点为空，则递归递进该孩子结点
*/
private static class Solution1 {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> inorder = new ArrayList<>();
inorderTraversal(inorder, root);
return inorder;
}
private void inorderTraversal(List<Integer> inorder, TreeNode root) {
if (root == null) {
return;
}
inorderTraversal(inorder, root.left);
inorder.add(root.val);
inorderTraversal(inorder, root.right);
}
}
}/**
* Example:
* Input: 3
* Output: 5
* Explanation:
* Given n = 3, there are a total of 5 unique BST's:
*
* 1 3 3 2 1
* \ / / / \ \
* 3 2 1 1 3 2
* / / \ \
* 2 1 2 3
*/
public class _0096_UniqueBinarySearchTrees {
/**
* Thought
* 卡特兰公式
* Challenge
* 发现规律
* 动态规划
*
* 定义两个函数
* G(n)，表示长度为n的序列可以构造不同的BST的个数
* F(i, n) ，表示以第i个为根，且长度为n的序列可以构造不同的BST的个数，1 <= i <= n
*
* G(n) = F(1, n) + F(2, n) + F(3, n) + ... + F(n, n)
* F(i, n) = G(i-1)*G(n-i)
*
* G(n) = G(0)*G(n-1) + G(1)*G(n-2) + G(2)*G(n-3) + ... + G(n-1)G(0)
*
* G(0) = 1
* G(1) = 1
* G(2) = G(0)*G(1) + G(1)
*/
private static class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i ++) {
for (int j = 1; j <= i; j ++) {
dp[i] += dp[j-1] * dp[i-j];
}
}
return dp[n];
}
}
}/**
* Example 1:
* 2
* / \
* 1 3
* Input: [2,1,3]
* Output: true
*
* Example 2:
* 5
* / \
* 1 4
* / \
* 3 6
* Input: [5,1,4,null,null,3,6]
* Output: false
*/
public class _0098_ValidateBinarySearchTree {
/**
* Thought
* 非递归中序遍历，使用栈
* Algorithm
* 1. 非递归中序遍历
* 比较前一个元素的值pre与当前元素的值curr的大小，若 pre >= curr 则返回false；
* 2. 遍历结束表示没有返回false，则返回true，即当前二叉树是BST。
*/
private static class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
long pre = Long.MIN_VALUE;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
if (curr.val <= pre) {
return false;
}
pre = curr.val;
curr = curr.right;
}
return true;
}
}
/**
* Thought
* 递归
* Challenge
* 交叉传递上下边界
*/
private static class Solution1 {
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
return validateBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean validateBST(TreeNode root, int lower, int upper) {
if (root == null) {
return true;
}
if (root.val <= lower || root.val >= upper) {
return false;
}
return validateBST(root.left, lower, root.val)
&& validateBST(root.right, root.val, upper);
}
}
}/**
* For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
*
* 1
* / \
* 2 2
* / \ / \
* 3 4 4 3
*
*
* But the following [1,2,2,null,3,null,3] is not:
* 1
* / \
* 2 2
* \ \
* 3 3
*/
public class _0101_SymmetricTree {
/**
* Thought
* 递归
*/
private static class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
return left.val == right.val
&& isSymmetric(left.left, right.right)
&& isSymmetric(left.right, right.left);
}
}
}/**
* Given binary tree [3,9,20,null,null,15,7],
* 3
* / \
* 9 20
* / \
* 15 7
*
* return its level order traversal as:
* [
* [3],
* [9,20],
* [15,7]
* ]
*/
public class _0102_BinaryTreeLevelOrderTraversal {
/**
*
* Thought
* 队列
* Challenge
* 使用两个整数表示当前行元素的个数、下一行元素的个数
*/
private static class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int currLevelNum = 1;
int nextLevelNum = 0;
LinkedList<Integer> currLineResult = new LinkedList<>();
while (!queue.isEmpty()) {
TreeNode head = queue.poll();
if (head.left != null) {
queue.offer(head.left);
nextLevelNum ++;
}
if (head.right != null) {
queue.offer(head.right);
nextLevelNum ++;
}
currLineResult.add(head.val);
currLevelNum --;
if (currLevelNum == 0) {
result.add(currLineResult);
currLineResult = new LinkedList<>();
currLevelNum = nextLevelNum;
nextLevelNum = 0;
}
}
return result;
}
}
}public class _0104_MaximumDepthOfBinaryTree {
/**
* Thought
* 二叉树的最大深度
* 方法一，递归
* 方法二，层次遍历
*/
private static class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right)+1;
}
public int maxDepth0(TreeNode root) {
if (root == null) return 0;
int leftDepth = maxDepth(root.left) + 1;
int rightDepth = maxDepth(root.right) + 1;
return leftDepth > rightDepth ? leftDepth : rightDepth;
}
}
}/**
* preorder = [3,9,20,15,7]
* inorder = [9,3,15,20,7]
* Return the following binary tree:
* 3
* / \
* 9 20
* / \
* 15 7
*/
public class _0105_ConstructBinaryTreeFromPreorderAndInorderTraversal {
/**
* Note
*
* Thought
* 根据先序遍历和中序遍历重建二叉树
*
* Challenge
* 确定边界是关键点
*
* Algorithm
* 1. 参数是前序遍历序列以及其起始、终止下标，中序遍历序列以及其起始、终止下标
* 2. 首先，判断起始和终止下标是否越界，如果越界，则返回null，这个null将作为只有一个孩子或者叶子结点的孩子
* 3. 根据前序遍历序列的第一个元素创建当前树的根结点
* 4. 查找根结点在中序遍历序列中的位置，也即是下标
* 5. 假如，中序遍历序列中不存在该根结点，抛出前序遍历和中序遍历序列不匹配的异常
* 6. 根据根结点在前序遍历和后续遍历中的下标，
* 可以计算出根结点的左子树在前序和后序遍历序列中的下标范围，然后递归地创建左子树，并将返回值赋值给它的根结点
* 7. 根据根结点在前序遍历和后续遍历中的下标，可以计算出根结点的右子树在前序和后序遍历序列中的下标范围，
* 然后递归地创建右子树，并将返回值赋值给它的根结点
* 8. 返回二叉树的根结点
*/
private static class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 判断输入数据
if(preorder == null || preorder.length == 0
|| inorder == null || inorder.length == 0) return null;
return constructBinTree(preorder, 0, preorder.length, inorder, 0, preorder.length);
}
/**
* @param preorder 前序遍历序列
* @param preStart 当前树的前序遍历序列的第一个元素的下标
* @param preEnd 当前树的前序遍历序列的最后一个元素的下标+1
* @param inorder 中序遍历序列
* @param inStart 当前树的中序遍历序列的第一个元素的下标
* @param inEnd 当前树的中序遍历序列的最后一个元素的下标+1
* @return 二叉树的根结点
*/
private TreeNode constructBinTree(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
// 递归终止条件，当开始位置大于结束位置时，则没有要处理的数据
if (preStart >= preEnd || inStart >= inEnd) return null;
// null 是只有一个孩子或者叶子结点的孩子
// 从前序遍历序列中取出根结点
int rootId = preorder[preStart];
TreeNode root = new TreeNode(rootId);
// 根结点在中序遍历序列中的位置
int idxOfRoot = -1;
for (int i = inStart; i < inEnd; i++){
if(inorder[i] == rootId){
idxOfRoot = i;
break;
}
}
if (idxOfRoot == -1) {
throw new RuntimeException("先序遍历序列和中序遍历序列不匹配.");
}
// 递归构建当前根结点的左子树，左子树的结点个数是 idxOfRoot-inStart
// 先序遍历序列中，当前根结点的左子树的范围是
// [preStart+1, preStart+(idxOfRoot-inStart)+1)，根据起始位置和偏移量计算范围
// 中序遍历序列中，当前根结点的左子树的范围是 [inStart, idxOfRoot)
root.left = constructBinTree(preorder, preStart+1,
preStart+idxOfRoot-inStart+1, inorder, inStart, idxOfRoot);
// 递归构建当前根结点的右子树，右子树的结点个数是 inEnd-idxOfRoot-1
// 先序遍历序列中，当前结点的右子树的范围是 [preEnd-(inEnd-idxOfRoot-1), preEnd)，
// 根据终止位置和偏移量计算范围
// 中序遍历序列中，当前结点的右子树的范围是 [idxOfRoot+1, inEnd)
root.right = constructBinTree(preorder, preEnd-inEnd+idxOfRoot+1 ,
preEnd, inorder, idxOfRoot+1, inEnd);
return root;
}
}
}/**
* Example 1:
* Given the following tree [3,9,20,null,null,15,7]:
* 3
* / \
* 9 20
* / \
* 15 7
* Return true.
*
* Example 2:
* Given the following tree [1,2,2,3,3,null,null,4,4]:
* 1
* / \
* 2 2
* / \
* 3 3
* / \
* 4 4
* Return false.
*/
public class _0110_BalancedBinaryTree {
/**
* Thought
* 递归
* 算法基础是递归二叉树的深度
*/
private static class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
int l = depth(root.left);
int r = depth(root.right);
if (Math.abs(l-r) > 1) return false;
return isBalanced(root.left) && isBalanced(root.right);
}
private int depth(TreeNode root){
if (root == null) return 0;
int l = depth(root.left);
int r = depth(root.right);
return Math.max(l, r) + 1;
}
}
}/**
* Example:
* Given binary tree [3,9,20,null,null,15,7],
* 3
* / \
* 9 20
* / \
* 15 7
* return its minimum depth = 2.
*/
public class _0111_MinimumDepthOfBinaryTree {
/**
* Thought
* 层次遍历二叉树
* 与递归解二叉树的最大深度的方法不同
*/
private static class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
// if (root.left == null || root.right == null) return 1;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 0;
while (!queue.isEmpty()){
level ++;
int len = queue.size();
for (int i = 0; i < len; i ++){
TreeNode currNode = queue.poll();
if (currNode.left == null && currNode.right == null)
return level;
if (currNode.left != null) queue.offer(currNode.left);
if (currNode.right != null) queue.offer(currNode.right);
}
}
return level;
}
}
}/**
* Given a binary tree, flatten it to a linked list in-place.
* For example, given the following tree:
*
* 1
* / \
* 2 5
* / \ \
* 3 4 6
*
* The flattened tree should look like:
* 1
* \
* 2
* \
* 3
* \
* 4
* \
* 5
* \
* 6
*/
public class _0114_FlattenBinaryTreeToLinkedList {
/**
* Thought
* 二叉树的先序遍历
* Challenge
* 旋转链表
* Algorithm
* 1. 设置curr指向root结点；
* 2. while (curr != null)
* 若curr存在左孩子结点
* 找到其最右孩子结点rightmost；
* 令rightmost指向curr的右孩子结点；
* 令当前结点curr的右孩子指向其左孩子结点；
* 令当前结点curr的左孩子结点为null；
* 令curr指向其右孩子结点；
* 3. 结束。
*/
private static class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
TreeNode curr = root;
while (curr != null) {
if (curr.left != null) {
TreeNode rightmost = curr.left;
while (rightmost.right != null) {
rightmost = rightmost.right;
}
rightmost.right = curr.right;
curr.right = curr.left;
curr.left = null;
}
curr = curr.right;
}
}
}
}/**
* Example 1:
* Input: [7,1,5,3,6,4]
* Output: 5
* Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
* Not 7-1 = 6, as selling price needs to be larger than buying price.
* Example 2:
* Input: [7,6,4,3,1]
* Output: 0
* Explanation: In this case, no transaction is done, i.e. max profit = 0.
*/
public class _0121_BestTimeToBuyAndSellSock {
/**
* Thought
* 方法一，暴力求解
* 方法二，动态规划
*/
private static class Solution {
/**
* 方法二，动态规划
*/
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int profit = 0;
int low = prices[0];
for (int i = 0; i < prices.length; i ++){
low = Math.min(low, prices[i]);
profit = Math.max(profit, prices[i]-low);
}
return profit;
}
/**
* 方法一，暴力求解
*/
public int maxProfit1(int[] prices) {
int maxProfit = 0;
for (int i = 0; i < prices.length; i ++) {
for (int j = i + 1; j < prices.length; j ++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
}
}/**
* @problem Binary Tree Maximum Path Sum
* @level Hard
* Given a non-empty binary tree, find the maximum path sum.
* For this problem, a path is defined as any sequence of nodes from some starting node
* to any node in the tree along the parent-child connections.
* The path must contain at least one node and does not need to go through the root.
* Example 1:
* Input: [1,2,3]
* 1
* / \
* 2 3
* Output: 6
* Example 2:
* Input: [-10,9,20,null,null,15,7]
* -10
* / \
* 9 20
* / \
* 15 7
* Output: 42
*/
public class _0124_BinaryTreeMaximumPathSum {
/**
* Challenge
* 递归返回条件和递归递进条件
*
* Algorithm
* 1. A path from start to end, goes up on the tree for 0 or more steps,
* then goes down for 0 or more steps.
* Once it goes down, it can't go up. Each path has a highest node,
* which is also the lowest common ancestor of all other nodes on the path.
* 2. A recursive method maxPathDown(TreeNode node) (1) computes the maximum path sum
* with highest node is the input node, update maximum if necessary (2) returns
* the maximum sum of the path that can be extended to input node's parent.
*
*/
private static class Solution {
int maxValue = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPathDown(root);
return maxValue;
}
private int maxPathDown(TreeNode root) {
if (root == null) {
return 0;
}
// 当前结点左分支的最大和
int leftSum = Math.max(maxPathDown(root.left), 0);
// 当前结点右分支的最大和
int rightSum = Math.max(maxPathDown(root.right), 0);
maxValue = Math.max(maxValue, root.val+leftSum+rightSum);
return Math.max(leftSum, rightSum) + root.val;
}
}
}/**
* Given a non-empty array of integers, every element appears twice except for one.
* Find that single one.
* Example 1:
* Input: [2,2,1]
* Output: 1
* Example 2:
* Input: [4,1,2,1,2]
* Output: 4
*/
public class _0136_SingleNumber {
/**
* Thought
* 位运算
* 任何整数与0异或均等于它本身；
* 任务整数与它本身异或均等于0；
*
* 位运算——异或运算
* 只有一个1则结果为1，也即是“有1则1”。
*
* 则可以推出：
* 任何整数和0异或结果是它本身。
* 一个整数异或它本身结果等于0。
*
* 可以进一步推出：
* 一个整数异或另一个整数两次结果是它本身。
*/
private static class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int element : nums) {
result ^= element;
}
return result;
}
}
}/**
* Given a non-empty string s and a dictionary wordDict containing a list of
* non-empty words, determine if s can be segmented into a space-separated sequence of
* one or more dictionary words.
*
* The same word in the dictionary may be reused multiple times in the segmentation.
* You may assume the dictionary does not contain duplicate words.
*
* Example 1:
* Input: s = "leetcode", wordDict = ["leet", "code"]
* Output: true
* Explanation: Return true because "leetcode" can be segmented as "leet code".
*
* Example 2:
* Input: s = "applepenapple", wordDict = ["apple", "pen"]
* Output: true
* Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
* Note that you are allowed to reuse a dictionary word.
*
* Example 3:
* Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
* Output: false
*/
public class _0139_WordBreak {
/**
* Thought
* 动态规划
* Algorithm
* 1. 定义两个变量 i 和 j，i 表示由前 i 个字符组成的字符串，j 表示长度为 i 的字符串的一个分割点；
* 2. 定义动态规划的转移状态 boolean[] dp = new int[n+1]，初始状态为 dp[0] = true，表示空字符串在字典中存在；
* 3. 使用两层循环遍历字符串，变量为i和j
* 若 dp[j] 为 true，且s.substring(j, i)在字典中也存在，则 dp[i] 为 true，表示该字符串可以被分拆
* 4. 返回 dp[n]。
*/
private static class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
if (wordDict == null) {
return false;
}
if (s == null || s.length() == 0) {
return true;
}
Set<String> wordDictSet = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for (int i = 1; i <= s.length(); i ++) {
for (int j = 0; j < i; j ++) {
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
/**
* Thought
* 递归法
*/
private static class Solution1 {
public boolean wordBreak(String s, List<String> wordDict) {
if (wordDict == null) {
return false;
}
if (s == null || s.length() == 0) {
return true;
}
return wordBreak(s, new HashSet(wordDict), 0);
}
private boolean wordBreak(String s, Set<String> wordDict, int start) {
if (start == s.length()) {
return true;
}
for (int end = start+1; end <= s.length(); end ++) {
if (wordDict.contains(s.substring(start, end)) && wordBreak(s, wordDict, end)) {
return true;
}
}
return false;
}
}
}public class _0141_LinkedListCycle {
/**
* Thought
* 前后双指针、快慢指针
* Challenge
* 推理结点位置
* Algorithm
* 1. 快慢指针找到环中的一个结点，若不存在环形则返回null。
*/
private static class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode quick = head;
ListNode slow = head;
while (quick != null && slow != null){
if (quick.next != null) quick = quick.next.next;
else return false;
slow = slow.next;
if (quick == slow) return true;
}
return false;
}
public boolean hasCycle1(ListNode head) {
if (head == null) {
return false;
}
ListNode quickPointer = head.next;
ListNode slowPointer = head;
while (slowPointer != null && quickPointer != null) {
if (slowPointer == quickPointer) {
return true;
}
slowPointer = slowPointer.next;
quickPointer = quickPointer.next;
if (quickPointer != null) {
quickPointer = quickPointer.next;
}
}
return false;
}
}
}public class _0142_LinkedListCycleII {
/**
* Thought
* 前后双指针、快慢指针
* Challenge
* 推理结点位置
* Algorithm
* 1. 快慢指针找到环中的一个结点，然后求解该环的长度m，若不存在环形则返回null；
* 2. 前后双指针 p1 和 p2，p1向前移动m步，p1 和 p2 同速移动，直到两者相遇
* （若链表长度为n，则p1向前移动m步后，p1和p2距离环形部分入口长度均为n-m，
* 也即同时同速移动p1和p2两者会相遇在环形入口结点）。
*/
private static class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode quick = head;
ListNode slow = head;
boolean isCycle = false;
while (quick != null && quick.next != null) {
quick = quick.next.next;
slow = slow.next;
if (quick == slow) {
isCycle = true;
break;
}
}
// 不存在环
if (!isCycle) {
return null;
}
// 环形部分的长度
int cycleLen = 1;
for (; slow.next != quick; slow = slow.next, cycleLen ++) ;
ListNode p1 = head;
ListNode p2 = head;
for (int i = 0; i < cycleLen; i ++, p1 = p1.next) ;
for (; p1 != p2; p1 = p1.next, p2 = p2.next) ;
return p2;
}
}
/**
* Thought
* 前后双指针、快慢指针
* Challenge
* 推理结点位置
* Algorithm
* 1. 快慢指针找到环中的一个结点，若不存在环形则返回null；
* 2. 使快慢指针中一个指针再次指向头结点，然后同时移动两个指针，它们再次相遇的结点即是环形的入口结点。
*/
private static class Solution1 {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode quick = head;
ListNode slow = head;
boolean isCycle = false;
while (quick != null && quick.next != null) {
quick = quick.next.next;
slow = slow.next;
if (quick == slow) {
isCycle = true;
break;
}
}
// 不存在环
if (!isCycle) {
return null;
}
slow = head;
while (slow != quick) {
slow = slow.next;
quick = quick.next;
}
return slow;
}
}
}/**
* Example:
* LRUCache cache = new LRUCache(2);
* cache.put(1,1);
* cache.put(2,2);
* cache.get(1); // returns 1
* cache.put(3,3); // evicts key 2
* cache.get(2); // returns -1 (not found)
* cache.put(4,4); // evicts key 1
* cache.get(1); // returns -1 (not found)
* cache.get(3); // returns 3
* cache.get(4); // returns 4
*/
public class _0146_LRUCache {
/**
* Thought
* 双向链表 + HashMap
*/
private static class LRUCache<K, V> {
private int cap = 10;
// value的类型是Node，因为在后面会根据结点获取key，所以不能简单地将value的类型定义为V
private HashMap<K, Node> map; // 保证访问结点的速度为O(1)
private Node head; // 最近插入或者访问的结点
private Node tail; // 最长时间没被访问的结点
private class Node{
K key;
V val;
Node next;
Node prev;
public Node(K key, V val) {
this.key = key;
this.val = val;
}
}
public LRUCache(int cap) {
this.cap = cap;
this.head = new Node(null, null);
this.tail = new Node(null, null);
head.next = tail;
tail.prev = head;
map = new HashMap<>();
}
/**
* 访问一个结点，则将该结点移动到双向链表的头部
*/
public V get(K key){
V val = null;
Node node = map.get(key);
if (node != null){
moveToHead(node);
val = node.val;
}
return val;
}
/**
* 插入或更新一个结点
* 若缓存中存在该结点，则将其移动到头部
* 若缓存中不存在该结点，则将其插入到头部，并判断链表的长度是否达到上限，若超过上限则删除最后一个结点
* @param key 结点的key
* @param val 结点的value
*/
public void put(K key, V val){
boolean exists = map.containsKey(key);
if (exists){ // 当前key已存在，不需要删除考虑删除最后一个元素的情况
Node node = map.get(key);
node.val = val; // val 可能会更新
moveToHead(node);
} else {
if (map.size() >= this.cap){ // 容量达到上限
// 删除最后一个元素
Node deleteNode = this.tail.prev;
deleteNode.prev.next = this.tail;
this.tail.prev = deleteNode.prev;
// 删除map中的索引
map.remove(deleteNode.key);
}
Node newNode = new Node(key, val);
insertToHead(newNode);
map.put(key, newNode);
}
}
/**
* 将当前结点移动到双向链表的第一个位置
* @param node 当前结点
*/
private void moveToHead(Node node) {
// 删除元素
node.prev.next = node.next;
node.next.prev = node.prev;
// 插入元素
this.head.next.prev = node;
node.next = head.next;
node.prev = head;
this.head.next = node;
}
private void insertToHead(Node node) {
this.head.next.prev = node;
node.next = this.head.next;
node.prev = this.head;
this.head.next = node;
}
}
/**
* 非泛型版本的LRU
*/
private static class Solution {
private static class LRUCache {
private int cap;
private HashMap<Integer, Node> map; // 保证访问结点的速度为O(1)
private Node head; // 最近插入或者访问的结点
private Node tail; // 最长时间没被访问的结点
private class Node {
Integer key;
Integer val;
Node next;
Node prev;
public Node(Integer key, Integer val) {
this.key = key;
this.val = val;
}
}
public LRUCache(int cap) {
this.cap = cap;
this.head = new Node(null, null);
this.tail = new Node(null, null);
head.next = tail;
tail.prev = head;
map = new HashMap<>();
}
/**
* 访问一个结点，则将该结点移动到双向链表的头部
*/
public int get(int key) {
int val = -1;
Node node = map.get(key);
if (node != null) {
moveToHead(node);
val = node.val;
}
return val;
}
/**
* 插入或更新一个结点
* 若缓存中存在该结点，则将其移动到头部
* 若缓存中不存在该结点，则将其插入到头部，并判断链表的长度是否达到上限，
* 若超过上限则删除最后一个结点
*
* @param key 结点的key
* @param val 结点的value
*/
public void put(int key, int val) {
boolean exists = map.containsKey(key);
if (exists) { // 当前key已存在，不需要删除考虑删除最后一个元素的情况
Node node = map.get(key);
node.val = val; // val 可能会更新
moveToHead(node);
} else {
if (map.size() >= this.cap) { // 容量达到上限
// 删除最后一个元素
Node deleteNode = this.tail.prev;
deleteNode.prev.next = this.tail;
this.tail.prev = deleteNode.prev;
// 删除map中的索引
map.remove(deleteNode.key);
}
Node newNode = new Node(key, val);
insertToHead(newNode);
map.put(key, newNode);
}
}
/**
* 将当前结点移动到双向链表的第一个位置
*/
private void moveToHead(Node node) {
// 删除元素
node.prev.next = node.next;
node.next.prev = node.prev;
// 插入元素
this.head.next.prev = node;
node.next = head.next;
node.prev = head;
this.head.next = node;
}
private void insertToHead(Node node) {
this.head.next.prev = node;
node.next = this.head.next;
node.prev = this.head;
this.head.next = node;
}
}
}
/**
* LinkedHashMap
*/
private static class Solution2 {
private static class LRUCache {
private int capacity;
private LinkedHashMap<Integer, Integer> lrcCache;
public LRUCache(int capacity) {
this.capacity = capacity;
lrcCache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return this.size() > capacity;
}
};
}
public int get(int key) {
if (lrcCache.containsKey(key)) {
return lrcCache.get(key);
}
return -1;
}
public void put(int key, int value) {
this.lrcCache.put(key, value);
}
}
}
}/**
* Sort a linked list in O(n log n) time using constant space complexity.
* Example 1:
* Input: 4->2->1->3
* Output: 1->2->3->4
* Example 2:
* Input: -1->5->3->4->0
* Output: -1->0->3->4->5
*/
public class _0148_SortList {
/**
* Thought
* 链表归并排序
* 链表快速排序
* Challenge
* 递归
* Algorithm
* 1. 使用快慢指针将字符串切分为两半
* 2. 左右两部分分别排序
* 3. 合并排序结果
*/
private static class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// step1 使用快慢指针将字符串切分为两半
ListNode slow = head;
ListNode fast = head;
ListNode prev = null;
while (fast != null && fast.next != null) {
prev = slow;
fast = fast.next.next;
slow = slow.next;
}
prev.next = null;
// step2 左右两部分分别排序
ListNode left = sortList(head);
ListNode right = sortList(slow);
// step3 合并排序结果
return merge(left, right);
}
private ListNode merge(ListNode left, ListNode right) {
ListNode head = new ListNode(-1);
ListNode curr = head;
while (left != null && right != null) {
if (left.val <= right.val) {
curr.next = left;
left = left.next;
} else {
curr.next = right;
right = right.next;
}
curr = curr.next;
}
if (left != null) {
curr.next = left;
}
if (right != null) {
curr.next = right;
}
return head.next;
}
}
}/**
* Given an integer array nums, find the contiguous subarray within an array
* (containing at least one number) which has the largest product.
*
* Example 1:
* Input: [2,3,-2,4]
* Output: 6
* Explanation: [2,3] has the largest product 6.
*
* Example 2:
* Input: [-2,0,-1]
* Output: 0
* Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
*/
public class _0152_MaximumProductSubarray {
/**
* Thought
* 对比53题--连续子串最大和
* 动态规划
*
* Complexity
* Time, O(n)
* Space, O(1)
*/
private static class Solution {
public int maxProduct(int[] nums) {
int max = nums[0];
int imax = nums[0]; // 当前的最大值
int imin = nums[0]; // 当前的最小值
for (int i = 1; i < nums.length; i ++) {
if (nums[i] < 0) {
int temp = imax;
imax = imin;
imin = temp;
}
imax = Math.max(imax*nums[i], nums[i]);
imin = Math.min(imin*nums[i], nums[i]);
max = Math.max(max, imax);
}
return max;
}
}
/**
* Thought
* 动态规划
*
* Complexity
* Time, O(n)
* Space, O(n)
*/
private static class Solution1 {
private class Tuple {
int imax;
int imin;
public Tuple (int imax, int imin) {
this.imax = imax;
this.imin = imin;
}
}
public int maxProduct(int[] nums) {
Tuple[] dp = new Tuple[nums.length];
dp[0] = new Tuple(nums[0], nums[0]);
int max = nums[0];
for (int i = 1; i < nums.length; i ++) {
Tuple prev = dp[i-1];
int imax = Math.max(Math.max(nums[i], nums[i] * prev.imax), nums[i] * prev.imin);
int imin = Math.min(Math.min(nums[i], nums[i] * prev.imin), nums[i] * prev.imax);
dp[i] = new Tuple(imax, imin);
max = Math.max(max, imax);
}
return max;
}
}
}/**
* push(x) -- Push element x onto stack.
* pop() -- Removes the element on top of the stack.
* top() -- Get the top element.
* getMin() -- Retrieve the minimum element in the stack.
*/
public class _0155_MinStack {
/**
* Thought
* 方法一，暴力法
* 方法二，双栈
*/
private static class Solution {
class MinStack {
LinkedList<Integer> stack = null;
LinkedList<Integer> minStack = null;
/** initialize your data structure here. */
public MinStack() {
stack = new LinkedList<>();
minStack = new LinkedList<>();
}
public void push(int x) {
stack.push(x);
if (minStack.isEmpty()) {
minStack.push(x);
} else {
int min = Math.min(minStack.peek(), x);
minStack.push(min);
}
}
public void pop() {
if (stack.isEmpty()) {
throw new RuntimeException("stack is empty, pop is illegal.");
}
minStack.pop();
stack.pop();
}
public int top() {
if (stack.isEmpty()) {
throw new RuntimeException("stack is empty, top is illegal.");
}
return stack.peek();
}
public int getMin() {
if (minStack.isEmpty()) {
throw new RuntimeException("stack is empty, getMin is illegal.");
}
return minStack.peek();
}
}
}
private static class Solution1 {
class MinStack {
private LinkedList<Integer> dataStack = null;
private LinkedList<Integer> minStack = null;
/** initialize your data structure here. */
public MinStack() {
dataStack = new LinkedList<>();
minStack = new LinkedList<>();
}
public void push(int x) {
dataStack.push(x);
if (minStack.isEmpty()) minStack.push(x);
else minStack.push(Math.min(minStack.peek(), x));
}
public void pop() {
if(!minStack.isEmpty()) minStack.pop();
if(!dataStack.isEmpty()) dataStack.pop();
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
}
}/**
* Write a program to find the node at which the intersection of two singly linked lists begins.
* For example, the following two linked lists:
* A: a1 → a2
* ↘
* c1 → c2 → c3
* ↗
* B: b1 → b2 → b3
* begin to intersect at node c1.
* Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
* Output: Reference of the node with value = 8
*/
public class _0160_IntersectionOfTwoLinkedLists {
/**
* Thought
* 链表的双指针应用。
* 参考，一个链表的倒数第K个结点。
* 计算两条链表的长度；
* 使用两个指针“右对齐”两个链表；
* 查找相同的结点。
*/
private static class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = length(headA);
int lenB = length(headB);
if (lenA > lenB) {
int diff = lenA - lenB;
for (; diff > 0; diff --, headA = headA.next);
}
if (lenA < lenB) {
int diff = lenB - lenA;
for (; diff > 0; diff --, headB = headB.next);
}
for (; headA != headB; headA = headA.next, headB = headB.next);
return headA;
}
private int length(ListNode head) {
int length = 0;
for (; head != null; head = head.next, length ++);
return length;
}
}
}/**
* Example 1:
* Input: [3,2,3]
* Output: 3
*
* Example 2:
* Input: [2,2,1,1,1,2,2]
* Output: 2
*/
public class _0169_MajorityElement {
private static class Solution {
/* 摩尔投票法 */
public int majorityElement(int[] nums) {
int result = nums[0];
int count = 0;
for (int i = 0; i < nums.length; i ++) {
if (result == nums[i]) count ++;
else count --;
if (count == 0) result = nums[i+1];
}
return result;
}
public int majorityElement2(int[] nums) {
int counter = 0;
int curr = nums[0];
for (int i = 0; i < nums.length; i ++){
if (counter == 0) curr = nums[i];
if (nums[i] == curr) counter ++;
else{
counter --;
if (counter <= 0) counter = 0;
}
}
return curr;
}
// 哈希表
public int majorityElement1(int[] nums) {
Integer result = null;
int majorityNum = nums.length/2;
Map<Integer, Integer> map = new HashMap<>();
for (int element : nums) {
Integer count = map.get(element);
if (count == null) count = 1;
else count = count + 1;
if (count > majorityNum) {
result = element;
break;
}
map.put(element, count);
}
return result;
}
}
}/**
* You are a professional robber planning to rob houses along a street.
* Each house has a certain amount of money stashed,
* the only constraint stopping you from robbing each of them is that adjacent houses
* have security system connected and it will automatically contact the police
* if two adjacent houses were broken into on the same night.
*
* Given a list of non-negative integers representing the amount of money of each house,
* determine the maximum amount of money you can rob tonight without alerting the police.
*
* Example 1:
* Input: [1,2,3,1]
* Output: 4
* Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
* Total amount you can rob = 1 + 3 = 4.
*
* Example 2:
* Input: [2,7,9,3,1]
* Output: 12
* Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
* Total amount you can rob = 2 + 9 + 1 = 12.
*/
public class _0198_HouseRobber {
private static class Solution {
public int rob0(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
} else if (nums.length == 1) {
return Math.max(nums[0], nums[1]);
}
int first = nums[0];
int second = Math.max(nums[0], nums[1]);
int rob = Math.max(first, second);
for (int i = 2; i < nums.length; i ++) {
rob = Math.max(second, first+nums[i]);
first = second;
second = rob;
}
return rob;
}
/**
* 两种状态，抢或不抢，使用列长为2的二维数组表示。
*/
public int rob1(int[] nums) {
int[][] dp = new int[nums.length+1][2];
// dp[i][1] means we rob the current house and dp[i][0] means we don't,
for (int i = 1; i < dp.length; i ++){
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]); // 不抢
dp[i][1] = dp[i-1][0] + nums[i-1]; // 抢
}
return Math.max(dp[nums.length][0], dp[nums.length][1]);
}
}
}/**
* Example 1:
* Input:
* 11110
* 11010
* 11000
* 00000
* Output: 1
*
* Example 2:
* Input:
* 11000
* 11000
* 00100
* 00011
* Output: 3
*/
public class _0200_NumberOfIslands {
/**
* Thought
* 递归 + 标记
* Challenge
* 递归
* Algorithm
* 1. 遍历二维数组中的每一个元素
* 若当前元素是'1'
* 将计数器加1
* 以该元素为入口DFS二维数组
* 若下标超出边界或者当前元素值为 '0'，则退出DFS
* 将当前元素设置为已访问过，即元素值置为 '0'
* 向当前元素的四个方向DFS
*/
private static class Solution {
public int numIslands(char[][] grid) {
int count = 0;
if (grid == null || grid.length == 0) {
return count;
}
int r = grid.length;
int c = grid[0].length;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (grid[i][j] == '1') {
count++;
dfsMarking(grid, i, j);
}
}
}
return count;
}
private void dfsMarking(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
dfsMarking(grid, i - 1, j);
dfsMarking(grid, i + 1, j);
dfsMarking(grid, i, j - 1);
dfsMarking(grid, i, j + 1);
}
}
}public class _0206_ReverseLinkedList {
private static class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode tmpNode = curr.next;
curr.next = prev;
prev = curr;
curr = tmpNode;
}
return prev;
}
public ListNode reverseList1(ListNode head) {
if (head == null || head.next == null) return head;
ListNode first = head;
first.next = null;
ListNode second = head.next;
while (second != null){
ListNode tempNode = second.next;
second.next = first;
first = second;
second = tempNode;
}
return first;
}
}
}/**
* There are a total of n courses you have to take, labeled from 0 to n-1.
*
* Some courses may have prerequisites, for example to take course 0
* you have to first take course 1, which is expressed as a pair: [0,1]
*
* Given the total number of courses and a list of prerequisite pairs,
* is it possible for you to finish all courses?
*
* Example 1:
* Input: 2, [[1,0]]
* Output: true
* Explanation: There are a total of 2 courses to take.
* To take course 1 you should have finished course 0. So it is possible.
*
* Example 2:
* Input: 2, [[1,0],[0,1]]
* Output: false
* Explanation: There are a total of 2 courses to take.
* To take course 1 you should have finished course 0, and to take course 0 you should
* also have finished course 1. So it is impossible.
*
* Note:
* The input prerequisites is a graph represented by a list of edges, not adjacency matrices.
* Read more about how a graph is represented.
* You may assume that there are no duplicate edges in the input prerequisites.
*/
public class _0207_CourseSchedule {
/**
* Thought
* 拓扑排序
* 拓扑顺序验证
*
* Challenge
* 入度、出度计算
* 程序实现
* 优化Solution1，避免重复遍历
*
* Algorithm
* 1. 初始化0~n-1每个元素的入度，设置满足条件的元素个数count为0，及入度为0的Queue；
* 2. 遍历入度数组，
* 若当前元素的入度为0
* 将其加入到Queue
* 3. 循环访问Queue，直到其为空
* 取出第一个元素
* count ++
* 将其出度元素的入度减1，若入度为0，则将其加入到Queue
* 4. 返回 count == numCourses
*/
private static class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 建立标记两点之间是否存在有向边的索引
int[][] matrix = new int[numCourses][numCourses];
// 初始化每个元素的入度
int[] inDegrees = new int[numCourses];
for (int[] edge: prerequisites) {
inDegrees[edge[1]] ++;
matrix[edge[0]][edge[1]] = 1;
}
int count = 0;
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < inDegrees.length; i ++) {
if (inDegrees[i] == 0) {
queue.offer(i);
}
}
if (queue.isEmpty()) {
return false;
}
while (!queue.isEmpty()) {
int element = queue.poll();
count ++;
// 查找以该元素为起始点的有向边，并将它们的入度减1
for (int i = 0; i < numCourses; i ++) {
if (matrix[element][i] == 1) {
inDegrees[i] --; // 可能为负整数
if (inDegrees[i] == 0) {
queue.offer(i);
}
}
}
}
return count == numCourses;
}
}
private static class Solution1 {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 初始化每个元素的入度
int[] inDegrees = new int[numCourses];
for (int[] edge: prerequisites) {
inDegrees[edge[1]] ++;
}
int count = 0;
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < inDegrees.length; i ++) {
if (inDegrees[i] == 0) {
queue.offer(i);
}
}
if (queue.isEmpty()) {
return false;
}
while (!queue.isEmpty()) {
int element = queue.poll();
count ++;
// 查找以该元素为起始点的有向边，并将它们的入度减1
for (int[] edge: prerequisites) {
if (edge[0] == element) {
inDegrees[edge[1]]--;
if (inDegrees[edge[1]] == 0) {
queue.offer(edge[1]);
}
}
}
}
return count == numCourses;
}
}
}/**
* Implement a trie with insert, search, and startsWith methods.
* Example:
* Trie trie = new Trie();
* trie.insert("apple");
* trie.search("apple"); // returns true
* trie.search("app"); // returns false
* trie.startsWith("app"); // returns true
* trie.insert("app");
* trie.search("app"); // returns true
*
* Note:
* You may assume that all inputs are consist of lowercase letters a-z.
* All inputs are guaranteed to be non-empty strings.
* </pre>
*/
public class _0208_ImplementTrie {
/**
* Thought
* 多路查找树
* Challenge
* 下标控制
* 代码实现
*/
private static class Solution {
static class TrieNode {
char val;
boolean isWord;
TrieNode[] children = new TrieNode[26];
TrieNode() {}
TrieNode(char ch) {
this.val = ch;
}
TrieNode(char ch, boolean isWord) {
this.val = ch;
this.isWord = isWord;
}
}
static class Trie {
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
// 根节点指向26个字母
root = new TrieNode(' ');
}
/** Inserts a word into the trie. */
public void insert(String word) {
if (word == null || word.length() == 0) {
return;
}
TrieNode curr = root;
for (int i = 0; i < word.length(); i ++) {
char ch = word.charAt(i);
if (curr.children[ch-'a'] == null) {
curr.children[ch-'a'] = new TrieNode(ch);
}
curr = curr.children[ch-'a'];
}
curr.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
if (word == null || word.length() == 0) {
return true;
}
TrieNode curr = root;
for (char ch: word.toCharArray()) {
// System.out.println("ch = " + ch);
if (curr.children[ch-'a'] == null) {
return false;
}
curr = curr.children[ch-'a'];
}
return curr.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
if (prefix == null || prefix.length() == 0) {
return true;
}
TrieNode curr = root;
for (char ch: prefix.toCharArray()) {
// System.out.println(ch);
if (curr.children[ch-'a'] == null) {
return false;
}
curr = curr.children[ch-'a'];
}
return true;
}
}
}
}/**
* Find the kth largest element in an unsorted array.
* Note that it is the kth largest element in the sorted order,
* not the kth distinct element.
*
* Example 1:
* Input: [3,2,1,5,6,4] and k = 2
* Output: 5
*
* Example 2:
* Input: [3,2,3,1,2,4,5,5,6] and k = 4
* Output: 4
*
* Note:
* You may assume k is always valid, 1 ≤ k ≤ array's length.
*/
public class _0215_KthLargestElementInAnArray {
/**
* Thought
* 方法一，排序，取倒数第 n-k 个元素
* 方法二，小根堆
* 方法三，快排改进方法
*/
private static class Solution {
public int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int low = 0;
int high = nums.length - 1;
while (low < high) {
int pos = partition(nums, low, high);
if (pos < k) {
low = pos + 1;
} else if (pos > k) {
high = pos - 1;
} else {
break;
}
}
return nums[k];
}
private int partition(int[] nums, int low, int high) {
int key = nums[low];
while (low < high) {
for (; low < high && nums[high] > key; high --);
if (low < high) {
nums[low] = nums[high];
low ++;
}
for (; low < high && nums[low] < key; low ++);
if (low < high) {
nums[high] = nums[low];
high --;
}
}
nums[low] = key;
return low;
}
}
private static class Solution1 {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minRootHeap = new PriorityQueue<>();
// PriorityQueue<Integer> minRootHeap = new PriorityQueue<>(Comparator.reverseOrder());
for (int i = 0; i < k; i ++) {
minRootHeap.offer(nums[i]);
}
for (int j = k; j < nums.length; j ++) {
if (nums[j] > minRootHeap.peek()) {
minRootHeap.poll();
minRootHeap.offer(nums[j]);
}
}
return minRootHeap.peek();
}
}
}/**
* Given a 2D binary matrix filled with 0's and 1's,
* find the largest square containing only 1's and return its area.
* Example:
* Input:
* 1 0 1 0 0
* 1 0 1 1 1
* 1 1 1 1 1
* 1 0 0 1 0
* Output: 4
*/
public class _0221_MaximalSquare {
/**
* Thought
* 方法一，暴力法
* 遍历以 matrix[i][j]为右下角元素、由'1'构成的正方形，求最大边长
* 时间复杂度为 O((mn)^2)
*
* 方法二，动态规划
* dp[i+1][j+1] 表示以 matrix[i][j] 为右下角元素的正方形的最大边长
* 若 matrix[i][j] == '1'，则 dp[i+1][j+1] 为其左上角、左侧、上面元素的最小值加1，
* 即dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1;
*/
private static class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
// dp[i+1][j+1] 表示以 matrix[i][j]为右下角元素的正方形的最大边长
int[][] dp = new int[matrix.length+1][matrix[0].length+1];
int max = 0;
for (int i = 1; i <= matrix.length; i ++) {
for (int j = 1; j <= matrix[0].length; j ++) {
if (matrix[i-1][j-1] == '1') {
dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1;
max = Math.max(max, dp[i][j]);
}
}
}
return max * max;
}
}
}/**
* Input:
* 4
* / \
* 2 7
* / \ / \
* 1 3 6 9
* Output:
* 4
* / \
* 7 2
* / \ / \
* 9 6 3 1
*/
public class _0226_InvertBinaryTree {
/**
* Thought
* 递归
*/
private static class Solution {
public TreeNode invertTree(TreeNode root) {
if (root != null) {
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
}
return root;
}
}
}/**
* Example 1:
* Input: 1->2
* Output: false
*
* Example 2:
* Input: 1->2->2->1
* Output: true
*/
public class _0234_PalindromeLinkedList {
/**
* Thought
* 双指针找到链表的中间结点；
* 反转链表的后半部分；
* 比较链表的前半部分和“后半部分”。
*/
private static class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
// slow 是链表后半截的头指针
if (fast != null) slow = slow.next;
ListNode head1 = head;
ListNode head2 = reverseList(slow); // 反转链表的后半截
while (head1 != null && head2 != null){
if (head1.val != head2.val) return false;
head1 = head1.next;
head2 = head2.next;
}
return true;
}
// 反转链表
private ListNode reverseList(ListNode head){
if (head == null || head.next == null) return head;
ListNode first = head;
ListNode second = head.next;
first.next = null; // 表示链表末尾
while (second != null){
ListNode tempNode = second.next;
second.next = first;
first = second;
second = tempNode;
}
return first;
}
}
private static class Solution1 {
public boolean isPalindrome(ListNode head) {
int len = len(head);
int half = len - len/2;
ListNode halfHead = head;
for (; half > 0; halfHead = halfHead.next, half --);
ListNode newHead = reverse(halfHead);
while (newHead != null) {
if (newHead.val != head.val) {
return false;
}
newHead = newHead.next;
head = head.next;
}
return true;
}
int len(ListNode head) {
int len = 0;
for (; head != null; head = head.next, len++);
return len;
}
ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode prev = head;
ListNode curr = head.next;
head.next = null;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
}
}/**
* Given a binary tree, find the lowest common ancestor (LCA)
* of two given nodes in the tree.
*
* Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
* 3
* / \
* 5 1
* / \ / \
* 6 2 0 8
* / |
* 7 4
* Example 1:
* Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
* Output: 3
* Explanation: The LCA of nodes 5 and 1 is 3.
*
* Example 2:
* Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
* Output: 5
* Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
*/
public class _0236_LowestCommonAncestorOfABinaryTree {
/**
* Thought
* 转化问题为，查找两条链表中最后一个相同的结点
* Challenge
* 查找树中两个结点之间的路径
* Algorithm
* 1. 分别查找根节点到两个结点之间的路径；
* 2. 查找两路径中最后一个相同的结点；
*/
private static class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> p1 = new ArrayList<>();
List<TreeNode> p2 = new ArrayList<>();
nodeToNodePath(root, p, p1);
nodeToNodePath(root, q, p2);
int i = 1;
for (; i < p1.size() && i < p2.size(); i ++) {
// 存在不相同的结点
if (p1.get(i-1) == p2.get(i-1) && p1.get(i) != p2.get(i)) {
return p1.get(i - 1);
}
}
// 不存在不同的结点，两个链表长度不等
if (i == p1.size() || i == p2.size()) {
if (p1.get(i-1) == p2.get(i-1)) {
return p1.get(i-1);
}
}
return null;
}
private boolean nodeToNodePath(TreeNode start, TreeNode end, List<TreeNode> path) {
path.add(start);
if (start == end) {
return true;
}
boolean found = false;
if (start != null) {
found = nodeToNodePath(start.left, end, path) || nodeToNodePath(start.right, end, path);
}
if (!found) {
path.remove(path.size()-1);
}
return found;
}
}
}/**
* Given an array nums of n integers where n > 1,
* return an array output such that output[i] is equal to
* the product of all the elements of nums except nums[i].
*
* Example:
* Input: [1,2,3,4]
* Output: [24,12,8,6]
*/
public class _0238_ProductOfArrayExceptSelf {
/**
* Thought
* 动态规划，从左右两边做动态规划
* result[i] = L * R；
*
* L0 = 1
* Li = 1 * nums[0] * nums[1] * … * nums[i-1]
*
* R0 = 1
* Rk = 1 * nums[n-1] * nums[n-2] * … * nums[k+1]
*
* Algorithm
* 1. int[] result = new int[nums.length]；
* 2. 从左遍历，result[i] = Li；
* 3. 从右遍历，result[i] *= Ri；
* 4. return result。
*/
private static class Solution {
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int[] result = new int[nums.length];
int L = 1;
for (int i = 0; i < nums.length; i ++) {
result[i] = L;
L *= nums[i];
}
int R = 1;
for (int k = nums.length-1; k >= 0; k --) {
result[k] *= R;
R *= nums[k];
}
return result;
}
}
}/**
* Write an efficient algorithm that searches for a value in an m x n matrix.
* This matrix has the following properties:
*
* Integers in each row are sorted in ascending from left to right.
* Integers in each column are sorted in ascending from top to bottom.
*
* Example:
* Consider the following matrix:
* [
* [1, 4, 7, 11, 15],
* [2, 5, 8, 12, 19],
* [3, 6, 9, 16, 22],
* [10, 13, 14, 17, 24],
* [18, 21, 23, 26, 30]
* ]
* Given target = 5, return true.
* Given target = 20, return false.
*/
public class _0240_SearchA2DMatrixII {
/**
* Thought
* 方法一、暴力法，时间复杂度为 O(m*n)；
* 方法二、沿着对角线遍历，M[i][i] 是左上角最的元素，该方法需要特别处理 m > n 和 m < n 的情况；
* 方法三、二维数组的行指针、列指针，双指针，时间复杂度是 O(m+n)；
*
* Algorithm
* 方法三，行列指针
* 1. 行、列指针的初始值分别为 m-1、0，即R = m - 1，C = 0；
* 2. while (R >= 0 && C < n)
* 比较 M[R][C] 与 T 的大小
* 若 M[R][C] == T 则返回 true
* 若 M[R][C] > T 则 R --
* 若 M[R][C] < T 则 C ++
* 3. 返回 false，表示在二维数组中没有找到目标元素
*/
private static class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int R = matrix.length - 1;
int C = 0;
while (R >= 0 && C < matrix[0].length) {
int curr = matrix[R][C];
if (curr > target) {
R --;
} else if (curr < target){
C ++;
} else {
return true;
}
}
return false;
}
}
}/**
* 题目：
* Given a binary tree, return all root-to-leaf paths.
* For example, given the following binary tree:
* 1
* / \
* 2 3
* \
* 5
* All root-to-leaf paths are: ["1->2->5", "1->3"]
*/
public class _0257_BinaryTreePaths {
private static class BinTreeNode{
int value;
BinTreeNode left;
BinTreeNode right;
public BinTreeNode (int _value){ value = _value; }
public void setChildren(BinTreeNode _left, BinTreeNode _right){
left = _left;
right = _right;
}
}
public List<String> binaryTreePaths(BinTreeNode root){
List<String> paths = new LinkedList<>();
if (root == null) return paths; // if root == null, return []
String path = "";
binaryTreePaths(root, paths, path);
return paths;
}
private void binaryTreePaths(BinTreeNode root, List<String> paths, String path) {
if (root == null) return;
if ("".equals(path)) path += root.value;
else path += "->" + root.value;
if (root.left == null && root.right == null){
paths.add(path);
return;
}
binaryTreePaths(root.left, paths, path);
binaryTreePaths(root.right, paths, path);
}
}/**
* Given a positive integer n, find the least number of perfect square numbers
* (for example, 1, 4, 9, 16, ...) which sum to n.
*
* Example 1:
* Input: n = 12
* Output: 3
* Explanation: 12 = 4 + 4 + 4.
*
* Example 2:
* Input: n = 13
* Output: 2
* Explanation: 13 = 4 + 9.
*/
public class _0279_PerfectSquares {
/**
* Thought
* 回溯法
* 13
* / | \
* 12 9 4
* / | \ / | \ / \
* 11 8 3 8 5 0 3 0
* /|\
* ……
*
* 求二叉树的最小深度，它的最大深度等于n。
*/
private static class Solution {
public int numSquares(int n) {
int[] memo = new int[n+1]; // 默认初始化为0
for (int i = 1; i <= n; i ++ ) {
memo[i] = i; // 最坏的情况是每次 +1
for (int j = 1; j * j <= i; j ++) {
memo[i] = Math.min(memo[i - j * j] + 1, memo[i]); // 动态转移方程
}
}
return memo[n];
}
}
private static class Solution2 {
public int numSquares(int n) {
int[] memo = new int[n+1];
int result = numSquares(n, memo);
return result;
}
private int numSquares(int n, int[] memo) {
if (memo[n] != 0) {
return memo[n];
}
int sqrt = (int) Math.sqrt(n);
if (sqrt * sqrt == n) {
memo[n] = 1;
return memo[n];
}
int depth = Integer.MAX_VALUE;
for (int i = 1; i * i < n; i ++) {
depth = Math.min(depth, numSquares(n - i * i, memo) + 1);
}
memo[n] = depth;
return memo[n];
}
}
private static class Solution1 {
public int numSquares(int n) {
int sqrt = (int) Math.sqrt(n);
if (sqrt * sqrt == n) {
return 1;
}
int depth = Integer.MAX_VALUE;
for (int i = 1; i * i < n; i ++) {
depth = Math.min(numSquares(n - i * i) + 1, depth);
}
return depth;
}
/**
* 拉格朗日四平方和定理
* 任何正整数均是完全平方数，它们都可以表示为4个以内的整数的平方和。
*/
public boolean isSquaresSum(int n) {
System.out.println(n);
if (n < 0) {
return false;
}
int sqrt = (int) Math.sqrt(n);
if (sqrt * sqrt == n) {
return true;
}
for (int i = 1; i * i < n; i ++) {
if (isSquaresSum(n - i * i)) {
return true;
}
}
return false;
}
}
}/**
* Given an array nums, write a function to move all 0's to the end of it
* while maintaining the relative order of the non-zero elements.
*
* Example:
* Input: [0,1,0,3,12]
* Output: [1,3,12,0,0]
*
* Note:
* You must do this in-place without making a copy of the array.
* Minimize the total number of operations.
*/
public class _0283_MoveZeroes {
private static class Solution {
public void moveZeroes(int[] nums) {
int pos = 0;
for (int num : nums){
if (num != 0) nums[pos++] = num;
}
while (pos < nums.length){
nums[pos++] = 0;
}
}
public void moveZeroes1(int[] nums) {
int numOfZero = 0;
for (int i = 0; i < nums.length; i ++){
if (nums[i] != 0) continue;
for (int j = i+1; j < nums.length; j ++){
if (nums[j] != 0) {
nums[i] = nums[j];
nums[j] = 0;
break;
}
}
}
}
}
}/**
* Example 1:
* Input: [1,3,4,2,2]
* Output: 2
*
* Example 2:
* Input: [3,1,3,4,2]
* Output: 3
*
* Note:
* You must not modify the array (assume the array is read only).
* You must use only constant, O(1) extra space.
* Your runtime complexity should be less than O(n2).
* There is only one duplicate number in the array, but it could be repeated more than once.
* </pre>
*/
public class _0287_FindTheDuplicateNumber {
/**
* Thought
* 142 环形链表II，求环形链表的入口结点
* Challenge
* 求链表的长度
*/
private static class Solution {
public int findDuplicate(int[] nums) {
Arrays.sort(nums);
int result = -1;
for (int i = 1; i < nums.length; i ++) {
if (nums[i-1] == nums[i]) {
result = nums[i];
break;
}
}
return result;
}
}
}/**
* Example:
* Input: [10,9,2,5,3,7,101,18]
* Output: 4
* Explanation:
* The longest increasing subsequence is [2,3,7,101].
*/
public class _0300_LongestIncreasingSubsequence {
/**
* Thought
* 动态规划
*
* Algorithm
* 1. dp[i+1] 表示以 nums[i]为结尾元素的最长上升子序列的长度
* 2. 初始值是 1
* 3. 动态转移条件和方程为
* nums[i] > nums[j]
* dp[i] = max(dp[i], dp[j]+1)
* 4. return max(dp[i])
*/
private static class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length+1];
Arrays.fill(dp, 1);
int len = 0;
for (int i = 0; i < nums.length; i ++) {
for (int j = 0; j < i; j ++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
len = Math.max(len, dp[i]);
}
return len;
}
}
private static class Solution1 {
public int lengthOfLIS(int[] nums) {
return lengthOfLIS(nums, Integer.MIN_VALUE, 0);
}
private int lengthOfLIS(int[] nums, int prev, int curpos) {
if (curpos == nums.length) {
return 0;
}
int taken = 0;
if (nums[curpos] > prev) {
taken = 1 + lengthOfLIS(nums, nums[curpos], curpos+1);
}
int nottaken = lengthOfLIS(nums, prev, curpos+1);
return Math.max(taken, nottaken);
}
}
}/**
* Say you have an array for which the ith element
* is the price of a given stock on day i.
*
* Design an algorithm to find the maximum profit.
* You may complete as many transactions as you like
* (ie, buy one and sell one share of the stock multiple times)
* with the following restrictions:
*
* You may not engage in multiple transactions at the same time
* (ie, you must sell the stock before you buy again).
* After you sell your stock, you cannot buy stock on next day.
* (ie, cooldown 1 day)
*
* Example:
* Input: [1,2,3,0,2]
* Output: 3
* Explanation: transactions = [buy, sell, cooldown, buy, sell]
*/
public class _0309_BestTimeToBuyAndSellStockWithCooldown {
private static class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 1) {
return 0;
}
int len = prices.length;
int[] buy = new int[len];
int[] sell = new int[len];
int[] rest = new int[len];
sell[0] = 0;
sell[1] = 0;
rest[0] = 0;
buy[0] = -prices[0];
for (int i = 1; i < len; i ++) {
buy[i] = rest[i-1]-prices[i];
sell[i] = Math.max(rest[i-1]+prices[i], buy[i-1]+prices[i]);
rest[i] = Math.max(Math.max(buy[i-1], rest[i-1]), sell[i-1]);
}
return Math.max(sell[len-1], rest[len-1]);
}
}
}/**
* You are given coins of different denominations and a total amount of
* money amount. Write a function to compute the fewest number of coins
* that you need to make up that amount. If that amount of money cannot
* be made up by any combination of the coins, return -1.
*
* Example 1:
* Input: coins = [1, 2, 5], amount = 11
* Output: 3
* Explanation: 11 = 5 + 5 + 1
*
* Example 2:
* Input: coins = [2], amount = 3
* Output: -1
*/
public class _0322_CoinChange {
/**
* Thought
* DP
* Algorithm
* 1. DP数组的初始值是 amount+1
* 2. 动态转移条件是余额大于硬币面值大小
* 3. 动态转移方程是
* dp[i] = min(dp[i], dp[i-coin]+1)
* 4. return dp[amount] > amount ? -1 : dp[amount]
*/
private static class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
int max = amount + 1;
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i ++) {
for (int coin: coins) {
if (coin > i) {
continue;
}
dp[i] = Math.min(dp[i], dp[i-coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
/**
* Thought
* DFS，有条件的计算二叉树的深度
*/
private static class Solution1 {
public int coinChange(int[] coins, int amount) {
int minCoins = minCoins(coins, amount);
if (minCoins == Integer.MAX_VALUE) {
minCoins = -1;
}
return minCoins;
}
private int minCoins(int[] coins, int amount) {
if (amount == 0) {
return 0;
}
int depth = Integer.MAX_VALUE;
for (int coin: coins) {
if (coin <= amount) {
int childDepth = minCoins(coins, amount - coin);
if (childDepth != Integer.MAX_VALUE) {
depth = Math.min(depth, childDepth+1);
}
}
}
return depth;
}
}
}/**
* The thief has found himself a new place for his thievery again.
* There is only one entrance to this area, called the "root."
* Besides the root, each house has one and only one parent house.
* After a tour, the smart thief realized that "all houses
* in this place forms a binary tree". It will automatically contact
* the police if two directly-linked houses were broken into on the same night.
*
* Determine the maximum amount of money the thief can
* rob tonight without alerting the police.
*
* Example 1:
* Input: [3,2,3,null,3,null,1]
* 3
* / \
* 2 3
* \ \
* 3 1
* Output: 7
* Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
*
* Example 2:
* Input: [3,4,5,1,3,null,1]
*
* 3
* / \
* 4 5
* / \ \
* 1 3 1
* Output: 9
* Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
*/
public class _0337_HouseRobberIII {
/**
* Thought
* DFS
*/
private static class Solution {
public int rob(TreeNode root) {
if (root == null) {
return 0;
} else {
int val = 0;
if (root.left != null) {
val += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
val += rob(root.right.left) + rob(root.right.right);
}
int robRoot = root.val + val;
int notRobRoot = rob(root.left) + rob(root.right);
return Math.max(robRoot, notRobRoot);
}
}
}
}/**
* Given a non negative integer number num. For every numbers i in the
* range 0 ≤ i ≤ num calculate the number of 1's in their binary
* representation and return them as an array.
*
* Example 1:
* Input: 2
* Output: [0,1,1]
*
* Example 2:
* Input: 5
* Output: [0,1,1,2,1,2]
*/
public class _0338_CountingBits {
/**
* Thought
* 动态规划
* Challenge
* 发现规律：
* An easy recurrence for this problem is f[i] = f[i / 2] + i % 2.
*/
private static class Solution {
public int[] countBits(int num) {
int[] res = new int[num+1];
for (int i = 1; i <= num; i ++) {
res[i] = res[i>>1] + (i & 1); // res[i] = res[i/2] + (i % 2);
}
return res;
}
public int[] countBits1(int num) {
int[] result = new int[num+1];
for (int i = 1; i <= num; i ++)
result[i] = result[i/2] + i % 2;
return result;
}
}
}/**
* Given a non-empty array of integers, return the k most frequent elements.
*
* Example 1:
* Input: nums = [1,1,1,2,2,3], k = 2
* Output: [1,2]
*
* Example 2:
* Input: nums = [1], k = 1
* Output: [1]
* Note:
* You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
* Your algorithm's time complexity must be better than O(n log n),
* where n is the array's size.
*/
public class _0347_TopKFrequentElements {
/**
* Thought
* 方法一，键值对排序，O(nlogn)
* 方法二，小根堆，O(nlogK)
* 方法三，桶排序，O(n)
*/
private static class Solution {
/**
* 方法二，小根堆
*/
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num: nums) {
int val = map.getOrDefault(num, 0);
map.put(num, val + 1);
}
Comparator<Integer> cmp = (i1, i2) -> map.get(i1) - map.get(i2);
PriorityQueue<Integer> minHeap = new PriorityQueue<>(cmp);
for (Integer key: map.keySet()) {
if (minHeap.size() < k) {
minHeap.offer(key);
} else if (map.get(key) > map.get(minHeap.peek())){
minHeap.poll();
minHeap.offer(key);
}
}
List<Integer> result = new ArrayList<>(k);
while (!minHeap.isEmpty()) {
result.add(minHeap.poll());
}
Collections.reverse(result);
return result;
}
}
private static class Solution1 {
/**
* 方法一，键值对排序
*/
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num: nums) {
int val = map.getOrDefault(num, 0);
map.put(num, val + 1);
}
List<Map.Entry<Integer, Integer>> kvList = new ArrayList<>(map.entrySet());
kvList.sort((e1, e2) -> {
int v1 = e1.getValue();
int v2 = e2.getValue();
return v1 - v2 > 0 ? -1 : v1 - v2 < 0 ? 1 : e1.getKey() - e2.getKey();
});
List<Integer> result = new ArrayList<>();
for (int i = 0; i < k; i ++) {
result.add(kvList.get(i).getKey());
}
return result;
}
}
}/**
* Examples:
* s = "3[a]2[bc]", return "aaabcbc".
* s = "3[a2[c]]", return "accaccacc".
* s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
*/
public class _0394_DecodeString {
/**
* Thought
* 方法一，递归法
* 方法二，双栈，分别保存子字符串和其出现的次数
*/
private static class Solution {
/**
* 方法二，双栈
*/
public String decodeString(String s) {
Stack<Integer> count = new Stack<>();
Stack<String> result = new Stack<>();
result.push("");
int i = 0;
while (i < s.length()) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) { // 数字
int start = i;
while (Character.isDigit(s.charAt(i+1))) {
i ++;
}
count.push(Integer.parseInt(s.substring(start, i+1)));
} else if (ch == '[') { // 子字符串开始
result.push("");
} else if (ch == ']') { // 子字符串结尾
String substr = result.pop();
StringBuilder str = new StringBuilder();
int times = count.pop();
for (int k = 0; k < times; k ++) {
str.append(substr);
}
result.push(result.pop() + str.toString());
} else { // 字符
result.push(result.pop() + ch);
}
i ++;
}
return result.pop();
}
}
}/**
* Suppose you have a random list of people standing in a queue.
* Each person is described by a pair of integers (h, k),
* where h is the height of the person and k is the number of people
* in front of this person who have a height greater than or equal to h.
* Write an algorithm to reconstruct the queue.
*
* Note:
* The number of people is less than 1,100.
*
* Example
* Input:
* [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
*
* Output:
* [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
*/
public class _0406_QueueReconstructionByHeight {
/**
* Thought
* 先排序后插入
* Challenge
* 发现规律
* Algorithm
* 1. 排序规则，按照先 H 高度降序，K 个数升序排序；
* 2. 遍历排序后的数组，根据 K 将元素插入到结果列表的 K 位置上。
*
* 高个子先排好相对位置，矮个子插入到 K 位上，矮个子前面必然存在 K 个高个子，
* 而插入的矮个子又不会影响高个子的 K
*/
private static class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (hk1, hk2) -> hk1[0] > hk2[0] ? -1 :
hk1[0] < hk2[0] ? 1 : hk1[1] - hk2[1]);
List<int[]> result = new LinkedList<>();
for (int[] p: people) {
result.add(p[1], p);
}
return result.toArray(new int[people.length][2]);
}
}
}/**
* Given a non-empty array containing only positive integers,
* find if the array can be partitioned into two subsets
* such that the sum of elements in both subsets is equal.
*
* Note:
* Each of the array element will not exceed 100.
* The array size will not exceed 200.
*
* Example 1:
* Input: [1, 5, 11, 5]
* Output: true
* Explanation: The array can be partitioned as [1, 5, 5] and [11].
*
* Example 2:
* Input: [1, 2, 3, 5]
* Output: false
* Explanation: The array cannot be partitioned into equal sum subsets.
*/
public class _0416_PartitionEqualSubsetSum {
private static class Solution {
public boolean canPartition(int[] nums) {
if (nums == null || nums.length < 2) {
return false;
}
int sum = 0;
for (int num: nums) {
sum += num;
}
if ((sum & 1) == 1) {
return false;
}
int target = sum / 2;
int len = nums.length;
boolean[][] dp = new boolean[len][target+1];
dp[0][nums[0]] = true;
for (int i = 1; i < len; i ++) {
for (int j = 0; j < target+1; j ++) {
dp[i][j] = dp[i-1][j];
if (j >= nums[i]) {
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
}
}
}
return dp[len-1][target];
}
}
}/**
* You are given a binary tree in which each node contains an integer value.
* Find the number of paths that sum to a given value.
*
* The path does not need to start or end at the root or a leaf,
* but it must go downwards (traveling only from parent nodes to child nodes).
*
* The tree has no more than 1,000 nodes and the values
* are in the range -1,000,000 to 1,000,000.
*
* Example:
* root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
*
* 10
* / \
* 5 -3
* / \ \
* 3 2 11
* / \ \
* 3 -2 1
*
* Return 3. The paths that sum to 8 are:
*
* 1. 5 -> 3
* 2. 5 -> 2 -> 1
* 3. -3 -> 11
*/
public class _0437_PathSumIII {
/**
* Thought
* 递归
*/
private static class Solution {
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
return pathNum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
private int pathNum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
sum -= root.val;
int num = sum == 0 ? 1 : 0;
return num + pathNum(root.left, sum) + pathNum(root.right, sum);
}
}
}/**
* Given a string s and a non-empty string p,
* find all the start indices of p's anagrams in s.
*
* Strings consists of lowercase English letters only and the length
* of both strings s and p will not be larger than 20,100.
*
* The order of output does not matter.
*
* Input:
* s: "abab" p: "ab"
* Output:
* [0, 1, 2]
* Explanation:
* The substring with start index = 0 is "ab", which is an anagram of "ab".
* The substring with start index = 1 is "ba", which is an anagram of "ab".
* The substring with start index = 2 is "ab", which is an anagram of "ab".
*/
public class _0438_FindAllAnagramsInAString {
private static class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s == null || p == null) {
return result;
}
int[] needs = new int[26];
int count = 0;
for (int i = 0; i < p.length(); i ++) {
int index = p.charAt(i) - 'a';
if (needs[index] == 0) {
count ++;
}
needs[index] ++;
}
int[] window = new int[26];
int left = 0;
int right = 0;
int match = 0;
while (right < s.length()) {
int index = s.charAt(right) - 'a';
right ++;
if (needs[index] > 0) {
window[index] ++;
if (window[index] == needs[index]) {
match ++;
}
}
while (match == count) {
int removeIndex = s.charAt(left) - 'a';
left ++;
if (needs[removeIndex] > 0) {
window[removeIndex] --;
if (window[removeIndex] < needs[removeIndex]) {
match --;
int len = right - (left - 1);
if (len == p.length()) {
result.add(left-1);
}
}
}
}
}
return result;
}
public List<Integer> findAnagrams1(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s == null || p == null) {
return result;
}
int[] standard = count(p);
for (int i = 0; i < s.length() - p.length() + 1; i ++) {
int end = i + p.length();
String sub = s.substring(i, end);
int[] map = count(sub);
boolean equals = compare(map, standard);
if (equals) {
result.add(i);
}
}
return result;
}
private int[] count(String sub) {
int[] map = new int[26];
for (int i = 0; i < sub.length(); i ++) {
int index = sub.charAt(i) - 'a';
map[index] ++;
}
return map;
}
private boolean compare(int[] map, int[] standard) {
boolean equals = true;
for (int i = 0; i < map.length; i ++) {
if (map[i] != standard[i]) {
equals = false;
break;
}
}
return equals;
}
}
}/**
* Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array),
* some elements appear twice and others appear once.
*
* Find all the elements of [1, n] inclusive that do not appear in this array.
*
* Could you do it without extra space and in O(n) runtime?
* You may assume the returned list does not count as extra space.
*
* Example:
* Input:
* [4,3,2,7,8,2,3,1]
* Output:
* [5,6]
*/
public class _0448_FindAllNumbersDisappearedInAnArray {
/**
* Thought
* 充分使用数组长度和数组元素大小的关系，数组元素可以作为数组的下标使用
*
* The basic idea is that we iterate through the input array and
* mark elements as negative using nums[nums[i] -1] = -nums[nums[i]-1].
* In this way all the numbers that we have seen will be marked as negative.
* In the second iteration, if a value is not marked as negative,
* it implies we have never seen that index before,
* so just add it to the return list.
*/
private static class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int index = Math.abs(nums[i]) - 1; // 元素关联的下标
if (nums[index] > 0) nums[index] = -nums[index]; // 元素标记下标对应数字是否出现
}
for (int j = 0; j < nums.length; j++) {
if (nums[j] > 0) list.add(j + 1);
}
return list;
}
public List<Integer> findDisappearedNumbers2(int[] nums) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int index = (nums[i] - 1) % nums.length;
nums[index] += nums.length;
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= nums.length) {
result.add(i + 1);
}
}
return result;
}
public List<Integer> findDisappearedNumbers1(int[] nums) {
long bitset = 0;
for (int element : nums) {
int index = pow(element - 1);
if ((bitset & index) == 0) {
bitset ^= index;
}
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int index = pow(i);
if ((bitset & index) != index) {
result.add(i + 1);
}
}
return result;
}
int pow(int n) {
int result = 1;
for (int i = 0; i < n; i++) {
result *= 2;
}
return result;
}
}
}/**
* The Hamming distance between two integers is the number of positions
* at which the corresponding bits are different.
*
* Input: x = 1, y = 4
* Output: 2
* Explanation:
* 1 (0 0 0 1)
* 4 (0 1 0 0)
* ↑ ↑
*/
public class _0461_HammingDistance {
private static class Solution {
public int hammingDistance(int x, int y) {
int counter = 0;
while (x != 0 || y != 0){
if ((x & 1) != (y & 1)) counter ++;
x = x >> 1;
y = y >> 1;
}
return counter;
}
public int hammingDistance1(int x, int y) {
int counter = 0;
for (int i = 0; i < 32; i ++){
if ((x & 1) != (y & 1)) counter ++;
x = x >> 1;
y = y >> 1;
}
return counter;
}
}
}/**
* You are given a list of non-negative integers, a1, a2, ..., an,
* and a target, S. Now you have 2 symbols + and -. For each integer,
* you should choose one from + and - as its new symbol.
*
* Find out how many ways to assign symbols to make sum of
* integers equal to target S.
*
* Input: nums is [1, 1, 1, 1, 1], S is 3.
* Output: 5
* Explanation:
* -1+1+1+1+1 = 3
* +1-1+1+1+1 = 3
* +1+1-1+1+1 = 3
* +1+1+1-1+1 = 3
* +1+1+1+1-1 = 3
* There are 5 ways to assign symbols to make the sum of nums be target 3.
*/
public class _0494_TargetSum {
/**
* Thought
* 递归
*/
private static class Solution {
public int findTargetSumWays(int[] nums, int S) {
return dfs(nums, S, 0);
}
private int dfs(int[] nums, int sum, int start) {
if (start == nums.length) {
return sum == 0 ? 1 : 0;
}
return dfs(nums, sum+nums[start], start+1)
+ dfs(nums, sum-nums[start], start+1);
}
}
}/**
* Given a Binary Search Tree (BST), convert it to a Greater Tree
* such that every key of the original BST is changed to the original key
* plus sum of all keys greater than the original key in BST.
*
* Input: The root of a Binary Search Tree like this:
* 5
* / \
* 2 13
* Output: The root of a Greater Tree like this:
* 18
* / \
* 20 13
*/
public class _0538_ConvertBSTToGreaterTree {
private static class Solution {
public TreeNode convertBST(TreeNode root) {
inorderVisit(root, new int[]{0});
return root;
}
private void inorderVisit(TreeNode root, int[] rightSum) {
if (root == null) {
return;
}
inorderVisit(root.right, rightSum);
root.val += rightSum[0];
rightSum[0] = root.val;
inorderVisit(root.left, rightSum);
}
}
}/**
* Given a binary tree, you need to compute the length of the
* diameter of the tree. The diameter of a binary tree is the length of
* the longest path between any two nodes in a tree.
* This path may or may not pass through the root.
*
* Example:
* Given a binary tree
* 1
* / \
* 2 3
* / \
* 4 5
* Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
*
* Note: The length of path between two nodes is represented by
* the number of edges between them.
*/
public class _0543_DiameterOfBinaryTree {
/**
* Thought
* 递归
*/
private static class Solution {
private int max = -1;
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
int diameter = depth(root.left) + depth(root.right);
max = Math.max(diameter, max);
diameterOfBinaryTree(root.left);
diameterOfBinaryTree(root.right);
return max;
}
private int depth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = depth(root.left);
int rightDepth = depth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
int maxVal = 0;
public int diameterOfBinaryTree1(TreeNode root) {
maxDepth(root);
return maxVal;
}
private int maxDepth(TreeNode root){
if (root == null) return 0;
int l = maxDepth(root.left);
int r = maxDepth(root.right);
maxVal = Math.max(maxVal, l+r);
return Math.max(l, r) + 1;
}
}
}/**
* Given an array of integers and an integer k, you need to find the
* total number of continuous subarrays whose sum equals to k.
*
* Example 1:
* Input:nums = [1,1,1], k = 2
* Output: 2
*/
public class _0560_SubarraySumEqualsK {
/**
* Thought
* 方法一，暴力法
* 方法二，动态规划
*/
private static class Solution {
/**
* 方法一，暴力法
*/
public int subarraySum(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.length; start ++) {
int sum = 0;
for (int end = start; end < nums.length; end ++) {
sum += nums[end];
if (sum == k) {
count ++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] input = {1, 1, 1};
int k = 2;
int result = new Solution().subarraySum(input, k);
System.out.println("result = " + result);
}
}
}/**
* Given an integer array, you need to find one continuous subarray
* that if you only sort this subarray in ascending order,
* then the whole array will be sorted in ascending order, too.
*
* You need to find the shortest such subarray and output its length.
*
* Input: [2, 6, 4, 8, 10, 9, 15]
* Output: 5
* Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to
* make the whole array sorted in ascending order.
*/
public class _581_ShortestUnsortedContinuousSubarray {
private static class Solution {
public int findUnsortedSubarray(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
int unsortedMinIndex = -1;
int unsortedMin = Integer.MAX_VALUE;
int max = nums[0];
int unsortedMaxIndex = -1;
int unsortedMax = Integer.MIN_VALUE;
int min = nums[nums.length-1];
for (int i = 0; i < nums.length; i ++) {
if (nums[i] < max) {
unsortedMin = Math.min(unsortedMin, nums[i]);
}
max = Math.max(max, nums[i]);
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] > unsortedMin) {
unsortedMinIndex = i;
break;
}
}
for (int j = nums.length-1; j >= 0; j --) {
if (nums[j] > min) {
unsortedMax = Math.max(unsortedMax, nums[j]);
}
min = Math.min(min, nums[j]);
}
for (int j = nums.length-1; j >= 0; j --) {
if (nums[j] < unsortedMax) {
unsortedMaxIndex = j;
break;
}
}
int count = 0;
if (unsortedMinIndex != -1) {
count = unsortedMaxIndex - unsortedMinIndex + 1;
}
return count;
}
public int findUnsortedSubarray1(int[] nums) {
int left = nums.length;
int right = 0;
for (int i = 0; i < nums.length; i ++) {
for (int j = i+1; j < nums.length; j ++) {
if (nums[i] > nums[j]) {
left = Math.min(i, left);
right = Math.max(j, right);
}
}
}
int count = 0;
if (right != 0) {
count = right - left + 1;
}
return count;
}
}
}/**
* Input:
* Tree 1 Tree 2
* 1 2
* / \ / \
* 3 2 1 3
* / \ \
* 5 4 7
* Output:
* Merged tree:
* 3
* / \
* 4 5
* / \ \
* 5 4 7
*/
public class _0617_MergeTwoBinaryTrees {
private static class Solution {
private TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) return t2;
if (t2 == null) return t1;
/* 合并根节点 */
t1.val += t2.val;
/* 递归合并左右子树 */
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}
}/**
* Example 1:
* Input: "abc"
* Output: 3
* Explanation: Three palindromic strings: "a", "b", "c".
*
* Example 2:
* Input: "aaa"
* Output: 6
* Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
*/
public class _0647_PalindromicSubstrings {
/**
* Thought
* 方法一，中心扩展法
* 方法二，动态规划
* 方法三，暴力验证所有子串
*/
private static class Solution {
/**
* 方法一，中心扩展法
*/
public int countSubstrings(String s) {
int count = 0;
for (int i = 0; i < s.length(); i ++) {
count += palindromicSubstrings(s, i, i);
count += palindromicSubstrings(s, i, i+1);
}
return count;
}
private int palindromicSubstrings(String str, int left, int right) {
int count = 0;
while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
count ++;
left --;
right ++;
}
return count;
}
}
private static class Solution1 {
/**
* 方法三，暴力验证所有子串
*/
public int countSubstrings(String s) {
int counter = 0;
for (int i = 0; i < s.length(); i ++){
for (int j = i+1; j < s.length()+1; j ++){
String str = s.substring(i, j);
if (isPalindromicString(str))
counter ++;
}
}
return counter;
}
private boolean isPalindromicString(String s){
if (s.length() == 1) return true;
boolean bool = true;
for (int i = 0; i < s.length()/2; i ++){
if (s.charAt(i) != s.charAt(s.length()-1-i)){
bool = false;
break;
}
}
return bool;
}
}
}