LeetCode 50. Pow(x, n) 剑指Offer 16.数值的整数次方 [Medium]

发表于 2020-02-03 更新于 2024-08-05 分类于 LeetCode ， Medium

题目

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

1 2	Input: 2.00000, 10 Output: 1024.00000

Example 2:

1 2	Input: 2.10000, 3 Output: 9.26100

Example 3:

1
2
3

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−231, 231 − 1]

解法1[Java]

分析

需要注意处理一些边界情况。对 Integer.MIN_VALUE 直接取负获取绝对值的方法是不行的，因为直接取负会导致数值溢出。没有对应的绝对值。

LeetCode 191. Number of 1 Bits 剑指Offer 15 二进制中 1 的个数

发表于 2020-02-03 更新于 2024-08-05 分类于 LeetCode ， Easy

Write a function that takes an unsigned integer and return the number of ‘1’ bits it has (also known as the Hamming weight).

Example 1:

1
2
3

Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

1
2
3

Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

1
2
3

Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3 above the input represents the signed integer -3.

Follow up:

If this function is called many times, how would you optimize it?

解答1[Java]

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        int flag = 1;
        for (int i = 0; i < 32; ++i) {
            if ((n & flag) != 0) {
                ++count;
            }
            flag <<= 1;
        }

        return count;
    }
}

解答2[Java]

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;

        while (n != 0) {
            n &= (n - 1);
            ++count;
        }

        return count;
    }
}

LeetCode 343. Integer Break 剑指Offer 14. 剪绳子 [Medium]

发表于 2020-02-01 更新于 2024-08-05

题目来源：https://leetcode.com/problems/integer-break/

题目难度：Medium

题目

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

1
2
3

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

1
2
3

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note: You may assume that n is not less than 2 and not larger than 58.

解答1[Java]：动态规划

public class Solution {
    public int integerBreak(int n) {
        if (n == 2) {
            return 1;
        } else if (n == 3) {
            return 2;
        }

        int[] product = new int[n + 1];

        product[2] = 2;
        product[3] = 3;

        int maxProduct;

        for (int i = 4; i <= n; ++i) {
            maxProduct = 0;
            for (int j = 2; j <= i / 2; ++j) {
                int tempProduct = product[j] * product[i - j];
                if (tempProduct > maxProduct) {
                    maxProduct = tempProduct;
                }
            }
            product[i] = maxProduct;
        }

        return product[n];
    }
}

分析

长度为 2 和 3 的时候其实不切更好的，但是要求要切，可以当作特殊情况直接返回对应的结果。

动态规划的思路：

定义一个数组 product[]，但是注意，长度为 2 和 3 的时候，我们不再切分，所以我们使 product[2] 为 2，product[3] 为 3。然后从 4 开始计算每个数切分后的最大值。

解答2[Java]：贪心算法

public class Solution {
    public int integerBreak(int n) {
        if (n == 2) {
            return 1;
        } else if (n == 3) {
            return 2;
        }

        int remainder = n % 3;
        int result = n / 3;

        if (remainder == 0) {
            return (int) Math.pow(3, result);
        } else if (remainder == 1) {
            return (int) Math.pow(3, result - 1) * 4;
        } else {
            return (int) Math.pow(3, result) * 2;
        }
    }
}

分析

切要一下一下的切。对于一个数，切还是不切，要看切之后乘积是不是比原来更大。

使用 $N$ 表示一个数，使用函数 $f=x(N-x)$ 表示切分后的乘积。当 $x=\frac{N}{2}$ 时，乘积最大。

但是因为 $N$ 和 $x$ 都必须是整数，

那么当 $N$ 是偶数的时候，则当 $x=\frac{N}{2}$ 时乘积最大，最大为 $\frac{N}{2} \times \frac{N}{2}$。

当 $N$ 是偶数的时候，则当 $x=\frac{N+1}{2}$ 或者 $x=\frac{N-1}{2}$ 时，乘积最大，最大值为 $\frac{N+1}{2} \times \frac{N-1}{2}$

如果想要切分之后的乘积比原来更大，则要求 $\frac{N}{2} \times \frac{N}{2} > N$ 和 $\frac{N+1}{2} \times \frac{N-1}{2} > N$

当 $N$ 是偶数的时候，$N \ge 4$ 的时候，切分后乘积大于等于原来的数。

当 $N$ 是奇数的时候，$N \ge 5$ 的时候，切分后乘积更大。

也就是说，只要 $N \ge 4$ 的时候我们就要切分。2 和 3 的时候不切分。

4 的时候可以切分成 2 和 2，5 的时候可以切分成 2 和 3。

然后你会发现，所有的数最后都会被切分成若干个 2 和若干个 3。

所以现在问题就变成 $N = 2x + 3y$ 如果分配 $x$ 和 $y$ 的问题。

$3(N-3)$ 和 $2(N-2)$ 哪个大？

$3(N-3)-2(N-2)=N-5$

当 $N>5$ 时，优先切 3 的到的结果更大。

当 $N \le 5$ 时，也就只有 4 和 5 两种情况，4 的话切和不切是一样的乘积都不会变大，5 的话切 2 和切 3 是一样的，切完乘积都是 6。

参考资料

A simple explanation of the math part and a O(n) solution - LeetCode Discussion

LeetCode 5. Longest Palindromic Substring [Medium]

发表于 2020-01-30 更新于 2024-08-05 分类于 LeetCode ， Medium

题目来源：https://leetcode.com/problems/longest-palindromic-substring/

题目难度：Medium

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1 2	Input: "cbbd" Output: "bb"

解答1[Java]

解答2[Java]

使用 S 表示原字符串

使用 T 表示转换过后的字符串

