牛客网剑指offer刷题汇总

基于牛客网刷剑指offer的全部java代码
GitHub地址

00 树和链表模组

各个题目中涉及的树、链表等通用定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}

01 判断一个行列都递增的数组是否包含某个数

题目描述
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。
请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//思路一,每一行二分查找法
//但是此方法时间复杂度为nlogn是在复杂度太大。
public boolean Find2(int target, int [][] array) {
for (int i = 0; i < array.length; i++) {
int low = 0;
int high = array[i].length-1;
int mid = (low+high)/2;
while(low<=high){
if(target>array[i][mid]){
low = mid + 1;
}else if(target<array[i][mid]){
high = mid - 1;
}else
return true;
}
}
return false;
}
//思路2,根据此数组的特性,
/*
利用二维数组由上到下,由左到右递增的规律,
那么选取右上角或者左下角的元素a[row][col]与target进行比较,
当target小于元素a[row][col]时,那么target必定在元素a所在行的左边,即col--;
当target大于元素a[row][col]时,那么target必定在元素a所在列的下边,即row++;
* */
public boolean Find(int target, int [][] array) {
int row = 0;
int col = array[0].length - 1;//选取右上角
while(row<=array.length-1 && col>=0){
if (target==array[row][col])
return true;
else if(target<array[row][col])
col--;
else
row++;
}
return false;
}

02 替换字符串中的空格为%20

请实现一个函数,将一个字符串中的空格替换成“%20”。
例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

1
2
3
4
5
6
7
8
9
10
11
12
public String replaceSpace(StringBuffer str) {
char[] c = str.toString().toCharArray();
StringBuffer sb = new StringBuffer();
for (int i = 0; i < c.length; i++) {
if (c[i]==' '){
sb.append("%20");
}else {
sb.append(c[i]);
}
}
return sb.toString();
}

03 从尾到头打印链表每个节点的值

输入一个链表,从尾到头打印链表每个节点的值。

1
2
3
4
5
6
7
8
9
10
//递归方式实现
ArrayList<Integer> arrayList = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if (listNode!=null){
this.printListFromTailToHead(listNode.next);
arrayList.add(listNode.val);
}
return arrayList;
}

04 根据中序和前序重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},
则重建二叉树并返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//根据先序找到头结点,根据头结点在中序中找到左右子树。然后递归重建。
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return this.reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
}
public TreeNode reConstructBinaryTree(int [] pre,int start1,int end1,int [] in,int start2,int end2) {
if (start1>end1 || start2>end2)
return null;
int rootData = pre[start1];
TreeNode head = new TreeNode(rootData);
//找到根节点位置
int rootIndex = findIndexInArray(in,rootData,start2,end2);
int offset = rootIndex - start2 - 1;
//构建左子树
TreeNode left = reConstructBinaryTree(pre,start1+1,start1+1+offset,in,start2,start2+offset);
//构建右子树
TreeNode right = reConstructBinaryTree(pre,start1+offset+2,end1,in,rootIndex+1,end2);
head.left = left;
head.right = right;
return head;
}
private int findIndexInArray(int[] a, int rootData, int begin, int end) {
for (int i = begin; i <= end; i++) {
if(a[i]==rootData)
return i;
}
return -1;
}

05 两个队列模拟一个栈

用两个栈实现一个队列的功能?要求给出算法和思路!
<分析>:
入队:将元素进栈A
出队:判断栈B是否为空,如果为空,则将栈A中所有元素pop,并push进栈B,栈B出栈;
如果不为空,栈B直接出栈。
用两个队列实现一个栈的功能?要求给出算法和思路!
<分析>:
入栈:将元素进队列A
出栈:判断队列A中元素的个数是否为1,如果等于1,则出队列,否则将队列A中的元素以此出队列并放入队列B,
直到队列A中的元素留下一个,然后队列A出队列,再把队列B中的元素出队列以此放入队列A中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
int a;
if (stack2.empty()){
while (!stack1.empty()){
a = stack1.pop();
stack2.push(a);
}
}
a = stack2.pop();
return a;
}

06 非递减数组旋转后变为递增数组输出最小元素

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int minNumberInRotateArray(int [] array) {
if(array.length==0)
return 0;
for (int i = 0; i < array.length; i++) {
if (array[i]<=array[i+1])
continue;
else {
int g = array[i + 1];
return g;
}
}
return 0;
}

07 输出斐波那契数列的第n项

F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//递归,但是递归时间复杂度过大,所思考其他方法
public int Fibonacci2(int n) {
if (0==n)
return 0;
else if (1==n){
return 1;
}else{
return Fibonacci2(n-2) + Fibonacci2(n-1);
}
}
//循环法
public int Fibonacci(int n) {
int prePreNum = 0;
int preNum = 1;
int sum = 0;
if (0==n)
return 0;
else if (1==n){
return 1;
}else{
for (int i = 2; i <=n; i++) {
sum = prePreNum + preNum;
prePreNum = preNum;
preNum = sum;
}
return sum;
}
}

08 青蛙跳台阶一次跳1级或者2级n级有多少种跳法

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//递归解法
public int JumpFloor(int target) {
if (0==target)
return 0;
else if (1==target)
return 1;
else if (2==target)
return 2;
else {
return (JumpFloor(target-1) + JumpFloor(target-2));
}
}
//迭代解法
public int JumpFloor2(int target){
if (target==0 || target==1 || target==2)
return target;
else {
// 第一阶和第二阶考虑过了,初始当前台阶为第三阶,向后迭代
// 思路:当前台阶的跳法总数=当前台阶后退一阶的台阶的跳法总数+当前台阶后退二阶的台阶的跳法总数
int lastNum = 2;//第三级台阶退后一节有几种跳法
int lastlastNum = 1;//第三级台阶退后2节有几种跳法
int sum=0;
for (int i = 3; i <= target; i++) {
sum = lastlastNum + lastNum;
lastlastNum = lastNum; // 后退一阶在下一次迭代变为后退两阶
lastNum = sum; // 当前台阶在下一次迭代变为后退一阶
}
return sum;
}
}

09 青蛙跳台阶可以调1-n级n级台阶共有多少种跳法

关于本题,前提是n个台阶会有一次n阶的跳法。分析如下:
f(1) = 1
f(2) = f(2-1) + f(2-2)//f(2-2) 表示2阶一次跳2阶的次数。
f(3) = f(3-1) + f(3-2) + f(3-3)

f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-(n-1)) + f(n-n)
说明:
1)这里的f(n) 代表的是n个台阶有一次1,2,…n阶的 跳法数。
2)n = 1时,只有1种跳法,f(1) = 1
3) n = 2时,会有两个跳得方式,一次1阶或者2阶,这回归到了问题(1) ,f(2) = f(2-1) + f(2-2)
4) n = 3时,会有三种跳得方式,1阶、2阶、3阶那么就是第一次跳出1阶后面剩下:
f(3-1);第一次跳出2阶,剩下f(3-2);第一次3阶,那么剩下f(3-3) 因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)
5) n = n时,会有n中跳的方式,1阶、2阶…n阶,得出结论:

f(n) = f(n-1)+f(n-2)+…+f(n-(n-1)) + f(n-n) =>
f(0) + f(1) + f(2) + f(3) + … + f(n-1)
6) 由以上已经是一种结论,但是为了简单,我们可以继续简化:
f(n-1) = f(0) + f(1)+f(2)+f(3) + … + f((n-1)-1) =
f(0) + f(1) + f(2) + f(3) + … + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + … + f(n-2) +
f(n-1) = f(n-1) + f(n-1)
可以得出:
f(n) = 2f(n-1)
7) 得出最终结论,在n阶台阶,一次有1、2、…n阶的跳的方式时,总得跳法为:
| 1 ,(n=0 )
f(n) = | 1 ,(n=1 )
| 2
f(n-1),(n>=2)

1
2
3
4
5
6
7
public int JumpFloorII(int target) {
if (target==1 || target==2)
return target;
else {
return 2*JumpFloorII(target-1);
}
}

10 矩形覆盖问题

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。
请问用n个2
1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

