Given an integer array queries
and a positive integer intLength
, return an array answer
where answer[i]
is either the queries[i]th
smallest positive palindrome of length intLength
or -1
if no such palindrome exists.
A palindrome is a number that reads the same backwards and forwards. Palindromes cannot have leading zeros.
Example 1:
Input: queries = [1,2,3,4,5,90], intLength = 3 Output: [101,111,121,131,141,999] Explanation: The first few palindromes of length 3 are: 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ... The 90th palindrome of length 3 is 999.
Example 2:
Input: queries = [2,4,6], intLength = 4 Output: [1111,1331,1551] Explanation: The first six palindromes of length 4 are: 1001, 1111, 1221, 1331, 1441, and 1551.
Constraints:
1 <= queries.length <= 5 * 104
1 <= queries[i] <= 109
1 <= intLength <= 15
Solution: Math
For even length e.g. 4, we work with length / 2, e.g. 2. Numbers: 10, 11, 12, …, 99, starting from 10, ends with 99, which consist of 99 – 10 + 1 = 90 numbers. For the x-th number, e.g. 88, the left part is 10 + 88 – 1 = 97, just mirror it o get the palindrome. 97|79. Thus we can answer a query in O(k/2) time which is critical.
For odd length e.g. 3 we work with length / 2 + 1, e.g. 2, Numbers: 10, 11, 12, 99. Drop the last digit and mirror the left part to get the palindrome. 101, 111, 121, …, 999.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: vector<long long> kthPalindrome(vector<int>& queries, int k) { long long s = pow(10, (k + 1) / 2 - 1); long long e = s * 10; auto gen = [](long long x, bool isOdd) { long long ans = x; for (long long c = isOdd ? x / 10 : x; c; c /= 10) ans = ans * 10 + c % 10; return ans; }; vector<long long> ans; for (int q : queries) ans.push_back(q > e - s ? -1 : gen(s + q - 1, k & 1)); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment