剑指Offer 解题报告

张天宇 on 2020-06-18

剑指Offer解题报告,记录一些题目的解法。

常用集合的复杂度

Data Structure 新增 查询/Find 删除/Delete GetByIndex
数组 Array (T[]) O(n) O(n) O(n) O(1)
链表 Linked list (LinkedList) O(1) O(n) O(n) O(n)
Resizable array list (List) O(1) O(n) O(n) O(1)
Stack (Stack) O(1) - O(1) -
Queue (Queue) O(1) - O(1) -
Hash table (Dictionary<K,T>) O(1) O(1) O(1) -
Tree-based dictionary(SortedDictionary<K,T>) O(log n) O(log n) O(log n) -
Hash table based set (HashSet) O(1) O(1) O(1) -
Tree based set (SortedSet) O(log n) O(log n) O(log n) -

二叉搜索树的后序遍历序列

题目大意

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

解题思路

左子树,右子树,根。左子树都小于根,右子树都大于根,来判断。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if (sequence.length == 0) return false;
return isLegal(sequence, 0, sequence.length-1);
}
public boolean isLegal(int [] sequence, int start, int end){
if (start == end) return true;
int mid = start;
while (sequence[mid++] < sequence[end] && mid < end);
int tmp = mid;
while (sequence[tmp++] > sequence[end] && tmp < end);
if (tmp < end) return false;
if (mid == start || mid == end){
return isLegal(sequence, start, end-1);
} else {
return isLegal(sequence, start, mid-1) && isLegal(sequence, mid, end-1);
}
}
}

斐波那契数列

解题思路

之前用数组做的,需要开辟空间,这次用常数空间又做了一遍。

代码

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int Fibonacci(int n) {
int a = 0, b = 1,result = 0;
for (int i = 2; i <= n; i++){
result = a + b;
a = b;
b = result;
}
return n >= 2? result : n;
}
}

从尾到头打印链表

题目大意

输入一个链表,按链表从尾到头的顺序返回一个ArrayList。

解题思路

递归,栈,函数反转。

代码

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
// 递归
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
if (listNode != null){
if (listNode.next != null){
list = printListFromTailToHead(listNode.next);
}
list.add(listNode.val);
}
return list;
}
}
// 函数反转
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
while (listNode != null){
list.add(listNode.val);
listNode = listNode.next;
}
Collections.reverse(list);
return list;
}
}
// 栈
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
while (listNode != null){
stack.push(listNode.val);
listNode = listNode.next;
}
while (!stack.isEmpty()){
list.add(stack.pop());
}
return list;
}
}

正则表达式匹配

题目大意

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

解题思路

当模式中的第二个字符不是“*”时:

  1. 如果字符串第一个字符和模式中的第一个字符相匹配,那么字符串和模式都后移一个字符,然后匹配剩余的。
  2. 如果字符串第一个字符和模式中的第一个字符相不匹配,直接返回false。

而当模式中的第二个字符是“*”时:

如果字符串第一个字符跟模式第一个字符不匹配,则模式后移2个字符,继续匹配。如果字符串第一个字符跟模式第一个字符匹配,可以有3种匹配方式:

  1. 模式后移2字符,相当于x*被忽略;
  2. 字符串后移1字符,模式后移2字符;
  3. 字符串后移1字符,模式不变,即继续匹配字符下一位,因为*可以匹配多位;

这里需要注意的是:Java里,要时刻检验数组是否越界。

代码

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
public class Solution {
public boolean match(char[] str, char[] pattern) {
if (str == null || pattern == null) {
return false;
}
int strIndex = 0, patternIndex = 0;
return matchCore(str, strIndex, pattern, patternIndex);
}

public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
// 有效性检验,str到尾,pattern到尾,匹配成功
if (strIndex == str.length && patternIndex == pattern.length) {
return true;
}
// pattern先到尾,匹配失败
if (strIndex != str.length && patternIndex == pattern.length) {
return false;
}
// 模式第二个是*,且字符串第一个跟模式第一个匹配,分三种匹配模式;
if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
|| (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex, pattern, patternIndex + 2) // 模式后移两位,即X*匹配空串
|| matchCore(str, strIndex + 1, pattern, patternIndex + 2) // 模式匹配了一个字符
|| matchCore(str, strIndex + 1, pattern, patternIndex); // *匹配了一个,但是str中不止一个
} else {
return matchCore(str, strIndex, pattern, patternIndex + 2);
}
}
// 模式第2个不是*,且字符串第1个跟模式第1个匹配,则都后移1位,否则直接返回false
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
|| (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
}
return false;
}
}

表示数值的字符串

题目大意

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

解题思路

  1. 函数AC大法
  2. 枚举
  3. 正则表达式(晕)

代码

1
2
3
4
5
6
7
8
9
10
public class Solution {
public boolean isNumeric(char[] str) {
try {
double re = Double.parseDouble(new String(str));
} catch (NumberFormatException e) {
return false;
}
return true;
}
}
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
public class Solution {
public boolean isNumeric(char[] str) {
if (str.length == 0)
return false;
// +-。E出现的标志
boolean sign = false, deciminal = false, hasE = false;
for (int i = 0; i < str.length; i++) {
if (str[i] == 'e' || str[i] == 'E') {
if (i == 0)
return false; // 指数符号前必须有整数
if (i == str.length - 1)
return false; // 指数符号后必须有证书
if (hasE)
return false; // 只能有一个指数符号
hasE = true;
} else if (str[i] == '.') {
if (hasE)
return false; // 小数点只能出现在指数符号之前
if (i == str.length - 1)
return false; // 小数点不能出现在最后一位上
if (deciminal)
return false; // 小数点只能出现一次
deciminal = true;
} else if (str[i] == '+' || str[i] == '-') {
if (!sign && i != 0 && !hasE)
return false; // 第一次出现+''-'符号只能在第一个字符或者指数符号后
if (sign && !hasE)
return false; // 第二出现'+''-'符号只能在指数符号后
if (i == str.length - 1)
return false; // '+''-'符号不能出现在最后一位上
sign = true;
} else if (str[i] < '0' || str[i] > '9')
return false; // 其它的非数字字符
}
return true;
}
}
1
2
3
4
5
6
7
8
import java.util.regex.Pattern;
public class Solution {
public static boolean isNumeric(char[] str) {
String pattern = "^[-+]?\\d*(?:\\.\\d*)?(?:[eE][+\\-]?\\d+)?$";
String s = new String(str);
return Pattern.matches(pattern,s);
}
}

数组中的逆序对

题目大意

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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。

解题思路

这道题稍微有点麻烦,看题解时候一度自闭,这里引用高赞答案的代码加以解释。

这里将数组的分解和合并作为两个阶段来分析。以{7,5,6,4}为例来分析统计算法逆序对的过程,先比较相邻的两个数字,如下图:

  1. 把长度为4的数组分解为两个长度为2的子数组;
  2. 把长度为2的数组分解为两个长度为1的子数组;
  3. 把长度为1的子数组合并排序并统计逆序对;
  4. 把长度为2的子数组合并排序并统计逆序对。

