算法-剑指Offer 解题方法总结

作者: tylorsenna | 来源:发表于2019-05-15 23:04 被阅读0次

[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出现的次数

求出1_{13的整数中1出现的次数,并算出100}1300的整数中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;
    }
};

未完待续...

算法-剑指Offer 解题方法总结

动态规划题型链接 (https://blog.csdn.net/weixin_41927235/article/details/103615653)

斐波那契数列（尾递归）

跳台阶（尾递归）

矩形覆盖

数值的整数次方

二进制中1的个数 (位操作)

链表中倒数第k个结点（快慢指针）

合并两个递增链表递归/非递归

合并两个递增数组，找出中位数

两个链表的第一个公共结点

树的子结构

二叉树的镜像

二叉树中序遍历的下一个结点

之字形打印二叉树

动态规划：最长公共子序列与最长公共子串

动态规划最大子数组和

动态规划买卖股票的最好时机1 LeetCode.121

二进制求和

数组中出现次数超过一半的数字

最小的K个数

整数1-n中1出现的次数

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法-剑指Offer 解题方法总结

动态规划题型链接 (https://blog.csdn.net/weixin_41927235/article/details/103615653)

斐波那契数列 （尾递归）

跳台阶 （尾递归）

矩形覆盖

数值的整数次方

二进制中1的个数 (位操作)

链表中倒数第k个结点 （快慢指针）

合并两个递增链表 递归/非递归

合并两个递增数组，找出中位数

两个链表的第一个公共结点

树的子结构

二叉树的镜像

二叉树中序遍历的下一个结点

之字形打印二叉树

动态规划：最长公共子序列与最长公共子串

动态规划 最大子数组和

动态规划 买卖股票的最好时机1 LeetCode.121

二进制求和

数组中出现次数超过一半的数字

最小的K个数

整数1-n中1出现的次数

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

斐波那契数列（尾递归）

跳台阶（尾递归）

链表中倒数第k个结点（快慢指针）

合并两个递增链表递归/非递归

动态规划最大子数组和

动态规划买卖股票的最好时机1 LeetCode.121