算法学习笔记（LeetCode OJ）

分类: IT文章 • 2025-01-30 17:40:07

==================================

LeetCode的一些算法题，都是自己做的，欢迎提出改进~~

LeetCode：http://oj.leetcode.com

==================================

<Reverse Words in a String>-20140328

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.

 1 public class Solution {
 2     public String reverseWords(String s) {
 3         s = s.trim();
 4         String[] str = s.split("\s{1,}");
 5         String tmp;
 6         int len = str.length;
 7         int halfLen = len/2;
 8         for(int i=0;i<halfLen;i++){
 9             tmp = str[i];
10             str[i] = str[len-i-1];
11             str[len-i-1] = tmp;
12         }
13         StringBuffer sb = new StringBuffer();
14         String result;
15         if(len==1){
16             result = str[0];
17         }else{
18             for(String string:str){
19                 sb.append(string+" ");
20             }
21             result = sb.toString().trim();
22         }
23         return result;
24     }
25 }

Java Code - 404ms - AC1/7

C++: http://blog.****.net/feliciafay/article/details/20884583

一个空格的情况
多个空格在一起的情况
空串的情况
首尾空格的情况
一些测试数据：
“            ”
“a       ”
"       a"
"      a     "
"     a      b    "
"     a b     "
"     a  b"
"a  b       "

Hint

<Evaluate Reverse Polish Notation>-20140329

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

 1 public class Solution {
 2     public int evalRPN(String[] tokens) {
 3         Stack<Integer> stack = new Stack();
 4         for(String str:tokens){
 5             if("+-*/".contains(str)){
 6                 int b = stack.pop();
 7                 int a = stack.pop();
 8                 switch(str){
 9                     case "+":
10                         stack.add(a+b);
11                         break;
12                     case "-":
13                         stack.add(a-b);
14                         break;
15                     case "*":
16                         stack.add(a*b);
17                         break;
18                     case "/":
19                         stack.add(a/b);
20                         break;
21                 }
22             }else{
23                 stack.add(Integer.parseInt(str));
24             }
25         }
26         return stack.pop();
27     }
28 }

Java Code - 484ms - AC1/1

<Max Points on a Line>-20140330

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

开始的实现：

 1 /**
 2  * Definition for a point.
 3  * class Point {
 4  *     int x;
 5  *     int y;
 6  *     Point() { x = 0; y = 0; }
 7  *     Point(int a, int b) { x = a; y = b; }
 8  * }
 9  */
10 public class Solution {
11     private boolean judgment(Point a, Point b, Point third){
12         return (a.y-third.y)*(b.x-third.x)==(b.y-third.y)*(a.x-third.x);
13     }
14     
15     public int maxPoints(Point[] points) {
16         int len = points.length;
17         if(len<3){
18             return len;
19         }
20         int[] mark = new int[len];
21         for(int m=0;m<len;m++){
22             mark[m] = 0;
23         }
24         int count = 2;
25         for(int i=0;i<len;i++){
26             int tmpCount = 2;
27             for(int j=i+1;j<len;j++){
28                 if(mark[j]==1){
29                     continue;
30                 }
31                 for(int k=j+1;k<len;k++){
32                     if(mark[k]==1){
33                         continue;
34                     }
35                     boolean judge = judgment(points[i],points[j],points[k]);
36                     if(judge){
37                         mark[k] = 1;
38                         tmpCount++;
39                     }
40                 }
41             }
42             if(tmpCount>count){
43                 count = tmpCount;
44             }
45         }
46         return count;
47     }
48 }

Java Code - Wrong

后来发现被坑了，它是有相同点出现这种情况的！！！开始我还傻傻地想为什么<5,6,18>三点共线而<0,5,6>却不共线，后来自己费了好大力气才明白过来。

然后，还有其他的问题，对此题无力了，还是先放放过几天头脑清醒再来弄吧T-T。

看看人家的思想先吧，不过我还是想先自己搞掂再看。

C++: http://blog.****.net/feliciafay/article/details/20704629

<Single Number>-20140414

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

1 public class Solution {
2     public int singleNumber(int[] A) {
3         int num = 0;
4         for(int i : A){
5             num ^= i;
6         }
7         return num;
8     }
9 }

Java Code

算法学习笔记（LeetCode OJ）

相关推荐