几个leetcode题型练练手


阿里云师兄说要补一个笔试,果然还是系统笔试只做出来一道太拉了吗:? 不过挺师兄的语气挺轻松:就是写两段代码。但是不打无准备之仗,还是几个类型的题找找手感先。

链表

剑指 Offer II 078. 合并排序链表

/**
 * 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) {
        int n = lists.length;
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((o1,o2)->o1.val-o2.val);
        for(int i=0;i<n;i++) {
            if(lists[i]!=null) minHeap.add(lists[i]);
        }
        ListNode tmp;
        ListNode fakeHead = new ListNode();
        ListNode cur = fakeHead;
        while(!minHeap.isEmpty()) {
            tmp = minHeap.poll();
            cur.next = tmp;
            cur = cur.next;
            if(tmp.next!=null) {
                minHeap.add(tmp.next);
            }
        }
        return fakeHead.next;
    }
}

剑指 Offer II 077. 链表排序

链表快排

/**
 * 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 sortList(ListNode head) {
        // 试一下链表快排
        if(head==null || head.next==null) {
            return head;
        }

        int n = 0;
        ListNode t = head;
        while(t!=null) {
            n++;
            t = t.next;
        }

        int c = new Random().nextInt(n);
        ListNode p = head;
        for(int i=0;i<c;i++) {
            p = p.next;
        }

        ListNode cur = head;
        ListNode middle = new ListNode();
        ListNode curMiddle = middle;
        ListNode left = new ListNode();
        ListNode curLeft = left;
        ListNode right = new ListNode();
        ListNode curRight = right;
        while(cur!=null) {
            if(cur.val==p.val) {
                curMiddle.next = cur;
                curMiddle = curMiddle.next;
            } else if(cur.val>p.val) {
                curRight.next = cur;
                curRight = curRight.next;
            } else {
                curLeft.next = cur;
                curLeft = curLeft.next;
            }
            cur = cur.next;
        }
        curMiddle.next = null;
        curLeft.next = null;
        curRight.next = null;
        ListNode resultFakeHead = new ListNode();
        ListNode result = resultFakeHead;
        ListNode ll = left.next;
        

        left = sortList(left.next);
        right = sortList(right.next);
        result.next = left;
        while(result.next!=null) {
            result = result.next;
        }
        result.next = middle.next;
        while(result.next!=null) {
            result = result.next;
        }
        result.next = right;
        while(result.next!=null) {
            result = result.next;
        }
        result.next = null;
        return resultFakeHead.next;
    }
}

放入容器中排序

/**
 * 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 sortList(ListNode head) {
        if(head==null||head.next==null) {
            return head;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode cur = head;
        while(cur!=null) {
            list.add(cur);
            cur = cur.next;
        }
        Collections.sort(list,(o1,o2)->o1.val-o2.val);
        ListNode fakeHead = new ListNode();
        cur = fakeHead;
        for(ListNode node:list) {
            cur.next = node;
            cur = cur.next;
        }
        cur.next = null;
        return fakeHead.next;
    }
}

字符串

1023. 驼峰式匹配

class Solution {
    public List<Boolean> camelMatch(String[] queries, String pattern) {
        List<Boolean> list = new ArrayList<>();
        for(int k=0;k<queries.length;k++) {
            String query = queries[k];
            int pid = 0;
            int i=0;
            for(;i<query.length();i++) {
                if(pid<pattern.length()) {
                    if(query.charAt(i)==pattern.charAt(pid)) {
                        pid++;
                    } else if(query.charAt(i)>='A'&&query.charAt(i)<='Z') {
                        break;
                    }
                } else if(pid==pattern.length()) {
                    if(query.charAt(i)>='A'&&query.charAt(i)<='Z') {
                        break;
                    }
                }
            }
            list.add(i==query.length()&&pid==pattern.length());
        }
        return list;
    }
}

二叉树

95. 不同的二叉搜索树 II

回溯法(有重复解)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> result = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for(int i=1;i<=n;i++) {
            set.add(i);
        }
        Set<Integer> nextSet = new HashSet(set);
        for(int r:set) {
            TreeNode root = new TreeNode(r);
            nextSet.remove(r);
            generateTrees0(result,nextSet,root);
            nextSet.add(r);
        }
        return result;
    }

    private TreeNode copy(TreeNode root) {
        if(root==null) return null;
        TreeNode result = new TreeNode(root.val);
        result.left = copy(root.left);
        result.right = copy(root.right);
        return result;
    }

    public void generateTrees0(List<TreeNode> result,Set<Integer> set,TreeNode root) {
        if(set.size()==0) result.add(copy(root));
        Set<Integer> nextSet = new HashSet(set);
        for(int r:set) {
            TreeNode node = new TreeNode(r);
            nextSet.remove(r);
            TreeNode cur = root;
            while(true) {
                if(r>cur.val) {
                    if(cur.right==null) {
                        cur.right = node;
                        generateTrees0(result,nextSet,root);
                        cur.right = null;
                        break;
                    }
                    cur = cur.right;
                } else {
                    if(cur.left==null) {
                        cur.left = node;
                        generateTrees0(result,nextSet,root);
                        cur.left = null;
                        break;
                    }
                    cur = cur.left;
                }
            }

            
            nextSet.add(r);
        }
    }
}

递归分区

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<TreeNode> result;
    public List<TreeNode> generateTrees(int n) {
        result = new ArrayList<>();
        return generateTreesHelper(1,n);
    }

    private TreeNode copy(TreeNode root) {
        if(root==null) return null;
        TreeNode result = new TreeNode(root.val);
        result.left = copy(root.left);
        result.right = copy(root.right);
        return result;
    }

    private List<TreeNode> generateTreesHelper(int start,int end) {
        List<TreeNode> result = new ArrayList<>();
        if(start>end) {
            result.add(null);
            return result;
        }
        for(int i=start;i<=end;i++) {
            TreeNode cur = new TreeNode(i);
            for(TreeNode node1:generateTreesHelper(start,i-1)) {
                for(TreeNode node2:generateTreesHelper(i+1,end)) {
                    TreeNode ro = copy(cur);
                    ro.left = node1;
                    ro.right = node2;
                    result.add(ro);
                }
            }
        }
        return result;
    }
}

动态规划

119. 杨辉三角 II

class Solution {
    public List<Integer> getRow(int rowIndex) {
        int[] before = new int[rowIndex+1];
        int[] result = new int[rowIndex+1];
        before[0] = 1;
        for(int i=1;i<=rowIndex;i++) {
            for(int j=0;j<=i;j++) {
                if(j-1<0||j>=i) {
                    result[j] = 1;
                } else {
                    result[j] = before[j-1]+before[j];
                }
            }
            int[] tmp = before;
            before = result;
            result = tmp;
        }
        //System.out.println(Arrays.toString(before));
        List<Integer> res = new ArrayList<>();
        for(int i=0;i<=rowIndex;i++) {
            res.add(before[i]);
        }
        return res;
    }
}

二分查找

287. 寻找重复数

二分

class Solution {
    public int findDuplicate(int[] nums) {
        int start = 1;
        int end = nums.length-1;

        while(start<end) {
            int mid = (start+end)/2;
            int leftCount = 0;
            int rightCount = 0;
            for(int num:nums) {
                if(num>=start&&num<=mid) {
                    leftCount++;
                } else {
                    rightCount++;
                }
            }
            if(leftCount>mid-start+1) {
                end = mid;
            } else {
                start = mid+1;
            }
        }
        return start;
    }
}

环形链表。

多线程

FooBar

import java.util.*;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.Semaphore;
import java.util.stream.IntStream;

public class Main{
    private Semaphore semaphoreFoo = new Semaphore(1);
    private Semaphore semaphoreBar = new Semaphore(0);

    public  void printFoo() throws InterruptedException {
        for(int i=0;i<100;i++) {
            semaphoreFoo.acquire();
            System.out.print("Foo");
            semaphoreBar.release();
        }
    }
    public void printBar() throws InterruptedException {
        for(int i=0;i<100;i++) {
            semaphoreBar.acquire();
            System.out.println("Bar");
            semaphoreFoo.release();
        }
    }
    public static void main(String[] args) throws InterruptedException {
        final Main inst = new Main();
        final CountDownLatch latch = new CountDownLatch(2);
        new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    inst.printFoo();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                latch.countDown();
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    inst.printBar();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                latch.countDown();
            }
        }).start();
        latch.await();
    }
}