Reverse Words in a String 

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class Solution {
    public String reverseWords(String s) {
        String[] helper = s.split(" ");
        StringBuffer sb = new StringBuffer();
        for(int i = helper.length - 1; i >= 0; i--){
            sb.append(helper[i]);
            if(i > 0){
                sb.append(" ");    
            }
        }
        String reverse = sb.toString();
        return reverse;
    }
}

Submission Result: Wrong Answer

Input: " 1" Output: "1 " Expected: "1"

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class Solution {
    public String reverseWords(String s) {
        String[] helper = s.split(" ");
        StringBuffer sb = new StringBuffer();
        for(int i = helper.length - 1; i >= 0; i--){
            sb.append(helper[i]);
            // if(i > 0){
                sb.append(" ");    
            // }         
        }
        String reverse = sb.toString();
        return reverse;
    }
}

Submission Result: Wrong Answer

Input: "" Output: " " Expected: ""

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public class Solution {
    public String reverseWords(String s) {
        if(s.equals("") || s.length() == 0){
            return null;
        }
        if(s.length() == 1){
            return s;
        }
        boolean head;
        boolean tail;
        if(s.charAt(0) == " "){
            head = true;
        }
        if(s.charAt(s.length() - 1) == " "){
            tail = true;
        }
        String[] helper = s.split(" ");
        StringBuffer sb = new StringBuffer();
        if(tail){
            sb.append(" ");
        }
        for(int i = helper.length - 1; i >= 0; i--){
            sb.append(helper[i]);
            if(i > 0){
                sb.append(" ");    
            }
            
        }
        if(head){
            sb.append(" ");
        }
        String reverse = sb.toString();
        return reverse;
    }
}

Submission Result: Compile Error

Line 11: error: incomparable types: char and String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public class Solution {
    public String reverseWords(String s) {
        if(s.equals("") || s.length() == 0){
            return null;
        }
        if(s.length() == 1){
            return s;
        }
        boolean head;
        boolean tail;
        if(s.charAt(0).isWhiteSpace()){
            head = true;
        }
        if(s.charAt(s.length() - 1).isWhiteSpace()){
            tail = true;
        }
        String[] helper = s.split(" ");
        StringBuffer sb = new StringBuffer();
        if(tail){
            sb.append(" ");
        }
        for(int i = helper.length - 1; i >= 0; i--){
            sb.append(helper[i]);
            if(i > 0){
                sb.append(" ");    
            }    
        }
        if(head){
            sb.append(" ");
        }
        String reverse = sb.toString();
        return reverse;
    }
}

Submission Result: Compile Error

Line 11: error: char cannot be dereferenced

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public class Solution {
    public String reverseWords(String s) {
        if(s.equals("") || s.length() == 0){
            return null;
        }
        if(s.length() == 1){
            return s;
        }
        boolean head;
        boolean tail;
        if(s.charAt(0) == ' '){
            head = true;
        }
        if(s.charAt(s.length() - 1) == ' '){
            tail = true;
        }
        String[] helper = s.split(" ");
        StringBuffer sb = new StringBuffer();
        if(tail){
            sb.append(" ");
        }
        for(int i = helper.length - 1; i >= 0; i--){
            sb.append(helper[i]);
            if(i > 0){
                sb.append(" ");    
            }       
        }
        if(head){
            sb.append(" ");
        }
        String reverse = sb.toString();
        return reverse;
    }
}

Submission Result: Compile Error

Line 19: error: variable tail might not have been initialized

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public class Solution {
    public String reverseWords(String s) {
        if(s.equals("") || s.length() == 0){
            return null;
        }
        if(s.length() == 1){
            return s;
        }
        boolean head = false;
        boolean tail = false;
        if(s.charAt(0) == ' '){
            head = true;
        }
        if(s.charAt(s.length() - 1) == ' '){
            tail = true;
        }
        String[] helper = s.split(" ");
        StringBuffer sb = new StringBuffer();
        if(tail){
            sb.append(" ");
        }
        for(int i = helper.length - 1; i >= 0; i--){
            sb.append(helper[i]);
            if(i > 0){
                sb.append(" ");    
            }    
        }
        if(head){
            sb.append(" ");
        }
        String reverse = sb.toString();
        return reverse;
    }
}

Submission Result: Wrong Answer

Input: "" Output: null

