月度归档:2017年06月

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

机器人的运动范围

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?

思路

回溯

代码

import java.util.*;
public class Solution {
    public static class Location{
        int row;
        int col;
        Location(int row,int col){
            this.row=row;
            this.col=col;
        }
    }
    //检查合法性
    private int getReadLocation(int rows, int cols,int locRow, int locCol){
        //是否越界
        if(locRow<0 || locRow>=rows || locCol<0|| locCol>=cols){
            return -1;
        }
        return locRow*cols+locCol;
    }
    private int getDigitSum(int num){
        int sum=0;
        while (num!=0){
            sum+=(num%10);
            num/=10;
        }
        return sum;
    }
    public int movingCount(int threshold, int rows, int cols) {
        if(threshold<0)return 0;
        Queue<Location> queue = new LinkedList<>();
        boolean[] isGone=new boolean[rows*cols];
        for (int i = 0; i < isGone.length; i++) {
            isGone[i]=false;
        }
        queue.add(new Location(0,0));
        isGone[getReadLocation(rows,cols,0,0)]=true;
        while (!queue.isEmpty()){
            Location location = queue.poll();
            //上
            if(getReadLocation(rows,cols,location.row-1,location.col)!=-1
                    &&isGone[getReadLocation(rows,cols,location.row-1,location.col)]==false
                    &&(getDigitSum(location.row-1)+getDigitSum(location.col)<=threshold)){
                queue.add(new Location(location.row-1,location.col));
                isGone[getReadLocation(rows,cols,location.row-1,location.col)]=true;
//                System.out.println("up-sum:"+"("+(location.row-1)+","+getDigitSum(location.col)+"):"+(getDigitSum(location.row-1)+getDigitSum(location.col)));
            }
            //下
            if(getReadLocation(rows,cols,location.row+1,location.col)!=-1
                    &&isGone[getReadLocation(rows,cols,location.row+1,location.col)]==false
                    &&(getDigitSum(location.row+1)+getDigitSum(location.col)<=threshold)){
                queue.add(new Location(location.row+1,location.col));
                isGone[getReadLocation(rows,cols,location.row+1,location.col)]=true;
//                System.out.println("down-sum:"+"("+(location.row+1)+","+getDigitSum(location.col)+"):"+(getDigitSum(location.row+1)+getDigitSum(location.col)));
            }
            //左
            if(getReadLocation(rows,cols,location.row,location.col-1)!=-1
                    &&isGone[getReadLocation(rows,cols,location.row,location.col-1)]==false
                    &&(getDigitSum(location.row)+getDigitSum(location.col-1)<=threshold)){
                queue.add(new Location(location.row,location.col-1));
                isGone[getReadLocation(rows,cols,location.row,location.col-1)]=true;
//                System.out.println("left-sum:"+"("+(location.row)+","+getDigitSum(location.col-1)+"):"+(getDigitSum(location.row)+getDigitSum(location.col-1)));
            }
            //右
            if(getReadLocation(rows,cols,location.row,location.col+1)!=-1
                    &&isGone[getReadLocation(rows,cols,location.row,location.col+1)]==false
                    &&(getDigitSum(location.row)+getDigitSum(location.col+1)<=threshold)){
                queue.add(new Location(location.row,location.col+1));
                isGone[getReadLocation(rows,cols,location.row,location.col+1)]=true;
//                System.out.println("right-sum:"+"("+(location.row)+","+getDigitSum(location.col+1)+"):"+(getDigitSum(location.row)+getDigitSum(location.col+1)));
            }
        }
        int result = 0;
        for (int i = 0; i < isGone.length ; i++) {
            if(isGone[i]){
                result++;
            }
        }
        return result;
    }
    public static void main(String[] args){
        Solution s = new Solution();
        System.out.println(s.movingCount(5,10,10));
        int sum = s.getDigitSum(16);
        int ab=0;
        int cnt=0;
        for (int i = 0; i <10 ; i++) {
            for (int j = 0; j <10 ; j++) {
                int c =s.getDigitSum(i)+s.getDigitSum(j);
                System.out.print(c+"  ");
                if(c<=5)cnt++;
            }
            System.out.println();
        }
        System.out.println(cnt);
    }
}

矩阵中的路径

题目描述

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径,但是矩阵中不包含”abcb”路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

思路

