hot30

前k个高频元素

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] ans = new int[k];
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int num : nums){
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        PriorityQueue<Map.Entry<Integer,Integer>> minHeap = new PriorityQueue<>(
                (a,b) -> (a.getValue() - b.getValue())
        );
        for(Map.Entry<Integer,Integer> num : map.entrySet()){
            minHeap.offer(num);
            if(minHeap.size() > k){
                minHeap.poll();
            }
        }
        for(int i = 0; i < k; i++){
            ans[i] = minHeap.poll().getKey();
        }
        return ans;
    }
}

前k个高频单词

/**
使用最小堆,复杂度O(n):Nlogk*/
import java.net.Inet4Address;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int num : nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        PriorityQueue<Map.Entry<Integer,Integer>> minHeap = new PriorityQueue<>(
            (a,b) ->(a.getValue() - b.getValue())
        );
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            minHeap.offer(entry);
            if(minHeap.size() > k){
                minHeap.poll();
            }
        }
        int[] ans = new int[k];
        for(int i = 0; i<k; i++){
            ans[i] = minHeap.poll().getKey();
        }
        return  ans;
    }
}

/**
快速选择*/
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 使用HashMap统计元素出现的频率
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 将频率映射到一个数组
        int[] frequencies = new int[map.size()];
        int index = 0;
        for (int frequency : map.values()) {
            frequencies[index++] = frequency;
        }

        // 使用快速选择找到第k个最大的频率
        int kthLargestFrequency = quickSelect(frequencies, 0, frequencies.length - 1, frequencies.length - k);

        // 构造结果数组
        int[] ans = new int[k];
        index = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() >= kthLargestFrequency) {
                ans[index++] = entry.getKey();
            }
        }
        return ans;
    }

    // 快速选择算法
    private int quickSelect(int[] nums, int left, int right, int k) {
        // 如果数组中只有一个元素
        if (left == right) {
            return nums[left];
        }

        // 随机选择一个基准元素并获取其索引
        int pivotIndex = randomPartition(nums, left, right);

        // 如果基准元素正好是第k个最大的元素
        if (pivotIndex == k) {
            return nums[pivotIndex];
        } else if (pivotIndex < k) {
            // 在右侧继续查找
            return quickSelect(nums, pivotIndex + 1, right, k);
        } else {
            // 在左侧继续查找
            return quickSelect(nums, left, pivotIndex - 1, k);
        }
    }

    // 随机选择基准元素进行分区
    private int randomPartition(int[] nums, int left, int right) {
        Random random = new Random();
        // 随机选择一个索引作为基准元素
        int pivotIndex = random.nextInt(right - left + 1) + left;

        // 将基准元素移动到数组的最右端
        swap(nums, pivotIndex, 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;
    }
}

按字典序排在最后的字串

class Solution {
    public String lastSubstring(String s) {
        // 使用TreeSet来存储所有的子串并自动按字典序排序
        TreeSet<String> set = new TreeSet<>();

        int n = s.length();
        // 遍历字符串s的所有可能的子串
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                set.add(s.substring(i, j));
            }
        }

        // 返回TreeSet中的最后一个元素，即按字典序排序后的最后一个子串
        return set.last();
    }
}

反转链表

//迭代
//链表的值的改变一定是想要改的一方被赋值
//pre想要去cur的位置
//pre = cur
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode urr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}
//递归
//nk-1 -> nk -> nk+1
//我们希望nk+1指向nk
//nk.next.next = nk
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

LRU缓存

import java.util.HashMap;

class LRUCache {
    class DlinkedList {
        int val;
        int key;
        DlinkedList next;
        DlinkedList pre;

        DlinkedList() {
        }

        DlinkedList(int val, int key) {
            this.val = val;
            this.key = key;
        }
    }

    HashMap<Integer, DlinkedList> cache;
    int size;
    int capacity;
    DlinkedList head;
    DlinkedList tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        size = 0;
        head = new DlinkedList();
        tail = new DlinkedList();
        head.next = tail;
        tail.pre = head;
        cache = new HashMap<>();
    }

    public int get(int key) {
        DlinkedList node = cache.get(key);
        if (node == null)
            return -1;
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        DlinkedList node = cache.get(key);
        if (node == null) {
            if (size < capacity) {
                node = new DlinkedList(value, key);
                addToHead(node);
                cache.put(key, node);
                size++;
            } else {
                removeTail();
                node = new DlinkedList(value, key);
                addToHead(node);
                cache.put(key, node);
            }
        } else {
            node.val = value;
            moveToHead(node);
        }
    }

    private void moveToHead(DlinkedList node) {
        removeNode(node);
        addToHead(node);
    }

    private void removeTail() {
        DlinkedList tailNode = tail.pre;
        removeNode(tailNode);
        cache.remove(tailNode.key);
    }

    private void addToHead(DlinkedList node) {
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        node.pre = head;
    }

    private void removeNode(DlinkedList node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
}

