打卡记录

Collapsing Strings（Trie树）

链接

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e6 + 10;
int son[N][26], idx, cnt1[N], cnt2[N];
int main()
{
	auto insert = [&](string& str, int* cnt) {
		int p = 0;
		for (int i = 0; i < str.size(); ++i)
		{
			int u = str[i] - 'a';
			if (!son[p][u]) son[p][u] = ++idx;
			p = son[p][u];
			cnt[p]++;
		}
	};
	int n = 0;
	long long ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;
		insert(s, cnt1);
		reverse(s.begin(), s.end());
		insert(s, cnt2);
		ans += 2ll * n * s.length();
	}
	for (int i = 1; i <= idx; i++)  ans -= 2ll * cnt1[i] * cnt2[i];
	cout << ans;
}

第 N 位数字（数学规律）

链接

class Solution:
    def findNthDigit(self, n: int) -> int:
        count, digit, start = 9, 1, 1
        while n > count:
            n -= count
            digit += 1
            start *= 10
            count = start * 9 * digit
        num = start + (n - 1) // digit
        return int(str(num)[(n - 1) % digit])