当前位置:

首页 > 编程开发 > Java教程 >

LeetCode剑指Offer刷题总结（四）

从上到下打印二叉树 32-III

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return ans;
        }
        deque.add(root);
        while((list = pollAll(deque)) != null){
            if(ans.size() % 2 != 0){
                Collections.reverse(list);
            }
            ans.add(list);
        }
        return ans;
    }

    public List<Integer> pollAll(Deque<TreeNode> deque){
        TreeNode tr;
        List<Integer> list = new ArrayList<>();
        int n = deque.size();
        if(n==0)
            return null;
        for (int i = 0 ; i < n ; i++){
            tr = deque.poll();
            list.add(tr.val);
            if(tr.left!=null){
                deque.add(tr.left);
            }
            if(tr.right!=null){
                deque.add(tr.right);
            }
        }
        return list;
    }
}

只需要稍稍注意加上反转条件，与32-2相同流程。

二叉搜索树的后序遍历序列 33

二叉搜索树：左子树中所有节点的值 << 根节点的值；右子树中所有节点的值 >> 根节点的值；其左、右子树也分别为二叉搜索树。

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(0,postorder.length-1, postorder);
    }

    public boolean recur(int i , int j, int[] postorder){
        if(i>=j) return true;
        int p = i;
        while(postorder[p]<postorder[j]) p++;
        int m = p;
        while(postorder[p]>postorder[j]) p++;
        return p==j && recur(i,m-1,postorder) && recur(m,j-1,postorder);
    }
}

这个思路在于，判断整数序列是否符合后序遍历特点，<左子树>，<右子树>，<根节点>。符合之后，对子树进行判断，写一个递归。

二叉树中和为某一值的路径 34

class Solution {
    Deque<Integer> list = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root,target);
        return res;
    }

    public void dfs(TreeNode root, int target) {
        if(root == null)
            return ;
        list.offerLast(root.val);
        target = target - root.val;
        if(target==0 && root.left==null && root.right==null)
            res.add(new LinkedList<Integer> (list));
        dfs(root.left,target);
        dfs(root.right,target);
        list.pollLast();
    }
}

本题需要对二叉树的路径进行递归，判断每个叶子节点是否满足和为target。

注意：这里有一个小细节，list为Deque是为了方便遍历，而Deque->List<Integer> 则是利用了 LinkedList的构造方法，可以将Collection对象直接构造为List。

二叉搜索树与双向链表 36

class Solution {
    Node head,pre;
    public Node treeToDoublyList(Node root) {
        if(root == null)
            return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    public void dfs(Node cur) {
        if(cur == null)
            return ;
        dfs(cur.left);
        if(pre != null)
            pre.right = cur;
        else head = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}

二叉搜索树的中序遍历即为按从小到大排序。需要注意的是节点的指针更换方式。

序列化二叉树 37

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        Deque<TreeNode> deque = new LinkedList<>() {{add(root);}};
        StringBuilder ans = new StringBuilder("[");
        while( deque.size() !=0 ) {
            TreeNode temp = deque.poll();
            if(temp != null){
                ans.append(temp.val+",");
                deque.add(temp.left);
                deque.add(temp.right);
            }
            else{
                ans.append("null,");
            }
        }
        ans.deleteCharAt(ans.length()-1);
        ans.append("]");
        return ans.toString();
    }

    // Decodes your encoded data to tree.
     public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] vals = data.substring(1,data.length()-1).split(",");
        TreeNode node = new TreeNode(Integer.parseInt(vals[0]));
        Deque<TreeNode> deque = new LinkedList<>() {{add(node);}};
        int i = 1;
        while( i < vals.length ) {
            TreeNode temp = deque.poll();
            if(!vals[i].equals("null")){
                temp.left = new TreeNode(Integer.parseInt(vals[i]));
                deque.add(temp.left);
            }
            i++;
            if(!vals[i].equals("null")){
                temp.right = new TreeNode(Integer.parseInt(vals[i]));
                deque.add(temp.right);
            }
            i++;
        }
        return node;
    }
}

本题的思路在于建立队列对二叉树结构进行BFS，实际算法思路并不复杂，主要在于理清算法流程。

字符串的排列 38 （全排列题型）

class Solution {

    List<String> res = new LinkedList<>();
    char[] c ;

    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }

    void dfs(int x) {
        if( x == c.length -1 ){
            res.add(String.valueOf(c));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x ; i < c.length ; i++) {
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            swap(i,x);
            dfs(x+1);
            swap(i,x);
        }
    }

    void swap(int a, int b) {
        char temp = c[a];
        c[a] = c[b];
        c[b] = temp;
        return ;
    }
}

这道题是回溯法的典型应用，利用深搜进行一个字符串的全排列组合，同时注意每个字符位置的剪枝（遇到重复的元素直接跳过）。