依旧是斐波那契数列
2n的大矩形,和n个21的小矩形
其中target2为大矩阵的大小
有以下几种情形:
target <= 0 大矩形为<= 2
0,直接return 1;
target = 1大矩形为21,只有一种摆放方法,return1;
target = 2 大矩形为2
2,有两种摆放方法,return2;
target = n 分为两步考虑:
第一次摆放一块 21 的小矩阵,则摆放方法总共为f(target - 1)
第一次摆放一块1
2的小矩阵,则摆放方法总共为f(target-2)
因为,摆放了一块12的小矩阵(用√√表示),对应下方的12(用××表示)摆放方法就确定了,所以为f(targte-2)

1
2
3
4
5
6
7
8
9
public int RectCover(int target) {
if (target==0)
return 0;
else if (target==2 || target==1){
return target;
}else {
return RectCover(target-1) + RectCover(target-2);
}
}

11 判断一个整数二进制表示中1的个数

输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
正常解法
*/
public int NumberOf1(int n) {
int count = 0;
if (n==0)
return 0;
else {
while (n != 0) {
n = n & (n-1);
count++;
}
}
return count;
}
/*
用java工具类
*/
public int NumberOf12(int n) {
return Integer.toBinaryString(n).replace("0","").length();
}

12 求double类型的exponent次方

题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public double Power(double base, int exponent) {
return (double)Math.pow(base,exponent);
}
//递归方法
public double Power2(double base, int exponent) {
int n = Math.abs( exponent );
double result = 0.0;
if (n==0)
return 1;
if (n==1)
result = base;
result = Power2( base,n>>1 );
result *= result;
if ((n&1)==1) //如果指数是奇数,那就要再乘一次
result *= base;
if (exponent<0) //如果指数为负数,则求result的倒数
result = 1 / result;
return result;
}
//累乘法
public double Power2(double base, int exponent) {
double result = 1.0;
for (int i = 0; i < Math.abs( exponent ); i++) {
result *= base;
}
if (exponent>= 0)
return result;
else
return 1 / result;
}

13 将数组的奇数放在前半部分偶数放在数组后半部分

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,
使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,
并保证奇数和奇数,偶数和偶数之间的相对位置不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void reOrderArray(int [] array) {
Vector<Integer> vector = new Vector<Integer>();
for (int i = 0; i <= array.length-1; i++) {
if (array[i]%2==1)
vector.add(array[i]);
}
for (int i = 0; i <= array.length-1; i++) {
if (array[i]%2==0)
vector.add(array[i]);
}
for (int i = 0; i <= array.length-1; i++) {
array[i] = vector.get(i);
}
}

14 输出链表倒数第K个节点

输入一个链表,输出该链表中倒数第k个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
最佳代码:Java代码,通过校验。代码思路如下:
两个指针,先让第一个指针和第二个指针都指向头结点,然后再让第一个指正走(k-1)步,到达第k个节点。
然后两个指针同时往后移动,当第一个结点到达末尾的时候,第二个结点所在位置就是倒数第k个节点了。。
*/
public ListNode FindKthToTail(ListNode head,int k) {
if (head==null||k<=0)
return null;
ListNode preNode = head;
ListNode lastNode = head;
for (int i = 1; i < k; i++) {
if (preNode.next!=null){
preNode = preNode.next;
}else {
return null;
}
}
while (preNode.next!=null){
preNode = preNode.next;
lastNode = lastNode.next;
}
return lastNode;
}

15 反转链表并输出链表所有元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
方法一:递归法
*/
public ListNode ReverseList2(ListNode head) {
if (head==null || head.next==null)
return head;
ListNode h = ReverseList2(head.next);
head.next.next = head;
head.next = null;
return h;
}
/*
方法二:正常替换法
*/
public ListNode ReverseList(ListNode head) {
ListNode pre = null;
ListNode next = null;
if (head==null || head.next==null)
return head;
while (head!=null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}

16 将两个单调递增的链表合并成单调不减的链表

题目描述
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
非递归版本,然而时间复杂度过大,那么考虑递归版本
*/
public ListNode Merge2(ListNode list1,ListNode list2) {
ListNode list = null;
ListNode next = null;
if (list1==null && list2==null)
return null;
else if(list1==null || list2==null){
if (list1==null)
return list2;
else
return list1;
}else {
while (list1!=null||list2!=null){
if (list1.val<=list2.val) {
if (list==null){
list = list1;
list.next = next;
}else {
next = list1;
list.next = next;
list = list.next;
list1 = list1.next;
}
}else {
if (list==null){
list = list2;
list.next = next;
}else {
next = list2;
list.next = next;
list = list.next;
list2 = list2.next;
}
}
}
}
return list;
}
/*
递归版本
*/
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode headNode = null;
if (list1==null)
return list2;
else if (list2==null)
return list1;
else {
if(list1.val<list2.val){
headNode = list1;
headNode.next = Merge(list1.next,list2);
}else {
headNode = list2;
headNode.next = Merge(list1,list2.next);
}
}
return headNode;
}

17 判断一个树是不是另一个树的子树

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
递归法求解
*/
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result = false;
if (root1==null || root2==null)
return false;
else {
if(root1.val==root2.val){
result = DoesTree1HaveTree2(root1,root2);
}
if (!result)
result = DoesTree1HaveTree2(root1.left,root2);
if (!result)
result = DoesTree1HaveTree2(root1.right,root2);
}
return result;
}
public boolean DoesTree1HaveTree2(TreeNode root1,TreeNode root2){
if(root1 == null && root2 != null)
return false;
if(root2 == null)
return true;
if(root1.val != root2.val)
return false;
return DoesTree1HaveTree2(root1.left, root2.left) && DoesTree1HaveTree2(root1.right, root2.right);
}

18 将二叉树变换为镜像二叉树

题目描述
操作给定的二叉树,将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义:源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5

1
2
3
4
5
6
7
8
9
10
11
12
13
public void Mirror(TreeNode root) {
TreeNode tmp = null;
if (root!=null){
tmp = root.left;
root.left = root.right;
root.right = tmp;
if (root.left!=null)
Mirror(root.left);
if (root.right!=null)
Mirror(root.right);
}
}

19 将矩阵从外到里打印出每一个数字

题目描述
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,
例如,如果输入如下矩阵:
[1 2 3 4]
[5 6 7 8]
[9 10 11 12]
[13 14 15 16]
则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
//主体循环部分才5行。其实是有规律可循的。将每一层的四个边角搞清楚就可以打印出来了
*/
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (matrix.length==0)
return result;
int n = matrix.length;
int m = matrix[0].length;
if (m==0)
return result;
int layer = (Math.min(n,m)-1)/2 + 1;//层数
for (int i = 0; i < layer; i++) {
//从左到右
for (int j = i; j < m - i; j++) {
result.add(matrix[i][j]);//左上角
}
//从右上到右下
for (int j = i + 1; j < n - i; j++) {
result.add(matrix[j][m - i - 1]);//右上角
}
//从右到左
for (int j = m - i - 2; j >= i && (n - i - 1 != i); j--) {
result.add(matrix[n - i - 1][j]);//右下角
}
//左下到左上
for (int j = n - i - 2; j > i && (m - i - 1 != i); j--) {
result.add(matrix[j][i]);//左下角
}
}
return result;
}

20 定义一种额外的栈可得得到栈中最小元素

定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。
注意不能有具体的int类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
思路:
用一个栈data保存数据,用另外一个栈min保存依次入栈最小的数
比如,data中依次入栈,543, 8, 10, 11, 12, 1
   则min依次入栈,5433,3, 3, 3, 1
*/
Stack dataStack = new Stack();
Stack minStack = new Stack();
public void push(int node) {
dataStack.push(node);
if (minStack.isEmpty()) {
minStack.push(node);
}else{
if (node<(int)minStack.peek()){
minStack.add(node);
}else {
minStack.add((int)minStack.peek());
}
}
}
public void pop() {
dataStack.pop();
minStack.pop();
}
public int top() {
return (int)dataStack.peek();
}
public int min() {
return (int)minStack.peek();
}

21 判断第二个栈序列是是否是第一个栈序列栈的弹出序列

