算法--2023.1.16

1.实现Trie

class Trie {
    public int[][] edges;
    public int cnt;
    public boolean[] child; 
    public Trie() {
        //edges用来存节点的边
        edges = new int[300010][26];
        //cnt用来记录当前新建节点的编号
        cnt = 1;
        //child用来记录这个节点是否是根结点
        child = new boolean[300010];
    }
    
    public void insert(String word) {
        //插入逻辑：先遍历字典树
        int t = 0;
        for(int i = 0;i<word.length();i++){
            int k = word.charAt(i) - 'a';
            //如果字典树中存在，则继续向下遍历
            if(edges[t][k]!=0){
                t = edges[t][k];
            }else{
                //如果不存在则新建节点
                edges[t][k] = cnt;
                cnt++;
                t = edges[t][k];
            }
        }
        child[t] = true;

    }
    
    public boolean search(String word) {
        //查询逻辑：如果查询到当前节点，他的叶子节点不存在则直接返回
        int t = 0, i = 0;
        for(;i<word.length();i++){
            int k = word.charAt(i) - 'a'; 
            if(edges[t][k]!=0){
                t = edges[t][k];
            }else{
                return false;
            }
        }
        //System.out.println(t);
        //这里需要不断最后这个节点是否是child节点
        return child[t];

    }
    
    public boolean startsWith(String prefix) {
        int t = 0, i = 0;
        for(;i<prefix.length();i++){
            int k = prefix.charAt(i) - 'a'; 
            if(edges[t][k]!=0){
                t = edges[t][k];
            }else{
                return false;
            }
        }
        //这里需要判断
        return true;

    }
}

2.力扣215--数组中的第k个最大元素

class Solution {
    //快排找低k大的数
    public int[] nums1;
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        nums1 = new int[n];
        for(int i = 0;i<n;i++){
            nums1[i] = nums[i];
        }
        return quickSostKth(0,n-1,k);
    }
    public int quickSostKth(int left, int right, int k){
        if(left>=right){
            return nums1[left];
        }
        int l = left-1, r = right+1;
        int mid = nums1[(l+r)/2];
        while(l<r){
            do l++; while(l<r&&nums1[l]>mid);
            do r--; while(l<r&&nums1[r]<mid);
            if(l<r){
                int temp = nums1[l];
                nums1[l] = nums1[r];
                nums1[r] = temp;
            }
        }
        if((r-left+1)>=k){
            return quickSostKth(left,r,k);
        }
        return quickSostKth(r+1,right,k-(r-left+1));
    }
    
}

3.力扣221--最大正方形

class Solution {
    public int maximalSquare(char[][] matrix) {
        //dp[i][j]:代表以i，j为右下角的全是1的正方形的边长
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m+1][n+1];
        for(int i = 0;i<=n;i++){
            dp[0][i] = 0;
        }
        for(int i = 0;i<=m;i++){
            dp[i][0] = 0;
        }
        int res = 0;
        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                if(matrix[i-1][j-1] == '1'){
                    //这个状态转移我还没有想清楚
                    dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
                    res = Math.max(res,dp[i][j]);
                }
            }
        }
        return res*res;
    }
}

4.力扣226--翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

5.力扣234--回文链表

class Solution {
    public ListNode reverse(ListNode head){
        ListNode t = null;
        while(head!=null){
            ListNode cur = head.next;
            head.next = t;
            t = head;
            head = cur;
        }
        return t;
    }
    public boolean isPalindrome(ListNode head) {
        ListNode p = head,t = head;
        int cnt = 0;
        while(t!=null){
            t = t.next;
            cnt++;
        }
        if(cnt == 1){
            return true;
        }
        if(cnt%2 == 0){
            int k = cnt/2;
            while(k!=1){
                p = p.next;
                k--;
            }
            ListNode q = p.next;
            p.next = null;
            ListNode reverseHead = reverse(q);
            while(head!=null&&reverseHead!=null){
                if(head.val!=reverseHead.val){
                    return false;
                }
                head = head.next;
                reverseHead = reverseHead.next;
            }
        }else{
            int k = cnt/2;
            while(k!=1){
                p = p.next;
                k--;
            }
            ListNode q = p.next.next;
            p.next = null;
            ListNode reverseHead = reverse(q);
            while(head!=null&&reverseHead!=null){
                if(head.val!=reverseHead.val){
                    return false;
                }
                head = head.next;
                reverseHead = reverseHead.next;
            }
        }
        return true;
    }
}