继续以上图为例,在ab两个步骤中,将数组最终分解为4个长度为1的子数组。

进入数组合并阶段,c中存在75、64两对逆序数对。两组统计完毕,将两对统计合并(这里之所以可以合并是因为内部已经确定了逆序对数目,因此直接判断两边合并后的组合起来的逆序数对即可)并排序(防止重复统计)。

c->d这个步骤,先定义两个指针分别指向两个数组的最后一个元素,进行比较,因为两个数组都为升序数组,因此如果左边的最后一个元素大于右边最后一个元素,那么该元素与右边数组每个元素都可以组成逆序数对。否则的话右边元素的指针往右移,检查比较小的元素是否符合逆序对的要求。

这里在每次比较时候都顺便将较大的元素从后往前插入到一个辅助数组中,目的是为了用有序的数组覆盖之前的数组。因为算法的整个执行过程相当于一次自底向上合并的过程。因此合并算法可以看作一个递归算法,逐渐将所有数组合并到一起。

代码

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
public class Solution {
private int count = 0;
public int InversePairs(int[] a) {
if (a == null || a.length == 0)
return -1;
mergeSort(a, 0, a.length - 1);
return count;
}
// 递归分解,分解到不可分解时候,进入合并阶段。
public void mergeSort(int[] a, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
}
// 合并阶段,从两个数组的最右侧开始比较,比较计数之后将较大元素依次插入拷贝数组,最后覆盖原数组,有点归并排序的意思。
public void merge(int[] a, int left, int mid, int right) {
int[] tmp = new int[right - left + 1];
int t = right - left;
int l = mid;
int r = right;
while (l >= left && r >= mid + 1) {
if (a[l] > a[r]) {
count += (r - mid);
tmp[t--] = a[l--];
if (count >= 1000000007) {
count %= 1000000007;
}
} else {
tmp[t--] = a[r--];
}
}
while (l >= left) {
tmp[t--] = a[l--];
}
while (r >= mid + 1) {
tmp[t--] = a[r--];
}
for (int i = 0; i <= right - left; i++) {
a[left + i] = tmp[i];
}
}
}

机器人的运动范围

题目大意

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

解题思路

将地图全部置0,遍历能够到达的点,将遍历的点置1并令计数+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
public class Solution {
int count = 0;
public int movingCount(int threshold, int rows, int cols){
int[][] arrays = new int[rows][cols];
findWay(arrays, 0, 0, threshold);
return count;
}
public void findWay(int[][] arrays, int i, int j, int k){
if (i <0 || j < 0 || i >= arrays.length || j >= arrays[0].length)
return;
if (getSum(i)+getSum(j)>k || arrays[i][j] != 0) return;
arrays[i][j] = 1;
count++;
findWay(arrays, i+1, j, k);
findWay(arrays, i, j+1, k);
}
public int getSum(int i){
int result = 0;
while (i!=0){
result += i%10;
i/=10;
}
return result;
}
}

把二叉树打印成多行

题目大意

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

解题思路

层次入队,并记录下当前层次的长度,方便区分层次进入下一层。

代码

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 class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
Queue<TreeNode> queue = new LinkedList<>();
if (pRoot == null) return result;
queue.offer(pRoot);
int length = 1;
while (!queue.isEmpty()){
ArrayList<Integer> rs = new ArrayList<>();
int t_l = 0, l = 0;
while (t_l++ < length){
TreeNode temp = queue.poll();
rs.add(temp.val);
if (temp.left != null) {
queue.offer(temp.left);
l++;
}
if (temp.right != null) {
queue.offer(temp.right);
l++;
}
}
result.add(rs);
length = l;
}
return result;
}
}

链表中环的入口节点

题目大意

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

解题思路

设置快慢指针,都从链表头出发,快指针每次走两步,慢指针一次走一步,假如有环,一定相遇于环中某点(结论1)。接着让两个指针分别从相遇点和链表头出发,两者都改为每次走一步,最终相遇于环入口(结论2)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode fast = pHead, low = pHead;
while (fast != null && fast.next != null) {
fast = fast.next.next;
low = low.next;
if (fast == low)
break;
}
if (fast == null || fast.next == null)
return null;
low = pHead;
while (fast != low) {
fast = fast.next;
low = low.next;
}
return fast;
}
}

左旋转字符串

题目大意

字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。

解题思路

直接调用函数,或两次翻转字符串,即$YX=(X^TY^T)^T$。

代码

1
2
3
4
5
6
public class Solution {
public String LeftRotateString(String str,int n) {
if (n>=str.length()) return str;
return str.substring(n)+str.substring(0,n);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public String LeftRotateString(String str,int n) {
if (n>=str.length()) return str;
char[] arrays = str.toCharArray();
for (int i = 0, j = n-1; i < j; i++, j--) swap(arrays, i,j);
for (int i = n, j = str.length()-1; i < j; i++, j--) swap(arrays, i,j);
for (int i = 0, j = str.length()-1; i < j; i++, j--) swap(arrays, i,j);
return new String(arrays);
}
public void swap(char[] a, int left, int right){
char t = a[left];
a[left] = a[right];
a[right] = t;
}
}
1
2
3
4
5
6
7
8
9
10
// 一种只需要切割一次的方法
public class Solution {
public String LeftRotateString(String str,int n) {
int length = str.length();
if (length == 0) return "";
n %= length;
str+=str;
return str.substring(n, n+length);
}
}

和为S的连续正数序列

题目大意

输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序

解题思路

滑动窗口,注意都往一个方向滑。本题要求都是正整数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
int low = 1, high =2;
while (high > low){
int cur = (high + low) * (high - low + 1) / 2;
if (sum == cur){
ArrayList<Integer> rs = new ArrayList<>();
for (int i = low; i<=high; i++){
rs.add(i);
}
result.add(rs);
low++;
} else if (sum > cur){
high++;
} else if (sum < cur){
low++;
}
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
string LeftRotateString(string str, int n)
{
int len = str.size();
if(len == 0) return str;
n %= len;
for(int i = 0, j = n - 1; i < j; ++i, --j) swap(str[i], str[j]);
for(int i = n, j = len - 1; i < j; ++i, --j) swap(str[i], str[j]);
for(int i = 0, j = len - 1; i < j; ++i, --j) swap(str[i], str[j]);
return str;
}
};

数字在排序数组中出现的次数

题目大意

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

解题思路

因为data中都是整数,所以可以稍微变一下,不是搜索k的两个位置,而是搜索k-0.5和k+0.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
25
26
27
public class Solution {
public int GetNumberOfK(int [] array , int k) {
return biSearch(array, k+0.5)-biSearch(array, k-0.5);
}
// 循环写法
public int biSearch(int[] array, double k){
int s = 0, e = array.length-1;
while (s <= e){
if (k > array[s+(e-s)/2]){
s = s+(e-s)/2+1;
} else {
e = s+(e-s)/2-1;
}
}
return s;
}
// 递归写法
public int bi(int [] array, int l, int r, double k){
if (l == r) return l;
int mid = (l + r) / 2;
if (array[mid] > k){
return bi(array, l, mid - 1, k);
} else {
return bi(array, mid, r, k);
}
}
}

整数中1出现的次数(从1到n整数中1出现的次数)

题目大意

求出1 ~ 13的整数中1出现的次数,并算出100 ~ 1300的整数中1出现的次数?为此他特别数了一下1 ~ 13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。

解题思路

硬解,这道题主要是循环时候的变量使用错误。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int resu = 0;
for (int i = 0; i <= n; i++) {
int t = i;
while (t != 0) {
if (t % 10 == 1)
resu++;
t /= 10;
}
}
return resu;
}
}

