双指针 (Two Pointers)
▼1. 有序数组的Two Sum
▼问题描述： 在有序数组中找出两个数，使它们的和为target。
解题思路： 使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
复杂度分析
时间复杂度： O(N)
空间复杂度： O(1)
Java 代码实现
public int[] twoSum(int[] numbers, int target) {
if (numbers == null) return null;
int i = 0, j = numbers.length - 1;
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum == target) {
return new int[]{i + 1, j + 1};
} else if (sum < target) {
i++;
} else {
j--;
}
}
return null;
}排序 (Sorting)
▼1. Kth Element
▼问题描述： 找到数组中第k大的元素。
解题思路： 使用快速排序的划分思想，每次划分后确定一个元素的最终位置。
复杂度分析
时间复杂度： O(N)
空间复杂度： O(1)
Java 代码实现
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0) return -1;
return findKthElement(nums, 0, nums.length - 1, nums.length - k);
}
private int findKthElement(int[] nums, int left, int right, int k) {
if (left >= right) return nums[left];
int pivotIndex = partition(nums, left, right);
if (pivotIndex == k) {
return nums[pivotIndex];
} else if (pivotIndex < k) {
return findKthElement(nums, pivotIndex + 1, right, k);
} else {
return findKthElement(nums, left, pivotIndex - 1, k);
}
}
private int partition(int[] nums, int left, int right) {
int pivot = nums[right];
int i = left;
for (int j = left; j < right; j++) {
if (nums[j] <= pivot) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, right);
return i;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}贪心思想 (Greedy)
▼1. 分配饼干
▼问题描述： 每个孩子都有一个满足度grid，每个饼干都有一个大小size，只有饼干的大小大于等于一个孩子的满足度，该孩子才会获得满足。求解最多可以获得满足的孩子数量。
解题思路： 给一个孩子的饼干应当尽量小并且又能满足该孩子，这样大饼干才能拿来给满足度比较大的孩子。因为满足度最小的孩子最容易得到满足，所以先满足满足度最小的孩子。
复杂度分析
时间复杂度： O(nlogn)
空间复杂度： O(1)
Java 代码实现
public int findContentChildren(int[] grid, int[] size) {
if (grid == null || size == null) return 0;
Arrays.sort(grid);
Arrays.sort(size);
int gi = 0, si = 0;
while (gi < grid.length && si < size.length) {
if (grid[gi] <= size[si]) {
gi++;
}
si++;
}
return gi;
}二分查找 (Binary Search)
▼1. 求开方
▼问题描述： 求一个数的开方。
解题思路： 一个数x的开方sqrt一定在0~x之间，并且满足sqrt == x / sqrt。
复杂度分析
时间复杂度： O(logx)
空间复杂度： O(1)
Java 代码实现
public int mySqrt(int x) {
if (x <= 1) {
return x;
}
int l = 1, h = x;
while (l <= h) {
int mid = l + (h - l) / 2;
int sqrt = x / mid;
if (sqrt == mid) {
return mid;
} else if (mid > sqrt) {
h = mid - 1;
} else {
l = mid + 1;
}
}
return h;
}分治 (Divide and Conquer)
▼1. 不同的二叉搜索树
▼问题描述： 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种。
解题思路： 使用递归的方式，假设以 i 为根节点，则左子树由 1...i-1 组成，右子树由 i+1...n 组成。
复杂度分析
时间复杂度： O(N³)
空间复杂度： O(N)
Java 代码实现
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];
}搜索 (Search)
▼1. 计算在网格中从原点到特定点的最短路径长度
▼问题描述： 计算在网格中从原点到特定点的最短路径长度。
解题思路： 使用广度优先搜索(BFS)，每次移动可以到达相邻的四个节点。
复杂度分析
时间复杂度： O(MN)
空间复杂度： O(MN)
Java 代码实现
public int shortestPath(int[][] grid, int K) {
int m = grid.length, n = grid[0].length;
int[][][] visited = new int[m][n][K + 1];
Queue queue = new LinkedList<>();
queue.offer(new int[]{0, 0, 0, 0}); // x, y, obstacles, distance
int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int x = cur[0], y = cur[1], used = cur[2], dist = cur[3];
if (x == m - 1 && y == n - 1) return dist;
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
int nused = used + grid[nx][ny];
if (nused > K) continue;
if (visited[nx][ny][nused] == 0) {
visited[nx][ny][nused] = 1;
queue.offer(new int[]{nx, ny, nused, dist + 1});
}
}
}
return -1;
} 动态规划 (Dynamic Programming)
▼1. 爬楼梯
▼问题描述： 有N阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。
解题思路： 定义一个数组dp存储上楼梯的方法数，dp[i]表示走到第i个楼梯的方法数。
复杂度分析
时间复杂度： O(N)
空间复杂度： O(1)
Java 代码实现
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int pre2 = 1, pre1 = 2;
for (int i = 2; i < n; i++) {
int cur = pre1 + pre2;
pre2 = pre1;
pre1 = cur;
}
return pre1;
}数学 (Math)
▼1. 生成素数序列
▼问题描述： 给定一个正整数 n，返回小于或等于 n 的所有素数。
解题思路： 使用埃拉托斯特尼筛选法，首先假设所有数字都是素数，然后依次标记非素数。
复杂度分析
时间复杂度： O(NloglogN)
空间复杂度： O(N)
Java 代码实现
public int countPrimes(int n) {
boolean[] isPrime = new boolean[n];
for (int i = 2; i < n; i++) {
isPrime[i] = true;
}
for (int i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) count++;
}
return count;
}链表 (Linked List)
▼1. 链表反转
▼问题描述： 反转链表。
解题思路： 使用头插法，每次将当前节点插入到新链表的头部。
复杂度分析
时间复杂度： O(N)
空间复杂度： O(1)
Java 代码实现
public ListNode reverseList(ListNode head) {
ListNode newHead = new ListNode(-1);
while (head != null) {
ListNode next = head.next;
head.next = newHead.next;
newHead.next = head;
head = next;
}
return newHead.next;
}树 (Tree)
▼1. 树的高度
▼问题描述： 求二叉树的最大深度。
解题思路： 使用递归，树的深度等于左右子树深度的最大值加一。
复杂度分析
时间复杂度： O(N)
空间复杂度： O(H)
Java 代码实现
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}栈和队列 (Stack and Queue)
▼1. 用栈实现队列
▼问题描述： 使用栈实现队列的 push 和 pop 操作。
解题思路： 使用两个栈，一个用于输入，一个用于输出。当输出栈为空时，将输入栈的所有元素弹出并压入输出栈。
复杂度分析
时间复杂度： O(1)
空间复杂度： O(N)
Java 代码实现
class MyQueue {
private Stack in = new Stack<>();
private Stack out = new Stack<>();
public void push(int x) {
in.push(x);
}
public int pop() {
if (out.isEmpty()) {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
return out.pop();
}
public int peek() {
if (out.isEmpty()) {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
return out.peek();
}
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
} 哈希表 (Hash Table)
▼1. 数组中两个数的和为给定值
▼问题描述： 在数组中找出两个数，它们的和为target。
解题思路： 使用哈希表记录已经遍历过的数字，对于当前数字，检查 target - nums[i] 是否在哈希表中。
复杂度分析
时间复杂度： O(N)
空间复杂度： O(N)
Java 代码实现
public int[] twoSum(int[] nums, int target) {
HashMap indexForNum = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (indexForNum.containsKey(target - nums[i])) {
return new int[]{indexForNum.get(target - nums[i]), i};
} else {
indexForNum.put(nums[i], i);
}
}
return null;
} 字符串 (String)
▼1. 字符串同构
▼问题描述： 判断两个字符串是否同构。
解题思路： 记录每个字符在字符串中上一次出现的位置，如果两个字符串中相同字符上次出现的位置相同，则它们是同构的。
复杂度分析
时间复杂度： O(N)
空间复杂度： O(1)
Java 代码实现
public boolean isIsomorphic(String s, String t) {
int[] preIndexOfS = new int[256];
int[] preIndexOfT = new int[256];
for (int i = 0; i < s.length(); i++) {
char sc = s.charAt(i), tc = t.charAt(i);
if (preIndexOfS[sc] != preIndexOfT[tc]) {
return false;
}
preIndexOfS[sc] = i + 1;
preIndexOfT[tc] = i + 1;
}
return true;
}数组与矩阵 (Array and Matrix)
▼1. 把数组中的0移到末尾
▼问题描述： 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
解题思路： 使用双指针，一个指针用于遍历数组，另一个指针指向当前应该放置非零元素的位置。
复杂度分析
时间复杂度： O(N)
空间复杂度： O(1)
Java 代码实现
public void moveZeroes(int[] nums) {
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[index++] = nums[i];
}
}
while (index < nums.length) {
nums[index++] = 0;
}
}图 (Graph)
▼1. 判断是否为二分图
▼问题描述： 判断一个图是否为二分图。
解题思路： 使用BFS或DFS遍历图，为每个节点分配颜色，相邻节点必须分配不同的颜色。
复杂度分析
时间复杂度： O(V+E)
空间复杂度： O(V)
Java 代码实现
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] colors = new int[n];
for (int i = 0; i < n; i++) {
if (colors[i] == 0) {
if (!isValidColor(graph, colors, i, 1)) {
return false;
}
}
}
return true;
}
private boolean isValidColor(int[][] graph, int[] colors, int node, int color) {
if (colors[node] != 0) {
return colors[node] == color;
}
colors[node] = color;
for (int neighbor : graph[node]) {
if (!isValidColor(graph, colors, neighbor, -color)) {
return false;
}
}
return true;
}位运算 (Bit Manipulation)
▼1. 数组中唯一一个不重复的元素
▼问题描述： 找出数组中只出现一次的元素，其他元素都出现两次。
解题思路： 使用异或运算，相同数字异或结果为0，任何数字与0异或都等于它本身。
复杂度分析
时间复杂度： O(N)
空间复杂度： O(1)
Java 代码实现
public int singleNumber(int[] nums) {
int ret = 0;
for (int n : nums) ret ^= n;
return ret;
}