树的代码
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
代码一 自己写的 5%
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
TreeNode t1;
TreeNode t2;
Stack<TreeNode> s1 = new Stack<TreeNode>();
Stack<TreeNode> s2 = new Stack<TreeNode>();
s1.push(root.left);
s2.push(root.right);
while (!(s1.isEmpty() || s2.isEmpty())) {
t1 = s1.pop();
t2 = s2.pop();
if (t1 == null && t2 == null) continue;
if (t1 == null && t2 != null || t1 != null && t2 == null) return false;
if (t1.val == t2.val) {
s1.push(t1.left);
s1.push(t1.right);
s2.push(t2.right);
s2.push(t2.left);
}else return false;
}
if (s1.isEmpty() && !s2.isEmpty() || s2.isEmpty() && !s1.isEmpty()) return false;
return true;
}
代码二 精简版
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> q = new LinkedList<TreeNode>();
if (root == null) return true;
q.add(root.left);
q.add(root.right);
while (q.size() > 1) {
TreeNode left = q.poll(), right = q.poll();
if (left == null && right == null) continue;
if (left == null ^ right == null) return false;
if (left.val != right.val) return false;
q.add(left.left);
q.add(right.right);
q.add(left.right);
q.add(right.left);
}
return true;
}
代码三 递归
public boolean isSymmetric(TreeNode root) {
return root==null || isSymmetricHelp(root.left, root.right);
}
private boolean isSymmetricHelp(TreeNode t1, TreeNode t2) {
if (t1 == null || t2 == null) return t1 == t2;
if (t1.val != t2.val) return false;
return isSymmetricHelp(t1.left, t2.right) && isSymmetricHelp(t1.right, t2.left);
}
104. Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
代码一 自己写的
public int maxDepth(TreeNode root) {
return bfs(root, 0);
}
int bfs(TreeNode node, int depth) {
if (node == null) return depth;
return Math.max(bfs(node.left, depth + 1), bfs(node.right, depth + 1));
}
代码二 精简版 16%
思维还是跟不上迭代的精髓，根本不需要一个变量去传递depth
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
111. Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
public int minDepth(TreeNode root) {
if (root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
}
102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> re=new LinkedList<List<Integer>>();
if(root==null) return re;
Queue<TreeNode> queue=new ArrayDeque<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
int size=queue.size();
List<Integer> list=new ArrayList<Integer>();
for(int i=0;i<size;i++){
TreeNode node=queue.poll();
list.add(node.val);
if(node.left!=null) queue.add(node.left);
if(node.right!=null) queue.add(node.right);
}
re.add(list);
}
return re;
}
103. Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
代码一 3%
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> re = new LinkedList<List<Integer>>();
if (root == null) return re;
Stack<TreeNode> stack= new Stack<TreeNode>();
Stack<TreeNode> next= new Stack<TreeNode>();
stack.push(root);
boolean flag = true;
while (!stack.isEmpty()) {
int size = stack.size();
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode node = stack.pop();
list.add(node.val);
if (flag) {
if (node.left != null) next.push(node.left);
if (node.right != null) next.push(node.right);
} else {
if (node.right != null) next.push(node.right);
if (node.left != null) next.push(node.left);
}
}
stack=next;
next= new Stack<TreeNode>();
flag = !flag;
re.add(list);
}
return re;
}
代码二 40%
从左到右遍历就可以了，只是在做list的时候反向插入即可。
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> re=new LinkedList<List<Integer>>();
if(root==null) return re;
Queue<TreeNode> queue=new ArrayDeque<TreeNode>();
queue.add(root);
boolean flag = true;
while(!queue.isEmpty()){
int size=queue.size();
List<Integer> list=new ArrayList<Integer>();
for(int i=0;i<size;i++){
TreeNode node=queue.poll();
if(flag) list.add(node.val);
else list.add(0, node.val);
if(node.left!=null) queue.add(node.left);
if(node.right!=null) queue.add(node.right);
}
flag!=flag;
re.add(list);
}
return re;
}
105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
代码一 75%
http://blog.csdn.net/crazy1235/article/details/51559645
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, inorder, 0, 0, inorder.length - 1);
}
public TreeNode build(int[] preorder, int[] inorder, int preIndex, int startInIndex, int endInIndex) {
if (startInIndex > endInIndex) return null;
int index = getIndexInInorder(inorder, preorder[preIndex]);
int LenL = index - startInIndex;
int LenR = endInIndex - index;
TreeNode node = new TreeNode(preorder[preIndex]);
if (LenL > 0) node.left = build(preorder, inorder, preIndex + 1, startInIndex, index - 1);
if (LenR > 0) node.right = build(preorder, inorder, preIndex + LenL + 1, index + 1, endInIndex);
return node;
}
public int getIndexInInorder(int[] inorder, int val) {
for (int i = 0; i < inorder.length; i++) {
if (val == inorder[i]) {
return i;
}
}
return -1;
}
108. Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
代码一：递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length==0) return null;
TreeNode head=build(nums,0,nums.length-1);
return head;
}
TreeNode build(int[] nums, int lo, int hi){
if( lo > hi ) return null;
int mid = ( lo + hi ) / 2;
TreeNode node = new TreeNode( nums[mid] );
node.left = build( nums, lo, mid-1 );
node.right = build( nums, mid + 1, hi );
return node;
}
代码二：非递归
public TreeNode sortedArrayToBST(int[] nums) {
int len = nums.length;
if ( len == 0 ) { return null; }
// 0 as a placeholder
TreeNode head = new TreeNode(0);
Deque<TreeNode> nodeStack = new LinkedList<TreeNode>() {{ push(head); }};
Deque<Integer> leftIndexStack = new LinkedList<Integer>() {{ push(0); }};
Deque<Integer> rightIndexStack = new LinkedList<Integer>() {{ push(len-1); }};
while ( !nodeStack.isEmpty() ) {
TreeNode currNode = nodeStack.pop();
int left = leftIndexStack.pop();
int right = rightIndexStack.pop();
int mid = left + (right-left)/2; // avoid overflow
currNode.val = nums[mid];
if ( left <= mid-1 ) {
currNode.left = new TreeNode(0);
nodeStack.push(currNode.left);
leftIndexStack.push(left);
rightIndexStack.push(mid-1);
}
if ( mid+1 <= right ) {
currNode.right = new TreeNode(0);
nodeStack.push(currNode.right);
leftIndexStack.push(mid+1);
rightIndexStack.push(right);
}
}
return head;
}
109. Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
造树，和上面的区别是没办法通过索引直接获得了。
代码一 递归
自顶向上
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head==null) return null;
ListNode slow=head;
ListNode fast=head;
ListNode prev=null;
while(fast!=null && fast.next!=null){
prev=slow;
slow=slow.next;
fast=fast.next.next;
}
TreeNode root=new TreeNode(slow.val);
if(prev!=null){
prev.next=null;
}else
head=null;
root.left=sortedListToBST(head);
root.right=sortedListToBST(slow.next);
return root;
}
}
代码二 递归
中序遍历（待探究） 自底向上
左结点，根，右结点
private ListNode node;
public TreeNode sortedListToBST(ListNode head) {
if(head == null){
return null;
}
int size = 0;
ListNode runner = head;
node = head;
while(runner != null){
runner = runner.next;
size ++;
}
return inorderHelper(0, size - 1);
}
public TreeNode inorderHelper(int start, int end){
if(start > end){
return null;
}
int mid = start + (end - start) / 2;
TreeNode left = inorderHelper(start, mid - 1);
treenode.left = left;
TreeNode treenode = new TreeNode(node.val);
node = node.next;
TreeNode right = inorderHelper(mid + 1, end);
treenode.right = right;
return treenode;
}
114. Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
代码一 从左向右
- 如果当前结点为叶结点，则返回该结点
- 如果左子树不为空，给左子树排序，找到左子树的最右下点node，node.right=右子树，继续给右子树排序。
- 如果左子树为空。（有可能它是整个左子树的一部分），返回该左子树的最右下端。
public void flatten(TreeNode root) {
if(root ==null) return;
dfs(root);
}
TreeNode dfs(TreeNode root){
if(root.left==null && root.right==null) return root;
if(root.left==null) {
return dfs(root.right);
}
TreeNode node=dfs(root.left);
node.right=root.right;
root.right=root.left;
root.left=null;
return dfs(root.right);
}
代码二 精简版
从右到左，从下到上
private TreeNode prev = null;
public void flatten(TreeNode root) {
if (root == null)
return;
flatten(root.right);
flatten(root.left);
root.right = prev;
root.left = null;
prev = root;
}
129. Sum Root to Leaf Numbers
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
public int sumNumbers(TreeNode root) {
return dfs(root,0);
}
int dfs(TreeNode node, int val){
if(node==null) return 0;
int sum=10*val+node.val;
if(node.left==null && node.right==null) return sum;
return dfs(node.left,sum)+dfs(node.right,sum);
}
112. Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
代码一 自己写的
左右枝一片混乱
一直在犯同一个错误，如果左枝为空，并不能通过左枝来判断，因为左枝根本不是叶结点！！！，应该只看右枝； 同样地，如果右枝为空，只看左枝。
public boolean dfs(TreeNode root, int sum) {
if(root==null) return sum==0;
if(root.left!=null ) {//如果左枝不为空
boolean flag=dfs(root.left, sum-root.val); //看一眼
if(flag) return true; //如果找到了直接返回
else if (root.right!=null){//如果右枝不为空
return dfs(root.right,sum-root.val); //返回右枝
}else return false;//如果右枝为空，则根本不用看右枝了
}
return dfs(root.right, sum-root.val); //如果左枝为空，则看右枝
}
代码二 人家写的，如此简洁
我是到空了，再判断。
人家是在父结点判断即可。如果左右枝都为空，直接判断，不再往下走。
想法和Q129一样的，我自己傻掉了。再巩固，学习。
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null) return false;
if(root.left == null && root.right == null && sum - root.val == 0) return true;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
113. Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
代码一 15%
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> re = new LinkedList<List<Integer>>();
dfs(re,new ArrayList<Integer>(),root,sum);
return re;
}
void dfs(List<List<Integer>> re,List<Integer> list, TreeNode node, int sum){
if(node==null) return;
int n=node.val;
List<Integer> newList=new ArrayList<Integer>(list);
newList.add(n);
if(node.left==null && node.right==null){
if(sum==n){
re.add(newList);
}
else return;
}
dfs(re, newList,node.left,sum-n);
dfs(re, newList,node.right,sum-n);
}
代码二 48%
微调整，不是每次重新创立新的list，而是在最后的时候remove就可以了
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> re = new LinkedList<List<Integer>>();
dfs(re, new ArrayList<Integer>(), root, sum);
return re;
}
void dfs(List<List<Integer>> re, List<Integer> list, TreeNode node, int sum) {
if (node == null) return;
int n = node.val;
list.add(n);
if (node.left == null && node.right == null && sum == n) {
List<Integer> newList = new ArrayList<Integer>(list);
re.add(newList);
} else {
dfs(re, list, node.left, sum - n);
dfs(re, list, node.right, sum - n);
}
list.remove(list.size() - 1);
}
437. Path Sum III
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
代码一 3% 自己写的bullshit。 新建map太花时间了。我记录的是减法，实际记录加法就可以了。这样就不用每次新建map了。
int count=0;
public int pathSum(TreeNode root, int sum) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(sum, 1);//这个写在哪里一开始没有想清楚
dfs(root, map, sum);
return count;
}
void dfs(TreeNode node, Map<Integer, Integer> map, int sum) {
if (node == null) return;
int cur = node.val;
//不要在这里加，因为不好减
if (map.containsKey(cur)) {
count += map.get(cur);
}
if (node.left == null && node.right == null) return;
Map<Integer, Integer> curMap = new HashMap<Integer, Integer>();
for (int target : map.keySet()) {
curMap.put(target - cur, map.get(target));
}
curMap.put(sum, curMap.getOrDefault(sum, 0)+1);//在这里加
dfs(node.left,curMap,sum);
dfs(node.right,curMap,sum);
curMap.put(sum, curMap.get(sum)-1);//在这里减
}
代码二 68% 记录加法
public int pathSum(TreeNode root, int sum) {
HashMap<Integer, Integer> preSum = new HashMap();
preSum.put(0, 1);
return helper(root, 0, sum, preSum);
}
public int helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSum) {
if (root == null) return 0;
currSum += root.val;
int res = preSum.getOrDefault(currSum - target, 0);
preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1);
res += helper(root.left, currSum, target, preSum) + helper(root.right, currSum, target, preSum);
preSum.put(currSum, preSum.get(currSum) - 1);
return res;
}
代码三 46% 真正的迭代
public int pathSum(TreeNode root, int sum) {
if (root == null) return 0;
return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
private int pathSumFrom(TreeNode node, int sum) {
if (node == null) return 0;
return (node.val == sum ? 1 : 0)
+ pathSumFrom(node.left, sum - node.val) + pathSumFrom(node.right, sum - node.val);
}
257. Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
/ \
2 3
\
5
All root-to-leaf paths are:
["1->2->5", "1->3"]
代码一 15%
public List<String> binaryTreePaths(TreeNode root) {
List<String> re = new LinkedList<String>();
if (root == null) return re;
if (root.left == null & root.right == null) {
re.add(String.valueOf(root.val));
return re;
}
bfs(root.left, re, String.valueOf(root.val));
bfs(root.right, re, String.valueOf(root.val));
return re;
}
void bfs(TreeNode node, List<String> list, String s) {
if (node == null) {
return;
}
s += "->" + node.val;
if (node.left == null && node.right == null) {
list.add(s);
return;
}
bfs(node.left, list, s);
bfs(node.right, list, s);
}
代码二 3%
public List<String> binaryTreePaths(TreeNode root) {
List<String> answer = new ArrayList<String>();
if (root != null) searchBT(root, "", answer);
return answer;
}
private void searchBT(TreeNode root, String path, List<String> answer) {
if (root.left == null && root.right == null) answer.add(path + root.val);
if (root.left != null) searchBT(root.left, path + root.val + "->", answer);
if (root.right != null) searchBT(root.right, path + root.val + "->", answer);
}
116. Populating Next Right Pointers in Each Node
Given a binary tree
class TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
代码一 16% 不符合要求
public void connect(TreeLinkNode root) {
if (root == null) return;
Queue<TreeLinkNode> q = new LinkedList<TreeLinkNode>();
q.offer(root);
while (!q.isEmpty()) {
Queue<TreeLinkNode> next = new LinkedList<TreeLinkNode>();
int size = q.size();
for (int i = 0; i < size; i++) {
TreeLinkNode node = q.poll();
node.next = q.peek();
if (node.left != null) next.offer(node.left);
if (node.right != null) next.offer(node.right);
}
q = next;
}
}
代码二 29%
public void connect(TreeLinkNode root) {
if (root == null) return;
TreeLinkNode cur = root;
TreeLinkNode nextLeftmost = null;
while (cur.left != null) {//往下走
nextLeftmost = cur.left; // save the start of next level
while (cur != null) {//往右走
cur.left.next = cur.right;
cur.right.next = cur.next == null ? null : cur.next.left;
cur = cur.next;
}
cur = nextLeftmost; // point to next level
}
}
代码三 75%
public void connect(TreeLinkNode root) {
if(root==null) return;
if(root.left!=null) {
root.left.next=root.right;
connect(root.left);
}
if(root.next!=null && root.right!=null){
root.right.next=root.next.left;
}
connect(root.right);
}
117. Populating Next Right Pointers in Each Node II
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space.
For example,
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
代码 50%
public void connect(TreeLinkNode root) {
if (root == null) return;
TreeLinkNode head = new TreeLinkNode(0);
TreeLinkNode cur = head;
while (root != null) {// 这个循环既是往右走，又是往下走
if (root.left != null) {
cur.next = root.left;// 神来之笔
cur = cur.next;
}
if (root.right != null) {
cur.next = root.right;
cur = cur.next;
}
root = root.next;
if (root == null) {
root = head.next;
cur = head;
head.next = null;
}
}
}
129. Sum Root to Leaf Numbers
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
代码一 递归59%
public int sumNumbers(TreeNode root) {
return dfs(root,0);
}
int dfs(TreeNode node, int val){
if(node==null) return 0;
int sum=10*val+node.val;
if(node.left==null && node.right==null) return sum;
return dfs(node.left,sum)+dfs(node.right,sum);
}
440. K-th Smallest in Lexicographical Order
Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.
Note: 1 ≤ k ≤ n ≤ 109.
Example:
Input:
n: 13 k: 2
Output:
10
Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.
分析
依次逐渐确定前缀，每次计算当前前缀下不超过n的个数，若个数超过k，则说明第k个数在当前前缀下，反之，则说明在当前前缀加1以后的前缀；
以first为前缀的数
[first, first+1]
[first10, (first+1)10]
[first100, (first+1)100]
另一种分析方法，这是一颗十叉树，前序遍历（然而不用真的遍历，只需要计算子树的大小即可）
public int findKthNumber(int n, int k) {
int ans=1;
for(k--;k>0;){
int count=0;
for(long first=ans,second=first+1;first<=n;first*=10,second*=10){
count+=Math.min(n+1,second)-first;
}
if(count<=k){
k-=count;
ans++;
}else{
k--;//减掉的是当前为前缀的那个数
ans*=10;//元素个数太多，需要减小，因此前缀变大
}
}
return ans;
}
自己更习惯用gap，其实是一样的，不过上面写的更精简一点
每次的形式都为[first, first+gap]，每次循环跟新first和gap
[4, 4+1] ----> gap=1，first=4
[410, 410+10]----> gap=10, first=40
[4100, 4100+100]----> gap=100, first=400
public int findKthNumber(int n, int k) {
long size = 1;
int cur = 1;
k--;
while (k != 0) {
size = getSize(cur, n);
if (size > k) {
cur = cur * 10;
k--;
} else {
cur++;
k -= size;
}
}
return cur;
}
long getSize(long cur, long n){
long count=0;
long gap=1;
while(cur<=n){
count+=Math.min(gap, n-cur+1);
gap*=10;
cur*=10;
}
return count;
}
