这里帖一下目前找到的仅有几道非Leetcode的题，附上自己的解答
欢迎补充更多面经或者其他解法
红绿灯：
[红, 绿, 绿, 红, 红]. 翻转⼀个⼦区间(红变绿,绿变红),使得绿灯个数最⼤. 返回区间的起点和终点
解答
这里假设返回区间的左右端都是inclusive的, 比如返回[2，2]就代表区间包含一个元素，下标为2
本质上是实现 Kadanes’ algorithm, O(n) time, O(1) space
代码
import java.util.*;
class TrafficLight{
public static int[] interval (String[] colors) {
int[] res = new int[2];
int[] encode = new int[colors.length];
for (int i = 0; i < colors.length; i++) {
if (colors[i].equals("R")) encode[i] = 1;
else encode[i] = -1;
}
int max_so_far = 0;
int max_ending_here = 0;
int start = 0, end = 0, next_start = 0;
for (int i = 0; i < colors.length; i++) {
max_ending_here += encode[i];
//System.out.println(i);
//System.out.println(max_ending_here);
if (max_ending_here < 0) {
//System.out.println("start next");
if (i < colors.length - 1) next_start = i + 1;
max_ending_here = 0;
} else if (max_so_far < max_ending_here) {
//System.out.println("end here");
end = i;
if (next_start > 0) start = next_start;
max_so_far = max_ending_here;
}
}
res[0] = start;
res[1] = end;
return res;
}
public static void main(String[] args) {
String[] colors = new String[]{"R", "G", "G", "R", "R"};
int[] res = interval(colors);
for (int r : res) {
System.out.println(r);
}
String[] colors1 = new String[]{"G", "R", "G", "G", "R", "R"};
int[] res1 = interval(colors1);
for (int r : res1) {
System.out.println(r);
}
}
}
设计一个买/卖一个商品的class，提供两个功能，buy(price, quantity)和sell(price, quantity)，意思就是有人出多少钱买多少个这个商
品，或者有人标价多少钱卖这个商品，返回值是买到或者卖出的数量，例子：
sell(10, 20) 返回0，暂时没人买，把这个数据存着
buy(5, 20) 返回0，没有人用<=5的价格卖这个商品，把这个订单也存起来
sell(4, 25) 返回20，上一行那个买家就买到了20个，然后剩5个存起来
buy(12, 30) 返回25，第一行的20个被买了，还有上一行剩的5个也被买了，然后还差5个的订单，存起来
另外，如果有多个卖家用不同的价格卖同一个商品，并且价格都低于当前buy的价格，先买哪个无所谓。反之亦然
概要
用两个treemap 分别存买方(buyMap)和卖方(sellMap)目前剩余的订单，key是价格，value是存货量。
每次buy交易，在sellMap中搜索出价不高于本次买方出价的存货，从价格低的搜起，如果某一价位的商品被买完，及时清空对应的map entry。 最后如果本次购买的量还有剩余（价格不高于出价的商品都买完了），剩余的加入对应的buyMap.
对于sell交易，只需要改为从buyMap中搜索价格不低于本次出价的存货，最后更新对应的sellMap就可以
复杂度：假设有n条交易记录， 用来存放map的空间是O(n), 每次交易都需要遍历一遍当前map, 时间上是O(n^2) 的
class BuyerSeller{
private Map<Integer, Integer> sellMap;
private Map<Integer, Integer> buyMap;
private int sellStock;
private int buyStock;
public BuyerSeller() {
this.buyMap = new TreeMap<>();
this.sellMap = new TreeMap<>();
sellStock = 0;
buyStock = 0;
}
public int sell(int price, int quantity) {
int res = quantity; // residual quantity not sold
if (buyMap.containsKey(price)) {
int bq = buyMap.get(price);
if (bq > quantity) {
buyMap.put(price, bq - quantity);
return quantity;
} else {
res = res - bq;
buyMap.remove(price);
}
}
List<Integer> keys = new ArrayList<>(); //store price entry to be removed
List<Integer> values = new ArrayList<>(); //store coresponding values
for (int p: buyMap.keySet()) {
if (p < price) {
// do nothing
} else {
int q = buyMap.get(p);
if (q > res) {
keys.add(p);
values.add(q - res);
res = 0;
break;
} else {
res = res - q;
keys.add(p);
values.add(0);
}
}
}
for (int i = 0; i < keys.size(); i++) {
if (values.get(i) > 0) buyMap.put(keys.get(i), values.get(i));
else buyMap.remove(keys.get(i));
}
if (res > 0) {
if (sellMap.containsKey(price)) {
int cur_q = sellMap.get(price);
sellMap.put(price, res + cur_q);
} else {
sellMap.put(price, res);
}
}
return quantity - res;
}
public int buy(int price, int quantity) {
int res = quantity; //residual quantity not bought
if (sellMap.containsKey(price)) {
int sq = sellMap.get(price);
if (sq > quantity) {
sellMap.put(price, sq - quantity);
return quantity;
} else {
res = res - sq;
sellMap.remove(price);
}
}
List<Integer> keys = new ArrayList<>(); //store price entry to be removed
List<Integer> values = new ArrayList<>(); //store coresponding values
for (int p: sellMap.keySet()) {
if (p <= price) {
int q = sellMap.get(p);
if (q > res) {
keys.add(p);
values.add(q - res);
res = 0;
break;
} else {
res = res - q;
keys.add(p);
values.add(0);
}
} else {
break;
}
}
for (int i = 0; i < keys.size(); i++) {
if (values.get(i) > 0) sellMap.put(keys.get(i), values.get(i));
else sellMap.remove(keys.get(i));
}
if (res > 0) {
if (buyMap.containsKey(price)) {
int cur_q = buyMap.get(price);
buyMap.put(price, res + cur_q);
} else {
buyMap.put(price, res);
}
}
return quantity - res;
}
// get number of products not bought
public int stockBuySize() {
for (int k : buyMap.keySet()) {
buyStock += buyMap.get(k);
}
return buyStock;
}
// get number of products not sold
public int stockSellSize() {
for (int k : sellMap.keySet()) {
sellStock += sellMap.get(k);
}
return sellStock;
}
}
class Trade {
public static void main(String[] args) {
System.out.println("trade 1");
BuyerSeller bs = new BuyerSeller();
System.out.println("sell amount: " + bs.sell(10, 20));
System.out.println("buy amount: " + bs.buy(5, 20));
System.out.println("sell amount: " + bs.sell(4, 25));
System.out.println("buy amount: " + bs.buy(12, 30));
System.out.println("number of products needed to buy: " + bs.stockBuySize());
System.out.println("number of products needed to sell: " + bs.stockSellSize());
System.out.println("trade 2");
BuyerSeller bs1 = new BuyerSeller();
System.out.println("sell amount: " + bs1.sell(1, 20));
System.out.println("buy amount: " + bs1.buy(2, 15));
System.out.println("sell amount: " + bs1.sell(1, 25));
System.out.println("buy amount: " + bs1.buy(2, 30));
System.out.println("number of products needed to buy: " + bs1.stockBuySize());
System.out.println("number of products needed to sell: " + bs1.stockSellSize());
}
}
Maximal sum increasing subsequence
Given an array of n positive integers. Write a program to find the sum of maximum sum subsequence of the given array such that the integers in the subsequence are sorted in increasing order. For example, if input is {1, 101, 2, 3, 100, 4, 5}, then output should be 106 (1 + 2 + 3 + 100), if the input array is {3, 4, 5, 10}, then output should be 22 (3 + 4 + 5 + 10) and if the input array is {10, 5, 4, 3}, then output should be 10。 链接
解答
思路还是dp， 存结束于每个下标位置的最大increasing subsequence sum
时间复杂度O(n^2), 空间复杂度O(n)
代码
import java.util.*;
class maxSumIS {
public static int maxSumIS(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int len = arr.length;
if (len == 1) return arr[0]; //lenght = 1 base case
int[] max_arr = new int[len];
max_arr[0] = arr[0];
int res = max_arr[0];
for (int i = 1; i < len; i++) {
int max = 0;
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i] && max_arr[j] > max) {
max = max_arr[j];
}
}
max_arr[i] = max + arr[i]; // if no element smaller than it, then should be length === 1
if (max_arr[i] > res) res = max_arr[i];
}
return res;
}
public static void main(String[] args) {
int[] arr = new int[]{1, 101, 2, 3, 100, 4, 5};
System.out.println(maxSumIS(arr));
int[] arr1 = new int[]{10, 5, 4, 3};
System.out.println(maxSumIS(arr1));
}
}