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.find(val) != visited.end()) { return -1; } int left = -1, right = -1; count++; visited.insert(val); if (val > 0) { left = backtracking(count, val - 1, target, visited); } if (val <= target * 2) { right = backtracking(count, val * 2, target, visited); } visited.erase(val); if (left != -1 && right != -1) { return min(left, right); } else if (left != -1) { return left; } return right; } }; Change target to startValue class Solution { public: int brokenCalc(int startValue, int target) { int r = 0; while (target > startValue) { target = target % 2 > 0 ? target + 1 : target / 2; r++; } return r + startValue - target; } };

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.append(roman[i]); } } } return 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 != x / rd % 10) { return false; } ld /= 10; rd *= 10; } return true; } };