【LeetCode】﹝数学规律ி﹞第N位数字、可怜的小猪

冷不防 2023-01-21 10:19 6阅读 0赞

## 【LeetCode】﹝数学规律ி﹞第N位数字、可怜的小猪 ##

### 文章目录 ###

*   *  【LeetCode】﹝数学规律ி﹞第N位数字、可怜的小猪
     *   *  乐团站位★
         *  罗马数字转整数★
         *  整数转罗马数字★★
         *  第 N 位数字★★
         *  数字 1 的个数★★★
         *  森林中的兔子★★
         *  直线上最多的点数★★★
         *  可怜的小猪★★★

### 乐团站位★ ###

[LCP 29. 乐团站位][LCP 29.]

【**题目**】某乐团的演出场地可视作 `num * num` 的二维矩阵 `grid`（左上角坐标为 `[0,0]`)，每个位置站有一位成员。乐团共有 `9` 种乐器，乐器编号为 `1~9`，每位成员持有 `1` 个乐器。

为保证声乐混合效果，成员站位规则为：自 `grid` 左上角开始顺时针螺旋形向内循环以 `1，2，...，9` 循环重复排列。例如当 `num = 5` 时，站位如图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

请返回位于场地坐标 \[`Xpos`,`Ypos`\] 的成员所持乐器编号。

**提示：**

*  `1 <= num <= 10^9`
 *  `0 <= Xpos, Ypos < num`

【**示例**】

输入：num = 3, Xpos = 0, Ypos = 2
    输出：3
    ------
    1 2 3
    8 9 4
    7 6 5

【**解题思路**】

参考题解[解题思路，先看在第几圈，再看在哪条边][Link 1]

class Solution {
        
        public int orchestraLayout(int num, int xPos, int yPos) {
        
            //先判断位于第几圈(注意圈数从0开始计数)
            long layer = Math.min(num - xPos - 1, num - yPos - 1);
            layer = Math.min(layer, Math.min(xPos, yPos));
            //使用变量t标记前几层的最后站位,大正方形减去小正方形
            //int t = (num * num - (num - 2 * layer) * (num - 2 * layer)) % 9;
            long t = 4 * layer * (num - layer) % 9;
    
            //顺时针（上右下左）四个边界分类讨论
            long start = layer, end = num - layer;
            if (xPos == start) {
        
                t += yPos - start;
            } else if (yPos == end - 1) {
        
                t += end - start - 1 + xPos - start; 
            } else if (xPos == end - 1) {
        
                t += (end - start) * 2 - 2 + end - yPos - 1;
            } else {
        
                t += (end - start) * 3 - 3 + end - xPos - 1;
            }
    
            return (int)(t % 9) + 1;
        }
    }

--------------------

### 罗马数字转整数★ ###

[13. 罗马数字转整数][13.]

【**题目**】罗马数字包含以下七种字符: `I`， `V`， `X`， `L`，`C`，`D` 和 `M`。

字符          数值
    I             1
    V             5
    X             10
    L             50
    C             100
    D             500
    M             1000

例如， 罗马数字 2 写做 `II` ，即为两个并列的 1。12 写做 `XII` ，即为`X + II`。 27 写做 `XXVII`, 即为 `XX + V + II` 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 `IIII`，而是`IV`。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为`IX`。这个特殊的规则只适用于以下六种情况：

*  `I`可以放在 `V`(5) 和 `X`(10) 的左边，来表示 4 和 9。
 *  `X` 可以放在 `L` (50) 和 `C` (100) 的左边，来表示 40 和 90。
 *  `C`可以放在 `D` (500) 和`M`(1000) 的左边，来表示 400 和 900。
 *  给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

**提示**：

*  `1 <= s.length <= 15`
 *  `s`仅含字符`('I', 'V', 'X', 'L', 'C', 'D', 'M')`
 *  题目数据保证`s`是一个有效的罗马数字，且表示整数在范围 \[1, 3999\] 内
 *  题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
 *  `IL` 和`IM` 这样的例子并不符合题目要求，49 应该写作 `XLIX`，999 应该写作`CMXCIX`。

【**示例**】

输入: "IX"
    输出: 9
    ---------------------
    输入: "MCMXCIV"
    输出: 1994
    解释: M = 1000, CM = 900, XC = 90, IV = 4.

