Nth Digit题目描述代码实现Happy Number题目描述代码实现Binary Tree Paths题目描述代码实现
Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …
Note: n is positive and will fit within the range of a 32-bit signed integer (n < 231).
Example 1:
Input:3Output:3Example 2:Input:11Output:0Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … is a 0, which is part of the number 10.
还有人的方法和我很像：
class Solution {public: int findNthDigit(int n) { // step 1. calculate how many digits the number has. long base = 9, digits = 1; while (n - base * digits > 0) { n -= base * digits; base *= 10; digits ++; } // step 2. calculate what the muber is. int index = n % digits; if (index == 0) index = digits; long num = 1; for (int i = 1; i < digits; i ++) num *= 10; num += (index == digits) ? n / digits - 1 : n / digits;; // step 3. find out which digit in the number is we want. for (int i = index; i < digits; i ++) num /= 10; return num % 10; }};Write an algorithm to determine if a number is “happy”.
A happy number is a number defined by the following PRocess: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number
在这里需要注意的是使用inline内联函数以后速度有了很大的提高。
C++中使用stringstream进行数字字符串的转化以及stringstream的使用： 1、stringstream的清空：http://blog.csdn.net/u012954083/article/details/23483619 2、数字字符串之间的转换：http://www.cnblogs.com/luxiaoxun/archive/2012/08/03/2621803.html 3、stringstream数字字符串之间转换：http://blog.csdn.net/touzani/article/details/1623850/
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1 / /2 3 / 5All root-to-leaf paths are:
["1->2->5", "1->3"]还有这样的递归方法：
void binaryTreePaths(vector<string>& result, TreeNode* root, string t) { if(!root->left && !root->right) { result.push_back(t); return; } if(root->left) binaryTreePaths(result, root->left, t + "->" + to_string(root->left->val)); if(root->right) binaryTreePaths(result, root->right, t + "->" + to_string(root->right->val));}vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; if(!root) return result; binaryTreePaths(result, root, to_string(root->val)); return result;}还有BFS的方法：
class Solution {public: vector<string> binaryTreePaths(TreeNode* root) { queue<pair<int, TreeNode*>> q; vector<string> path; vector<string> res; path.push_back(""); if(!root) return res; q.push({0, root}); while(!q.empty()){ auto p = q.front(); q.pop(); string s = path[p.first]; s = s==""? to_string(p.second->val) : s + "->" + to_string(p.second->val); if(!p.second->left && !p.second->right) res.push_back(s); else{ path.push_back(s); if(p.second->left) q.push({path.size()-1, p.second->left}); if(p.second->right) q.push({path.size()-1, p.second->right}); } } return res; }};新闻热点
疑难解答
