力扣热题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 个结点

image-20220131235306694

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