LHJ's Blog

剑指Offer

✍ 二维数组中的查找

✨ 题目描述

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

💡 解题思路1

    最简单的一种方法就是从头到尾遍历整个数组,找到目标target返回true,否则返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public boolean Find(int target, int [][] array) {
if(array == null || array.length == 0){
return false;
}
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;
}
}

🔔 现在分析一下这个解法,思路很简单,就是一个遍历,整个算法的时间复杂度⏳为O(n^2),空间复杂度⏳为O(1)。算法的时间复杂度有点高,并不是最理想的情况。

💡 解题思路2

    认真再看一遍题目可以发现有一个条件: 每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。这种情况就很适合采用二分搜索的方式进行查找。

🎈 由于数组的每一行是递增的,因此可以对数组的每一行进行二分查找

🎈 数组的每一列也是递增的,因此可以确定target具体在哪一行

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
public class Solution {
public boolean Find(int target, int [][] array) {
if(array == null || array.length == 0 || array[0].length == 0){
return false;
}
int m = array.length, n = array[0].length;
for(int i = 0; i < m; i++){
int last = array[i][n - 1];
int first = array[i][0];
if(target >= first && target <= last){
boolean success = binarySearch(array[i], target, 0, n - 1);
if(success){
return true;
}
}
}
return false;
}

private boolean binarySearch(int[] array, int target, int left, int right){
if(right < left){
return false;
}
int mid = left + (right - left) / 2;
if(array[mid] == target){
return true;
}else if(array[mid] > target){
return binarySearch(array, target, left, mid - 1);
}else{
return binarySearch(array, target, mid + 1, right);
}
}
}

🔔 现在分析一下这个解法,思路很简单,首先是从头到尾查找每一行,排除掉target不可能存在的行,然后对这一行进行二分搜索,查找这个target是否存在。整个算法的时间复杂度⏳为O(nlog(n)),空间复杂度⏳为O(1)。比第一种方法稍微好一点。

✍ 替换空格

✨ 题目描述

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

💡 解题思路1

    这个题目可以使用Java中String类的APIreplace,把空格替换成%20

1
2
3
4
5
6
7
8
public class Solution {
public String replaceSpace(StringBuffer str) {
if(str == null){
return null;
}
return str.toString().replace(" ", "%20");
}
}

🔔 题目很简单,但是很显然不是为了考验你调用API的能力,而且面试的时候这么做面试官也不会满意(要是满意了我还不去了,细思极恐)

💡 解题思路2

    既然不可以用API,那么就换一种做法,题目的意思是把空格换成%20,那么可以尝试使用额外的空间保存正确的结果。

1️⃣ 新建一个StringBuffer,用于保存正确的结果

2️⃣ 遍历给定的字符串,如果碰到空格,那么插入%20,否则插入当前字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public String replaceSpace(StringBuffer str) {
if(str == null){
return null;
}
StringBuffer res = new StringBuffer();
for(int i = 0; i < str.length(); i++){
if(str.charAt(i) == ' '){
res.append("%20");
}else{
res.append(str.charAt(i));
}
}
return res.toString();
}
}

🔔 现在分析一下这个解法,思路很简单,就是一个遍历,然后把结果存储到新的数组里面。假设给定的数组长度为n,空格数量为m,整个算法的时间复杂度⏳为O(n),空间复杂度⏳为O(n + 2 * m)。使用了额外的空间,并不是很理想。

💡 解题思路3

    第二种解法使用了额外的空间不是很理想,事实上最后一定会用到额外的空间,最理想的情况是额外使用的空间为O(2 * m)。所以需要在原空间上进行扩展。在原空间上进行扩展就需要知道一共有几个空格,是从前向后扩展还是从后向前扩展?有几个空格很容易实现,遍历一次就行了;从前向后扩展肯定是不行的,因为每次进行扩展都会导致后面的元素向后移,代价比较大,从后向前移动,每个字符只移动一次,代价就比较小。

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
public class Solution {
public String replaceSpace(StringBuffer str) {
if(str == null){
return null;
}
int count = 0;
for(int i = 0; i < str.length(); i++){
if(str.charAt(i) == ' '){
count++;
}
}
int oldLength = str.length();
int newLength = oldLength + count * 2;
str.setLength(newLength);
for(int i = oldLength - 1, j = newLength - 1; i >= 0 && i < newLength; i--){
if(str.charAt(i) == ' '){
str.setCharAt(j--, '0');
str.setCharAt(j--, '2');
str.setCharAt(j--, '%');
}else{
str.setCharAt(j--, str.charAt(i));
}
}
return str.toString();
}
}

✍ 从尾到头打印链表

✨ 题目描述

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

💡 解题思路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 ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
import java.util.Collections;

public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<>();
while(listNode != null){
res.add(listNode.val);
listNode = listNode.next;
}
Collections.reverse(res);
return res;
}
}

当然如果不用Collections也是ok的,可以使用ArrayList里面的插入方法add(index, value),每次插入的位置都是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 class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;

public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<>();
while(listNode != null){
res.add(0, listNode.val);
listNode = listNode.next;
}
return res;
}
}

🔔 这两种方法都是一样的,由于需要保存链表元素,所以空间复杂度⏳是O(n),然后要遍历一次链表,时间复杂度是⏳O(n)。

对于第一种方法:先记下所有元素,然后逆序。这个逆序的时间复杂度是O(n/2),所以第一种方法的时间复杂度⏳是O(n + n / 2) ~ O(n)。

对于第二种方法,因为是每次都插入到第一个位置,导致后面的元素都要向后移动,对于第i个元素的移动次数是:i - 1(插入第一个元素移动次数为0,第二个移动次数为1,第三个为2..【已经存在的元素向后移动一个位置】),所以整个的移动次数是0 + 1 + 2 + 3 + 4 + 5 … + n - 1 = n(n - 1) / 2。所以第二种方法的时间复杂度是⏳O(n + n(n - 1) / 2) ~ O(n^2)

✍ 重建二叉树

✨ 题目描述

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

💡 解题思路1

题目的意思简单来说就是给定先序遍历和中序遍历,然后构造这个二叉树。这个题目的思路可以从先序遍历和中序遍历的关系来理解,如下图:

☕ 初始序列:

niuke

☕ 你会发现对于先序遍历的第一个元素,可以把中序遍历分为左右两个部分

p2