最小的K个数

题目大意

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

解题思路

用最大堆保存这k个数,每次只和堆顶比,如果比堆顶小,删除堆顶,新数入堆。

参考

代码

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
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
int length = input.length;
if (k > length || k == 0) {
return result;
}
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 < length; i++) {
if (maxHeap.size() != k) {
maxHeap.offer(input[i]);
} else if (maxHeap.peek() > input[i]) {
maxHeap.poll();
maxHeap.offer(input[i]);
}
}
for (Integer integer : maxHeap) {
result.add(integer);
}
return result;
}
}

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

题目大意

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

解题思路

  1. 我的提交,直接给对应位置计数,有超过的就输出,没有就是0。这样好像对给定数组的大小要有一定的预判,这题属于巧合。
  2. 采用阵地攻守的思想:第一个数字作为第一个士兵,守阵地;count = 1;遇到相同元素,count++;遇到不相同元素,即为敌人,同归于尽,count–;当遇到count为0的情况,又以新的i值作为守阵地的士兵,继续下去,到最后还留在阵地上的士兵,有可能是主元素。再加一次循环,记录这个士兵的个数看是否大于数组一般即可。
  3. 数组排序后,如果符合条件的数存在,则一定是数组中间那个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
int a[10] = {0};
int half = numbers.size() / 2;
for (auto num : numbers) {
a[num]++;
if (a[num] > half) return num;
}
return 0;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int len = array.length;
if (len == 0) return 0;
int num = array[0], count=1;
for (int i = 1; i < len; i++){
if (array[i] == num) count++;
else count--;
if (count == 0){
num = array[i];
count = 1;
}
}
count = 0;
for (int i = 0; i < len; i++){
if (array[i]==num) count++;
}
return count*2>len?num:0;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers){
// 因为用到了sort,时间复杂度O(NlogN),并非最优
if(numbers.empty()) return 0;
sort(numbers.begin(),numbers.end()); // 排序,取数组中间那个数
int middle = numbers[numbers.size()/2];
int count=0; // 出现次数
for(int i=0;i<numbers.size();++i){
if(numbers[i]==middle) ++count;
}
return (count>numbers.size()/2) ? middle : 0;
}
};

二叉搜索树与双向链表

题目大意

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

解题思路

中序递归遍历,因为中序之后就是升序,每次把节点移动到head的左边。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//直接用中序遍历
public class Solution {
TreeNode head = null;
TreeNode realHead = null;
public TreeNode Convert(TreeNode pRootOfTree) {
ConvertSub(pRootOfTree);
return realHead;
}

private void ConvertSub(TreeNode pRootOfTree) {
if(pRootOfTree==null) return;
ConvertSub(pRootOfTree.left);
if (head == null) {
head = pRootOfTree;
realHead = pRootOfTree;
} else {
head.right = pRootOfTree;
pRootOfTree.left = head;
head = pRootOfTree;
}
ConvertSub(pRootOfTree.right);
}
}

复杂链表的复制

题目大意

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针random指向一个随机节点),请对此链表进行深拷贝,并返回拷贝后的头结点。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

解题思路

代码

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 class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null) {
return null;
}
RandomListNode currentNode = pHead;
// 1.复制每个节点,如复制A得到A1,将节点A1插到A后面
while (currentNode != null) {
RandomListNode cloneNode = new RandomListNode(currentNode.label);
RandomListNode nextNode = currentNode.next;
cloneNode.next = nextNode;
currentNode.next = cloneNode;
currentNode = nextNode;
}
currentNode = pHead;
// 2.重新遍历链表,复制了老节点的随即指针给新结点,如A1.random = A.random
while (currentNode != null) {
currentNode.next.random = currentNode.random == null ? null : currentNode.random.next;
currentNode = currentNode.next.next;
}
// 3. 拆分链表,将链表拆分为原链表和复制后的链表
currentNode = pHead;
RandomListNode pCloneHead = pHead.next;
while (currentNode != null) {
RandomListNode cloneNode = currentNode.next;
currentNode.next = cloneNode.next;
cloneNode.next = cloneNode.next == null ? null : cloneNode.next.next;
currentNode = currentNode.next;
}
return pCloneHead;
}
}

旋转数组的最小数字

题目大意

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

解题思路

  • 最直接的方法是使用 暴力法:搜索整个数组,找到其中的最小元素,这样的时间复杂度是 O(N),其中 N 是给定数组的大小。

  • 这道题目可以使用 二分搜索 的思想进行解决。

    • 找到数组的中间元素 mid。
    • 如果中间元素 > 数组第 low 个元素,则在 mid 右边搜索变化点。
    • 如果中间元素 < 数组第 high 个元素,则在 mid 左边搜索变化点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int findMin(int[] nums) {
int low = 0, high = nums.length - 1;
while (low < high) {
if (nums[low] < nums[high]) return nums[low];
int mid = low + (high - low) / 2;
if (nums[mid] > nums[high]){
low = mid + 1;
} else{
high = mid;
}
}
return nums[low];
}
}

替换空格

题目大意

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

解题思路

  • 直接调用函数

  • 从前往后依次遍历字符串,遇到空格替换即可。使用这种解法在每一次碰到空格字符的时候都做替换,并且由于是把 1 个字符替换成 3 个字符,那么每次替换一个空格后都需要把空格后面所有的字符都后移两个字节,否则就有两个字符被覆盖。假设字符串的长度是 n 。对每个空格字符,需要移动后面 O(n) 个字符,因此对含有 O(n) 个空格字符的字符串而言总的时间复杂度是 O(n^2) 。

  • 首先遍历一次字符串,统计出字符串中空格的总数,同时计算出替换之后的字符串的总长度。接下来,定义两个指针:P1P2

    其中指针 P1 指向原始字符串的末尾,指针 P2 指向替换之后的字符串的末尾。然后将指针 P1 向前移动,逐个把它指向的字符复制到指针 P2 指向的位置。当碰到空格的时候,指针 P1 先不动,挪动指针 P2 的位置并赋值 %20 ,然后再同时向前移动并复制。

  • 在解法二的基础上重新开辟 一个新的数组进行数据的存放。

  • 我提交的解法,遇到空格就追加。

代码

