class Solution {
    public int uniquePaths(int m, int n) {
        int[][] memo = new int[m][n];
        return dfs(m-1,n-1,memo);
    }
    private int dfs(int i,int j,int[][] memo){
        if(i<0||j<0)return 0;
        if(i==0&&j==0)return 1;
        if(memo[i][j] != 0)return memo[i][j];
        return memo[i][j] = dfs(i-1,j,memo) + dfs(i,j-1,memo);
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m+1][n+1];
        //初始化
        for(int i=1;i<=m;i++)f[i][1] = 1;
        for(int i=1;i<=n;i++)f[1][i] = 1;
        
        for(int i=2;i<=m;i++){
            for(int j=2;j<=n;j++){
                f[i][j] = f[i-1][j] + f[i][j-1];
            }
        }
        return f[m][n];
    }
}

class Solution {
    public int minPathSum(int[][] g) {
        return dfs(g.length-1,g[0].length-1,g);        
    }
    private int dfs(int i,int j,int[][]g){
        if(i<0||j<0)return Integer.MAX_VALUE;
        if(i==0&&j==0)return g[i][j];
        return Math.min(dfs(i,j-1,g),dfs(i-1,j,g)) + g[i][j];
    }
}

class Solution {
    public int minPathSum(int[][] g) {
        int m = g.length;
        int n =g[0].length;
        int[][] memo = new int[m][n];
        for(int[] row : memo)Arrays.fill(row,-1);//-1表示没有计算过
        return dfs(m-1,n-1,g,memo);        
    }
    private int dfs(int i,int j,int[][]g,int[][] memo){
        if(i<0||j<0)return Integer.MAX_VALUE;
        if(i==0&&j==0)return g[i][j];
        if(memo[i][j] != -1)return memo[i][j];
        return memo[i][j] = Math.min(dfs(i,j-1,g,memo),dfs(i-1,j,g,memo)) + g[i][j];
    }
}

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] f = new int[m + 1][n + 1];
        Arrays.fill(f[0], Integer.MAX_VALUE);//初始化1
        f[0][1] = 0;//初始化2
        for (int i = 0; i < m; i++) {
            f[i + 1][0] = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                f[i + 1][j + 1] = Math.min(f[i + 1][j], f[i][j + 1]) + grid[i][j];
            }
        }
        return f[m][n];
    }
}

class Solution {
    public String longestPalindrome(String s) {
        if(s==null||s.length()<1)return "";
        //将原来的字符串转化为处理后的字符串 每个字符之间加入'#' 并在开头和结尾添加特殊字符
        StringBuilder sb = new StringBuilder("^");
        for(char c:s.toCharArray())sb.append('#').append(c);
        sb.append("#$");
        String T = sb.toString();

        int n = T.length();
        //表示回文半径
        int[] p = new int[n];
        int C = 0,R = 0;//中心 右边界
        int maxLen = 0,start = 0;
        for(int i=1;i<n-1;i++){
            int i_mirror = 2*C -i;//i关于C的对称点
            p[i] = (R>i)? Math.min(R-i,p[i_mirror]):1; 保证合法，右端点不超出R
            //尝试扩展回文半径
            while(T.charAt(i+p[i]) == T.charAt(i-p[i]))p[i]++;
            //如果宽展后的回文串右边界超过了R 那么需要更新中心和有边界
            if(i+p[i]>R){
                C = i;
                R = i + p[i];
            }
            //更新最长回文子串的长度和起始位置
            if(p[i]>maxLen){
                maxLen = p[i];
                start = (i-maxLen)/2;//计算原始字符串的起始位置
            }
        }
        //返回最长回文子串
        return s.substring(start,start + maxLen - 1);
    }
}

class Solution {
    private char[] s, t;
    private int[][] memo;
    public int longestCommonSubsequence(String text1, String text2) {
        s = text1.toCharArray();
        t = text2.toCharArray();
        int n = s.length;
        int m = t.length;
        memo = new int[n][m];
        for(int[] row : memo)Arrays.fill(row,-1);//表示没有计算过
        return dfs(n-1,m-1);
    }
    //index<n,m的最长公共子序列的长度
    private int dfs(int i,int j){
        if(i<0||j<0)return 0;
        if(memo[i][j] !=-1)return memo[i][j];//之前计算过
        if(s[i] == t[j])return memo[i][j] = dfs(i-1,j-1)+1;
        return memo[i][j] = Math.max(dfs(i-1,j),dfs(i,j-1));
    }

}

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] s = text1.toCharArray();
        char[] t = text2.toCharArray();
        int n = s.length;
        int m = t.length;
        int[][] f = new int[n + 1][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                f[i + 1][j + 1] = (s[i] == t[j] ? f[i][j] + 1 :
                                  Math.max(f[i][j + 1], f[i + 1][j]) );
            }
        }
        return f[n][m];
    }
}

class Solution {
    public int minDistance(String word1, String word2) {
        char[] s = word1.toCharArray();
        char[] t = word2.toCharArray();
        int n = s.length;
        int m = t.length;
        int[][] f = new int[n + 1][m + 1];
        
        // 初始化
        for (int i = 0; i <= n; i++) f[i][0] = i;
        for (int j = 0; j <= m; j++) f[0][j] = j;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s[i] == t[j]) {
                    f[i + 1][j + 1] = f[i][j]; // 当字符相等时，直接使用f[i][j]的值
                } else {
                    f[i + 1][j + 1] = Math.min(Math.min(f[i][j + 1], f[i + 1][j]), f[i][j]) + 1;
                }
            }
        }
        return f[n][m];
    }
}

class Solution {
    public int singleNumber(int[] nums) {
        int x = 0;
        for (int num : nums)  // 1. 遍历 nums 执行异或运算
            x ^= num;//^同0异1
        return x;            // 2. 返回出现一次的数字 x

    }
}

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0,votes = 0;
        for(int num:nums){
            if(votes == 0) x = num;
            votes += (num==x?1:-1);
        }
        return x;
    }
}

class Solution {
    public void sortColors(int[] nums) {
        //n0表示0的数量 n1表示0和1的数量 双指针 三次刷漆
        int n0 = 0,n1 = 0;
        for(int i=0;i<nums.length;i++){//i表示012的数量
            int num = nums[i];
            nums[i] = 2;
            if(num<2)nums[n1++] = 1;//指针1指向
            if(num<1)nums[n0++] = 0;//指针0指向
        }
    }
}

class Solution {
    public int findDuplicate(int[] nums) {
        // 快慢指针初始化
        int slow = nums[0];
        int fast = nums[0];
        
        // 找到快慢指针相遇的位置
        do {
            slow = nums[slow]; // 慢指针每次走一步
            fast = nums[nums[fast]]; // 快指针每次走两步
        } while (slow != fast);
        
        // 寻找环的入口，即重复的数字
        int ptr1 = nums[0];
        int ptr2 = slow;
        while (ptr1 != ptr2) {
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }
        
        return ptr1; // 返回重复的数字
    }
}