集合1

一、JAVA的集合
  Java集合类是一种特别有用的工具类,可用于存储数量不确定的对象(对象的引用),并可以实现常用 的数据结构,如栈、队列等。除此之外,Java集合还可用于保存具有映射关系的关联数组。Java集合大致可分为List、Set、Queue和Map四种体系。

  • List:代表有序、 重复的集合
  • Set:代表无序、不可重复的集合
  • Map:代表具有映射关系的集合
  • Queue:代表一种队列集合实现(Java5之后)

JAVA的集合类与数组的区别

  1. 数组一旦确定之后不能更改大小,所以JAVA引出了集合类的东西来满足存放长度不确定的对象(对象的引用)。
  2. JAVA的集合类只能存放对象,数组也可以存放基本类型数据。

二、Connection接口(根接口)

①常用的方法:

  1. public boolean add(E e); 给定的对象放到当前集合中。
  2. public void clear(); 清空当前集合中的所有元素。
  3. public boolean remove(E e); 把给定的对象在当前集合中删除。
  4. public boolean contains(E e); 判断当前集合是否包含给定的对象。
  5. public boolean isEmpty(); 判断当前集合是否为空。
  6. public int size(); 返回集合中元素的个数。
  7. public Object[] toArray(); 把集合中的元素存储到数组中。

具体实现:

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

public class Main {
public static void main(String[] args) {
//创建一个集合对象(多态)
Collection<String> names=new ArrayList<String>();
//添加
names.add("郭德纲");
names.add("刘德华");
names.add("柳岩");
names.add("范伟");

//删除
System.out.println(names); 输出[郭德纲, 刘德华, 柳岩, 范伟]
boolean a=names.remove("郭德纲");
System.out.println(a); //输出true
System.out.println(names); //输出[刘德华, 柳岩, 范伟]

//获取长度
int size=names.size();
System.out.println(size); //输出3

//清空集合中所有元素
names.clear();

//判断是否为空
boolean b=names.isEmpty();
System.out.println(b); //输出true

}
}

代码结果:

[郭德纲, 刘德华, 柳岩, 范伟]
true
[刘德华, 柳岩, 范伟]
3
true


Lambda表达式

一、介绍接口实现的三种方法,引出Lambda表达式。

  定义接口(comparator):

1
2
3
interface comparator{ 
int compare(int a,int b); //抽象方法
}

  定义实现类(Mycomparator):

1
2
3
4
5
6
class Mycomparator implements comparator{  //实现类必须实现接口里面的所有抽象方法
@override
public int compare(int a,int b){
return a-b;
}
}

  • 1.使用接口实现类
    1
    2
    3
    4
    5
    6
    public class ChengXu{
    public static void main(String[] args){
    comparator comparator1=new Mycomparator(); //多态(左边父类,右边子类) 编译在左,实现在右
    comparator1.compare;
    }
    }

  • 2.使用匿名接口类
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public class ChengXu{
    public static void main(String[] args){
    comparator comparator2=new comparator(){ //哪个接口要实现就写哪个接口的匿名抽象类
    @override
    public int compare(int a,int b){
    return a-b;
    }
    }
    }
    }

  • 3.使用Lambda表达式
    1
    2
    3
    4
    5
    public class ChengXu{
    public static void main(String[] args){
    comparator comparator3=(a,b) ->a-b;
    }
    }

二、Lambda表达式的基本语法
1.Lambda表达式只能描述只有一个抽象方法的接口(@FunctionalInterface注释)。
2.也可以用于集合类中遍历集合元素。
3.包含三个部分

  1. 形参列表:允许省略参数类型。(一个参数的话可以省略形参的圆括号)。
  2. 箭头(->):必须有英文画线和大于符号组成。
  3. 代码块:如果只有一句,省略”{}”。
  4. java8中引入了一个新的操作符”->”(箭头操作符/Lambda操作符),将Lambda表达式拆分为两个部分:
  5. 左边:Lambda表达式的参数列表(实现的抽象方法参数相同)
  6. 右边:Lambda表达式中所需要的功能(方法体)

三、函数式接口
  代表只含有一个抽象方法接口(默认方法、类方法可以有很多)。
  JAVA8专门为函数式接口提供了@FunctionalInterface注解。放在接口定义的前面,用于告诉编译器执行更为严格检查,不是函数式接口就会报错。


例如:

1
2
3
4
5
6
Runnable r=()->{
for(int i=0;i<100;i++)
{
System.out.println();
}
};

解释:
Lambda表达式实现的是匿名方法(只能实现特定函数式接口的唯一方法),因此就有两个限制

  1. Lambda表达式的目标类型必须是明确的函数式接口。(我觉得最适合的就是(参数列表强制类型转换))
  2. Lambda表达式只能为函数式接口创建对象。

Java在java.util.function包下面预定义了很多函数式接口

  1. XxxFunction:这类接口中通常有一个apply()抽象方法,对参数处理后返回一个新的值。
  2. XxxConsumer:这类接口中通常有一个accept()抽象方法,对参数处理后但是不返回新的值。
  3. XxxPredicate:这类接口中通常有一个test()抽象方法,对参数进行某种处理后返回一个boolean值,用于筛选数据。
  4. XxxSupplier:这类接口中通常有一个getAsXxx()抽象方法,不需要输入一个值通过某种算法返回一个值。

四、方法引用和构造器引用
  如果Lambda表达式的代码块只有一条代码,那么就可以在代码块中使用方法引用和构造器引用。

人机交互实验

页面介绍:主要是电影资源网,分为热映部分和广告部分以及热门电影部分。
然后使用CSS的标题框模块等增强H5代码形成的框架感(我主要给最下面的底部和导航弄了CSS格式)。

主页面H5和CSS的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
<!DOCTYPE html >
<html >

<!--head部分-->
<head>
<meta charset=UTF-8">

<!--设置各种格式-->
<style>
ul {
list-style-type: none;
margin: 0;
padding: 0;
overflow: hidden;
background-color: white;<!--导引行字背景-->
}

li {
float: left;
}

li a {
display: gray;
color: blue;<!--字体颜色-->
text-align: center;
padding: 14px 16px;
text-decoration: none;
}

li a:hover {
background-color: red;<!--选中后背景-->
}

