笔经整理4

题目来源：牛客网

1.列表补全

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

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

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

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

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

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

输入描述:

每个测试输入包含1个测试用例，包含四个整数，分别表示偏移量offset、元素数量n，列表L1的长度l1，列表L2的长度l2。

输出描述:

在一行内输出四个整数分别表示L1和L2的区间start1，end1，start2，end2，每个数字之间有一个空格。
注意，区间段使用半开半闭区间表示，即包含起点，不包含终点。如果某个列表的区间为空，使用[0, 0)表示，如果某个列表被跳过，使用[len, len)表示，len表示列表的长度。

输入例子1:

2 4 4 4
1 2 4 4
4 1 3 3

输出例子1:

2 4 0 2
1 3 0 0
3 3 1 2

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 个方块落下时他觉得太无聊就关掉了，小易希望你告诉他这局游戏他获得的分数。

输入描述:

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

输出描述:

小易这局游戏获得的分数

示例1

输入

3 9
1 1 2 2 2 3 1 2 3

输出

2

思路：统计个数找最小值。

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);
        }
    }
}

---

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

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”。

输出描述:

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

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 '#';
    }
}