Expected: ""

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class Solution {
    public String reverseWords(String s) {
        if(s.equals("") || s.length() == 0 || s.length() == 1){
            return s;
        }
        boolean head = false;
        boolean tail = false;
        if(s.charAt(0) == ' '){
            head = true;
        }
        if(s.charAt(s.length() - 1) == ' '){
            tail = true;
        }
        String[] helper = s.split(" ");
        StringBuffer sb = new StringBuffer();
        if(tail){
            sb.append(" ");
        }
        for(int i = helper.length - 1; i >= 0; i--){
            sb.append(helper[i]);
            if(i > 0){
                sb.append(" ");    
            }    
        }
        if(head){
            sb.append(" ");
        }
        String reverse = sb.toString();
        return reverse;
    }}

Submission Result: Wrong Answer

Input: " " Output: " " Expected: ""

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public class Solution {
    public String reverseWords(String s) {
        String[] helper = s.split(" ");
        if(helper.size() == 0){
            return "";
        }
        // if(s == " "){
        //     return "";
        // }
        if(s.equals("") || s.length() == 0 || s.length() == 1){
            return s;
        }
        boolean head = false;
        boolean tail = false;
        if(s.charAt(0) == ' '){
            head = true;
        }
        if(s.charAt(s.length() - 1) == ' '){
            tail = true;
        }
        StringBuffer sb = new StringBuffer();
        if(tail){
            sb.append(" ");
        }
        for(int i = helper.length - 1; i >= 0; i--){
            sb.append(helper[i]);
            if(i > 0){
                sb.append(" ");    
            }   
        }
        if(head){
            sb.append(" ");
        }
        String reverse = sb.toString();
        return reverse;
    }
}

Submission Result: Compile Error

Line 4: error: cannot find symbol: method size()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Solution {
    public String reverseWords(String s) {
        // if(s == " "){
        //     return "";
        // }
        // 可能有多个空格
        String[] helper = s.split(" ");
        if(helper.length == 0){
            return "";
        }
        if(s.equals("") || s.length() == 0 || s.length() == 1){
            return s;
        }
        // boolean head = false;
        // boolean tail = false;
        // if(s.charAt(0) == ' '){
        //     head = true;
        // }
        // if(s.charAt(s.length() - 1) == ' '){
        //     tail = true;
        // }
        StringBuffer sb = new StringBuffer();
        if(helper.length == 1){
            sb.append(helper[0]);
            return sb.toString();
        }
        // if(tail){
        //     sb.append(" ");
        // }
        for(int i = helper.length - 1; i >= 0; i--){
            sb.append(helper[i]);
            if(i > 0){
                sb.append(" ");    
            }   
        }
        // if(head){
        //     sb.append(" ");
        // }
        String reverse = sb.toString();
        return reverse;
    }
}

Submission Result: Wrong Answer

Input: " 1" Output: "1 "

Expected: "1"

第二天

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Solution {
    public String reverseWords(String s) {
        
        int l = s.length();
        if(l == 0){
            return s;
        }
        int i = 0;
        while(i < l){
            if(s.charAt(i).isWhiteSpace()){
                i++;
            }else{
                break;
            }
        }
        int tail = l;
        while(tail >= 0){
            if(s.charAt(l).isWhiteSpace()){
                tail--;
            }else{
                break;
            }
        }
        String ss = new String();
        ss = s.subString(i, tail + 1);
        int ll = ss.length();
        if(ll == 0 || ll == 1){
            return s;
        }
        
        String[] helper = ss.split(' ');
        StringBuffer sb = new StringBuffer();
        for(int j = helper.length - 1; j >= 0; j-- ){
            sb.append(helper[j]);
            if(j > 0){
                sb.append(" ");
            }
        }
        
        return sb.toString();
    }
}

Submission Result: Compile Error

Line 10: error: char cannot be dereferenced

The type char is a primitive -- not an object -- so it cannot be dereferenced

Dereferencing is the process of accessing the value referred to by a reference. Since a char is already a value (not a reference), it can not be dereferenced.

use Character class:

if(Character.isLetter(c)) {}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Solution {
    public String reverseWords(String s) {
        
        int l = s.length();
        if(l == 0){
            return s;
        }
        int i = 0;
        while(i < l){
            if(Character.isWhiteSpace(s.charAt(i))){
                i++;
            }else{
                break;
            }
        }
        int tail = l;
        while(tail >= 0){
            if(Character.isWhiteSpace(s.charAt(i))){
                tail--;
            }else{
                break;
            }
        }
        String ss = new String();
        ss = s.subString(i, tail + 1);
        int ll = ss.length();
        if(ll == 0 || ll == 1){
            return s;
        }
        
        String[] helper = ss.split(' ');
        StringBuffer sb = new StringBuffer();
        for(int j = helper.length - 1; j >= 0; j-- ){
            sb.append(helper[j]);
            if(j > 0){
                sb.append(" ");
            }
        }
        
        return sb.toString();
    }
}