<!--底部的格式-->
#bottom{
margin:30px auto 0px auto;
width:1200px;
height:40px;
line-height:40px;
border-top:1px solid #CCCCCC;
}

#bottom .copyright{
float:left;
color:#999999;
font-family:"微软雅黑";
font-size:14px;}


</style>

</head>


<!--body部分-->
<body>

<!--头部显示 电影资源网-->
<ul>
<br></br>
<li><a href="javascript:;">电影购票</a></li>
<li><a href="detail/dianying.html">电影</a></li>
<li><a href="javascript:;">电视剧</a></li>
<li><a href="javascript:;">少儿</a></li>
<li><a href="javascript:;">其他</a></li>
<li><a href="javascript:;">圈子</a></li>
<li><a href="javascript:;">最热电影</a></li>
</ul>

<!--正在热映部分-->
<div id="main">
<div id="left">
<div class="is-on">
<div class="hd">
<h2>正在热映</h2>
<div class="right">
<a class="leftBtn" href="javascript:;"></a>
<a class="rightBtn" href="javascript:;"></a>
</div>
</div>
<div class="bd">
<div class="container">
<ul>

<li>
<a href="detail/mnyys.html"><img src="images/1.jpg" alt="" />
</a>
<p><a href="detail/mnyys.html">美女与野兽</a>

<span class="score">7.2分</span></p>


</li>

<li>
<a href="detail/thwj.html"><img src="images/2.jpg" alt="" />
</a>
<p><a href="detail/thwj.html">头号玩家</a>

<span class="score">8.7分</span></p>


</li>

<li>
<a href="detail/fwhyj.html"><img src="images/3.jpg" alt="" />
</a>
<p><a href="detail/fwhyj.html">飞屋环游记</a>

<span class="score">8.9分</span></p>


</li>

<li>
<a href="detail/mtyj.html">
<img src="images/4.jpg" alt="" />
</a>
<p><a href="detail/mtyj.html">摩天营救</a>

<span class="score">8.6分</span></p>

</li>

<li>
<a href="detail/yhhwd.html"><img src="images/5.jpg" alt="" />
</a>
<p><a href="detail/yhhwd.html">银河护卫队</a>

<span class="score">8.0分</span></p>

</li>
</ul>
</div>
</div>
</div>

<!--中间广告部分-->
<div class="banner">
<a href="javascript:;"><img src="images/banner2.jpg" /></a>
</div>

<!--热门电影部分-->
<div class="hot-film">
<div class="hot-film-top">
<h2>热门电影</h2>
<ul>
<li><a>热门</a></li>
<li><a>最新</a></li>
<li><a>更多</a></li>
<br></br>
</ul>
</div>
<div class="hot-film-main">
<div class="hot-film-list">
<ul>
<li>
<a href="detail/thwj.html">
<img src="images/2.jpg" alt="" />
</a>
<p><a href="detail/thwj.html">头号玩家</a>
<span class="score">8.7分</span></p>
</li>

<li>
<a href="detail/fwhyj.html">
<img src="images/3.jpg" alt="" />
</a>
<p><a href="detail/fwhyj.html">飞屋环游记</a>
<span class="score">8.9分</span></p>
</li>

<li>
<a href="detail/yhhwd.html">
<img src="images/5.jpg" alt="" />
</a>
<p><a href="detail/yhhwd.html">银河护卫队</a>
<span class="score">8.0分</span></p>
</li>

<li>
<a href="detail/crzdy2.html">
<img src="images/1.jpg" alt="" />
</a>
<p><a href="detail/mnyys.html">美女与野兽</a>
<span class="score">8.7分</span></p>
</li>

<li>
<a href="detail/jtmdt.html">
<img src="images/4.jpg" alt="" />
</a>
<p><a href="detail/mtyj.html">摩天营救</a>
<span class="score">7.5分</span></p>
</li>

</ul>
</div>


</div>
</div>
</div>


<!--最下面的部分-->

<div id="bottom">
<span class="copyright">电影资源网 </span>
</div>

</body>

</html>

主页面截图:


二级页面显示其中一个电影的具体情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
<!DOCTYPE html >
<html >
<head>
<meta charset=utf-8" />
<title>飞屋环游记的介绍</title>
<style>
ul {
list-style-type: none;
margin: 0;
padding: 0;
overflow: hidden;
background-color: white;<!--导引行字背景-->
}

li {
float: left;
}

li a {
display: gray;
color: blue;<!--字体颜色-->
text-align: center;
padding: 14px 16px;
text-decoration: none;
}

li a:hover {
background-color: red;<!--选中后背景-->
}

<!--底部的格式-->
#bottom{
margin:30px auto 0px auto;
width:1200px;
height:40px;
line-height:40px;
border-top:1px solid #CCCCCC;
}

#bottom .copyright{
float:left;
color:#999999;
font-family:"微软雅黑";
font-size:14px;}

</style>

</head>

<body>
<ul>
<br></br>
<li><a href="javascript:;">电影购票</a></li>
<li><a href="javascript:;">电影</a></li>
<li><a href="javascript:;">电视剧</a></li>
<li><a href="javascript:;">少儿</a></li>
<li><a href="javascript:;">其他</a></li>
<li><a href="javascript:;">圈子</a></li>
<li><a href="javascript:;">最热电影</a></li>
</ul>


<div id="left">
<h1>
<span>飞屋环游记</span>
<span>(2010)</span>
</h1>
<div class="subject">
<div class="mainpic">
<img src="../images/3.jpg" />
</div>
<div >
<span>导演</span>: 彼特·道格特 / 鲍勃·彼德森<br/>
<span>编剧</span>: 鲍勃·彼德森 / 彼特·道格特 / 汤姆·麦卡锡<br/>
<span><span>主演</span>: 爱德华·阿斯纳 / 克里斯托弗·普卢默 / 乔丹·长井 / 鲍勃·彼德森 / 戴尔里·林多 / 杰罗姆·兰福特</span><br/>
<span>类型:</span> 剧情 / 喜剧 / 动画 / 冒险<br/>
<span>制片国家/地区:</span> 美国<br/>
<span>语言:</span> 英语<br/>
<span>片长:</span> 96分钟<br/>
</div>
<div>
<span >飞屋环游记的剧情简介:</span>
<div>
  小男孩卡尔(Carl Fredricksen)怀揣着对于冒险的热爱偶遇假小子艾丽(Ellie),而艾丽把整个屋子当成一艘大飞船游戏居然使他对这个女孩子有些着迷,相同的爱好最终使两个人成为了一生的爱侣。
