发表于 | 分类于

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

解法1：

按位相乘，注意把中间结果要存储在一个res[length1 + length2]的数组里。
然后从后往前扫描，比较容易错的是对应的res的数组的位置。要特别注意一下。
C++

1

Java

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 multiply(String num1, String num2) {
        if (num1.length() == 0 || num2.length() == 0) {
            return "";
        }
        int[] digits = new int[num1.length() + num2.length()];
        // Start from the last digit in num2, i.e. the bottom one
        for (int i = num2.length() - 1; i >= 0; i--) {
            int carry = 0;
            for (int j = num1.length() - 1; j >= 0; j--) {
                int temp = carry + (num1.charAt(j) - '0')*(num2.charAt(i) - '0') + digits[num2.length() - 1 - i + num1.length() - 1 -j];
                digits[num2.length() - 1 - i + num1.length() - 1 -j] = temp % 10;
                carry = temp / 10;
            }
            if (carry != 0) {
                digits[num1.length() + num2.length() - 1 - i] = carry;
            }
        }
        int i = 0, j = digits.length - 1;
        while (i < j) {
            int temp = digits[i];
            digits[i] = digits[j];
            digits[j] = temp;
            i++;
            j--;
        }
        StringBuilder builder = new StringBuilder();
        for (int k = 0; k < digits.length; k++) {
            if (builder.length() == 0 && digits[k] == 0) {
                continue;
            }
            builder.append(digits[k]);
        }
        if (builder.length() == 0) {
            builder.append(0);
        }
        return builder.toString();
    }
}

精简很多的code的写法：

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        int[] res = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int index1 = i + j, index2 = i + j + 1;
                int sum = mul + res[index2];
                res[index1] += sum / 10;
                res[index2] = (sum % 10);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int num : res) {
            if (!(sb.length() == 0 && num == 0)) sb.append(num);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

发表于 | 分类于

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

1
2
3
4
5
6
7
[
 "((()))",
 "(()())",
 "(())()",
 "()(())",
 "()()()"
]

解法1：

比较经典的DFS题目,dfs的思想要掌握
C++

1

Java

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
public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        helper("", res, n, n);
        return res;
    }
    private void helper(String current, List<String> res, int left, int right) {
        if (left == 0 && right == 0) {
            res.add(current);
            return;
        }
        if (left > 0) {
            helper(current + "(", res, left - 1, right);
        }
        if (right > 0 && left < right) {
            helper(current + ")", res, left, right - 1);
        }
    }
}

发表于 | 分类于

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

Clarification:

What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

解法1：

用一个stack来存储每一个找出来的word，然后再一个个pop出来同时加上space
C++

1

Java

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
public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        Stack<String> words = new Stack<String>();
        int i = 0, j = 0;
        while (i < s.length()) {
            while (i < s.length() && s.charAt(i) == ' ') {
                i++;
            }
            j = i + 1;
            while (j < s.length() && s.charAt(j) != ' ') {
                j++;
            }
            if (i < s.length()) {
                words.push(s.substring(i, j));
            }
            i = j;
        }
        StringBuilder builder = new StringBuilder();
        while (!words.empty()) {
            builder.append(words.pop());
            builder.append(' ');
        }
        if (builder.length() > 0) {
            builder.setLength(builder.length() - 1);        
        }
        return builder.toString();
    }
}

发表于 | 分类于

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

1
string convert(string text, int nRows);

convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

解法1：O(N) Time + O(N) Space

这题的数学解法很难想，也比较花时间。很直观的做法倒是不错。就每一行用一个stringbuilder，然后一行行的塞。先从上往下，再从下往上斜着填。
当所有数字填满了之后把stringbuilder连起来就可以了。
C++

1

Java

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 String convert(String s, int numRows) {
        StringBuilder[] builders = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            builders[i] = new StringBuilder();
        }
        int pos = 0;
        while (pos < s.length()) {
            for (int i = 0; i < numRows && pos < s.length(); i++) {
                builders[i].append(s.charAt(pos++));
            }
            for (int i = numRows - 2; i >= 1 && pos < s.length(); i--) {
                builders[i].append(s.charAt(pos++));
            }
        }
        for (int i = 1; i < numRows; i++) {
            builders[0].append(builders[i]);
        }
        return builders[0].toString();
    }
}

发表于 | 分类于

Given a group of two strings, you need to find the longest uncommon subsequence of this group of two strings. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.

A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.

The input will be two strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn’t exist, return -1.

Example 1:

1
2
3
4
5
Input: "aba", "cdc"
Output: 3
Explanation: The longest uncommon subsequence is "aba" (or "cdc"),
because "aba" is a subsequence of "aba",
but not a subsequence of any other strings in the group of two strings.

Note:

Both strings’ lengths will not exceed 100.
Only letters from a ~ z will appear in input strings.

解法1：

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int findLUSlength(String a, String b) {
        if (a == null || b == null) {
           return -1;
        }
        if (a.equals(b)) {
            return -1;
        }
        return Math.max(a.length(), b.length());
    }
}

发表于 | 分类于

You are given a string representing an attendance record for a student. The record only contains the following three characters:

'A' : Absent.
'L' : Late.
'P' : Present.

A student could be rewarded if his attendance record doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:

1
2
Input: "PPALLP"
Output: True

Example 2:

1
2
Input: "PPALLL"
Output: False

解法1：

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public boolean checkRecord(String s) {
        int aCount = 0, lCount = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'A') {
                aCount++;
                lCount = 0;
            } else if (s.charAt(i) == 'L') {
                lCount++;
            } else {
                lCount = 0;
            }
            if (aCount > 1 || lCount > 2) {
                return false;
            }
        }
        return true;        
    }
}

发表于 | 分类于

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     
Output: "1(2(4))(3)"
Explanation: Originallay it needs to be "1(2(4)())(3()())",
but you need to omit all the unnecessary empty parenthesis pairs.
And it will be "1(2(4))(3)".

Example 2:

1
2
3
4
5
6
7
8
9
10
11
Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example,
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

解法1：

C++

1

Java

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public String tree2str(TreeNode t) {
        StringBuilder builder = new StringBuilder();        
        helper(builder, t);
        return builder.toString();
    }
    private void helper(StringBuilder builder, TreeNode t) {
        if (t != null) {
            builder.append(Integer.toString(t.val));
            if (t.left != null || t.right != null) {
                builder.append("(");
                helper(builder, t.left);
                builder.append(")");
                if (t.right != null) {
                    builder.append("(");
                    helper(builder, t.right);
                    builder.append(")");
                }
            }
        }
    }
}

发表于 | 分类于

Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.

A string such as “word” contains only the following valid abbreviations:

1
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Notice that only the above abbreviations are valid abbreviations of the string “word”. Any other string is not a valid abbreviation of “word”.

Note:
Assume s contains only lowercase letters and abbr contains only lowercase letters and digits.

Example 1:

1
2
3
Given s = "internationalization", abbr = "i12iz4n":
Return true.

Example 2:

1
2
3
Given s = "apple", abbr = "a2e":
Return false.

解法1：

string类的题目似乎用指针可以规避掉一些cornercase的处理。这题用两个指针维护当前比较的起始位置。
先比较是否相等，如果相等则都往前进一步。
如果不相等，则考虑abbr是否为数字，把数字parse出来后i相应的比较位置就前进对应的数字个数。
这里要注意的是，数字的开端不能为０.
C++

1

Java

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
public class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        if (word == null && abbr == null) {
            return true;
        } else if (word == null || abbr == null) {
            return false;
        }
        int i = 0, j = 0;
        while (i < word.length() && j < abbr.length()) {
            char w = word.charAt(i);
            char a = abbr.charAt(j);
            if (w == a) {
                i++;
                j++;
            } else if (a > '0' && a <= '9') {
                int start = j;
                while (j < abbr.length() && abbr.charAt(j) >= '0' && abbr.charAt(j) <= '9') {
                    j++;
                }
                i += Integer.valueOf(abbr.substring(start, j));
            } else {
                return false;
            }
        }
        return i == word.length() && j == abbr.length();
    }
}

发表于 | 分类于

The API: int read4(char[] buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function will only be called once for each test case.

解法1：

C++

1

Java

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
/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); */
public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    public int read(char[] buf, int n) {
        char[] buffer = new char[4];
        int pos = 0;
        while (pos < n) {
            int read = read4(buffer);
            for (int i = 0; i < read && pos < n; i++) {
                buf[pos++] = buffer[i];
            }
            if (read == 0) {
                break;
            }
        }
        return pos;
    }
}

发表于 | 分类于

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

解法1：

C++

1

Java

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 strStr(String haystack, String needle) {
        if (needle == null || haystack == null) {
            return -1;
        }
        int n = haystack.length(), m = needle.length();
        if (m > n) {
            return -1;
        }
        for (int i = 0; i <= n - m; i++) {
            if (haystack.substring(i, i + m).equals(needle)) {
                return i;
            }
        }
        return -1;        
    }
}