最长有效括号
给定一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。
Python解法:
# 从前往后遍历字符串
# 1、入栈条件为1.栈为空 2.当前字符是'(' 3.栈顶符号位')',因为三种条件都没办法消去成对的括号。
# 2、计算结果:符合消去成对括号时,拿当前下标减去栈顶下标即可
class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s:
return 0
stack = []
res = 0
for i in range(len(s)):
if not stack or s[i] == '(' or s[stack[-1]] == ')':
stack.append(i)
else:
stack.pop()
if stack:
res = max(res, i - (stack[-1]))
else:
res = max(res, i - 1)
return res
# 测试
s = Solution()
arr = ")()())"
print(s.longestValidParentheses(arr))
答案:
4
Java解法:
public static int longestValidParentheses(String s) {
if (s == null || s.length() == 0){
return 0;
}
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int res = 0;
for (int i = 0 ; i < s.length() ; i++){
if( s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if(stack.isEmpty()){
stack.push(i);
}else {
res = Math.max(res , i - stack.peek());
}
}
}
return res;
}
}
搜索旋转排序数组
给你一个整数数组 nums ,和一个整数 target 。
该整数数组原本是按升序排列,但输入时在预先未知的某个点上进行了旋转。(例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1。
Python解法:
class Solution:
def search(self, nums: list, target: int) -> int:
if not nums:
return -1
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# 左半段有序
if nums[mid] > nums[left]:
if nums[left] <= target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
# 右半段有序
else:
if nums[mid] <= target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
# 测试
s = Solution()
nums = [4,5,6,7,0,1,2]
target = 7
print(s.search(nums,target))
答案:
3
Java解法:
/*二分法*/
public static int search(int[] nums, int target) {
if (nums == null || nums.length < 2){
return -1;
}
int len = nums.length;
int left = 0, right = len - 1;
while (left < right){
int mid = (left + right) / 2;
if (nums[mid] == target){
return mid;
/*左边有序*/
} else 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;
}
在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
Python解法:
# 二分法
class Solution:
def searchRange(self, nums: list, target: int) -> list:
n = len(nums)
left = 0
right = n
while left < right:
mid = int(left + (right-left)/2)
if nums[mid] == target:
start = mid - 1
end = mid + 1
# 两边扩散
while start >= 0 and nums[start] == target:
start -= 1
while end < n and nums[end] == target:
end += 1
return [start + 1, end - 1]
elif nums[mid] < target:
left = mid + 1
else:
right = mid
return [-1, -1]
#测试
s = Solution()
nums = [5, 7, 7, 8, 8, 10]
target = 8
print(s.searchRange(nums,target))
答案:
[3, 4]
Java解法:
/**
*二分法
*/
public static int[] searchRange(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (target == nums[mid]) {
left = mid - 1;
right = mid + 1;
while(left >= 0 && nums[left] == target){
left--;
}
while(right < n && nums[right] == target){
right++;
}
return new int[]{left + 1 , right - 1};
}else if (nums[mid] < target){
left = mid + 1;
}else {
right = mid;
}
}
return new int[]{-1 , - 1};
}
搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置
Python解法
class Solution:
def searchInsert(self, nums: list, target: int) -> int:
left , right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
# 测试
s = Solution()
nums = [5, 7, 7, 8, 8, 10]
target = 9
print(s.searchInsert(nums,target))
# 答案
5
Java解法:
/**
* 二分法
*/
public static int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length;
while(left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] < target){
left = mid + 1;
}else{
right = mid;
}
}
return left;
}
有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
Python解法:
# 遍历数独。
# 检查看到每个单元格值是否已经在当前的行 / 列 / 子数独中出现过:
# 如果出现重复,返回 false。
# 如果没有,则保留此值以进行进一步跟踪。
# 返回 true。
class Solution:
def isValidSudoku(self, board) -> bool:
# 初始化数据
rows = [{} for i in range(9)]
columns = [{} for i in range(9)]
boxes = [{} for i in range(9)]
# validate a board
for i in range(9):
for j in range(9):
num = board[i][j]
if num != '.':
num = int(num)
box_index = (i // 3) * 3 + j // 3
rows[i][num] = rows[i].get(num, 0) + 1
columns[j][num] = columns[j].get(num, 0) + 1
boxes[box_index][num] = boxes[box_index].get(num, 0) + 1
if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
return False
return True
# 测试
s = Solution()
board = [
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
print(s.isValidSudoku(board))
答案:
Ture
Java版本:
public static boolean isValidSudoku(char[][] board) {
int[][] rows = new int[9][9];
int[][] col = new int[9][9];
int[][] sbox = new int[9][9];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j]!='.'){
int num = board[i][j] - '1';
int index_box = (i/3)*3+j/3;
if (rows[i][num]==1) {
return false;
} else {
rows[i][num]=1;
}
if (col[j][num]==1) {
return false;
} else {
col[j][num]=1;
}
if (sbox[index_box][num]==1){
return false;}
else {
sbox[index_box][num]=1;
}
}
}
}
return true;
}
解数独
编写一个程序,通过填充空格来解决数独问题
Python解法:
# 解数独
class Solution:
def solveSudoku(self, board: list) -> None:
nums = {"1", "2", "3", "4", "5", "6", "7", "8", "9"}
row = [set() for _ in range(9)]
col = [set() for _ in range(9)]
palace = [[set() for _ in range(3)] for _ in range(3)] # 3*3
blank = []
# 初始化,按照行、列、宫 分别存入哈希表
for i in range(9):
for j in range(9):
ch = board[i][j]
if ch == ".":
blank.append((i, j)) # 还未填充的位置
else:
row[i].add(ch) # 行
col[j].add(ch) # 列
palace[i // 3][j // 3].add(ch) # 9宫格
# 递归
def dfs(n):
if n == len(blank):
return True
i, j = blank[n]
rst = nums - row[i] - col[j] - palace[i // 3][j // 3] # 剩余的数字
if not rst:
return False
for num in rst:
board[i][j] = num
row[i].add(num)
col[j].add(num)
palace[i // 3][j // 3].add(num)
if dfs(n + 1):
return True
row[i].remove(num)
col[j].remove(num)
palace[i // 3][j // 3].remove(num)
dfs(0)
# 测试
s = Solution()
board = [
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
print(s.solveSudoku(board))
Java版本:
/**
* 回溯
* 逐行,从左到右,在每一个位置上试探1-9,成功就进入下一个位置,失败就取消本次选择,做下一个选择
* 当前行试探完毕就换行,知道换到最后一行
* 子数独的索引是 (i / 3) * 3 + j / 3
*/
public static void solveSudoku(char[][] board) {
if(board == null || board.length < 9 || board[0].length < 9){
return;
}
backTrace(board,0,0);
}
private static boolean backTrace(char[][] board, int row, int col){
int n = board.length;
if (col == 9) {
return backTrace(board, row + 1, 0);
}
// 满足结束条件,全部行全部位置都已试探过
if (row == n) {
return true;
}
// 这个位置数字已给出,不需要试探,直接试探下一个位置
if (board[row][col] != '.') {
return backTrace(board, row, col + 1);
}
for (char c = '1'; c <= '9'; c++){
if (!isValid(board, row, col, c))
continue;
board[row][col] = c;
if (backTrace(board, row, col + 1))
return true;
board[row][col] = '.';
}
// 这个位置把1-9都试过了,都无法继续下去,说明上一次的选择失败,需要回溯
return false;
}
/**
* 判断数字是否有效
*/
private static boolean isValid(char[][] board, int row, int col, char ch) {
for (int i = 0 ; i < board.length ; i++){
/* 判断,行、列、9宫格是否已经出现过了 */
if (board[row][i] == ch) {
return false;
}
if (board[i][col] == ch) {
return false;
}
if (board[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == ch){
return false;
}
}
return true;
}
外观数列
给定一个正整数 n ,输出外观数列的第 n 项。
「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。
Python版本:
# 外观数列
class Solution:
def countAndSay(self, n: int) -> str:
if n == 1:
return '1'
s = self.countAndSay(n - 1)
i, res = 0, ''
# j为索引,c为具体值
for j, c in enumerate(s):
if c != s[i]:
res += str(j - i) + s[i]
i = j
res += str(len(s) - i) + s[-1] # 最后一个元素统计
return res
# 测试
s = Solution()
print(s.countAndSay(4))
# 答案:
1211
Java版本:
/**
* 递归方法
*/
public static String countAndSay(int n) {
/* 递归终止条件 */
if (n == 1) {
return "1";
}
StringBuffer res = new StringBuffer();
/* 拿到上一层的字符串 */
String str = countAndSay(n - 1);
int len = str.length();
/* 开始时指针为0 */
int start = 0;
/* 注意这从起始条件要和下面长度统一 */
for (int i = 1 ; i < len + 1 ; i++) {
/* 字符串最后一位直接拼接 */
if (i == len) {
res.append(i - start).append(str.charAt(start));
/* 直到start位的字符串和i位的字符串不同,拼接并更新start位 */
} else if (str.charAt(i) != str.charAt(start) ) {
res.append(i - start).append(str.charAt(start));
start = i;
}
}
return res.toString();
}
组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
Python版本:
# 回溯算法 + 剪枝
class Solution:
def combinationSum(self, candidates: list, target: int) -> list:
size = len(candidates)
if size == 0:
return []
cur = []
res = []
self.dfs(candidates, 0, size, cur, res, target)
return res
def dfs(self, candidates, begin, size, cur, res, target):
if target < 0:
return
if target == 0:
res.append(cur)
return
for idx in range(begin, size):
self.dfs(candidates, idx, size, cur + [candidates[idx]], res, target - candidates[idx])
# 测试
s = Solution()
candidates = [2, 3, 6, 7]
target = 7
print(s.combinationSum(candidates, target))
答案:
[[2, 2, 3], [7]]
Java版本:
/*
* 回溯 + 剪枝
*/
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
dfs(res,new ArrayList<Integer>(),0,candidates,target);
return res;
}
public static void dfs(List<List<Integer>> res , List cur , int begin , int[] candidates, int target){
if (target < 0){
return;
}
if (target == 0){
res.add(new ArrayList<>(cur));
}
for (int i = begin ; i < candidates.length ; i++) {
cur.add(candidates[i]);
dfs(res,cur,i,candidates,target-candidates[i]);
cur.remove(cur.size()-1);
}
}
组合总和2
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
Python版本:
class Solution:
def combinationSum2(self, candidates: list, target: int) -> list:
size = len(candidates)
if size == 0:
return []
path = []
res = []
candidates.sort()
self.dfs(candidates, 0, size, path, res, target)
return res
def dfs(self,candidates: list, begin: int, size: int, path: list, res: list, target: int):
if target < 0:
return
if target == 0:
res.append(path)
return
for i in range(begin,size):
# 跳过同样的数字
if i > 0 and candidates[i] == candidates[i-1]:
continue
# i+1 用过的数字不再用
self.dfs(candidates, i+1, size, path+[candidates[i]], res, target-candidates[i])
# 测试
s = Solution()
candidates = [10,1,2,7,6,1,5]
target = 8
print(s.combinationSum2(candidates, target))
#答案:
[[1, 2, 5], [1, 7], [2, 6]]
Java版本:
public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
/* 对数组排序 */
Arrays.sort(candidates);
dfs(res,new ArrayList<Integer>(),0,candidates,target);
return res;
}
public static void dfs(List<List<Integer>> res , List cur , int begin , int[] candidates, int target ){
if (target < 0){
return;
}
if (target == 0){
res.add(new ArrayList<>(cur));
return;
}
for (int i = begin ; i < candidates.length ; i++) {
/* 用过的不再用 */
if(i > begin && candidates[i] == candidates[i-1]) {
continue;
}
cur.add(candidates[i]);
dfs(res,cur,i+1 ,candidates,target-candidates[i]);
cur.remove(cur.size()-1);
}
}
缺失的第一个正数
给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。
Python版本:
# 缺失的第一个正数
class Solution:
def firstMissingPositive(self, nums: list) -> int:
s = set()
for x in nums:
s.add(x)
n = len(nums)
for i in range(1, n+1):
if i not in s:
return i
return n+1
# 测试
s = Solution()
nums = [1,2,0]
print(s.firstMissingPositive(nums))
# 答案:
3
Java版本:
public static int firstMissingPositive(int[] nums) {
int len = nums.length;
Set<Integer> hashSet = new HashSet<>();
for (int num : nums) {
hashSet.add(num);
}
for (int i = 1; i <= len; i++) {
if (!hashSet.contains(i))
return i;
}
return len + 1;
}
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
Python版本:
# 接雨水
class Solution:
# 双指针
def trap(self, height: list) -> int:
res = 0
left, right = 0, len(height)-1
max_left, max_right = 0, 0
while left < right:
if height[left] < height[right]:
if height[left] > max_left:
max_left = height[left]
else:
res += max_left - height[left]
left += 1
else:
if height[right] > max_right:
max_right = height[right]
else:
res += max_right - height[right]
right -= 1
return res
# 测试
s = Solution()
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(s.trap(height))
答案:
6
Java版本:
/*
暴力法
*/
public static int trap(int[] height) {
int len = height.length;
int res = 0;
for (int i = 1 ; i < len - 1 ; i++){
int left = 0 ,right = 0;
/*向左边扫*/
for (int j = i ; j >= 0 ; j--){
left = Math.max(left,height[j]);
}
/*向右边扫*/
for (int j = i ; j < len ; j++){
right = Math.max(right,height[j]);
}
res += Math.min(right , left) - height[i];
}
return res;
}
/*
双指针法
如果一端有更高的条形块(例如右端),积水的高度依赖于当前方向的高度(从左到右)。当我们发现另一侧(右侧)的条形块高度不是最高的,我们则开始从相反的方向遍历(从右到左)。
可以使用两个指针交替进行,实现 1 次遍历即可完成。
*/
public static int trap2(int[] height) {
int left = 0 , right = height.length-1;
int max_left = 0 ,max_right = 0 , res = 0;
while (left < right){
if (height[left] < height[right]){
if (height[left] > max_left){
max_left = height[left];
}else{
res += max_left - height[left];
}
left++;
}else{
if (height[right] > max_right){
max_right = height[right];
}else{
res += max_right - height[right];
}
right--;
}
}
return res;
}
字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头,除非是数字 0 本身。
不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理。
Python解法:
# 字符串相乘
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == '0' or num2 == '0':
return '0'
num1, num2 = num1[::-1], num2[::-1]
res = 0
for i, x in enumerate(num1):
tmp = 0
for j, y in enumerate(num2):
tmp += int(x) * int(y) * 10 ** j
print(i)
res += tmp * 10 ** i
return res
# 测试
s = Solution()
num1, num2 = '234', '30'
print(s.multiply(num1,num2))
答案:
7020
Java解法:
/*
做乘法
*/
public static String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")){
return "0";
}
int n = num1.length() , m = num2.length();
int []arrs = new int[n+m];
/*用数组来存储每个位置的值*/
for (int i = n-1 ; i >= 0 ; i--){
int x = num1.charAt(i) - '0';
for (int j = m-1 ; j >= 0 ; j--){
int y = num2.charAt(j) - '0';
arrs[i+j+1] += x * y;
}
}
/*对大于9的值做取余和进位*/
for (int i = n+m-1 ; i > 0 ; i--){
arrs[i-1] += arrs[i] / 10;
arrs[i] %= 10;
}
/*判断首位情况*/
int idx = arrs[0] == 0 ? 1 : 0;
/*遍历数组,组成字符串*/
StringBuffer res = new StringBuffer();
while (idx < m + n) {
res.append(arrs[idx]);
idx++;
}
return res.toString();
}
通配符匹配
给定一个字符串 (s) 和一个字符模式 § ,实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。
?
可以匹配任何单个字符。
*
可以匹配任意字符串(包括空字符串)。
Java版本:
/*
小写字母 a-z,可以匹配对应的一个小写字母;dp[i][j]=(si 与 pj相同)∧dp[i−1][j−1]
问号 ?,可以匹配任意一个小写字母;dp[i][j]=dp[i−1][j−1]
星号 *,可以匹配任意字符串,可以为空,也就是匹配零或任意多个小写字母。dp[i][j]=dp[i][j−1]∨dp[i−1][j]
dp[0][0] = True,即当字符串 s 和模式 p 均为空时,匹配成功;
dp[i][0] = False,即空模式无法匹配非空字符串;
dp[0][j] 需要分情况讨论:因为星号才能匹配空字符串,所以只有当模式 p 的前 j 个字符均为星号时,dp[0][j] 才为真。
*/
/*
动态规划
*/
public static boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean [][]dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
/* dp[0][j] 情况做处理*/
for (int i = 1 ; i <= n ; i++){
if (p.charAt(i - 1) == '*'){
dp[0][i] = true;
}else{
break;
}
}
/* 根据转态方程做处理 */
for (int i = 1 ; i <= m ; i++){
for (int j = 1 ; j <= n ; j++){
if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?'){
dp[i][j] = dp[i - 1][j - 1];
}else if (p.charAt(j-1) == '*'){
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}
}
}
return dp[m][n];
}
Python版本:
# 小写字母 a-z,可以匹配对应的一个小写字母;dp[i][j]=(si 与 pj相同)∧dp[i−1][j−1]
# 问号 ?,可以匹配任意一个小写字母;dp[i][j]=dp[i−1][j−1]
# 星号 *,可以匹配任意字符串,可以为空,也就是匹配零或任意多个小写字母。dp[i][j]=dp[i][j−1]∨dp[i−1][j]
# dp[0][0] = True,即当字符串 s 和模式 p 均为空时,匹配成功;
# dp[i][0] = False,即空模式无法匹配非空字符串;
# dp[0][j] 需要分情况讨论:因为星号才能匹配空字符串,所以只有当模式 p 的前 j 个字符均为星号时,dp[0][j] 才为真。
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
# 构造二维数组
dp = [[False] * (n+1) for j in range(m+1)]
dp[0][0] = True
# dp[0][j] 情况做处理
for i in range(1,n+1):
if p[i-1] == '*':
dp[0][i] = True
else:
break
# 根据转态方程做处理
for i in range(1,m+1):
for j in range(1, n+1):
if p[j-1] == s[i-1] or p[j-1] == '?':
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
dp[i][j] = dp[i-1][j] or dp[i][j-1]
return dp[m][n]
# 测试
demo = Solution()
s = "aa"
p = "*"
print(demo.isMatch(s,p))
答案:
True
跳跃游戏2
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
Python版本:
# 跳跃游戏2
# 维护当前能够到达的最大下标位置,记为边界。从左到右遍历数组,到达边界时,更新边界并将跳跃次数增加1
class Solution:
def jump(self, nums: list) -> int:
n = len(nums)
maxVal, step, end = 0, 0, 0
for i in range(n-1):
maxVal = max(maxVal, i+nums[i])
if i == end:
end = maxVal
step += 1
return step
# 测试
nums = [2,3,1,2,4,2,3]
s = Solution()
print(s.jump(nums))
# 答案:
3
Java版本:
/*
维护当前能够到达的最大下标位置,记为边界。从左到右遍历数组,到达边界时,更新边界并将跳跃次数增加1
*/
public static int jump(int[] nums) {
int n = nums.length;
int max = 0, step = 0, end = 0;
for (int i = 0 ; i < n - 1 ; i++) {
max = Math.max(max, i + nums[i]);
if (i == end) {
end = max;
step++;
}
}
return step;
}
全排列
给定一个没有重复数字的序列,返回其所有可能的全排列。
Java版本:
/*
搜索回溯
*/
public static List<List<Integer>> permute(int[] nums) {
if (nums == null || nums.length < 1){
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
boolean[] flag = new boolean[nums.length];
backTrack(res, new ArrayList<Integer>(), nums, flag);
return res;
}
public static void backTrack(List<List<Integer>> res , List list , int[]nums, boolean[] flag){
if (nums.length == list.size()){
res.add(new ArrayList<>(list));
return;
}
for (int i = 0 ; i < nums.length ; i++){
if (!flag[i]){
flag[i] = true;
list.add(nums[i]);
backTrack(res, list, nums, flag);
list.remove(list.size()-1);
flag[i] = false;
}
}
}
Python版本:
# 全排列
# 给定一个没有重复数字的序列,返回其所有可能的全排列。
class Solution:
def permute(self, nums) -> list:
if not nums:
return []
res = []
flag = [False for _ in range(len(nums))]
self.backTrack(res, [], nums, flag)
return res
def backTrack(self, res: list, data: list, nums: list, flag: list):
if len(data) == len(nums):
res.append(data[:])
return
for i in range(len(nums)):
if not flag[i]:
flag[i] = True
self.backTrack(res, data + [nums[i]], nums, flag)
flag[i] = False
# 测试
s = Solution()
nums = [1,2,3]
print(s.permute(nums))
# 答案:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
全排列2
给定一个可包含重复数字的序列 nums ,按任意顺序返回所有不重复的全排列。
Java版本:
/*
搜索回溯
*/
public static List<List<Integer>> permuteUnique(int[] nums) {
if (nums == null || nums.length < 1){
return new ArrayList<>();
}
HashSet<List<Integer>> set = new HashSet<>();
boolean []flag = new boolean[nums.length];
backTrack(set, new ArrayList<Integer>(), nums, flag);
return new ArrayList<>(set);
}
public static void backTrack(HashSet<List<Integer>> set , List list , int []nums , boolean []flag){
if (list.size() == nums.length){
set.add(new ArrayList<>(list));
return;
}
for (int i = 0 ; i < nums.length ; i++){
if (!flag[i]){
flag[i] = true;
list.add(nums[i]);
backTrack(set, list, nums, flag);
list.remove(list.size()-1);
flag[i] = false;
}
}
}
Python版本:
# 全排列2
# 给定一个没有重复数字的序列,返回其所有可能的全排列。
class Solution:
def permute(self, nums) -> list:
if not nums:
return []
res = []
flag = [False for _ in range(len(nums))]
self.backTrack(res, [], nums, flag)
return res
def backTrack(self, res: list, data: list, nums: list, flag: list):
if len(data) == len(nums):
res.append(data[:])
return
for i in range(len(nums)):
if not flag[i]:
flag[i] = True
self.backTrack(res, data + [nums[i]], nums, flag)
flag[i] = False
# 测试
s = Solution()
nums = [1,2,1]
print(s.permute(nums))
# 答案:
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
字母异位词分组
给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
Java版本:
/*
将字符串转化为char数组类型,进行排序,即字符一样的最终都会一样
然后根据键值对的判断,放进map
*/
public static List<List<String>> groupAnagrams(String []strs){
if (strs == null){
return new ArrayList<>();
}
Map<String, List<String>> map = new HashMap<>();
for (String s : strs){
char[] c = s.toCharArray();
Arrays.sort(c);
String key = new String(c);
List<String> list = map.getOrDefault(key, new ArrayList<>());
list.add(s);
map.put(key,list);
}
return new ArrayList<>(map.values());
}
Python版本:
# 字母异位词分组
# 给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
import collections
class Solution:
def groupAnagrams(self, strs: list) -> list:
# collections.defaultdict() 该函数返回一个类似字典的对象,变量存在,则用以初始化构造器,如果没有,则为None。其它的功能和dict一样
data = collections.defaultdict(list)
for st in strs:
key = "".join(sorted(st))
data[key].append(st)
return list(data.values())
# 测试
s = Solution()
strs = ["eat", "tea", "tan", "ate", "nat", "bat"];
print(s.groupAnagrams(strs))
# 答案:
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
Java版本:
/*
最直接的方法:转置+反转
转置:以左上连接右下的对角线为轴,两边值互换
反转:每一行的值对称互换
*/
public static void rotate(int [][]matrix){
int n = matrix.length;
/* 转置 */
for (int i = 0 ; i < n ; i++){
for (int j = i ; j < n ; j++){
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
/* 反转 */
for (int i = 0 ; i < n ; i++){
for (int j = 0 ; j < n / 2 + 1 ; j ++){
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][n-j-1];
matrix[i][n-j-1] = tmp;
}
}
}
Python版本:
# 旋转图像
class Solution:
def rotate(self, matrix: list) -> list:
n = len(matrix)
# 转置
for i in range(0,n):
for j in range(i,n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# 反转
for i in range(0,n):
for j in range(0, n//2+1):
matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1],matrix[i][j]
return matrix
# 测试
s = Solution()
matrix = [
[1,2,3],
[4,5,6],
[7,8,9]
]
print(s.rotate(matrix))
#答案:
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
Pow(x, n)
实现 pow(x, n) ,即计算 x 的 n 次幂函数。
Python版本:
# Pow(x, n)
# 实现 pow(x, n) ,即计算 x 的 n 次幂函数。
class Solution:
# 方法:快速幂 + 递归
def myPow(self, x: float, n: int) -> float:
if n >= 0:
return self.quickMul(x, n)
else:
return 1.0/self.quickMul(x, -n)
def quickMul(self, x: float, n: int):
if n == 0:
return 1.0
y = self.quickMul(x, n//2)
if n % 2 == 0:
return y * y
else:
return y * y * x
# 测试
s = Solution()
x = 2.00000
n = 10
print(s.myPow(x, n))
答案:
1024.0
Java版本:
public static double myPow(double x, int n) {
if (n >= 0){
return quickMul(x,n);
}else {
return 1.0/quickMul(x,-n);
}
}
public static double quickMul(double x , int n){
if (n == 0){
return 1.0;
}
double y = quickMul(x, n/2);
if (n % 2 == 0){
return y * y;
}else {
return y * y * x;
}
}
N皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
Java解法:
/*
思路:基于集合的回溯
判断一个位置所在的列和两条斜线上是否已经有皇后,使用三个集合 col、left_slash、right_slash
分别记录每一列以及两个方向的每条斜线上是否有皇后。
*/
public static List<List<String>> solveNQueens(int n){
/*结果*/
List<List<String>> res = new ArrayList<>();
/*三个集合,列,左斜线,右斜线*/
Set<Integer> col = new HashSet<>();
Set<Integer> left_slash = new HashSet<>();
Set<Integer> right_slash = new HashSet<>();
/*初始化*/
int[] queens = new int[n];
Arrays.fill(queens, -1);
backTrack(res, queens, n, 0, col, left_slash, right_slash);
return res;
}
/**
*回溯
*/
public static void backTrack(List<List<String>> res, int[] queens, int n, int row, Set<Integer> col, Set<Integer> left_slash, Set<Integer> right_slash) {
if (row == n){
List<String> board = generateBoard(queens, n);
res.add(board);
return;
}
for (int i = 0; i < n ; i++){
/* 判断列,左、右斜线是否存在 */
if (col.contains(i)){
continue;
}
/*
从左上到右下方向,同一条斜线上的每个位置满足行下标与列下标之差相等
从右上到左下方向,同一条斜线上的每个位置满足行下标与列下标之和相等
*/
if (left_slash.contains(row - i)){
continue;
}
if (right_slash.contains(row + i)){
continue;
}
queens[row] = i;
col.add(i) ;
left_slash.add(row - i);
right_slash.add(row + i);
backTrack(res, queens, n, row+1, col, left_slash, right_slash);
right_slash.remove(row + i);
left_slash.remove(row - i);
col.remove(i);
queens[row] = -1;
}
}
/**
*生成结果
*/
public static List<String> generateBoard(int[] queens, int n){
List<String> list = new ArrayList<>();
for (int i = 0 ; i < n ; i++){
char []c = new char[n];
Arrays.fill(c,'.');
c[queens[i]] = 'Q';
list.add(new String(c));
}
return list;
}
Python解法:
# N 皇后
# n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击
class Solution:
def solveNQueens(self, n: int) -> list:
res = list()
queens = [-1] * n
col = set()
left_slash = set()
right_slash = set()
self.backTrack(res, queens, n, 0, col, left_slash, right_slash)
return res
def backTrack(self, res: list, queens: list, n: int, row: int, col: set, left_slash: set, right_slash: set):
if row == n:
board = self.generateBoard(queens, n)
res.append(board)
else:
for i in range(n):
if i in col or row - i in left_slash or row + i in right_slash:
continue
queens[row] = i
col.add(i)
left_slash.add(row - i)
right_slash.add(row + i)
self.backTrack(res, queens, n, row+1, col, left_slash, right_slash)
right_slash.remove(row + i)
left_slash.remove(row - i)
col.remove(i)
queens[row] = -1
def generateBoard(self, queens: list, n :int):
board = list()
for i in range(n):
rows = ['.' for i in range(n)]
rows[queens[i]] = "Q"
board.append("".join(rows))
rows[queens[i]] = "."
return board
# 测试
s = Solution()
print(s.solveNQueens(4))
# 答案:
[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]