1
2
3
4
5
public class Solution {
public String replaceSpace(StringBuffer str) {
return str.toString().replaceAll("\\s", "%20");
}
}
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 class Solution {
public String replaceSpace(StringBuffer str) {
String str1 = str.toString();
if(str1.equals(""))
return str1;
char [] strArray = str1.toCharArray();
int i =0;
int lengthSpace = 0;
while(i < strArray.length){
if(strArray[i] == ' ')
lengthSpace++;
i++;
}
int newStrLength = strArray.length + lengthSpace*2;
char [] newStr = new char[newStrLength];
int j = newStrLength-1;
i = strArray.length - 1;
while(i >= 0){
if(strArray[i] != ' '){
newStr[j--] = strArray[i--];
}else{
newStr[j--] = '0';
newStr[j--] = '2';
newStr[j--] = '%';
i--;
}
}
return new String(newStr);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public static String replaceSpace(StringBuffer str) {
String str_to = str.toString();
String result = "";
for (int i = 0; i < str_to.length(); i++) {
if (str_to.charAt(i) == ' ')
result += "%20";
else
result += str_to.charAt(i);
}
return result;
}
}

二维数组中的查找

题目大意

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

解题思路

  1. 规模不是很大,直接暴力

  2. 一种很巧妙的方法

    仔细观察矩阵,可以发现:左下角元素 为所在列最大元素,所在行最小元素

    如果 左下角元素 大于了目标值,则目标值一定在该行的上方, 左下角元素所在行可以消去。

    如果 左下角元素 小于了目标值,则目标值一定在该列的右方, 左下角元素所在列可以消去。

    具体操作为从矩阵左下角元素开始遍历,并与目标值对比:

    • matrix[i][j] > target 时:行索引向上移动一格(即 i--),即消去矩阵第 i 行元素;
    • matrix[i][j] < target 时:列索引向右移动一格(即 j++),即消去矩阵第 j 列元素;
    • matrix[i][j] == target 时:返回 true。
    • 如果越界,则返回 false。

代码

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public boolean Find(int target, int[][] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
if (array[i][j] == target) {
return true;
}
}
}
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
//初始化 i 和 j 为数组左下角元素
int i = matrix.length - 1,
int j = 0;
//如果 i 和 j 没有越界继续判断
while(i >= 0 && j < matrix[0].length){
if(matrix[i][j] > target){
//行索引向上移动一格(即 i-- ),即消去矩阵第 i 行元素
i--;
}else if(matrix[i][j] < target){
//列索引向右移动一格(即 j++ ),即消去矩阵第 j 列元素
j++;
}else{
//找到目标值,直接返回 ture
return true;
}
}
//没有找到目标值,返回 false
return false;
}
}

树的子结构

题目大意

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

解题思路

树的操作主要是递归的应用,递归要注意设置递归的跳出条件。

判断当前节点值是否相等,是就进入子树判断环节。如果不是,分别以pRoot1的左右子树作为新起点,再次判断。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
//子树判断函数
bool isSubtree(TreeNode* pRootA, TreeNode* pRootB) {
if (pRootB == NULL) return true;
if (pRootA == NULL) return false;
if (pRootB->val == pRootA->val) {
return isSubtree(pRootA->left, pRootB->left) &&
isSubtree(pRootA->right, pRootB->right);
} else
return false;
}
public:
bool HasSubtree(TreeNode* pRootA, TreeNode* pRootB) {
//树中有一个为空,即返回false
if (pRootA == NULL || pRootB == NULL) return false;
//当前节点或者左右子树中存在子结构即可
return isSubtree(pRootA, pRootB) || HasSubtree(pRootA->left, pRootB) ||
HasSubtree(pRootA->right, pRootB);
}
};

从上往下打印二叉树

题目大意

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> result;
queue<TreeNode*> q;
TreeNode* front;
if (root == NULL) return result;
q.push(root);
while (!q.empty()) {
front = q.front();
q.pop();
if (front->left) q.push(front->left);
if (front->right) q.push(front->right);
result.push_back(front->val);
}
return result;
}
};

树的后序遍历序列

题目大意

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

解题思路

  1. 递归:判断当前的序列左子树是否小于根,右子树是否大于根。如果都符合要求,递归判断左右子树。

  2. 非递归(牛客): 左子树一定比右子树小,因此去掉根后,数字分为left,right两部分,right部分的最后一个数字是右子树的根他也比左子树所有值大,因此我们可以每次只看有子树是否符合条件即可,即使到达了左子树,左子树也可以看出由左右子树组成的树还想右子树那样处理。对于左子树回到了原问题,对于右子树,左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树。只需看看右子树的右子树是否符合要求即可。

代码

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
//非递归
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int size = sequence.size();
if(0==size)return false;
int i = 0;
while(--size){
while(sequence[i]<sequence[size]) i++;
while(sequence[i]>sequence[size]) i++;
if(i<size)return false;
i=0;
}
return true;
}
};
//递归
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if (sequence.empty() || sequence.size() <= 0) return false;
bool left = true, right = true;
int i = 0;
while (sequence[i] < sequence[sequence.size() - 1]) i++;
//判断左小
int l = 0, r = i;
int pos = sequence.size() - 1;
while (l <= i - 1) {
if (sequence[l] >= sequence[pos]) return false;
l++;
}
//判断右小
while (r < pos) {
if (sequence[r] <= sequence[pos]) return false;
r++;
}
vector<int>::const_iterator first1 = sequence.begin();
vector<int>::const_iterator last1 = sequence.begin() + i;
if (i > 0) {
vector<int> sequence_l(first1, last1);
left = VerifySquenceOfBST(sequence_l);
}
//判断右子树
if (i < sequence.size() - 1) {
vector<int>::const_iterator last2 =
sequence.begin() + sequence.size() - 1;
vector<int> sequence_f(last1, last2);
right = VerifySquenceOfBST(sequence_f);
}
return (left && right);
}
};

二叉树中和为某一值的路径

题目大意

输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前) 。

解题思路

递归搜索,每搜索到一个节点,和更新。到了叶节点,判断剩下的和是否与根节点相等,非叶节点接着搜索左右子树。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<vector<int> > result;
vector<int> resu_t;
void find(TreeNode* root, int expectNumber) {
if (root == NULL || expectNumber < root->val) return;
resu_t.push_back(root->val);
if (!root->left && !root->right && expectNumber == root->val)
result.push_back(resu_t);
else {
if (root->left) find(root->left, expectNumber - root->val);
if (root->right) find(root->right, expectNumber - root->val);
}
resu_t.pop_back();
}
vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
find(root, expectNumber);
return result;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> single = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if (root == null) return result;
single.add(root.val);
target -= root.val;
if (target == 0 && root.left == null && root.right == null){
result.add(new ArrayList<Integer>(single));
}
FindPath(root.left, target);
FindPath(root.right, target);
single.remove(single.size()-1);
return result;
}
}

连续子数组的最大和

题目大意

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

解题思路

如果前n-1个数和为负数,加上第n个数肯定要比第n个数小。否则的话怎么加都比第n个数大。当和大于了当前的最大和时候更新最大和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
//先进行异常处理
if (array.empty() || array.size() == 0) return 0;
int sum_t = 0;
int great = array[0];
for (int i = 0; i < array.size(); i++) {
if (sum_t < 0)
sum_t = array[i];
else
sum_t += array[i];
if (sum_t > great) great = sum_t;
}
return great;
}
};

