[ZigZag Conversion](https://leetcode.com/problems/zigzag-conversion/)。之字形变换，给一字符串与行数，求该字串按之字形排列后的每行输出。如```PAYPALISHIRING```按四行排列：
```
P     I    N
A   L S  I G
Y A   H R
P     I
```
行输出为：```PINALSIGYAHRPI```。

思路：就是一个观察规律的问题，从转换后的模式来看，行的重复周期是$2rows-2$，第一行的字母对应着原字串的```i*(2rows-2)```，最后一行字母与第一行字母同理，不过有一个```rows-1```的offset。如首行```P```的下一个字母为```I```，那么加上一个周期长度$6$即可得到；而尾行的```P```下一个字母为```I```，同样加上一个周期长度$6$即可得到。难点在于中间的对应关系。中间行的一个周期内出现两个字母，如第二行的```A```下一个字母是```L```，如果加上一个周期长度的话只会得到```S```，所以需要做修正：再减去两倍所在行数。


```python
def convert(s: str, numRows: int) -> str:
    if numRows < 2 or len(s) < 2:
        return s

    res = list()
    len_clc = 2*numRows-2    # 周期长度
    len_s = len(s)

    for row in range(numRows):
        idx = row
        while idx < len_s:
            res.append(s[idx])
            
            if row != 0 and row != numRows-1:    # 非首尾行还要额外加字母
                ex_idx = idx+len_clc-2*row
                if ex_idx < len_s:
                    res.append(s[ex_idx])
                    
            idx += len_clc

    return ''.join(res)
```




    'PINALSIGYAHRPI'



[Add Strings](https://leetcode.com/problems/add-strings/)。字符串形式的整数相加，不允许使用整形转换。

思路：不允许使用整形转换，肯定只能使用ASCII码来进行运算。由低往高诸位相加，每次将一位加到res上去，注意进位即可。


```python
def addStrings(num1: str, num2: str) -> str:
    # ord('0')=48, ord('9')=57
    p1, p2 = len(num1)-1, len(num2)-1
    res = str()
    carry = 0

    while p1 >= 0 or p2 >= 0:
        bit1 = num1[p1] if p1 >= 0 else '0'
        bit2 = num2[p2] if p2 >= 0 else '0'

        cur_sum = ord(bit1)-48+ord(bit2)-48+carry
        if cur_sum > 9:
            carry = 1
            cur_sum -= 10
        else:
            carry = 0

        res += str(cur_sum)

        p1 -= 1
        p2 -= 1

    if carry:
        res += str(carry)

    return res[::-1]


addStrings('408', '5')
```




    '413'



[Optimal Division](https://leetcode.com/problems/optimal-division/)。最优除法顺序，给一数组，数字之间全是除法运算，求一个除法顺序使得最终结果最大。

思路：当数字超过$3$个时，在最后两数字加上一个括号$a/(b/c)$，相当于把$c$转换成了乘数；当数字更多时，把后面的数字全用括号括起来，相当于把它们全部变成了乘数。


```python
def optimalDivision(nums) -> str:
    if len(nums) < 2:
        return str(nums[0])
    elif len(nums) < 3:
        return '/'.join(map(str, nums))
    else:
        return str(nums[0])+'/('+'/'.join(map(str, nums[1:]))+')'
```

[Maximum Sum Circular Subarray](https://leetcode.com/problems/maximum-sum-circular-subarray/)。设定一个循环数组，求该数组内能得到的最大累计和。

思路：仔细思考，如果最大连续和跨首尾的话，说明数组中必定有负数。最大连续和与最小连续和肯定不会同时跨首尾，即是说如果把数组看成是非循环的，至少能求出最大连续和与最小连续和之中的一个。然后用数组和减去最小连续和得到一个备选最大连续和。返回两个最大连续和的最大者即可。难点在于处理全是负数的情况，设置一个标志位即可。


```python
def maxSubarraySumCircular(A) -> int:
    cur_max = cur_min = 0
    max_sum = min_sum = A[0]

    all_Neg = True    # 全负标志

    for num in A:
        if num > 0:
            all_Neg = False

        cur_max += num
        max_sum = max(max_sum, cur_max)
        if cur_max < 0:
            cur_max = 0

        cur_min += num
        min_sum = min(min_sum, cur_min)
        if cur_min > 0:
            cur_min = 0

    if all_Neg:
        return max(A)

    return max(max_sum, sum(A)-min_sum)


maxSubarraySumCircular([-1, -2, -3])
```




    -1



[Super Pow](https://leetcode.com/problems/super-pow/)。大数取模，给定一个底数$a$，幂数$b$以字串形式给出。求$a^{b}\%1337$的值。

思路：取出幂数的首位```b[0]```，计算$a^{b[0]}\%1337$得到```res```，若幂数存在下一位，则下次计算$res^{10}*a^{b[1]}\%1337$。以此计算，得到最后的```res```即为答案。


```python
def superPow(a: int, b) -> int:
    len_b = len(b)

    res = a**b[0] % 1337

    for i in range(1, len_b):
        res = (res**10)*(a**b[i]) % 1337

    return res
```




    1024



[Beautiful Array](https://leetcode.com/problems/beautiful-array/)。指定一个连续正数序列的长度，将其变序，求出任意一个漂亮数组。即对于任意位置的$i<k<j$，都有$A[k]*2!=A[i]*A[j]$。

思路：首先搞懂题目意思，$A[k]*2$肯定是偶数，最简单的情况，令$A[k]$左边都是奇数，$A[k]$右边都是偶数，那么不可能有$A[k]*2=A[i]*A[j]$。然后有如下几个性质：若$A$是漂亮数组，则$2*A-1$(奇数)与$2*A$(偶数)均是漂亮数组。那么以最小的数组$[1]$出发，可以每次将漂亮数组翻倍，直到得到长度为$n$的漂亮数组。


```python
def beautifulArray(N: int):
    res = [1]

    while len(res) < N:
        res = [2*num-1 for num in res]+[2*num for num in res]

    return [num for num in res if num <= N]    # 删掉超出范围的数字
```

[Rotate Function](https://leetcode.com/problems/rotate-function/)。给一个长度为$n$的数组，令$F(0)=0*arr[0]+1*arr[1]+...+(n-1)arr[n-1]$，将数组循环右移一位，得$F(1)=0*arr[n-1]+1*arr[0]+..+(n-1)arr[n-2]$。求$F(k)$的最大值，其中$k\in{[0,n-1]}$。

思路：找规律。
$$
\begin{align}
sum&=arr[0]+arr[1]+...+arr[n-1] \\
F(0)&=0*arr[0]+1*arr[1]+...+(n-1)arr[n-1] \\
F(1)&=0*arr[n-1]+1*arr[0]+...+(n-1)arr[n-2] \\
&=F(0)+sum-n*arr[n-1] \\
F(2)&=0*arr[n-2]+1*arr[n-1]+...+(n-1)arr[n-3] \\
&=F(1)+sum-n*arr[n-2] \\
F(k)&=F(k-1)+sum-n*arr[n-k] \\
\end{align}
$$


```python
def maxRotateFunction(A) -> int:
    sum_A = sum(A)
    n = len(A)

    F = sum([idx*num for idx, num in enumerate(A)])    # F(0)
    res = F
    for k in range(1, n):
        F += sum_A-n*A[n-k]
        res = max(res, F)

    return res
```




    26



[Water and Jug Problem](https://leetcode.com/problems/water-and-jug-problem/)。量水问题，给两个容积$x$与$y$的桶，判断是否能量出容积为$z$的水。

思路：数学问题。$z$需要满足的条件有两个，一是$x$和$y$最大公约数的倍数，二是不超过$x$和$y$的容积和，难点在于要考虑各种不规范的测试用例。记住，背后思路暂没去弄懂。


```python
def canMeasureWater(x: int, y: int, z: int) -> bool:
    def gcd(x, y):
        '''
        辗转相除法求最大公约数
        '''
        while y:
            x, y = y, x % y
        return x

    if z == 0:
        return True
    if x == z or y == z or x+y == z:
        return True
    if x == 0 or y == 0:
        return x == z or y == z

    return z % gcd(x, y) == 0 and z <= x+y
```




    False



[Valid Square](https://leetcode.com/problems/valid-square/)。给四个坐标，判断是否构成正方形。

思路：因为输入只有四个二维坐标，所以方法有很多种。这里使用的方法如下：正方形任一点到最近两点的距离一定相等，且所有点到最近点的距离都相等。


```python
def validSquare(p1, p2, p3, p4) -> bool:
    edge = set()    # 边长，正方形只有一种边长
    points = [p1, p2, p3, p4]

    if len(set(map(tuple, points))) < 4:    # 如果点有重合
        return False

    for cur_p in points:
        # 任一点到其他三个点的距离
        dist = set([((cur_p[0]-p[0])**2+(cur_p[1]-p[1])**2) ** 0.5
                    for p in points if p != cur_p])
        if len(dist) > 2:
            return False

        edge.add(min(dist))
        if len(edge) > 1:
            return False

    return True
```




    True



[Rectangle Overlap](https://leetcode.com/problems/rectangle-overlap/)。矩阵判重，矩阵由左下角右上角坐标来定位。

思路：求出左下角LD的最大值，右上角RU的最小值。只有当LR的横纵坐标都小于RU的横纵坐标时两矩阵才没有重叠。


```python
def isRectangleOverlap(rec1, rec2) -> bool:
    ld_1, ru_1 = (rec1[0], rec1[1]), (rec1[2], rec1[3])
    ld_2, ru_2 = (rec2[0], rec2[1]), (rec2[2], rec2[3])

    ld_overlap = (max(ld_1[0], ld_2[0]), max(ld_1[1], ld_2[1]))
    ru_overlap = (min(ru_1[0], ru_2[0]), min(ru_1[1], ru_2[1]))

    return True if ld_overlap[0] < ru_overlap[0] and ld_overlap[1] < ru_overlap[1] else False
```




    False



[Rectangle Area](https://leetcode.com/problems/rectangle-area/)。给两个矩形，求总面积。矩形的位置由左下角与右上角坐标定位。

思路：难点在于考虑所有重叠的情况。


```python
def computeArea(A: int, B: int, C: int, D: int, E: int, F: int, G: int, H: int) -> int:
    ld_1, ru_1, ld_2, ru_2 = (A, B), (C, D), (E, F), (G, H)

    # 求两矩形的面积和
    res = (ru_1[0]-ld_1[0])*(ru_1[1]-ld_1[1])  \
        + (ru_2[0]-ld_2[0])*(ru_2[1]-ld_2[1])

    # 重叠坐标
    ld_overlap = (max(ld_1[0], ld_2[0]), max(ld_1[1], ld_2[1]))
    ru_overlap = (min(ru_1[0], ru_2[0]), min(ru_1[1], ru_2[1]))

    # 判断是否重叠
    if ld_overlap[0] < ru_overlap[0] and ld_overlap[1] < ru_overlap[1]:
        res -= (ru_overlap[0]-ld_overlap[0])*(ru_overlap[1]-ld_overlap[1])

    return res
```




    45



[Count Numbers with Unique Digits](https://leetcode.com/problems/count-numbers-with-unique-digits/)。指定最大值为$10^{n}$，求区间$[0,10^{n})$内所有数里面不含重复数字的个数。

思路：首先考虑特殊情况，$1$位数时答案为$10$个数；两位数时，首位可$[1-9]$任取，第二位可取$0$，也是$9$种选择，所以答案是$10+9\times{9}=81$；若有第三位时，则只有$8$种选择，即$10+9\times{9}+9\times{9}\times{8}$；...。易得当位数大于$10$时，就不可能再存在不含重复数字的数了，程序可以直接返回。


```python
def countNumbersWithUniqueDigits(n: int) -> int:
    if n == 0:
        return 1
    if n == 1:
        return 10

    n_cur = 9    # 多位数下的当前位取值可能数
    res = 10    # 累计可能取值数
    for i in range(2, min(10+1, n+1)):    # i最大取到10
        n_cur *= 9-i+2    # 增加一位时多出的数字
        res += n_cur    # 加和

    return res
```




    739




```python

```

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