[Task Scheduler](https://leetcode.com/problems/task-scheduler/)。给一大写字母的数组，代表$26$种任务的集合。CPU任一时间片可以挑选任一任务去执行，但是同种任务的两次执行之间需要有$n$个时间片的间隔。问执行完所有任务最少需要多少时间片。如```tasks = ["A","A","A","B","B","B"]```，```n = 2```，执行时间片为：```A -> B -> idle -> A -> B -> idle -> A -> B```。

思路：首先对同种任务进行计数，同种任务之间的执行至少要间隔$n$，那么易得最短时间取决于数量最多的那种任务。易得完成$k$个同种任务至少需要$(k-1)*(n+1)+1$个时间片，若数量最多的任务有$s$种，那么至少需要$(k-1)*(n+1)+s$个时间片。


```python
def leastInterval(tasks, n: int) -> int:
    res = len(tasks)

    cnts = [0]*26
    for ch in tasks:
        cnts[ord(ch)-65] += 1
    cnts.sort(reverse=True)

    neet_t = (cnts[0]-1)*(n+1)
    for cnt in cnts:
        if cnt == cnts[0]:
            neet_t += 1

    return max(res, neet_t)
```




    8



[Fraction to Recurring Decimal](https://leetcode.com/problems/fraction-to-recurring-decimal/)。将分数转换成小数形式，当出现循环小数时，将循环部分加上括号。

思路：首先明确分数中分子为除数，分母为被除数。手动做一下除法就不难发现，当某一次的余数在之前出现过时，肯定就会出现循环小数，所以该题解法是先正常的做除法，并记录每一次余数出现的位置，当余数重复时即出现循环小数。


```python
def fractionToDecimal(numerator: int, denominator: int) -> str:
    res = '-' if numerator*denominator < 0 else ''    # 符号
    numerator, denominator = abs(numerator), abs(denominator)
    integer, remainder = divmod(numerator, denominator)    # 首个商与余数
    res += str(integer)

    if remainder:
        res += '.'
    else:
        return res

    remainder_idx = dict()    # 记录余数位置的字典
    while remainder:
        if remainder not in remainder_idx:
            remainder_idx[remainder] = len(res)
            integer, remainder = divmod(remainder*10, denominator)
            res += str(integer)
        else:
            idx = remainder_idx[remainder]
            res = '{}({})'.format(res[:idx], res[idx:])
            break

    return res
```

求倒数第$Q$个排列，**2019网易笔试题**。给$n$个自然数，然后指定其中一个排列，假设选中的是第$Q$个排列，求倒数第$Q$个排列。如$n=3$，选中排列$123$，它是第$1$个排列，那么要求倒数第$i$个排列$321$。

思路：找规律，第$Q$个排列和倒数第$Q$个排列，对应位的数字相加恰好等于$n+1$。


```python
def func(n, num):
    num = list(str(num))
    res = list()

    for bit in num:
        res.append(n+1-int(bit))

    return int(''.join(map(str, res)))
```




    321



[Beautiful Arrangement II](https://leetcode.com/problems/beautiful-arrangement-ii/)。给$n$个正整数，重排这些正整数，使得任意两相邻值的绝对差值只有$k$种取值。如$[1,2,3]$只有一种绝对差值$1$。

思路：找规律。易得```func(4,1)=[1,2,3,4]```，```func(4,2)=[4,1,2,3]```，```func(4,3)=[1,4,2,3]```。发现交替放置$k$个大小值如```[1,4,3,2]```可以构成$k-1$种差值，而令最后一种差值为$1$，顺序放置剩余的元素即可。在$[1,n]$区间设置首位双指针，若$k$为奇数，则放置$i$；若$k$为偶数则放置$j$。


```python
def constructArray(n: int, k: int):
    res = list()
    i, j = 1, n
    while i <= j:
        if k > 1:
            if k & 1:    # 奇数
                res.append(i)
                i += 1
            else:    # 偶数
                res.append(j)
                j -= 1
            k -= 1
        else:
            res.append(i)
            i += 1
    return res
```




    [6, 1, 5, 2, 3, 4]



[Number of Digit One](https://leetcode.com/problems/number-of-digit-one/)。求$[1,n]$范围内$1$出现的次数。

思路：直接取出最大值$n$，由低往高依次将每一位都置成$1$，然后判断高位与地位各有多少种取值。设由掩码$mask$提取出的数字是$idx$，有以下三种情况;
- $idx=0$，该位若要置$1$的话那么高位数字只能先减$1$，高位数字在$[0,high-1]$任取，低位数字任取，即$high\times{mask}$；
- $idx=1$，当高位数字在$[0,high-1]$时，低位数字任取，当高位数字取最大值时，低位只能在$[0,low]$里取值，即$high\times{mask}+low+1$；
- $idx>1$，高位数字可在$[0,high]$中任取，低位数字任取，即$(high+1)\times{mask}$。


```python
def countDigitOne(n: int) -> int:
    res = 0
    mask = 1

    while mask <= n:
        idx = n//mask % 10
        high = n//mask//10
        low = n % mask

        if idx == 0:
            res += high*mask
        elif idx == 1:
            res += high*mask+low+1
        else:
            res += (high+1)*mask

        mask *= 10

    return res

countDigitOne(11)
```




    4



[Nth Digit](https://leetcode.com/problems/nth-digit/)。给一自然数的顺序排序，求该字符串中的第$n$位数字。

思路：$1$位数有$9$个数字，$2$位数有$90$个数字，$3$位数有$900$个数字。按该规律$n$位数有$9\times{10}^{n-1}$个数字。


```python
def findNthDigit(n: int) -> int:
    if n < 10:
        return n

    bits = 2
    n -= 10

    while n > 9*(10**(bits-1))*bits:
        n -= 9*(10**(bits-1))*bits
        bits += 1

    start = 10**(bits-1)    # bits位数字的起点数字，1，10，100，...
    number = start+n//bits  # 第n位在哪一个数字中

    return str(number)[n % bits]
```

    1 2 10





    '0'



[Count Primes](https://leetcode.com/problems/count-primes/)。计数$n$以内的质数个数。

思路：设置一个长度为$n$的状态数组，以倍数法来标记非质数，然后对该数组求和即可。有一个数学定理，$n$以内的最大质数不会超过$\sqrt{n}$。


```python
def countPrimes(self, n: int) -> int:
    if n < 2:
        return 0

    import math
    thresh = int(math.sqrt(n))
    isPrime = [True]*n
    isPrime[0] = isPrime[1] = False    # 0,1不算质数

    for i in range(2, thresh+1):
        if isPrime[i]:
            isPrime[i*i:n:i] = [False]*len(isPrime[i*i:n:i])

    return sum(isPrime)
```




    4



[Roman to Integer](https://leetcode.com/problems/roman-to-integer/)。**2019老虎证券笔试题**。罗马数字转阿拉伯数字。

思路：找规律题。如$IV=4$而$VI=6$，若两罗马字符$ab$中$a\ge{b}$，说明$a$是正的，反之表明$a$是负的。


```python
def romanToInt(s: str) -> int:
    lookup = {'I': 1, 'V': 5, 'X': 10, 'L': 50,
              'C': 100, 'D': 500, 'M': 1000}

    res = 0
    for i in range(len(s)-1):
        if lookup[s[i]] < lookup[s[i+1]]:
            res -= lookup[s[i]]
        else:
            res += lookup[s[i]]

    return res+lookup[s[-1]]
```




    False



[Gray Code](https://leetcode.com/problems/gray-code/)。指定二进制的位数$n$，输出在该位数下的十进制格雷码序列。

思路：纯规律题。
$$
\begin{align}
n=0 \ & [0] \\
n=1 \ & [0,1] \\
n=2 \ & [00,01,11,10] \\
n=3 \ & [000,001,011,010,110,111,101,100] \\
\end{align}
$$
观察到每下一级的格雷码可以对半分成两份，前半部分与上一级数字相同，只是在高位加$0$；而后半部分则是上一级序列的逆序，然后再高位加$1$，相当于加$2^{(i-1)}$。


```python
def grayCode(n: int):
    res=[0]
    if n==0:
        return res
    
    for i in range(1,n+1):
        res.extend([item+2**(i-1) for item in res[::-1]])
        
    return res
```




    [0, 1, 3, 2]



[1-bit and 2-bit Characters](https://leetcode.com/problems/1-bit-and-2-bit-characters/)。现有两种特殊字符，第一种字符被编码成$0$，第二种字符编码成$10$和$11$。现给一编码串，判断该编码串的是否是以第一种字符结尾。

思路：两种编码有明显的区别，第一种字符编码以$0$开头，一位；第二种字符编码以$1$开头，两位。使用工作指针线性扫描字串，遇到$0$前进一位，遇到$1$前进两位，判断指针能否停在最后一位即可。


```python
def isOneBitCharacter(bits) -> bool:
    n = len(bits)
    idx = 0

    while idx < n-1:
        if bits[idx] == 0:
            idx += 1
        else:
            idx += 2

    return idx == n-1
```




    True



[Self Dividing Numbers](https://leetcode.com/problems/self-dividing-numbers/)。给定一个范围，求出范围内所有的SDN。SDN定义为能被自身中所有数字整除的数，并且SDN不允许包含0。

思路：逻辑实现题。


```python
def selfDividingNumbers(left: int, right: int):
    res=list()
    if left>right:
        return res
    
    for num in range(left,right+1):
        tmp=num
        
        while tmp:
            bit=tmp%10
            if bit==0 or num%bit!=0:
                break
            else:
                tmp//=10
                
        if tmp==0:
            res.append(num)
            
    return res
```




    [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]



判断点是否在多边形内。**2019去哪儿笔试题**。首先给出用户坐标，后跟的是多边形的点的坐标，保证顺序。判断该点是否在多边形内部。

思路：经典计算几何题，思路来源于[网上](https://www.cnblogs.com/anningwang/p/7581545.html)。由于笔试不允许使用Python，所以只测试了两个最简单的用例，不保证正确性。


```python
import sys


def func(x_u, y_u, xs, ys):
    res = False
    n = len(xs)
    i, j = 0, n - 1
    while i < n:
        if ((ys[i] > y_u) != (ys[j] > y_u)
                and (x_u < (xs[j] - xs[i]) * (y_u - ys[i]) / (ys[j] - ys[i]) + xs[i])):
            res = not res
        j = i
        i += 1

    return res


coord = sys.stdin.readline().strip().split()
x_u, y_u = list(map(float, coord[0].split(',')))
xs = list(map(float, [item.split(',')[0] for item in coord[1:]]))
ys = list(map(float, [item.split(',')[1] for item in coord[1:]]))

print(xs, ys, x_u, y_u)
print(func(x_u, y_u, xs, ys))
```

77df36b14fa98bb12518dd50ee3419f683e29fcb
ipynb
Jupyter Notebook
Algorithm/OnlineExam/Python/Math.ipynb
Daya-Jin/DataStructureAndAlgorithm
212e53e255f103fcf0471bdf9422fd306f3745b5
MIT
2019-03-07T03:19:54.000Z
2019-08-22T08:12:41.000Z
Algorithm/OnlineExam/Python/Math.ipynb
Daya-Jin/DataStructureAndAlgorithm
212e53e255f103fcf0471bdf9422fd306f3745b5
MIT
Algorithm/OnlineExam/Python/Math.ipynb
Daya-Jin/DataStructureAndAlgorithm
212e53e255f103fcf0471bdf9422fd306f3745b5
MIT
Qwen/Qwen-72B
1. YES
2. YES