题目描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。
假设压入栈的所有数字均不相等。
例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,
但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
【思路】借用一个辅助的栈,遍历压栈顺序,先将第一个放入栈中,
这里是1,然后判断栈顶元素是不是出栈顺序的第一个元素,这里是4,很显然1≠4,所以我们继续压栈,
直到相等以后开始出栈,出栈一个元素,则将出栈顺序向后移动一位,直到不相等,这样循环等压栈顺序遍历完成
,如果辅助栈还不为空,说明弹出序列不是该栈的弹出顺序。
举例:
入栈1,2,3,4,5
出栈4,5,3,2,1
首先1入辅助栈,此时栈顶1≠4,继续入栈2
此时栈顶2≠4,继续入栈3
此时栈顶3≠4,继续入栈4
此时栈顶4=4,出栈4,弹出序列向后一位,此时为5,,辅助栈里面是1,2,3
此时栈顶3≠5,继续入栈5
此时栈顶5=5,出栈5,弹出序列向后一位,此时为3,,辅助栈里面是1,2,3
….
依次执行,最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。
*/
public boolean IsPopOrder(int [] pushA,int [] popA) {
if (pushA.length==0 || popA.length==0)
return false;
Stack<Integer> stack = new Stack<>();
//用于标识弹出序列的位置
int popIndex = 0;
for (int i = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
//如果栈不为空,且栈顶元素等于弹出序列
while (!stack.isEmpty() && stack.peek()==popA[popIndex]){
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}

22 层序打印二叉树

题目描述
从上往下打印出二叉树的每个节点,同层节点从左至右打印。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
用队列来实现层序遍历,然而却时间复杂度过大
*/
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
ArrayList<Integer> arrayList = new ArrayList<>();
if (root == null)
return arrayList;
queue.add(root);
while (!queue.isEmpty()) {
TreeNode treeNode = queue.poll();
arrayList.add(treeNode.val);
if (root.left != null)
queue.add(root.left);
if (root.right != null)
queue.add(root.right);
}
return arrayList;
}
/*
用ArrayList来模拟队列
*/
public ArrayList<Integer> PrintFromTopToBottom2(TreeNode root){
ArrayList<Integer> list = new ArrayList<>();
ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
if (root == null) {
return list;
}
queue.add(root);
while (queue.size() != 0) {
TreeNode temp = queue.remove(0);
list.add(temp.val);
if (temp.left != null){
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
}
return list;
}

23 判断一个数组是不是某二叉搜索树的后序遍历

题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
递归解法
*/
public boolean VerifySquenceOfBST2(int [] sequence) {
int length = sequence.length - 1;
if (length<0)
return false;
if (length==0){
return true;
}
return juge(sequence,0,length);
}
private boolean juge(int[] sequence, int start, int root) {
if (start>=root)
return true;
int i = root;
while (i>start && sequence[i-1]>sequence[root])
i--;
for (int j = start; j < i-1; j++) {
if (sequence[j]>sequence[root])
return false;
}
return juge(sequence,start,i-1) && juge(sequence,i,root-1);
}
/*
//非递归
  //非递归也是一个基于递归的思想:
//左子树一定比右子树小,因此去掉根后,数字分为left,right两部分,
//right部分的最后一个数字是右子树的根他也比左子树所有值大,
//因此我们可以每次只看有子树是否符合条件即可,
//即使到达了左子树左子树也可以看出由左右子树组成的树还想右子树那样处理
 //对于左子树回到了原问题,对于右子树,左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树
//只需看看右子树的右子树是否符合要求即可
*/
public boolean VerifySquenceOfBST(int [] sequence) {
int size = sequence.length-1;
if (size<0)
return false;
int i = 0;
while (size>=0){
while(sequence[i]<sequence[size]){
i++;
}
while(sequence[i]>sequence[size]){
i++;
}
if (i<size)
return false;
i=0;
size--;
}
return true;
}

24 打印二叉树的路径

输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。
路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
递归解法
*/
ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
if (root==null)
return listAll;
list.add(root.val);
target = target - root.val;
if (target==0 && root.left==null && root.right==null)
listAll.add(new ArrayList<Integer>(list));
FindPath(root.left,target);
FindPath(root.right,target);
//如果到叶子节点找不到那么就要回退
list.remove(list.size()-1);
return listAll;
}

25 复杂链表的复制

题目描述
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),
返回结果为复制后复杂链表的head。
(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
递归法
*/
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead==null)
return null;
RandomListNode randomListNodeHead = new RandomListNode(pHead.label);
randomListNodeHead.next = pHead.next;
randomListNodeHead.random = pHead.random;
//递归其他节点
randomListNodeHead.next = Clone(pHead.next);
return randomListNodeHead;
}
/*
方法二:拆分法
*/
public RandomListNode Clone2(RandomListNode pHead){
if (pHead==null)
return null;
RandomListNode pCur = pHead;
//在每一个节点后增加一个和他相同的节点如A>B>C变为A>A'>B>B'>C>C'
while(pCur!=null){
RandomListNode node = new RandomListNode(pCur.label);
node.next = pCur.next;
node.random = pCur.random;
pCur.next = node;
pCur = node.next;
}
pCur = pHead;//置换为头结点
RandomListNode pCloneHead = pHead.next;
RandomListNode cur = pCloneHead;
//链表拆分
while(pCur!=null){
pCur.next = pCur.next.next;
if (cur.next!=null){
cur.next = cur.next.next;
}
pCur = pCur.next;
cur = cur.next;
}
return pCloneHead;
}

26 二叉搜索树转换为有小到大的双向链表

/
题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
例如 10
/ \
6 14
/ \ / \
4 8 12 16
更改为4=6=8=10=12=14=16
/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
1.将左子树构造成双链表,并返回链表头节点。
2.定位至左子树双链表最后一个节点。
3.如果左子树链表不为空的话,将当前root追加到左子树链表。
4.将右子树构造成双链表,并返回链表头节点。
5.如果右子树链表不为空的话,将该链表追加到root节点之后。
6.根据左子树链表是否为空确定返回的节点。
*/
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree==null)
return null;
if (pRootOfTree.left==null && pRootOfTree.right==null){
return pRootOfTree;
}
// 1.将左子树构造成双链表,并返回链表头节点
TreeNode left = Convert(pRootOfTree.left);
//2.定位至左子树双链表最后一个节点。
TreeNode pLeftLastNode = left;
while (pLeftLastNode!=null&&pLeftLastNode.right!=null){
//因为最后一个要么是叶子节点的右节点要么就是无右子树的左子树根节点
pLeftLastNode = pLeftLastNode.right;
}
// 3.如果左子树链表不为空的话,将当前root追加到左子树链表
if (left!=null){
pLeftLastNode.right = pRootOfTree;
pRootOfTree.left = pLeftLastNode;
}
// 4.将右子树构造成双链表,并返回链表头节点
TreeNode right = Convert(pRootOfTree.right);
// 5.如果右子树链表不为空的话,将该链表追加到root节点之后
if (right!=null){
pRootOfTree.right = right;
right.left = pRootOfTree;
}
return left!=null?left:pRootOfTree;
}

27 得到abc字符的全排列