三数之和

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i<nums.length; i++){
            if(i == 0 || (i > 0 && nums[i] != nums[i-1])){
                int left = i + 1;
                int right = nums.length - 1;
                while(left < right){
                    int sum = nums[i] + nums[left] + nums[right];
                    if(sum==0) {
                        ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
                        while(left < right && nums[left] == nums[left+1]){
                            left++;
                        }
                        while (right > left && nums[right] == nums[right - 1]){
                            right--;
                        }
                        left++;
                        right--;
                    }else if(sum > 0){
                        right--;
                    }else if(sum < 0){
                        left++;
                    }
                }
            }
        }
        return ans;
    }
}

最长回文串

class Solution {
    public int longestPalindrome(String s) {
        int[] ca = new int[128];
        for(char c : s.toCharArray()){
            ca[c]++;
        }
        int count = 0;
        for(int num : ca){
            count += num % 2;

        }
        //abbba
        return count==0 ? s.length() : s.length() - count + 1;
    }
}

全排列

import java.util.ArrayList;
import java.util.List;

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backTracking(nums);
        return ans;
    }
    private void backTracking(int[] nums){
        if(path.size() == nums.length){
            ans.add(new ArrayList<>(path));
        }
        for(int i = 0 ; i < nums.length; i++){
            if(path.contains(nums[i])){
                continue;
            }
            path.add(nums[i]);
            backTracking(nums);
            path.remove(path.size() - 1);
        }
    }
}

二叉树的最近公共祖先

//递归的查看当前子树的节点中是否包含p和q节点
class Solution {
    TreeNode res=null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        traver(root,p,q);
        return res;
    }

    public int traver(TreeNode root,TreeNode p, TreeNode q){
        if(root==null) return 0;
        int a=traver(root.left,p,q);
        int b=traver(root.right,p,q);

        int sum=a+b;
        if(root.val==p.val||root.val== q.val) sum+=1;

        if(res==null&&sum==2)  res=root;
        return sum;
    }
}

最长公共子序列

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] dp = new int[len1+1][len2+1];
        //dp[i][j] = dp[i-1][j-1]+1
        //dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]
        for(int i = 0; i<=len1; i++){
            dp[i][0] = 0;
        }
        for(int i = 0; i<=len2; i++){
            dp[0][i] = 0;
        }
        for(int i = 1; i<=len1; i++){
            for(int j = 1; j<=len2; j++){
                if(text1.charAt(i - 1) == text2.charAt(j - 1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[len1][len2];
    }
}

合并k个升序链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = null;
        for(int i = 0; i < lists.length; i++){
            dummy = merge(dummy,lists[i]);
        }
        return dummy;
    }
    public ListNode merge(ListNode heada,ListNode headb){
        ListNode a = heada;
        ListNode b = headb;
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        while(a!= null && b!= null){
            if(a.val <= b.val){
                pre.next = a;
                a = a.next;
            }else if(a.val > b.val){
                pre.next = b;
                b = b.next;
            }
            pre = pre.next;
        }
        pre.next = (a == null) ? b : a;
        return dummy.next;
    }
}

长度最小的子数组

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for(; right < nums.length; right++){
            sum += nums[right];
            while (sum >= target){
                min = Math.min(min,right - left + 1);
                sum -= nums[left++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

合并两个有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode l1 = list1;
        ListNode l2 = list2;
        ListNode head = new ListNode(0);
        ListNode pre = head;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val) {
                pre.next = l1;
                l1 = l1.next;
            }else if(l1.val >= l2.val){
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }
        pre.next = (l1 == null) ? l2 : l1;
        return head.next;
    } 
}

比较版本号

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] res1 = version1.split("\\.");
        String[] res2 = version2.split("\\.");
        for(int i = 0; i<res1.length || i < res2.length; i++){
            int x = 0;
            int y = 0;
            if(i < res1.length){
                x = Integer.parseInt(res1[i]);
            }
            if(i < res2.length){
                y = Integer.parseInt(res2[i]);
            }
            if(x > y){
                return 1;
            }
            if(x < y){
                return -1;
            }
        }
        return 0;
    }
}

打家劫舍II