☕ 如果只看左边,先序遍历的第二个元素又可以把左边部分的序列分为左右两个部分

p3

到这一步应该就有一个整体的思路了:整体就是一个递归,先序遍历获取到的第一个元素(相对)作为头节点,每次通过先序遍历的第一个元素(相对)把序列(相对)分为左右两个部分,然后对分开的这两个序列采用相同的措施,构造当前头节点的左右子树。

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
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.Map;
import java.util.HashMap;

public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < in.length; i++){
map.put(in[i], i);
}
return build(pre, 0, in, 0, in.length - 1, map);
}

private TreeNode build(int[] pre, int preIndex, int[] in, int inStart, int inEnd, Map<Integer, Integer> map){
if(preIndex >= pre.length || inStart > inEnd){
return null;
}
int headVal = pre[preIndex];
TreeNode root = new TreeNode(headVal);
//index的左边是左序列,右边是右序列
int index = map.get(headVal);
root.left = build(pre, preIndex + 1, in, inStart, index - 1, map);
root.right = build(pre, preIndex + index - inStart + 1, in, index + 1, inEnd, map);
return root;
}
}

🔔 需要使用额外的空间保存节点信息,空间复杂度⏳为O(n),每次是对序列进行二分操作,因此构造树的时间复杂度⏳是O(log2n)

✍ 用两个栈实现队列

✨ 题目描述

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

💡 解题思路1

这道题目的主要用意是考察栈和队列的概念:栈(Stack)是一种先进后出的数据结构,就像工地彻砖一样,最底下的一定是最先彻好的,最上面的一定是最后彻的,也就是后来居上。而队列(Queue)和栈恰好相反,是一种先进先出的数据结构,就像排队,最前面的肯定会先那啥(想不出了🤣),最后的肯定..是吧(跳过跳过..🤣🤣🤣)

题目给定的是两个栈来实现队列,假如说是S1和S2,先考虑单一的情况:只进行Push操作的时候。这种情况应该是用一个栈还是两个栈一起来保存Push进来的值呢?这里肯定应该只用一个栈来保存数据,因为如果同时使用两个栈来保存的话,势必会导致数据的位置发生错乱。即对于Push操作,只是用一个栈来保存数据。现在再考虑Pop的操作:由于队列第一个出来的是第一个元素,但是栈第一个元素是最后一个,那么可以把栈的元素移动到另一个栈里面去。这样就可以将栈的元素逆序。这种情况是对于一个栈为空的情况,如果另一个栈不为空呢?另一个栈里面的元素位置一定会先于接收Push的栈元素的位置。即对于Pop操作,如果另一个栈为空,那么把当前这个栈的元素移动过去,取栈顶元素;否则取另一个栈的栈顶元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Stack;

public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
stack1.push(node);
}

public int pop() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}

✍ 旋转数组的最小数字

✨ 题目描述

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

💡 解题思路1

看了半天才看明白题目的意思,意思就是找数组里面的最小元素呗。简单啊,直接遍历一次就完了😁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 0){
return 0;
}
int min = Integer.MAX_VALUE;
for(int num : array){
if(min > num){
min = num;
}
}
return min;
}
}

🔍 方法简单粗暴,来分析一下效率:整体需要遍历一次数组,因此时间复杂度⌛为O(n),由于没有使用到额外的空间,因此空间复杂度⏳为O(1)

💡 解题思路2

再看看题目会发现一个规律:数组部分是有序的,这个有序就很有深意了,意味着如果从头向后搜索,如果一旦出现了非递增的情况,那么这个元素就是最小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 0){
return 0;
}
if(array.length == 1){
return array[0];
}
int index = 1;
while(index < array.length && array[index - 1] <= array[index]){
index++;
}
return array[index];
}
}

这种解法和第一种解法其实并没有性能上的提升,时间复杂度还是O(n),但是你在面试的时候先说了第一个,然后说了第二个,面试官就会觉得这个小伙子有点东西,招进来招进来😂😂😂

✍ 斐波那契数列

✨ 题目描述

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。

n<=39

💡 解题思路1

先普及一下斐波那契数列的概念:第一个数字为0,第二个数字为1,之后的每一个数字都是前面两个数字之和,即第n个数字为(n - 1)、(n - 2)数字的和。

最简单的一种方法就是,直接算到第n个数字不就完了🤣

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int Fibonacci(int n) {
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public int Fibonacci(int n) {
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
int f1 = 0, f2 = 1, res = 0;
for(int i = 2; i <= n; i++){
res = f1 + f2;
f1 = f2;
f2 = res;
}
return res;
}
}

照例来一次效率分析,整体的时间复杂度为O(n),因为都需要从0到n依次计算。然后这道题你会发现一个很有意思的地方:用第一种递归的代码,耗时1350ms,而第二种看着就不爽的代码耗时15ms !,这是因为递归需要不断的去调用本方法,而方法在执行的时候,其底层会在虚拟机栈中创建一个栈帧,方法执行完后这个栈帧会出栈。递归会导致不断地去创建栈帧和出栈,这样一来,表面上看,两种方法区别不大,甚至递归好看的多,但是在底层递归比普通的循环多出了好几倍的工作量(不仅仅是入栈和出栈这么简单)

✍ 跳台阶

✨ 题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

💡 解题思路1

这种题目是递归最经典的场景了,可以这么想:假如说一共有n级台阶,跳到第n级台阶只有两种方法:从n - 1级台阶或者从n - 2级台阶跳上来(因为一次只能跳一级或者两级),假如从第一级台阶通过x中跳法跳到了n - 1级台阶,此时你只有一种方法跳到第n级台阶,最后的方法次数为x,如果通过y中方法跳到了第n - 2级台阶,那么最后你也只有一种方法跳到第n级台阶(很奇怪吧,因为应该是有两种的:一次跳2级或者跳2次1级,但是,如果是跳两次1级的,第一次跳了以后不就到了n - 1级了吗?这个问题已经讨论过了,不要重复计算)。即跳到第n级台阶的方法为:n - 1级的方法 + 第n - 2级的方法

然后再整理一下边界的情况:如果台阶数为0,次数为0;如果台阶数为1,次数为1;如果台阶数为2,次数为2;之后的就可以用上面总结的公式进行推导了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public int JumpFloor(int target) {
if(target == 0){
return 0;
}
if(target == 1){
return 1;
}
if(target == 2){
return 2;
}
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
}

当然用递归的方法效率实在不高,不过这道题主要是为了训练递归的思维。

