Script Note

import sys

import re

from itertools import combinations_with_replacement as rcb

from itertools import combinations as cb

if __name__ == '__main__':

    all_vt = set()

    group_list = {}

    i = 0

    with open('vt.txt') as f:

        lines = f.readlines()

    for line in lines:

        group_list[i] = {}

        p_list = []

        n_list = []

        for l in str(line).split():

            if re.search('P', l):

                p_list.append(l)

            else:

                n_list.append(l)

            all_vt.add(l)

        group_list[i]['P'] = p_list

        group_list[i]['N'] = n_list

        i = i + 1

    print(group_list)

    for vt in all_vt:

        vt_type = 'P'

        adj_type = 'N'

        if re.search('N', vt):

            vt_type = 'N'

            adj_type = 'P'

        adj_vt = re.sub(vt_type, adj_type, vt)

        for key in group_list:

            print(group_list[key])

            group = group_list[key]

            if adj_vt not in group[adj_type]:

                continue

            if vt in group[vt_type]:

                continue

            risk_types = list(rcb(group[vt_type], 2))

            for risk_type in risk_types:

                if vt in risk_type:

                    continue

                if re.sub(vt_type, adj_type, risk_type[0]) in group[adj_type] and re.sub(vt_type, adj_type, risk_type[1]) in group[adj_type]:

                    continue

                print("Violate Group: ", adj_vt, risk_type)

LeetCode 258. Add Digits [Easy] [C++] 解題筆記

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

 

Example 1:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

Example 2:

Input: num = 0
Output: 0

想法:

    這題就是直接照著題目給的方式實作就好，問題是 follow up 要求用 O(1) 的時間來完成。

老實說 i have no idea，看了別人的作法原來是要用數學解阿! 原來題目描述的這個東西叫做 Digital root，

我們可以用 num mod 9 來檢查 num 的 digital root 是多少。舉例而言 12345 可以拆解為:

12345 = 1 x 10000 + 2 x 1000 + 3 x 100 + 4 x 10 + 5 = 1 x (9999 + 1) + 2 x (999 + 1) + 3 x (99 + 1) + 4 x (9 + 1) + 5

= (1 x 9999 + 2 x 999 + 3 x 99 + 4 x 9) + (1 + 2 + 3 + 4 + 5) 

可以看出前面的括弧可以被 9 整除，因此 12345 除以 9 的餘數就會來自後面的括弧剛好就是 digital root 的定義(所以位數相加且<10)

所以 num 的 digital root 就會等於 num % 9 唯一的例外是 9，其實也不算是例外，只是說在 mod 9 中 9 剛好是等於 0的

因此遇到 num % 9 == 0 時需要把結果替換成 9。

完整程式碼:

解法一:

class Solution {
public:
    int addDigits(int num) {
        int sum = num;
        while (num >= 10) {
            sum = 0;
            while (num) {
                sum += num % 10;
                num = num / 10;
            }
            num = sum;
        }
        return sum;
    }
};

解法二(數學解):

class Solution {
public:
    int addDigits(int num) {
        if (num == 0) { return 0; }
        if (num % 9 == 0) { return 9; }
        return num % 9;
    }
};