/
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public ArrayList<String> Permutation(String str) {
ArrayList<String> arrayList = new ArrayList<String>();
HashSet<String> hashSet = new HashSet<String>();
if (str!=null && str.toCharArray().length>0){
PermutationHelper(str.toCharArray(),0,hashSet);
}
arrayList.addAll(hashSet);
Collections.sort(arrayList);
return arrayList;
}
public void PermutationHelper(char[] chars, int i, HashSet<String> hashSet) {
if (i==chars.length-1){
hashSet.add(new String(chars));
}else {
for (int j = i; j < chars.length; j++) {
swap(chars,i,j);
PermutationHelper(chars,i+1,hashSet);
swap(chars,i,j);
}
}
}
public void swap(char[] chars, int i, int j) {
if (i!=j){
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}

28 查找一个出现次数超过数组一半的数字

/
题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/*
时间复杂度为O(N)利用数组的特性来进行
在遍历数组时保存两个值:一是数组中一个数字,一是次数。
遍历下一个数字时,若它与之前保存的数字相同,则次数加1,否则次数减1;
若次数为0,则保存下一个数字,并将次数置为1。
遍历结束后,所保存的数字即为所求。然后再判断它是否符合条件即可。
*/
public int MoreThanHalfNum_Solution(int [] array) {
int result = array[0];
int times = 1;
if(array==null||array.length<=0){
return 0;
}
for (int i = 1; i < array.length; i++) {
if (times==0){
result = array[i];
times = 1;
}else if (array[i]==result){
times++;
}else {
times--;
}
}
times = 0;
for (int i = 0; i < array.length; i++) {
if (result==array[i]){
times++;
}
}
if (times*2 <= array.length)
result = 0;
return result;
}
/*
用HashMap O(N),用桶排序方法也可
*/
public int MoreThanHalfNum_Solution2(int [] array) {
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < array.length; i++) {
if (!map.containsKey(array[i])){
map.put(array[i],1);
}else {
int count = map.get(array[i]);
count++;
map.put(array[i],count);
}
}
Iterator iterator = map.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry entry = (Map.Entry) iterator.next();
int key = (int) entry.getKey();
int val = (int) entry.getValue();
if (val>array.length/2){
return key;
}
}
return 0;
}
/*
用快排思想,也就是找到中位数,时间复杂度过大
*/
public int MoreThanHalfNum_Solution3(int [] array) {
if (array.length<=0)
return 0;
int start = 0;
int end = array.length - 1;
int mid = (end-start)/2;
int index = partition(array,start,end);
while (index!=mid){
if (index>mid){
index = partition(array,start,index-1);
}else {
index = partition(array,index+1,end);
}
}
int result = array[mid];
int times = 0;
for (int i = 0; i < array.length; i++) {
if (result==array[i]){
times++;
}
}
if (times*2 <= array.length)
result = 0;
return result;
}
private int partition(int[] array, int start, int end) {
int flag = array[start];
int ff = start;
while (start!=end) {
while (array[end] >= flag && start < end) {
end--;
}
while (array[start] < flag && start < end) {
flag++;
}
if (start < end) {
int t = array[start];
array[start] = array[end];
array[end] = t;
}
}
int temp = array[start];
array[start] = flag;
array[ff] = temp;
return start;
}

29 找出数组中最小的k个数字

/
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。
/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
冒泡排序
*/
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> arrayList = new ArrayList<Integer>();
if (input.length<k)
return arrayList;
for (int i = 0; i < k; i++) {
for (int j = input.length-i-1; j >0 ; j--) {
if (input[j]<input[j-1]){
int temp = input[j];
input[j] = input[j-1];
input[j-1] = temp;
}
}
}
for (int j = 0; j < k; j++) {
arrayList.add(input[j]);
}
return arrayList;
}

30 寻找连续向量的最大值

/
题目描述
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。
今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。
但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},
连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住?(子向量的长度至少是1)
/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int FindGreatestSumOfSubArray(int[] array) {
if (array.length==0 || array==null)
return 0;
int curSum = 0;
int greatestSum = Integer.MIN_VALUE;
for (int i = 0; i < array.length; i++) {
if (curSum<0){
curSum = array[i];
}else {
curSum = curSum + array[i];
}
if (curSum>greatestSum){
greatestSum = curSum;
}
}
return greatestSum;
}

31 求一个范围内1出现的次数

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?
为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。
ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
//主要思路:设定整数点(如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)
*/
public int NumberOf1Between1AndN_Solution(int n) {
if (n<=0)
return 0;
int count = 0;
for (int i = 1; i <= n; i=i*10) {//i表示当前分析哪一个
int a = n/i;
int b = n%i;
if (a%10==1){
count+= b+1;
}
count+= (a+8)/10*i;
}
return count;
}

32 数组内所有数字拼在一起选出最小数

/
题目描述
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String PrintMinNumber(int [] numbers) {
ArrayList<Integer> arrayList = new ArrayList<>();
String s = "";
for (int i = 0; i < numbers.length; i++) {
arrayList.add(numbers[i]);
}
Collections.sort(arrayList,new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2) {
String str1 = o1 + "" + o2;
String str2 = o2 + "" + o1;
return str1.compareTo(str2);
}
});
for(int j:arrayList){
s+=j;
}
return s;
}

33 查找第N个丑数

/
题目描述
把只包含因子2、3和5的数称作丑数(Ugly Number)。
例如6、8都是丑数,但14不是,因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
该思路: 我们只用比较3个数:用于乘2的最小的数、用于乘3的最小的数,用于乘5的最小的
*/
public int GetUglyNumber_Solution(int index) {
if (index==0 || index==1)
return index;
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
int i2=0,i3=0,i5=0;
while (arrayList.size()<index){
int m2 = arrayList.get(i2)*2;
int m3 = arrayList.get(i3)*3;
int m5 = arrayList.get(i5)*5;
int min = Math.min(m2,Math.min(m3,m5));
arrayList.add(min);
if (min==m2){
i2++;
}
if (min==m3){
i3++;
}
if (min==m5){
i5++;
}
}
return arrayList.get(arrayList.size()-1);
}

34 找到字符串中只出现一次的字符

题目描述
在一个字符串(1<=字符串长度<=10000,全部由大写字母组成)中找到第一个只出现一次的字符,并返回它的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
HashMap法
*/
public int FirstNotRepeatingChar(String str) {
HashMap<Character,Integer> hashMap = new HashMap<Character, Integer>();
char c[] = str.toCharArray();
for (int i = 0; i < c.length; i++) {
if (hashMap.containsKey(c[i])){
int times = hashMap.get(c[i]);
hashMap.put(c[i],++times);
}else {
hashMap.put(c[i],1);
}
}
for (int i = 0; i < c.length; i++) {
if (hashMap.get(c[i])==1)
return c[i];
}
return -1;
}

35 求逆序对总数

/
题目描述
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围:
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2
10^5
输入例子:
1,2,3,4,5,6,7,0
输出例子:
7
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
归并排序的改进,把数据分成前后两个数组(递归分到每个数组仅有一个数据项),
合并数组,合并时,出现前面的数组值array[i]大于后面数组值array[j]时;
则前面数组array[i]~array[mid]都是大于array[j]的,count += mid+1 - i
*/
int cnt = 0;
public int InversePairs(int [] array) {
if (array==null)
return 0;
mergesort(array,0,array.length-1);
return cnt%1000000007;
}
public void mergesort(int[] array, int start, int end) {
if (start>=end)
return;
int mid = start+(end-start)/2;
mergesort(array,start,mid);
mergesort(array,mid+1,end);
merge(array,start,mid,end);
}
public void merge(int[] array, int start, int mid, int end) {
int []tmp = new int[end-start+1];
int i = start, j=mid+1,k=0;
while (i<=mid&&j<=end){
if (array[i]<array[j]){
tmp[k++] = array[i++];
}else {
tmp[k++] = array[j++];
cnt = cnt + mid - i + 1;
//防止测试例过大
if (cnt>1000000007)
cnt = cnt % 1000000007;
}
}
while (i<=mid){
tmp[k++] = array[i++];
}
while (j<=end){
tmp[k++] = array[j++];
}
for (int l = 0; l < tmp.length ; l++) {
array[start+l] = tmp[l];
}
}

36 找出链表的第一个公共点

题目描述
输入两个链表,找出它们的第一个公共结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
找出2个链表的长度,然后让长的先走两个链表的长度差,然后再一起走
(因为2个链表用公共的尾部)
*/
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1==null||pHead2==null)
return null;
int l1 = 1;
int l2 = 1;
ListNode ph1 = pHead1;
ListNode ph2 = pHead2;
while(ph1!=null){
ph1 = ph1.next;
l1++;
}
while(ph2!=null){
ph2 = ph2.next;
l2++;
}
if (l1>=l2){
int step = l1-l2;
while (step-->0){
pHead1 = pHead1.next;
}
}else {
int step = l2-l1;
while (step-->0){
pHead2 = pHead2.next;
}
}
while (pHead1!=null){
if (pHead1==pHead2)
return pHead1;
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
return pHead1;
}

37 统计一个数字在排序数组中出现的次数