【**解题思路**】

方法一：`if/else`语句

class Solution {
        
        public int romanToInt(String s) {
        
            int x = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
        
                int n = x;
                if (i > 0) {
        
                    if (s.charAt(i - 1) == 'I' && s.charAt(i) == 'V') {
        
                        x += 4;
                    } else if(s.charAt(i - 1) == 'I' && s.charAt(i) == 'X') {
        
                        x += 9;
                    } else if(s.charAt(i - 1) == 'X' && s.charAt(i) == 'L') {
        
                        x += 40;
                    } else if(s.charAt(i - 1) == 'X' && s.charAt(i) == 'C') {
        
                        x += 90;
                    } else if(s.charAt(i - 1) == 'C' && s.charAt(i) == 'D') {
        
                        x += 400;
                    } else if(s.charAt(i - 1) == 'C' && s.charAt(i) == 'M') {
        
                        x += 900;
                    }
                }
                if (n != x) {
        
                    i--;
                } else {
        
                    switch (s.charAt(i)) {
        
                        case 'I' : x += 1;    break;
                        case 'V' : x += 5;    break;
                        case 'X' : x += 10;   break;
                        case 'L' : x += 50;   break;
                        case 'C' : x += 100;  break;
                        case 'D' : x += 500;  break;
                        case 'M' : x += 1000; break;
                        default : break;
                    }
                }
            }
            return x;
        }
    }

方法二：`HashMap`

class Solution {
        
        public int romanToInt(String s) {
        
            if (s == null || s.length() == 0) {
        
                return 0;
            }
            char[] keys = {
        'I', 'V', 'X', 'L', 'C', 'D', 'M'};
            int[] vals = {
        1, 5, 10, 50, 100, 500, 1000};
            Map<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < keys.length; i++) {
        
                map.put(keys[i], vals[i]);
            }
            int res = 0;
            for (int i = 0; i < s.length(); i++) {
        
                if (i + 1 < s.length() && map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) {
        
                    res += map.get(s.charAt(i + 1)) - map.get(s.charAt(i));
                    i += 1;
                } else {
        
                    res += map.get(s.charAt(i));
                }
            }
            
            return res;
        }
    }

--------------------

### 整数转罗马数字★★ ###

[12. 整数转罗马数字][12.]

【**题目**】罗马数字包含以下七种字符： `I`， `V`， `X`， `L`，`C`，`D` 和 `M`。

字符          数值
    I             1
    V             5
    X             10
    L             50
    C             100
    D             500
    M             1000

例如， 罗马数字 2 写做 `II` ，即为两个并列的 1。12 写做 `XII` ，即为 `X + II` 。 27 写做 `XXVII`, 即为 `XX + V + II` 。通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 `IIII`，而是 `IV`。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 `IX`。这个特殊的规则只适用于以下六种情况：

*  `I` 可以放在 `V` (5) 和 `X` (10) 的左边，来表示 4 和 9。
 *  `X` 可以放在 `L` (50) 和 `C` (100) 的左边，来表示 40 和 90。
 *  `C` 可以放在 `D` (500) 和 `M` (1000) 的左边，来表示 400 和 900。
 *  给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

**提示：**

*  `1 <= num <= 3999`

【**示例**】

输入: 9
    输出: "IX"
    ----------------------------------------
    输入: 58
    输出: "LVIII"
    解释: L = 50, V = 5, III = 3.
    -----------------------------------------
    输入: 1994
    输出: "MCMXCIV"
    解释: M = 1000, CM = 900, XC = 90, IV = 4.

【**解题思路**】

建立罗马数字特殊情况的键值对，由大到小查询

class Solution {
        