✍ 变态跳台阶

✨ 题目描述

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

💡 解题思路1

这道题和上到题意思差不多,都是一样的分析方法。按照之前的分析方法,跳到第n级台阶的方法为f(n) = f(n - 1) + f(n - 2) + ... + f(0)。那么跳到第n - 1级台阶的方法就是f(n - 1) = f(n - 2) + f(n - 3) + ... + f(0),这样一来,势必要记录从n - 10的所有记录(其实不用,第一种方法先这么写着)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int JumpFloorII(int target) {
int[] dp = new int[target + 1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= target; i++){
int temp = 1;
for(int j = 0; j < i; j++){
temp += dp[j];
}
dp[i] = temp;
}
return dp[target];
}
}

照例一波分析☕:很明显,这种解法用了额外的存储空间,空间复杂度为O(n + 1) ~ O(n),时间复杂度上是O(n * (n - 1)) ~ O(n^2)

💡 解题思路2

现在看一下另一种解法(其实就是一个算式总结)

从前面的推到中可以得出:

f(n) = f(n - 1) + f(n - 2) + ... + f(0)

f(n - 1) = f(n - 2) + f(n - 3) + ... + f(0)

所以

f(n) = 2 * f(n - 1)

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int JumpFloorII(int target) {
if(target == 0){
return 0;
}
if(target == 1){
return 1;
}
return 2 * JumpFloorII(target - 1);
}
}

✍ 矩形覆盖

✨ 题目描述

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

💡 解题思路1

这题目其实很简单的,就是填满嘛,然后一条边是2,一条边是n。你现在的东西是2 * 1的,意味着你有两种放置的方案,横着或者竖着,意味着你一次可以让n - 1,或者用两次让n - 2(在补齐另一边的情况下)。这样题目不就回到了跳台阶的样子了吗,就是一次跳1步或者2步呗。

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

✍ 二进制中1的个数

✨ 题目描述

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

💡 解题思路1

最简单的就是十进制转二进制那一套,n对2求余,n取商,统计余数为1的个数,直到n为0为止。但是这一套只对正数有效,对负数要求的是补码…

我发现Java里面有一个现成的API,toBinaryString,直接转字节串了,统计一下就好,但是解题是不可以调API的,不然就丢失了灵魂。

可能你会想,把正数和负数区分开来,然后计算?太麻烦了吧,转来转去的不想搞🤣。

你可以这么想,假如你现在是在判断一个二进制的数有几个1,而不是一个十进制的数,那你要怎么统计呢?与运算,用1和这个二进制的每一位进行与运算,如果不是0,那就是1,否则就是0。但问题是摆在面前的是一个十进制的数,怎么得到二进制的数?与运算啊🤣,计算机存储的数字其实底层已经是二进制了,运算的时候也是二进制运算,压根就不需要你去转。直接用就OK。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int NumberOf1(int n) {
int sum = 0;
int flag = 1;
while(flag != 0){
if((flag & n) != 0){
sum++;
}
flag = flag << 1;
}
return sum;
}
}

💡 解题思路2

思路其实是一样的,只不过上一种解法有个小小的弊端:运算的次数比较多,必须等到flag=0的时候才会结束,什么时候=0?超出位数的时候!

最好的解法是,有几个1就计算几次。那就是说每运算一次,数字的二进制形式就会少一个1,这个少一个1的少法肯定是从右边开始,比如这样:

7 -> 111 ——– 统计一次,目前统计的1的个数为1

6 -> 110 ——– 最右边少了一个1了,这时统计的1的个数为2

4 -> 100 ——– 再次少了一个1,统计个数为3

再少一个1后就是000 = 0了,结束,确实有几个1,计算了几次。那要怎么做到这种效果?就是让n每次对n - 1进行与运算

1
2
3
4
5
6
7
8
9
10
public class Solution {
public int NumberOf1(int n) {
int sum = 0;
while(n != 0){
sum++;
n = n & (n - 1);
}
return sum;
}
}

✍ 数值的整数次方

✨ 题目描述

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

保证base和exponent不同时为0

💡 解题思路1

这个题目好理解啊,一个简单的做法就是:数值的n次方实际就是这个数乘了n次,那就可以循环做咯。(需要注意的是这个n可能为负数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public double Power(double base, int exponent) {
if(base == 0){
return 0;
}
if(exponent == 0){
return 1;
}
double res = 1;
boolean flag = exponent > 0;
exponent = exponent > 0 ? exponent : -1 * exponent;
for(int i = 0; i < exponent; i++){
res = res * base;
}
return flag ? res : 1 / res;
}
}

这种解法是最low的,时间复杂度很明显是O(n)

💡 解题思路2

还有一种解法叫做快速求幂,这种解法的时间复杂度是O(log2n),比O(n)快了很多。

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) {
if(base == 0){
return 0;
}
if(exponent == 0){
return 1;
}
double res = 1;
boolean flag = exponent > 0;
exponent = exponent > 0 ? exponent : -1 * exponent;
while(exponent > 0){
if(exponent % 2 == 1){
res = res * base;
}
base = base * base;
exponent = exponent / 2;
}
return flag ? res : 1 / res;
}
}
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) {
if(base == 0){
return 0;
}
if(exponent == 0){
return 1;
}
double res = 1;
boolean flag = exponent > 0;
exponent = exponent > 0 ? exponent : -1 * exponent;
while(exponent > 0){
if((exponent & 1) == 1){
res = res * base;
}
base = base * base;
exponent = exponent >> 1;
}
return flag ? res : 1 / res;
}
}

✍ 调整数组顺序

✨ 题目描述

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

💡 解题思路1

一种方法,先从左到右找到第一个偶数i,然后从i往后找到第一个奇数j,把这两个交换一下,重复这个操作就完事了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
public void reOrderArray(int [] array) {
int i = 0, j = 0;
while(i < array.length && j < array.length){
while(i < array.length && array[i] % 2 != 0){
i++;
}
j = i + 1;
while(j < array.length && array[j] % 2 == 0){
j++;
}
if(i < array.length && j < array.length && array[i] % 2 == 0 && array[j] % 2 != 0){
for(int k = j; k > i; k--){
int temp = array[k];
array[k] = array[k - 1];
array[k - 1] = temp;
}
}
}
}
}

✍ 链表中倒数第k个节点

✨ 题目描述

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

💡 解题思路1

