leetcode

0914 算法题

leetcode 179 最大数

给定一个nums数组，请重新排列每个数的顺序，使得其排列组成一个最大的数
主要熟悉冒泡排序、String的compareTo函数，它是从高位到低位逐位比较大小。
还有处理00这种情况

import java.util.*;
import java.lang.*;
class Solution {public String largestNumber(int[] nums) {// 冒泡int left=0;int temp=0;for(int i=0;i<nums.length-1;i++){for(int j=nums.length-1;j>left;j--){// j 大于 j-1if(((""+nums[j]+nums[j-1]).compareTo(""+nums[j-1]+nums[j]))>0){temp=nums[j];nums[j]=nums[j-1];nums[j-1]=temp;}}}StringBuilder result=new StringBuilder("");for(int i=0;i<nums.length;i++){result.append(nums[i]);}//00if(result.substring(0,1).equals("0")){return "0";}return result.toString();}
}

leetcode nums数组两个数字和为target

1遍历数组，向后查找是否有与当前下标数和为target的。为了加速查找，可以先排序，在进行查找。时间复杂度为O(nlogn)
2使用hash表存储nums[i],每次遍历到一个元素，检索hash表中是否有target-nums[i]，如果有则返回该匹配的结果，否则将其放入hash表中。时间复杂度为O(n),空间复杂度为O(n)。
判断某个值存不存在，一般都有空间换时间的替代解法，使用hashMap，set等。本题是判断target-num[i]是否存在。

排序复习

冒泡

for(int i=0;i<nums.length;i++)
{int left=0;int temp=0;for(int j=nums.length-1;j>left;j--){temp=nums[j];nums[j]=nums[j-1];nums[j-1]=temp;}
}

快速排序

#使用了nums[left]作为划分界限，并从nums[left+1]开始排序，最终再把nums[left]和nums[j]交换。void quicksort(int[] nums,int left,int right)
{<!-- 划分 -->int i=left;int j=right+1;int temp=0;while(true){while(nums[++i]<nums[left] & i<right);while(nums[--j]>nums[left]);if(i>=j){break;}temp=nums[i];nums[i]=nums[j];nums[j]=temp;}temp=nums[left];nums[left]=nums[j];nums[j]=temp;quicksort(nums,left,j);quicksort(nums,j+1,right);
}

堆排序

#java 用优先队列实现
#默认是小根堆
PriorityQueue<Integer> queue = new PriorityQueue<>();# 大根堆
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
});#简化写法
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2)->o2.compareTo(o1));
Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());queue.offer(12);
queue.poll();

牛客 DP18 滑雪

动态规划 极值类型，求出得到极值的path。这题关键点是确定起点和计算方向，起点是最低的点，计算方向是按照高度增加。

import java.util.*;//     
class HeightAxis{public int height;public int i;public int j;public  HeightAxis(int height,int i,int j){this.height=height;this.i=i;this.j=j;}
}public class Main{
//     选出最长的路径，状态值为当前的max长度，依赖为取决于三个方向。起始点为当一个点的四周没有比他低的（排除来路），其max=0。如何取到所有滑道。public static void main(String[] args){Scanner scanner=new Scanner(System.in);int n=0;int m=0;n=scanner.nextInt();m=scanner.nextInt();PriorityQueue<HeightAxis> heightQueue=heightQueue=new PriorityQueue<HeightAxis>((o1,o2)->(o1.height-o2.height));;int [][] matrix=new int[n][m];for(int i=0;i<n;i++){for(int j=0;j<m;j++){matrix[i][j]=scanner.nextInt();HeightAxis h=new HeightAxis(matrix[i][j],i,j);heightQueue.offer(h);}}Main.answer(matrix,n,m,heightQueue);}public static void answer(int [][] matrix,int n,int m,PriorityQueue<HeightAxis> heightQueue){int [] [] dp=new int [n][m];int maxResult=Integer.MIN_VALUE;while(heightQueue.size()>0){    HeightAxis h=heightQueue.poll();int i=h.i;int j=h.j;int max=1;if(i-1>=0 && matrix[i][j]>matrix[i-1][j]){max=(dp[i-1][j]+1)>max?(dp[i-1][j]+1):max;}if(i+1<n && matrix[i][j]>matrix[i+1][j]){max=(dp[i+1][j]+1)>max?(dp[i+1][j]+1):max;}if(j-1>=0 && matrix[i][j]>matrix[i][j-1]){max=(dp[i][j-1]+1)>max?(dp[i][j-1]+1):max;}if(j+1<m && matrix[i][j]>matrix[i][j+1]){max=(dp[i][j+1]+1)>max?(dp[i][j+1]+1):max;}dp[i][j]=max;  maxResult=max>maxResult?max:maxResult;}System.out.println(maxResult);
//     max}
}