Math

tags: Math,backtracking,LeetCode101 Backtracking and stack overflow Intuition: We can abstract all the operations to a Tree, then apply DFS on it. For example: startValue=2, target=3, the tree looks like: /* 2 /\ / \ / \ 1(-1) 4(x2) /\ /\--+ / \ / \ 0(-1) 2(x2) 3(-1) 8(x2) */ class Solution { public: int brokenCalc(int startValue, int target) { unordered_set<int> visited; return backtracking(0, startValue, target, visited); } int backtracking(int count, int val, int target, unordered_set<int> & visited) { if (val == target) { return count; } if (visited....

tags: Math,Hash Table,LeetCode101 class Solution { public: string intToRoman(int num) { vector<string> roman {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; vector<int> integers {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }; string r; int times = 0; for (int i = 0; i < integers.size(); ++i) { if (num >= integers[i]) { times = num / integers[i]; num -= times * integers[i]; for (int j = times; j > 0; --j) { r....

tags: LeetCode101,Math The key idea is: To use \(log10(10^n) = n\) to get how many digits in the number. Then we need iterate \(n + 1\) times to compare each side. The digit in the left is \(\frac{x}{10^{n-i}} \mod 10\). The digit in the right is \(\frac{x}{10^i} \mod 10\). class Solution { public: bool isPalindrome(int x) { if (x < 0) { return false; } // failed at here if (x < 10) { return true; } int n = log10(x); int ld = pow(10, n); // left div int rd = 1; // right div for (int i = 0; i < (n + 1) / 2; i++) { // left right if (x / ld % 10 !...