题目给出的链表是一个单向链表,单向链表是不能向前搜索的。因此一个办法是先记录链表的长度n,然后再找第n - 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
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
import java.util.ArrayList;

public class Solution {
public ListNode FindKthToTail(ListNode head, int k) {
if(head == null){
return null;
}
int n = 0;
ListNode p = head;
while(p != null){
n++;
p = p.next;
}
if(n < k){
return null;
}
ListNode node = head;
for(int i = 0; i < n - k; i++){
node = node.next;
}
return node;
}
}

✍ 反转链表

✨ 题目描述

输入一个链表,反转链表后,输出新链表的表头。

💡 解题思路1

假设有链表如下

aaa

现有三个指针premidnext的指向位置如下

p1

可以看出,只需mid指向pre,节点1、2就完成反转,再重新调整三个指针的位置,使三个指针整体向前移动一个位置,一次调整如下

p2

只需重复以上步骤就可以完成链表反转

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 ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode pre = null, mid = head, next = null, newHead = null;
while(mid != null){
next = mid.next;
if(next == null){
newHead = mid;
}
mid.next = pre;
pre = mid;
mid = next;
}
return newHead;
}
}

✍ 合并两个排序链表

✨ 题目描述

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

💡 解题思路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
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode p1 = list1, p2 = list2, p = new ListNode(-1), curr = p;
while(p1 != null || p2 != null){
int val1 = p1 == null ? Integer.MAX_VALUE : p1.val;
int val2 = p2 == null ? Integer.MAX_VALUE : p2.val;
if(val1 < val2){
curr.next = p1;
p1 = p1.next;
}else{
curr.next = p2;
p2 = p2.next;
}
curr = curr.next;
}
return p.next;
}
}

✍ 树的子结构

✨ 题目描述

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

💡 解题思路1

子树意味着A树有一部分和B树相同,那么只需要将A的子树和B一一比较,如果有一个匹配了,那么B就是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
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null){
return false;
}
return isSubTree(root1, root2)
|| HasSubtree(root1.left, root2)
|| HasSubtree(root1.right, root2);
}

private boolean isSubTree(TreeNode root1, TreeNode root2) {
if(root2 == null){
return true;
}
if(root1 == null && root2 != null){
return false;
}
if(root1.val == root2.val){
return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right);
}else{
return false;
}
}
}

✍ 二叉树的镜像

✨ 题目描述

操作给定的二叉树,将其变换为源二叉树的镜像。

💡 解题思路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 TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root == null){
return;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
Mirror(root.left);
Mirror(root.right);
}
}

✍ 顺时针打印矩阵

✨ 题目描述

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: 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

题目没什么好说的,照着意思写就对了

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
import java.util.ArrayList;
public class Solution {

public static ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> res = new ArrayList<>();
if(matrix == null || matrix.length == 0){
return res;
}
int left = 0, right = matrix[0].length - 1, top = 0, buttom = matrix.length - 1;
while(left <= right && top <= buttom){
//上一行
for(int i = left; i < right; i++){
res.add(matrix[top][i]);
}
//右一列
for(int i = top; i <= buttom; i++){
res.add(matrix[i][right]);
}
if(left < right && top < buttom){
//下一行
for(int i = right - 1; i >= left; i--){
res.add(matrix[buttom][i]);
}
//左一列
for(int i = buttom - 1; i > top; i--){
res.add(matrix[i][left]);
}
}
left++;
right--;
top++;
buttom--;
}
return res;
}
}

✍ 栈的压入、弹出序列

✨ 题目描述

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

💡 解题思路1

很简单,我在给定一个压入序列,判断另一个序列是不是出栈序列的时候,我会在脑海中模拟这个压入序列,如果压入的过程中碰到了和出栈序列相同的值,那么就出栈。重复这个步骤直到两边都为空为止。按照这个思路写代码即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.ArrayList;

public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA == null || popA == null){
return false;
}
int index1 = 0, index2 = 0;
ArrayList<Integer> list = new ArrayList<>();
while(index1 < pushA.length && index2 < popA.length){
list.add(0, pushA[index1++]);
while(list.size() > 0 && list.get(0) == popA[index2]){
list.remove(0);
index2++;
}
}
return index2 == popA.length;
}
}

✍ 从上往下打印二叉树

✨ 题目描述

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

💡 解题思路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
import java.util.ArrayList;
import java.util.LinkedList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
if(root == null){
return res;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(queue.size() > 0){
TreeNode node = queue.poll();
if(node == null){
continue;
}
res.add(node.val);
queue.offer(node.left);
queue.offer(node.right);
}
return res;
}
}

✍ 二叉搜索树的后序遍历

✨ 题目描述

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

💡 解题思路1

二叉搜索树有一个特性:任意一个节点,该节点的左子节点一定比这个节点小,右子节点一定比这个节点大。

如果是中序遍历,显然是一个递增的序列,如果是后续遍历,比如下图:

这个树的后续遍历是:5 7 6 9 11 10 8

可以看出来,如果按照根节点分,可以把后序遍历的序列分为两部分,一部分都比根节点8小,一部分都比根节点8大,即左子树和右子树。同样的,拆分后的序列也会有这种特性。即判断一个序列是不是二叉搜索树的后序遍历,只需判断是否满足这个特性即可。

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 {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence == null || sequence.length == 0){
return false;
}
return judge(sequence, 0, sequence.length - 1);
}

private boolean judge(int[] sequence, int start, int end){
if(start >= end){
return true;
}
int index = start;
while(index < end && sequence[index] <= sequence[end]){
index++;
}
for(int i = index; i <= end; i++){
if(sequence[i] < sequence[end]){
return false;
}
}
return judge(sequence, start, index - 1) && judge(sequence, index, end - 1);
}
}

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

✨ 题目描述

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

💡 解题思路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
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(root == null || root.val > target){
return res;
}
findPath(root, target, res, new ArrayList<Integer>(), 0);
return res;
}

private void findPath(TreeNode root, int target, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> temp, int sum){
if(root == null){
return;
}
sum = sum + root.val;
if(root.left == null && root.right == null){
if(sum == target){
temp.add(root.val);
res.add(new ArrayList<>(temp));
temp.remove(temp.size() - 1);
}
return;
}
temp.add(root.val);
findPath(root.left, target, res, temp, sum);
findPath(root.right, target, res, temp, sum);
temp.remove(temp.size() - 1);
}
}

