以下是为你整理的上述 LeetCode 题目对应的链接：
排序算法
- 插入排序
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i]; // 当前需要插入的元素
int j = i - 1;
// 将比 key 大的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // 插入 key 到正确位置
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
insertionSort(arr);
System.out.println("排序后的数组:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
- 冒泡排序
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果没有发生交换，说明数组已经有序，提前退出
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("排序后的数组:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
- 快速排序
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 找到分区点，将数组分为两部分
int pi = partition(arr, low, high);
// 递归排序左半部分
quickSort(arr, low, pi - 1);
// 递归排序右半部分
quickSort(arr, pi + 1, high);
}
}
// 分区函数
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1; // i 是较小元素的索引
for (int j = low; j < high; j++) {
// 如果当前元素小于或等于基准
if (arr[j] <= pivot) {
i++;
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准元素放到正确的位置
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // 返回基准元素的索引
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
- 堆排序
public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;
// 构建最大堆（从最后一个非叶子节点开始）
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 逐个提取堆顶元素（最大值），放到数组末尾
for (int i = n - 1; i > 0; i--) {
// 将堆顶元素（最大值）与当前末尾元素交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 重新调整堆，使其满足最大堆性质
heapify(arr, i, 0);
}
}
// 堆化函数：调整以 i 为根的子树为最大堆
private static void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化最大值为根节点
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点比根节点大，更新最大值
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点比当前最大值大，更新最大值
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点，交换并递归调整
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// 递归调整受影响的子树
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
heapSort(arr);
System.out.println("排序后的数组:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
- 计数排序
public class CountingSort {
public static void countingSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
// 找出数组中的最大值
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
// 定义计数数组，长度为最大值 + 1
int[] count = new int[max + 1];
// 统计每个元素出现的次数
for (int num : arr) {
count[num]++;
}
// 遍历计数数组，将元素按顺序放回原数组
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 2, 8, 3, 3, 1};
System.out.println(" 排序前:");
for (int num : arr) {
System.out.print(num + " ");
}
// 调用计数排序方法
countingSort(arr);
System.out.println("\n 排序后:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
- 桶排序
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static double[] bucketSort(double[] array) {
if (array == null || array.length == 0) {
return array;
}
// 找出数组中的最大值和最小值
double max = array[0];
double min = array[0];
for (double num : array) {
if (num > max) {
max = num;
}
if (num < min) {
min = num;
}
}
// 计算桶的数量
int bucketNum = array.length;
List<List<Double>> buckets = new ArrayList<>();
for (int i = 0; i < bucketNum; i++) {
buckets.add(new ArrayList<>());
}
// 将元素分配到不同的桶中
for (double num : array) {
int bucketIndex = (int) ((num - min) * (bucketNum - 1) / (max - min));
buckets.get(bucketIndex).add(num);
}
// 对每个桶内的元素进行排序
for (List<Double> bucket : buckets) {
Collections.sort(bucket);
}
// 将所有桶中的元素合并到一个数组中
double[] sortedArray = new double[array.length];
int index = 0;
for (List<Double> bucket : buckets) {
for (double num : bucket) {
sortedArray[index++] = num;
}
}
return sortedArray;
}
public static void main(String[] args) {
double[] array = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};
double[] sortedArray = bucketSort(array);
for (double num : sortedArray) {
System.out.print(num + " ");
}
}
}
动态规划
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int first = 1;
int second = 2;
int result = 0;
for (int i = 3; i <= n; i++) {
result = first + second;
first = second;
second = result;
}
return result;
}
}
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, amount+1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for(int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price;
} else if (price - minPrice > maxProfit) {
maxProfit = price - minPrice;
}
}
return maxProfit;
}
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
int pr = prices[i] - prices[i - 1]
if (pr > 0) {
profit += pr;
}
}
return profit;
}
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int max = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
max = Math.max(max, dp[i]);
}
}
return max;
}
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
if (n == 1) return nums[0];
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[n - 1];
}
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
if (n == 1) {
return nums[0];
}
// Case 1: Rob houses from the first to the second - last house
int result1 = robRange(nums, 0, n - 2);
// Case 2: Rob houses from the second to the last house
int result2 = robRange(nums, 1, n - 1);
// Return the maximum of the two results
return Math.max(result1, result2);
}
private int robRange(int[] nums, int start, int end) {
if (start == end) {
return nums[start];
}
int n = end - start + 1;
int[] dp = new int[n];
dp[0] = nums[start];
dp[1] = Math.max(nums[start], nums[start + 1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[start + i]);
}
return dp[n - 1];
}
public int change(int amount, int[] coins) {
// Create a dp array to store the number of combinations for each amount
int[] dp = new int[amount + 1];
// Initialize dp[0] to 1, as there is one way to make up amount 0 (using no coins)
dp[0] = 1;
// Iterate through each coin denomination
for (int coin : coins) {
// Update the dp array for each amount from coin to the target amount
for (int i = coin; i <= amount; i++) {
// The number of combinations to make up amount i is the sum of the original number of combinations
// and the number of combinations to make up amount i - coin
dp[i] += dp[i - coin];
}
}
// Return the number of combinations to make up the target amount
return dp[amount];
}
回溯算法
private List<List<String>> result = new ArrayList<>();
private int n;
public List<List<String>> solveNQueens(int n) {
this.n = n;
char[][] board = new char[n][n];
// Initialize the chessboard
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
backtrack(board, 0);
return result;
}
private void backtrack(char[][] board, int row) {
if (row == n) {
result.add(constructSolution(board));
return;
}
for (int col = 0; col < n; col++) {
if (isValid(board, row, col)) {
board[row][col] = 'Q';
backtrack(board, row + 1);
board[row][col] = '.';
}
}
}
private boolean isValid(char[][] board, int row, int col) {
// Check the column
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') {
return false;
}
}
// Check the upper - left diagonal
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
// Check the upper - right diagonal
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
private List<String> constructSolution(char[][] board) {
List<String> solution = new ArrayList<>();
for (int i = 0; i < n; i++) {
solution.add(new String(board[i]));
}
return solution;
}
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
track(result, new ArrayList<Integer>(), nums, 0);
return result;
}
private void track(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {
result.add(new ArrayList<>(tempList));
for (int i = start; i < nums.length; i++) {
tempList.add(nums[i]);
track(result, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}
List<List<Integer>> result;
List<Integer> list;
boolean[] used;
int[] nums;
public List<List<Integer>> permute(int[] nums) {
this.result = new ArrayList<>();
this.used = new boolean[nums.length];
this.list = new ArrayList<>();
this.nums = nums;
track();
return result;
}
private void track() {
if (list.size() == nums.length) {
result.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
used[i] = true;
list.add(nums[i]);
track();
used[i] = false;
list.remove(list.size() - 1);
}
}
private List<List<Integer>> result;
private List<Integer> temp;
private int n;
private int k;
public List<List<Integer>> combine(int n, int k) {
this.result = new ArrayList<>();
this.temp = new ArrayList<>();
this.n = n;
this.k = k;
track(1);
return result;
}
private void track(int start) {
if (temp.size() == k) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = start; i <=n; i++) {
temp.add(i);
track(i+1);
temp.remove(temp.size() - 1);
}
}
private static final String[] PHONE_MAP = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
private List<String> result;
private StringBuilder sb;
private String digits;
public List<String> letterCombinations(String digits) {
this.result = new ArrayList<>();
this.sb = new StringBuilder();
this.digits = digits;
if (digits == null || digits.length() == 0) {
return result;
}
track(0);
return result;
}
private void track(int index) {
if (index == digits.length()) {
result.add(sb.toString());
return;
}
int digit = digits.charAt(index) - '0';
String letters = PHONE_MAP[digit];
for (int i = 0; i < letters.length(); i++) {
sb.append(letters.charAt(i));
track(index+1);
sb.deleteCharAt(sb.length() - 1);
}
}
private boolean[][] visited;
private int rows, cols;
public boolean exist(char[][] board, String word) {
rows = board.length;
cols = board[0].length;
visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == word.charAt(0) && backtrack(board, word, i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean backtrack(char[][] board, String word, int i, int j, int index) {
if (index == word.length()) {
return true;
}
if (i < 0 || i >= rows || j < 0 || j >= cols || visited[i][j] || board[i][j] != word.charAt(index)) {
return false;
}
visited[i][j] = true;
boolean found = backtrack(board, word, i + 1, j, index + 1) ||
backtrack(board, word, i - 1, j, index + 1) ||
backtrack(board, word, i, j + 1, index + 1) ||
backtrack(board, word, i, j - 1, index + 1);
visited[i][j] = false;
return found;
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), candidates, target, 0);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
if (remain < 0) {
return;
} else if (remain == 0) {
result.add(new ArrayList<>(tempList));
} else {
for (int i = start; i < candidates.length; i++) {
tempList.add(candidates[i]);
backtrack(result, tempList, candidates, remain - candidates[i], i);
tempList.remove(tempList.size() - 1);
}
}
}
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
backtrack(result, new ArrayList<>(), candidates, target, 0);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
if (remain < 0) {
return;
} else if (remain == 0) {
result.add(new ArrayList<>(tempList));
} else {
for (int i = start; i < candidates.length; i++) {
// Skip duplicates
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
tempList.add(candidates[i]);
backtrack(result, tempList, candidates, remain - candidates[i], i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
贪心算法
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int nums = 0;
int i = 0;
int j = 0;
while(i < g.length && j < s.length) {
if (s[j] >= g[i]) {
nums++;
i++;
}
j++;
}
return nums;
}
public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;
for (int bill: bills) {
switch(bill) {
case 5:
five++;
break;
case 10:
if(five == 0) {
return false;
}
five--;
ten++;
break;
case 20:
if(five>0&&ten>0) {
five--;
ten--;
} else if(five >= 3) {
five -= 3;
} else {
return false;
}
break;
}
}
return true;
}
public int maxSubArray(int[] nums) {
int maxSoFar = nums[0];
int maxEndHere = nums[0];
for (int i = 1; i < nums.length; i++) {
maxEndHere = Math.max(nums[i], maxEndHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndHere);
}
return maxSoFar;
}
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price;
} else if (price - minPrice > maxProfit) {
maxProfit = price - minPrice;
}
}
return maxProfit;
}
public boolean canJump(int[] nums) {
int lastPos = nums.length - 1;
for (int i = nums.length - 1; i >= 0; i--) {
if (i + nums[i] >= lastPos) {
lastPos = i;
}
}
return lastPos == 0;
}
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0;
int current = 0;
int start = 0;
for (int i = 0; i < gas.length; i++) {
total += gas[i] - cost[i];
current += gas[i] - cost[i];
if (current < 0) {
start = i + 1;
current = 0;
}
}
return total >= 0 ? start : -1;
}
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int count = 0;
for (int i = 0; i < flowerbed.length; i++) {
if (
flowerbed[i] == 0
&& (i == 0 || flowerbed[i - 1] == 0)
&& (i == flowerbed.length - 1 || flowerbed[i+1] == 0)
) {
flowerbed[i] = 1;
count++;
}
}
return count >= n;
}
位运算
public int singleNumber(int[] nums) {
int result = 0;
for (int num: nums) {
result ^= num;
}
return result;
}
public int singleNumber(int[] nums) {
int ones = 0, twos = 0;
for (int num : nums) {
ones = (ones ^ num) & ~twos;
twos = (twos ^ num) & ~ones;
}
return ones;
}
public int[] singleNumber(int[] nums) {
// 第一步：对所有数字进行异或
int xorResult = 0;
for (int num : nums) {
xorResult ^= num; // xorResult 最终得到的是两个只出现一次的数字的异或结果
}
// 第二步：找到 xorResult 中最右边的 1
int rightmostOne = xorResult & (-xorResult);
// 第三步：根据这个位将数组分成两组
int x = 0;
for (int num : nums) {
if ((num & rightmostOne) != 0) { // 如果当前数字在这个位上是 1
x ^= num; // 将其归入第一组并异或
}
}
// 第四步：得到另一个数
int y = xorResult ^ x; // 用总异或结果异或第一个数，得到第二个数
return new int[]{x, y};
}
public int hammingDistance(int x, int y) {
int xor = x ^ y;
int distance = 0;
while(xor != 0) {
distance += xor & 1;
xor >>= 1;
}
return distance;
}
public int missingNumber(int[] nums) {
int xor = 0;
for (int i = 0; i <= nums.length; i++) {
xor ^= i;
}
for(int n : nums) {
xor ^= n;
}
return xor;
}
数学题
public double myPow(double x, int n) {
long N = n;
return N >= 0 ? quickPow(x, N) : 1.0 / quickPow(x, -N);
}
private double quickPow(double x, long n) {
double ans = 1.0;
double current = x;
while (n > 0) {
if (n % 2 == 1) {
ans *= current;
}
current *= current;
n /= 2;
}
return ans;
}
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
int m = num1.length();
int n = num2.length();
// 初始化结果数组
int[] result = new int[m + n];
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
// 计算当前位的乘积
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
// 计算乘积在结果数组中的位置
int p1 = i + j;
int p2 = i + j + 1;
// 加上之前的进位
int total = mul + result[p2];
// 更新结果数组
result[p2] = total % 10;
result[p1] += total / 10;
}
}
StringBuilder sb = new StringBuilder();
// 处理前导零
for (int num : result) {
if (!(sb.length() == 0 && num == 0)) {
sb.append(num);
}
}
return sb.toString();
}
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length;
int n = nums2.length;
int imin = 0, imax = m, halfLen = (m + n + 1) / 2;
while (imin <= imax) {
int i = (imin + imax) / 2;
int j = halfLen - i;
if (i < m && nums2[j - 1] > nums1[i]) {
// i 太小，需要增大
imin = i + 1;
} else if (i > 0 && nums1[i - 1] > nums2[j]) {
// i 太大，需要减小
imax = i - 1;
} else {
// i 是完美的分割点
int maxOfLeft;
if (i == 0) {
maxOfLeft = nums2[j - 1];
} else if (j == 0) {
maxOfLeft = nums1[i - 1];
} else {
maxOfLeft = Math.max(nums1[i - 1], nums2[j - 1]);
}
if ((m + n) % 2 == 1) {
return maxOfLeft;
}
int minOfRight;
if (i == m) {
minOfRight = nums2[j];
} else if (j == n) {
minOfRight = nums1[i];
} else {
minOfRight = Math.min(nums1[i], nums2[j]);
}
return (maxOfLeft + minOfRight) / 2.0;
}
}
return 0.0;
}
public int reverse(int x) {
int sign = x < 0 ? -1 : 1;
x = Math.abs(x);
int result = 0;
while (x != 0) {
int digit = x % 10;
x /= 10;
// 检查是否溢出
if (result > (Integer.MAX_VALUE - digit) / 10) {
return 0;
}
result = result * 10 + digit;
}
result *= sign;
return result;
}
public String gcdOfStrings(String str1, String str2) {
int gcdLength = gcd(str1.length(), str2.length());
for (int length = gcdLength; length > 0; length--) {
if (gcdLength % length == 0) {
String candidate = str1.substring(0, length);
if (repeatString(candidate, str1.length() / length).equals(str1) && repeatString(candidate, str2.length() / length).equals(str2)) {
return candidate;
}
}
}
return "";
}
// 求最大公约数
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
// 重复字符串
private String repeatString(String s, int n) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(s);
}
return sb.toString();
}
二分查找
public int firstBadVersion(int n) {
int left = 1; // 定义左边界为 1
int right = n; // 定义右边界为 n
while (left < right) { // 当左边界小于右边界时，进行二分查找
int mid = left + (right - left) / 2; // 计算中间位置
if (isBadVersion(mid)) { // 如果中间位置是坏版本
right = mid; // 将右边界更新为中间位置
} else { // 如果中间位置不是坏版本
left = mid + 1; // 将左边界更新为中间位置的下一个
}
}
return left; // 返回最终的左边界，即为第一个坏版本
}
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target) {
return mid;
} else if(nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int left = (m + n + 1) / 2;
int right = (m + n + 2) / 2;
return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
}
private int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
if (i >= nums1.length) return nums2[j + k - 1];
if (j >= nums2.length) return nums1[i + k - 1];
if (k == 1) return Math.min(nums1[i], nums2[j]);
int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
if (midVal1 < midVal2) {
return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
} else {
return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
}
}
数组
public void moveZeroes(int[] nums) {
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[j] = nums[i];
++j;
}
}
for (int i = j; i < nums.length; i++) {
nums[i] = 0;
}
}
int left = 0, right = nums.length - 1, current = 0;
while (current <= right) {
if (nums[current] == 0) {
swap(nums, left, current);
left++;
current++;
} else if (nums[current] == 2) {
swap(nums, right, current);
right--;
} else {
current++;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k] = nums1[i];
i--;
} else {
nums1[k] = nums2[j];
j--;
}
k--;
}
while (j >= 0) {
nums1[k] = nums2[j];
j--;
k--;
}
}
链表
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNode sortList(ListNode head) {
return sort(head, null);
}
private ListNode sort(ListNode head, ListNode tail) {
if (head == null) return head;
if (head.next == tail) {
head.next = null;
return head;
}
ListNode slow = head, fast = head;
while (fast != tail) {
slow = slow.next;
fast = fast.next;
if (fast != tail) fast = fast.next;
}
ListNode l1 = sort(head, slow);
ListNode l2 = sort(slow, tail);
return merge(l1, l2);
}
private ListNode merge(ListNode n1, ListNode n2) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (n1 != null && n2 != null) {
if (n1.val <= n2.val) {
cur.next = n1;
n1 = n1.next;
} else {
cur.next = n2;
n2 = n2.next;
}
cur = cur.next;
}
cur.next = n1 != null ? n1 : n2;
return dummy.next;
}
public void reorderList(ListNode head) {
if (head == null) return;
// 找到中间转折的点
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
System.out.println("slow -> " + slow.val);
// 翻转后边的列表
ListNode nl = new ListNode();
while (slow.next != null) {
ListNode tmp = slow.next;
// 移除主链表
slow.next = slow.next.next;
// 放入翻转链表
tmp.next = nl.next;
nl.next = tmp;
}
// 合并链表
ListNode cur = head;
while (nl.next != null) {
ListNode tmp = nl.next;
nl.next = nl.next.next;
// 加入主链表
tmp.next = cur.next;
cur.next = tmp;
cur = cur.next.next;
System.out.print(".");
}
}
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (head != null && head.next != null) {
ListNode first = head;
ListNode second = head.next;
prev.next = second;
first.next = second.next;
second.next = first;
prev = first;
head = first.next;
}
return dummy.next;
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
ListNode result = lists[0];
for (int i = 1; i < lists.length; i++) {
result = mergeTwoLists(result, lists[i]);
}
return result;
}
// 合并两个有序链表的方法
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
if (l1 != null) {
current.next = l1;
}
if (l2 != null) {
current.next = l2;
}
return dummy.next;
}
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
public ListNode detectCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
ListNode cur = head;
while (cur != null) {
if (!set.add(cur)) {
return cur;
}
cur = cur.next;
}
return null;
}
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode cur = head;
while (cur != null) {
boolean hasD = false;
while (cur.next != null && cur.val == cur.next.val) {
hasD = true;
cur = cur.next;
}
if (hasD) {
pre.next = cur.next;
} else {
pre = pre.next;
}
cur = cur.next;
}
return dummy.next;
}
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
// 找到链表中间节点
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 反转后半部分链表
ListNode secondHalf = reverseList(slow.next);
ListNode firstHalf = head;
// 比较两部分链表
while (secondHalf != null) {
if (firstHalf.val != secondHalf.val) {
return false;
}
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextNode = current.next;
current.next = prev;
prev = current;
current = nextNode;
}
return prev;
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA;
ListNode pB = headB;
while (pA != pB) {
pA = pA != null ? pA.next : headB;
pB = pB != null ? pB.next : headA;
}
return pA;
}
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 奇数链表的头节点
ListNode odd = head;
// 偶数链表的头节点
ListNode even = head.next;
// 保存偶数链表的头节点，用于后续连接
ListNode evenHead = even;
while (even != null && even.next != null) {
// 连接奇数节点
odd.next = even.next;
odd = odd.next;
// 连接偶数节点
even.next = odd.next;
even = even.next;
}
// 将偶数链表连接到奇数链表的末尾
odd.next = evenHead;
return head;
}
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = dummy;
while (current.next != null) {
if (current.next.val == val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return dummy.next;
}
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// 让 first 指针先移动 n + 1 步
for (int i = 0; i <= n; i++) {
first = first.next;
}
// 同时移动 first 和 second 指针
while (first != null) {
first = first.next;
second = second.next;
}
// 删除倒数第 n 个节点
second.next = second.next.next;
return dummy.next;
}
栈
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c: s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
stack.pop();
} else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
stack.pop();
} else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
stack.pop();
} else {
return false;
}
}
return stack.isEmpty();
}
public int trap(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int result = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
result += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
result += rightMax - height[right];
}
right--;
}
}
return result;
}
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
stack.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
right[i] = stack.isEmpty() ? n : stack.peek();
stack.push(i);
}
int maxArea = 0;
for (int i = 0; i < n; i++) {
maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
}
return maxArea;
}
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
stack.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
right[i] = stack.isEmpty() ? n : stack.peek();
stack.push(i);
}
int maxArea = 0;
for (int i = 0; i < n; i++) {
maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
}
return maxArea;
}
队列
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
public String minWindow(String s, String t) {
if (s == null || s.length() == 0 || t == null || t.length() == 0) {
return "";
}
int[] need = new int[128];
for (char c : t.toCharArray()) {
need[c]++;
}
int left = 0, right = 0, start = 0, minLen = Integer.MAX_VALUE, count = t.length();
while (right < s.length()) {
char c = s.charAt(right);
if (need[c] > 0) {
count--;
}
need[c]--;
right++;
while (count == 0) {
if (right - left < minLen) {
minLen = right - left;
start = left;
}
char leftChar = s.charAt(left);
need[leftChar]++;
if (need[leftChar] > 0) {
count++;
}
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
private int[] data;
private int front;
private int rear;
private int size;
public MyCircularDeque(int k) {
data = new int[k];
front = 0;
rear = 0;
size = 0;
}
public boolean insertFront(int value) {
if (isFull()) {
return false;
}
front = (front - 1 + data.length) % data.length;
data[front] = value;
size++;
return true;
}
public boolean insertLast(int value) {
if (isFull()) {
return false;
}
data[rear] = value;
rear = (rear + 1) % data.length;
size++;
return true;
}
public boolean deleteFront() {
if (isEmpty()) {
return false;
}
front = (front + 1) % data.length;
size--;
return true;
}
public boolean deleteLast() {
if (isEmpty()) {
return false;
}
rear = (rear - 1 + data.length) % data.length;
size--;
return true;
}
public int getFront() {
if (isEmpty()) {
return -1;
}
return data[front];
}
public int getRear() {
if (isEmpty()) {
return -1;
}
return data[(rear - 1 + data.length) % data.length];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == data.length;
}
双指针
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
// This line should never be reached since there is exactly one solution
return new int[]{-1, -1};
}
}
public List<List<Integer>> threeSum(int[] nums) {
// Initialize the result list to store the triplets
List<List<Integer>> result = new ArrayList<>();
// Sort the array in ascending order to simplify the process of finding triplets
Arrays.sort(nums);
// Iterate through the array, considering each element as a potential first element of a triplet
for (int i = 0; i < nums.length - 2; i++) {
// Skip duplicates for the first number to avoid duplicate triplets
if (i > 0 && nums[i] == nums[i - 1]) continue;
// Initialize two pointers, one at the next element and one at the end of the array
int left = i + 1;
int right = nums.length - 1;
// Calculate the target sum for the other two numbers
int target = -nums[i];
// Use two-pointer approach to find the other two numbers that sum up to the target
while (left < right) {
// Calculate the sum of the two numbers pointed by the left and right pointers
int sum = nums[left] + nums[right];
// If the sum is equal to the target, we found a triplet
if (sum == target) {
// Add the triplet to the result list
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// Skip duplicates for the second and third numbers
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
// Move the pointers to the next unique numbers
left++;
right--;
}
// If the sum is less than the target, move the left pointer to the right to increase the sum
else if (sum < target) {
left++;
}
// If the sum is greater than the target, move the right pointer to the left to decrease the sum
else {
right--;
}
}
}
// Return the list of triplets
return result;
}
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums); // Sort the array first
for (int i = 0; i < nums.length - 3; i++) {
// Skip duplicates for the first number
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length - 2; j++) {
// Skip duplicates for the second number
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = nums.length - 1;
long newTarget = (long) target - nums[i] - nums[j];
while (left < right) {
long sum = (long) nums[left] + nums[right];
if (sum == newTarget) {
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
// Skip duplicates for the third and fourth numbers
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < newTarget) {
left++;
} else {
right--;
}
}
}
}
return result;
}
public int removeElement(int[] nums, int val) {
int k = 0; // Initialize the pointer for the next position to place a non-val element
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[k] = nums[i]; // Place the non-val element at the next position
k++; // Move the pointer to the next position
}
}
return k; // Return the number of elements that are not equal to val
}
public boolean isPalindrome(String s) {
// Convert the string to lowercase and remove non-alphanumeric characters
String cleanString = s.toLowerCase().replaceAll("[^a-z0-9]", "");
// Check if the clean string is a palindrome
int left = 0;
int right = cleanString.length() - 1;
while (left < right) {
if (cleanString.charAt(left) != cleanString.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
public boolean isPalindrome(String s) {
String cleanStr = s.toLowerCase().replaceAll("[^a-z0-9]", "");
int left = 0;
int right = cleanStr.length() - 1;
while(left < right) {
if(cleanStr.charAt(left) != cleanStr.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
哈希表
public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[0];
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int com = target - nums[i];
if (map.containsKey(com)) {
return new int[]{map.get(com), i};
}
map.put(nums[i], i);
}
return new int[0];
}
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) {
return new ArrayList<>();
}
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
String sortedStr = new String(charArray);
if (!map.containsKey(sortedStr)) {
map.put(sortedStr, new ArrayList<>());
}
map.get(sortedStr).add(str);
}
return new ArrayList<>(map.values());
}
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) {
return new ArrayList<>();
}
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
String sortedStr = new String(charArray);
if (!map.containsKey(sortedStr)) {
map.put(sortedStr, new ArrayList<>());
}
map.get(sortedStr).add(str);
}
return new ArrayList<>(map.values());
}
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>();
while (n != 1 && !set.contains(n)) {
set.add(n);
n = getNext(n);
}
return n == 1;
}
private int getNext(int n) {
int total = 0;
while(n > 0) {
int digit = n % 10;
total += digit * digit;
n = n / 10;
}
return total;
}
public boolean canConstruct(String ransomNote, String magazine) {
int[] count = new int[26];
for (char c : magazine.toCharArray()) {
count[c - 'a']++;
}
for (char c : ransomNote.toCharArray()) {
if (--count[c - 'a'] < 0) {
return false;
}
}
return true;
}
public int firstUniqChar(String s) {
Map<Character, Integer> map = new HashMap<>();
char[] charArray = s.toCharArray();
for (char c : charArray) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
for (int i = 0; i < charArray.length; i++) {
if (map.get(charArray[i]) == 1) {
return i;
}
}
return -1;
}
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (!set.add(num)) {
return true;
}
}
return false;
}
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (map.containsKey(num) && i - map.get(num) <= k) {
return true;
}
map.put(num, i);
}
return false;
}
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
for (int num : nums1) {
set1.add(num);
}
Set<Integer> set2 = new HashSet<>();
for (int num : nums2) {
if (set1.contains(num)) {
set2.add(num;)
}
}
int[] result = new int[set2.size()];
int index = 0;
for (int num : set2) {
result[i++] = num;
}
return result;
}
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
for (int num : nums1) {
set1.add(num);
}
Set<Integer> set2 = new HashSet<>();
for (int num : nums2) {
if (set1.contains(num)) {
set2.add(num);
}
}
int[] result = new int[set2.size()];
int index = 0;
for (int num : set2) {
result[index++] = num;
}
return result;
}
前缀和
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] prefixSum = new int[n + 1];
prefixSum[0] = 0;
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
}
int minPrefixSum = 0;
int maxSubArraySum = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) {
maxSubArraySum = Math.max(maxSubArraySum, prefixSum[i] - minPrefixSum);
minPrefixSum = Math.min(minPrefixSum, prefixSum[i]);
}
return maxSubArraySum;
}
public int subarraySum(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
int count = 0;
int prefixNum = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int num: nums) {
prefixNum += num;
if (map.containsKey(prefixNum - k)) {
count += map.get(prefixNum - k);
}
map.put(prefixNum, map.getOrDefault(prefixNum, 0) + 1);
}
return count;
}
public int pivotIndex(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int total = 0;
for (int num: nums) {
total += num;
}
int left = 0;
for (int i = 0; i < nums.length; i++) {
if (left == total - left - nums[i]) {
return i;
}
left += nums[i];
}
return -1;
}
public int minSubArrayLen(int target, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int min = Integer.MAX_VALUE;
int left = 0;
int sum = 0;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
min = Math.min(min, right - left + 1);
sum -= nums[left];
left++;
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
二叉树
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorder(root, result);
return result;
}
private void preorder(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
result.add(node.val);
preorder(node.left, result);
preorder(node.right, result);
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorder(root, result);
return result;
}
private void inorder(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
inorder(node.left, result);
result.add(node.val);
inorder(node.right, result);
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorder(root, result);
return result;
}
private void inorder(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
inorder(node.left, result);
inorder(node.right, result);
result.add(node.val);
}
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int maxIndex = left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] > nums[maxIndex]) {
maxIndex = i;
}
}
TreeNode root = new TreeNode(nums[maxIndex]);
root.left = build(nums, left, maxIndex - 1);
root.right = build(nums, maxIndex + 1, right);
return root;
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.pollFirst();
currentLevel.add(node.val);
if (node.left != null) {
queue.offerLast(node.left);
}
if (node.right != null) {
queue.offerLast(node.right);
}
}
result.add(currentLevel);
}
return result;
}
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int minDepth = Integer.MAX_VALUE;
if (root.left != null) {
minDepth = Math.min(minDepth, minDepth(root.left));
}
if (root.right != null) {
minDepth = Math.min(minDepth, minDepth(root.right));
}
return minDepth + 1;
}
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
} else if (left != null) {
return left;
} else {
return right;
}
}
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
return (left.val == right.val) && isMirror(left.left, right.right) && isMirror(left.left, right.left);
}
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
private TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) {
return null;
}
int rootVal = postorder[postEnd];
TreeNode root = new TreeNode(rootVal);
int rootIndexInorder = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndexInorder = i;
break;
}
}
int leftSubtreeSize = rootIndexInorder - inStart;
root.left = build(inorder, inStart, rootIndexInorder - 1, postorder, postStart, postStart + leftSubtreeSize - 1);
root.right = build(inorder, rootIndexInorder + 1, inEnd, postorder, postStart + leftSubtreeSize, postEnd - 1);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
int rootIndexInorder = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndexInorder = i;
break;
}
}
int leftSubtreeSize = rootIndexInorder - inStart;
root.left = build(preorder, preStart + 1, preStart + leftSubtreeSize, inorder, inStart, rootIndexInorder - 1);
root.right = build(preorder, preStart + leftSubtreeSize + 1, preEnd, inorder, rootIndexInorder + 1, inEnd);
return root;
}