[toc]
动态规划题型链接 (https://blog.csdn.net/weixin_41927235/article/details/103615653)
斐波那契数列 （尾递归）
- 使用伪递归 F(n) = F(n-1)+b
- 当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。 其实和迭代原理是一样的（for循环）
// 0 1 1 2 3 5 8 13.......
public class Solution {
public int Fibonacci(int n) {
return Fibonacci(n,0,1); //n == 2 返回 s1+s2==0+1
}
private static int Fibonacci(int n,int s1,int s2){
if(n==0) return 0;
if(n==1) return s2;
else return Fibonacci(n - 1, s2, s1 + s2);
}
}
跳台阶 （尾递归）
- 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
矩形覆盖
- 我们可以用2X1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2X1的小矩形无重叠地覆盖一个2Xn的大矩形，总共有多少种方法？
// 0 1 2 3 5 8
public class Solution {
public int JumpFloor(int target) {
return Jump(target,1,2);//n == 2 返回 s1+s2==1+2
}
public int Jump(int n, int s1, int s2){
if(n == 0){
return 0;
}else if(n == 1){
return 1;
}else if(n == 2){
return s2;
}else{
return Jump(n-1,s2,s1+s2);
}
}
}
- 只需要满足 F(n) = F(n-1)+b这种动态规划的问题都适合用尾递归解决。
- F（n）= F(n-1)+F(n-2)+...+F(1)这种也可以。如变态跳台阶：
- Q:一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
- A:2的n次方
import java.lang.Math; //可以直接else返回Math.pow(2,taget-1)
// 0 1 2 4 8 16 .....
public class Solution {
public int JumpFloorII(int target) {
if(target == 0){
return 0;
}else if(target == 1){
return 1;
}else{
return 2*JumpFloorII(target-1);
}
}
}
数值的整数次方
- 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
//整数快速幂算法：https://blog.csdn.net/qq_19782019/article/details/85621386
class Solution {
double power(double base, int exp) {
if (exp == 1) return base;
if ((exp & 1) == 0) {
int tmp = power(base, exp >> 1);
return tmp * tmp;
} else {
int tmp = power(base, (exp - 1) >> 1);
return tmp * tmp * base;
}
}
public:
double Power(double base, int exp) {
if (base == 0) {
if (exp > 0) return 0;
else if (exp == 0) return 0;
else throw invalid_argument("Invalid input!");
} else {
if (exp > 0) return power(base, exp);
else if (exp == 0) return 1;
else return 1 / power(base, -exp);
}
}
};
二进制中1的个数 (位操作)
- Q:输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
- A:刚开始想着把int转为以二进制表示方法转为String，然后数1的个数，后来看了讨论区，orz： 位操作
public class Solution {
public int NumberOf1(int n) {
int result=0;
int test=n;
while (test!=0){
test&=(test-1);
result++;
}
return result;
}
}
链表中倒数第k个结点 （快慢指针）
- Q:输入一个链表，输出该链表中倒数第k个结点
- A:快慢指针解决，先让快指针走k-1步，走完以后，慢指针开始和快指针一起走，当快指针到达链表尾部时候，慢指针就指向倒数第k个结点。
- 注意：在快指针走k-1步时要判断快指针是否为null，即有没有第k个结点的存在。如果是，返回null。
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode slow = head;
ListNode fast = head;
for(int i=0; i<k; i++){//快指针走k-1步
if(fast == null){
return null;
}
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
合并两个递增链表 递归/非递归
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
/*//非递归
ListNode root = new ListNode(-1);
ListNode start = root;
while(list1!=null && list2!=null){
if(list1.val < list2.val){
root.next = list1;
root = list1;
list1 = list1.next;
}else{
root.next = list2;
root = list2;
list2 = list2.next;
}
}
//把未结束的链表连接到合并后的链表尾部
if(list1!=null){
root.next = list1;
}
if(list2!=null){
root.next = list2;
}
return start.next;*/
//递归方法：
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
if(list1.val <= list2.val){
list1.next = Merge(list1.next,list2);
return list1;
}else{
list2.next = Merge(list1,list2.next);
return list2;
}
}
}
合并两个递增数组，找出中位数
public class Main {
public static int[] merge(int[] array1, int[] array2){
int[] result = new int[array1.length + array2.length];
int i=0, j=0, k=0;
while(i<array1.length && j<array2.length){
if(array1[i] < array2[j]){
result[k++] = array1[i++];
}else {
result[k++] = array2[j++];
}
}
while(i<array1.length){
result[k++] = array1[i++];
}
while(j<array2.length){
result[k++] = array2[j++];
}
return result;
}
public static void main(String[] args) { //合并两个递增数组，找中位数
int[] array1 = new int[]{1,4,7,8};
int[] array2 = new int[]{2,3,4};
int mid = (array1.length + array2.length)/2 + 1;
int[] temp = merge(array1,array2);
for(int i=0; i<temp.length;i++){
System.out.println(" " + temp[i]);
}
System.out.println("中位数" + temp[mid]);
}
两个链表的第一个公共结点
- 公共节点之后的结点都在为同一条链表。
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int len1 = getLength(pHead1);
int len2 = getLength(pHead2);
ListNode longList = len1>len2?pHead1:pHead2;
ListNode shortList = len1>len2?pHead2:pHead1;
int len = len1>len2?len1-len2:len2-len1;
while(len-->0){
longList = longList.next;
}
while(longList != shortList){
longList = longList.next;
shortList = shortList.next;
}
return longList;
}
public int getLength(ListNode node){
int length = 0;
while(node!=null){
length++;
node = node.next;
}
return length;
}
}
树的子结构
- Q：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
- A: 利用两次递归：第一次先找到根节点相同的位置，第二次递归判断root2是否为root1的子结构。
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result = false;
//当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false
if(root1!=null && root2!=null){
//如果找到了对应Tree2的根节点的点
if(root1.val == root2.val){
//以这个根节点为为起点判断是否包含Tree2
result = doesTree1HaveTree2(root1, root2);
}
//如果找不到，那么就再去root的左儿子当作起点，去判断是否包含Tree2
if (!result) {
result = HasSubtree(root1.left,root2);
}
//如果还找不到，那么就再去root的右儿子当作起点，去判断是否包含Tree2
if (!result) {
result = HasSubtree(root1.right,root2);
}
}
//返回结果
return result;
}
public boolean doesTree1HaveTree2(TreeNode node1,TreeNode node2){
//如果Tree2已经遍历完了都能对应的上，返回true
if(node2 == null){
return true;
}
//如果Tree2还没有遍历完，Tree1却遍历完了。返回false
if (node1 == null) {
return false;
}
//如果其中有一个点没有对应上，返回false
if (node1.val != node2.val) {
return false;
}
//如果根节点对应的上，那么就分别去子节点里面匹配
return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
}
}
二叉树的镜像
- Q:操作给定的二叉树，将其变换为源二叉树的镜像。
- A:我们或许还记得递归的终极思想是数学归纳法，我们思考递归的时候一定不要去一步一步看它执行了啥，只会更绕。我们牢牢记住，思考的方式是我们首先假设子问题都已经完美处理，我只需要处理一下最终的问题即可，子问题的处理方式与最终那个处理方式一样，但是问题规模一定要以1的进制缩小。最后给一个递归出口条件即可。
- 对于本题，首先假设root的左右子树已经都处理好了，即左子树自身已经镜像了，右子树自身也镜像了，那么最后一步就是交换左右子树，问题解决。所以我只需要将root.left和root.right交换即可。下面进入递归，就是处理子问题。子问题的处理方式与root一样，只是要缩小问题规模，所以只需要考虑root.left是什么情况，root.right是什么情况即可。
import java.util.Stack; //需要引入包
public class Solution {
public void Mirror(TreeNode root) {
/*//递归版本
//若该节点不为空
if(root!= null){
//交换左右子树
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
//递归遍历左子树
if(root.left!=null){
Mirror(root.left);
}
//递归遍历右子树
if(root.right!=null){
Mirror(root.right);
}
}*/
//非递归
if(root == null){
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode temp,parent;
while(!stack.isEmpty()){
parent = stack.pop();
temp = parent.left;
parent.left = parent.right;
parent.right = temp;
if(parent.left!=null){
stack.push(parent.left);
}
if(parent.right!=null){
stack.push(parent.right);
}
}
}
}
二叉树中序遍历的下一个结点
- 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode == null){//1.二叉树为空，则返回空
return null;
}
if(pNode.right != null){//2.右子树存在，那么下一个结点必是右子树的最左侧结点
TreeLinkNode temp = pNode.right;
while(temp.left != null){
temp = temp.left;
}
return temp;
}
if(pNode.next == null){//当前结点是根结点，且无右子树
return null;
}
TreeLinkNode temp = pNode;
//如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果
while(temp.next != null){
TreeLinkNode parent = temp.next;
if(parent.left == temp){
return parent;
}
temp = temp.next;
}
return null;
}
}
之字形打印二叉树
- 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result= new ArrayList<ArrayList<Integer>>();
if(pRoot == null){
return result;
}
Stack<TreeNode> s1 = new Stack<TreeNode>();//存奇数层结点
Stack<TreeNode> s2 = new Stack<TreeNode>();//存偶数层结点
s1.push(pRoot);
TreeNode temp;
int layer = 1;//第一层
while(!s1.isEmpty() || !s2.isEmpty()){
if(layer%2 == 1){//奇数层
ArrayList<Integer> list1 = new ArrayList<Integer>();
while(!s1.isEmpty()){
temp = s1.pop();
list1.add(temp.val);
if(temp.left != null){
s2.push(temp.left);
}
if(temp.right != null){
s2.push(temp.right);
}
}
if(!list1.isEmpty()){
result.add(list1);
layer++;
}
}else{//偶数层
ArrayList<Integer> list2 = new ArrayList<Integer>();
while(!s2.isEmpty()){
temp = s2.pop();
list2.add(temp.val);
if(temp.right != null){
s1.push(temp.right);
}
if(temp.left != null){
s1.push(temp.left);
}
}
if(!list2.isEmpty()){
result.add(list2);
layer++;
}
}
}
return result;
}
}
动态规划：最长公共子序列与最长公共子串
- Q： 子串应该比较好理解，至于什么是子序列，这里给出一个例子：有两个母串
cnblogs
belong - 比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致，我们将其称为公共子序列。最长公共子序列（Longest Common Subsequence,LCS），顾名思义，是指在所有的子序列中最长的那一个。子串是要求更严格的一种子序列，要求在母串中连续地出现。在上述例子的中，最长公共子序列为blog（cnblogs, belong），最长公共子串为lo（cnblogs, belong）。
- A: 求解算法 对于母串X=<x1,x2,⋯,xm>, Y=<y1,y2,⋯,yn>，求LCS与最长公共子串。
- 暴力解法
假设 m<n， 对于母串X，我们可以暴力找出2m个子序列，然后依次在母串Y中匹配，算法的时间复杂度会达到指数级O(n∗2m)。显然，暴力求解不太适用于此类问题。 - 动态规划
假设Z=<z1,z2,⋯,zk>是X与Y的LCS， 我们观察到
如果xm=yn，则zk=xm=yn，有Zk−1是Xm−1与Yn−1的LCS；
如果xm≠yn，则Zk是Xm与Yn−1的LCS，或者是Xm−1与Yn的LCS。
因此，求解LCS的问题则变成递归求解的两个子问题。但是，上述的递归求解的办法中，重复的子问题多，效率低下。改进的办法——用空间换时间，用数组保存中间状态，方便后面的计算。这就是动态规划（DP)的核心思想了。 - DP求解LCS
用二维数组c[i][j]记录串x1x2⋯xi与y1y2⋯yj的LCS长度
public static int lcs(String str1, String str2) {
int len1 = str1.length();
int len2 = str2.length();
int c[][] = new int[len1+1][len2+1];
for (int i = 0; i <= len1; i++) {
for( int j = 0; j <= len2; j++) {
if(i == 0 || j == 0) {
c[i][j] = 0;
} else if (str1.charAt(i-1) == str2.charAt(j-1)) {
c[i][j] = c[i-1][j-1] + 1;
} else {
c[i][j] = max(c[i - 1][j], c[i][j - 1]);
}
}
}
return c[len1][len2];
}
- DP求解最长公共子串
- 前面提到了子串是一种特殊的子序列，因此同样可以用DP来解决。定义数组的存储含义对于后面推导转移方程显得尤为重要，糟糕的数组定义会导致异常繁杂的转移方程。考虑到子串的连续性，将二维数组c[i,j]用来记录具有这样特点的子串——结尾为母串x1x2⋯xi与y1y2⋯yj的结尾——的长度。得到转移方程：：
- 最长公共子串的长度为 max(c[i,j]), i∈{1,⋯,m},j∈{1,⋯,n}。
public static int lcs(String str1, String str2) {
int len1 = str1.length();
int len2 = str2.length();
int result = 0; //记录最长公共子串长度
int c[][] = new int[len1+1][len2+1];
for (int i = 0; i <= len1; i++) {
for( int j = 0; j <= len2; j++) {
if(i == 0 || j == 0) {
c[i][j] = 0;
} else if (str1.charAt(i-1) == str2.charAt(j-1)) {
c[i][j] = c[i-1][j-1] + 1;
result = max(c[i][j], result);
} else {
c[i][j] = 0;
}
}
}
return result;
}
作者：Treant
出处：http://www.cnblogs.com/en-heng/
分类: 算法
动态规划 最大子数组和
F（i）：以array[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变
F（i）=max（F（i-1）+array[i] ， array[i]）
res：所有子数组的和的最大值
res=max（res，F（i））
如数组[6, -3, -2, 7, -15, 1, 2, 2]
- 初始状态：
F（0）=6
res=6 - i=1：
F（1）=max（F（0）-3，-3）=max（6-3，3）=3
res=max（F（1），res）=max（3，6）=6 - i=2：
F（2）=max（F（1）-2，-2）=max（3-2，-2）=1
res=max（F（2），res）=max（1，6）=6 - i=3：
F（3）=max（F（2）+7，7）=max（1+7，7）=8
res=max（F（2），res）=max（8，6）=8 - i=4：
F（4）=max（F（3）-15，-15）=max（8-15，-15）=-7
res=max（F（4），res）=max（-7，8）=8
以此类推
最终res的值为8
public int FindGreatestSumOfSubArray(int[] array) {
int res = array[0]; //记录当前所有子数组的和的最大值
int max=array[0]; //包含array[i]的连续数组最大值
for (int i = 1; i < array.length; i++) {
max=Math.max(max+array[i], array[i]);
res=Math.max(max, res);
}
return res;
//更加清晰的动态规划：
/*
int []dp = new int[array.length];
dp[0] = array[0];
int max = array[0];
for (int i = 1; i < array.length; i++) {
dp[i] = dp[i - 1] >= 0 ? (dp[i - 1] + array[i]) : array[i];
if (dp[i] > max)
max = dp[i];
}
return max;
*/
}
动态规划 买卖股票的最好时机1 LeetCode.121
- 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
- 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
- 注意你不能在买入股票前卖出股票。
- 输入: [7,1,5,3,6,4]
- 输出: 5
- 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6,因为卖出价格需要大于买入价格。
- 输入: [7,6,4,3,1]
- 输出: 0
- 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<2) return 0;
int min = prices[0];
int profit = 0;
for(int i=1; i<prices.size(); i++){
profit = profit>prices[i]-min?profit:prices[i]-min;
min = min>prices[i]?prices[i]:min;
}
return profit;
}
};
二进制求和
- 输入: a = "11", b = "1"
- 输出: "100"
class Solution {
public String addBinary(String a, String b) {
// 太容易溢出，错误做法，位数需要满足数据类型。。。
// int int_a = Integer.parseInt(a,2);
// int int_b = Integer.parseInt(b,2);
// int result = int_a + int_b;
// return Integer.toBinaryString(result);
//完美做法：类似链表加法
StringBuffer sb = new StringBuffer();
int carry = 0, i = a.length()-1, j = b.length()-1;
while(i >= 0 || j >= 0 || carry != 0){
if(i >= 0) carry += a.charAt(i--)-'0';
if(j >= 0) carry += b.charAt(j--)-'0';
sb.append(carry%2);
carry /= 2;
}
return sb.reverse().toString();
}
}
数组中出现次数超过一半的数字
- 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
import java.util.HashMap;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
/*
HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>();
for(int i=0; i<array.length; i++){
if(hashMap.containsKey(array[i])){
int num = hashMap.get(array[i]);
hashMap.put(array[i],num+1);
}else{
hashMap.put(array[i],1);
}
}
for(int i=0; i<array.length; i++){
if(hashMap.get(array[i]) > (array.length/2)){
return array[i];
}
}
return 0;*/
//打擂台算法
if(array.length<=0){
return 0;
}
int result = array[0];
int times = 1;
for(int i=0;i<array.length;i++){
if(times==0){
result = array[i];
times =1;
}else if(array[i]==result)
times++;
else
times--;
}
int time = 0;
for(int i=0;i<array.length;++i){
if(array[i] == result)
time++;
}
if(time*2<=array.length){
return 0;
}else{
return result;
}
}
}
最小的K个数
- 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(input == null || k <= 0 || input.length<=0 || input.length <k){
return list;
}
//用前k个数构造最大堆 O（n+nlogK）
for(int len=k/2-1; len>=0; len--){
adjustMaxHeapHeapSort(input,len,k-1); //从0到k-1
}
//从第k个元素开始分别与最大堆的最大值做比较，如果比最大值小，则替换并调整堆。
//最终堆里的就是最小的K个数。
int temp;
for(int i=k; i<input.length; i++){
if(input[i] < input[0]){
temp = input[0];
input[0] = input[i];
input[i] = temp;
adjustMaxHeapHeapSort(input,0,k-1);
}
}
//输出结果 结果不需要是顺序or逆序 只要是最小的k个数就行。
for(int i=k-1; i>=0; i--){
list.add(input[i]);
}
/*
//java的优先级队列是用堆实现的
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2){
return o2.compareTo(o1); //大的反而小，为了使其成为大顶堆
}
});
for(int i=0; i<input.length; i++){
if(maxHeap.size() != k){
maxHeap.offer(input[i]);
}else if(maxHeap.peek() >= input[i]){
Integer temp = maxHeap.poll();
temp = null;
maxHeap.offer(input[i]);
}
}
for(Integer integer : maxHeap){
list.add(integer);
}*/
return list;
}
public void adjustMaxHeapHeapSort(int[] input, int pos, int length){
int temp;
int child;
for(temp = input[pos]; 2*pos+1<=length; pos=child){
child=2*pos+1;
if(child<length && input[child]<input[child+1]){
child++;
}
if(input[child] > temp){
input[pos] = input[child];
}else{
break;
}
}
input[pos] = temp;
}
}
整数1-n中1出现的次数
- 求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
#include <math.h>
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
//主要思路：设定整数点（如1、10、100等等）作为位置点i（对应n的各位、十位、百位等等），分别对每个数位上有多少包含1的点进行分析
//根据设定的整数位置，对n进行分割，分为两部分，高位n/i，低位n%i
//当i表示百位，且百位对应的数>=2,如n=31456,i=100，则a=314,b=56，此时百位为1的次数有a/10+1=32（最高两位0~31），每一次都包含100个连续的点，即共有(a%10+1)*100个点的百位为1
//当i表示百位，且百位对应的数为1，如n=31156,i=100，则a=311,b=56，此时百位对应的就是1，则共有a%10(最高两位0-30)次是包含100个连续点，当最高两位为31（即a=311），本次只对应局部点00~56，共b+1次，所有点加起来共有（a%10*100）+(b+1)，这些点百位对应为1
//当i表示百位，且百位对应的数为0,如n=31056,i=100，则a=310,b=56，此时百位为1的次数有a/10=31（最高两位0~30）
//综合以上三种情况，当百位对应0或>=2时，有(a+8)/10次包含所有100个点，还有当百位为1(a%10==1)，需要增加局部点b+1
//之所以补8，是因为当百位为0，则a/10==(a+8)/10，当百位>=2，补8会产生进位位，效果等同于(a/10+1)
int count=0;
long long i=1;
for(i=1;i<=n;i*=10)
{
//i表示当前分析的是哪一个数位
int a = n/i,b = n%i;
count=count+(a+8)/10*i+(a%10==1)*(b+1);
}
return count;
}
};
未完待续...