✍ 复杂链表的复制

✨ 题目描述

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

💡 解题思路1

方法很简单,先把next链复制下来,然后再一个一个的去找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
33
34
35
36
37
38
39
40
41
42
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;

RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead == null){
return null;
}
RandomListNode res = new RandomListNode(-1);
RandomListNode p = pHead, curr = res;
while(p != null){
curr.next = new RandomListNode(p.label);
curr = curr.next;
p = p.next;
}
p = pHead;
RandomListNode node = res.next;
while(p != null){
curr = res.next;
boolean find = false;
while(p.random != null && curr != null){
if(curr.label == p.random.label){
node.random = curr;
break;
}
curr = curr.next;
}
node = node.next;
p = p.next;
}
return res.next;
}
}

💡 解题思路2

还有一种很有意思的解法:

首先在原来链表的基础上复制每一个节点到原来节点的后面,复制后如下图

接着根据原来的链表信息添加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
33
34
35
36
37
38
39
40
41
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;

RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead == null){
return null;
}
RandomListNode currNode = pHead;
while(currNode != null){
RandomListNode newNode = new RandomListNode(currNode.label);
RandomListNode nextNode = currNode.next;
currNode.next = newNode;
newNode.next = nextNode;
currNode = nextNode;
}
currNode = pHead;
while(currNode != null){
currNode.next.random = currNode.random == null ? null : currNode.random.next;
currNode = currNode.next.next;
}
RandomListNode res = pHead.next;
currNode = pHead;
while(currNode != null){
RandomListNode node = currNode.next;
currNode.next = node.next;
node.next = node.next == null ? null : node.next.next;
currNode = currNode.next;
}
return res;
}
}

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

✨ 题目描述

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

💡 解题思路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
import java.util.HashMap;

public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int num = 0, max = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < array.length; i++){
if(map.containsKey(array[i])){
int value = map.get(array[i]) + 1;
map.put(array[i], value);
if(max < value){
max = value;
num = array[i];
}
}else{
map.put(array[i], 1);
if(max < 1){
max = 1;
num = array[i];
}
}
}
int half = array.length / 2;
return max > half ? num : 0;
}
}

💡 解题思路2

既然超过了一半,那么对这个数组排序以后,中间的那个数一定是超过一半的那个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.Arrays;

public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0){
return 0;
}
Arrays.sort(array);
int res = array[array.length / 2];
int times = 0;
for(int i = 0; i < array.length; i++){
if(array[i] == res){
times++;
}
}
return times > array.length / 2 ? res : 0;
}
}

💡 解题思路3

另一种有意思的解法是:既然有一个数超过了总数的一半,那么意味着这个数的数量就会比其它的数的和还要多。考虑一种极端的情况:超过总数一半的数在左边,其他的数在右边;初始的时候记录值为第一个数,统计值为1,遍历整个数组,如果碰到了相同的数,统计值+1,否则-1,如果统计值为0,修改记录值为下一个数,统计值为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 {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0){
return 0;
}
int res = array[0], times = 1;
for(int i = 1; i < array.length; i++){
if(times == 0){
res = array[i];
times = 1;
}else if(array[i] == res){
times++;
}else{
times--;
}
}
times = 0;
for(int i = 0; i < array.length; i++){
if(array[i] == res){
times++;
}
}
return times > array.length / 2 ? res : 0;
}
}

✍ 最小的K个数

✨ 题目描述

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

💡 解题思路1

最简单的就是先对整个数组排序,然后取前K个即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;

public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if(input == null || input.length == 0 || k < 0 || k > input.length){
return res;
}
Arrays.sort(input);
for(int i = 0; i < k; i++){
res.add(input[i]);
}
return res;
}
}

💡 解题思路2

对整个数组排序的代价就比较大了,因为只是需要k个数而已。可以参考冒泡排序的思路,只进行k次排序,找出k个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if(input == null || input.length == 0 || k < 0 || k > input.length){
return res;
}
for(int i = 0; i < k; i++){
for(int j = i + 1; j < input.length; j++){
if(input[i] > input[j]){
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
}
res.add(input[i]);
}
return res;
}
}

💡 解题思路3

第二种解法参考了冒泡排序的思想,这一种可以再参考快速排序的思想:每一次选择一个中间值,一次排序将小于这个中间值的数方在左边,大于这个中间值的数放在右边,再对左右两边重复这个操作即可。同样的,如果要找到K个最小的数,就可以理解为在进行快速排序的时候,某一个时刻这个中间值的为止恰好是k,那么前面的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
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;

public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if (input == null || input.length == 0 || k > input.length || k < 0) {
return res;
}
int index = partition(input, start, end);
while (index != (k - 1)) {
if (index > (k - 1)) {
index = partition(input, 0, index - 1);
} else {
index = partition(input, index + 1, input.length - 1);
}
}
for (int i = 0; i < k; i++) {
res.add(input[i]);
}
return res;
}

private int partition(int[] input, int left, int right) {
int temp = input[left];
while (left < right) {
while (left < right && input[right] >= temp) right--;
input[left] = input[right];
while (left < right && input[left] <= temp) left++;
input[right] = input[left];
}
input[left] = temp;
return left;
}
}

💡 解题思路4

还可以参考堆排序的思想:假设堆排序使用大顶堆进行排序,按照堆排序的思想,每次将堆顶元素(数组中的最大值)和数组的最后一个元素交换位置,此时数组的最后一个值就是数组的最大值了,然后调整堆使之成为一个大顶堆,继续上述的步骤即可完成排序。放到这个问题上来说就是只要对len - 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
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
import java.util.*;

public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if(input == null || input.length == 0 || k < 0 || k > input.length){
return res;
}
buildMaxHeap(input);
int len = input.length, times = input.length - k;
for(int i = len - 1; i >= 0 && times > 0; i--){
swap(input, 0, i);
len--;
times--;
heapify(input, 0, len);
}
for(int i = 0; i < k; i++){
res.add(input[i]);
}
return res;
}

private void buildMaxHeap(int[] arr) {
for (int i = arr.length - 1; i >= 0; i--) {
heapify(arr, i, arr.length);
}
}

private void heapify(int[] arr, int index, int len) {
int left = index * 2 + 1, right = index * 2 + 2, largest = index;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != index) {
swap(arr, index, largest);
heapify(arr, largest, len);
}
}

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

✍ 连续子数组的最大和