把数组排成最小的数

题目大意

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

解题思路

比较器的应用,新写一个比较器,将放在前面能有效降低数大小的数定义为小数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
static bool cmp(int a, int b) {
string tmp1 = "";
string tmp2 = "";
tmp1 += to_string(a);
tmp1 += to_string(b);
tmp2 += to_string(b);
tmp2 += to_string(a);
return tmp1 < tmp2;
}
string PrintMinNumber(vector<int> numbers) {
sort(numbers.begin(), numbers.end(), cmp);
string result = "";
for (auto n : numbers) result += to_string(n);
return result;
}
};
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
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public String PrintMinNumber(int[] numbers) {
String resu = "";
if (numbers.length == 0)
return resu;
int len = numbers.length;
String[] array = new String[len];
for (int i = 0; i < len; i++) {
array[i] = String.valueOf(numbers[i]);
}
Arrays.sort(array, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
String r1 = s1 + s2;
String r2 = s2 + s1;
return r1.compareTo(r2);
}
});
for (int i = 0; i < array.length; i++) {
resu += array[i];
}
return resu;
}
}

丑数

题目大意

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

解题思路

首先从丑数的定义我们知道,一个丑数的因子只有2,3,5,那么丑数p = 2 ^ x * 3 ^ y * 5 ^ z,换句话说一个丑数一定由另一个丑数乘以2或者乘以3或者乘以5得到,那么我们从1开始乘以2,3,5,就得到2,3,5三个丑数,在从这三个丑数出发乘以2,3,5就得到4,6,10,6,9,15,10,15,25九个丑数,我们发现这种方法会得到重复的丑数,而且我们题目要求第N个丑数,这样的方法得到的丑数也是无序的。那么我们可以维护三个队列 。分别存放最后一次乘进来的数。参考链接

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int GetUglyNumber_Solution(int index) {
// 0-6的丑数分别为0-6
if (index < 7) return index;
//p2,p3,p5分别为三个队列的指针,newNum为从队列头选出来的最小数
vector<int> result(index);
int t2 = 0, t3 = 0, t5 = 0;
result[0] = 1;
for (int i = 1; i < index; i++) {
//选出三个队列头最小的数
result[i] =
min(result[t2] * 2, min(result[t3] * 3, result[t5] * 5));
//这三个if有可能进入一个或者多个,进入多个是三个队列头最小的数有多个的情况
if (result[i] == result[t2] * 2) t2++;
if (result[i] == result[t3] * 3) t3++;
if (result[i] == result[t5] * 5) t5++;
}
return result[index - 1];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;
public class Solution {
public int GetUglyNumber_Solution(int index) {
if (index < 7) return index;
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
int t2 = 0, t3 = 0, t5 =0;
for (int i = 1; i < index; i++){
int min = Math.min(arrayList.get(t2)*2, Math.min(arrayList.get(t3)*3, arrayList.get(t5)*5));
arrayList.add(min);
if (min == arrayList.get(t2) * 2) t2++;
if (min == arrayList.get(t3) * 3) t3++;
if (min == arrayList.get(t5) * 5) t5++;
}
return arrayList.get(index-1);
}
}

第一个只出现一次的字符

题目大意

在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写)。

解题思路

  1. 我使用了find的相关函数,第一次出现和最后一次出现是一个位置说明只出现了一次。
  2. 使用map做,这道题因为有大小写,使用int count[26]并不好做。
  3. 牛客看到的一个处理大小写的,使用int count[58],为什么是58呢,a-z=65-90,A-Z=97-122,直接取65-122,中间的几个也算进去,一共38。

代码

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
//1
class Solution {
public:
int FirstNotRepeatingChar(string str) {
int pos = -1;
for (int i = 0; i < str.size(); i++) {
if (str.find_last_of(str[i]) == str.find_first_of(str[i])) {
pos = i;
break;
}
}
return pos;
}
};
//2
class Solution {
public:
int FirstNotRepeatingChar(string str) {
map<char, int> mp;
for(int i = 0; i < str.size(); ++i)
mp[str[i]]++;
for(int i = 0; i < str.size(); ++i){
if(mp[str[i]]==1)
return i;
}
return -1;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 3
public static int solution(String str){
int[] words = new int[58];
for(int i = 0;i<str.length();i++){
words[((int)str.charAt(i))-65] += 1;
}
for(int i=0;i<str.length();i++){
if(words[((int)str.charAt(i))-65]==1)
return i;
}
return -1;
}
// 1java版
public int FirstNotRepeatingChar(String str) {
int pos = -1;
for (int i = 0; i < str.length(); i++) {
if (str.indexOf(str.charAt(i)) == str.lastIndexOf(str.charAt(i))) {
pos = i;
return pos;
}
}
return pos;
}

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

题目大意

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

解题思路

相当于一个Y字形排列,先让长的指针头移动到短的位置,确保他们的尾在同一位置,然后共同推进到值相同的位置。

代码

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
class Solution {
public:
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
int l1 = 0, l2 = 0;
if (pHead1 == NULL || pHead2 == NULL) return NULL;
ListNode *t1 = pHead1, *t2 = pHead2, *result;
while (pHead1->next != NULL) {
l1++;
pHead1 = pHead1->next;
}
while (pHead2->next != NULL) {
l2++;
pHead2 = pHead2->next;
}
int gap = abs(l1 - l2);
if (l1 >= l2) {
while (gap > 0) {
t1 = t1->next;
gap--;
}
} else if (l1 < l2) {
while (gap > 0) {
t2 = t2->next;
gap--;
}
}
while (t1 != t2) {
t1 = t1->next;
t2 = t2->next;
}
return t1;
}
};

数字在排序数组中出现的次数

题目大意

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

解题思路

本来我写的是找到第一个数就开始计数,不是了就跳出。

牛客:二分查找,因为data中都是整数,所以可以稍微变一下,不是搜索k的两个位置,而是搜索k-0.5和k+0.5。这两个数应该插入的位置,然后相减即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
return biSearch(data, k+0.5) - biSearch(data, k-0.5) ;
}
private:
int biSearch(const vector<int> & data, double num){
int s = 0, e = data.size()-1;
while(s <= e){
int mid = (e - s)/2 + s;
if(data[mid] < num)
s = mid + 1;
else if(data[mid] > num)
e = mid - 1;
}
return 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
//1
class Solution {
public:
int treelength(TreeNode* pRoot) {
if (pRoot == NULL) return 0;
return max(treelength(pRoot->left), treelength(pRoot->right)) + 1;
}
bool IsBalanced_Solution(TreeNode* pRoot) {
if (pRoot == NULL) return true;
// 判断左右子树是不是平衡二叉树,最近一次刷题忘记了
return (IsBalanced_Solution(pRoot->left) &&
IsBalanced_Solution(pRoot->right) &&
abs(treelength(pRoot->left) - treelength(pRoot->right)) <= 1);
}
};
//2 剪枝
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
return getDepth(root) != -1;
}

