编程练习题（2）

最长有效括号

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

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..']]