        public String intToRoman(int num) {
        
            int[] keys = {
        1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
            String[] vals = {
        "M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
            StringBuffer sb = new StringBuffer();
            int e = 0;
            while (e < keys.length) {
        
                if (num >= keys[e]) {
        
                    sb.append(vals[e]);
                    num -= keys[e];
                } else {
        
                    e += 1;
                }
            }
            return sb.toString();
        }
    }

--------------------

### 第 N 位数字★★ ###

[400. 第 N 位数字][400. _ N]

【**题目**】在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …中找到第 `n` 位数字。

**注意**：`n` 是正数且在 32 位整数范围内（`n < 2^31`）。

【**示例**】

输入：11
    输出：0
    解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。

【**解题思路**】

找规律

很明显
    1 ~ 9       1 x 9
    10 ~ 99     2 x 90
    100 ~ 999   3 x 900
    ···         ···
    n位          n x 9(n-1个0)
    --------------------------
    对于一个数字n，假如为200,先找出其对应整数有几位
    200 - 1 x 9  = 191
    191 - 2 x 90 = 11
    很明显，有三位
    11 / 3 = 3···2 说明是三位数字中第4个，为 100 + 3 = 103
    余数为2，说明是103中的第二位为0

代码如下

class Solution {
        
        public int findNthDigit(int n) {
        
            int e = 0;
            for (int i = 1; i < 10; i++) {
        
                long t = i * 9 * (long)Math.pow(10, i - 1);
                if (n <= t) {
        
                    e = i;
                    break;
                }
                n -= t;
            }
            
            int d = (n % e == 0) ? (n / e - 1) : (n / e);
            int r = (n % e == 0) ? e : (n % e);
            int num = (int)Math.pow(10, e - 1) + d;
            
            return String.valueOf(num).charAt(r - 1) - '0';   
        }
    }

--------------------

### 数字 1 的个数★★★ ###

[233. 数字 1 的个数][233. _ 1]

【**题目**】给定一个整数 `n`，计算所有小于等于 `n` 的非负整数中数字 `1` 出现的个数。

**提示：**

*  `0 <= n <= 2 * 109`

【**示例**】

输入：n = 13
    输出：6

【**解题思路**】

找规律

1 ~ 9        1个1      总共1个1       1 ~ 1      1个1
    10 ~ 99      19个1     总共20个1      10 ~ 19    10个1
    100 ~ 999    280个1    总共300个1     100 ~ 199  100个1
    ···          ···       ···
    n位           ···      总共n x 10^(n - 1) 个 1
    --------------------------------------------------------

代码如下

class Solution {
        
        public int countDigitOne(int n) {
        
            if (n <= 0) {
        
                return 0;
            }
            if (n == 1) {
        
                return 1;
            }
            String sn = String.valueOf(n);
            int high = sn.charAt(0) - '0';
            int base = (sn.length() - 1) * (int)Math.pow(10, sn.length() - 2);
            int cur = (int)Math.pow(10, sn.length() - 1);
            if (high == 1) {
        
                return base + n - cur + 1 + countDigitOne(n - high * cur);
            } else {
        
                return base * high + cur + countDigitOne(n - high * cur);
            }
        }
    }

--------------------

### 森林中的兔子★★ ###

[781. 森林中的兔子][781.]

【**题目**】森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。

返回森林中兔子的最少数量。

**说明:**

1.  `answers` 的长度最大为`1000`。
2.  `answers[i]` 是在 `[0, 999]` 范围内的整数。

【**示例**】

示例:
    输入: answers = [1, 1, 2]
    输出: 5
    --------------------------------------
    输入: answers = [10, 10, 10]
    输出: 11

【**解题思路**】

值相同的兔子可以放为一组，若其值为`t`，相同值的数量为`n`，

*  若`n < t`，则当前组还有其它未加入的兔子，当前组数量应设置为最大值`t + 1`
 *  若`n >= t`，判断按最大值`t+1`可分为几组，每组数量取`t+1`即可

class Solution {
        
        public int numRabbits(int[] answers) {
        
            int[] mark = new int[1000];
            for (int answer : answers) {
        
                mark[answer]++;
            }
            int res = mark[0];
            for (int i = 1; i < 1000; i++) {
        
                if (mark[i] == 0) {
        
                    continue;
                }
                res += (mark[i] + i) / (i + 1) * (i + 1);
            }
            return res;
        }
    }

--------------------

### 直线上最多的点数★★★ ###

[149. 直线上最多的点数][149.]

【**题目**】给定一个二维平面，平面上有 *n* 个点，求最多有多少个点在同一条直线上。

【**示例**】

输入: [[1,1],[2,2],[3,3]]
    输出: 3
    解释:
    ^
    |
    |        o
    |     o
    |  o  
    +------------->
    0  1  2  3  4
    ------------------------------------------------------------------------
    输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
    输出: 4
    解释:
    ^
    |
    |  o
    |     o        o
    |        o
    |  o        o
    +------------------->
    0  1  2  3  4  5  6

【**解题思路**】

因为两点组成一条直线，双重for循环暴力查找，使用哈希表统计与当前点组成的直线斜率相同的点数个数，取最大值即可。分情况讨论，与当前点重合的点，直线斜率为0，斜率不存在，斜率为其它值等。

class Solution {
        
        public int maxPoints(int[][] points) {
        
            if (points == null || points.length == 0) {
        
                return 0;
            }
    
            Map<String, Integer> map = new HashMap<>();
            int same = 0, res = 0;
    
            for (int i = 0; i < points.length; i++) {
        
                same = 0;
                map.clear();
    
                for (int j = 0; j < points.length; j++) {
        
                    if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
        
                        same++;
                    } else if (points[i][0] == points[j][0]) {
        
                        String t = "0,-1";
                        map.put(t, map.getOrDefault(t, 0) + 1);
                    } else if (points[i][1] == points[j][1]) {
        
                        String t = "-1,0";
                        map.put(t, map.getOrDefault(t, 0) + 1);
                    } else {
        
                        int[] d = {
        points[i][0] - points[j][0], points[i][1] - points[j][1]};
                        int g = gcd(d[0], d[1]);
                        d[0] /= g;
                        d[1] /= g;
                        if (d[0] < 0) {
        
                            d[0] = -d[0];
                            d[1] = -d[1];
                        }
                        String t = d[0] + "," + d[1];
                        map.put(t, map.getOrDefault(t, 0) + 1);
                    }
                }
    
                res = Math.max(res, same);
                for (Integer val : map.values()) {
        
                    res = Math.max(res, val + same);
                }
            }
    
            return res;
        }
    
        private int gcd(int a, int b) {
        
            return b == 0 ? a : gcd(b, a % b);
        }
    
    }

--------------------

### 可怜的小猪★★★ ###

[458. 可怜的小猪][458.]

【**题目**】

有 `buckets` 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 `minutesToTest` 分钟时间来确定哪桶液体是有毒的。

喂猪的规则如下：

*  选择若干活猪进行喂养
 *  可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
 *  小猪喝完水后，必须有 `minutesToDie` 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
 *  过了 `minutesToDie` 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
 *  重复这一过程，直到时间用完。

给你桶的数目 `buckets` ，`minutesToDie` 和 `minutesToTest` ，返回在规定时间内判断哪个桶有毒所需的 最小 猪数。

【**示例**】

输入：buckets = 1000, minutesToDie = 15, minutesToTest = 60
    输出：5
    ------------------------------------------------------------
    输入：buckets = 4, minutesToDie = 15, minutesToTest = 15
    输出：2

【**解题思路**】

可测的最大次数为  
 t = m i n u t e s T o T e s t / m i n u t e T o D i e + 1 t = minutesToTest/minuteToDie +1 t=minutesToTest/minuteToDie\+1  
若现有x只猪，n个桶,则应满足  
 t x > = n t^x >= n tx>=n  
化简得  
 x > = l o g n / l o g a x>=logn/loga x>=logn/loga  
对结果向上取整

class Solution {
        
        public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        
            int t = minutesToTest / minutesToDie + 1;
            return (int)Math.ceil(Math.log(buckets) / Math.log(t));
        }
    }

> 更多解析见[官方题解][Link 2]

[LCP 29.]: https://leetcode-cn.com/problems/SNJvJP/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221020/e874fef0f343479ebdb02779358249ab.png
[Link 1]: https://leetcode-cn.com/problems/SNJvJP/solution/zhu-bu-ding-wei-by-zesunlight-tio3/
[13.]: https://leetcode-cn.com/problems/roman-to-integer/
[12.]: https://leetcode-cn.com/problems/integer-to-roman/
[400. _ N]: https://leetcode-cn.com/problems/nth-digit/
[233. _ 1]: https://leetcode-cn.com/problems/number-of-digit-one/
[781.]: https://leetcode-cn.com/problems/rabbits-in-forest/
[149.]: https://leetcode-cn.com/problems/max-points-on-a-line/
[458.]: https://leetcode-cn.com/problems/poor-pigs/
[Link 2]: https://leetcode-cn.com/problems/poor-pigs/solution/ke-lian-de-xiao-zhu-by-leetcode/