最近發(fā)現(xiàn)大神們很多都在混LeatCode
這個(gè)網(wǎng)站集合了很多的面試上的算法題羞酗，支持c++，java紊服，和python檀轨，
很多問題想起來很簡(jiǎn)單，但是做起來很麻煩..而且會(huì)有很多的問題沒想到
提交之后被他的測(cè)試用例一測(cè)試就原型閉路了欺嗤，我盡量以一天一道道兩道
題的速度來做参萄，寫這個(gè)系列的目的一是總結(jié)，一是督促煎饼。
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.
第一題讹挎，句子反轉(zhuǎn)，不算難
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函數(shù)吆玖，去掉開頭和結(jié)尾的空格
while(s.startsWith(" ")){
s = s.substring(1, s.length());
}
while(s.endsWith(" ")){
s = s.substring(0, s.length()-1);
}
if (!s.contains(" "))
return s;
//正則表達(dá)式筒溃，消掉多個(gè)空格
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 ");
// }
}
第二題 給定一個(gè)逆波蘭表達(dá)式，求該表達(dá)式的值
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
還算簡(jiǎn)單沾乘，仔細(xì)一看怜奖，就是棧的應(yīng)用了...直接上代碼
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.
給一個(gè)平面上的點(diǎn)，找到所有這些點(diǎn)落在哪條線上的點(diǎn)最多意鲸，并返回這個(gè)最大值
這個(gè)題....讓我發(fā)現(xiàn)了太多邏輯上的漏洞烦周，比如說數(shù)學(xué)上點(diǎn)，多個(gè)點(diǎn)重合算一個(gè)點(diǎn)
但是怎顾，如果用這樣的方式給點(diǎn)的話读慎，重合的點(diǎn)是要算兩個(gè)的
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 可能有重復(fù)的點(diǎn)
* 第一步槐雾，如果給的是空的數(shù)組夭委，返回0
* 如果給的是只有一個(gè)點(diǎn)的數(shù)組，返回1
* 至少給了兩個(gè)點(diǎn)的情況下
* 判斷是否有不同的點(diǎn)募强，如果沒有返回points.length
* 用兩個(gè)不同的點(diǎn)算出直線方程,之后再由函數(shù)getPointNumber算出points中
* 有多少個(gè)點(diǎn)在該直線上株灸，并計(jì)算所有這樣的直線，找到最大值
*/
按照這個(gè)思路擎值，代碼不會(huì)特別難...但我寫了好長時(shí)間才寫對(duì)慌烧！
問題就是出在前面提到的想當(dāng)然和各種邏輯錯(cuò)誤。鸠儿。屹蚊。
下面的法一厕氨，發(fā)現(xiàn)要判斷重復(fù)點(diǎn)的情況太麻煩了，于是砍掉重練...
下面貼代碼
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個(gè)二維平面上的點(diǎn)汹粤，求出這n個(gè)點(diǎn)當(dāng)中最多有多少個(gè)點(diǎn)在同一直線上命斧。
*/
public class Solution {
/*
* 法一 ，這樣的想法就是錯(cuò)誤的
*/
// 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 可能有重復(fù)的點(diǎn)
* 第一步国葬，如果給的是空的數(shù)組，返回0
* 如果給的是只有一個(gè)點(diǎn)的數(shù)組芹壕，返回1
* 至少給了兩個(gè)點(diǎn)
* 判斷是否有不同的點(diǎn)汇四，如果沒有返回points.length
* 用兩個(gè)不同的點(diǎn)算出直線方程,之后再由函數(shù)getPointNumber算出points中有多少個(gè)點(diǎn)在該
* 直線上，并計(jì)算所有這樣的直線哪雕，找到最大值
*/
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);
}
}