<br />
  他们有一个梦想,那就是有朝一日要去南美洲的“仙境瀑布”探险,但直到艾丽去世,这个梦想也未能实现。终于有一天,曾经专卖气球的老人卡尔居然用五颜六色的气球拽着他的房子飞上了天空,他决定要去实现他们未曾实现的梦想。令卡尔始料不及的是,门廊居然搭上了一个自称是“荒野开拓者”的小男孩小罗(Russell),小罗的喋喋不休让卡尔对这个小胖墩格外讨厌。
<br />
  一老一少在飞行中经过了千难万险终于看到了传说中的“仙境瀑布”,在相处过程中卡尔发现小罗其实是个惹人怜爱的孩子。在步行穿越一座森林时,他们遇到了不会飞的大鸟凯文(Kevin)和一只会说话的狗狗逗逗(Dug),让老人惊讶的是他们还遇到了他少年的崇拜偶像——探险家查尔斯·蒙兹(Charles Muntz),而且他发现蒙兹居然是一个为达目的不择手段的坏人。这时,老人离自己的梦想之地只有一步之遥……
<br />
  本片荣获第82届奥斯卡最佳动画长片、最佳配乐2项大奖。
</div>
</div>
</div>
</div>


<div id="bottom">
<span class="copyright">电影资源网</span>

</body>
</html>

二级页面截图:


导航行的“电影”部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
<!DOCTYPE html >
<html >
<head>
<meta charset=utf-8" />
<title>飞屋环游记的介绍</title>
<style>
ul {
list-style-type: none;
margin: 0;
padding: 0;
overflow: hidden;
background-color: white;<!--导引行字背景-->
}

li {
float: left;
}

li a {
display: gray;
color: blue;<!--字体颜色-->
text-align: center;
padding: 14px 16px;
text-decoration: none;
}

li a:hover {
background-color: red;<!--选中后背景-->
}

<!--底部的格式-->
#bottom{
margin:30px auto 0px auto;
width:1200px;
height:40px;
line-height:40px;
border-top:1px solid #CCCCCC;
}

#bottom .copyright{
float:left;
color:#999999;
font-family:"微软雅黑";
font-size:14px;}

</style>

</head>

<body>
<ul>
<br></br>
<li><a href="javascript:;">电影购票</a></li>
<li><a href="javascript:;">电影</a></li>
<li><a href="javascript:;">电视剧</a></li>
<li><a href="javascript:;">少儿</a></li>
<li><a href="javascript:;">其他</a></li>
<li><a href="javascript:;">圈子</a></li>
<li><a href="javascript:;">最热电影</a></li>
</ul>


<!--电影部分-->

<div id="left">
<div class="is-on">
<div class="hd">
<h2>电影大全</h2>
<div class="right">
<a class="leftBtn" href="javascript:;"></a>
<a class="rightBtn" href="javascript:;"></a>
</div>
</div>
<div class="bd">
<div class="container">
<ul>

<li>
<a href="detail/mnyys.html"><img src="images/1.jpg" alt="" />
</a>
<p><a href="detail/mnyys.html">美女与野兽</a>

<span class="score">7.2分</span></p>


</li>

<li>
<a href="detail/thwj.html"><img src="images/2.jpg" alt="" />
</a>
<p><a href="detail/thwj.html">头号玩家</a>

<span class="score">8.7分</span></p>


</li>

<li>
<a href="detail/fwhyj.html"><img src="images/3.jpg" alt="" />
</a>
<p><a href="detail/fwhyj.html">飞屋环游记</a>

<span class="score">8.9分</span></p>


</li>

<li>
<a href="detail/mtyj.html">
<img src="images/4.jpg" alt="" />
</a>
<p><a href="detail/mtyj.html">摩天营救</a>

<span class="score">8.6分</span></p>

</li>

<li>
<a href="detail/yhhwd.html"><img src="images/5.jpg" alt="" />
</a>
<p><a href="detail/yhhwd.html">银河护卫队</a>

<span class="score">8.0分</span></p>

</li>
</ul>
</div>
</div>

<div id="bottom">
<span class="copyright">电影资源网</span>

</body>
</html>

电影部分截图:


回溯算法

回溯法:
回溯在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就 “回溯” 返回,尝试别的路径。按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,
回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。

例子:
八皇后问题
在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法?
思路:
通过分析题目可以得到,就是每一行就必须有一个皇后。
①第一种想法是假设8*8的棋盘是一个矩阵形式,那么假设皇后i和皇后j的位置为(i,Xi)和(j,Xj),只要保证两个坐标的点斜率不是1和-1就行。
②采用回溯法:
假设现在有四个皇后需要放置:
(1)假设第一个皇后放在第一行第一列的位置,那么第二行的皇后就只能放在第二行第三列/第四列位置。
(2)现在让第二个皇后放在第二行第三列的位置,那么第三行的皇后就没有位置可以放了,没有满足题意的位置了。

因此我们需要返回考虑第二个皇后的安置问题:
(2)现在让第二个皇后放在第二行第四列的位置,那么第三行的皇后就可以放在第三行第二列位置。
(3)第三行皇后放置后,第四行皇后又没位置了。

因此需要不断地去尝试,选择路径去放置

具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class BaHuangHou{	
public static void main(String[] args) {
int a[]=new int[4];
int number=4,count=0;
operate(0);
System.out.println(count);
}

public static boolean panduan(int n) {
for(int i=0;i<n;i++)
if((a[i]==a[n])||(Math.abs(n-i)==Math.abs(a[i]-a[n]))) //判断下一个皇后是否和上一个皇后在同一行或者是对角线
return false;

return true;
}

public static void operate(int n) { //放置一个皇后
if(n==number)
{
count++;
}
else if(n<number)
{
for(int i=0;i<number;i++)
{
a[n]=i;
if(panduan(n)) //判断是否可以放置
operate(n+1);
}
}
}


}

代码结果如下:

贪心算法

贪心算法:
  又称贪婪算法。重复地使用一个贪婪规则(确定一个符合的准则)去挑选解的一部分,从局部最优解逐步达到全局最优
  贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
