binary-tree-postorder-traversal

题目描述

Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
Given binary tree{1,#,2,3},
1
\
2
/
3

return[3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?

思路

递归遍历

代码

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    //后序遍历
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer>  result = new ArrayList<>();
        postOrderTraversalCore(result,root);
        return result;
    }
    private void postOrderTraversalCore(ArrayList<Integer>  result,TreeNode root){
        if(root == null) return;
        postOrderTraversalCore(result,root.left);
        postOrderTraversalCore(result,root.right);
        result.add(root.val);
    }
}

binary-tree-preorder-traversal

题目描述

Given a binary tree, return the preorder traversal of its nodes’ values.
For example:
Given binary tree{1,#,2,3},
1
\
2
/
3

return[1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?

思路

递归遍历

代码

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    //前序遍历
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer>  result = new ArrayList<>();
        preOrderTraversalCore(result,root);
        return result;
    }
    private void preOrderTraversalCore(ArrayList<Integer>  result,TreeNode root){
        if(root == null) return;
        result.add(root.val);
        preOrderTraversalCore(result,root.left);
        preOrderTraversalCore(result,root.right);
    }
}

insertion-sort-list

题目描述

Sort a linked list using insertion sort.

思路

新建一个链表,从原来的表中不断的取数据,再插入的过程中保证有序。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode p = head;
        while (p!=null){
            ListNode next = p.next;
            insert(dummy,p);
            p = next;
        }
        return dummy.next;
    }
    //dummy 是已经排序好的链表,第一个节点不用
    private void  insert(ListNode dummy,ListNode node){
        ListNode p = dummy;
        while (p.next!=null&& p.next.val<node.val){
            p=p.next;
        }
        ListNode next = p.next;
        p.next=node;
        node.next=next;
    }
}

sort-list

题目描述

Sort a linked list in O(n log n) time using constant space complexity.

思路