Submission Result: Compile Error

Line 10: error: cannot find symbol: method isWhiteSpace(char)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Solution {
    public String reverseWords(String s) {
        
        int l = s.length();
        if(l == 0){
            return s;
        }
        int i = 0;
        while(i < l){
            if(Character.isWhitespace(s.charAt(i))){
                i++;
            }else{
                break;
            }
        }
        int tail = l;
        while(tail >= 0){
            if(Character.isWhitespace(s.charAt(i))){
                tail--;
            }else{
                break;
            }
        }
        String ss = new String();
        ss = s.subString(i, tail + 1);
        int ll = ss.length();
        if(ll == 0 || ll == 1){
            return s;
        }
        
        String[] helper = ss.split(' ');
        StringBuffer sb = new StringBuffer();
        for(int j = helper.length - 1; j >= 0; j-- ){
            sb.append(helper[j]);
            if(j > 0){
                sb.append(" ");
            }
        }
        
        return sb.toString();
    }
}

Submission Result: Compile Error

Line 25: error: cannot find symbol: method subString(int,int)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Solution {
    public String reverseWords(String s) {
        
        int l = s.length();
        if(l == 0){
            return s;
        }
        int i = 0;
        while(i < l){
            if(Character.isWhitespace(s.charAt(i))){
                i++;
            }else{
                break;
            }
        }
        int tail = l;
        while(tail >= 0){
            if(Character.isWhitespace(s.charAt(i))){
                tail--;
            }else{
                break;
            }
        }
        String ss = new String();
        ss = s.substring(i, tail + 1);
        int ll = ss.length();
        if(ll == 0 || ll == 1){
            return s;
        }
        
        String[] helper = ss.split(' ');
        StringBuffer sb = new StringBuffer();
        for(int j = helper.length - 1; j >= 0; j-- ){
            sb.append(helper[j]);
            if(j > 0){
                sb.append(" ");
            }
        }
        
        return sb.toString();
    }
}

Submission Result: Compile Error

Line 31: error: no suitable method found for split(char)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Solution {
    public String reverseWords(String s) {
        
        int l = s.length();
        if(l == 0){
            return s;
        }
        int i = 0;
        while(i < l){
            if(Character.isWhitespace(s.charAt(i))){
                i++;
            }else{
                break;
            }
        }
        int tail = l;
        while(tail >= 0){
            if(Character.isWhitespace(s.charAt(i))){
                tail--;
            }else{
                break;
            }
        }
        String ss = new String();
        ss = s.substring(i, tail + 1);
        int ll = ss.length();
        if(ll == 0 || ll == 1){
            return s;
        }
        
        String[] helper = ss.split(" ");
        StringBuffer sb = new StringBuffer();
        for(int j = helper.length - 1; j >= 0; j-- ){
            sb.append(helper[j]);
            if(j > 0){
                sb.append(" ");
            }
        }
        
        return sb.toString();
    }
}

Submission Result: Runtime Error

Runtime Error Message: Line 18: java.lang.StringIndexOutOfBoundsException: String index out of range: 1

Last executed input: " "

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Solution {
    public String reverseWords(String s) {
        
        int l = s.length();
        if(l == 0){
            return s;
        }
        int i = 0;
        while(i < l){
            if(Character.isWhitespace(s.charAt(i))){
                i++;
            }else{
                break;
            }
        }
        int tail = l - 1;
        while(tail >= 0){
            if(Character.isWhitespace(s.charAt(i))){
                tail--;
            }else{
                break;
            }
        }
        String ss = new String();
        ss = s.substring(i, tail + 1);
        int ll = ss.length();
        if(ll == 0 || ll == 1){
            return s;
        }
        
        String[] helper = ss.split(" ");
        StringBuffer sb = new StringBuffer();
        for(int j = helper.length - 1; j >= 0; j-- ){
            sb.append(helper[j]);
            if(j > 0){
                sb.append(" ");
            }
        }
        
        return sb.toString();
    }
}

Submission Result: Runtime Error

Runtime Error Message: Line 18: java.lang.StringIndexOutOfBoundsException: String index out of range: 1