class Solution {
    //有两个区间范围
    //从0到len-1
    //从1到len 
    //其中x,y,z 表示前两个房间的的金额和.当前要偷的房间的金额
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 1){
            return nums[0];
        }else if(len == 2){
            return Math.max(nums[0],nums[1]);
        }
        return Math.max(maxPrice(nums,0,len - 1),maxPrice(nums,1,len));
    }
    public int maxPrice(int[] nums,int start,int end){
        int x = 0;
        int y = 0;
        int z = 0;
        for(int i = start; i<end; i++){
            y = z;
            z = Math.max(y, x + nums[i]);
            x = y;
        }
        return z;
    }
}

买卖股票的最佳时机II

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for(int i = 1; i<prices.length; i++){
            int temp = 0;
            if(prices[i] > prices[i - 1]){
                temp = prices[i] - prices[i - 1];
                profit += temp;
            }
        }
        return profit;
    }
}

寻找重复数

class Solution {
    /**
     * 一共假设有三段路,第一段从出发点到入口: a 从入口到相遇点: b, 从相遇点到入口: c
     * 其中b+c = L
     * 另外可以知道a的距离 a+b
     * 那么b的距离 2*(a+b)
     * 可以得到2*(a+b) = a + n * (b + c) + b
     * a = (n - 1)* b + n * c = (n - 1) * L + c
     * */
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];

        // 找到快慢指针相遇的点
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (fast != slow);

        // 找到循环的起始点
        fast = nums[0];
        while (fast != slow) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}

验证回文串

class Solution {
    public boolean isPalindrome(String s) {
        int start = 0;
        int end = s.length() - 1;
        while(start <= end){
            while(start <= end && !Character.isLetterOrDigit(s.charAt(end))){
                end--;
            }
            while (start <= end && !Character.isLetterOrDigit(s.charAt(start))){
                start++;
            }
            if(start <= end){
                if(Character.toLowerCase(s.charAt(start)) != Character.toLowerCase(s.charAt(end))){
                    return false;
                }
            }
            start++;
            end--;
        }
        return true;
    }
}

移掉k位数字

import java.net.Inet4Address;
import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public String removeKdigits(String num, int k) {
        Deque<Character> stack = new LinkedList<>();
        for(int i = 0; i < num.length(); i++){
            char digit = num.charAt(i);
            while (!stack.isEmpty() && k>0 && stack.peekLast() > digit){
                stack.pollLast();
                k--;
            }
            stack.offerLast(digit);
        }
        for(int i = 0; i<k; i++){
            stack.pollLast();
        }
        StringBuilder sb = new StringBuilder();
        boolean isZero = true;
        while(!stack.isEmpty()){
            char digit = stack.pollFirst();
            if(isZero && digit == '0'){
                continue;
            }
            isZero = false;
            sb.append(digit);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

两两交换链表中的结点

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        while(pre.next != null && pre.next.next != null){
            ListNode node1 = pre.next;
            ListNode node2 = node1.next;

            pre.next = node2;
            node1.next = node2.next;
            node2.next = node1;

            pre = node1;
        }
        return dummy.next;
    }
}

优势洗牌

import java.util.Arrays;
class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        //核心在于进行匹配num1中的元素进行放置
        Integer[] idx1 = new Integer[nums1.length];
        Integer[] idx2 = new Integer[nums2.length];
        for(int i = 0; i < nums1.length; i++){
            idx1[i] = i;
            idx2[i] = i;
        }
        Arrays.sort(idx1, (i, j) -> nums1[i] - nums1[j]);
        Arrays.sort(idx2, (i, j) -> nums2[i] - nums2[j]);

        int[] ans = new int[nums1.length];
        int left = 0;
        int right = nums1.length - 1;
        for(int i = 0; i < nums1.length; i++){
            if(nums1[idx1[i]] > nums2[idx2[left]]){
                ans[idx2[left]] = nums1[idx1[i]];
                left++;
            }else{
                 ans[idx2[right]] = nums1[idx1[i]];
                 right--;
            }
        }
        return ans;
    }
}

二分查找

class Solution {
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;
        int mid = 0;
        while(start<=end){
            mid = (start+end)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                end = mid - 1;
            }else if(nums[mid]<target){
                start = mid + 1;
            }
        }
        return -1;
    }
}

二叉树的中序遍历

