8.17刷题

发表于 | 分类于 | 0 comments

第一题 38. Count and Say

题目描述

第一个给出的是String = 1,之后每一个都是按照一定规律对前面的那个String进行描述。

例如，第一个数是1，第二个则对第一个进行描述，有1个1 = > 11
第二个数即为11, 第三个对第二个进行描述，可看做2个1 => 21
则第三个数为21，第四个对第三个进行描述，可看做1个2 和 1个1 = > 1211
依次类推

算法

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
class Solution {
    public String countAndSay(int n) {
        StringBuilder cur = new StringBuilder();
        cur.append(1);
        StringBuilder pre = new StringBuilder();
        for (int i = 1; i < n; i++) {
            pre = cur;
            cur =  new StringBuilder();
            int count = 1;
            char prechar = pre.charAt(0);
            for (int j = 1, len = pre.length(); j < pre.length(); j++) {
                if (prechar == pre.charAt(j)) {
                    count++;
                }
                else {
                    cur.append(count).append(prechar);
                    prechar = pre.charAt(j);
                    count = 1;
                }
            }
            cur.append(count).append(prechar);
        }
        return cur.toString();        
    }
}

第二题 271. Encode and Decode Strings

题目描述

将List中的所有String encode成为一段String，并能够decode返回原来的String

算法

利用count + /的方式进行encode和decode

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 Codec {
    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str.length()).append('/').append(str);
        }
        return sb.toString();
    }
    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> res = new ArrayList<>();
        int index = 0;
        while (index < s.length()) {
            int sep = s.indexOf('/', index);
            int count = Integer.valueOf(s.substring(index, sep));
            res.add(s.substring(sep + 1, sep + count + 1));
            index = sep + count + 1;
        }
        return res;
    }
}

第三题 67. Add Binary

题目描述

在Binary的数字表达下加1

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int indexa = a.length() - 1, indexb = b.length() - 1, carry = 0;
        while (indexa >= 0 || indexb >= 0) {
            int sum = carry;
            if (indexa >= 0) sum += a.charAt(indexa--) - '0';
            if (indexb >= 0) sum += b.charAt(indexb--) - '0';
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry != 0) sb.append(carry);
        return sb.reverse().toString();        
    }
}

第四题 43. Multiply Strings

题目描述

将两个String作为乘法相乘

算法

如果两个数相乘，那么他们对应的位置的乘机永远是一个两位数，乘机的结果在第i + j + 1和第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
class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length(), 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 part1 = i + j, part2 = i + j + 1;
                int sum = res[part2];
                sum += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                res[part2] = sum % 10;
                res[part1] += 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();        
    }
}