力扣热题3-回溯、链表
按照leetcode刷一遍:leetcode hot
17. 电话号码的字母组合
回溯法。
class Solution {
public List<String> letterCombinations(String digits) {
String[] letters = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
List<String>result = new ArrayList<>();
StringBuilder sb = new StringBuilder();
letterCombinations0(digits,result,letters,sb,0);
return result;
}
private void letterCombinations0(String digits,List<String> result, String[] letters,StringBuilder sb,int start) {
if(start==digits.length()) {
if(sb.toString().equals("")) return;
result.add(sb.toString());
return;
}
//System.out.printf("%d\n",digits.charAt(start)-'0');
for(int i=0;i<letters[(int)(digits.charAt(start)-'0')].length();i++) {
sb.append(letters[digits.charAt(start)-'0'].charAt(i));
letterCombinations0(digits,result,letters,sb,start+1);
sb.deleteCharAt(sb.length()-1);
}
}
}
19. 删除链表的倒数第 N 个结点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fakeHead = new ListNode();
fakeHead.next = head;
//找当前节点的前一个
n++;
ListNode right = fakeHead;
while(n--!=0) {
right = right.next;
}
ListNode left = fakeHead;
while(right!=null) {
right = right.next;
left = left.next;
}
left.next = left.next.next;
return fakeHead.next;
}
}
20. 有效的括号
模拟栈
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(int i=0;i<s.length();i++) {
char c = s.charAt(i);
if(c=='('||c=='['||c=='{') {
stack.push(c);
} else {
if(stack.isEmpty()) {
return false;
}
if(c==')'&&stack.peek()=='('||
c==']'&&stack.peek()=='['||
c=='}'&&stack.peek()=='{') {
stack.pop();
} else {
stack.push(c);
}
}
}
return stack.isEmpty();
}
}
21. 合并两个有序链表
非递归解法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode fakeHead = new ListNode();
ListNode cur = fakeHead;
ListNode p1 = list1;
ListNode p2 = list2;
while(p1!=null && p2!=null) {
if(p1.val > p2.val) {
cur.next = p2;
p2 = p2.next;
} else {
cur.next = p1;
p1 = p1.next;
}
cur = cur.next;
}
if(p1!=null) cur.next = p1;
else if(p2!=null) cur.next = p2;
return fakeHead.next;
}
}
(再看看)递归解法
虽说递归解法不如上面效率高,但是思想还是可以学习一下的。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1==null) return list2;
if(list2==null) return list1;
if(list1.val > list2.val) {
list2.next = mergeTwoLists(list1,list2.next);
return list2;
} else {
list1.next = mergeTwoLists(list1.next,list2);
return list1;
}
}
}
22. 括号生成
常规递归回溯法
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
StringBuilder sb = new StringBuilder();
generateParenthesis0(n,sb,result,0,0);
return result;
}
private void generateParenthesis0(int n,StringBuilder sb,List<String> result,int count1,int count2) {
if(count1+count2==n*2) {
result.add(sb.toString());
return;
}
if(count1<n) {
sb.append('(');
generateParenthesis0(n,sb,result,count1+1,count2);
sb.deleteCharAt(sb.length()-1);
}
if(count1>count2) {
sb.append(')');
generateParenthesis0(n,sb,result,count1,count2+1);
sb.deleteCharAt(sb.length()-1);
}
}
}
竟然还有人尼玛用动态规划做,但是没有dfs好理解,不管了。
23. 合并K个升序链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0) return null;
ListNode fakeHead = new ListNode();
ListNode cur = fakeHead;
int pos;
PriorityQueue<ListNode> pq = new PriorityQueue<>((o1,o2)->o1.val-o2.val);
ListNode list;
for(int i=0;i<lists.length;i++) {
list = lists[i];
if(list==null) continue;
pq.add(list);
}
while(!pq.isEmpty()) {
cur.next = pq.poll();
cur = cur.next;
if(cur.next==null) continue;
else {
pq.add(cur.next);
}
}
return fakeHead.next;
}
}
26. 删除有序数组中的重复项
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length==0) return 0;
int idx = 1;
for(int i=1;i<nums.length;i++) {
if(nums[i]==nums[i-1]) continue;
nums[idx++] = nums[i];
}
return idx;
}
}