演算法高級學習1
一、大樓輪廓（有序表）
給定一個 N×3 的矩陣 matrix，對於每一個長度為 3 的小數組 arr，都表示一個大樓的三個數 據。
arr[0]表示大樓的左邊界，arr[1]表示大樓的右邊界，arr[2]表示大樓的高度(一定大於 0)。
每座大樓的地基都在 X 軸上，大樓之間可能會有重疊，請返回整體的輪廓線數組。
【舉例】
matrix = { {2,5,6}, {1,7,4}, {4,6,7}, {3,6,5}, {10,13,2}, {9,11,3}, {12,14,4}, {10,12,5} }
返回：
{{1,2,4}, {2,4,6}, {4,6,7}, {6,7,4}, {9,10,3}, {10,12,5},{12,14,4}}
/**
* @Author: 郜宇博
*/
public class BuildingBorder {
public static void main(String[] args) {
int[][] matrix = new int[][]{
{2,7,3},
{3,5,5},
{4,6,4}
};
List<List<Integer>> buildingBorder = getBuildingBorder(matrix);
System.out.println(buildingBorder);
}
/**
* 用於記錄高度變化
*/
public static class Node{
public int index;
public boolean isAdd;
public int height;
public Node(int index, boolean isAdd, int height) {
this.index = index;
this.isAdd = isAdd;
this.height = height;
}
}
public static List<List<Integer>> getBuildingBorder(int[][] matrix){
Node[] nodes = getHeightUpDown(matrix);
//構造兩個有序表
//坐標-高度表
TreeMap<Integer,Integer> indexHeightMap = new TreeMap<>();
//高度-次數表
TreeMap<Integer,Integer> heightTimesMap = new TreeMap<>();
fillMap(indexHeightMap,heightTimesMap,nodes);
//返回結果
return getBorder(indexHeightMap);
}
public static List<List<Integer>> getBorder(TreeMap<Integer,Integer> indexHeightMap){
List<List<Integer>> res = new ArrayList<>();
int start = indexHeightMap.firstKey();
int preHeight = indexHeightMap.get(start);
for (Map.Entry<Integer,Integer> entry: indexHeightMap.entrySet()){
//如果高度發生變化
if (entry.getValue() != preHeight){
//添加（start,curKey,preHeight）
List<Integer> border= null;
if (preHeight != 0){
border = new ArrayList<>(Arrays.asList(start,entry.getKey(),preHeight));
res.add(border);
}
//新的list，起始點，高度都變了
start = entry.getKey();
preHeight = entry.getValue();
}
}
return res;
}
/**
* 填充map表
*/
public static void fillMap(TreeMap<Integer,Integer> indexHeightMap,TreeMap<Integer,Integer> heightTimesMap,Node[] nodes){
for (Node node: nodes){
//是否為添加
if (node.isAdd){
//1.處理heightTimesMap
//添加過，次數+1
if (heightTimesMap.containsKey(node.height)){
heightTimesMap.put(node.height,heightTimesMap.get(node.height)+1);
}else {
//沒添加guo
heightTimesMap.put(node.height,1);
}
}else {
//下降
if (heightTimesMap.get(node.height)==1){
//刪除後為0，則移除
heightTimesMap.remove(node.height);
}else {
heightTimesMap.put(node.height,heightTimesMap.get(node.height)-1);
}
}
//2.處理indexHeightMap
//沒有高度了，到結尾了
//獲取最大高度
Integer maxHeight = heightTimesMap.isEmpty()?0:heightTimesMap.lastKey();
indexHeightMap.put(node.index,maxHeight);
}
}
/**
* 獲取高度變化的數組,返回排序後的結果
*/
public static Node[] getHeightUpDown(int[][] matrix){
Node[] resultNode = new Node[matrix.length * 2];
for (int i = 0; i < matrix.length; i++){
for (int j = 0; j < matrix[0].length ; j++){
resultNode[i * 2] = new Node(matrix[i][0],true,matrix[i][2]);
resultNode[i * 2+1] = new Node(matrix[i][1],false,matrix[i][2]);
}
}
//按照index大小排序，相同的話根據add在前，排序，防止出現線狀樓
Arrays.sort(resultNode,(x,y)->{
if (x.index != y.index){
return x.index - y.index;
}
if (x.isAdd != y.isAdd){
return x.isAdd?-1:1;
}
return 0;
});
return resultNode;
}
}
二、最長子數組等於k(構造單調性、滑動窗口)
給定一個數組 arr，該數組無序，但每個值均為正數，再給定一個正數 k。
求 arr 的 所有子 數組中所有元素相加和為 k 的最長子數組長度。
例如，arr=[1,2,1,1,1]，k=3。
累加和為 3 的最長子數組為[1,1,1]，所以結果返回 3。
要求：時間複雜度O(N)，額外空間複雜度O(1)
/**
* @Author: 郜宇博
* 給定一個數組 arr，該數組無序，但每個值均為正數，再給定一個正數 k。
* 求 arr 的 所有子 數組中所有元素相加和為 k 的最長子數組長度。
*/
public class LongestChildArraySumK {
public static void main(String[] args) {
int len = 30;
int k = 15;
int[] arr = generatePositiveArray(len);
System.out.println(getLongestCount(arr, k));
}
/**
* 構造單調性，因為數組都是正數，保持一個區間，
* 當區間內sum < k時，繼續擴充區間
* 當區間sum = k 時，以i為起點，此區間最大了，更換區間，r++, l++
* 當sum > k時，如果l,r在同一位置，都向後移動，不在的話，left++,縮小區域
*/
public static int getLongestCount(int[] array, int target){
int left = 0;
int right = 0;
// sum = [left,...,right]
int sum = array[0];
int result = Integer.MIN_VALUE;
while (right != array.length){
//sum = array[right];
if (sum == target){
result = Math.max(result, right - left + 1);
if (right == array.length-1){
return Math.max(result, 0);
}
sum = sum - array[left++] + array[++right];
}
else if (sum < target){
if (right == array.length-1){
return Math.max(result, 0);
}
sum += array[++right];
}else {
if (left == right){
sum = array[++left];
right++;
}else {
sum -= array[left++];
}
}
}
return Math.max(result, 0);
}
public static int[] generatePositiveArray(int size) {
int[] result = new int[size];
for (int i = 0; i != size; i++) {
result[i] = (int) (Math.random() * 10) + 1;
}
return result;
}
}
三、拿硬幣
給定一個非負數組，每一個值代表該位置上有幾個銅板。
a和b玩遊戲，a先手，b後手， 輪到某個人的時候，只能在一個位置上拿任意數量的銅板，但是不能不拿。
誰最先把銅板拿完誰贏。假設a和b都極度聰明，請返回獲勝者的名字。
/**
* @Author: 郜宇博
* 給定一個非負數組，每一個值代表該位置上有幾個銅板。
* a和b玩遊戲，a先手，b後手， 輪到某個人的時候，只能在一個位置上拿任意數量的銅板，但是不能不拿。
* 誰最先把銅板拿完誰贏。假設a和b都極度聰明，請返回獲勝者的名字。
*/
public class PickMoneyWin {
public static void main(String[] args) {
int[] array = new int[]{3,4,1};
System.out.println(getWinner(array));
}
/**
* 最後桌子上剩下1個硬幣時，先手贏，否則後手贏
* 將所有數字求異或和，為0說明先手怎麼都贏不了
*/
public static String getWinner(int[] array){
int eorResult = 0;
for (int num: array){
eorResult ^= num;
}
return eorResult==0?"後手":"先手";
}
}
四、最長子數組小於等於k（捨去部分解）
給定一個無序數組 arr，其中元素可正、可負、可 0，給定一個整數 k。
求 arr 所 有的子數組 中累加和小於或等於 k 的最長子數組長度。
例如:arr=[3,-2,-4,0,6]，k=-2，相加和小於或等於-2 的最長子數組為{3,-2,-4,0}，所以結果返回4。
/**
* @Author: 郜宇博
* 給定一個無序數組 arr，其中元素可正、可負、可0，給定一個整數k。
* 求arr 所有的子數組累加和小於或等於k的最長子數組長度。
*/
public class LongestChildArraySumLessK {
public static void main(String[] args) {
int[] array = new int[]{3,-2,-4,0,6};
System.out.println(getSumLessK(array,-2));
}
public static int getSumLessK(int[] array, int target) {
//準備兩個數組
//1.以i開始，向後最小sum
//2.到達最小sum的邊界坐標
int[] minSum = new int[array.length];
int[] minBorder = new int[array.length];
minSum[array.length - 1] = array[array.length - 1];
minBorder[array.length - 1] = array.length - 1;
for (int i = array.length - 2; i >= 0; i--) {
minSum[i] = array[i];
minBorder[i] = i;
//如果右邊的最小和<0，那麼應該向右拓展
if (minSum[i + 1] <= 0) {
minSum[i] += minSum[i + 1];
minBorder[i] = minBorder[i + 1];
}
}
int left = 0;
int right = 0;
int result = 0;
int curSum = 0;
for (; array.length - left > result; left++) {
//不越界，並且滿足條件
while (right < array.length && minSum[right] + curSum <= target) {
//更新curSum
curSum += minSum[right];
right = minBorder[right] + 1;
}
//找到了以left為左邊界最長滿足條件的數組，更新
result = Math.max(result,right - left);
//邊界整體向右移動(!重點)
if (left == right){
right++;
}else {
curSum -= array[left];
}
}
return result;
}
}
