1. 经典暴力破解题型
1.1 枚举所有子数组（前缀和优化）
问题： 给定一个整数数组 arr，求出所有子数组的和。
方法 1：暴力解法
时间复杂度：O(n^3)
for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {int sum = 0;for (int k = i; k <= j; k++) {sum += arr[k];}}
}
方法 2：前缀和优化
时间复杂度：O(n^2)
int[] preSum = new int[n + 1];
for (int i = 1; i <= n; i++) {preSum[i] = preSum[i - 1] + arr[i - 1];
}
for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {int sum = preSum[j + 1] - preSum[i];}
}
📌 优化方向：
- 前缀和 可以将 O(n^3) 降至 O(n^2)，进一步优化可使用滑动窗口（仅适用于正数数组）。
- 分治法 也可用于求解最大子数组和，时间复杂度 O(nlogn)。
1.2 全排列 & 组合（回溯）
问题： 给定 n 个数，找出所有可能的排列方式。
全排列（时间复杂度：O(n!)）
static void permute(int[] nums, List<Integer> path, boolean[] used) {if (path.size() == nums.length) {res.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (!used[i]) {used[i] = true;path.add(nums[i]);permute(nums, path, used);path.remove(path.size() - 1);used[i] = false;}}
}
组合（时间复杂度：O(2^n)）
static void combine(int[] nums, int k, int start, List<Integer> path) {if (path.size() == k) {res.add(new ArrayList<>(path));return;}for (int i = start; i < nums.length; i++) {path.add(nums[i]);combine(nums, k, i + 1, path);path.remove(path.size() - 1);}
}
📌 优化方向：
- 剪枝（如不必要的递归调用）可以减少不必要的计算。
- 使用位运算生成所有子集。
1.3 二维网格暴力搜索（DFS）
问题： 迷宫问题，找出所有可能的路径。
public static void dfs(int[][] maze, int x, int y, boolean[][] visited) {if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length || visited[x][y] || maze[x][y] == 1) return;visited[x][y] = true;dfs(maze, x + 1, y, visited);dfs(maze, x - 1, y, visited);dfs(maze, x, y + 1, visited);dfs(maze, x, y - 1, visited);visited[x][y] = false;
}
📌 优化方向：
- BFS 可用于最短路径求解，适用于无权图。
- A*搜索 提供更高效的路径搜索。
1.4 暴力匹配（字符串匹配）
问题： 给定两个字符串 s 和 t，判断 t 是否是 s 的子串。
public static int bruteForceSearch(String s, String t) {int n = s.length(), m = t.length();for (int i = 0; i <= n - m; i++) {int j;for (j = 0; j < m; j++) {if (s.charAt(i + j) != t.charAt(j)) break;}if (j == m) return i;}return -1;
}
📌 优化方向：
- KMP 算法 预处理
next数组，降低复杂度至 O(n+m)。 - Boyer-Moore 算法 适用于大文本匹配，平均复杂度 O(n/m)。
2. 位运算基础知识
2.1 常见位运算操作
&（按位与）：a & b|（按位或）：a | b^（按位异或）：a ^ b~（按位取反）：~a<<（左移）：a << 1>>（右移）：a >> 1
2.2 位运算技巧
- 判断奇偶：
x & 1 == 1（奇数），x & 1 == 0（偶数） - 交换两数：
a ^= b; b ^= a; a ^= b; - 判断某一位是否为1：
(x >> k) & 1 - 快速计算 2 的幂次：
1 << k
📌 应用场景：
- 位运算加速：如位运算优化子集生成。
- 哈希函数优化。
3. 日期处理相关知识点
3.1 日期格式化
String formattedDate = String.format("%04d-%02d-%02d", year, month, day);
3.2 判断闰年
static boolean isLeapYear(int year) {return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}
3.3 判断合法日期
static boolean isValidDate(int year, int month, int day) {if (month < 1 || month > 12 || day < 1) return false;int[] daysInMonth = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};if (month == 2 && isLeapYear(year)) daysInMonth[2] = 29;return day <= daysInMonth[month];
}
📌 应用场景：
- 计算年龄差异。
- 处理时间戳转换。
4. 结论
- 暴力破解适用于小规模问题，大规模问题需要优化。
- 尽可能优化，如前缀和、位运算、剪枝等。
- 多练习不同类型的暴力破解题目，逐步优化解法！ 🚀