Last executed input: " "

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Solution {
    public String reverseWords(String s) {
        
        int l = s.length();
        if(l == 0){
            return s;
        }
        int i = 0;
        while(i < l){
            if(Character.isWhitespace(s.charAt(i))){
                i++;
            }else{
                break;
            }
        }
        int tail = l - 1;
        while(tail >= 0){
            if(Character.isWhitespace(s.charAt(tail))){
                tail--;
            }else{
                break;
            }
        }
        String ss = new String();
        ss = s.substring(i, tail + 1);
        int ll = ss.length();
        if(ll == 0 || ll == 1){
            return s;
        }
        
        String[] helper = ss.split(" ");
        StringBuffer sb = new StringBuffer();
        for(int j = helper.length - 1; j >= 0; j-- ){
            sb.append(helper[j]);
            if(j > 0){
                sb.append(" ");
            }
        }
        
        return sb.toString();
    }
}

Submission Result: Runtime Error

Runtime Error Message: Line 25: java.lang.StringIndexOutOfBoundsException: String index out of range: -1

Last executed input: " "

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public class Solution {
    public String reverseWords(String s) {
        
        int l = s.length();
        if(l == 0){
            return s;
        }
        int i = 0;
        while(i < l){
            if(Character.isWhitespace(s.charAt(i))){
                i++;
            }else{
                break;
            }
        }
        int tail = l - 1;
        while(tail >= 0){
            if(Character.isWhitespace(s.charAt(tail))){
                tail--;
            }else{
                break;
            }
        }
        String ss = new String();
        if(tail > i){
            ss = s.substring(i, tail + 1);
        }
        int ll = ss.length();
        if(ll == 0 || ll == 1){
            return s;
        }
        
        String[] helper = ss.split(" ");
        StringBuffer sb = new StringBuffer();
        for(int j = helper.length - 1; j >= 0; j-- ){
            sb.append(helper[j]);
            if(j > 0){
                sb.append(" ");
            }
        }
        
        return sb.toString();
    }
}

Submission Result: Wrong Answer

Input: " " Output: " "

Expected: ""

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

public class Solution {
    public String reverseWords(String s) {
        
        int l = s.length();
        if(l == 0){
            return s;
        }
        int i = 0;
        while(i < l){
            if(Character.isWhitespace(s.charAt(i))){
                i++;
            }else{
                break;
            }
        }
        int tail = l - 1;
        while(tail >= 0){
            if(Character.isWhitespace(s.charAt(tail))){
                tail--;
            }else{
                break;
            }
        }
        String ss = new String();
        if(tail >= i){
            ss = s.substring(i, tail + 1);
        }else{
            return "";
        }
        int ll = ss.length();
        if(ll == 0 || ll == 1){
            return s;
        }
        
        String[] helper = ss.split(" ");
        StringBuffer sb = new StringBuffer();
        for(int j = helper.length - 1; j >= 0; j-- ){
            sb.append(helper[j]);
            if(j > 0){
                sb.append(" ");
            }
        }
        
        return sb.toString();
    }
}

Submission Result: Wrong Answer

Input: " 1" Output: " 1"

Expected: "1"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Solution {
    public String reverseWords(String s) {
        if(s.length() == 0 || s == null){
            return s;
        }
        
        if(s.length() == 1 && s != " "){
            return s;
        }
        
        s = s.trim();
        
        String[] helper = s.split("\\s+");
        
        StringBuffer sb = new StringBuffer();
        
        for(int i = helper.length - 1; i >= 0; i-- ){
            sb.append(helper[i]);
            if(i != 0){
                sb.append(" ");
            }
        }
        
        return sb.toString();
        
    }
}

Submission Result: Wrong Answer

Input: " " Output: " "

Expected: ""

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Solution {
    public String reverseWords(String s) {
        if(s.length() == 0 || s == null){
            return s;
        }
        
        if(s.length() == 1 && !s.equals(" ")){
            return s;
        }
//忘记用 trim()来去首尾的空格        
        s = s.trim();

        //这里注意所有空格的表达形式, 包括whitespace, tab, enter等 详见http://stackoverflow.com/a/225360/2345313
        String[] helper = s.split("\\s+");
        
        StringBuffer sb = new StringBuffer();
        
        for(int i = helper.length - 1; i >= 0; i-- ){
            sb.append(helper[i]);
            if(i != 0){
                sb.append(" ");
            }
        }
        
        return sb.toString();
        
    }
}

