Haiyang Yu's Blog
0%

发表于 更新于 Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：

1
2
3
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

1
2
3
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

2 <= n <= 58

1. 贪心

如果我们给定了绳子长度n, 和绳子个数m, 那么就可以在O(1)时间内算出来最大乘积.

假设绳子可以取值实数, 最大解肯定是每个绳子的长度都一样长, 这样才能最大. 很简单的原理, 如果一个绳子长为a, 一个绳子长为b, (a != b), 那么换一种剪法, 都剪成(a + b) / 2的长度, 那么新的乘积((a + b) / 2) ^ 2肯定大于原来的乘积ab. (均值不等式)

所以, 每个绳子的长度就为n/m的时候最大. 但是这里要求绳子长度为整数, 所以必定有的绳子长度是floor(n/m), 有的长度为floor(n/m) + 1. 但是不会出现任意两条绳子的差值超过1的情况.

所以, 应该有n % m条绳子长为floor(n/m) + 1, m - n % m 条绳子长为floor(n/m). 计算乘积即可.

最后, m由2遍历到n, 找出最大的返回即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int cuttingRope(int n) {
        double maxProduct = 0.0;
        for(int m = 2; m <= n; ++m)
        {
            maxProduct = Math.max(maxProduct, cuttingRope(n,m));
        }
        return (int) maxProduct;
    }

    private double cuttingRope(int n, int m)
    {
        int len = n / m;
        int len_Plus1 = len + 1;
        int count_len_Plus1 = n % m;
        int count_len = m - count_len_Plus1;
        return Math.pow(len, count_len) * Math.pow(len_Plus1, count_len_Plus1);
    }
}

2. 数学推导

https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/mian-shi-ti-14-i-jian-sheng-zi-tan-xin-si-xiang-by/

这个方法真的巧妙, 我一开始用的绳子的个数m推导的, 即求(n/m)^m的最大值, 得到m = n/e. 然后去用两个整数逼近m. 但是这个是不对的, 因为当n = 30的时候, m = 11.03. 如果用11和12逼近的话, 永远不会找到最大值是m = 10.

但是用绳子的长度x就可以, 推导出来x = e的时候有最大值. 整数逼近e为2或3, 同时, 2个3的乘积比3个2的乘积大, 就一段一段的截取3就可以了.

同时要注意特殊情况, 如果最后一段是1, 那么把上一段的3匀出来成为2 * 2, 会比3 * 1大.

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 int cuttingRope(int n) {
        if(n <= 3)
            return n - 1;
        else
        {
            int m = n / 3;
            int remain = n % 3;
            if(remain == 0)
            {
                return (int) Math.pow(3, m);
            }
            else if(remain == 1)
            {
                return (int) Math.pow(3, m-1) * 4;
            }
            else
            {
                return (int) Math.pow(3, m) * 2;
            }
        }
    }
}

发表于 更新于 Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

1
2
3
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

1
2
3
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

2 <= n <= 1000

1. 快速幂求余(递归)

和上一题剑指 Offer 14- I. 剪绳子一样, 只不过这次要求出的数很大, 需要取模.

整道题的难点都在pow(3,m) % c上面了

先用java内置函数求出pow(3,m)再取模肯定是不行的, 那样pow(3,m)会太大了超过long的范围. 所以我们只能自己定义一个函数long pow(int a, int b, int c) 来计算a ^ b % 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
class Solution {
    public int cuttingRope(int n) {
        if(n <= 3)
            return n - 1;
        else
        {
            long ans = 0L;
            int m = n / 3;
            int remain = n % 3;
            int c = 1000000007;
            if(remain == 0)
            {
                ans = pow(3, m, c);
            }
            else if(remain == 1)
            {
                ans = pow(3, m-1, c) * 4 % c;
            }
            else
            {
                ans = pow(3, m, c) * 2 % c;
            }
            return (int) ans;
        }
    }

    private long pow(int a, int b, int c)
    {
        if(b == 0)
            return 1;
        if(b == 1)
            return a % c;
        if((b & 1) == 0)
            return pow(a, b/2, c) * pow(a, b/2, c) % c;
        else
            return (pow(a, b/2, c) * a % c) * pow(a, b/2, c) % c;
    }
}

2. 快速幂(循环)

参考于https://zhuanlan.zhihu.com/p/95902286

通过2进制的运算, 转化指数.

例如要计算a的10次幂, 10写为2进制之后为1010

可以转化为 0个a的1次幂, 1个a的2次幂, 0个a的4次幂, 1个a的8次幂.

所以依次计算即可.

记a的起始值为a0

从a的1次幂开始, 如果n末尾为0, 就说明没有a的1次幂, ans不变, a变为a * a. n = n / 2.

现在n = 5, 末尾为1, a = a0^2, 说明有1个a的2次幂, *ans = a, 再次更新a变为a * a. n = n / 2.

现在n = 2, 末尾为0, a = a0^4, 说明没有a的4次幂, ans不变, 再次更新a变为a * a. n = n / 2.

现在n = 1, 末尾为1, a = a0^8, 说明有1个a的8次幂, *ans = a, 再次更新a变为a * a. n = n / 2.

现在 n = 0, 结束循环.

从上面看出, ans 与a0^2相乘过一次, 与a0^8相乘一次, 刚好为a0^10.

