1.题目 求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。 2.思路 2.1方法一： 将所有数字转换成字符串，再遍历每个字符串的每一位。当n位数较大时，时间复杂度会比较高O(n^2) public class Solution { public int NumberOf1Between1AndN_Solution(int n...

1.题目HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)2.思路采用动态规划算法：算法思路如下1.状态转移方程：arr[i]=arr[i-1]+array[i]2.并且每一步判断是不是小于0，如果小于0则置为...

1.题目把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。如，输入7，返回82.思路方法一：个人感觉思路对的，可是牛客说我时间复杂度过大,但是代码比较直观所谓一个数m是另一个数n的因子，是指n能被m整除，也就是说n%m==0. public class Solution { public int GetUglyNumber_Solution(int index) { int[] result = new int[index]; ...

1.题目输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）如：输入[1,2,3,4,5],[4,3,5,1,2] 返回false 输入[1,2,3,4,5],[4,5,3,2,1] 返回true2.思路模拟法：直接模拟即可。因为弹出之前的值都会先入栈，所以这里用个栈来辅助。 初始化：用指针i指向pushV的第一个位置， 指针j指向popV的...

1.题目输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。如，输入：{1,3,5},{2,4,6}；输出：{1,2,3,4,5,6}2.思路：方法一：迭代版本牛客官方思路初始化：定义cur指向新链表的头结点操作： 如果l1指向的结点值小于等于l2指向的结点值，则将l1指向的结点值链接到cur的next指针，然后l1指向下一个结点值 否则，让l2指向下一个结点值 循环步骤1,2，直到l1或者l2为null 将l1或者l2剩下的部分链接到cur的后面技巧：一般创建单链表，都会设一个虚拟头结点，也叫哨兵，因为这样每一个结点都有一个前驱...

1.题目输入一个链表，反转链表后，输出新链表的表头。如，输入123，输出32.思路题目所给的是单链表，想了一下反转后的样子：最后一个结点指向倒数第二个，倒数第二个指向倒数第三个，......，第二个指向第一个，第一个指向null;知道了反转后各个结点指向哪之后，就需要开始调整每个结点的next指针。这就需要把结点挨个从链表上摘下来，做调整；这个调整过程需要两个指针辅助：pre记录其前一个结点位置，好让该结点的next指针指向前一个结点，但是在指向前一个结点前需要用一个指针p记录后一个结点地址，避免结点丢失。例子： 以head结点为例步骤如下： 1.反转后head是指向null，所以...

1.题目输入一个链表，输出该链表中倒数第k个结点。如，输入：1,{1,2,3,4,5}；返回：{5}2.思路方法一：我首先想到的是存入hashmap，然后直接对应键值来取值，由于是倒数的，所以要有长度记录从0开始储存，记录长度为len，则找倒数第k个就是(len-k)个时间复杂度：O(n),空间复杂度：O(n) import java.util.*; public class Solution { public ListNode FindKthToTail(ListNode head,int k) { HashMap<Integer,ListNode> ma...

1.题目输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。2.思路：方法一： 新开数组空间换时间的解法, a.从头遍历数组,如果是奇数从头部放入到新数组中, b.从尾遍历数组，如果是偶数从尾部放入新数组 c.将新数组的元素复制到原数组时间复杂度O(n^2) public class Solution { public void reOrderArray(int [] array) { if(array.length==0) ret...

1.题目给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。（保证base和exponent不同时为0 —）如，输入2，3；返回8.00000 2.思路方法一：直接调用Math类的pow方法 public class Solution { public double Power(double base, int exponent) { return Math.pow(base,exponent); } }方法二：上述方法就显得本题毫无意义，可直接实现pow()方法时间复杂度：O(n) public class...

1.题目输入一个链表，按链表从尾到头的顺序返回一个ArrayList。如，输入：{67,0,24,58}；输出：[58,24,0,67]2.思路：方法一：这种反向输出很容易想到了栈 import java.util.ArrayList; import java.util.*; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { Stack<ListNode> s=new Stack<>(); ...

1.题目 请实现两个函数，分别用来序列化和反序列化二叉树： 二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以！表示一个结点值的结束（value!）。 二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。示例：输入：{8,6,10,5,7,9,11}输出：{8,6,10,5,7,9,11} 2.思路/* 对于序列化：使用前序遍历，递归的将二叉树的值转化为字符，并且在...

1.题目： 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。2.思路：方法一：与题目《把二叉树打印成多行》，《从上往下打印二叉树》类似，都是树的广度优先遍历(BFS),或者说是层序遍历；只不过这道题增加打印的规则，那么我们可以在以前代码的基础上增加一点约束就行： list.add(T): 按照索引顺序从小到大依次添加 list.add(index, T): 将元素插入index位置，index索引后的元素依次后移,这就完成了每一行元素的倒序，或者使用Collection.reverse()方...

1.题目：请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。2.思路：根据上图可知：若满足对称二叉树，必须满足： 1. L->val == R->val 2. L->left->val == R->right->val 3. L->right->val == R->left->val因此可以自顶向下，递归求解即可。 1.设置一个递归函数isSame(r1, r2),表示如果对称，返回true，否则返回false 2.递归终止条件：r1==nullptr &...

1.题目：输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。1.思路：递归算法三部曲： 1).明白递归函数的功能：FindPath(TreeNode* root,int sum)，从root节点出发，找和为sum的路径 2).递归终止条件：当root节点为叶子节点(root.left!=null&&root.right!=null)并且sum==target, 表示找到了一条符合条件的路径 3).下一次递归：如果左子树不空，递归左子树FindPath(ro...