private int getDepth(TreeNode root) {
if (root == null) return 0;
int left = getDepth(root.left);
if (left == -1) return -1;
int right = getDepth(root.right);
if (right == -1) return -1;
return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}
}

孩子们的游戏(圆圈中最后剩下的数)

题目大意

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

如果没有小朋友,请返回-1。

解题思路

队列模拟过程,牛客网上的公式没整明白。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if (n <1|| m <1) return -1;
Queue<Integer> queue = new LinkedList<Integer>();
for (int i=0; i<n; i++)
queue.offer(i);
while (queue.size()>1){
for (int i = 0; i< m-1; i++){
queue.offer(queue.poll());
}
queue.poll();
}
return queue.peek();
}
}

不用加减乘除做加法

题目大意

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

解题思路

首先看十进制是如何做的: 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为最终结果。

代码

1
2
3
4
5
6
7
8
9
10
public class Solution {
public int Add(int num1,int num2) {
while (num2!=0) {
int temp = num1^num2;
num2 = (num1&num2)<<1;
num1 = temp;
}
return num1;
}
}

二叉树的下一个结点

题目大意

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

解题思路

根据图,如果有右子树,找右子树的最左节点即可。

如果没有右子树,则要找到当前节点往上的某一父亲节点,即找到这个父亲节点前走过的节点都是该父亲节点的左孩子。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
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;
}
}

对称的二叉树

题目大意

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

解题思路

开始没弄明白题目要求是对称,以为只需要检查左右结点值相等就可以,直接递归了。做题不能心急。

确定非空后,检查左子树的右子树是否和右子树的左子树、右子树的右子树和左子树的左子树是否相同。递归。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot) {
if (pRoot == NULL) return true;
return comTree(pRoot->left, pRoot->right);
}
bool comTree(TreeNode* left, TreeNode* right) {
if (left == NULL) return right == NULL;
if (right == NULL) return false;
if (left->val != right->val) return false;
return comTree(left->right, right->left) &&
comTree(left->left, right->right);
}
};

按之字形顺序打印二叉树

题目大意

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

解题思路

使用flag记录奇偶数层,分别处理。这里要注意偶数层从右往左,要先记录右子树。另一个问题是在第二次做的时候发现的,因为每次都与上一层顺序相反,所以应该都使用栈,反向入栈的时候右子树要先压入栈。

代码

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
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
if (pRoot ==null) return result;
stack1.push(pRoot);
int layer =1;
while (!stack1.isEmpty()||!stack2.isEmpty()){
if (layer%2!=0){
ArrayList<Integer> rs= new ArrayList<>();
while (!stack1.isEmpty()){
TreeNode temp = stack1.pop();
rs.add(temp.val);
if (temp.left != null)
stack2.push(temp.left);
if (temp.right != null)
stack2.push(temp.right);
}
result.add(rs);
layer++;
}else{
ArrayList<Integer> rs= new ArrayList<>();
while (!stack2.isEmpty()){
TreeNode temp = stack2.pop();
rs.add(temp.val);
if (temp.right != null)
stack1.push(temp.right);
if (temp.left != null)
stack1.push(temp.left);
}
result.add(rs);
layer++;
}
}
return result;
}
}

二叉搜索树的第k个结点

题目大意

给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。

解题思路

二叉树中序遍历的第k个结点即为所求。

代码

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 class Solution {
int index = 0;
TreeNode KthNode(TreeNode pRoot, int k){
if (pRoot == null) return 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;
}
}
// 非递归
import java.util.*;
public class Solution {
TreeNode KthNode(TreeNode pRoot, int k){
if (pRoot == null) return null;
int i = 0;
Stack<TreeNode> stack = new Stack<TreeNode>();
while (pRoot != null || !stack.isEmpty()){
if (pRoot != null){
stack.push(pRoot);
pRoot = pRoot.left;
} else{
pRoot = stack.pop();
i++;
if (i == k) return pRoot;
pRoot = pRoot.right;
}
}
return null;
}
}

数据流中的中位数

题目大意

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。

解题思路

使用priority_queue建立大顶堆和小顶堆,即用大顶堆存储中位数左边的,小顶堆存储中位数右边的,这样大顶堆出队是中位数左边最近的最大数,小顶堆出来的是右边最小的。每次插入保证左右数量相同或者左边比右边大一,取中位数时候相同取平均数,不相同取左边的最大值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
public class Solution {
// 大顶堆
PriorityQueue<Integer> head = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// 降序排列
return o2 - o1;
}
});
// 小顶堆
PriorityQueue<Integer> tail = new PriorityQueue<>();
public void Insert(Integer num) {
if (head.size() == 0|| num <= head.peek()) head.offer(num);
else tail.offer(num);
if (head.size() == tail.size() +2) tail.offer(head.poll());
if (head.size() +1 == tail.size()) head.offer(tail.poll());
}
public Double GetMedian() {
return head.size()==tail.size()?(head.peek()+tail.peek())/2.0:(double)head.peek();
}
}
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
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Solution {
public static void main(String[] args) {
Solution so = new Solution();
Scanner scan = new Scanner(System.in);
while (scan.hasNextInt()){
int num=scan.nextInt();
so.Insert(num);
Double result = so.GetMedian();
System.out.println(result);
}
}

//最大堆,存储流左边的元素
PriorityQueue<Integer> left = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
/**以下是对比较器升序、降序的理解.
*(1) 写成return o1.compareTo(o2) 或者 return o1-o2表示升序
*(2) 写成return o2.compareTo(o1) 或者return o2-o1表示降序
*/
return o2.compareTo(o1);
}
});
//最小堆,存储流右边元素
PriorityQueue<Integer> right = new PriorityQueue<Integer>();
//计数器,初始值为0,插进去一个增加一个
int N = 0;

public void Insert(Integer num) {
//奇数放到left,从left往right倒一个最大值,为的就是保证right最小堆中的所有的值都要大于left
if (N % 2 == 0) {
//刚开始N=0,首先是right最小堆中有元素
left.add(num);
right.add(left.poll());
} else {
right.add(num);
left.add(right.poll());
}
N++;
}

public Double GetMedian() {
if (N % 2 == 1) {
//奇数个,因为右边比左边多一个,也可以认为右边比左边先有元素
double result = (double)right.peek();
return result;
} else {
//要先将和转换为double类型,然后再除
double result = (double) (left.peek() + right.peek())/2;
return result;
}
}
}

数值的整数次方

题目大意

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0。

解题思路

特殊情况的处理。举例:10^1101 = 10 ^ 0001 * 10 ^ 0100 * 10 ^ 1000。通过&1和>>1来逐位读取1101,为1时将该位代表的乘数累乘到最终结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public double Power(double base, int exponent) {
double res = 1, curr = base;
int n = exponent;
if (exponent > 0)
exponent *= 1;
else if (exponent < 0) {
if (base == 0)
throw new RuntimeException("分母为0");
exponent *= -1;
} else {
return 1;
}
while (exponent != 0) {
if ((exponent & 1) == 1)
res *= curr;
curr *= curr;
exponent >>= 1;
}
return n > 0 ? res : (1 / res);
}
}

