头像

JinxinLi


访客:5936

离线:4天前


活动打卡代码 LeetCode 148. Sort List

JinxinLi
2个月前
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p = dummy;
        int n = 0;
        while (p.next != null) {
            n++;
            p = p.next;
        }

        for (int step = 1; step < n; step *= 2) {
            ListNode cur = dummy.next;//同dummy防止之后head要再换的情况
            ListNode tail = dummy;
            while (cur != null) {
                ListNode left = cur;
                ListNode right = cut(left, step);
                cur = cut(right, step);
                // System.out.println(right.val);
                tail.next = merge(left, right);
                while (tail.next != null) {
                    tail = tail.next;
                }
            }
        }
        return dummy.next;
    }

    private ListNode cut(ListNode head, int n) {
        ListNode p = head;
        while (--n > 0 && p != null) {
            p = p.next;
        }
        if (p == null) return null;
        ListNode q = p.next;
        p.next = null;
        return q;
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 != null) cur.next = l1;
        if (l2 != null) cur.next = l2;
        return dummy.next;
    }
}



JinxinLi
2个月前
class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        s = " " + s;
        p = " " + p;
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0][0] = true;

        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p.charAt(j) != '*') {
                    if (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.') {
                        if (i > 0) f[i][j] = f[i - 1][j - 1];
                    }
                } else {
                    if (j > 1) f[i][j] = f[i][j - 2];
                    if (i > 0 && (p.charAt(j - 1) == s.charAt(i) || p.charAt(j - 1) == '.')) {
                        f[i][j] = f[i][j] | f[i][j - 1] | f[i - 1][j] ;
                    }
                }
            }
        }
        return f[n][m];        
    }
}


活动打卡代码 LeetCode 664. Strange Printer

JinxinLi
2个月前
class Solution {
    public int strangePrinter(String s) {
        if (s == null || s.length() == 0) return 0;
        char[] S = s.toCharArray();
        int n = S.length;
        int[][] f = new int[n + 1][n + 1];

        for (int len = 1; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                f[l][r] = f[l + 1][r] + 1;// 当 l = n - 1的时候,l+1则无效,所以需要用n + 1 
                for (int k = l + 1; k <= r; k++) {
                    if (S[k] == S[l])
                        f[l][r] = Math.min(f[l][r], f[l][k - 1] + f[k + 1][r]);
                } 
            }
        }

        return f[0][n - 1];
    }
}


活动打卡代码 LeetCode 518. Coin Change 2

JinxinLi
2个月前
class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] f = new int[amount + 1];
        f[0] = 1;
        for (int c : coins) {
            for (int j = c; j <= amount; j++) {
                f[j] += f[j - c];
            }
        }
        return f[amount];
    }
}


活动打卡代码 LeetCode 72. Edit Distance

JinxinLi
2个月前
class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[][] f = new int[n + 1][m + 1];

        for (int i = 0; i <= n; i++) {
            f[i][0] = i;
        }
        for (int i = 0; i <= m; i++) {
            f[0][i] = i;
        }
        //f[i][j] = f[i - 1][j] // f[i][j - 1] // 同f[i][j]
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                } else {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
                }
            }
        }
        return f[n][m];
    }
}



JinxinLi
2个月前
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        //插入到最大的小于a[i]的数后面,如果求出最大的小于的数是r,那么a[i]的位置是q[r+1]
        int[] tails = new int[nums.length + 1];
        int len = 0;
        tails[0] = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int l = 0, r = len;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (tails[mid] < nums[i]) l = mid;
                else r = mid - 1;
            }
            len = Math.max(len, r + 1);
            tails[r + 1] = nums[i];
        }
        return len;
    }
}


活动打卡代码 LeetCode 198. House Robber

JinxinLi
2个月前
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] f = new int[2];
        f[0] = 0;
        f[1] = nums[0];
        int temp = f[0];
        for (int i = 1; i < n; i++) {
            f[0] = Math.max(f[1], temp);
            f[1] = temp + nums[i];
            temp = f[0];
        }
        return Math.max(f[0], f[1]);
    }
}


活动打卡代码 LeetCode 91. Decode Ways

JinxinLi
2个月前
class Solution {
    public int numDecodings(String s) {
        //
        if (s == null || s.length() == 0) return 0;

        int n = s.length();
        int[] f = new int[n + 1];
        s = " " + s;
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (s.charAt(i) >= '1' && s.charAt(i) <= '9') {
                f[i] += f[i - 1];
            }
            if (i > 1) {

                int num = (s.charAt(i - 1) - '0')  * 10 + s.charAt(i) - '0';
                if (num >= 10 && num <= 26) f[i] += f[i - 2];
            }
        }
        return f[n];
    }
}


活动打卡代码 LeetCode 63. Unique Paths II

JinxinLi
2个月前
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[][] f = new int[n][m];
        f[0][0] = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (obstacleGrid[i][j] == 1) {
                    f[i][j] = 0;
                }    
                else {
                    if (j > 0) f[i][j] += f[i][j - 1];
                    if (i > 0) f[i][j] += f[i - 1][j];
                }
            }
        }
        return f[n - 1][m - 1];
    }
}


活动打卡代码 LeetCode 120. Triangle

JinxinLi
2个月前
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        //自下而上来走
        int min = Integer.MAX_VALUE;
        int n = triangle.size();
        int[] f = new int[n + 1];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                f[j] = Math.min(f[j], f[j + 1]) + triangle.get(i).get(j);
            }
        }
        return f[0];
    }
}