1. 打印从1到最大n位数
输入数字n,按顺序打印出从1到最大n位十进制数。比如输入3，则依次打印出 1 2 3 .. 999
解题思路：
首先考虑问题的时候要足够全面，数字整型会存在越界问题，所以对于此类型的问题，使用字符串拼接或者数组解决起来比较容易
1 | package com.nyist.offer; |
这个方法实现起来比较简单，效率较高
2.创建链表并删除链表中重复的元素
输入链表的长度，以及元素内容创建链表，找到重复的元素，删除。例如：输入链表长度为6，对应元素分别为 1,2,2,3,4,4，那么删除重复元素后链表的内容是:1,2,3,4
解题思路：
首先我们创建元素时候，遍历根节点知道为null的时候再创建当前节点，如果头节点为空的时候，直接创建的节点为根节点。找重复元素的时候，应该保留当前元素的前一个节点，然后发现当前节点和前一个节点的元素相同，则把前一个节点的下一个节点指向当前节点的下一个节点。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98package com.nyist.offer;
import java.util.Scanner;
public class DeleteLink {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入链表的长度:");
LinkNode1 linkNode = null;
if(!scanner.hasNextInt() || scanner.nextInt() <= 0){
System.out.println("输入不合法！");
}
else{
int len = scanner.nextInt();
for(int i = 0; i < len;i++){
System.out.print("请输入第"+(i+1)+"个数:");
if(scanner.hasNextInt()){
int num = scanner.nextInt();
if(linkNode == null){
linkNode = new LinkNode1(num);
}
else{
LinkNode1 linkNode1 = linkNode;
while (linkNode1.getNextNode1() != null){
linkNode1 = linkNode1.getNextNode1();
}
linkNode1.setNextNode1(new LinkNode1(num));
}
}
else{
System.out.println("输入不合法");
}
}
}
scanner.close();
deleteRepateNode(linkNode);
}
private static void deleteRepateNode(LinkNode1 linkNode) {
Integer temp = null;
if(linkNode != null){
LinkNode1 linkNode1 = linkNode;
LinkNode1 linkNode12 = linkNode1;
while (linkNode1 != null){
if(temp == null){
temp = linkNode1.getData();
linkNode12 = linkNode1;
linkNode1 = linkNode1.getNextNode1();
}
else{
if(linkNode1.getData() == temp){
linkNode12.setNextNode1(linkNode1.getNextNode1());
linkNode1 = linkNode12.getNextNode1();
}
else{
linkNode12 = linkNode1;
temp = linkNode12.getData();
linkNode1 = linkNode1.getNextNode1();
}
}
}
System.out.println(linkNode);
}
}
}
class LinkNode1{
private LinkNode1 nextNode;
private Integer data;
public LinkNode1(Integer data) {
this.data = data;
}
public LinkNode1() {
}
public LinkNode1 getNextNode1() {
return nextNode;
}
public void setNextNode1(LinkNode1 nextNode) {
this.nextNode = nextNode;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
}
3. 割绳子
给你一根长度为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。
解题思路：
使用动态规划。使用动态规划是从上往下分析，然后解决的时候是从下往上的解决，即从最小的问题入手，然后逐渐解决大问题的过程。
我们把最大乘积设置为f(n)，n表示绳子的长度。
首先我们分析绳子的长度为1的时候，没办法剪(m、n都是整数)，所以为0,即f(1) = 0；绳子的长度为2的时候，只有一个剪的办法,分半剪，分别为1,乘积为1,即f(2)=1;绳子长度为3的时候，可以分割成1,2或者1,1,1，那么最大的是1,2乘积为2,则f(3)=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
43
44
45
46package com.nyist.offer;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class CutStir {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入绳子的长度:");
int len = scanner.nextInt();
int maxMulti = cutResult(len);
System.out.println(maxMulti);
}
//动态规划
private static int cutResult(int len) {
if(len == 1) return 0;
else if(len == 2) return 1;
else if(len == 3) return 2;
int[] results = new int[len+1];
results[0] = 0;
results[1] = 1;
results[2] = 2;
results[3] = 3;
results[4] = 4;
int max = 0;
for(int i = 5;i <= len;i++){
max = 0;
for(int j = 1;j <= i/2;j++){
int result = results[j] * results[i-j];
if(result > max){
max = result;
}
}
results[i] = max;
}
max = results[len];
return max;
}
}
总结: 为了重复计算，我们自下向上的计算，然后把计算的结果存放在数组中.其中results数组中下标0,1,2,3,4对应的值为1,2,3,4,其实是当n大于4的时候，对应的1,2,3,4是可以不分割的。这时候最大。
4. 用13的瓷砖密铺320的地板有几种方式
用13的瓷砖密铺320的地板有几种方式
解题思路：
动态规划。3*n的问题，最后我们只需要把n设置成20即可解决问题。当n=1的时候，只有一种铺法，f(1)=1;当n=2的时候，两个都要竖着铺，则只有一个方法，即f(2)=1;当n=3的时候，竖着或者横着铺3个，有2种方法，即f(3)=2，那么如果n = n,那么首先如果我们使用横着铺，那么面积还剩余3(n-1)，如果竖着铺，则下面长度为2,和上面选择同样的方式，则右面的部分可以有其他的选择，选择面积3（n-3）,那么f(n) = (n-1)+(n-3)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32package com.nyist.offer;
import java.util.Scanner;
/**
* 关于铺瓷砖的问题
* 用1*3的瓷砖密铺3*20的地板有几种方式
*/
public class TilingProgram {
public static void main(String[] args) {
int n = 20;
int way = tiling(n);
System.out.println("共有"+way+"种方法！");
}
private static int tiling(int n) {
int[] ways = new int[n+1];
if(n == 0) return 1;
if(n == 1) return 1;
if(n == 2) return 1;
if(n == 3) return 2;
ways[0] = 1;
ways[1] = 1;
ways[2] = 1;
ways[3] = 2;
for(int i = 4; i <= n;i++){
ways[i] = ways[i-1]+ways[i-3];
}
return ways[20];
}
}
5.调整数组的顺序使奇树位于偶数前面
输入一个数组，实现一个函数来调整该数组的顺序，使得所有的奇数位于数组的前部，数组的偶数位于数组的后半部分**
解题思路：
我们解决这个问题可以使用辅助数组，那么空间复杂度为O(n),但是不是我们想要的结果，那么我们可以使用两个指向，一个指向数组的头部，一个指向数组的尾部，然后分别靠近，知道相遇再结束，靠近的过程中，如果左边的指向是奇数，那么++,右边的指向为偶数同样++,当两边相反的时候交换1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53package com.nyist.offer;
public class ChangeArr {
public static void main(String[] args) {
int[] arr = new int[]{1,2,3,3,4,0,5,5,6,6,7};
arr = doChange(arr);
showResult(arr);
}
private static void showResult(int[] arr) {
System.out.println("改变后的数组:");
for (int i : arr) {
System.out.print(i+" ");
}
}
private static int[] doChange(int[] arr) {
int l = 0;
int r = arr.length-1;
while (true){
if(l >= r){
break;
}
if(isOk(arr[l]) && isOk(arr[r])){
l++;
}
if(!isOk(arr[l]) && isOk(arr[r])){
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
l++;
r--;
}
if(isOk(arr[l]) && !isOk(arr[r])){
l++;
r--;
}
if(!isOk(arr[l]) && !isOk(arr[r])){
r--;
}
}
return arr;
}
private static boolean isOk(int num) {
if(num % 2 != 0){
return true;
}
return false;
}
}
注: 考虑时间复杂度和空间复杂度，以及我们函数的相似部分的抽离，上述的问题是根据奇偶数把数组分成前后两部分，然后我们遇到下一个类型的题目，例如，根据是都是2的幂次方分成前后两部分，这时候我们只需要改写isOK函数的部分。
算法很有意思，渐渐修炼中…贵在坚持
