整数中1出现的次数 问题陈述 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。 示例： 12输入：n = 12输出：5 问题解法 将从各位至最高位出现1的次数累加即可得到。 记当前位为cur，cur的左边所有位记为高位high；cur的右边所有位记为低位low；10i10^i10i记为位因子digit。 某位中出现1的次数计算方法 当cur=0时，此位1的个数计算公式为：high×digit。 当cur=1时，此位1的个数计算公式为：high×digit+low+1。 当cur=2，3，4，5，6，7，8，9时，此位1的个数计算公式为：（high+1）×digit。 变量递推 12345while high != 0 or cur != 0 //当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出 low += cur * digit //将 cur 加入 low ，组成下轮 low cur = high % 10 ...

礼物的最大价值 问题陈述 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？ 示例： 12345678输入: [ [1,3,1], [1,5,1], [4,2,1]]输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物 思路分析 可使用动态规划解决此题。 状态定义：设动态规划矩阵dp，dp[i,j]代表从棋盘的左上角开始，到达[i,j]单元格能拿到最多礼物的累积值。 转移方程： 当i=0，j=0时，为起始元素。 当i=0，j$\ne$0时，为矩阵第一行元素，只可能从左边到达。 当i$\ne$0，j=0时，为矩阵第一列元素，只可能从上边到达。 当i≠0i\ne0i​=0,j≠0j\ne0j​=0时，可从左边或上边到达，据题意取两者中的最大值 初始状态：dp[0][0]=grid[0][0]。 返回值：dp[m-1][n-1],其中m，n为矩阵的长 ...

数组中出现一次的数字Ⅱ 问题陈述 思路分析 解法一 可考虑用一个HashMap来存，key为数字，value为出现次数。 代码实现 123456789101112131415161718192021222324252627public class SingleNumber { public int getSingleNumber(int[] nums){ Map<Integer,Integer> map=new HashMap<>(); for(int c:nums) { if (!map.containsKey(c)) { map.put(c, 1); continue; } else { map.put(c, map.get(c) + 1); } } int ...

数据流中的中位数 问题陈述 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。 例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构： void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。 示例1： 1234输入：["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"][[],[1],[2],[],[3],[]]输出：[null,null,null,1.50000,null,2.00000] 思路分析 可将数据流保存在一个列表中，并将其有序排列，在添加元素时保持有序， ...

多数元素 问题陈述 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 思路分析 方法一 哈希表 我们可以用一个哈希表来存储每个元素出现的次数，key为数值，value为出现次数。然后遍历HashMap寻找value大于1/2 length的数。 1234567891011121314151617181920212223242526class solution{ private Map<Integer,Integer> countNums(int[] nums){ Map<Integer,Integer> count=new Map<Integer,Integer>(); for(int num:nums){ if(!count.containsKey(num)){ count.put(num,1); ...

动态规划（dp） 递归与动态规划 动态规划是自底向上，递归树是自顶向下。 自顶向下：从一个规模较大的问题向下逐渐分解。如斐波那契问题，计算 f(20)，逐步分解到f(1)、f(2)，然后返回结果。 1234567int Fibonacci(size_t n){ if(n==1||n==2){ return n; } return Fibonacci(n-1)+Fibonacci(n-2);}//递归虽然代码优雅，但是数值过大可能会算不出来。 自底向上：从最底下、最简单的问题开始往上推，也就是动态规划的思想，通过循环迭代得到结果。 123456789//利用动态规划计算斐波那契数列int Fibonacci(int n){ vector<int> dp(N+1,0);//dp数组初始化 dp[1]=dp[2]=1; for(int i=3;i<=N;i++){ dp[i]=dp[i-1]+dp[i-2]; } return ...

二叉树中和为某一值的路径 问题陈述 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例: 给定如下二叉树，以及目标和 sum = 22。 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 思路分析 对每一层进行递归迭代，下一次的sum为sum减去当前已访问结点值。 代码实现 12345678910111213141516171819class solution { LinkedList<List<Integer>> list=new LinkedList<>(); LinkedList<Integer> path=new LinkedList<>(); public List<List<Integer> pathSum(TreeN ...

二叉搜索树的后序遍历序列 问题陈述 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树： 12345 5 / \ 2 6 / \1 3 示例 1： 输入: [1,6,3,2,5] 输出: false 思路分析 二叉搜索树：左子树的值小于根，右子树的值大于根。 后序遍历：左右根。如上示例，后序遍历为13265。 递归判断：具体见代码注释。 代码实现 12345678910111213141516class Solution {public: bool verifyPostorder(vector<int>& postorder) { return recurr(postorder,0,postorder.size()-1); //递归判断，初始化i=0，j=postorder.size()-1 } bool recurr(vector<int>& ...

复制带随机指针的链表 问题陈述 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的 深拷贝。 我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示： val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 示例： 输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]] 思路分析 浅拷贝与深拷贝 浅拷贝只复制指针的指向，即a和b共用同一个内存空间。深拷贝则开辟了一个新的内存空间用以存储该内容。 代码实现 回溯法 1234567891011121314151617181920212223242526272829303132333435/*// Definition for a Node.class Node { public int val; pub ...

栈的压入、弹出序列 问题陈述 给定一个入栈序列，可能存在多种出栈序列。然后我们给定一个出栈序列，判断它是否是正确的出栈序列。 思路分析 按入栈序列逐个入栈并判断当前栈顶元素是否和出栈序列元素相等，若相等则出栈该元素，同时出栈序列指向下一个元素。 继续入栈，继续判断。若为合理的出栈序列，最后栈必空。 代码实现 1234567891011121314151617181920public class StackPop_sequence { public boolean is_StackPop_sequence(int[] in,int[] out){ Stack<Integer> stack=new Stack<>(); int j=0,n=out.length; for(int i=0;i<in.length;i++){ stack.push(in[i]); while (!stack.isEmpty()&&j& ...