52Heartz's Blog

分享科技与生活

发表于 更新于 分类于

解答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
public class Solution {
    public int minNumberInRotateArray(int[] array) {
        int index1 = 0;
        int index2 = array.length - 1;
        int indexMid = 0;

        if (array.length == 0) {
            return 0;
        }

        while (array[index1] >= array[index2]) {
            if (index2 - index1 == 1) {
                indexMid = index2;
                break;
            }

            indexMid = (index1 + index2) / 2;

            if (array[index1] == array[indexMid] && array[indexMid] == array[index2]) {
                return minSequentialSearch(array);
            }

            if (array[indexMid] >= array[index1]) {
                index1 = indexMid;
            } else if (array[indexMid] <= array[index2]) {
                index2 = indexMid;
            }
        }

        return array[indexMid];
    }

    private int minSequentialSearch(int[] array) {
        int indexMin = 0;
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[indexMin]) {
                indexMin = i;
            }
        }

        return array[indexMin];
    }
}

时间复杂度

时间复杂度为对数级别 $O(logN)$。

解答2[Java]：时间复杂度 $O(n/2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int minNumberInRotateArray(int[] array) {
        if (array.length == 0) {
            return 0;
        }

        int min = array[0];

        for (int i = 1; i < array.length; ++i) {
            if (array[i] < min) {
                return array[i];
            }
        }

        return min;
    }
}

思路

旋转之后，从左向右对比两个相邻的数，总会找到一组数，第一个数大于第二个数，那么第二个数就是最小值。因为第二个数往后的所有数就是旋转操作移到最后的一系列数。

发表于 更新于

关于二进制的表示方法，需要深入的了解一下。这个内容和Java中整形变量的存储有关。

整形类型，以二进制表示的情况下，最高位是符号位，其余用来存储具体数值。符号位为0，那么是一个正值，符号位为1，那么为一个负值。那么是不是对于一个正值，十进制下值为5，是不是把二进制表示情况下的最高位从0改为1，这个值就变成-5了呢？

其实不是的。二进制表示的正数和负数，计数规则是不一样的。

今天计算机当中表示整数最普遍的系统是二进制补码（two’s complement）计数法。

我们来看使用4个位（bit）来表示整数的情况。

第一位是符号位，表示正负，0 代表为正，1代表负。

剩下三位，表示正数的时候就和普通的二进制计数法一样。

表示负数的时候，000表示8，001表示7……

如图所示：

two-complement-notation

如何把表示负数的补码转换成普通的二进制表示法呢？

首先，根据符号位确定正负号，然后把符号为排除在外。

然后把补码从右向左数，遇到第一个1之后，把第一个1左边的所有数取反，也就是0改为1，1改为0。

然后再按照普通二进制计数法来解读就可以了。

比如 1001 表示 -7 实际就是，先把符号为看作负号，然后把 001 中 1 左边的 00 改为 11，最后结果就是 -7。

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/multiply-strings/

题目难度：Medium

解答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
import java.util.Scanner;
public class Main {
    public String multiply(String num1, String num2) {
        int n1 = num1.length(), n2 = num2.length();
        int[] products = new int[n1 + n2];
        for (int i = n1 - 1; i >= 0; i--) {
            for (int j = n2 - 1; j >= 0; j--) {
                int d1 = num1.charAt(i) - '0';
                int d2 = num2.charAt(j) - '0';
                products[i + j + 1] += d1 * d2;
            }
        }
        int carry = 0;
        for (int i = products.length - 1; i >= 0; i--) {
            int tmp = (products[i] + carry) % 10;
            carry = (products[i] + carry) / 10;
            products[i] = tmp;
        }
        StringBuilder sb = new StringBuilder();
        for (int num : products)
            sb.append(num);
        while (sb.length() != 0 && sb.charAt(0) == '0')
            sb.deleteCharAt(0);
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

这个算法基于一下规律：

  1. 位数分别为 i 和 j 的两个数相乘，乘积的位数不超过 i+j 位。
  2. 把结果看作一个大小为 i+j 的数组，那么第一个数的第 i 位和第二个数的第 j 位的乘积会影响结果的第 i+j 位和第 i+j+1 位。

因此，把第一个数的第 i 位和第二个数的第 j 位的乘积先存到结果的 i+j+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
import java.util.Scanner;

public class Main {
    public String longestPalindrome(String s) {
        int curLen = 0;
        int start = -1;
        char[] array = s.toCharArray();
        for (int i = 0; i < array.length; i++) {
            if (isPalindrome(array, i - curLen - 1, i)) {
                start = i - curLen - 1;
                curLen += 2;
            } else if (isPalindrome(array, i - curLen, i)) {
                start = i - curLen;
                curLen += 1;
            }
        }
        return new String(array, start, curLen);
    }

    private boolean isPalindrome(char[] array, int start, int end) {
        if (start < 0) {
            return false;
        }
        while (start < end) {
            if (array[start++] != array[end--]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String string = in.nextLine();
        System.out.println(new Main().longestPalindrome(string));
    }
}

参考链接

  1. (AC) relatively short and very clear Java solution
  2. LeetCode 5. Longest Palindromic Substring
  3. 最长回文子串——Manacher 算法

发表于 更新于 分类于

题目

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2, 4, 7, 3, 5, 6, 8} 和中序遍历序列 {4, 7, 2, 1, 5, 3, 8, 6}，则重建出二叉树并输出它的头结点。

阅读全文 »
0%