Submission Result: Accepted

2Sum_continue

凭着记忆写一下hashmap的写法:

  • 其实已经是修改过几个小毛病的版本, 比如new HashMap;

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map map = new HashMap<Integer, Integer>();
        int i = 0;
        int j = numbers.length - 1;
        while(i <= j){
            if(!map.containsKey(numbers[j])){
                map.put(target - numbers[i], numbers[i]);
                i++;
                j--;
            }else{
                result[0] = i + 1;
                result[1] = j + 1;
                return result;
            }
        }
        
        return result;
    }
}

  • Result: 

    1
2
3
4
5

    Submission Result: Wrong Answer

Input:	[3,2,4], 6
Output:	0, 0
Expected:	2, 3

  • 调整一下i和j的变更条件:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map map = new HashMap<Integer, Integer>();
        int i = 0;
        int j = numbers.length - 1;
        while(i <= j){
            while(j > 0){
                if(!map.containsKey(numbers[j])){
                    map.put(target - numbers[i], numbers[i]);
                    i++;
                }else{
                    result[0] = i + 1;
                    result[1] = j + 1;
                    return result;
                }
                j--;
            }
        }
        
        return result;
    }
}

  • Result: 

    1
2
3
4
5

    Submission Result: Wrong Answer

Input:	[3,2,4], 6
Output:	0, 0
Expected:	2, 3

  • 分析: 理论上之前本方法的时间复杂度是O(n^2); 如果按照上面写法两个while循环钱淘的话, 依然还是O(n^2), 这样就没意义了, 应该扫一遍数据进hashtable就可以判断出是否有结果了, 上面的问题就是怎样在得到两个相加和为target的数值之后取得他们的index,

何不在扫入hashmap的时候把index作为value存入呢? 这有点茅塞顿开的意思, 但是悲剧的是依然写错了..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map map = new HashMap<Integer, Integer>();
        int i = 0;
        int j = 0;
        while(i < numbers.length){
            if(!map.containsKey(numbers[i])){
                map.put(target - numbers[i], i);
                i++;
            }else{
                j = map.get(target - numbers[i]);
                if(i < map.get(target - numbers[i])){
                    result[0] = i + 1;
                    result[1] = map.get(target - numbers[i] + 1);
                    return result;
                }else{ 
                    result[0] = j + 1;
                    result[1] = i + 1;
                    return result;
                }
            }
        }
        return result;
    }
}

  • Result: 

    1
2
3

    Submission Result: Compile Error

Line 12: error: incompatible types

  • 借助于eclipse debug, 终于找到问题所在, 应该去get(numbers[i]), 另外不加(Integer) leetcode无法贬编译 + 这个运算符, 其实我已经定义了get出来的是Integer, 按理说不用转换, 不知道为什么, 可能这样更严谨?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map map = new HashMap<Integer, Integer>();
        int i = 0;
        while(i < numbers.length){
            if(!map.containsKey(numbers[i])){
                map.put(target - numbers[i], i);
                i++;
            }else{
                result[0] = (Integer)map.get( numbers[i]) + 1;
                result[1] = i + 1;
                return result;
            }

        }
        return result;
    }
}

总结: 自己想出来的和之前参考的solution虽然大致思路一样, 但是具体的实现上还是不同的, 而且貌似自己写的更简洁一些. 最后实在找不到问题所在了去看了下之前的solution, 发现那边也是直接map.get( numbers[i]), 并没有加强制类型转换. 不过加上肯定不会错就是了.

LeetCode:TwoSum (1)

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