✨ 题目描述

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

💡 解题思路1

题目很简单,就是求一个数组中连续的最大和。我们可以假设拥有了从第i个位置到第j个位置这一段序列,如果这一段序列的和为负数,就应该舍弃这一段序列,因为可以将这一段序列视为一个负数,为了使得值最大,自然不应该加上一个负数,同样的,如果序列的和大于等于0就保留,继续验证i ~ j + 1这一段序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int res = Integer.MIN_VALUE, temp = 0;
for(int i = 0; i < array.length; i++){
temp = temp + array[i];
res = Math.max(res, temp);
if(temp < 0){
temp = 0;
}
}
return res;
}
}

✍ 整数中1出现的次数

✨ 题目描述

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

💡 解题思路1

一个简单的方法是对数字进行拆解,统计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 res = 0;
for(int i = 1; i <= n; i++){
int temp = i;
while(temp > 0){
int x = temp % 10;
temp = temp / 10;
res = x == 1 ? res + 1 : res;
}
}
return res;
}
}

✍ 把数排成最小的数

✨ 题目描述

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

💡 解题思路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
import java.util.*;

public class Solution {
public String PrintMinNumber(int [] numbers) {
if(numbers == null || numbers.length == 0){
return "";
}
ArrayList<String> res = new ArrayList<>();
boolean[] visited = new boolean[numbers.length];
solution(numbers, res, visited, new StringBuilder(), 0);
Collections.sort(res);
return res.get(0);
}

private void solution(int[] arr, ArrayList<String> res, boolean[] visited, StringBuilder temp, int count){
if(count == arr.length){
res.add(temp.toString());
return;
}
for(int i = 0; i < arr.length; i++){
if(!visited[i]){
temp.append(arr[i]);
visited[i] = true;
solution(arr, res, visited, temp, count + 1);
temp.delete(temp.length() - String.valueOf(arr[i]).length(), temp.length());
visited[i] = false;
}
}
}
}

💡 解题思路2

对于两个字符串来说,如果要排列成最小的一个字符串,那么就可以比较这两个组合之后的字符串。对于超过两个字符串来说,可以比较第i个和第j个字符串组合之后的字符串,将小一号的字符串方在前面,这样最后得到的字符串就是最小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;

public class Solution {
public String PrintMinNumber(int [] numbers) {
String[] arr = new String[numbers.length];
for(int i = 0; i < arr.length; i++){
arr[i] = String.valueOf(numbers[i]);
}
Arrays.sort(arr, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));
StringBuilder res = new StringBuilder();
for(int i = 0; i < arr.length; i++){
res.append(arr[i]);
}
return res.toString();
}
}

✍ 丑数

✨ 题目描述

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

💡 解题思路1

假设nm的一个因子,那么必定有m % n == 0,同理,丑数的质因子为2、3、5,所以m % 2 == 0 && m % 3 == 0 && m % 5 == 0

对于某一个丑数xx * 2x * 3x * 5x * 2 * 3 * 5..都是丑数

要求第N个丑数,枚举过去就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index == 0) return 0;
int[] dp = new int[index + 1];
dp[1] = 1;
int i2 = 1, i3 = 1, i5 = 1;
for(int i = 2; i <= index; i++){
int temp2 = dp[i2] * 2, temp3 = dp[i3] * 3, temp5 = dp[i5] * 5;
int min = Math.min(temp2, Math.min(temp3, temp5));
if(temp2 == min) i2++;
if(temp3 == min) i3++;
if(temp5 == min) i5++;
dp[i] = min;
}
return dp[index];
}
}

✍ 第一个只出现一次的数字

✨ 题目描述

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

💡 解题思路1

简单啊,用HashMap保存每一个字符出现的次数,然后找到第一个出现一次的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.HashMap;

public class Solution {
public int FirstNotRepeatingChar(String str) {
if(str == null || str.length() == 0){
return -1;
}
HashMap<Character, Integer> map = new HashMap<>();
for(char ch : str.toCharArray()){
if(map.containsKey(ch)){
map.put(ch, map.get(ch) + 1);
}else{
map.put(ch, 1);
}
}
for(int i = 0; i < str.length(); i++){
if(map.get(str.charAt(i)) == 1){
return i;
}
}
return -1;
}
}

✍ 数组中的逆序对

✨ 题目描述

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

💡 解题思路1

一个简单的方法就是遍历每一对数字,检查是否是一个逆序对。但是这种做法超时了…

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int InversePairs(int [] array) {
long res = 0;
for(int i = 0; i < array.length; i++){
for(int j = i + 1; j < array.length; j++){
if(array[i] > array[j]){
res++;
}
}
}
return (int) res % 1000000007;
}
}

✍ 两个链表的第一个公共节点

✨ 题目描述

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

💡 解题思路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 ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
import java.util.ArrayList;

public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ArrayList<ListNode> list = new ArrayList<>();
while(pHead1 != null){
list.add(pHead1);
pHead1 = pHead1.next;
}
while(pHead2 != null){
if(list.contains(pHead2)) return pHead2;
pHead2 = pHead2.next;
}
return null;
}
}

💡 解题思路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
34
35
36
37
38
39
40
41
42
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int len1 = getListLength(pHead1);
int len2 = getListLength(pHead2);
int len = Math.abs(len1 - len2);
if(len1 > len2){
while(len > 0){
pHead1 = pHead1.next;
len--;
}
}else{
while(len > 0){
pHead2 = pHead2.next;
len--;
}
}
while(pHead1 != pHead2){
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
return pHead1;
}

private int getListLength(ListNode head){
ListNode p = head;
int res = 0;
while(p != null){
res++;
p = p.next;
}
return res;
}
}

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

✨ 题目描述

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

💡 解题思路1

简单的方法就是扫描整个数组,统计这个数字的次数,当然还可以根据题意进行优化一下,因为是排好序的,所以不需要扫描整个数组,扫描到指定的数字后,如果出现不是这个数字的时候就可以停止扫描了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public int GetNumberOfK(int [] array , int k) {
if(array == null || array.length == 0){
return 0;
}
int res = 0;
boolean find = false;
for(int i = 0; i < array.length; i++){
if(array[i] == k){
find = true;
res++;
}else if(find == true){
break;
}
}
return res;
}
}

