最近发现大神们很多都在混LeatCode
这个网站集合了很多的面试上的算法题，支持c++，java，和python，
很多问题想起来很简单，但是做起来很麻烦..而且会有很多的问题没想到
提交之后被他的测试用例一测试就原型闭路了，我尽量以一天一道道两道
题的速度来做，写这个系列的目的一是总结，一是督促。
Reverse Words in a String
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
click to show clarification.
第一题，句子反转，不算难
package everse.Words;
import java.util.ArrayList;
public class Solution {
public Solution(String s){
System.out.print(reverseWords(s));
}
public String reverseWords(String s) {
if( s.equals(""))
return s;
//为了使用用split函数，去掉开头和结尾的空格
while(s.startsWith(" ")){
s = s.substring(1, s.length());
}
while(s.endsWith(" ")){
s = s.substring(0, s.length()-1);
}
if (!s.contains(" "))
return s;
//正则表达式，消掉多个空格
String[] st = s.split("\\s{1,}");
ArrayList<String> list = new ArrayList<String>();
int i = st.length - 1;
for(; i>=0 ; i--){
list.add(st[i]);
}
String result = list.toString();
result = result.substring(1, result.length()-1);
result=result.replaceAll(", "," ");
return result;
}
// public static void main(String[] args){
// Solution test = new Solution(" a b ");
// }
}
第二题 给定一个逆波兰表达式，求该表达式的值
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
还算简单，仔细一看，就是栈的应用了...直接上代码
package Evaluate.Reverse.Polish.Notation;
import java.util.Stack;
public class Solution {
public int evalRPN(String[] tokens) {
Integer xx ,yy,r;
Stack<String> store = new Stack<String>();
for(int i = 0; i < tokens.length; i++ ){
if(Character.isDigit(tokens[i].charAt(tokens[i].length() - 1)))
store.push(tokens[i]);
else{
switch (tokens[i]) {
case "+":
xx = Integer.parseInt(store.pop());
yy = Integer.parseInt(store.pop());
r = xx + yy;
store.push(r.toString());
break;
case "-":
xx = Integer.parseInt(store.pop());
yy = Integer.parseInt(store.pop());
r = yy-xx;
store.push(r.toString());
break;
case "*":
xx = Integer.parseInt(store.pop());
yy = Integer.parseInt(store.pop());
r = xx * yy;
store.push(r.toString());
break;
case "/":
xx = Integer.parseInt(store.pop());
yy = Integer.parseInt(store.pop());
r = yy/xx;
store.push(r.toString());
break;
default:
break;
}
}
}
return Integer.parseInt(store.pop());
}
// public Solution(String[] s){
// System.out.print(evalRPN(s));
// }
//
//
// public static void main(String[] args){
// String[] s = {"3","-4","+"};
// Solution test = new Solution(s);
// }
}
平面找线
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
给一个平面上的点，找到所有这些点落在哪条线上的点最多，并返回这个最大值
这个题....让我发现了太多逻辑上的漏洞，比如说数学上点，多个点重合算一个点
但是，如果用这样的方式给点的话，重合的点是要算两个的
class Point {
Integer x;
Integer y;
public Point() {
x = 0; y = 0;
}
public Point(int a, int b) {
x = a; y = b;
}
}
Point[] points
先说下我的思路
/*
* 思路，给的points 可能有重复的点
* 第一步，如果给的是空的数组，返回0
* 如果给的是只有一个点的数组，返回1
* 至少给了两个点的情况下
* 判断是否有不同的点，如果没有返回points.length
* 用两个不同的点算出直线方程,之后再由函数getPointNumber算出points中
* 有多少个点在该直线上，并计算所有这样的直线，找到最大值
*/
按照这个思路，代码不会特别难...但我写了好长时间才写对！
问题就是出在前面提到的想当然和各种逻辑错误。。。
下面的法一，发现要判断重复点的情况太麻烦了，于是砍掉重练...
下面贴代码
package Max.Points.Line;
class Point {
Integer x;
Integer y;
public Point() {
x = 0; y = 0;
}
public Point(int a, int b) {
x = a; y = b;
}
}
/*
* Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
* 给定n个二维平面上的点，求出这n个点当中最多有多少个点在同一直线上。
*/
public class Solution {
/*
* 法一 ，这样的想法就是错误的
*/
// public int maxPoints(Point[] points) {
// if(points.length == 0)
// return 0;
// if(points.length == 1)
// return 1;
//
// HashMap<Double , Integer> store = new HashMap<Double, Integer>();
// Integer count = 0;
// Integer repeatPoint = 0;
// Double temp;
// Iterator iter;
//
// for(int i = 0; i < points.length; i++){
// for(int j = 0; j < points.length; j++){
// if(i == j)
// continue;
// repeatPoint = 0;
// if (points[i].equals(points[j])){
// repeatPoint ++;
// continue;
// }
// temp = slope(points[i], points[j]);
// if(store.containsKey(temp))
// store.put(temp, store.get(temp) +1 );
// else
// store.put(temp, 2 );
// }
// iter = store.entrySet().iterator();
// count += repeatPoint;
// while(iter.hasNext()){
// Map.Entry entry = (Map.Entry) iter.next();
// if ((Integer) entry.getValue() >= count){
// count = (Integer) entry.getValue();
// }
// }
//
// store.clear();
//
// }
// return count;
// }
/*
* 思路，给的points 可能有重复的点
* 第一步，如果给的是空的数组，返回0
* 如果给的是只有一个点的数组，返回1
* 至少给了两个点
* 判断是否有不同的点，如果没有返回points.length
* 用两个不同的点算出直线方程,之后再由函数getPointNumber算出points中有多少个点在该
* 直线上，并计算所有这样的直线，找到最大值
*/
public int maxPoints(Point[] points) {
if(points.length == 0)
return 0;
if(points.length == 1)
return 1;
Integer repeatNum = 0;
for(Point p : points){
if(p.equals(points[0]))
repeatNum ++;
}
if(repeatNum == points.length)
return points.length;
Integer maxCount = 0;
Integer temp = 0;
for(int i = 0; i < points.length ; i ++){
for(int j = 0; j < points.length ; j ++){
if(points[i] == points[j])
continue;
temp = getPointNumber(points, points[i], points[j]);
if(temp > maxCount)
maxCount = temp;
}
}
return maxCount ;
}
public Integer getPointNumber(Point[] points, Point p1, Point p2){
Integer count = 0;
//直线若垂直
if(p1.x == p2.x){
for(Point p : points){
if(p.x == p1.x){
count ++ ;
}
}
return count;
}
//直线s水平
if(p1.y == p2.y){
for(Point p : points){
if(p.y == p1.y){
count ++ ;
}
}
return count;
}
//直线倾斜
for(Point p :points){
if((double)(p.y - p2.y)/(p1.y - p2.y) == (double)(p.x - p2.x)/(p1.x - p2.x) ){
count ++ ;
}
}
return count;
}
public Solution(Point[] s){
System.out.print(maxPoints(s));
}
public static void main(String[] atgs){
Point[] s1 = {new Point(1,1), new Point(1,1), new Point(2,2),new Point(2,2)};
Point[] s2 = {new Point(0,0), new Point(1,1), new Point(1,-1)};
Point[] s3 = {new Point(3,1), new Point(12,3), new Point(3,1),new Point(-6,-1)};
Point[] s4 = {new Point(-4,1), new Point(-7,7), new Point(-1,5),new Point(9,-25)};
Solution test = new Solution(s4);
}
}
网友评论