题目描述
统计一个数字在排序数组中出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public int GetNumberOfK(int[] array, int k) {
int first = getFirstK( array, k, 0, array.length - 1 );
int end = getLastK( array, k, 0, array.length - 1 );
if (first!=-1 && end!=-1)
return end - first + 1;
else
return 0;
}
public int getFirstK(int[] array, int k, int start, int end) {
if (end < start)
return -1;
int mid = (start + end) >> 1;
if (k>array[mid]){
return getFirstK( array,k,mid+1,end );
}else if (k<array[mid]){
return getFirstK( array,k,start,mid-1 );
}else if (mid-1>=0 && array[mid-1]==k){
return getFirstK( array,k,start,mid-1 );
}else {
return mid;
}
}
public int getLastK(int[] array, int k, int start, int end) {
if (end < start)
return -1;
int mid = (start + end) >> 1;
if (k > array[mid]) {
return getLastK( array, k, mid + 1, end );
} else if (k < array[mid]) {
return getLastK( array, k, start, mid - 1 );
} else if (mid + 1 <= array.length - 1 && array[mid + 1] == k) {
return getLastK( array, k, mid + 1, end );
} else {
return mid;
}
}

38 求树的深度

/
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度
/

1
2
3
4
5
6
7
8
public int TreeDepth(TreeNode root) {
if (root==null)
return 0;
int nLeft = TreeDepth( root.left );
int nRight = TreeDepth( root.right );
return (nLeft > nRight ? nLeft+1 : nRight + 1);
}

39 判断树是否为平衡二叉树

题目描述
输入一棵二叉树,判断该二叉树是否是平衡二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public boolean IsBalanced_Solution(TreeNode root) {
if (root==null)
return true;
int left = TreeDepth( root.left );
int right = TreeDepth( root.right );
int diff = left -right;
if (diff>1 || diff <-1){
return false;
}
return IsBalanced_Solution( root.left ) && IsBalanced_Solution( root.right );
}
public int TreeDepth(TreeNode root) {
if (root==null)
return 0;
int nLeft = TreeDepth( root.left );
int nRight = TreeDepth( root.right );
return (nLeft > nRight ? nLeft+1 : nRight + 1);
}
//方法二只需遍历一次
//后续遍历时,遍历到一个节点,其左右子树已经遍历  依次自底向上判断,每个节点只需要遍历一次
private boolean isBalanced=true;
public boolean IsBalanced_Solution2(TreeNode root) {
getDepth(root);
return isBalanced;
}
public int getDepth(TreeNode root){
if(root==null)
return 0;
int left=getDepth(root.left);
int right=getDepth(root.right);
if(Math.abs(left-right)>1){
isBalanced=false;
}
return right>left ?right+1:left+1;
}

40 数组中只出现一次的两个数字

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
*/
int index = 0;
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int result = 0;
for (int i = 0; i < array.length; i++) {
result = result^array[i];
}
index = findBit1(result);
for (int i = 0; i < array.length; i++) {
if (hasBit1(array[i])){
num1[0] = num1[0]^array[i];
}else {
num2[0] = num2[0]^array[i];
}
}
}
public int findBit1(int a){
int temp = a;
while ((temp & 1)==0 && index<= 32){
temp = temp >> 1;
index++;
}
return index;
}
public boolean hasBit1(int a){
a = a >> index;
return (a & 1)==1;
}

41 求和为S的连续正数序列

题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。
但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。
现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
用两个数small、big分别表示序列的最小值和最大值,首先把small初始为1,big初始为2,如果small到big的和大于s,
就从序列中去掉最小的值,也就是增大small的值,如果small到big的和小于s,那么就增大big的值,又因为序列至少2个数,
所以small小于(s+1)/2。寻找small和big之间的序列和看是否满足条件即可。
*/
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>( );
if (sum < 3)
return arrayLists;
int small = 1;
int big = 2;
int mid = (sum+1)/2;
int curSum = small + big;
while (small<mid){
ArrayList<Integer> list = new ArrayList<>( );
if (curSum==sum){
for (int i = small ; i <= big; i++) {
list.add( i );
}
arrayLists.add( list );
}
while (curSum > sum && small < mid){
curSum = curSum - small;
small++;
if (curSum==sum){
for (int i = small ; i <= big; i++) {
list.add( i );
}
arrayLists.add( list );
}
}
big++;
curSum += big;
}
return arrayLists;
}

42 递增数组两个数和为S求乘积最小的两个数

题目描述
输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。(乘积最小的两个数就是离得最远的两个数)
输出描述:
对应每个测试案例,输出两个数,小的先输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
ArrayList<Integer> arrayList = new ArrayList<>( );
if (array==null || sum==0)
return arrayList;
int start = 0;
int end = array.length-1;
int curSum = array[start] + array[end];
while (start<=end) {
if (curSum == sum) {
arrayList.add( array[start] );
arrayList.add( array[end] );
break;
} else if (curSum > sum) {
end--;
} else {
start++;
}
curSum = array[start] + array[end];
}
return arrayList;
}

43 字符串移位

题目描述
汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。
对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,
要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
方法一直接翻转
*/
public String LeftRotateString2(String str,int n) {
if (str==null||n>str.length())
return "";
else {
char[] c = str.toCharArray();
StringBuffer sb = new StringBuffer();
for (int i = n; i < c.length; i++) {
sb.append( c[i] );
}
for (int i = 0; i < n; i++) {
sb.append( c[i] );
}
return sb.toString();
}
}
/*
方法二:三次翻转
*/
public String LeftRotateString(String str,int n) {
int l = str.length();
if (str==null||n>l)
return "";
char[] c = str.toCharArray();
swap( c,0,n-1 );
swap( c,n,c.length-1 );
swap( c,0,c.length-1 );
String s = new String( c );
return s;
}
public static void swap(char[] cArr,int front,int end){
while(front < end){
char tmp = cArr[end];
cArr[end] = cArr[front];
cArr[front] = tmp;
front++;
end--;
}
}

44 翻转字符串及每个单词

牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。
同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。
例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,
正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public String ReverseSentence(String str) {
char[] cArr = str.toCharArray();
//对整个字符串进行字符翻转
swap(cArr, 0, cArr.length - 1);
int begin = 0;
//对每个单词进行字符串翻转操作
for (int i = 1; i < cArr.length; i++){
if (cArr[i]==' '){
swap(cArr,begin,i-1);
begin = i+1;
}
}
swap(cArr,begin,cArr.length-1);
return new String(cArr);
}
public static void swap(char[] cArr,int front,int end){
while(front < end){
char tmp = cArr[end];
cArr[end] = cArr[front];
cArr[front] = tmp;
front++;
end--;
}
}

增:骰子各个点数出现的概率

题目:把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Problem43 {
public static void main(String[] args) {
Problem43 p=new Problem43();
p.printProbability(2);
}
public void printProbability(int number){
if(number<1)
return;
int gMaxValue=6;
int[][] probabilities=new int[2][];
probabilities[0]=new int[gMaxValue*number+1];
probabilities[1]=new int[gMaxValue*number+1];
int flag=0;
for(int i=1;i<gMaxValue;i++){
probabilities[flag][i]=1;
}
for(int k=2;k<=number;++k){
for(int i=0;i<k;i++){
probabilities[1-flag][i]=0;
}
for(int i=k;i<=gMaxValue*k;i++){
probabilities[1-flag][i]=0;
for(int j=1;j<=i&&j<=gMaxValue;j++)
probabilities[1-flag][i]+=probabilities[flag][i-j];
}
flag=1-flag;
}
double total=Math.pow(gMaxValue, number);
for(int i=number;i<gMaxValue*number;i++){
double ratio=(double)probabilities[flag][i]/total;
System.out.print(i+" ");
System.out.println(ratio);
}
}
}

45 判断带通配符序列的是否连续

题目描述
LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)..
.他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿!!
“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,
他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。
上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。
LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isContinuous(int [] numbers) {
if (numbers==null || numbers.length < 5)
return false;
Arrays.sort( numbers );
int numZero = 0;
int numGap = 0;
for (int i = 0; i < numbers.length&&numbers[i]==0; i++) {
numZero++;
}
int small = numZero;
int big = small + 1;
while (big < numbers.length){
if (numbers[small]==numbers[big])
return false;
numGap += numbers[big]-numbers[small]-1;
small=big;
big++;
}
return (numGap>numZero) ? false : true;
}