💡 解题思路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
34
35
36
public class Solution {
public int GetNumberOfK(int [] array , int k) {
if(array == null || array.length == 0){
return 0;
}
int res = 0;
int index = binarySearch(array, k);
if(index == -1){
return 0;
}
while(index < array.length && array[index++] == k){
res++;
}
return res;
}

//二分搜索找到数字第一个出现的位置
private int binarySearch(int[] array, int target){
int left = 0, right = array.length - 1;
while(left < right){
int mid = left + (right - left) / 2;
if(array[mid] == target){
right = mid;
}else if(array[mid] < target){
left = mid + 1;
}else {
right = mid - 1;
}
}
if(array[left] == target){
return left;
}else{
return -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
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
public int TreeDepth(TreeNode root) {
if(root == null){
return 0;
}
int left = TreeDepth(root.left);
int right = TreeDepth(root.right);
return left > right ? (left + 1) : (right + 1);
}
}

✍ 平衡二叉树

✨ 题目描述

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

💡 解题思路1

平衡二叉树就是左子树和右子树的高度差不超过1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null){
return true;
}
int left = treeDepth(root.left);
int right = treeDepth(root.right);
return Math.abs(left - right) <= 1;
}

private int treeDepth(TreeNode root){
if(root == null){
return 0;
}
int left = treeDepth(root.left);
int right = treeDepth(root.right);
return left > right ? (left + 1) : (right + 1);
}
}

✍ 和为S的连续正数序列

✨ 题目描述

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

💡 解题思路1

一个简单的做法就是:遍历1 ~ sum的所有数,找出和为sum的序列

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

public class Solution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(sum <= 0){
return res;
}
for(int i = 1; i <= sum; i++){
int index = i, curr = 0;
while(curr < sum){
curr = curr + index;
index++;
}
if(curr == sum && (index - i) > 1){
ArrayList<Integer> temp = new ArrayList<>();
for(int j = i; j < index; j++){
temp.add(j);
}
res.add(temp);
}
}
return res;
}
}

💡 解题思路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
24
25
26
27
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(sum <= 0){
return res;
}
// n(a1 + an) / 2
for(int i = 1; i <= sum; i++){
for(int j = i + 1; j <= sum; j++){
int temp = (j - i + 1) * (i + j) / 2;
if(temp == sum){
ArrayList<Integer> list = new ArrayList<>();
for(int h = i; h <= j; h++){
list.add(h);
}
res.add(list);
break;
}
if(temp > sum){
break;
}
}
}
return res;
}
}

💡 解题思路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
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(sum <= 0){
return res;
}
int left = 1, right = 2;
while(left < right){
int temp = (right - left + 1) * (left + right) / 2;
if(temp == sum){
ArrayList<Integer> list = new ArrayList<>();
for(int i = left; i <= right; i++){
list.add(i);
}
res.add(list);
left++;
}else if(temp < sum){
right++;
}else{
left++;
}
}
return res;
}
}

✍ 和为S的两个数字

✨ 题目描述

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

💡 解题思路1

问题也很简单,找到所有的和为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
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> res = new ArrayList<>();
if(array == null || array.length == 0){
return res;
}
int num1 = -1, num2 = -1, min = Integer.MAX_VALUE;
for(int i = 0; i < array.length && array[i] <= sum; i++){
int index = binarySearch(array, sum - array[i], i + 1, array.length - 1);
if(index != -1 && (array[i] * array[index]) < min){
num1 = array[i];
num2 = array[index];
min = num1 * num2;
}
}
if(num1 + num2 == sum){
res.add(num1);
res.add(num2);
}
return res;
}

private int binarySearch(int[] array, int target, int left, int right){
if(left <= right){
int mid = left + (right - left) / 2;
if(array[mid] == target){
return mid;
}
if(array[mid] < target){
return binarySearch(array, target, mid + 1, right);
}else{
return binarySearch(array, target, left, mid - 1);
}
}
return -1;
}
}

💡 解题思路2

另一种思路首先需要明白:数字和相等的两个组合,相差越远的组合乘积越小。既然数组满足递增的特性,那么就可以设置一个左右指针,不断移动这两个指针使得和为指定值,然后当和为指定值的时候,这两个数就是答案(此时必然这个组合的距离最远)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> res = new ArrayList<>();
if(array == null || array.length == 0){
return res;
}
int left = 0, right = array.length - 1;
while(left < right){
if(array[left] + array[right] == sum){
res.add(array[left]);
res.add(array[right]);
break;
}
while(left < right && array[left] + array[right] < sum) left++;
while(left < right && array[left] + array[right] > sum) right--;
}
return res;
}
}

✍ 左旋转字符串

✨ 题目描述

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

💡 解题思路1

一个取巧的做法,切串即可

1
2
3
4
5
6
7
8
9
public class Solution {
public String LeftRotateString(String str,int n) {
if(str == null || str.length() == 0 || n == 0 || n % str.length() == 0){
return str;
}
n = n % str.length();
return str.substring(n) + str.substring(0, n);
}
}

✍ 左旋转字符串

✨ 题目描述

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

💡 解题思路1

照着题目意思做即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Arrays;

public class Solution {
public String ReverseSentence(String str) {
//把字符串按照空格切割一下,然后反转不就完了
if(str == null || str.equals(" ") || str.trim().equals("")) return str;
//if(str.trim().equals("")) return " ";
String[] strs = str.split(" ");
StringBuilder b = new StringBuilder();
for(int i = strs.length - 1; i >= 0; i--){
if(i == 0){
b.append(strs[i]);
}else{
b.append(strs[i]).append(" ");
}
}
return b.toString();
}
}

✍ 扑克牌顺子

✨ 题目描述

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的运气如何, 如果牌能组成顺子就输出true,否则就输出false。为了方便起见,你可以认为大小王是0。

💡 解题思路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
import java.util.Arrays;

public class Solution {
public boolean isContinuous(int [] numbers) {
if(numbers == null || numbers.length == 0){
return false;
}
Arrays.sort(numbers);
int zero = 0, pre = -1;
for(int i = 0; i < numbers.length; i++){
if(numbers[i] == 0){
zero++;
}else if(numbers[i] <= pre){
return false;
}else if(pre == -1){
pre = numbers[i];
}else if(numbers[i] - pre != 1){
zero = zero - (numbers[i] - pre - 1);
if(zero < 0){
return false;
}
pre = numbers[i];
}else{
pre = numbers[i];
}
}
return true;
}
}

✍ 孩子们的游戏

✨ 题目描述

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

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