由于牛客网这里的输入的矩阵是一个一维数组,所以就用了个转换函数,但还是用二维的思路去做,回溯思想,没什么特别

代码

import java.util.*;
public class Solution {
    /**
     *
     * @param matrix
     * @param rows 行
     * @param cols 列
     * @param str
     * @return
     */
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if (matrix==null||matrix.length==0||str==null||str.length==0)return false;
        boolean[] isGone = new boolean[matrix.length];
        for (int i = 0; i <isGone.length ; i++) {
            isGone[i]=false;
        }
        for (int i = 0; i <rows ; i++) {
            for (int j = 0; j <cols ; j++) {
                if(hasPathCore(matrix,rows,cols,str,i,j,0,isGone)){
                    return true;
                }
            }
        }
        return false;
    }
    private boolean hasPathCore(char[] matrix, int rows, int cols, char[] str,
                                int locRow, int locCol,int strIndex,boolean[] isGone){
        //是否越界
        if(locRow<0 || locRow>=rows || locCol<0|| locCol>=cols){
            return false;
        }
        //是否已经走过
        if(isGone[getReadLocation(rows,cols,locRow,locCol)]){
            return false;
        }
        //是否与目标字符相同
        if(str[strIndex]!=matrix[getReadLocation(rows,cols,locRow,locCol)]){
            return false;
        }
        isGone[getReadLocation(rows,cols,locRow,locCol)]=true;
        //是否识别完成
        if(strIndex==str.length-1){
            isGone[getReadLocation(rows,cols,locRow,locCol)]=false;
            return true;
        }
        //还没有完成,继续走
        //上
        if(hasPathCore(matrix,rows,cols,str,locRow-1,locCol,strIndex+1,isGone)){
            isGone[getReadLocation(rows,cols,locRow,locCol)]=false;
            return true;
        }
        //下
        if(hasPathCore(matrix,rows,cols,str,locRow+1,locCol,strIndex+1,isGone)){
            isGone[getReadLocation(rows,cols,locRow,locCol)]=false;
            return true;
        }
        //左
        if(hasPathCore(matrix,rows,cols,str,locRow,locCol-1,strIndex+1,isGone)){
            isGone[getReadLocation(rows,cols,locRow,locCol)]=false;
            return true;
        }
        //右
        if(hasPathCore(matrix,rows,cols,str,locRow,locCol+1,strIndex+1,isGone)){
            isGone[getReadLocation(rows,cols,locRow,locCol)]=false;
            return true;
        }
        isGone[getReadLocation(rows,cols,locRow,locCol)]=false;
        return false;
    }
    //不检查合法性
    private int getReadLocation(int rows, int cols,int locRow, int locCol){
        return locRow*cols+locCol;
    }
}

二叉搜索树的第k个结点

题目描述

给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。

思路

中序遍历的结果就是二叉搜索树的按顺序从小到到的序列

代码

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
     int num=0;
    TreeNode KthNode(TreeNode pRoot, int k) {
        if(pRoot==null)return null;
        //遍历左子树
        TreeNode left = KthNode(pRoot.left,k);
        if(left!=null)return left;
        //遍历根节点
        num++;
        if(num==k)return pRoot;
        //遍历右子树
        TreeNode right = KthNode(pRoot.right,k);
        if(right!=null)return right;

        return null;
    }

}

序列化二叉树

题目描述

请实现两个函数,分别用来序列化和反序列化二叉树

思路

前序遍历加空指针符号

代码

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
  String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeCore(root,sb);
        sb.deleteCharAt(sb.length()-1);
        return sb.toString();
    }
    private void serializeCore(TreeNode root,StringBuilder sb){
        if(root == null){
            sb.append("#,");
            return;
        }
        sb.append(root.val + ",");
        serializeCore(root.left,sb);
        serializeCore(root.right,sb);
    }
    TreeNode Deserialize(String str) {
        if(str==null||str.length()==0)return null;
        String[] strs = str.split(",");
        return deserializeCore(strs);
    }
    int index = -1;
    TreeNode deserializeCore(String[] strs){
        index++;
        if(!strs[index].equals("#")){
            TreeNode node = new TreeNode(0);
            node.val = Integer.parseInt(strs[index]);
            node.left=deserializeCore(strs);
            node.right=deserializeCore(strs);
            return node;
        }
        //# 代表空指针
        return null;
    }
}