46 约瑟夫环

题目描述
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*
如果只求最后一个报数胜利者的话,我们可以用数学归纳法解决该问题,为了讨论方便,先把问题稍微改变一下,并不影响原意:
问题描述:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m%n的人开始):
k  k+1  k+2  ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
现在我们把他们的编号做一下转换:
k     --> 0
k+1   --> 1
k+2   --> 2
...
...
k-2   --> n-2
k-1   --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:
例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗?!!
变回去的公式很简单,相信大家都可以推出来:x'=(x+k)%n。
令f[i]表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n]。
递推公式
f[1]=0;
f[i]=(f[i-1]+m)%i;  (i>1)
有了这个公式,我们要做的就是从1-n顺序算出f[i]的数值,最后结果是f[n]。
因为实际生活中编号总是从1开始,我们输出f[n]+1。
*/
//递归法
public int LastRemaining_Solution2(int n, int m) {
if (n<1 || m < 1)
return -1;
if (n==1)
return 1;
else
return (LastRemaining_Solution2(n-1,m)+m)%n;
}
//循环法
public int LastRemaining_Solution(int n, int m) {
if (n<1 || m < 1)
return -1;
int last = 0;
for (int i = 2; i <= n ; i++) {
last = (last + m)% i;
}
return last;
}
//正常法
//数组来模拟环
public int LastRemaining_Solution3(int n, int m) {
if (n<1 || m <1)
return -1;
int []arrary = new int[n];
int i = -1,step = 0, count = n;
while (count>0){//跳出循环时将最后一个元素也设置为了-1
i++; //指向上一个被删除对象的下一个元素。
if (i>=n) //模拟环
i=0;
if (arrary[i]==-1)
continue; //跳过已经删除的对象
step++;
if (step==m){
arrary[i] = -1;
step = 0;
count--;
}
}
return i;
}
//运用ArrayList
public int LastRemaining_Solution4(int n, int m) {
if (n<1 || m < 1)
return -1;
ArrayList<Integer> arrayList = new ArrayList<>( );
for (int i = 0; i < n; i++) {
arrayList.add( i );
}
int index = -1;
while (arrayList.size()>1){
index = (index+m)%arrayList.size();
arrayList.remove( index );
index--;
}
return arrayList.get( 0 );
}

47 1+2+3+…+n不得使用判断条件及乘除法

题目描述
求1+2+3+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

1
2
3
4
5
6
7
8
9
/*
&&就是逻辑与,逻辑与有个短路特点,前面为假,后面不计算
*/
public int Sum_Solution(int n) {
int ans = n;
boolean a;
a= ans>=1 && (ans+=Sum_Solution( n-1 ))>=0;
return ans;
}

48 不用加法求两个数之和

题目描述
写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
首先看十进制是如何做的: 5+7=12,三步走
第一步:相加各位的值,不算进位,得到2。
第二步:计算进位值,得到10. 如果这一步的进位值为0,那么第一步得到的值就是最终结果。
第三步:重复上述两步,只是相加的值变成上述两步的得到的结果2和10,得到12。
同样我们可以用三步走的方式计算二进制值相加: 5-101,7-111
第一步:相加各位的值,不算进位,得到010,二进制每位相加就相当于各位做异或操作,101^111。
第二步:计算进位值,得到1010,相当于各位做与操作得到101,再向左移一位得到1010,(101&111)<<1。
第三步重复上述两步, 各位相加 010^1010=1000,进位值为100=(010&1010)<<1。
继续重复上述两步:1000^100 = 1100,进位值为0,跳出循环,1100为最终结果。
*/
public int Add(int num1,int num2) {
while (num2!=0){
int sum = num1^num2; //不考虑进位相加
int carry = (num1&num2)<<1; //进位
num1 = sum;
num2 = carry;
}
return num1;
}

49 字符串转为数字

题目描述
将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
输入描述:
输入一个字符串,包括数字字母符号,可以为空

输出描述:
如果是合法的数值表达则返回该数字,否则返回0

输入例子:
+2147483647
1a33

输出例子:
2147483647
0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int StrToInt(String str) {
if (str=="" || str.length()==0)
return 0;
int flag = 0;
char [] a = str.toCharArray();
if (a[0]=='-') {
flag = 1;
a[0] = '0';
}
if (a[0]=='+') {
a[0] = '0';
}
int sum = 0;
for (int i = 0; i < a.length; i++) {
if (a[i]>'9' || a[i]<'0')
return 0;
sum = sum*10 + a[i] - '0';
}
return flag==0?sum : sum*-1;
}

50 找出数组内任意一个重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个,赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
boolean[] k = new boolean[length];
for (int i = 0; i < length; i++) {
if (k[numbers[i]]==true){
duplication[0] = numbers[i];
return true;
}
k[numbers[i]] = true;
}
return false;
}

51 乘积数组的构建

题目描述
给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]A[i-1]A[i+1]A[n-1]。不能使用除法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]
由此可知B[i]可拆分成两部分,一部分为
C[i]=A[0]*A[1]*...*A[i-1];
D[i]=A[i+1]*...*A[n-1]。
B0 1 A1 A2 ... An-2 An-1
B1 A0 1 A2 ... An-2 An-1
B2 A0 A1 1 ... An-2 An-1
... A0 A1 ... 1 An-2 An-1
Bn-2 A0 A1 A2 ... 1 An-1
Bn-1 A0 A1 Aw ... An-2 1
又根据C[i]和D[i]的特性可以得知。
C[i]=C[i-1]*A[i-1]; //左下角部分
D[i]=D[i+1]*A[i+1]; //右上角部分
*/
public int[] multiply(int[] A) {
int len = A.length;
int forward[] = new int[len];
int backward[] = new int[len];
int B[] = new int[len];
forward[0] = 1;
backward[len-1] = 1;
//下三角求C
for (int i = 1 ; i < len; i++) {
forward[i] = forward[i-1]*A[i-1];
}
//上三角求D
for (int i = len-2; i>=0; i--) {
backward[i] = backward[i+1]*A[i+1];
}
for (int i = 0; i < len; i++) {
B[i] = forward[i] * backward[i];
}
return B;
}

52 正则表达式的匹配

题目描述
请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符,而’‘表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aaa”与模式”a.a”和”abaca”匹配,但是与”aa.a”和”ab*a”均不匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*
当模式中的第二个字符不是“*”时:
1、如果字符串第一个字符和模式中的第一个字符相匹配,那么字符串和模式都后移一个字符,然后匹配剩余的。
2、如果
字符串第一个字符和模式中的第一个字符相不匹配,直接返回false。
而当模式中的第二个字符是“*”时:
如果字符串第一个字符跟模式第一个字符不匹配,则模式后移2个字符,继续匹配。
如果字符串第一个字符跟模式第一个字符匹配,可以有3种匹配方式:
1、模式后移2字符,相当于x*被忽略;
2、字符串后移1字符,模式后移2字符;相当于匹配一个
3、字符串后移1字符,模式不变,即继续匹配字符下一位,因为*可以匹配多位;相当于匹配多位
这里需要注意的是:Java里,要时刻检验数组是否越界。
*/
public boolean match(char[] str, char[] pattern) {
if (pattern==null || str==null)
return false;
int strIndex = 0;
int patternIndex = 0;
return matchCore(str,strIndex,pattern,patternIndex);
}
private boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
//有效性检查二者都到达尾部,匹配成功
if (str.length==strIndex && pattern.length==patternIndex) {
return true;
}
//pattern先到尾部匹配失败
if (strIndex!=str.length && patternIndex==pattern.length)
return false;
//正则第二个字符是*,且字符串第1个跟正则第1个匹配,分3种匹配模式;
// 如不匹配,模式后移2位
if (patternIndex+1<pattern.length && pattern[patternIndex+1]=='*'){
if ((strIndex!=str.length && str[strIndex]==pattern[patternIndex])
||(strIndex!=str.length && pattern[patternIndex]=='.')){
//字符串第一个和正则第一个匹配
//模式忽略x*直接后移
return matchCore(str,strIndex,pattern,patternIndex+2)||
//字符后移1,正则后移2相当于只匹配一个
matchCore(str,strIndex+1,pattern,patternIndex+2)
//字符后移1,正则不懂,相当于匹配多个
||matchCore(str,strIndex+1,pattern,patternIndex);
}else{
return matchCore(str,strIndex,pattern,patternIndex+2);
}
}
//正则第二个字符不是*,如果第一个字符匹配,则都后移以为,否则返回false
if ((strIndex!=str.length && pattern[patternIndex]==str[strIndex])||
(strIndex!=str.length&&pattern[patternIndex]=='.')){
return matchCore(str,strIndex+1,pattern,patternIndex+1);
}
return false;
}