先用快慢指针找出链表的中间节点,然后再递归归并排序这这两段链表。

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode mid = findMid(head);
        ListNode right = mid.next;
        mid.next=null;
        return merge(sortList(head),sortList(right));
    }
    private ListNode merge(ListNode head1,ListNode head2){
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (head1!=null&&head2!=null){
            if(head1.val<=head2.val){
                cur.next=head1;
                head1=head1.next;
            }else {
                cur.next=head2;
                head2=head2.next;
            }
            cur=cur.next;
        }
        if(head1!=null){
            cur.next=head1;
        }else if(head2!=null){
            cur.next=head2;
        }
        return dummy.next;
    }
    //快慢指针求链表中间的节点
    private ListNode findMid(ListNode head){
        if(head == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next!=null && fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

max-points-on-a-line

题目描述

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

代码

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */

import java.util.*;
public class Solution {
   public int maxPoints(Point[] points) {
        if(points==null)return 0;
        if(points.length<2)return points.length;
        Map<Float,Integer> counts=new HashMap<>();
        int max=0;
        for (int i = 0; i < points.length; i++) {
            counts.clear();
            int samePoint=0;
            int verticalLine=0;

            for (int j = 0; j < points.length; j++) {
                if(i==j)continue;
                if(points[i].y == points[j].y && points[i].x == points[j].x){
                    //重合了,所有加一
                    samePoint++;
                    continue;
                }
                if(points[i].x == points[j].x){
                    //垂直
                    verticalLine++;
                    continue;
                }
                float slope = (float) (points[i].y-points[j].y)/(points[i].x-points[j].x);
                if(counts.containsKey(slope)){
                    counts.put(slope,counts.get(slope)+1);
                }else {
                    counts.put(slope,1);
                }

            }
            int tempMax = verticalLine;
            for (Float key:counts.keySet()) {
                tempMax = tempMax > counts.get(key)?tempMax:counts.get(key);
            }
            max = tempMax+samePoint+1>max?tempMax+samePoint+1:max;
        }
        return max;
    }
}

evaluate-reverse-polish-notation

题目描述

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are+,-,,/. Each operand may be an integer or another expression.
Some examples:
[“2”, “1”, “+”, “3”, “
“] -> ((2 + 1) * 3) -> 9
[“4”, “13”, “5”, “/”, “+”] -> (4 + (13 / 5)) -> 6

思路

使用一个操作栈,遇到数字,就入栈,遇到操作符从栈中弹出两个操作数,进行操作完以后把结果压回栈中,最后理论上栈中会剩一个元素,这元素就是表达式的最终结果。

代码

import java.util.Stack;
public class Solution {
    //["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
    public int evalRPN(String[] tokens) {
        if(tokens == null || tokens.length==0){
            return 0;
        }
        Stack<String> s = new Stack<>();
        int index=0;
        while (index<tokens.length){
            if(isNumber(tokens[index])){
                s.push(tokens[index]);
                index++;
            }else {
                //是操作符

                int right = Integer.parseInt(s.pop());
                int left = Integer.parseInt(s.pop());

                switch (tokens[index++]){
                    case "+":
                        s.push(String.valueOf(right+left));
                        break;
                    case "-":
                        s.push(String.valueOf(left-right));
                        break;
                    case "*":
                        s.push(String.valueOf(left*right));
                        break;
                    case "/":
                        s.push(String.valueOf(left/right));
                        break;
                    default:break;
                }
            }
        }
        return Integer.parseInt(s.peek());
    }
    private boolean isNumber(String str){
        try {
            Integer integer = Integer.parseInt(str);
            return true;
        }catch (Exception e){
            return false;
        }
    }
}

minimum-depth-of-binary-tree

题目描述

Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
给出一个二叉树,找它的最小深度

思路

和剑指offer里面的找树深度做法类似,先找出左右子树的深度,选最小的加一。

代码

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int run(TreeNode root) {
        if (root==null)return 0;
        int leftDepth = run(root.left);
        int rightDepth = run(root.right);
        if(leftDepth==0&&rightDepth==0){
            return 1;
        }
        if(leftDepth==0){
            return rightDepth+1;
        }
        if(rightDepth==0){
            return leftDepth+1;
        }
        return leftDepth<rightDepth?leftDepth+1:rightDepth+1;
    }
}

孩子们的游戏(圆圈中最后剩下的数)

题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。

请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)

代码

public class Solution {
    public int LastRemaining_Solution(int n,int m) {
        if(n==0) return -1;
         
       int s=0;
       for(int i=2;i<=n;i++){
           s=(s+m)%i;
       }
       return s;
    }
}

数据流中的中位数

题目描述

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

代码

import java.util.*;
public class Solution {

    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>( 15,new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    });

    int count = 0;

    public void Insert(Integer num) {
        if(count %2 ==0){
            //数据总数为偶数,新加入的元素,进入最小堆
            maxHeap.offer(num);
            int filteredMaxNum = maxHeap.poll();
            minHeap.offer(filteredMaxNum);
        }else {
            minHeap.offer(num);
            int filteredMinNum = minHeap.poll();
            maxHeap.offer(filteredMinNum);
        }
        count++;
    }

    public Double GetMedian() {
        if(count%2==0){
            return new Double((minHeap.peek()+maxHeap.peek()))/2;
        }else {
            return new Double(minHeap.peek());
        }
    }
}

滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

代码

import java.util.*;
public class Solution {
     public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if(size==0)return res;
        int begin;
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < num.length; i++) {
            begin = i - size + 1;
            if(q.isEmpty()){
                //q.add(i);
            }else if(begin > q.peekFirst()){
                q.pollFirst();
            }

            while ((!q.isEmpty()) && num[q.peekLast()] <= num[i]){
                q.pollLast();
            }
            q.add(i);
            if (begin >= 0){
                res.add(num[q.peekFirst()]);
            }
        }

        return res;
    }
}