标签归档:leetcode

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