Skip to content

Commit 3cc193c

Browse files
kunkunthreekunkunthree
committed
增加新的leetcode编程题，各公司笔试题
1 parent 1050a51 commit 3cc193c

68 files changed

Lines changed: 4091 additions & 14 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎ChapterAlgorithm/src/algorithm/KMP_Knuth_Morris_Pratt.java‎

Lines changed: 83 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,7 @@
11
package algorithm;
2+
3+
import java.util.Arrays;
4+
25
/*
36
* KMP算法：用于字符串匹配，在长度为m的字符串里匹配长度为n的字符串，O(m+n)time，O(n)space
47
* http://blog.csdn.net/yutianzuijin/article/details/11954939/
@@ -54,7 +57,13 @@ public class KMP_Knuth_Morris_Pratt {
5457
public static void main(String[] args) {
5558
String original = "12312312345234";
5659
String find = "23";
60+
getNext("ABCAACBBCBADAABCACBD");
61+
getNext2("ABCAACBBCBADAABCACBD");
62+
getNext("ababaabab");
63+
getNext3("ababaabab");
5764
search(original, find, getNext(original));
65+
// search2(original, find, getNext2(original));
66+
search3(original, find, getNext3(original));
5867
}
5968
public static int[] getNext(String b)
6069
{
@@ -70,7 +79,7 @@ public static int[] getNext(String b)
7079
if(b.charAt(i)==b.charAt(j))j++;
7180
next[i+1]=j;
7281
}
73-
82+
System.out.println("next : " + Arrays.toString(next));
7483
return next;
7584
}
7685
public static void search(String original, String find, int next[]) {
@@ -87,4 +96,77 @@ public static void search(String original, String find, int next[]) {
8796
}
8897
}
8998
}
99+
100+
//next表示长度为i的字符串前缀和后缀的最长公共部分，从0开始
101+
public static int[] getNext2(String b)
102+
{
103+
int len=b.length();
104+
int j= -1;
105+
106+
int next[]=new int[len];//next表示长度为i的字符串前缀和后缀的最长公共部分，从0开始
107+
next[0]=-1;
108+
109+
for(int i=0;i<len-1;i++)//i表示字符串的下标，从0开始
110+
{//j在每次循环开始都表示next[i]的值，同时也表示需要比较的下一个位置
111+
while(j>-1&&b.charAt(i)!=b.charAt(j))j=next[j];
112+
if(b.charAt(i+1) == b.charAt(j+1)){
113+
next[i+1]=next[++j];
114+
}else{
115+
next[i+1]=++j;
116+
}
117+
}
118+
System.out.println("next2 : " + Arrays.toString(next));
119+
return next;
120+
}
121+
public static void search2(String original, String find, int next[]) {
122+
int j = 0;
123+
for (int i = 0; i < original.length(); i++) {
124+
while (j > -1 && original.charAt(i) != find.charAt(j))
125+
j = next[j];
126+
if (j == -1 || original.charAt(i) == find.charAt(j))
127+
j++;
128+
if (j == find.length()) {
129+
System.out.println("2 find at position " + (i - j + 1));
130+
System.out.println(original.subSequence(i - j + 1, i + 1));
131+
j = next[j];
132+
}
133+
}
134+
}
135+
136+
//next表示长度为i的字符串前缀和后缀的最长公共部分，从0开始
137+
public static int[] getNext3(String b)
138+
{
139+
int len=b.length();
140+
int j= 0;
141+
142+
int next[]=new int[len];//next表示长度为i的字符串前缀和后缀的最长公共部分，从0开始
143+
if(len > 0){
144+
next[0]=0;
145+
}
146+
147+
for(int i=1;i<len-1;i++)//i表示字符串的下标，从0开始
148+
{//j在每次循环开始都表示next[i]的值，同时也表示需要比较的下一个位置
149+
while(j>0 && b.charAt(i)!=b.charAt(j) )j=next[j-1];
150+
if(b.charAt(i) == b.charAt(j)){
151+
j++;
152+
}
153+
next[i]=j;
154+
}
155+
System.out.println("next3 : " + Arrays.toString(next));
156+
return next;
157+
}
158+
public static void search3(String original, String find, int next[]) {
159+
int j = 0;
160+
for (int i = 0; i < original.length(); i++) {
161+
while (j > 0 && original.charAt(i) != find.charAt(j))
162+
j = next[j-1];
163+
if (original.charAt(i) == find.charAt(j))
164+
j++;
165+
if (j == find.length()) {
166+
System.out.println("3 find at position " + (i - j + 1));
167+
System.out.println(original.subSequence(i - j + 1, i + 1));
168+
j = next[j];
169+
}
170+
}
171+
}
90172
}

‎ChapterAlgorithm/src/algorithm/ali/automn2017/NO1.java‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package algorithm.ali.automn2017;
2+
/*
3+
* 天猫国际每天都会卖出很多跨境商品，用户每次下单可能购买多个商品，购买总数小于10件，由于海关规定，每一个进入海关的箱子里面的商品总额不能超过2000元（否则不能清关）所以当用户下单总金额超过2000，必须使用多个箱子分开包装运输；现在为了节约运输成本，希望在满足海关的要求下，能够使用尽可能少的箱子。
4+
注：
5+
每个商品都有自己的单价，有特定的长宽高，所有商品都是长方体
6+
商品可以横放、竖放、侧放，但不用考虑斜放，但是长宽高各项总和必须都要小于等于箱子的长宽高
7+
假定目前天猫国际使用同一种规格的箱子
8+
boxLong,boxWidth,boxHigh
9+
（箱子长，箱子宽，箱子高）
10+
11+
某用户下单买了如下商品
12+
n（商品件数）
13+
item1Price,item1Long,item1With,item1High
14+
item2Price,item2Long,item2With,item2High
15+
item3Price,item3Long,item3With,item3High
16+
item4Price,item4Long,item4With,item4High
17+
...
18+
（商品价格，商品长，商品宽，商品高）
19+
(所有输入类型均为int型正整数)
20+
21+
请你算出需要使用最小的箱子数量，可以将这些商品顺利得清关送到消费者手中，如果无解，输出-1
22+
23+
输入:
24+
输入箱子长宽高 输入购买商品数 输入每个商品长宽高
25+
输出:
26+
输出最小箱子数
27+
输入范例:
28+
10 20 30
29+
3
30+
1000 10 10 30
31+
500 10 10 20
32+
600 8 10 20
33+
输出范例:
34+
2
35+
*/
36+
public class NO1 {
37+
38+
}

‎ChapterAlgorithm/src/algorithm/ali/automn2017/NO2.java‎

Lines changed: 229 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,229 @@
1+
package algorithm.ali.automn2017;
2+
3+
import java.io.FileInputStream;
4+
import java.io.InputStreamReader;
5+
/*
6+
* 在快递公司干线运输的车辆使用中，存在着单边车和双边车的两种使用场景，例如 北京中心-杭州中心，
7+
* 两个分拨中心到彼此的单量对等，则可以开双边车（即同一辆车可以往返对开），
8+
* 而当两个中心的对发单量不对等时，则会采用单边车，并且双边车的成本是低于单边车的，
9+
* 即将两辆对开的单边车合并为一辆往返的双边车是能够节省运力成本的
10+
单边车优化原则：
11+
将单边车优化的规则进行可抽象为以下三种（A,B,C均表示分拨中心）：
12+
规则-1: A-B单边车，B-A单边车 优化方案：将A-B和B-A的两辆单边车合并为双边；
13+
规则-2: A-B单边车，B-C单边车，C-A单边车 优化方案：将A-B、B-C、C-A的三辆单边车优化为一辆环形往返车；
14+
规则-3: A-B单边车，C-A单边车，B、C同省 优化方案：当B、C同省，将A-B、C-A两辆单边优化为一辆环形往返
15+
问题如下：
16+
以某快递公司的实际单边车数据为例
17+
（线路ID编码;出分拨中心; 出分拨中心所在省;到达分拨中心;到达分拨中心所在省；车型；），
18+
进行优化，优化的规则参照以上，并且优先级依次降低，合并的时候需要考虑车型（分为17.5m和9.6m两种）：
19+
1、相同车型才能进行合并；
20+
2、两辆同方向的9.6m可以与一辆17.5m的对开车型合并优化
21+
说明：优化输出结果按照规则分类，
22+
例如rule1： 2016120001+2016120002表示将单边车线路ID编码为2016120001和2016120002按照规则1合并优化
23+
24+
输入:
25+
线路数据，大于2行 每行由6列组成 线路ID;出发分拨中心名称;出发省名称;到达分拨中心名称;到达省名称;车型;
26+
输出:
27+
按照三个优化规则输出的单边车优化结果
28+
输入范例:
29+
350410;嘉兴中心;浙江省;西安中心;陕西省;9.6m;
30+
350424;西安中心;陕西省;嘉兴中心;浙江省;9.6m;
31+
350428;嘉兴中心;浙江省;长沙中心;湖南省;17.5m;
32+
350432;长沙中心;湖南省;武汉中心;湖北省;17.5m;
33+
350448;武汉中心;湖北省;嘉兴中心;浙江省;17.5m;
34+
350476;嘉兴中心;浙江省;潍坊中心;山东省;9.6m;
35+
350479;潍坊中心;山东省;嘉兴中心;浙江省;17.5m;
36+
350481;嘉兴中心;浙江省;成都中心;四川省;9.6m;
37+
输出范例:
38+
rule1:350410+350424
39+
rule2:350428+350432+350448
40+
*/
41+
import java.util.*;
42+
import java.io.*;
43+
public class NO2 {
44+
public static void main(String[] args) {
45+
Scanner scanner = null;
46+
try{
47+
scanner = new Scanner(new InputStreamReader(new FileInputStream(new File("/home/xiepuxin/data.txt"))));
48+
}catch(Exception e){
49+
e.printStackTrace();
50+
}
51+
List<UnilateralLine> lineList = new ArrayList<UnilateralLine>();
52+
while (scanner.hasNextLine()) {
53+
String[] options = scanner.nextLine().split(";");
54+
if (options.length < 5) {
55+
break;
56+
}
57+
lineList.add(new UnilateralLine(options[0], options[1], options[2],
58+
options[3], options[4], options[5]));
59+
}
60+
scanner.close();
61+
62+
// wirte your code here
63+
List<String> result = calculateUnilateral(lineList);
64+
65+
for (String str : result) {
66+
System.out.println(str);
67+
}
68+
}
69+
70+
public static List<String> calculateUnilateral(List<UnilateralLine> lineList) {
71+
List<String> result = new ArrayList<String>();
72+
Map<String,String> map = new HashMap<>();
73+
int n = lineList.size();
74+
boolean[] remove = new boolean[n];
75+
76+
for(int i = 0 ; i < n ; i++){
77+
if(remove[i] == false){
78+
for(int j = i+1 ; j < n ;j++){
79+
if(remove[j] == false &&
80+
lineList.get(i).getSCen().equals(lineList.get(j).getECen()) &&
81+
lineList.get(j).getSCen().equals(lineList.get(i).getECen())){
82+
if(lineList.get(i).getTType().equals(lineList.get(j).getTType())){
83+
remove[i] = true;
84+
remove[j] = true;
85+
result.add("rule1:" + lineList.get(i).getId() + "+" + lineList.get(j).getId());
86+
}else{
87+
UnilateralLine small = null;
88+
String value = "";
89+
if(lineList.get(i).getTType().equals("9.6m")){
90+
small = lineList.get(i);
91+
value = i+"+"+j + " " + lineList.get(i).getECen()+"+"+lineList.get(i).getSCen();
92+
}else{
93+
small = lineList.get(j);
94+
value = j+"+"+i + " " + lineList.get(j).getECen()+"+"+lineList.get(j).getSCen();
95+
}
96+
String s = small.getSCen()+small.getECen();
97+
if(map.containsKey(s)){
98+
String[] ss = map.get(s).split(" ");
99+
String[] index = ss[0].split("\\+");
100+
String[] id = ss[1].split("\\+");
101+
int a = Integer.valueOf(index[0]);
102+
int b = Integer.valueOf(index[1]);
103+
if(remove[a] == true || remove[b] == true){
104+
continue;
105+
}
106+
remove[a] = true;
107+
remove[b] = true;
108+
remove[i] = true;
109+
remove[j] = true;
110+
result.add("rule1:" + small.getId() + "+" + lineList.get(a).getId()+ "+" + lineList.get(b).getId());
111+
}else{
112+
map.put(s, value);
113+
}
114+
}
115+
}
116+
}
117+
}
118+
}
119+
for(int i = 0 ; i < n ; i++){
120+
if(remove[i] == false){
121+
for(int j = i+1 ; j < n ; j++){
122+
if(remove[j] == false){
123+
for(int k = j+1 ; k < n ; k++){
124+
if(remove[k] == false &&
125+
lineList.get(i).getSCen().equals(lineList.get(k).getECen()) &&
126+
lineList.get(j).getSCen().equals(lineList.get(i).getECen()) &&
127+
lineList.get(k).getSCen().equals(lineList.get(j).getECen()) &&
128+
lineList.get(i).getTType().equals(lineList.get(j).getTType()) &&
129+
lineList.get(j).getTType().equals(lineList.get(k).getTType()) ){
130+
remove[i] = true;
131+
remove[j] = true;
132+
remove[k] = true;
133+
result.add("rule2:" + lineList.get(i).getId() + "+" + lineList.get(j).getId() + "+" + lineList.get(k).getId());
134+
}
135+
}
136+
}
137+
}
138+
}
139+
}
140+
for(int i = 0 ; i < n ; i++){
141+
if(remove[i] == false){
142+
for(int j = i+1 ; j < n ; j++){
143+
if(remove[j] == false &&
144+
lineList.get(i).getTType().equals(lineList.get(j).getTType()) &&
145+
(
146+
(lineList.get(i).getSCen().equals(lineList.get(j).getECen()) &&
147+
lineList.get(i).getEPro().equals(lineList.get(j).getSPro())) ||
148+
(lineList.get(i).getSCen().equals(lineList.get(j).getECen()) &&
149+
lineList.get(i).getEPro().equals(lineList.get(j).getSPro()))
150+
)
151+
){
152+
remove[i] = true;
153+
remove[j] = true;
154+
result.add("rule3:" + lineList.get(i).getId() + "+" + lineList.get(j).getId());
155+
}
156+
}
157+
}
158+
}
159+
return result;
160+
}
161+
162+
public static class UnilateralLine {
163+
private String id;
164+
private String sCen;// 出发分拨
165+
private String sPro;// 出发省
166+
private String eCen;// 到达分拨
167+
private String ePro;// 到达省
168+
// 9.6m/17.5m
169+
private String tType;// 车型
170+
171+
public UnilateralLine(String id, String sCen, String sPro, String eCen,
172+
String ePro, String tType) {
173+
this.id = id;
174+
this.sCen = sCen;
175+
this.sPro = sPro;
176+
this.eCen = eCen;
177+
this.ePro = ePro;
178+
this.tType = tType;
179+
}
180+
181+
public String getId() {
182+
return id;
183+
}
184+
185+
public void setId(String id) {
186+
this.id = id;
187+
}
188+
189+
public String getSCen() {
190+
return sCen;
191+
}
192+
193+
public void setSCen(String ePro) {
194+
this.ePro = ePro;
195+
}
196+
197+
public String getSPro() {
198+
return sPro;
199+
}
200+
201+
public void setSPro(String sPro) {
202+
this.sPro = sPro;
203+
}
204+
205+
public String getECen() {
206+
return eCen;
207+
}
208+
209+
public void setECen(String eCen) {
210+
this.eCen = eCen;
211+
}
212+
213+
public String getEPro() {
214+
return ePro;
215+
}
216+
217+
public void setEPro(String ePro) {
218+
this.ePro = ePro;
219+
}
220+
221+
public String getTType() {
222+
return tType;
223+
}
224+
225+
public void setTType(String tType) {
226+
this.tType = tType;
227+
}
228+
}
229+
}

0 commit comments

Comments
 (0)