java算法题 之 思维转换
- 顶级难题：楼轮廓问题
- 最大矩形覆盖数量
- 模拟容器存水
-
- 前后缀差点最大值
- 旋转词
顶级难题：楼轮廓问题
- 仍然是按照数组的常规思路将问题划分为每个x值下的问题
class BuildingOutline {
// 全部流程的主方法
public static List> buildingOutline(int[][] matrix) {
Node[] nodes = new Node[matrix.length * 2];
// 每一个大楼轮廓数组，产生两个描述高度变化的对象
for (int i = 0; i < matrix.length; i++) {
nodes[i * 2] = new Node(matrix[i][0], true, matrix[i][2]);
nodes[i * 2 + 1] = new Node(matrix[i][1], false, matrix[i][2]);
}
// 把描述高度变化的对象数组，按照规定的排序策略排序(x值，同按先add后delete)
Arrays.sort(nodes, new NodeComparator());
// TreeMap有序自动按key排序
TreeMap mapHeightTimes = new TreeMap<>();
TreeMap mapXvalueHeight = new TreeMap<>();
for (Node node : nodes) {
if (node.isAdd) { // 如果当前是加入操作
mapHeightTimes.merge(node.height, 1, Integer::sum);
} else { // 如果当前是删除操作
if (mapHeightTimes.get(node.height) == 1) { // 如果当前的高度出现次数为1，直接删除记录
mapHeightTimes.remove(node.height);
} else { // 如果当前的高度出现次数大于1，次数减1即可
mapHeightTimes.put(node.height,
mapHeightTimes.get(node.height) - 1);
}
}
// 根据mapHeightTimes中的最大高度，设置每个x值下的最高高度值
if (mapHeightTimes.isEmpty()) { // 如果mapHeightTimes为空，说明最大高度为0
mapXvalueHeight.put(node.x, 0);
} else { // 如果mapHeightTimes不为空，通过mapHeightTimes.lastKey()取得最大高度
mapXvalueHeight.put(node.x, mapHeightTimes.lastKey());
}
}
// res为结果数组，每一个List代表一个轮廓线，有开始位置，结束位置，高度，一共三个信息
List> res = new ArrayList<>();
// 一个新轮廓线的开始位置
int start = 0;
// 之前的最大高度
int preHeight = 0;
// 根据mapXvalueHeight生成res数组
for (Map.Entry entry : mapXvalueHeight.entrySet()) {
// 当前位置
int curX = entry.getKey();
// 当前最大高度
int curMaxHeight = entry.getValue();
if (preHeight != curMaxHeight) { // 之前最大高度和当前最大高度不一样时
if (preHeight != 0) {
res.add(new ArrayList<>(Arrays.asList(start, curX, preHeight)));
}
start = curX;
preHeight = curMaxHeight;
}
}
return res;
}
// 描述高度变化的对象
static class Node {
public int x; // x轴上的值
public boolean isAdd;// true为加入，false为删除
public int height; // 高度
public Node(int x, boolean isAdd, int h) {
this.x = x;
this.isAdd = isAdd;
this.height = h;
}
}
// 排序的比较策略
// 1，第一个维度的x值从小到大。
// 2，如果第一个维度的值相等，看第二个维度的值，“加入”排在前，“删除”排在后
// 3，如果两个对象第一维度和第二个维度的值都相等，则认为两个对象相等，谁在前都行。
private static class NodeComparator implements Comparator {
@Override
public int compare(Node o1, Node o2) {
if (o1.x != o2.x) {
return o1.x - o2.x;
}
if (o1.isAdd != o2.isAdd) {
return o1.isAdd ? -1 : 1;
}
return 0;
}
}
}
最大矩形覆盖数量
public class Main {
public static class Rectangle {
public int up;
public int down;
public int left;
public int right;
public Rectangle(int up, int down, int left, int right) {
this.up = up;
this.down = down;
this.left = left;
this.right = right;
}
}
public static class DownComparator implements Comparator {
public int compare(Rectangle o1, Rectangle o2) {
return o1.down - o2.down;
}
}
public static class LeftComparator implements Comparator {
public int compare(Rectangle o1, Rectangle o2) {
return o1.left - o2.left;
}
}
public static int maxCover(Rectangle[] recs) {
if (recs == null || recs.length == 0) {
return 0;
}
//按照矩形底边进行排序
Arrays.sort(recs, new DownComparator());
//通过左边大小进行排序
TreeSet leftOrdered = new TreeSet<>(new LeftComparator());
int ans = 0;
for (int i = 0; i < recs.length; i++) {
int curDown = recs[i].down;
int index = i;
//将底边为curDown到所有recs填入到leftOrdered
while (recs[index].down == curDown) {
leftOrdered.add(recs[index]);
index++;
}
i = index;
//取出leftOrdered中所有up值小于curDown的值
removeLowerOnCurDown(leftOrdered, curDown);
//此时定存在一条直线同时穿过所有leftOrdered中所有元素
//将二维关系转化成了一维线性关系
HashSet rightOrdered = new HashSet<>();
for (Rectangle rec : leftOrdered) {
//将右边界小于rec.left的值从rightOrdered中删除。
removeLeftOnCurLeft(rightOrdered, rec.left);
//rightOrdered将rec填入
rightOrdered.add(rec);
//此时更新ans
ans = Math.max(ans, rightOrdered.size());
}
}
return ans;
}
public static void removeLowerOnCurDown(TreeSet set, int curDown) {
List removes = new ArrayList<>();
for (Rectangle rec : set) {
if (rec.up <= curDown) {
removes.add(rec);
}
}
for (Rectangle rec : removes) {
set.remove(rec);
}
}
public static void removeLeftOnCurLeft(HashSet rightOrdered, int curLeft) {
HashSetset=new HashSet();
for (Rectangle rectangle : rightOrdered) {
if (rectangle.right<=curLeft) {
set.add(rectangle);
}
}
for (Rectangle rectangle : set) {
rightOrdered.remove(rectangle);
}
}
}
模拟容器存水
- 一般思维是计算每个凹槽所能承受水的量
- 转换成分析每一桶上层最多盛的水的量，就转换成了求两边最大值的最小值问题，经过数据预处理就能相对高效的实现。
- 另外可以进一步通过动态方法进行最值的求解，空间复杂度变成O(1)
空间O(N)
public class Test {
public static void main(String[] args) {
System.out.println(num(new int[]{4,5,1,3,2}));
}
public static int num(int[] arr){
if (arr==null||arr.length==0)return 0;
int[] leftMax=new int[arr.length];
leftMax[0]=arr[0];
for (int i = 1; i < arr.length; i++) {
leftMax[i]= Math.max(leftMax[i - 1], arr[i]);
}
int[] rightMax=new int[arr.length];
rightMax[arr.length-1]=arr[arr.length-1];
for (int i=arr.length-2;i>=0;i--){
rightMax[i]=Math.max(rightMax[i+1],arr[i]);
}
int num=0;
for (int i=1;i
空间O(1)
public class Test {
public static void main(String[] args) {
System.out.println(num(new int[]{4, 5, 1, 3, 2}));
}
public static int num(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int leftMax = arr[0];
int rightMax = arr[arr.length - 1];
int leftIndex = 1;
int rightIndex = arr.length - 1;
int num = 0;
while (leftIndex <= rightIndex) {
if (leftMax < rightMax) {
if (leftMax < arr[leftIndex]) {
leftMax = arr[leftIndex];
} else {
num += leftMax - arr[leftIndex];
}
leftIndex++;
} else {
if (rightMax < arr[rightIndex]) {
rightMax = arr[rightIndex];
} else {
num += rightMax - arr[rightIndex];
}
rightIndex--;
}
}
return num;
}
}
前后缀差点最大值
- 一般思路：数据预处理建立两个从左右两端的最值数组，再遍历求解。
- 极限思维：直接获取最大值和左右两端的差值
public class Test {
public static int num(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int max=arr[0];
for (int i=1;i
旋转词
- 一般思路：尝试所有的情况，看是否存在相同的
- 优化思路：见代码
public class Test {
public static boolean isRoa(String s,String r){
if (s.length()!=r.length())return false;
String ss= s + s;
return ss.contains(r);
}
}
