JinxinLi

JinxinLi
2个月前
/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
int n = 0;
while (p.next != null) {
n++;
p = p.next;
}

for (int step = 1; step < n; step *= 2) {
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) {
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];
}
}


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];
}
}


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];
}
}


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;
}
}


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]);
}
}


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];
}
}


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];
}
}


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];
}
}