滑动窗口的最大值(补录)

题目大意

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{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
import java.util.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size){
ArrayList<Integer> result = new ArrayList<>();
if (num.length == 0||size==0) return result;
for (int i = 0; i <= num.length-size; i++){
int[] temp = Arrays.copyOfRange(num, i, i+size);
Arrays.sort(temp);
result.add(temp[temp.length-1]);
}
return resut;
}
}

二进制中1的个数

题目大意

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

解题思路

  • 调用bitset函数即可,相关内容在边走边学中有记录
  • 直接和对应的数字相与
  • 执行数 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
class Solution {
public:
int NumberOf1(int n) {
return bitset<32>(n).count();
}
};
//知道并会用函数真的强

//另一种解法,直接与对应的与就好。
import java.util.BitSet;
public class Solution {
public int NumberOf1(int n) {
int count = 0;
int flag = 1;
while (flag != 0) {
if ((n & flag) != 0)
count++;
flag = flag << 1;
}
return count;
}
}

// 我们将 9 减 1 ,对应的就是 9 的二进制中最右边的一个 1 变成了 0,其之后的位置全变为 1 .然后我们将 8 和 9 进行位与运算,并将结果保存在 n = n & (n-1)=8 ,然后对 n 继续重复上述步骤,直到 n = 0 为止。8 减去 1 为 7:然后让 8 和 7 进行与运算,结果为 0 ,总共执行 2 次,9 的二进制中 1 的个数为 2.
int NumberOf1_Solution2(int n){
int count = 0;
while (n){
++count;
n = (n - 1) & n;
}
return count;
}

包含min函数的栈

题目大意

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

解题思路

引入辅助栈即最小元素栈,每次压栈元素比当前元素更小,就把这个元素压入最小元素栈,原本的元素成了最小元素。同理,如果弹出的元素和最小栈的栈顶元素相等,就把最小元素的栈顶弹出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
void push(int value) {
resu.push(value);
if (mins.empty())
mins.push(value);
else if (mins.top() >= value)
mins.push(value);
}
void pop() {
if (resu.top() == mins.top()) mins.pop();
resu.pop();
}
int top() { return resu.top(); }
int min() { return mins.top(); }
private:
stack<int> resu;
stack<int> mins;
};

栈的压入弹出序列

题目大意

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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
class Solution {
public:
bool IsPopOrder(vector<int> pushV, vector<int> popV) {
//一直压 压到相等 弹出去
stack<int> resu;
resu.push(pushV[0]);
int i = 0, j = 0, tmp = i;
while (i < (int)pushV.size() && j < (int)popV.size()) {
if (resu.top() != popV[j]) {
i += 1;
tmp = i;
cout << "r" << pushV[tmp] << endl;
resu.push(pushV[tmp]);
} else {
cout << "c" << resu.top() << endl;
resu.pop();
j += 1;
tmp = i + 1;
}
}
return resu.empty();
}
};

数组中只出现一次的字数

题目大意

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

解题思路

  1. 自己的:排序后判断当前位置与后面的位置是否相同,不相同变记录。
  2. 讨论区高赞:可以用位运算实现,如果将所有所有数字相异或,则最后的结果肯定是那两个只出现一次的数字异或的结果,所以根据异或的结果1所在的最低位,把数字分成两半,每一半里都还有只出现一次的数据和成对出现的数据。这样继续对每一半相异或则可以分别求出两个只出现一次的数字。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if (array.length<2) return;
int size = array.length;
int temp = array[0];
for (int i = 1; i < size; i++) temp ^= array[i];
int index = 0;
while ((temp & 1) ==0){
temp = temp >> 1;
++index;
}
for (int i = 0; i < size; i++){
if (IsBit(array[i], index)){
num1[0] ^= array[i];
}
else num2[0] ^= array[i];
}
}
public boolean IsBit(int num, int index){
num = num >> index;
return (num & 1)==1?true:false;
}
}

和为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
23
24
25
26
27
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array, int sum) {
int minn = 10000000;
vector<int> tmp;
int left = 0, right = array.size() - 1;
while (left < right) {
if (array[left] + array[right] == sum) {
if (array[left] * array[right] < minn) {
tmp = vector<int>();
tmp.push_back(array[left]);
tmp.push_back(array[right]);
minn = array[left] * array[right];
}
left++;
right--;
} else if (array[left] + array[right] > sum) {
right--;
break;
} else if (array[left] + array[right] < sum) {
left++;
break;
}
}
return tmp;
}
};

翻转单词序列

题目大意

“I am a student.” ->“student. a am I”

解题思路

先整体翻转,再每个单词翻转。

本来最后处理了最后一个,看了别人的代码,又去看了看题,原来其实就是单词倒序输出,没必要单独处理最后一个。

代码

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
class Solution {
public:
void ReverseWord(string &str, int s, int e) {
while (s < e) swap(str[s++], str[e--]);
}

string ReverseSentence(string str) {
ReverseWord(str, 0, str.size() - 1); //先整体翻转
int s = 0, e = 0;
int i = 0;
while (i < str.size()) {
while (i < str.size() && str[i] == ' ') //空格跳过
i++;
e = s = i; //记录单词的第一个字符的位置
while (i < str.size() &&
str[i] != ' ') //不是空格 找单词最后一个字符的位置
{
i++;
e++;
}
ReverseWord(str, s, e - 1); //局部翻转
}
return str;
}
};

扑克牌顺子

题目大意

王用0表示,可以替代任何数,判断五张牌是否可以组成顺子。

解题思路

除了0之外的牌,最大最小值之差不能大于4,而且不能有重复值。

//吐槽:这题测试样例里竟然有空数组?迷

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public boolean isContinuous(int [] numbers) {
if (numbers.length == 0) return false;
int[] count = new int[14];
for (int i = 0; i < numbers.length; i++) {
count[numbers[i]]++;
if (count[numbers[i]]>1 && numbers[i]!=0) return false;
}
int min=15, max =-1;
for (int i = 0; i < numbers.length; i++){
if (numbers[i]<min&&numbers[i]!=0){
min = numbers[i];
}
if (numbers[i]>max&&numbers[i]!=0){
max = numbers[i];
}
}
return max-min<=4;
}
}

数组中重复的数字

题目大意

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

解题思路

自己想的是查找第一次出现的位置和最后一次出现的位置。

牛客:用在数字对应位置加length,取模后不影响大小,取模前判断一下是不是大于length。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool duplicate(int numbers[], int length, int* duplication) {
for(int i=0;i!=length;++i){
int index=numbers[i]%length;
if(numbers[index]>=length){
*duplication=index;
return 1;
}
numbers[index]+=length;
}
return 0;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public boolean duplicate(int numbers[], int length, int[] duplication) {
for (int i = 0; i < length; i++) {
int index = numbers[i] % length;
if (numbers[index] >= length) {
duplication[0] = index;
return true;
}
numbers[index] += length;
}
return false;
}
}

构建乘积数组

题目大意

