思路：
state: cut[j]表示子串s[0…j]所需要的最小分割次数，isPalindrome[i][j]表示字符串s的子串s[i…j]是否为回文串
function:
initialize: cut[j] = j
answer: cut[j-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class {
public int minCut(String s) {
int n = s.length();
int[] cut = new int[n];
boolean[][] isPalindrome = new boolean[n][n];
for (int j = 0; j < n; j++) {
cut[j] = j;
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j)
&& (j - i <= 1 || isPalindrome[i + 1][j - 1])) {
isPalindrome[i][j] = true;
if (i > 0) {
cut[j] = Math.min(cut[j], cut[i - 1] + 1);
} else {
cut[j] = 0;
}
}
}
}
return cut[n - 1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class {
public ListNode deleteDuplicates(ListNode head) {
ListNode p = head;
while (p != null && p.next != null) {
if (p.val == p.next.val) {
p.next = p.next.next;
} else {
p = p.next;
}
}
return head;
}
}
|
思路：
引入虚节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode p = dummyHead;
while (p.next != null && p.next.next != null) {
int val = p.next.val;
if (p.next.val == p.next.next.val) {
p.next = p.next.next.next;
while (p.next != null && p.next.val == val) {
p.next = p.next.next;
}
} else {
p = p.next;
}
}
return dummyHead.next;
}
}
|
近期评论