💡 解题思路1

典型的约瑟夫环问题

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n == 0 || m == 0){
return -1;
}
int s = 0;
for(int i = 2; i <=n; i++){
s = (s + m) % i;
}
return s;
}
}

✍ 求1+2+3+…+n

✨ 题目描述

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

💡 解题思路1

不能使用循环、判断就套公式咯

等差序列的公式:a1 * n + n * (n - 1) * d / 2n * (a1 + an) * d / 2

1
2
3
4
5
6
7
8
9
public class Solution {
public int Sum_Solution(int n) {
if(n <= 0){
return 0;
}
// n * (a1 + an) * d / 2
return n * (1 + n) / 2;
}
}

✍ 不用加减乘除做加法

✨ 题目描述

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

💡 解题思路1

计算机中能够识别的只有0和1,进行运算的时候其实就是0和1的与、或等运算。

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;
}
}

✍ 把字符串转化为整数

✨ 题目描述

将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

💡 解题思路1

em…按照题目意思来就可以了,需要注意的是可能会超出int的范围

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 StrToInt(String str) {
if(str == null || str.length() == 0){
return 0;
}
long res = 0;
boolean negative = str.charAt(0) == '-' ? true : false;
for(int i = (str.charAt(0) == '-' || str.charAt(0) == '+') ? 1 : 0; i < str.length(); i++){
if(str.charAt(i) < '0' || str.charAt(i) > '9'){
return 0;
}
res = res * 10 + (str.charAt(i) - '0');
}
res = negative ? (-1 * res) : res;
if(res > Integer.MAX_VALUE || res < Integer.MIN_VALUE){
return 0;
}
return (int) res;
}
}

✍ 数组中重复的数字

✨ 题目描述

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

💡 解题思路1

可以使用一个Map记录出现的数字,如果遍历到的数字已经记录在Map中,那么这个就是第一个重复的数字,直接返回即可。(当然也可以利用数值在0 ~ n - 1这个区间使用boolean来记录一个数字是否出现过)

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.HashMap;

public class Solution {
// 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) {
if(numbers == null || numbers.length == 0 || length <= 0){
return false;
}
HashMap<Integer, Integer> map = new HashMap<>();
int res = 0;
for(int i = 0; i < length; i++){
if(map.containsKey(numbers[i])){
duplication[0] = numbers[i];
return true;
}else{
map.put(numbers[i], 1);
}
}
return false;
}
}

💡 解题思路2

当然如果不想使用额外的空间也是可以的,遍历numbers数组,然后这个数组对应位置上的值+length,下一次如果遍历到相同的一个数的时候,对应位置上就会numbers[n] > length,这个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
public class Solution {
// 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) {
if(numbers == null || numbers.length == 0 || length == 0){
return false;
}
for(int i = 0; i < length; i++){
int n = numbers[i];
if(n >= length){
n -= length;
}
if(numbers[n] >= length){
duplication[0] = n;
return true;
}
numbers[n] = numbers[n] + 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]。不能使用除法。

💡 解题思路1

题目的意思是最后的B数组中,B[i]就是A中除了A[i]各个数的乘积。既然不可以用除法,那么可以用个最简单的方法,对于每个A[i]都乘一次呗(当然是不可能用这种方法的,太耗时太蠢了)。

可以考虑构造两个数组,一个数组是没有乘第一个数的序列,第二个是没有乘最后一个数的序列。如下:

第一个序列:1 a1 a1a2 a1a2a3

第二个序列:a2a3a4 a3a4 a4 1

那么这两个序列对于位置上相乘就是结果B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int[] multiply(int[] A) {
if(A.length <= 1) return A;
int[] B = new int[A.length];
B[0] = 1;
for(int i = 1; i < B.length; i++){
B[i] = B[i - 1] * A[i - 1];
}
int temp = 1;
for(int i = B.length - 2; i >= 0; i--){
temp *= A[i + 1];
B[i] *= temp;
}
return B;
}
}

✍ 构建乘积数组

✨ 题目描述

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

💡 解题思路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 {
public boolean match(char[] str, char[] pattern){
if(str.length == 0 && pattern.length == 0) return true;
return match(str, pattern, 0, 0);
}

private boolean match(char[] str, char[] pattern, int i, int j){
if(i > str.length) return false;
if(i == str.length && j == pattern.length) return true;
if(i != str.length && j == pattern.length) return false;

if(j + 1 < pattern.length && pattern[j + 1] == '*'){
if((i < str.length && str[i] == pattern[j]) || pattern[j] == '.'){
return match(str, pattern, i, j + 2)
|| match(str, pattern, i + 1, j + 2)
|| match(str, pattern, i + 1, j);
}else{
return match(str, pattern, i, j + 2);
}
}
if((i < str.length && str[i] == pattern[j]) || pattern[j] == '.')
return match(str, pattern, i + 1, j + 1);
return false;
}
}

✍ 字符流中第一个不重复的字符

✨ 题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符”go”时,第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时,第一个只出现一次的字符是”l”。

💡 解题思路1

题目很简单,当然可以使用一个Map保存每个字符出现的次数,记录整个字符流,但是这样很傻。ASCII中一共是128个字符,因此可以使用一个大小为128的队列,每次让第一次出现的字符入队,其它不入队,然后只需判断队首的字符是不是只出现一次即可。

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.LinkedList;

public class Solution {

private LinkedList<Character> queue = new LinkedList<>();

private char[] chs = new char[128];

//Insert one char from stringstream
public void Insert(char ch){
chs[ch]++;
if(chs[ch] == 1){
queue.offer(ch);
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce(){
while(queue.size() > 0){
char ch = queue.peekFirst();
if(chs[ch] == 1){
return ch;
}else{
queue.pop();
}
}
return '#';
}
}

✍ 链表中环的入口节点

✨ 题目描述

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

💡 解题思路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
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}
*/
import java.util.ArrayList;

public class Solution {

public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead == null){
return null;
}
ArrayList<ListNode> list = new ArrayList<>();
ListNode p = pHead;
while(p != null){
if(list.contains(p)){
return p;
}
list.add(p);
p = p.next;
}
return null;
}
}

💡 解题思路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
34
35
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {

public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead == null) {
return null;
}
ListNode fast = pHead, slow = pHead;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
break;
}
}
if(fast == null || fast.next == null) {
return null;
}
slow = pHead;
while(fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}


 评论