例如:
背包问题:
有三个参赛者:A,B,C;
每个比赛者一个包(包的载重量为20kg)
给定N个物品,每个物品有一定的质量和价值
规则:
  1.物品可以切一部分放入
  2.包装的物品的总质量不超过包的载重量
  3.包里装的物品的价值之和最高者获胜
假设:物品n=3,包的载重量c=20
物品1:V=25,M=18
物品2:V=24,M=15
物品3:V=15,M=10

思路:
A考虑优先放入价值高的物品:
  max=25+24(2/15)=28.2;
B考虑优先放入重量低的物品:
  max=15+24
(10/15)=31;
C考虑优先放入性价比高的物品:
  max=24+15(5/10)=31.5;
*
所以说我们对于此题选择C考虑的方法为解决题目的贪心规则。**

一、两地调度:
公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0],飞往 B 市的费用为 costs[i][1]。
返回将每个人都飞到某座城市的最低费用,要求每个城市都有 N 人抵达。
示例:
  输入:[[10,20],[30,200],[400,50],[30,20]]
输出:110
解释:
  第一个人去 A 市,费用为 10。
  第二个人去 A 市,费用为 30。
  第三个人去 B 市,费用为 50。
  第四个人去 B 市,费用为 20。

思路:
  我们可以考虑先让公司指派2N个人全都去A城,然后计算从A和B出发的金钱差额放入数组里面,排序之后将数组前一半的人替换到B去,这样可以保证有N个人去A,其他人去B。然后也可以保证最低费用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Scanner;
import java.util.Arrays;
public class DiYiGe{
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int m=input.nextInt();
int[][] a=new int[n][m];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
a[i][j]=input.nextInt(); //双层循环读取分别去A和B的花费
}
}
System.out.println(min(a));
}

public static int min(int[][] a) {
int m=a.length; //原数组的长度
int b[] = new int[m]; //对应存放每个人去A和B的消耗差
int sum = 0;
for(int i=0;i<m;i++){
b[i] = a[i][1]-a[i][0]; //计算从A到B城的消耗差
sum +=a[i][0]; //加上所有人到A城的费用
}
Arrays.sort(b); //将差距
for(int i=0;i<m/2;i++)
sum+=b[i]; //减去应到B城的人员的额外消耗
return sum;
}
}

代码结果如下:


二、柠檬水找零:
  在柠檬水摊上,每一杯柠檬水的售价为 5 美元。
  顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。
每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。
  注意,一开始你手头没有任何零钱。

示例:
  输入:[5,5,5,10,20]
  输出:true
解释:
  前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。
  第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。
  第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。
  由于所有客户都得到了正确的找零,所以我们输出 true。

思路:先收前面的人钱,然后保证手里有零钱,如果需要找20的话,先考虑找10元大的钱,保证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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.Scanner;
public class NingMeng {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<n;i++)
{
a[i]=input.nextInt();
}
System.out.println(Change(a));
}

public static boolean Change(int[] a) {
int money[] = new int[3]; // 利用下标存放5/10/20元的数量
money[0]++; //存放5元的个数
for (int i=1;i<a.length;i++) {
switch (a[i]) { //依次找零
case 5:
money[0]++; //如果是5元直接+1
break;
case 10:
money[1]++; //十元的话+1
money[0]--; //找零5元
if (money[0] < 0) {
return false; //不能成功找零
}
break;
case 20:
money[2]++; //如果是20元直接+1
if (money[1]>0) { //如果有10元找一张 10元-1 5元-1
money[1]--;
money[0]--;
}
else {
money[0] -= 3; //如果找5元 5元-3
}

if (money[0] < 0) {
return false;
}
break;
}
}
return true;
}
}

代码结果如下:


三、跳台阶
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
例如:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
说明:假设你总是可以到达数组的最后一个位置。
思路:
假如a={2,3,1,1,4,2,1}那么最符合题意的就是2跳到3的位置然后跳到4然后跳到终点。
现在当处于第一个位置2的时候考虑是跳到3还是1,显然跳到3更好一点,那么跳到3之后考虑跳到1还是1还是4,因此选择4的位置,最后选择跳到终点。
->我们考虑下一个要跳跃的点就必须是保证上一次和这一次的跳跃点距离最远,这样可以保证输出少。

贪心算法代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  public int jump(int[] a) {
int sum = 0;
int zy = 0; // 能跳到的最远距离
int max = 0; // 下一步可以跳到的最远距离
for(int i = 0; i < a.length - 1; i++)
{
max = Math.max(max, i + a[i]);
// 更新当前点
if(i == zy)
{
zy = max;
sum++;
}
}
return sum;
}

以爬楼梯为例

一、爬楼梯
题目:
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
思路:
  此题目和铺地板等题目一样,都有两种方式解决。
  ①递归:递归思路为不断递归方法,求F(i)时候就要求F(i-1)和F(i-2);
  ②动态规划:规划方程F(i)=F(i-1)+f(i-2);(i从2开始)
动态规划具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Scanner;
public class FeiBoNaQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt(); //定义数组的长度
int[] a=new int[n];
a[0]=1; //要爬一层台阶,有一种方法
a[1]=2; //要爬两层台阶,有两种方法
System.out.println(climbStairs(n,a)); //传递a数组和要爬的层数
}
public static int climbStairs(int n,int[] a) {
if(n==1)
return 1; //如果爬一层楼就是1个方法
for(int i=2;i<n;i++)
{
a[i]=a[i-1]+a[i-2]; //相当于斐波拉契数列思想

}
return a[n-1]; //返回的一定是数组长度-1的值
}
}

代码结果如下:


二、买卖股票的最佳时机
题目:
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
例如:
  输入:7,1,5,3,6,4
  输出: 5
  解释:在第二天的时候买入,在第五天卖出,最大利润=6-1=5。
注意利润不能是7-1=6,因为卖出价格需要大于买入价格。
思路:
①拿到题目第一种思路就是暴力求解法,利用两重循环两个数进行比较,然后根据条件限制选出两个数值之间差距最大的两个数,即为买卖股票的最佳时机。
具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Scanner;
public class FeiBoNaQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<a.length;i++)
{
a[i]=input.nextInt();
}
System.out.println(maxProfit(a));
}
public static int maxProfit(int[] a) {
int max=0;
for(int i=0;i<a.length;i++)
{
for(int j=i+1;j<a.length;j++)
{
if(j>=i) //后面的那个价格要比前面的高(保证不亏钱)
{
max=Math.max(max,(a[j]-a[i])); // 选出两者之间差距最大的即为最大利润
}
}
}
return max;
}
}

