8000 算法题解析 · iloveruning/Java-Guide@1707620 · GitHub
[go: up one dir, main page]
Skip to content 8000

Commit 1707620

Browse files
SnailclimbSnailclimb
committed
算法题解析
1 parent 9e1fc3d commit 1707620

6 files changed

+604
-0
lines changed

‎数据结构与算法/算法题解析/网易2018校招编程题1-3.md renamed to ‎数据结构与算法/算法题解析/公司真题/网易2018校招编程题1-3.md

File renamed without changes.

‎数据结构与算法/算法题解析/剑指offer/（1）斐波那契数列问题和跳台阶问题.md

Lines changed: 127 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,127 @@
1+
### 一 斐波那契数列
2+
#### **题目描述：**
3+
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
4+
n<=39
5+
6+
#### **问题分析：**
7+
可以肯定的是这一题通过递归的方式是肯定能做出来，但是这样会有一个很大的问题，那就是递归大量的重复计算会导致内存溢出。另外可以使用迭代法，用fn1和fn2保存计算过程中的结果，并复用起来。下面我会把两个方法示例代码都给出来并给出两个方法的运行时间对比。
8+
9+
#### **示例代码：**
10+
**采用迭代法：**
11+
12+
```java
13+
14+
int Fibonacci(int number) {
15+
if (number <= 0) {
16+
return 0;
17+
}
18+
if (number == 1 || number == 2) {
19+
return 1;
20+
}
21+
int first = 1, second = 1, third = 0;
22+
for (int i = 3; i <= number; i++) {
23+
third = first + second;
24+
first = second;
25+
second = third;
26+
}
27+
return third;
28+
}
29+
```
30+
**采用递归：**
31+
```java
32+
public int Fibonacci(int n) {
33+
34+
if (n <= 0) {
35+
return 0;
36+
}
37+
if (n == 1||n==2) {
38+
return 1;
39+
}
40+
41+
return Fibonacci(n - 2) + Fibonacci(n - 1);
42+
43+
}
44+
```
45+
46+
#### **运行时间对比：**
47+
假设n为40我们分别使用迭代法和递归法计算，计算结果如下：
48+
1. 迭代法
49+
![迭代法](https://ws1.sinaimg.cn/large/006rNwoDgy1fpydt5as85j308a025dfl.jpg)
50+
2. 递归法
51+
![递归法](https://ws1.sinaimg.cn/large/006rNwoDgy1fpydt2d1k3j30ed02kt8i.jpg)
52+
53+
54+
### 二 跳台阶问题
55+
#### **题目描述：**
56+
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
57+
#### **问题分析：**
58+
**正常分析法：**
59+
a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);
60+
b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)
61+
c.由a，b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)
62+
d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2
63+
**找规律分析法：**
64+
f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5， 可以总结出f(n) = f(n-1) + f(n-2)的规律。
65+
但是为什么会出现这样的规律呢？假设现在6个台阶，我们可以从第5跳一步到6，这样的话有多少种方案跳到5就有多少种方案跳到6，另外我们也可以从4跳两步跳到6，跳到4有多少种方案的话，就有多少种方案跳到6，其他的不能从3跳到6什么的啦，所以最后就是f(6) = f(5) + f(4)；这样子也很好理解变态跳台阶的问题了。
66+
67+
**所以这道题其实就是斐波那契数列的问题。**
68+
代码只需要在上一题的代码稍做修改即可。和上一题唯一不同的就是这一题的初始元素变为 1 2 3 5 8.....而上一题为1 1 2 3 5 .......。另外这一题也可以用递归做，但是递归效率太低，所以我这里只给出了迭代方式的代码。
69+
#### **示例代码：**
70+
```java
71+
72+
int jumpFloor(int number) {
73+
if (number <= 0) {
74+
return 0;
75+
}
76+
if (number == 1) {
77+
return 1;
78+
}
79+
if (number == 2) {
80+
return 2;
81+
}
82+
int first = 1, second = 2, third = 0;
83+
for (int i = 3; i <= number; i++) {
84+
third = first + second;
85+
first = second;
86+
second = third;
87+
}
88+
return third;
89+
}
90+
```
91+
92+
93+
### 三 变态跳台阶问题
94+
#### **题目描述：**
95+
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
96+
97+
#### **问题分析：**
98+
假设n>=2，第一步有n种跳法：跳1级、跳2级、到跳n级
99+
跳1级，剩下n-1级，则剩下跳法是f(n-1)
100+
跳2级，剩下n-2级，则剩下跳法是f(n-2)
101+
......
102+
跳n-1级，剩下1级，则剩下跳法是f(1)
103+
跳n级，剩下0级，则剩下跳法是f(0)
104+
所以在n>=2的情况下：
105+
f(n)=f(n-1)+f(n-2)+...+f(1)
106+
因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
107+
所以f(n)=2*f(n-1) 又f(1)=1,所以可得**f(n)=2^(number-1)**
108+
109+
#### **示例代码：**
110+
111+
```java
112+
int JumpFloorII(int number) {
113+
return 1 << --number;//2^(number-1)用位移操作进行，更快
114+
}
115+
```
116+
#### **补充：**
117+
**java中有三种移位运算符：**
118+
1. << : **左移运算符**，等同于乘2的n次方
119+
2. >>: **右移运算符**，等同于除2的n次方
120+
3. >>> **无符号右移运算符**，不管移动前最高位是0还是1，右移后左侧产生的空位部分都以0来填充。与>>类似。
121+
例：
122+
int a = 16;
123+
int b = a << 2;//左移2，等同于16 * 2的2次方，也就是16 * 4
124+
int c = a >> 2;//右移2，等同于16 / 2的2次方，也就是16 / 4
125+
126+
**欢迎关注我的微信公众号（分享各种Java学习资源，面试题，以及企业级Java实战项目回复关键字免费领取）：**
127+
![微信公众号](https://user-gold-cdn.xitu.io/2018/3/19/1623c870135a3609?w=215&h=215&f=jpeg&s=29172)

‎数据结构与算法/算法题解析/剑指offer/（2）二维数组查找和替换空格问题.md

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
### 一 二维数组查找
2+
#### **题目描述：**
3+
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
4+
#### **问题解析：**
5+
这一道题还是比较简单的，我们需要考虑的是如何做，效率最快。这里有一种很好理解的思路：
6+
7+
> 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
8+
因此从左下角开始查找，当要查找数字比左下角数字大时。右移
9+
要查找数字比左下角数字小时，上移。这样找的速度最快。
10+
11+
#### **示例代码：**
12+
```java
13+
public boolean Find(int target, int [][] array) {
14+
//基本思路从左下角开始找，这样速度最快
15+
int row = array.length-1;//行
16+
int column = 0;//列
17+
//当行数大于0，当前列数小于总列数时循环条件成立
18+
while((row >= 0)&& (column< array[0].length)){
19+
if(array[row][column] > target){
20+
row--;
21+
}else if(array[row][column] < target){
22+
column++;
23+
}else{
24+
return true;
25+
}
26+
}
27+
return false;
28+
}
29+
```
30+
### 二 替换空格
31+
#### **题目描述：**
32+
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
33+
#### **问题分析：**
34+
这道题不难，我们可以通过循环判断字符串的字符是否为空格，是的话就利用append()方法添加追加“%20”，否则还是追加原字符。
35+
36+
或者最简单的方法就是利用： replaceAll(String regex,String replacement)方法了，一行代码就可以解决。
37+
38+
#### **示例代码：**
39+
**常规做法：**
40+
```java
41+
public String replaceSpace(StringBuffer str) {
42+
StringBuffer out=new StringBuffer();
43+
for (int i = 0; i < str.toString().length(); i++) {
44+
char b=str.charAt(i);
45+
if(String.valueOf(b).equals(" ")){
46+
out.append("%20");
47+
}else{
48+
out.append(b);
49+
}
50+
}
51+
return out.toString();
52+
}
53+
```
54+
**一行代码解决：**
55+
```java
56+
public String replaceSpace(StringBuffer str) {
57+
//return str.toString().replaceAll(" ", "%20");
58+
//public String replaceAll(String regex,String replacement)
59+
//用给定的替换替换与给定的regular expression匹配的此字符串的每个子字符串。
60+
//\ 转义字符. 如果你要使用 "\" 本身, 则应该使用 "\\". String类型中的空格用“\s”表示，所以我这里猜测"\\s"就是代表空格的意思
61+
return str.toString().replaceAll("\\s", "%20");
62+
}
63+
64+
```

‎数据结构与算法/算法题解析/剑指offer/（3）数值的整数次方和调整数组元素顺序.md

Lines changed: 113 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,113 @@
1+
### 一 数值的整数次方
2+
#### **题目描述：**
3+
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
4+
#### **问题解析：**
5+
这道题算是比较麻烦和难一点的一个了。我这里采用的是**二分幂**思想，当然也可以采用**快速幂**。
6+
更具剑指offer书中细节，该题的解题思路如下：
7+
1.当底数为0且指数<0时，会出现对0求倒数的情况，需进行错误处理，设置一个全局变量；
8+
2.判断底数是否等于0，由于base为double型，所以不能直接用==判断
9+
3.优化求幂函数（二分幂）。
10+
当n为偶数，a^n =（a^n/2）*（a^n/2）；
11+
当n为奇数，a^n = a^[(n-1)/2] * a^[(n-1)/2] * a。时间复杂度O(logn)
12+
13+
**时间复杂度**：O(logn)
14+
#### **示例代码：**
15+
```java
16+
public class Solution {
17+
boolean invalidInput=false;
18+
public double Power(double base, int exponent) {
19+
//如果底数等于0并且指数小于0
20+
//由于base为double型，不能直接用==判断
21+
if(equal(base,0.0)&&exponent<0){
22+
invalidInput=true;
23+
return 0.0;
24+
}
25+
int absexponent=exponent;
26+
//如果指数小于0，将指数转正
27+
if(exponent<0)
28+
absexponent=-exponent;
29+
//getPower方法求出base的exponent次方。
30+
double res=getPower(base,absexponent);
31+
//如果指数小于0，所得结果为上面求的结果的倒数
32+
if(exponent<0) F438
33+
res=1.0/res;
34+
return res;
35+
}
36+
//比较两个double型变量是否相等的方法
37+
boolean equal(double num1,double num2){
38+
if(num1-num2>-0.000001&&num1-num2<0.000001)
39+
return true;
40+
else
41+
return false;
42+
}
43+
//求出b的e次方的方法
44+
double getPower(double b,int e){
45+
//如果指数为0，返回1
46+
if(e==0)
47+
return 1.0;
48+
//如果指数为1，返回b
49+
if(e==1)
50+
return b;
51+
//e>>1相等于e/2，这里就是求a^n =（a^n/2）*（a^n/2）
52+
double result=getPower(b,e>>1);
53+
result*=result;
54+
//如果指数n为奇数，则要再乘一次底数base
55+
if((e&1)==1)
56+
result*=b;
57+
return result;
58+
}
59+
}
60+
```
61+
62+
当然这一题也可以采用笨方法：累乘。不过这种方法的时间复杂度为O（n），这样没有前一种方法效率高。
63+
```java
64+
// 使用累乘
65+
public double powerAnother(double base, int exponent) {
66+
double result = 1.0;
67+
for (int i = 0; i < Math.abs(exponent); i++) {
68+
result *= base;
69+
}
70+
if (exponent >= 0)
71+
return result;
72+
else
73+
return 1 / result;
74+
}
75+
```
76+
### 二 调整数组顺序使奇数位于偶数前面
77+
#### **题目描述：**
78+
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
79+
80+
#### **问题解析：**
81+
这道题有挺多种解法的，给大家介绍一种我觉得挺好理解的方法：
82+
我们首先统计奇数的个数假设为n,然后新建一个等长数组，然后通过循环判断原数组中的元素为偶数还是奇数。如果是则从数组下标0的元素开始，把该奇数添加到新数组；如果是偶数则从数组下标为n的元素开始把该偶数添加到新数组中。
83+
84+
#### **示例代码：**
85+
时间复杂度为O（n），空间复杂度为O（n）的算法
86+
```java
87+
public class Solution {
88+
public void reOrderArray(int [] array) {
89+
//如果数组长度等于0或者等于1，什么都不做直接返回
90+
if(array.length==0||array.length==1)
91+
return;
92+
//oddCount：保存奇数个数
93+
//oddBegin：奇数从数组头部开始添加
94+
int oddCount=0,oddBegin=0;
95+
//新建一个数组
96+
int[] newArray=new int[array.length];
97+
//计算出（数组中的奇数个数）开始添加元素
98+
for(int i=0;i<array.length;i++){
99+
if((array[i]&1)==1) oddCount++;
100+
}
101+
for(int i=0;i<array.length;i++){
102+
//如果数为基数新数组从头开始添加元素
103+
//如果为偶数就从oddCount（数组中的奇数个数）开始添加元素
104+
if((array[i]&1)==1)
105+
newArray[oddBegin++]=array[i];
106+
else newArray[oddCount++]=array[i];
107+
}
108+
for(int i=0;i<array.length;i++){
109+
array[i]=newArray[i];
110+
}
111+
}
112+
}
113+
```

0 commit comments

Comments
 (0)
0