本文最后更新于 458 天前,其中的信息可能已经有所发展或是发生改变。
- 排列
- 原理就是
C++
中的 next_permutation
函数,生成指定序列的下一个全排列
- 从给定序列的最右端开始,找到第一个满足
nums[i] < nums[i + 1]
的元素 nums[i]
- 若找不到这样的元素
nums[i]
:说明当前序列是最后一个排列,函数将序列重排为第一个排列,并返回 false
- 若找到了元素
nums[i]
:继续从最右端开始,找到第一个满足 nums[i] < nums[j]
的元素 nums[j]
。
- 交换
nums[i]
和 nums[j]
,然后从 i + 1
开始将序列反转,使得它们按照升序排列。
| class Solution { |
| public void nextPermutation(int[] nums) { |
| int n = nums.length; |
| int i = n - 2; |
| while (i >= 0 && nums[i] >= nums[i + 1]) i --; |
| if (i >= 0) { |
| int j = n - 1; |
| while (nums[j] <= nums[i]) j --; |
| swap(nums, i, j); |
| } |
| reverse(nums, i + 1, n - 1); |
| } |
| |
| private void swap(int[] nums, int i, int j) { |
| int t = nums[i]; |
| nums[i] = nums[j]; |
| nums[j] = t; |
| } |
| |
| private void reverse(int[] nums, int l, int r) { |
| while (l < r) { |
| this.swap(nums, l, r); |
| l ++; r --; |
| } |
| } |
| |
| } |
- 栈
- 用
Stack<Integer>
存储所有 (
的下标
- 当遇到右括号时,检查栈是否为空:
- 若栈为空,则说明当前右括号没有匹配的左括号,将当前右括号的位置作为新的起始位置。
- 若不为空,则弹出栈顶元素,并更新当前有效括号的长度(当前右括号的位置减去栈顶元素的值)
- 遍历完字符串后,得到最长有效括号的长度
| class Solution { |
| public int longestValidParentheses(String s) { |
| Stack<Integer> stack = new Stack<>(); |
| int ans = 0; |
| int start = -1; |
| |
| for (int i = 0; i < s.length(); i++) { |
| |
| if (s.charAt(i) == '(') stack.push(i); |
| else { |
| if (stack.isEmpty()) { |
| start = i; |
| } |
| else { |
| stack.pop(); |
| |
| if (stack.isEmpty()) ans = Math.max(ans, i - start); |
| else ans = Math.max(ans, i - stack.peek()); |
| } |
| } |
| } |
| |
| return ans; |
| } |
| } |
优化:
- 模拟
- 设当前的括号出现的次数
res
,第一次扫代表 (
,起始位置 l = 0
,第二次扫代表 )
,起始位置 r = n - 1
- 先从左往右扫一遍,若为
(
,res ++
;
- 当遇到
)
时:
- 若
res == 0
,则更新最长有效括号的长度 ans
,并更新起始位置 l
- 否则:说明匹配,
res --
,若此时 res == 0
,则匹配了全部左括号,更新 ans
- 第一遍扫完后,判断是否还有未匹配的左括号。如果没有或者最长有效括号的长度
ans
已经大于等于剩余未匹配左括号的长度(n - l),则直接返回 ans
。
- 如果还有未匹配的左括号,说明可能出现以右括号结尾的有效括号序列。再从右往左扫第二遍,步骤是一样的。
- 最终返回最长有效括号的长度
ans
。
| class Solution { |
| public int longestValidParentheses(String s) { |
| int res = 0; |
| int n = s.length(); |
| int ans = 0, l = 0; |
| |
| for (int i = 0; i < n; i ++) { |
| if (s.charAt(i) == '(') { |
| res ++; continue; |
| } |
| |
| if (res == 0) { |
| ans = Math.max(ans, i - l); |
| l = i + 1; |
| } |
| else { |
| res --; |
| if (res == 0) ans = Math.max(ans, i - l + 1); |
| } |
| } |
| |
| if (res == 0 || ans >= n - l) return ans; |
| |
| int r = n - 1; res = 0; |
| |
| for (int i = n - 1; i > l; i --) { |
| if (s.charAt(i) == ')') { |
| res ++; continue; |
| } |
| if (res == 0) { |
| ans = Math.max(ans, r - i); |
| r = i - 1; |
| } |
| else |
| res --; |
| if (res == 0) ans = Math.max(ans, r - i + 1); |
| } |
| } |
| |
| return ans; |
| } |
| } |
- 二分
- 显然,在旋转点的左侧满足
nums[i] >= nums[0]
,而右侧 nums[i] < nums[0]
- 根据上述的单调性我们第一次二分找到旋转点的位置
- 然后判断
target
在旋转点的左半部分还是右半部分
- 显然,当
target >= nums[0]
时在左半部分
- 然后继续二分,更新
l, r
为新的目标区间继续查找
| class Solution { |
| public int search(int[] nums, int target) { |
| int n = nums.length; |
| if (n == 1) return nums[0] == target ? 0 : -1; |
| int l = 0, r = n - 1; |
| |
| while (l <= r) { |
| int mid = (l + r) >> 1; |
| if (nums[mid] == target) return mid; |
| if (nums[mid] >= nums[0]) l = mid + 1; |
| else r = mid - 1; |
| } |
| if (l < n && nums[l] == target) return l; |
| |
| if (target >= nums[0]) { |
| r = l - 1; l = 0; |
| } |
| else { |
| l ++; r = n - 1; |
| } |
| |
| while (l <= r) { |
| int mid = (l + r) >> 1; |
| if (nums[mid] == target) return mid; |
| if (nums[mid] < target) l = mid + 1; |
| else r = mid - 1; |
| } |
| return l < n && nums[l] == target ? l : -1; |
| } |
| } |
- 二分
- 数组已从小到大排序,满足单调性
- 第一遍二分寻找第一个小于
target
的数,期间更新 nums[mid] == target
的下标,即为第一个位置
- 第二遍二分寻找第一个大于
target
的数,期间更新 nums[mid] == target
的下标,即为第二个位置
| class Solution { |
| public int[] searchRange(int[] nums, int target) { |
| int n = nums.length; |
| int l = 0, r = n - 1; |
| int res = -1; |
| while (l <= r) { |
| int mid = (l + r) >> 1; |
| if (nums[mid] == target) res = mid; |
| if (nums[mid] < target) l = mid + 1; |
| else r = mid - 1; |
| } |
| if (res == -1) return new int[]{-1, -1}; |
| l = res; r = n - 1; |
| int cnt = -1; |
| while (l <= r) { |
| int mid = (l + r) >> 1; |
| if (nums[mid] == target) cnt = mid; |
| if (nums[mid] > target) r = mid - 1; |
| else l = mid + 1; |
| } |
| return new int[]{res, cnt}; |
| } |
| } |
| class Solution { |
| public int searchInsert(int[] nums, int target) { |
| int l = 0, r = nums.length - 1; |
| while (l <= r) { |
| int mid = (l + r) >> 1; |
| if (nums[mid] == target) return mid; |
| if (nums[mid] < target) l = mid + 1; |
| else r = mid - 1; |
| } |
| return l; |
| } |
| } |
- 模拟
- 只需要验证已有的数是否符号规则就行,因此我们可以用
区区十几个循环嵌套来解决
- 首先将数独按照 3×3 分为 9 组,然后用
boolean[][]
维护每组格子的状态
- 具体滴,对于格子
board[i][j]
,所在的组编号 u
映射为 u = i / 3 * 3 + j / 3
- 则
boolean[][] vis[u][num]
表示第 u
组数字 num
是否已经存在
- 那么除此之外,还需要判断行和列的格子的状态即可
| class Solution { |
| public boolean isValidSudoku(char[][] board) { |
| boolean[][] vis = new boolean[10][10]; |
| boolean[][] row = new boolean[10][10]; |
| boolean[][] col = new boolean[10][10]; |
| |
| for (int i = 0; i < 9; i ++) { |
| for (int j = 0; j < 9; j ++) { |
| char t = board[i][j]; |
| if (t == '.') continue; |
| int num = t - '0'; |
| |
| int u = i / 3 * 3 + j / 3; |
| |
| if (vis[u][num] || row[i][num] || col[j][num]) return false; |
| vis[u][num] = row[i][num] = col[j][num] = true; |
| } |
| } |
| return true; |
| } |
| } |
- DFS
- 对于
board[i][j]
从 1∼9 暴力搜索每一个可能的值
- 难点仍是在于判断是否合法,思路同上一题
| class Solution { |
| public void solveSudoku(char[][] board) { |
| boolean[][] vis = new boolean[10][10]; |
| boolean[][] row = new boolean[10][10]; |
| boolean[][] col = new boolean[10][10]; |
| init(board, vis, row, col); |
| dfs(board, 0, 0, vis, row, col); |
| } |
| |
| private boolean dfs(char[][] board, int i, int j, boolean[][] vis, |
| boolean[][] row, boolean[][] col) { |
| if (i == 9) return true; |
| if (j == 9) return dfs(board, i + 1, 0, vis, row, col); |
| if (board[i][j] != '.') return dfs(board, i, j + 1, vis, row, col); |
| |
| for (int num = 1; num <= 9; num ++) { |
| int idx = i / 3 * 3 + j / 3; |
| if (!vis[idx][num] && !row[i][num] && !col[j][num]) { |
| vis[idx][num] = row[i][num] = col[j][num] = true; |
| board[i][j] = (char)(num + '0'); |
| if (dfs(board, i, j + 1, vis, row, col)) return true; |
| |
| vis[idx][num] = row[i][num] = col[j][num] = false; |
| board[i][j] = '.'; |
| } |
| } |
| return false; |
| } |
| |
| private void init(char[][] board, boolean[][] vis, |
| boolean[][] row, boolean[][] col) { |
| for (int i = 0; i < 9; i ++) { |
| for (int j = 0; j < 9; j ++) { |
| if (board[i][j] != '.') { |
| int num = board[i][j] - '0'; |
| int idx = i / 3 * 3 + j / 3; |
| vis[idx][num] = row[i][num] = col[j][num] = true; |
| } |
| } |
| } |
| } |
| } |
- DFS
- 递归的每一层,对上一层生成的
s
进行遍历
- 用
char flag
记录当前的字符,cnt
记录当前字符的数量
- 用
StringBuilder sb
来接收对 s
的描述并且继续搜索
| class Solution { |
| public String countAndSay(int n) { |
| return dfs(n, 1, "1"); |
| } |
| |
| private String dfs(int n, int u, String s) { |
| if (u == n) return s; |
| StringBuilder sb = new StringBuilder(); |
| int cnt = 0; |
| char flag = s.charAt(0); |
| for (int i = 0; i < s.length(); i ++) { |
| if (s.charAt(i) == flag) cnt ++; |
| else { |
| |
| sb.append(cnt); sb.append(flag); |
| flag = s.charAt(i); cnt = 1; |
| } |
| } |
| |
| sb.append(cnt); sb.append(flag); |
| return dfs(n, u + 1, sb.toString()); |
| } |
| } |
- DFS
- 首先对
candidates
从小到大排序
- 递归的每一层视作对
candidates[i]
的选择
- 由于数组是从小到大单调的,当
cnt + candidates[i] > target
即可不用在向后遍历
| class Solution { |
| public List<List<Integer>> combinationSum(int[] candidates, int target) { |
| Arrays.sort(candidates); |
| List<List<Integer>> ans = new ArrayList<>(); |
| List<Integer> res = new ArrayList<>(); |
| dfs(candidates, target, 0, 0, res, ans); |
| return ans; |
| } |
| |
| private void dfs(int[] candidates, int target, int u, int cnt, |
| List<Integer> res, List<List<Integer>> ans) { |
| if (cnt == target) { |
| ans.add(new ArrayList<>(res)); |
| return ; |
| } |
| |
| for (int i = u; i < candidates.length; i ++) { |
| if (cnt + candidates[i] <= target) { |
| res.add(candidates[i]); |
| dfs(candidates, target, i, cnt + candidates[i], res, ans); |
| res.remove(res.size() - 1); |
| } |
| else break; |
| } |
| } |
| } |
- DFS
- 和上一题思路一样,不同的是不能包含重复选择
- 有两种方式:
- 添加
HashSet<Integer> vis
标记使用过的数
- 在选择时加一层判断
candidates[i] == candidates[i - 1]
时跳过
| class Solution { |
| public List<List<Integer>> combinationSum2(int[] candidates, int target) { |
| Arrays.sort(candidates); |
| List<List<Integer>> ans = new ArrayList<>(); |
| List<Integer> res = new ArrayList<>(); |
| dfs(candidates, target, 0, 0, res, ans); |
| return ans; |
| } |
| |
| private void dfs(int[] candidates, int target, int u, int cnt, |
| List<Integer> res, List<List<Integer>> ans) { |
| if (cnt == target) { |
| ans.add(new ArrayList<>(res)); |
| return ; |
| } |
| for (int i = u; i < candidates.length; i ++) { |
| if (i > u && candidates[i] == candidates[i - 1]) continue; |
| if (cnt + candidates[i] <= target) { |
| res.add(candidates[i]); |
| dfs(candidates, target, i + 1, cnt + candidates[i], res, ans); |
| res.remove(res.size() - 1); |
| } |
| else break; |
| } |
| } |
| } |
<<<<<<< HEAD
- 模拟
- 将数组本身视作哈希表
- 预处理
nums[i] <= 0 || nums[i] > n
的值为 n + 1
,表示不存在
- 将出现的正数对应的位置标记为负数,通过改变正数对应位置上的符号来标记该位置所对应的数值已经出现过
- 最后,遍历找到第一个为正数的位置,即为缺失的最小正整数。
| class Solution { |
| public int firstMissingPositive(int[] nums) { |
| int n = nums.length; |
| |
| for (int i = 0; i < n; i ++) { |
| if (nums[i] <= 0 || nums[i] > n) nums[i] = n + 1; |
| } |
| |
| |
| for (int i = 0; i < n; i ++) { |
| int num = Math.abs(nums[i]); |
| if (num <= n) nums[num - 1] = -Math.abs(nums[num - 1]); |
| } |
| |
| |
| for (int i = 0; i < n; i ++) { |
| if (nums[i] > 0) return i + 1; |
| } |
| |
| |
| return n + 1; |
| } |
| } |
- 单调栈
- 维护
height[i]
之前出现过的最高的挡板
- 对于
height[i] < height[st.peek()]
说明后面可能存在更高的挡板
- 否则应当结算之前所接到的雨水
| class Solution { |
| public int trap(int[] height) { |
| Stack<Integer> st = new Stack<>(); |
| int ans = 0; |
| for (int i = 0; i < height.length; i++) { |
| if (!st.isEmpty() && height[i] > height[st.peek()]) { |
| int t = st.pop(); |
| if (st.isEmpty()) break; |
| int l = i - st.peek() - 1; |
| int r = Math.min(height[i], height[st.peek()]) - height[t]; |
| ans += l * r; |
| } |
| st.push(i); |
| } |
| return ans; |
| } |
| } |
| class Solution { |
| 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[] res = new int[m + n]; |
| for (int i = m - 1; i >= 0; i--) { |
| int x = num1.charAt(i) - '0'; |
| for (int j = n - 1; j >= 0; j--) { |
| int y = num2.charAt(j) - '0'; |
| res[i + j + 1] += x * y; |
| } |
| } |
| int base = 0; |
| for (int i = m + n - 1; i >= 0; i--) { |
| int sum = res[i] + base; |
| res[i] = sum % 10; |
| base = sum / 10; |
| } |
| StringBuilder sb = new StringBuilder(); |
| for (int num : res) sb.append(num); |
| while (sb.length() > 0 && sb.charAt(0) == '0') sb.deleteCharAt(0); |
| return sb.toString(); |
| } |
| } |
- dp
- 第二题青春版
- 状态表示:
- 设
dp[i][j]
表示字符串 s
的前 i
个字符和字符串 p
的前 j
个字符是否匹配。
- 初始化
dp[0][0]
为 true
,表示空字符串和空模式是匹配的。
- 初始化所有
*
之前的状态为 true
,因为 *
可以匹配空字符串。
-
状态计算:
- 如果
p
的当前字符是 *
,则可以选择匹配空字符串 dp[i][j-1]
或者匹配多个字符 dp[i-1][j]
,只要有一个为 true
,则 dp[i][j]
也为 true
。
- 如果
p
的当前字符是 ?
,或者 p
的当前字符和 s
的当前字符相等,则将 dp[i][j] = dp[i-1][j-1]
,表示当前位置的匹配状态与前一个位置的匹配状态相同。
- 否则,
dp[i][j]
为 false
,表示当前位置的字符不匹配。
| class Solution { |
| public boolean isMatch(String s, String p) { |
| int n = s.length(), m = p.length(); |
| boolean[][] dp = new boolean[n + 1][m + 1]; |
| dp[0][0] = true; |
| |
| for (int i = 1; i <= m; i ++) { |
| if (p.charAt(i - 1) == '*') dp[0][i] = true; |
| else break; |
| } |
| for (int i = 1; i <= n; i ++) { |
| for (int j = 1; j <= m; j ++) { |
| if (p.charAt(j - 1) == '*') dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; |
| else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1]; |
| } |
| } |
| return dp[n][m]; |
| } |
| } |
- 贪心
- 对于当前所处的位置
i
,当 i + nums[i] >= n - 1
时可以直接返回结果
- 否则,从
j = i
遍历到 j = i + nums[i]
,设下一步的位置为 res
,以 res
能到达的最远位置为 idx
- 显然,
j + nums[j]
即为下一步可以到达的最远位置 idx
- 则只需找到
j + nums[j]
的最大值,并用 res
维护下一步的坐标 j
即可
| class Solution { |
| public int jump(int[] nums) { |
| int ans = 0, n = nums.length; |
| if(n <= 1) return 0; |
| for(int i = 0; i < n; i ++){ |
| int res = 0, idx = 0; |
| if(i + nums[i] >= n - 1) return ans + 1; |
| for(int j = i + 1; j <= i + nums[i]; j ++){ |
| if(j + nums[j] >= idx){ |
| idx = j + nums[j]; |
| res = j; |
| } |
| } |
| i = res - 1; ans ++; |
| } |
| return ans; |
| } |
| } |
- 排列
- [31. 下一个排列](#31. 下一个排列) 题无修版(
- 先将给出的数组按照从小到大排序,以最小字典序寻找下一个全排列
- 找不到全排列直接返回
| class Solution { |
| public List<List<Integer>> permute(int[] nums) { |
| Arrays.sort(nums); |
| List<List<Integer>> ans = new ArrayList<>(); |
| ans.add(this.asList(nums)); |
| while (nextPermutation(nums)) ans.add(this.asList(nums)); |
| return ans; |
| } |
| |
| public boolean nextPermutation(int[] nums) { |
| int n = nums.length, i = n - 2; |
| while (i >= 0 && nums[i] >= nums[i + 1]) i --; |
| if (i >= 0) { |
| int j = n - 1; |
| while (nums[j] <= nums[i]) j --; |
| swap(nums, i, j); |
| this.reverse(nums, i + 1, n - 1); |
| return true; |
| } |
| else return false; |
| } |
| |
| private void swap(int[] nums, int i, int j) { |
| int t = nums[i]; |
| nums[i] = nums[j]; nums[j] = t; |
| } |
| |
| private void reverse(int[] nums, int l, int r) { |
| while (l < r) { |
| this.swap(nums, l, r); |
| l ++; r --; |
| } |
| } |
| |
| private List<Integer> asList(int[] nums) { |
| List<Integer> res = new ArrayList<>(); |
| for (int num : nums) res.add(num); |
| return res; |
| } |
| } |
| class Solution { |
| public List<List<Integer>> permuteUnique(int[] nums) { |
| Arrays.sort(nums); |
| List<List<Integer>> ans = new ArrayList<>(); |
| ans.add(this.asList(nums)); |
| while (nextPermutation(nums)) ans.add(this.asList(nums)); |
| return ans; |
| } |
| |
| public boolean nextPermutation(int[] nums) { |
| int n = nums.length, i = n - 2; |
| while (i >= 0 && nums[i] >= nums[i + 1]) i --; |
| if (i >= 0) { |
| int j = n - 1; |
| while (nums[j] <= nums[i]) j --; |
| swap(nums, i, j); |
| this.reverse(nums, i + 1, n - 1); |
| return true; |
| } |
| else return false; |
| } |
| |
| private void swap(int[] nums, int i, int j) { |
| int t = nums[i]; |
| nums[i] = nums[j]; nums[j] = t; |
| } |
| |
| private void reverse(int[] nums, int l, int r) { |
| while (l < r) { |
| this.swap(nums, l, r); |
| l ++; r --; |
| } |
| } |
| |
| private List<Integer> asList(int[] nums) { |
| List<Integer> res = new ArrayList<>(); |
| for (int num : nums) res.add(num); |
| return res; |
| } |
| } |
- 矩阵转置
- 用线性代数的知识,先将矩阵转置,再翻转即可
- 将矩阵 A 的行换成同序数的列得到的新的矩阵,叫做 A 的转置矩阵,记作: AT。
- 转置运算公式:
)
| class Solution { |
| public void rotate(int[][] matrix) { |
| int n = matrix.length; |
| |
| for (int i = 0; i < n; i ++) { |
| for (int j = i; j < n; j ++) { |
| int temp = matrix[i][j]; |
| matrix[i][j] = matrix[j][i]; |
| matrix[j][i] = temp; |
| } |
| } |
| |
| for (int i = 0; i < n; i ++) { |
| for (int j = 0; j < n / 2; j ++) { |
| int temp = matrix[i][j]; |
| matrix[i][j] = matrix[i][n - 1 - j]; |
| matrix[i][n - 1 - j] = temp; |
| } |
| } |
| } |
| } |
- 哈希表
- 对于
strs[i]
将其按照字典序排序并映射下标,保存到 HashMap
中
- 每次找到相同的排序后的映射,将其加入到答案
List[i]
后面即可
| class Solution { |
| public List<List<String>> groupAnagrams(String[] strs) { |
| List<List<String>> ans = new ArrayList<>(); |
| HashMap<String, Integer> vis = new HashMap<>(); |
| int idx = 0; |
| for (String s : strs) { |
| char[] t = s.toCharArray(); |
| Arrays.sort(t); |
| String st = new String(t); |
| |
| if (vis.containsKey(st)) ans.get(vis.get(st)).add(s); |
| else { |
| |
| List<String> newList = new ArrayList<>(); |
| newList.add(s); ans.add(newList); |
| vis.put(st, idx ++); |
| } |
| } |
| return ans; |
| } |
| } |
| class Solution { |
| public double myPow(double x, int n) { |
| if (x == 0.0d) return 0.0d; |
| long k = n; |
| double res = 1.0d; |
| if (k < 0) { |
| x = 1 / x; |
| k = -k; |
| } |
| while (k > 0) { |
| if ((k & 1) == 1) res *= x; |
| x *= x; |
| k >>= 1; |
| } |
| return res; |
| } |
| } |
- DFS
- 递归的每一层,只能放一次棋子
- 对于每个棋子,必须保证其斜率 1 和 −1 的直线上和这一列上没有相同的棋子
- 即对于棋子
[i][j]
在斜率为 1 和 −1 时判断其截距是否已经存在即可,且要求 j
列不存在相同的棋子
| class Solution { |
| public List<List<String>> solveNQueens(int n) { |
| boolean[] col = new boolean[n]; |
| boolean[] l = new boolean[n * 2 + 1]; |
| boolean[] r = new boolean[n * 2 + 1]; |
| List<String> res = new ArrayList<>(); |
| List<List<String>> ans = new ArrayList<>(); |
| dfs(0, n, col, l, r, res, ans); |
| return ans; |
| } |
| |
| void dfs(int u, int n, boolean[] col, boolean[] l, boolean[] r, |
| List<String> res, List<List<String>> ans) { |
| if (u == n) { |
| ans.add(new ArrayList<>(res)); |
| return ; |
| } |
| char[] s = new char[n]; |
| for (int i = 0; i < n; i ++) s[i] = '.'; |
| for (int i = 0; i < n; i ++) { |
| |
| if (!col[i] && !l[u - i + n] && !r[u + i]) { |
| col[i] = l[u - i + n] = r[u + i] = true; |
| s[i] = 'Q'; |
| res.add(new String(s)); |
| dfs (u + 1, n, col, l, r, res, ans); |
| |
| res.remove(res.size() - 1); |
| s[i] = '.'; |
| col[i] = l[u - i + n] = r[u + i] = false; |
| } |
| } |
| } |
| } |
- DFS
- 上一题青春版
- 只需要维护方案数量即可,不需要记录答案
| class Solution { |
| private int ans; |
| |
| public int totalNQueens(int n) { |
| boolean[] col = new boolean[n]; |
| boolean[] l = new boolean[n * 2 + 1]; |
| boolean[] r = new boolean[n * 2 + 1]; |
| return dfs (0, n, col, l, r); |
| } |
| |
| int dfs(int u, int n, boolean[] col, boolean[] l, boolean[] r) { |
| if (u == n) return 1; |
| int res = 0; |
| for (int i = 0; i < n; i ++) { |
| |
| if (!col[i] && !l[u - i + n] && !r[u + i]) { |
| col[i] = l[u - i + n] = r[u + i] = true; |
| res += dfs (u + 1, n, col, l, r); |
| col[i] = l[u - i + n] = r[u + i] = false; |
| } |
| } |
| return res; |
| } |
| } |
- dp
- 状态表示:
dp[i]
表示以 nums[i]
结尾的数组中,最大的连续子数组的值
- 状态计算:
- 若
dp[i] <= 0
说明前面的数组没有继续扩展的需要,以 dp[i]
结尾的最大值为 Math.max(dp[i - 1], nums[i])
- 否则,最大值为
dp[i - 1] + nums[i]
| class Solution { |
| public int maxSubArray(int[] nums) { |
| int n = nums.length; |
| int[] dp = new int[n]; |
| dp[0] = nums[0]; |
| int ans = nums[0]; |
| for (int i = 1; i < n; i ++) { |
| if (dp[i - 1] > 0) dp[i] = dp[i - 1] + nums[i]; |
| else dp[i] = Math.max(dp[i - 1], nums[i]); |
| ans = Math.max(ans, dp[i]); |
| } |
| return ans; |
| } |
| } |
- 模拟
- 本质就是蛇形矩阵
- 按照旋转的顺时针方向构建偏移量数组
- 设
l, r
为当前遍历位置的坐标:
- 若
l < 0 || r < 0 || l >= n || r >= m
说明越界,此时要按照顺时针方向转向
- 若
vis[l][r]
已经被标记过,说明之前已经走过这个位置,显然也是越界行为,也要转向
- 遍历的步数为
n * m
| class Solution { |
| public List<Integer> spiralOrder(int[][] matrix) { |
| int n = matrix.length, m = matrix[0].length; |
| boolean[][] vis = new boolean[n][m]; |
| List<Integer> ans = new ArrayList<>(); |
| int x = 0, y = 0, d = 0; |
| int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0}; |
| for (int i = 0; i < n * m; i ++) { |
| ans.add(matrix[x][y]); vis[x][y] = true; |
| int l = x + dx[d], r = y + dy[d]; |
| if (l < 0 || r < 0 || r >= m || l >= n || vis[l][r]) { |
| d = (d + 1) % 4; |
| l = x + dx[d]; r = y + dy[d]; |
| } |
| x = l; y = r; |
| } |
| return ans; |
| } |
| } |
- 模拟
- 45 的青春版
- 用
idx
记录可以到达的最大位置的下标
- 每次循环:
- 若
i > idx
说明当前位置 i
无法到达,直接 false
- 更新
idx = Math.max(idx, i + nums[i])
- 若
idx >= nums.length - 1
说明已经可以到达尾部,直接 true
| class Solution { |
| public boolean canJump(int[] nums) { |
| int idx = 0; |
| for (int i = 0; i < nums.length; i++) { |
| if (i > idx) return false; |
| idx = Math.max(idx, i + nums[i]); |
| if (idx >= nums.length - 1) { |
| return true; |
| } |
| } |
| return false; |
| } |
| } |
- 区间合并
- 板子题
- 对区间左端点排序,判断前一个区间的右端点和当前区间的左端点关系
- 若前一个区间的右端点小于等于当前区间左端点,说明可以合并,更新右端点
- 否则当前区间为新的区间
| class Solution { |
| public int[][] merge(int[][] intervals) { |
| int n = intervals.length; |
| Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]); |
| List<int[]> ans = new ArrayList<>(); |
| int l = intervals[0][0], r = intervals[0][1]; |
| for (int i = 1; i < n; i ++) { |
| |
| if (intervals[i][0] <= r) r = Math.max(intervals[i][1], r); |
| else { |
| ans.add(new int[]{l, r}); |
| l = intervals[i][0]; r = intervals[i][1]; |
| } |
| } |
| ans.add(new int[]{l, r}); |
| return ans.toArray(new int[ans.size()][]); |
| } |
| } |
| class Solution { |
| public int[][] insert(int[][] intervals, int[] newInterval) { |
| int[][] res = new int[intervals.length + 1][2]; |
| for (int i = 0; i < intervals.length; i ++) res[i] = intervals[i]; |
| res[intervals.length] = newInterval; |
| intervals = res; |
| Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]); |
| List<int[]> ans = new ArrayList<>(); |
| int l = intervals[0][0], r = intervals[0][1]; |
| for (int i = 1; i < intervals.length; i ++) { |
| |
| if (intervals[i][0] <= r) r = Math.max(intervals[i][1], r); |
| else { |
| ans.add(new int[]{l, r}); |
| l = intervals[i][0]; r = intervals[i][1]; |
| } |
| } |
| ans.add(new int[]{l, r}); |
| return ans.toArray(new int[ans.size()][]); |
| } |
| } |
| class Solution { |
| public int lengthOfLastWord(String s) { |
| int cnt = 0; |
| char op = 'a'; |
| int idx = s.length() - 1; |
| while (idx >= 0 && s.charAt(idx) == ' ') idx --; |
| while (idx >= 0) { |
| op = s.charAt(idx); |
| if ((op >= 'a' && op <= 'z') || (op >= 'A' && op <= 'Z')) cnt ++; |
| else return cnt; |
| idx --; |
| } |
| return cnt; |
| } |
| } |
| class Solution { |
| public int[][] generateMatrix(int n) { |
| int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0}; |
| int l = 0, r = 0, d = 0; |
| int[][] ans = new int[n][n]; |
| for (int i = 1; i <= n * n; i ++) { |
| ans[l][r] = i; |
| int x = l + dx[d], y = r + dy[d]; |
| if (x < 0 || y < 0 || x >= n || y >= n || ans[x][y] != 0) { |
| d = (d + 1) % 4; |
| x = l + dx[d]; y = r + dy[d]; |
| } |
| l = x; r = y; |
| } |
| return ans; |
| } |
| } |
| class Solution { |
| public String getPermutation(int n, int k) { |
| char[] nums = new char[n]; |
| for (int i = 0; i < n; i ++) nums[i] = (char)(i + 1 + '0'); |
| while (k -- > 1) nextPermutation(nums); |
| return String.valueOf(nums); |
| } |
| |
| public void nextPermutation(char[] nums) { |
| int n = nums.length; |
| int i = n - 2; |
| while (i >= 0 && nums[i] >= nums[i + 1]) i --; |
| if (i >= 0) { |
| int j = n - 1; |
| while (nums[j] <= nums[i]) j --; |
| swap(nums, i, j); |
| } |
| reverse(nums, i + 1, n - 1); |
| } |
| |
| private void swap(char[] nums, int i, int j) { |
| char t = nums[i]; |
| nums[i] = nums[j]; |
| nums[j] = t; |
| } |
| |
| private void reverse(char[] nums, int l, int r) { |
| while (l < r) { |
| this.swap(nums, l, r); |
| l ++; r --; |
| } |
| } |
| |
| } |