代码结果如下:

②第二种思路就是动态规划,这还是我参考别人的想法想到了。
当前的最大利润=max{前一个值的最大利润max,当前值-前面的最小值}。
max=Math.max(max,(a[i]-min)); (min初始值一定要为a[0],不然默认为0的话,最大利润永远为0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;
public class TouQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<a.length;i++)
{
a[i]=input.nextInt();
}
System.out.println(rob(a));
}


public static int rob(int[] a) {
int max=0,min=a[0],i=0; //先让最小值为第一个值
for( i=0;i<a.length;i++)
{
min=Math.min(min,a[i]); //每次判断确定最小值
max=Math.max(max,(a[i]-min)); //判断当前的最大利润是前一个的利润还是当前减去前面的最小值哪个大
}
return max;
}
}

代码结果如下:


三、买卖股票的最佳时机II
题目:
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 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
import java.util.Scanner;
public class TouQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<a.length;i++)
{
a[i]=input.nextInt();
}
System.out.println(rob(a));
}

public static int rob(int[] a) {
int i=0,sum=0;
for(i=1;i<a.length;i++)
{
if(a[i-1]<a[i]) //上升状态
{
sum+=a[i]-a[i-1]; //将所有上升状态的值都加起来
}
}
return sum;
}
}

代码结果如下:


四、打家劫舍
题目:
  你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
  给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
示例:
  输入:2,7,9,3,1
  输出:12
解释:先偷第一家的金额为2,然后偷第三家的金额为9,接着偷第五家的金额为1.
思路:
  此题为经典的动态规划问题,我一开始理解的就是要么奇数最大要么偶数最大就解决了,然后我就循环判断奇数总和与偶数总和的大小,但是发现还是有很大问题。
以三个为例:
  第一步:我们只偷第一家的,记作max=a[0];
  第二步:因为不能偷相邻的房间,我们要判断是第一家的还是第二家的金额大,记作max=Math.max(a[0],a[1]);
  第三步:考虑是第一家的金额+第三家的金额和第二家的金额那个大,记作max=Math.max(a[0]+a[2],a[1]);
  由此,我们可以用一个a数组存放输入的每家金额值,b数组去存放每一步取得的最大的金额:
  b[i]=Math.max((b[i-2]+a[i]),b[i-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
import java.util.Scanner;
public class TouQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<a.length;i++)
{
a[i]=input.nextInt();
}
System.out.println(rob(a));
}

public static int rob(int[] a) {
int[] b=new int[a.length];
b[0]=a[0]; //只能偷第一家
b[1]=Math.max(a[0],a[1]); //确定偷第二家的时候是哪一家比较有钱,确定从1还是2家开始
for(int i=2;i<a.length;i++)
{
b[i]=Math.max(b[i-2]+a[i],b[i-1]); //比较前一家的金额和之前一家加上现在一家的金额哪个大
}
return b[a.length-1]; //注意输出长度-1的值
}
}

代码结果如下:


动态规划

动态规划
  简单的说就是,大问题化解为小问题,然后小问题解决后组装成大问题,可以压缩解决大问题的时间。

动态规划和递归的区别:
  我自己学的时候,我对动态规划的感觉就是这明明就是递归嘛,但是当我解决了几道题之后发现还是有一定区别。
  两种想法都是将大问题分解为小问题,使用类似于分而治之的思想去解决问题。
  以斐波拉契数列为例,递归要算F(n)=F(n-1)+F(n-2);(n>2)就需要算n-1和n-2的解,依次解决的话就会重复计算中间的值,会导致计算量变大;而动态规划的话,会减少计算重复值,更优化。


举例:

一、斐波拉契数列
  题目:兔子繁殖问题:
  这是一个有趣的古典数学问题,著名意大利数学家Fibonacci曾提出一个问题:有一对小兔子,从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。按此规律,假设没有兔子死亡,第一个月有一对刚出生的小兔子,问第n个月有多少对兔子?
  这就是著名的斐波那契数列(Fibonacci sequence),该数列,又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……
  特点:这个数列从第3项开始,每一项都等于前两项之和。
  思路:
  ①递归:从第二项开始 F(n)=F(n-1)+F(n-2);
  ②动态规划:定义left,right以及sum三个变量,通过不断地更新和移位算出接下来的值,可以避免递归的重复计算。

  具体实现:
  ①递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.Scanner;
public class FeiBoNaQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
a[1]=a[0]=1;
System.out.println(FB(n));
}
public static int FB(int n) {
if(n<=1) //输入为0/1输出结果为0/1
return n;
else
return FB(n-1)+FB(n-2); //不断递归公式
}
}

  代码结果:
  !

  ②动态规划:

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.Scanner;
public class FeiBoNaQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
System.out.println(FB(n-1));
}
public static int FB(int n) {
if(n<=1)
return n;
int left=1,right=1;
int sum=0;
for(int i=2;i<=n;i++) //从第三个开始(0开始)为前两个之和
{
sum=left+right; //第三个为第一个数和第二个数之和
right=left; //第一个数指向第二个数位置
left=sum; //第三个数字指向第一个数位置
}
return sum;
}
}

  代码结果:
  !


二、跳台阶
  题目:
  一只青蛙一次可以跳上一级台阶,也可以跳上两级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
  思路:
  首先考虑需要跳两级台阶,那么第一种情况就是一次跳两级,第二种是一次跳一级。
  那么如果需要跳n级台阶,把跳法记作函数f(n):当n>2时,一是第一次跳一级,那么剩下的n-1级就需要f(n-1)。
二是第一次跳两级,那么剩下的n-2级就需要f(n-2)。所以整理可知,这实际上也是一个斐波拉数列!

  具体实现:

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.Scanner;
public class TiaoTaiJie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
System.out.println(TaiJie(n-1));
}
public static int TaiJie(int n) {
if(n<=1)
return n;
int left=1,right=1;
int sum=0;
for(int i=2;i<=n;i++) //从第三个开始(0开始)为前两个之和
{
sum=left+right; //第三个为第一个数和第二个数之和
right=left; //第一个数指向第二个数位置
left=sum; //第三个数字指向第一个数位置
}
return sum;
}
}

  代码结果:
  !


三、变态跳台阶
  题目:
  在上题目的基础上,这次一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶….也可以跳上n级台阶。求青蛙上一个n级台阶总共有多少跳法。
  思路:
  我们可以依旧从最简单的二级开始考虑:
  如果我们需要跳上2级台阶,那么第一种方法是跳二级台阶,第二种是一次一级。
  如果是n级台阶,那么可以从n-1级跳一级上去,也可以从n-2级跳两级上去:
  因此 f(n)=f(n-1)+f(n-2)+…+f(1); (1)
  如果是n-1级台阶,那么可以从n-2级跳一级上去,也可以从n-3级跳两级上去:
  因此 f(n-1)=f(n-2)+f(n-3)+…+f(1); (2)
  则(1)和(2)式联立,我们可以得出f(n)=2*f(n-1);

  具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Scanner;
public class BianTaiTiaoTaiJie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
System.out.println(BianTai(n));
}
public static int BianTai(int n) {
if(n==1)
return 1; //需要跳一级只有一种方法
if(n==2)
return 2; //需要跳二级有两种方法
else
return 2*BianTai(n-1);/return (int)Math.pow(2,n-1); //需要跳n级有n-1种方法(不断求解)
}
}

  代码结果:
  !


还有一些可以被动态规划解决的问题

  • 资源分配问题(求最优解/利益最大)
  • 铺地板(和跳台阶一样)
  • 矩阵覆盖(和跳台阶一样)
  • 借还滑板鞋(考虑最优解)
  • 最优二叉树搜索树

总结:

  • 碰到上面的例题时,需要考虑最优解使用递归/动态规划即可。但是递归不太推荐,性能没有动态规划好。
  • 需要从最简单然后推导出规律和推导公式。
  • 尽可能避免无所谓的复杂计算,得到加快算法求解的时间。

IntelliJ IDEA

一、IntelliJ IDEA 2019下载:
  1.访问IntelliJ IDEA官网,点击Download转到下载页面:
  !
  2.IntelliJ IDEA有两个版本:商业付费旗舰版(Ultimate)和开源免费社区版(Community)。旗舰版和社区版功能对比也在该页面下面,个人推荐下载商业付费旗舰版(Ultimate),毕竟功能丰富且强大。当前版本为IntelliJ IDEA 2019.2.3:
  !
  3.以IntelliJ IDEA 2019.1 Ultimate为例,双击安装包安装:
  !
  4.开始安装,点击Next:
  !
  5.选择安装位置,点击Next:
  !
  6.接下来有如下三个安装选项:
  Create Desktop Shortcut:创建桌面快捷方式图标,建议勾选64-bit launcher;
  Update context menu:是否将从文件夹打开项目添加至鼠标右键,根据需要勾选;
  Create Associations:关联文件格式,不推荐勾选,一般都是使用如Sublime Text、EditPlus等轻量级文本编辑器打开;
  Download and install JRE x86 by JetBrains:下载并安装JetBrains的JRE。若曾在安装JDK的时候也安装了JRE,则无需勾选此项;
  Update PATH variable (restart needed):是否将IDEA启动目录添加到环境变量中,即可以从命令行中启动IDEA,根据需要勾选:
  !
  7.创建开始菜单文件夹:
  !
  8.安装成功:选择第二个(稍后手动重新自动电脑)
  !
  9.首次安装选择Do not import settings,即不导入任何设置;若是升级可以选择第一项Config or installation folder,即指定为之前版本的配置文件夹或安装根目录:
  !
  10.是否同意用户协议,勾选I confirm that I have read and accept the terms of this User Agreement,点击Continue:
  !
  11.是否发送匿名使用统计数据,建议点击Don’t Send:
  !
  12.设置IntelliJ IDEA的UI主题,个人喜欢Darcula主题(以前的版本Darcula都放在IntelliJ后面,现在可能更多的人喜欢Darcula),后期也可以在设置里自行修改,点击Next: Default plugins:
  !
  13.IntelliJ IDEA支持功能插件化。以IntelliJ Platform为基础,添加相应功能的插件后就有了CLion、WebStorm、PyCharm、PHPStorm、Android Studio、GoLand、RubyMine等独立的IDE。对IntelliJ IDEA的插件管理,可以根据开发需求对某些插件开启或关闭。适当地关闭不需要的插件有助于减少占用空间和加快响应速度。初次使用IntelliJ IDEA建议直接点击Next: Featured plugins,上手以后可以在设置的插件管理中进行对插件增删:
  !
  14.IntelliJ IDEA推荐的插件列表,个人推荐安装IDE Features Trainer,可以在空闲的时候练习使用IDE的一些功能和快捷键,其余的根据自己的需要安装,一般选第二个!,点击Start using IntelliJ IDEA:
  !
二、商业版激活:
  1.新建一个记事本,将以下代码复制之后将文件改为reg格式:

1
2
3
4
5
6
7
8
9
10
Windows Registry Editor Version 5.00 [HKEY_CLASSES_ROOT\*\shell\runas] 
@="获取超级管理员权限"
"NoWorkingDirectory"="" [HKEY_CLASSES_ROOT\*\shell\runas\command]
@="cmd.exe /c takeown /f \"%1\" && icacls \"%1\" /grant administrators:F" "IsolatedCommand"="cmd.exe /c takeown /f \"%1\" && icacls \"%1\" /grant administrators:F"
[HKEY_CLASSES_ROOT\exefile\shell\runas2]
@="获取超级管理员权限"
"NoWorkingDirectory"="" [HKEY_CLASSES_ROOT\exefile\shell\runas2\command] @="cmd.exe /c takeown /f \"%1\" && icacls \"%1\" /grant administrators:F" "IsolatedCommand"="cmd.exe /c takeown /f \"%1\" && icacls \"%1\" /grant administrators:F"
[HKEY_CLASSES_ROOT\Directory\shell\runas]
@="获取超级管理员权限"
"NoWorkingDirectory"=""[HKEY_CLASSES_ROOT\Directory\shell\runas\command] @="cmd.exe /c takeown /f \"%1\" /r /d y && icacls \"%1\" /grant administrators:F /t" "IsolatedCommand"="cmd.exe /c takeown /f \"%1\" /r /d y && icacls \"%1\" /grant administrators:F /t"

  2.然后把该文本文档命名为 “Win10获取超级管理员权限.reg” ,然后双击导入注册表即可,这样就获得了Win10超级管理员权限。

  3.需要将0.0.0.0 https://account.jetbrains.com:443添加到hosts文件中(C:\Windows\System32\drivers\etc\hosts)中,屏蔽JetBrains校验注册码。

  4.打开软件,依次选择Activate、Activation code,将注册码粘贴到下面的框里,点击OK:
例如(百度激活码):

1
2
MNQ043JMTU-eyJsaWNlbnNlSWQiOiJNTlEwNDNKTVRVIiwibGljZW5zZWVOYW1lIjoiR1VPIEJJTiIsImFzc2lnbmVlTmFtZSI6IiIsImFzc2lnbmVlRW1haWwiOiIiLCJsaWNlbnNlUmVzdHJpY3Rpb24iOiIiLCJjaGVja0NvbmN1cnJlbnRVc2UiOmZhbHNlLCJwcm9kdWN0cyI6W3siY29kZSI6IklJIiwiZmFsbGJhY2tEYXRlIjoiMjAxOS0wNC0wNSIsInBhaWRVcFRvIjoiMjAyMC0wNC0wNCJ9XSwiaGFzaCI6IjEyNjIxNDIwLzBwIiwiZ3JhY2VQZXJpb2REYXlzIjo3LCJhdXRvUHJvbG9uZ2F0ZWQiOnRydWUsImlzQXV0b1Byb2xvbmdhdGVkIjp0cnVlfQ==-Zmbxcn7NPlqBNqAURX0uiLzybnruyx6PG+6KYZrpzm/IJJs5nnIogGgdfIJoifO6fbaaJYc5pjds7CHdrt/neIpvF2o/HvIjMEF4/AhNV7HUGsAa9zpMszc6YBIkMmVFh4Y7GPKOStA14/Ld83AC7kGnwL1Fq7eAXKJFljc00GMejPpfE0zDqTN634bC+0ojfklhWXaLqhUt230SiE8onnd3quvEaH5NsW7sIQm2spyONZI+iHvHFtl4EvG7tlRlD1StsfhrbgNNxz61FOEEQ+GtZIzMx+T4sbpfoRyms7lbWQecrbAtE0c2sR98esm4PcDUhrFVBxGorPC1ppOLSQ==-
MIIElTCCAn2gAwIBAgIBCTANBgkqhkiG9w0BAQsFADAYMRYwFAYDVQQDDA1KZXRQcm9maWxlIENBMB4XDTE4MTEwMTEyMjk0NloXDTIwMTEwMjEyMjk0NlowaDELMAkGA1UEBhMCQ1oxDjAMBgNVBAgMBU51c2xlMQ8wDQYDVQQHDAZQcmFndWUxGTAXBgNVBAoMEEpldEJyYWlucyBzLnIuby4xHTAbBgNVBAMMFHByb2QzeS1mcm9tLTIwMTgxMTAxMIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAxcQkq+zdxlR2mmRYBPzGbUNdMN6OaXiXzxIWtMEkrJMO/5oUfQJbLLuMSMK0QHFmaI37WShyxZcfRCidwXjot4zmNBKnlyHodDij/78TmVqFl8nOeD5+07B8VEaIu7c3E1N+e1doC6wht4I4+IEmtsPAdoaj5WCQVQbrI8KeT8M9VcBIWX7fD0fhexfg3ZRt0xqwMcXGNp3DdJHiO0rCdU+Itv7EmtnSVq9jBG1usMSFvMowR25mju2JcPFp1+I4ZI+FqgR8gyG8oiNDyNEoAbsR3lOpI7grUYSvkB/xVy/VoklPCK2h0f0GJxFjnye8NT1PAywoyl7RmiAVRE/EKwIDAQABo4GZMIGWMAkGA1UdEwQCMAAwHQYDVR0OBBYEFGEpG9oZGcfLMGNBkY7SgHiMGgTcMEgGA1UdIwRBMD+AFKOetkhnQhI2Qb1t4Lm0oFKLl/GzoRykGjAYMRYwFAYDVQQDDA1KZXRQcm9maWxlIENBggkA0myxg7KDeeEwEwYDVR0lBAwwCgYIKwYBBQUHAwEwCwYDVR0PBAQDAgWgMA0GCSqGSIb3DQEBCwUAA4ICAQAF8uc+YJOHHwOFcPzmbjcxNDuGoOUIP+2h1R75Lecswb7ru2LWWSUMtXVKQzChLNPn/72W0k+oI056tgiwuG7M49LXp4zQVlQnFmWU1wwGvVhq5R63Rpjx1zjGUhcXgayu7+9zMUW596Lbomsg8qVve6euqsrFicYkIIuUu4zYPndJwfe0YkS5nY72SHnNdbPhEnN8wcB2Kz+OIG0lih3yz5EqFhld03bGp222ZQCIghCTVL6QBNadGsiN/lWLl4JdR3lJkZzlpFdiHijoVRdWeSWqM4y0t23c92HXKrgppoSV18XMxrWVdoSM3nuMHwxGhFyde05OdDtLpCv+jlWf5REAHHA201pAU6bJSZINyHDUTB+Beo28rRXSwSh3OUIvYwKNVeoBY+KwOJ7WnuTCUq1meE6GkKc4D/cXmgpOyW/1SmBz3XjVIi/zprZ0zf3qH5mkphtg6ksjKgKjmx1cXfZAAX6wcDBNaCL+Ortep1Dh8xDUbqbBVNBL4jbiL3i3xsfNiyJgaZ5sX7i8tmStEpLbPwvHcByuf59qJhV/bZOl8KqJBETCDJcY6O2aqhTUy+9x93ThKs1GKrRPePrWPluud7ttlgtRveit/pcBrnQcXOl1rHq7ByB8CFAxNotRUYL9IF5n3wJOgkPojMy6jetQA5Ogc8Sm7RG6vg1yow==

三、创作开始:
  1.Create New Project,即创建新项目
  2.需要先配置项目JDK,点击New:选择本地所安装的JDK的根目录(系统环境变量JAVA_HOME)(一般就是你安装的jdk显示的位置)
  3.选择Java
  4.询问是否从模板创建项目,不勾选,点击Next
  5.项目创建成功后,自动生成了.idea文件夹、src文件夹和HelloWorld.iml。.idea文件夹和HelloWorld.iml是IntelliJ IDEA项目配置信息相关的,暂不予考虑。在src文件夹下编写代码。右键src文件夹,选择New,通过二级菜单可以创建Java Class、Package和XML文件等
  6.运行HelloWord.java,可以通过右键或顶部工具栏运行或调试,Run为运行,Debug为调试。运行结果在下面的Console控制台显示

接雨水

题目

 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。


 
示例:
 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 输出: 6

解题思路

在乘更多的水的题目基础下,此题需解决每个格子怎么确定接水量。
通过分析,每个格子左边和右边的最大值中哪个小一点就会影响接水量(受最小值影响),因此我们确定两个指针i和j用来移动得出每个格子的接水量,而定义leftmax和rightmax为当前格子左边和右边的最大值。
  分为两个情况:
(1)如果左边的最大值<右边的最大值,那么就要确定左边i指针指向的格子接水量(leftmax-height[i])
(2)如果左边的最大值>=右边的最大值,那么就要确定右边j指针指向的格子接水量(rightmax-height[j])

方法:双指针法

代码(根据力扣官网提交作品的格式):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int trap(int[] height) {
int max=0,leftmax=0,rightmax=0;
int i=0;
int j=height.length-1;
while(i<j)
{
leftmax=Math.max(leftmax, height[i]); //更新为左边最大值
rightmax=Math.max(rightmax, height[j]); //更新为右边最大值
if(leftmax<rightmax) //如果左边最大值小于右边最大值,左边就为限制因素
{
max+=leftmax-height[i]; //接水量=左边最大值-当前格子值
i++; //指针后移,计算下一个格子
}
else //如果左边最大值大于等于右边最大值,右边就为限制因素
{
max+=rightmax-height[j]; //接水量=右边最大值-当前格子值
j--; //指针前移,计算前一个格子
}

}
return max;
}
}

完整代码

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.Scanner;
public class Solution{
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int w=0;w<a.length;w++)
{
a[w]=input.nextInt(); //输入n个柱状
}
System.out.println(trap(a)); //输出接水量
}
public static int trap(int[] height) {
int max=0,leftmax=0,rightmax=0;
int i=0; //从首部开始
int j=height.length-1; //从尾部开始
while(i<j)
{
leftmax=Math.max(leftmax, height[i]); //更新为左边最大值
rightmax=Math.max(rightmax, height[j]); //更新为右边最大值
if(leftmax<rightmax) //如果左边最大值小于右边最大值,左边就为限制因素
{
max+=leftmax-height[i]; //接水量=左边最大值-当前格子值
i++; //指针后移,计算下一个格子
}
else //如果左边最大值大于等于右边最大值,右边就为限制因素
{
max+=rightmax-height[j]; //接水量=右边最大值-当前格子值
j--; //指针前移,计算前一个格子
}

}
return max;
}

}

代码截图


乘更多的水

题目:
 给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水
 说明:你不能倾斜容器,且 n 的值至少为 2。
 示例:
 输入: [1,8,6,2,5,4,8,3,7]
 输出: 49

解题思路
此题意味着垂直的两条线段将会与坐标轴构成一个矩形区域,较短线段的长度将会作为矩形区域的宽度,两线间距将会作为矩形区域的长度,而我们必须最大化该矩形区域的面积,所以考虑面积最大的情况。
方法一:暴力法
代码(根据力扣官网提交作品的格式):

1
2
3
4
5
6
7
8
9
public class Solution {
public int mArea(int[] height) {
int max=0; //存放最大值
for (int i=0;i<height.length;i++)
for (int j=i+1;j<height.length;j++)
max = Math.max(max, Math.min(height[i], height[j])*(j-i)); //最大面积=较短边×下标的差
return max;
}
}

 复杂度分析:
 时间复杂度:O(n²)
 空间复杂度:O(1)


方法二:双指针法
思路:在方法一暴力求解的前提下,我们考虑两线段之间形成的区域总是会受到其中较短那条长度的限制。此外,两线段距离越远,得到的面积就越大。
 我们在由线段长度构成的数组中使用两个指针,一个放在开始,一个置于末尾。 此外,我们会使用变量 maxarea 来持续存储到目前为止所获得的最大面积。 在每一步中,我们会找出指针所指向的两条线段形成的区域,更新 maxarea,并将指向较短线段的指针向较长线段那端移动一步。
 为了使面积最大化,我们需要考虑更长的两条线段之间的区域。如果我们试图将指向较长线段的指针向内侧移动,矩形区域的面积将受限于较短的线段而不会获得任何增加。但是,在同样的条件下,移动指向较短线段的指针尽管造成了矩形宽度的减小,但却可能会有助于面积的增大。因为移动较短线段的指针会得到一条相对较长的线段,这可以克服由宽度减小而引起的面积减小。
代码(根据力扣官网提交作品的格式):

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int maxArea(int[] height) {
int maxarea = 0,i = 0, j = height.length - 1; //指针i和j分别指向首部和尾部
while (i < j) { //i小于j才能循环
maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i)); //最大面积=较短边×下标的差
if (height[i] < height[j]) //如果左边的值小,就将指针i右移
i++;
else //如果右边的值小或者两者相等,就将指针j左移
j--;
}
return maxarea;
}
}

 复杂度分析:
 时间复杂度:O(n)
 空间复杂度:O(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.Scanner;
public class Ji {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt(); //输入n个柱状
int[] a=new int[n]; //动态生成n大小的整型数组
for(int w=0;w<a.length;w++)
{
a[w]=input.nextInt(); //循环输入每个柱状的值
}
System.out.println(maxArea(a)); //输出最终值
}

public static int maxArea(int[] height) {
int maxarea=0,i=0,j=height.length-1; //指针i和j分别指向首部和尾部
while(i<j)
{
maxarea=Math.max(maxarea,Math.min(height[i], height[j])*(j-i)); //最大面积=较短边×下标的差
if(height[i]<height[j])
i++; //如果左边的值小,就将指针i右移
else
j--; //如果右边的值小或者两者相等,就将指针j左移
}
return maxarea;
}



}

,