53 判断字符串是否用来表示数值

题目描述
请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public boolean isNumeric2(char[] str) {
//正则
String string = String.valueOf(str);
return string.matches("[\\+-]?[0-9]*(\\.[0-9]*)?([eE][\\+-]?[0-9]+)?");
}
public boolean isNumeric(char[] s) {
if (s == null)
return false;
if(s.length==0)
return false;
if((s.length==1)&&(s[0]<'0'||s[0]>'9'))
return false;
if(s[0]=='+'||s[0]=='-'){
if(s.length==2&&(s[1]=='.'))
return false;
}else if((s[0]<'0'||s[0]>'9')&&s[0]!='.')
return false;//首位既不是符号也不是数字还不是小数点,当然是false
int i = 1;
while((i<s.length)&&(s[i]>='0'&&s[i]<='9'))
i++;
if(i<s.length&&s[i]=='.'){
i++;
if(i>=s.length) return false;
while((i<s.length)&&(s[i]>='0'&&s[i]<='9'))
i++;
}
if(i<s.length&&(s[i]=='e'||s[i]=='E')){
i++;
if((i<s.length)&&(s[i]=='+'||s[i]=='-')){
i++;
if(i<s.length)
while((i<s.length)&&(s[i]>='0'&&s[i]<='9'))
i++;
else
return false;
}
else if(i<s.length){
while((i<s.length)&&(s[i]>='0'&&s[i]<='9')) i++;
}else return false;
}
if(i<s.length) return false;
return true;
}

54 找出字符流中第一个只出现一次的字符

题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符”go”时,第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时,第一个只出现一次的字符是”l”。
输出描述:
如果当前字符流没有存在出现一次的字符,返回#字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int hashtable[] = new int[256];
StringBuffer stringBuffer = new StringBuffer();
//Insert one char from stringstream
public void Insert(char ch)
{
stringBuffer.append(ch);
if (hashtable[ch]==0)
hashtable[ch]=1;
else
hashtable[ch] += 1;
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
char str[] = stringBuffer.toString().toCharArray();
for (char c : str) {
if (hashtable[c]==1)
return c;
}
return '#';
}

55 在一个有环链表中找到链表环的入口

题目描述
一个链表中包含环,请找出该链表的环的入口结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*
1.第一步,找环中相汇点。分别用p1,p2指向链表头部,p1每次走一步,p2每次走二步,
直到p1==p2找到在环中的相汇点。
2.第二步,找环的入口。
接上步,当p1==p2时,p2所经过节点数为2x,p1所经过节点数为x,
设环中有n个节点,p2比p1多走一圈有2x=n+x;n=x;
可以看出p1实际走了一个环的步数,再让p2指向链表头部,p1位置不变,p1,p2每次走一步直到p1==p2;
此时p1指向环的入口。
*/
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode meetNode = meetingNode(pHead);
if (meetNode==null)
return null;
//先找到走到相交结点时候走了多少部
ListNode l1 = pHead;
int step = 1;
while (l1.next!=meetNode){
step++;
l1 = l1.next;
}
//快指针先走一个环的步数
l1 = pHead;
for (int i = 0; i < step; i++) {
l1 = l1.next;
}
ListNode l2 = pHead;
while(l1!=l2){
l1 = l1.next;
l2 = l2.next;
}
return l1;
}
public ListNode meetingNode(ListNode pHead){
if (pHead==null)
return null;
ListNode pSlow = pHead.next;
if (pSlow==null)
return null;
ListNode pFast = pSlow.next;
while (pSlow!=null && pFast!=null){
if (pFast==pSlow)
return pFast;
pSlow = pSlow.next;
pFast = pFast.next;
if (pFast!=null)
pFast = pFast.next;//快指针走两步慢指针走一步
}
return null;
}

56 删除链表中重复的结点

题目描述
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode deleteDuplication(ListNode pHead) {
if (pHead==null)
return null;
if (pHead!=null&&pHead.next==null)
return pHead;
ListNode first = new ListNode(-1); //trick标志
first.next = pHead;
ListNode p = pHead;
ListNode last = first;
while (p!=null&&p.next!=null){
if (p.val==p.next.val){
int val = p.val;
while (p!=null&&p.val==val)
p = p.next;
last.next = p;
}else {
last = p;
p = p.next;
}
}
return first.next;
}

57 找出中序遍历的下一个结点

题目描述
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
a
/ \
b c
/ \ / \
d e f g
/ \
h i
中序遍历为 d,b,h,e,i,a,f,c,g
情况1:如结点b存在右孩子,他的下一个结点为右子树里面最左结点为h
情况2:结点d下一个结点为b,结点h下一个结点为e,i的下一个结点为a。
情况2总结起来就是向上遍历直到当前结点为父节点的左孩子结点
*/
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (pNode==null)
return null;
if (pNode.right!=null){//如果结点存在右子树就找右子树里面的最左结点
pNode = pNode.right;
while (pNode.left!=null){
pNode = pNode.left;
}
return pNode;
}
while(pNode.next!=null){//如果不存在右子树结点就找第一个当前结点为父结点左孩子的父节点
if (pNode.next.left==pNode)
return pNode.next;
pNode = pNode.next;
}
return null;//知道根节点也没有找到
}

58 判断二叉树是否是对称的

题目描述
请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
boolean isSymmetrical(TreeNode pRoot){
return isSymmetrical(pRoot,pRoot);
}
private boolean isSymmetrical(TreeNode pRoot, TreeNode pRoot1) {
if (pRoot==null&&pRoot1==null)
return true;
if (pRoot==null||pRoot1==null)
return false;
if (pRoot.val!=pRoot1.val)
return false;
return isSymmetrical(pRoot.left,pRoot1.right)
&&isSymmetrical(pRoot.right,pRoot1.left);
}

59 之字形打印二叉树

题目描述
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
*/
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
if (pRoot==null)
return arrayLists;
ArrayList<Integer> arrayList = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
int start=0,end = 1;
boolean leftToRght = true;
while (!queue.isEmpty()){
TreeNode p = queue.poll();
arrayList.add(p.val);
start++;
if (p.left!=null)
queue.add(p.left);
if (p.right!=null)
queue.add(p.right);
if (start==end){
end = queue.size();
start = 0;
if (leftToRght) {
arrayLists.add(arrayList);
}
if (!leftToRght){
arrayLists.add(reverse(arrayList));
}
leftToRght=!leftToRght;
arrayList = new ArrayList<>();
}
}
return arrayLists;
}
public ArrayList<Integer> reverse(ArrayList<Integer> arrayList) {
int len = arrayList.size();
ArrayList<Integer> reverseArrayList = new ArrayList<>();
for (int i = len-1; i >=0 ; i--) {
reverseArrayList.add(arrayList.get(i));
}
return reverseArrayList;
}

60 层序打印二叉树

题目描述
从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
if (pRoot==null)
return arrayLists;
ArrayList<Integer> arrayList = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
int start=0,end = 1;
while (!queue.isEmpty()){
TreeNode p = queue.poll();
arrayList.add(p.val);
start++;
if (p.left!=null)
queue.add(p.left);
if (p.right!=null)
queue.add(p.right);
if (start==end){
end = queue.size();
start = 0;
arrayLists.add(arrayList);
arrayList = new ArrayList<>();
}
}
return arrayLists;
}

61 序列化反序列化二叉树