数组中出现次数超过一半的数字 39（求众数）

本题有多种思路，排序，利用map进行计数，以及摩尔计数法。

摩尔计数法实际上可以理解为假设共有n个不同的数字，即有n方势力，每两方可以对拼消耗，无论如何消耗，最终剩下来的肯定是最大的一方势力。（在存在众数的情况下）

1：HashMap 时间复杂度O(N)，空间复杂度O(N)

class Solution {
    public int majorityElement(int[] nums) {
        int len = nums.length/2;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i : nums){
            if(map.containsKey(i)){
                int count = map.get(i);
                map.put(i,count+1);
            }
            else{
                map.put(i,1);
            }
        }
        for(Integer o : map.keySet()){
            if(map.get(o) > len)
                return o;
        }
        return 0;
    }
}

2：摩尔投票法

class Solution {
    public int majorityElement(int[] nums) {
        int votes=0,x=0;
        for(int i : nums) {
            if(votes ==0) {
                votes++;
                x = i;
                continue;
            }
            if(i == x) votes++;
            else votes--;
        }
        return x;
    }
}

思路都较为简单，理解即可。

最小的k个数 40 （TOP K）

多种思路：排序，维护大根堆的前k个元素，快排变形

1：排序思路

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] ans = new int[k];
        if(k==0) return ans;
        Arrays.sort(arr);
        for(int i= 0 ; i < k ; i++){
            ans[i] = arr[i];
        }
        return ans;
    }
}

2：利用大根堆

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];
        if(k==0) return res;
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2){
                return o2 - o1;
            }
        });
        for(int i = 0 ; i < k ; i++){
            queue.offer(arr[i]);
        }
        for(int j = k ; j < arr.length ; j++){
            if(arr[j] < queue.peek()){
                queue.poll();
                queue.offer(arr[j]);
            }
        }
        for(int i = 0 ; i < k ; i++){
            res[i] = queue.poll();
        }
        return res;
    }
}

这里要注意，java默认的是小根堆，所以需要重写compare方法，维护前K个元素即可。

return o1-o2(升序) return o2-o1(降序)

3：快排变形

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k==0 || arr.length==0) return new int[0];
        return quickSearch(arr,0,arr.length-1,k-1);
    }

    public int[] quickSearch(int[] num,int l,int r,int k){
        int j = partition(num,l,r);
        if(j==k){
            return Arrays.copyOf(num,j+1);
        }
        return j > k ? quickSearch(num,l,j-1,k) : quickSearch(num,j+1,r,k); //j本身是没用的可以跳过
    }

    public int partition(int[] nums,int l,int r){
        int tmp = nums[l];
        int i=l,j=r+1;
        while(true){
            while(++i<r && nums[i]<tmp) ;
            while(--j>l && nums[j]>tmp) ;
            if(i>=j) break;
            int t = nums[i];
            nums[i]=nums[j];
            nums[j]=t;
        }
        nums[l] = nums[j];
        nums[j] = tmp;
        return j;
    }
}

这里相较于快排只是缺少最终对整体的递归，主要在于判断每次快排第一个元素在数组中的位置，并放到相应位置。

数据流中的中位数 41

class MedianFinder {

    Queue<Integer> A,B;

    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<>();
        B = new PriorityQueue<>((x,y) -> (y-x));
    }
    
    public void addNum(int num) {
        if(A.size()!=B.size()){
            A.add(num);
            B.add(A.poll());
        }
        else{
            B.add(num);
            A.add(B.poll());
        }
    }
    
    public double findMedian() {
        return A.size()>B.size() ? A.peek() : (A.peek()+B.peek())/2.0;
    }
}

代码不长，主要利用2个堆：一个大根堆一个小根堆，对元素进行大小分割，小元素在大根堆里，大元素在小根堆里。

试想一下，这样的话，堆顶就是中位数了，具体实现思想是：A，B两个堆，A=B=0或其他数时，向B添加元素，出B堆顶元素到A，保证去A的元素为较小一方；当A!=B时，A加元素，出A堆顶元素到B，保证去B的元素较大。从A=B=1时开始就会一直保持A较小一方，B较大一方，需要自己理解一下。

连续子数组的最大和 42

该题利用动态规划(N)和暴力求解(N^2)均可

动态规划：

class Solution {
    public int maxSubArray(int[] nums) {
        int max,pre=nums[0];
        max = pre;
        for(int i = 1 ; i < nums.length ; i++) {
            pre = nums[i] > (pre+nums[i]) ? nums[i] : (pre+nums[i]);
            max = max > pre ? max : pre;
        }
        return max;
    }
}

因为是连续子数组，pre代表当前i为最后一位，对应的连续子数组最大值。需要体会一下状态转移过程。

本文作者： GaoYuan206
本文链接： https://www.cnblogs.com/gaoyuan206/p/15402465.html

栏目列表