使用 C 表示目前已知的子回文串中，右边界的位置最大的那个子回文串的中心。

使用 R 表示以 C 为中心的回文串的最右端的位置。

使用 i 表示 T 中正要确定回文串长度的一个位置。

使用 i’ 表示以 C 为中心，i 的对称位置

假设字符串 S 为 babcbabcbaccba

转换为字符串 T：#b#a#b#c#b#a#b#c#b#a#c#c#b#a#

考虑以下三种情况：

情况1：i’ 的回文串的左边界不超过 C 的回文串的左边界。

这种情况下，P[i] = P[i’]

情况2：i’ 的回文串的左边界超过了 C 的回文串的左边界。

这种情况下，i 的右边界不可能超过 C 的右边界，因为如果 i 的右边界超过了 C 的右边界，则证明 C 的回文串的长度还能更长。

情况3：i’ 的回文串的左边界和 C 的回文串的左边界相同。

参考资料

LeetCode 4. Median of Two Sorted Arrays [Hard]

发表于 2020-01-30 更新于 2024-08-05 分类于 LeetCode ， Hard

题目来源：

题目难度：Hard

题目

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

解答1[Java]

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int[] nums = new int[nums1.length + nums2.length];
    System.arraycopy(nums1, 0, nums, 0, nums1.length);
    System.arraycopy(nums2, 0, nums, nums1.length, nums2.length);
    Arrays.sort(nums);
    if ((nums.length & 1) == 0) {
        return (nums[(nums.length / 2) - 1] + nums[nums.length / 2]) / 2.0;
    } else {
        return nums[nums.length / 2];
    }
}

时空复杂度分析

时间复杂度：$O((m+n)log(m+n))$

空间复杂度：$O(m+n)$

解法2[Java]

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) {
            int[] temp = A;
            A = B;
            B = temp;
            int tmp = m;
            m = n;
            n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && B[j - 1] > A[i]) {
                iMin = i + 1;
            } else if (i > iMin && A[i - 1] > B[j]) {
                iMax = i - 1;
            } else {
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = B[halfLen - 1];
                } else if (j == 0) {
                    maxLeft = A[halfLen - 1];
                } else {
                    maxLeft = Math.max(A[i - 1], B[j - 1]);
                }
                if (((m + n) & 1) == 1) {
                    return maxLeft;
                }

                int minRight;
                if (i == m) {
                    minRight = B[j];
                } else if (j == n) {
                    minRight = A[i];
                } else {
                    minRight = Math.min(B[j], A[i]);
                }

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
}

算法分析

核心思想是二分查找。

假设 A 数组是长度为 4，B 数组长度为 6，那么把 A 数组和 B 数组混合，然后重新排序，称之为数组 C。那么数组 C 的前半部分，必定由 A 中的若干个数和 B 中的若干个数组成。

时空复杂度分析

时间复杂度：$O(log(min(m,n))$

空间复杂度：$O(1)$

拓展

思考：如果是求三个有序数组的中位数呢？

参考资料

官方题解：Median of Two Sorted Arrays - LeetCode Articles

关于 SQLite

发表于 2020-01-29 更新于 2022-09-13 分类于 Java

官方文档：SQLite Home Page

自增主键

自增主键必须是 INTEGER PRIMARY KEY，INT PRIMARY KEY 都不行。

Caused by: org.sqlite.SQLiteException: [SQLITE_ERROR] SQL error or missing database (AUTOINCREMENT is only allowed on an INTEGER PRIMARY KEY)
	at org.sqlite.core.DB.newSQLException(DB.java:1010)
	at org.sqlite.core.DB.newSQLException(DB.java:1022)
	at org.sqlite.core.DB.throwex(DB.java:987)
	at org.sqlite.core.NativeDB._exec_utf8(NativeDB.java)
	at org.sqlite.core.NativeDB._exec(NativeDB.java:94)
	at org.sqlite.jdbc3.JDBC3Statement.executeUpdate(JDBC3Statement.java:109)

详细可参考：CREATE TABLE

With one exception noted below, if a rowid table has a primary key that consists of a single column and the declared type of that column is “INTEGER” in any mixture of upper and lower case, then the column becomes an alias for the rowid. Such a column is usually referred to as an “integer primary key”. A PRIMARY KEY column only becomes an integer primary key if the declared type name is exactly “INTEGER”. Other integer type names like “INT” or “BIGINT” or “SHORT INTEGER” or “UNSIGNED INTEGER” causes the primary key column to behave as an ordinary table column with integer affinity and a unique index, not as an alias for the rowid.

拓展

Zepo/GYDataCenter: An alternative to Core Data for people who like using SQLite directly.

常见问题

加载 native library 出错

报错：

Caused by: java.lang.Exception: No native library is found for os.name=Linux and os.arch=ppc64le. path=/org/sqlite/native/Linux/ppc64le
at org.sqlite.SQLiteJDBCLoader.loadSQLiteNativeLibrary(SQLiteJDBCLoader.java:333) ~[sqlite-jdbc-3.28.0.jar:?]
at org.sqlite.SQLiteJDBCLoader.initialize(SQLiteJDBCLoader.java:64) ~[sqlite-jdbc-3.28.0.jar:?]
at org.sqlite.core.NativeDB.load(NativeDB.java:63) ~[sqlite-jdbc-3.28.0.jar:?]
at org.sqlite.SQLiteConnection.open(SQLiteConnection.java:235) ~[sqlite-jdbc-3.28.0.jar:?]

可能原因之一：

SQLite 数据初次启动时需要加载 native library，需要把打包在 JAR 中的 native library 文件解压到临时目录中，如果当前操作系统用户读写操作系统默认临时目录有权限问题，就有可能会无法正常加载到 native library 导致此报错。