这种方法应该是快速幂最优解法了, 对数复杂度, 常数空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private long pow(int a0, int b, int c)
    {
        long a = a0;
        if(b < 0)
            return 0;
        long ans = 1;
        int n = b;
        while(n > 0)
        {
            if((n & 1) == 1)
            {
                ans = ans * a % c;
            }
            a = a * a % c;
            n = n >> 1;
        }
        return ans;
    }

发表于 更新于 Valine：
本文字数： 776 阅读时长 ≈ 1 分钟

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

1
2
3
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

1
2
3
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

1
2
3
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

输入必须是长度为 32 的 二进制串 。

1. 位运算

和leetcode 191相同, 不断地使用n = n & (n - 1)操作即可, 直到n == 0

也可以使用一个游标cursor = 1, cursor每次左移一位, 每次都与n进行AND位运算, 统计位运算中1的个数.

也可以判断n最后一位是不是1, 然后将n不断地右移, 直到n = 0. 这种方法要注意一定要用无符号右移, 即java中的>>>.

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int ans = 0;
        while(n != 0)
        {
            n = n & (n - 1);
            ++ans;
        }
        return ans;
    }
}

发表于 更新于 Valine：
本文字数： 1.1k 阅读时长 ≈ 1 分钟

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1:

1
2
输入: 2.00000, 10
输出: 1024.00000

示例 2:

1
2
输入: 2.10000, 3
输出: 9.26100

示例 3:

1
2
3
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

1. 快速幂

题本身不难, 就是要注意先判断边界条件, 这个题边界条件非常多!

首先要判断x是不是等于0. 而不是先判断n是不是等于0. (如果你先判断n, n为负, 返回1/x的-n次方. 如果这时候x为0就gg了.)

x如果等于0, 对于大于0的n, 小于0的n, 等于0的n都有处理方法.

这里还要注意判断x为0的时候是浮点数直接用==来判断还是要指定eps. 如果是面试可以问面试官怎么处理.

处理完x等于0之后, 再处理n小于等于0了

等于0, 小于0都好说, 但是不要忘了这有个坑n = -2147483648 = INT_MIN. 如果直接判断n<0就转化成1/x的-n次方那肯定这里会出错!!!

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
class Solution {
    public double myPow(double x, int n) {
        if(x == 0.0)
        {
            if(n == 0){
                throw new ArithmeticException("Undefined behavior");
            }
            else if(n < 0){
                return Double.POSITIVE_INFINITY;
            }
            else{
                return 0.0;
            }
        }
        if(n == 0)
            return 1.0;
        if(n < 0 && n != Integer.MIN_VALUE)
            return myPow(1/x, -n);
        if(n == Integer.MIN_VALUE)
        {
            return myPow(x, Integer.MIN_VALUE + 1) * myPow(x, -1);
        }
        double ans = 1.0;
        while(n > 0)
        {
            if((n&1) == 1)
                ans *= x;
            x *= x;
            n >>= 1;
        }
        return ans;
        
    }
}

发表于 更新于 Valine：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

1
2
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明：

用返回一个整数列表来代替打印
n 为正整数

1. 大数运算

这题要是按照leetcode来, 肯定不行. leetcode上面的函数是public int[] printNumbers(int n). 因为返回值是int[], 自然不需要考虑int溢出的问题. 没法达到使用大数的效果.

还是自己写一个吧. 这题的关键在于

  • 是否判断n<=0的情况
  • 字符串表示的数的加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
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> printNumbers(int n) {
        if(n <= 0){
            return new ArrayList<>();
        }
        String begin = "1";
        List<String> list = new ArrayList<>();
        while (begin.length() <= n)
        {
            list.add(begin);
            begin = stringIncrement(begin);
        }
        return list;
    }

    private String stringIncrement(String s){
        char[] chars = s.toCharArray();
        int i = chars.length - 1;
        while(i >= 0)
        {
            if (chars[i] != '9')
                break;
            --i;
        }
        if(i == -1)
        {
            char[] ans = new char[chars.length + 1];
            ans[0] = '1';
            for(int k = 1; k < ans.length; ++k)
            {
                ans[k] = '0';
            }
            return  String.valueOf(ans);
        }
        else
        {
            chars[i] += 1;
            for(int j = i + 1; j < chars.length; ++j)
            {
                chars[j] = '0';
            }
            return String.valueOf(chars);
        }
    }

    public static void main(String[] args) {
        //test cases
        // n = 0, -1, 1, 2, 3
        Solution s = new Solution();
        System.out.println(s.printNumbers(2));
    }
}

发表于 更新于 Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123”都表示数值，但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。

阅读全文 »

发表于 更新于 Valine：
本文字数： 1.6k 阅读时长 ≈ 1 分钟

给定单向链表的头指针和一个要删除的节点，定义一个函数删除该节点。

阅读全文 »

发表于 更新于 Valine：
本文字数： 4.6k 阅读时长 ≈ 4 分钟

请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。

示例 1:

输入:

1
2
3
4
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
4
5
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

1
2
3
4
5
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

1
2
3
4
5
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

1
2
3
4
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和无连续的 ‘*’。

阅读全文 »

发表于 更新于 Valine：
本文字数： 902 阅读时长 ≈ 1 分钟

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

阅读全文 »

发表于 更新于 Valine：
本文字数： 898 阅读时长 ≈ 1 分钟

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

阅读全文 »