题目描述
请实现两个函数,分别用来序列化和反序列化二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int index = -1;
String Serialize(TreeNode root) {
StringBuffer stringBuffer = new StringBuffer( );
if (root==null){
stringBuffer.append( "#," );
return stringBuffer.toString();
}
stringBuffer.append( root.val + "," );
stringBuffer.append( Serialize( root.left ) );
stringBuffer.append( Serialize( root.right ) );
return stringBuffer.toString();
}
TreeNode Deserialize(String str) {
index++;
int len = str.length();
if (index>=len)
return null;
String []strr = str.split( "," );
TreeNode node = null;
if (!strr[index].equals( "#" )){
node = new TreeNode( Integer.valueOf( strr[index] ) );
node.left = Deserialize(str);
node.right = Deserialize(str);
}
return node;
}

62 寻找儿茶搜索树第K大的结点

题目描述
给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
中序遍历得到的就是一个递增序列,只要我们按照中序遍历,第K个元素就是我们要找的元素
*/
int index = 0;//计数器
TreeNode KthNode(TreeNode pRoot, int k) {
if (pRoot==null||k<=0)
return null;
if (pRoot!=null){
TreeNode node = KthNode( pRoot.left,k );
if (node!=null)
return node;
index++;
if (index==k)
return pRoot;
node = KthNode( pRoot.right,k );
if (node!=null)
return node;
}
return null;
}

63 大顶堆小顶堆综合求数据流的中位数

题目描述
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
Java的PriorityQueue是从JDK1.5开始提供的新的数据结构接口,默认内部是自然排序,结果为小顶堆,
也可以自定义排序器,比如下面反转比较,完成大顶堆。
思路:为了保证插入新数据和取中位数的时间效率都高效,这里使用大顶堆+小顶堆的容器,并且满足:
1、两个堆中的数据数目差不能超过1,这样可以使中位数只会出现在两个堆的交接处;
2、大顶堆的所有数据都小于小顶堆,这样就满足了排序要求。
*/
private int count = 0;
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}});
public void Insert(Integer num) {
if (count %2 == 0) {//当数据总数为偶数时,新加入的元素,应当进入小根堆        
// (注意不是直接进入小根堆,而是经大根堆筛选后取大根堆中最大元素进入小根堆)        
// 1.新加入的元素先入到大根堆,由大根堆筛选出堆中最大的元素
maxHeap.offer(num);
int filteredMaxNum = maxHeap.poll();
//2.筛选后的【大根堆中的最大元素】进入小根堆        
minHeap.offer(filteredMaxNum);
} else {//当数据总数为奇数时,新加入的元素,应当进入大根堆        
// (注意不是直接进入大根堆,而是经小根堆筛选后取小根堆中最大元素进入大根堆)
//1.新加入的元素先入到小根堆,由小根堆筛选出堆中最小的元素        
minHeap.offer(num);
int filteredMinNum = minHeap.poll();
//2.筛选后的【小根堆中的最小元素】进入小根堆
maxHeap.offer(filteredMinNum);
}
count++;
}
public Double GetMedian() {
if (count %2 == 0) {
return new Double((minHeap.peek() + maxHeap.peek())) / 2;
} else {
return new Double(minHeap.peek());
}
}

64 滑动窗口的最大值

题目描述
给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
队列序可以从两端删除元素,因此使用双端队列。
 *     原则: *     对新来的元素k,将其与双端队列中的元素相比较
 *     1)前面比k小的,直接移出队列(因为不再可能成为后面滑动窗口的最大值了!),
 *     2)前面比k大的X,比较两者下标,判断X是否已不在窗口之内,不在了,直接移出队列
 *     队列的第一个元素是滑动窗口中的最大值
*/
public ArrayList<Integer> maxInWindows(int [] num, int size) {
ArrayList<Integer> res = new ArrayList<>( );
if (size==0)
return res;
int begin;
ArrayDeque<Integer> q = new ArrayDeque<>( );
for (int i = 0; i < num.length; i++) {
begin = i - size + 1;
if (q.isEmpty())
q.add( i );
else if (begin>q.peekFirst())
q.pollFirst();//清除前端过期不在滑动窗口内的元素
while ((!q.isEmpty()) && num[q.peekLast()]<=num[i])
q.pollLast(); //去掉前面小于后面值的前端元素,因为前面值不可能是滑动窗口的最大元素了
q.add( i );//最大数下标加入队列
if (begin>=0)
res.add( num[q.peekFirst()] );
}
return res;
}
/*
 * 思路:滑动窗口应当是队列,但为了得到滑动窗口的最大值,
队列序可以从两端删除元素,因此使用双端队列。
 *     原则: *     对新来的元素k,将其与双端队列中的元素相比较
 *     1)前面比k小的,直接移出队列(因为不再可能成为后面滑动窗口的最大值了!),
 *     2)前面比k大的X,比较两者下标,判断X是否已不在窗口之内,不在了,直接移出队列
 *     队列的第一个元素是滑动窗口中的最大值
*/
public ArrayList<Integer> maxInWindows2(int [] num, int size)
{
ArrayList<Integer> ret = new ArrayList<>();
if (num == null) {
return ret;
}
if (num.length < size || size < 1) {
return ret;
}
LinkedList<Integer> indexDeque = new LinkedList<>();
for (int i = 0; i < size - 1; i++) {
while (!indexDeque.isEmpty() && num[i] > num[indexDeque.getLast()]) {
indexDeque.removeLast();
}
indexDeque.addLast(i);
}
for (int i = size - 1; i < num.length; i++) {
while (!indexDeque.isEmpty() && num[i] > num[indexDeque.getLast()]) {
indexDeque.removeLast();
}
indexDeque.addLast(i);
if (i - indexDeque.getFirst() + 1 > size) {
indexDeque.removeFirst();
}
ret.add(num[indexDeque.getFirst()]);
}
return ret;
}

65 回溯判断矩阵内是否存在符合条件的字符串路径

题目描述
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如[a b c e s f c s a d e e]是3*4矩阵,其包含字符串”bcced”的路径,但是矩阵中不包含“abcb”路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
用一个状态数组保存之前访问过的字符,然后再分别按上,下,左,右递归,找不到就回溯
*/
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
int flag[] = new int[matrix.length];
for(int i=0;i<rows;i++){
for (int j = 0; j<cols; j++){
if(helper(matrix,rows,cols,i,j,str,0,flag))
return true;
}
}
return false;
}
public boolean helper(char[] matrix, int rows, int cols, int i, int j, char[] str, int k, int[] flag) {
int index = i*cols + j;
if(i<0||i>=rows||j<0||j>=cols||matrix[index]!=str[k]||flag[index]==1){//不符合条件或者是该格子字符不是要找的,或者该格子已经走过
return false;
}
//如果该格子是下一个要找的
if(k==str.length - 1)//长度达到要找的长度,证明全找到路径存在
return true;
//没有到达末尾
flag[index] = 1;
//判断下一步上下左右能否找到,分别在上下左右寻找
if(helper(matrix,rows,cols,i-1,j,str,k+1,flag)
||helper(matrix,rows,cols,i+1,j,str,k+1,flag)
||helper(matrix,rows,cols,i,j-1,str,k+1,flag)
||helper(matrix,rows,cols,i,j+1,str,k+1,flag)
){
return true;
}
//如果找不到回溯
flag[index] = 0;
return false;
}

66 判断机器人能走到多少个格子

题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public int movingCount(int threshold, int rows, int cols)
{
int flag[][] = new int[rows][cols];
return helper(0,0,rows,cols,flag,threshold);
}
/*
递归思想走下去
*/
public int helper(int i,int j,int rows,int cols,int flag[][],int threshold){
int count = 0;
//首先判断是否在超过边界,或者不满足条件,或者已经走过
if(threshold<=0||i<0||i>=rows||j<0||j>=cols||(sum(i)+sum(j))>threshold||flag[i][j]==1)
return 0;
//如果一切符合条件变为1表示已经走过
flag[i][j] = 1;
//当前步加上向其他4个方向各能走的步数
count = helper(i+1,j,rows,cols,flag,threshold)
+helper(i-1,j,rows,cols,flag,threshold)
+helper(i,j+1,rows,cols,flag,threshold)
+helper(i,j-1,rows,cols,flag,threshold)+1;
return count;
}
//判断位数之和
public int sum(int i){
int sum = 0;
while(i>0){
sum += i%10;
i = i/10;
}
return sum;
}

坚持原创技术分享,您的支持将鼓励我继续创作!