OJ:

  • 首先用最笨的方法来解，不过好像Java Array的相关method我都忘得差不多了....记录下来再更正吧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2]; 
        int l = numbers.size();
        int i, j;
        for (i = 0; i < l; i++){
            for(int j = i + 1; j < l; j++){
                if(numbers[i] + numbers[j] = target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        
    }
}
  • Result: Line4: error: cannot find symbol: method size()

  • 忘记有没有直接看Array长度的函数了，先不去查文档，转化成熟悉的String来做

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        String source  = numbers.toString();
        int[] result = new int[2]; 
        //int l = numbers.size();
        l = source.length();
        int i, j;
        for (i = 0; i < l; i++){
            for(int j = i + 1; j < l; j++){
                if(numbers[i] + numbers[j] = target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        
    }
}

  • Result: Line 6: error: cannot find symbol: variable l 这个错误就是粗心大意了, 后面还有一个错误: Line 9: error: variable j is already defined in method twoSum(int[],int) 我还是再看一遍code再提交吧

  • 审查了一遍,又发现个错误, i的边界判定不应该是length, 而应该是length - 1

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        String source  = numbers.toString();
        int[] result = new int[2]; 
        int l = source.length();
        int i, j;
        for (i = 0; i < l - 1; i++){
            for(j = i + 1; j < l; j++){
                if(numbers[i] + numbers[j] = target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        
    }
}

  • Result: Line 9: error: unexpected type

  • 太不严谨了 - -, 平常用eclipse确实有依赖性, 函数名自己都不去记了, 这种 "==" 自己居然也没注意到

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        String source  = numbers.toString();
        int[] result = new int[2]; 
        int l = source.length();
        int i, j;
        for (i = 0; i < l - 1; i++){
            for(j = i + 1; j < l; j++){
                if(numbers[i] + numbers[j] == target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        
    }
}

  • Result: Line 17: error: missing return statement

  • 简直是错误百出

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        String source  = numbers.toString();
        int[] result = new int[2]; 
        int l = source.length();
        int i, j;
        for (i = 0; i < l - 1; i++){
            for(j = i + 1; j < l; j++){
                if(numbers[i] + numbers[j] == target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        
        return result;
        
    }
}

  • Result: Runtime Error Message: Line 9: java.lang.ArrayIndexOutOfBoundsException: 3 Last executed input: [3,2,4], 6

  • 再改!

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        String source  = numbers.toString();
        int[] result = new int[2]; 
        int l = source.length();
        int i, j;
        for (i = 0; i <= l - 2; i++){
            for(j = i + 1; j <= l - 1; j++){
                if(numbers[i] + numbers[j] == target){
                    result[0] = i + 1;
                    result[1] = j + 1;
                    return result;
                }
            }
        }
        
        return result;
        
    }
}

  • Result: Runtime Error Message: Line 9: java.lang.ArrayIndexOutOfBoundsException: 3 Last executed input: [3,2,4], 6

  • IMPORTANT: 之所以会这样, 是因为Arrays.toString(), 并不是返回的Arrays里面元素的值, 比如 int[] numbers = {3, 2, 4}, 实测 System.out.println(numbers.toString()) 结果为 [I@53281264 所以上面code中的length实际为11, 怪不得会出现ArrayIndexOutOfBoundsException.

正确获得Arrays长度的方法: Arrays.length

之前刷提的时候不知所以然, 这次我们进阶了, 其实刚才写代码的时候也想到直接用 Arrays.length, 但是这个 .length不是一个method呀, 这在一切皆是Object的Java中显得有些不合群, 所以没用, 这次问题的出现是必然的, 因为我没有系统的学习过数据结构也好, 算法也好, Java也好, 以点带面, 查缺补漏吧.

还是参考StackOverflow的解释: 为什么ArrayList可以用ArrayList.size()来获取ArrayList的长度, 而 Array.length -- 并不是一个method, 却可以得到Array的长度呢?

Arrays are special objects in java, they have a simple attribute named length which is final. There is no "class definition" of an array (you can't find it in any .class file), they're a part of the language itself.

10.7. Array Members

The members of an array type are all of the following: The public final field length, which contains the number of components of the array. length may be positive or zero. The public method clone, which overrides the method of the same name in class Object and throws no checked exceptions. The return type of the clone method of an array type T[] is T[]. A clone of a multidimensional array is shallow, which is to say that it creates only a single new array. Subarrays are shared. All the members inherited from class Object; the only method of Object that is not inherited is its clone method. Note also that ArrayList.size() provides the number of object actually stored in the array whereas myArray.length ([]) provides the "capacity". That is, if for myArray = new int[10];, it returns 10. It is not the number of objects you've put in the array.

  • 改正Arrays.length :

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        String source  = numbers.toString();
        int[] result = new int[2]; 
        // int l = source.length();
        int l = numbers.length;
        int i, j;
        for (i = 0; i <= l - 2; i++){
            for(j = i + 1; j <= l - 1; j++){
                if(numbers[i] + numbers[j] == target){
                    result[0] = i + 1;
                    result[1] = j + 1;
                    return result;
                }
            }
        }
        
        return result;
        
    }
}

  • 改正这一错误之后的代码可以正确运行了, 但是 leetcode的OJ表示此程序太慢了, Time Limit Exceeded.

这并不出乎意料, 因为这个是最笨的方法, 时间复杂度应该是O(n^2)