给定一个数组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]。不能使用除法。

解题思路

下三角用连乘可以很容求得,上三角,从下向上也是连乘。因此我们的思路就很清晰了,先算下三角中的连乘,即我们先算出B[i]中的一部分,然后倒过来按上三角中的分布规律,把另一部分也乘进去。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> B(A.size(),0);
if (A.size()) {
B[0]=1;
for (int i = 1; i < A.size(); i++) {
B[i] = B[i - 1] * A[i - 1];
}
int temp = 1;
for (int j = A.size() - 2; j >= 0; j--) {
temp *= A[j + 1];
B[j] *= temp;
}
}
return B;
}
};

剪绳子

题目大意

给你一根长度为n的绳子,请把绳子剪成m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

解题思路

  1. 对前面的数计算可以得到,3的数量越多越好,因为222<33,将特殊情况处理,然后输出即可。特别的,如果余数是1,说明最后应该是1+3=2+2。
  2. 动态规划:
    • 当n<=3时候,分为两种情况:
      • n=2时候,绳子只能剪为两个长度为1的绳子,最大乘积为1;
      • n=3时候,绳子只能剪为长度为1和2的两段,最大乘积为2,直接返回。
    • 当n>3,按照动态规划处理:
      • 初始值:dp[1]=1,d[2]=2,dp[3]=3。这么写是因为大于3的绳子完全可以拆分为3、2和1的绳子,拆分得到长度为3的绳子不必再拆分,算入乘积的话就是3本身,21同理。例如,n=4可以拆分为3+1、2+2、1+3,而321都是最终直接作为计算乘积时的因子出现的,因此dp[i]=i(1-3)。
      • 递推公式:对于长度大于3的绳子来说,要取得最大乘积dp[n],就需要知道它的前三个状态dp[n-1]、dp[n-2]、dp[n-3],而相应的最大乘积为3dp[n-3]、2dp[n-2]、1dp[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
public class Solution {
public int cutRope(int target) {
if (target == 2) return 1;
if (target == 3) return 2;
int x = target % 3;
int y = target / 3;
if (x == 1)
return 4 * (int)Math.pow(3, y-1);
else if (x == 2)
return 2 * (int)Math.pow(3, y);
else return (int)Math.pow(3, y);
}
}
class Solution {
public int cuttingRope(int n) {
if(n <= 3){
return n-1;
}
int dp[] = {1,2,3};
for(int i = 3; i < n; i++) {
int tmp = Math.max(3 * dp[0],Math.max(2 * dp[1], 1 * dp[2]));
dp[0] = dp[1];
dp[1] = dp[2];
dp[2] = tmp;
}
return dp[2];
}
}

重建二叉树

题目大意

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

解题思路

递归解决,前序遍历的左子树也是前序,中序遍历的左子树也是按照中序。

1
Arrays.copyOfRange(pre, 1, i + 1);	//拷贝pre数组的[1,i+1)个元素

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;
public class Solution {
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
if (pre.length == 0 || in.length == 0)
return null;
TreeNode node = new TreeNode(pre[0]);
for (int i = 0; i < in.length; i++) {
if (pre[0] == in[i]) {
node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),
Arrays.copyOfRange(in, i + 1, in.length));
break;
}
}
return node;
}
}

字符串的排列

题目大意

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

解题思路

对abb,第一个数a与第二个数b交换得到bab,然后考虑第一个数与第三个数交换,此时由于第三个数等于第二个数,所以第一个数就不再用与第三个数交换了。再考虑bab,它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕!

代码

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
import java.util.ArrayList;
import java.util.*;

public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> result = new ArrayList<String>();
if (str != null && str.length() > 0) {
PermutationHelper(str.toCharArray(), 0, result);
Collections.sort(result);
}
return result;
}

public void PermutationHelper(char[] chars, int i, ArrayList<String> list) {
if (i == chars.length - 1)
list.add(String.valueOf(chars));
else {
Set<Character> charSet = new HashSet<Character>();
for (int j = i; j < chars.length; j++) {
if (!charSet.contains(chars[j])) {
charSet.add(chars[j]);
swap(chars, i, j);
PermutationHelper(chars, i + 1, list);
swap(chars, j, i);
}
}
}
}

private void swap(char[] cs, int i, int j) {
char temp = cs[i];
cs[i] = cs[j];
cs[j] = temp;
}
}

删除链表中重复的结点

题目大意

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表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
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null || pHead.next == null)
return pHead;
ListNode Head = new ListNode(0);
Head.next = pHead;
ListNode pre = Head, last = Head.next;
while (last != null) {
if (last.next != null && last.val == last.next.val) {
while (last.next != null && last.val == last.next.val) {
last = last.next;
}
pre.next = last.next;
last = last.next;
} else {
pre = pre.next;
last = last.next;
}
}
return Head.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 如果至少保留一个重复的节点
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
ListNode pre = pHead, last = pHead.next;
while (last.next != null) {
if (pre.val == last.val) {
last = last.next;
pre.next = last;
} else {
pre = pre.next;
last = last.next;
}
}
return pHead;
}
}

矩阵中的路径

题目大意

判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。

解题思路

回溯,增加判断。

代码

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 class Solution {
boolean[] visited = null;

public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
visited = new boolean[matrix.length];
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (subHasPath(matrix, rows, cols, str, i, j, 0))
return true;
return false;
}

public boolean subHasPath(char[] matrix, int rows, int cols, char[] str, int row, int col, int len) {
if (matrix[row * cols + col] != str[len] || visited[row * cols + col] == true)
return false;
if (len == str.length - 1)
return true;
visited[row * cols + col] = true;
if (row > 0 && subHasPath(matrix, rows, cols, str, row - 1, col, len + 1))
return true;
if (row < rows - 1 && subHasPath(matrix, rows, cols, str, row + 1, col, len + 1))
return true;
if (col > 0 && subHasPath(matrix, rows, cols, str, row, col - 1, len + 1))
return true;
if (col < cols - 1 && subHasPath(matrix, rows, cols, str, row, col + 1, len + 1))
return true;
visited[row * cols + col] = false;
return false;
}
}

序列化二叉树

题目大意

实现两个函数,分别用来序列化和反序列化二叉树

解题思路

设置序号index,将字符串根据逗号分割为数组,根据index的值来设置树节点的val,如果节点的值为#,则返回空的树节点。

此题中的解法中,相当于每次调用序列化函数都会在自身序列化后调用左子树,index用来记录到哪个节点了,从而达到递归的目的。

代码

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 class Solution {
int index = -1;
String Serialize(TreeNode root) {
if (root == null)
return "#";
else
return root.val + "!" + Serialize(root.left) + "!" + Serialize(root.right);
}
TreeNode Deserialize(String str) {
String[] s = str.split("!");
index++;
int len = s.length;
if (index > len) {
return null;
}
TreeNode treeNode = null;
if (!s[index].equals("#")) {
treeNode = new TreeNode(Integer.parseInt(s[index]));
treeNode.left = Deserialize(str);
treeNode.right = Deserialize(str);
}
return treeNode;
}
}