357. Count Numbers with Unique Digits
with count unique Numbers digits
2023-09-11 14:22:45 时间
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example:
Input: 2
Output: 91
Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100,
excluding 11, 22, 33, 44, 55, 66, 77, 88, 99
Approach #1: Math. [C++]
class Solution { public: int countNumbersWithUniqueDigits(int n) { if (n == 0) return 1; if (n == 1) return 10; int ans = 10; int count = 9; int temp = 9; while (n > 1 && count > 0) { temp = temp * count; ans += temp; count--; n--; } return ans; } };
Analysis:
f(1) = 10;
f(2) = f(1) + 9 * 9; xy: x: can be 1, 2.....8, 9. y: can't be the same as with x but it can be 0, so there are 9 difference kinds choise.
f(2) = f(2) + 9 * 9 * 8;
Approach #2: backtracking. [C++]
public class Solution { public static int countNumbersWithUniqueDigits(int n) { if (n > 10) { return countNumbersWithUniqueDigits(10); } int count = 1; // x == 0 long max = (long) Math.pow(10, n); boolean[] used = new boolean[10]; for (int i = 1; i < 10; i++) { used[i] = true; count += search(i, max, used); used[i] = false; } return count; } private static int search(long prev, long max, boolean[] used) { int count = 0; if (prev < max) { count += 1; } else { return count; } for (int i = 0; i < 10; i++) { if (!used[i]) { used[i] = true; long cur = 10 * prev + i; count += search(cur, max, used); used[i] = false; } } return count; } }
相关文章
- 卡尔曼滤波—Simple Kalman Filter for 2D tracking with OpenCV
- [Express 5] Create a express 5 application with node 14
- [Algorithm] Count occurrences of a number in a sorted array with duplicates using Binary Search
- [Python] Indexing An Array With Another Array with numpy
- [ES2017] Iterate over properties of an object with ES2017 Object.entries()
- [Grunt] Minifying your output with grunt-uglify
- [VSCode] Create a sharable code snippet image with Polacode extension
- [PostCss] Easily Load Google Fonts with PostCSS Font Magician
- [Poi] Build and Analyze Your JavaScript Bundles with Poi
- [React Intl] Render Content with Placeholders using react-intl FormattedMessage
- [React] Recompose: Theme React Components Live with Context
- [Javascript] Manipulate the DOM with the classList API
- [Whole Web, Node.js PM2] Loggin with PM2
- 已解决otherwise you may silence this warning and allow it anyway with ‘–trusted-host mirrors.aliyun.com
- ERROR 3009 (HY000): Column count of mysql.user is wrong. Expected 45, found 43. Created with MySQL 5
- 地平线模型转换报错 ERROR The opset version of th..., only model with opset_version 10/11 is supported.