Fork me on GitHub

笔经整理4

题目来源:牛客网

1.列表补全

在商城的某个位置有一个商品列表,该列表是由L1、L2两个子列表拼接而成。当用户浏览并翻页时,需要从列表L1、L2中获取商品进行展示。展示规则如下:

  1. 用户可以进行多次翻页,用offset表示用户在之前页面已经浏览的商品数量,比如offset为4,表示用户已经看了4个商品

  2. n表示当前页面需要展示的商品数量

  3. 展示商品时首先使用列表L1,如果列表L1长度不够,再从列表L2中选取商品

  4. 从列表L2中补全商品时,也可能存在数量不足的情况

请根据上述规则,计算列表L1和L2中哪些商品在当前页面被展示了

输入描述:
1
每个测试输入包含1个测试用例,包含四个整数,分别表示偏移量offset、元素数量n,列表L1的长度l1,列表L2的长度l2
输出描述:
1
2
在一行内输出四个整数分别表示L1L2的区间start1,end1,start2,end2,每个数字之间有一个空格。
注意,区间段使用半开半闭区间表示,即包含起点,不包含终点。如果某个列表的区间为空,使用[0, 0)表示,如果某个列表被跳过,使用[len, len)表示,len表示列表的长度。
输入例子1:
1
2
3
2 4 4 4
1 2 4 4
4 1 3 3
输出例子1:
1
2
3
2 4 0 2
1 3 0 0
3 3 1 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
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int offset = sc.nextInt();
int n = sc.nextInt();
int l1 = sc.nextInt();
int l2 = sc.nextInt();
int h1, t1, h2, t2;
if (offset < l1) {
h1 = offset;
t1 = Math.min(offset + n, l1);
h2 = 0;
t2 = Math.max(Math.min(l2, offset + n - l1), 0);
} else if (offset < l1 + l2) {
h1 = l1;
t1 = l1;
h2 = offset - l1;
t2 = Math.max(Math.min(l2, offset + n - l1), 0);
} else {
h1 = l1;
t1 = l1;
h2 = l2;
t2 = l2;
}
String ret = String.format("%s %s %s %s", h1, t1, h2, t2);
System.out.println(ret);
}
}
}

2.俄罗斯方块

小易有一个古老的游戏机,上面有着经典的游戏俄罗斯方块。因为它比较古老,所以规则和一般的俄罗斯方块不同。
荧幕上一共有 n 列,每次都会有一个 1 x 1 的方块随机落下,在同一列中,后落下的方块会叠在先前的方块之上,当一整行方块都被占满时,这一行会被消去,并得到1分。
有一天,小易又开了一局游戏,当玩到第 m 个方块落下时他觉得太无聊就关掉了,小易希望你告诉他这局游戏他获得的分数。

输入描述:

1
2
3
第一行两个数 n, m
第二行 m 个数,c1, c2, ... , cm , ci 表示第 i 个方块落在第几列
其中 1 <= n, m <= 1000, 1 <= ci <= n

输出描述:

1
小易这局游戏获得的分数

示例1

输入

1
2
3 9
1 1 2 2 2 3 1 2 3

输出

1
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
import java.util.*;
import java.util.stream.Collectors;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt(); // column
int m = sc.nextInt(); // num
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i<m;++i){
int temp = sc.nextInt();
if(map.containsKey(temp)){
map.put(temp,map.get(temp)+1);
}else{
map.put(temp,1);
}
}
int num = (int)map.keySet().stream().filter(x -> x>=1 && x<=n).count();
int result;
if(num!=n){
result = 0;
}else{
result = map.values().stream().sorted().collect(Collectors.toList()).get(0);
}
System.out.println(result);
}
}
}

由前序数组、中序数组转换成二叉树

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

import java.util.*;

public class 前序中序拿到转换二叉树 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String line0 = sc.nextLine();
String line1 = sc.nextLine();
String[] pres = line0.split("\\s");
String[] mids = line1.split("\\s");
int n = pres.length;
int[] pre = new int[n];
int[] mid = new int[n];
for (int i = 0; i < n; ++i) {
pre[i] = Integer.parseInt(pres[i]);
mid[i] = Integer.parseInt(mids[i]);
}
treeNode root = transferTree(pre, mid, 0, n - 1, 0, n - 1);
System.out.println(root);
}
}

private static treeNode transferTree(int[] pre, int[] mid, int preL, int preR, int midL, int midR) {
if (preL > preR) {
return null;
}
int x = findX(mid, pre[preL]);
int leftLength = x - midL;
int rightLength = midR - x;
treeNode root = new treeNode(pre[preL]);
root.setLeft(transferTree(pre, mid, preL + 1, preL + leftLength, midL, x - 1));
root.setRight(transferTree(pre, mid, preR - rightLength + 1, preR, x + 1, midR));
return root;
}

private static int findX(int[] itemList, int target) {
for (int i = 0; i < itemList.length; ++i) {
if (itemList[i] == target) {
return i;
}
}
return -1;
}

public static class treeNode {
int val;
treeNode left, right;
public treeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
public void setLeft(treeNode left) {
this.left = left;
}
public void setRight(treeNode right) {
this.right = right;
}
}
}

分治

分治思想的绝好例子:二维平面上有 n 个点,如何快速计算出两个距离最近的点对?

分治算法应用-最近点对的最小距离-hdu 1007 Quoit Design

todo


LinkedHashMap 的好例子

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

  1. 用 linkedHashMap 既做 hash 判重,又记录了插入顺序。
  2. 需要 iterator 进行递推

题目描述

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

输出描述:

如果当前字符流没有存在出现一次的字符,返回#字符。

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.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/**
*
*
* @program: offer
* @author: maidong
* @create: 2019-08-11 21:04
**/

public class 字符流中第一个不重复的字符 {
Map<String, Integer> map = new LinkedHashMap<>();

//Insert one char from stringstream
public void Insert(char ch) {
String str = Character.toString(ch);
if (map.containsKey(str)) {
map.put(str, map.get(str) + 1);
} else {
map.put(str, 1);
}
}

//return the first appearence once char in current stringstream
public char FirstAppearingOnce() {
Set<Entry<String, Integer>> set = map.entrySet();
Iterator<Entry<String, Integer>> it = set.iterator();
while (it.hasNext()) {
Entry entry = it.next();
String key = (String) entry.getKey();
int value = (int) entry.getValue();
if (value == 1) {
return Character.valueOf(key.charAt(0));
}
}
return '#';
}
}
-------------The End-------------