//递归
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        traverse(root,ans);
        return ans;
    }
    public void traverse(TreeNode root,List<Integer> ans){
        if(root == null)
            return ;
        traverse(root.left,ans);
        ans.add(root.val);
        traverse(root.right,ans);
    }
}
//非递归
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        while(root != null || !stack.isEmpty()){
            while (root != null){
                stack.push(root);
                root = root.left;
            }
            //此时弹出的是一个null
            root = stack.pop();
            ans.add(root.val);
            root = root.right;
        }
        return ans;
    }

最大子数组和

//贪心
class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = nums[0];
        for(int num : nums){
            sum += num;
            max = Math.max(max,sum);
            sum = Math.max(sum,0);
        }
        return max
;
    }
}
//动态规划
class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int maxSum = dp[0];

        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            maxSum = Math.max(maxSum, dp[i]);
        }

        return maxSum;
    }
}

k个逆序对数组

螺旋矩阵

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return ans;
        }

        int top = 0, left = 0;
        int below = matrix.length - 1, right = matrix[0].length - 1;

        while (left <= right && top <= below) {
            // Traverse top row
            for (int i = left; i <= right; i++) {
                ans.add(matrix[top][i]);
            }
            top++;

            // Traverse right column
            for (int i = top; i <= below; i++) {
                ans.add(matrix[i][right]);
            }
            right--;

            // Traverse bottom row
            if (top <= below) { // Check if top and below pointers are still valid
                for (int i = right; i >= left; i--) {
                    ans.add(matrix[below][i]);
                }
                below--;
            }

            // Traverse left column
            if (left <= right) { // Check if left and right pointers are still valid
                for (int i = below; i >= top; i--) {
                    ans.add(matrix[i][left]);
                }
                left++;
            }
        }
        return ans;
    }
}

两数之和

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i<nums.length; i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{i,map.get(target - nums[i])};
            }
            map.put(nums[i],i);
        }
        return new int[]{};
    }
}

划分字母区间

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> partitionLabels(String s) {
        int len = s.length();
        int[] ca = new int[27];
        for(int i = 0; i < len; i++){
            ca[s.charAt(i) - 'a'] = i;
        }
        int idx = 0;
        int last = -1;
        List<Integer> ans = new ArrayList<>();
        for(int i = 0 ; i<len; i++){
            idx = Math.max(idx,ca[s.charAt(i) - 'a']);
            if(idx == i){
                ans.add(i - last);
                last = idx;
            }
        }
        return ans;
    }
}

删除链表的倒数第N个结点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        //删除头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode fast = dummy;
        ListNode slow = dummy;

        // Move fast pointer n steps ahead
        for (int i = 0; i <= n; i++) {
            if (fast == null) {
                return null; // List length is less than n
            }
            fast = fast.next;
        }

        // Move both pointers until fast reaches the end
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // Remove the nth node from the end
        slow.next = slow.next.next;

        return dummy.next;
    }
}

多个数组求交集

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> intersection(int[][] nums) {
        int len = nums.length;
        int[] cnt = new int[1001];
        for(int[] arr : nums){
            for (int num : arr){
                cnt[num]++;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for(int i = 0; i< 1001 ; i++){
            if(cnt[i] == len){
                ans.add(i);
            }
        }
        return ans;
    }
}

环形链表II

/**
 * Definition for singly-linked list.
 * class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) {
 * val = x;
 * next = null;
 * }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(slow!=fast){
            if(fast == null || fast.next == null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = fast.next;
        slow = head;
        while(fast!=slow){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

子集II

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backTracking(nums,0);
        return ans;
    }
    public void backTracking(int[] nums,int start){
        ans.add(new ArrayList<>(path));
        for(int i = start; i<nums.length; i++){
            if(i > start && nums[i] == nums[i - 1]){
                continue;
            }
            path.add(nums[i]);
            backTracking(nums, i+1);
            path.remove(path.size() - 1);
        }
    }
}

正则表达式匹配

class Solution {
    public boolean isMatch(String s, String p) {
        int slen = s.length();
        int plen = p.length();
        boolean[][] dp = new boolean[slen + 1][plen + 1];
        dp[0][0] = true;

        for (int i = 0; i <= slen; i++) {
            for (int j = 1; j <= plen; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[slen][plen];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

全排列

import java.util.ArrayList;
import java.util.List;

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backTracking(nums);
        return ans;
    }
    private void backTracking(int[] nums){
        if(path.size() == nums.length){
            ans.add(new ArrayList<>(path));
        }
        for(int i = 0 ; i < nums.length; i++){
            if(path.contains(nums[i])){
                continue;
            }
            path.add(nums[i]);
            backTracking(nums);
            path.remove(path.size() - 1);
        }
    }
}