F
分割数组的最大值
public int splitArray(int[] nums, int m){
int left = Integer.MIN_VALUE;
int right = 0;
for(int i = 0;i < nums.length; i++){
if(nums[i] > left){
left = nums[i];
}
right += nums[i];
}
while(left < right){
int mid = left + (right - left)/2;
int count = getcount(nums, mid);
if(count > m){
//分的次数多了，那证明是给的每组的小了
left = mid + 1;
}else {
right = mid;
}
}
return left;
}
public int getcount(int[] nums,int tar){
int m = 1;
int sum = 0;
for(int i = 0;i < nums.length;i++){
if(sum + nums[i] > tar){
sum = 0;
m ++;
}
sum += nums[i];
}
return m;
}
M
马戏团人塔
public int bestSeqAtIndex(int[] height, int[] weight) {
if(height.length == 0||weight.length == 0||height.length != weight.length){
return 0;
}else if(height.length == 1 && weight.length == 1){
return 1;
}else{
int[][] arrays = new int[height.length][2];
for(int i = 0;i<height.length;i ++){
arrays[i][0] = height[i];
arrays[i][1] = weight[i];
}
Arrays.sort(arrays,new Comparator<int[]>() {
public int compare(int[] a,int[] b) {
return a[0]==b[0]?(b[1]-a[1]):(a[0] - b[0]);
}
});
int[] tail = new int[height.length];
int end = 0;
tail[end] = arrays[0][1];
for(int i = 1;i < arrays.length;i++){
if(arrays[i][1] > tail[end]){
tail[++ end] = arrays[i][1];
}else{
int left = 0;
int right = end;
while(left < right){
int mid = left + (right - left)/2;
if(tail[mid] < arrays[i][1]){
left = mid + 1;
}else{
right = mid;
}
}
tail[left] = arrays[i][1];
}
}
return ++end;
}
}
P
Pow(x,y)
public static void main(String[] args){
double x = 2.00000;
int n = 10;
Solution_p_Pow solution_p_Pow = new Solution_p_Pow();
System.out.print(solution_p_Pow.myPow(x, n));
}
public double myPow(double x,int n){
if(n < 0){
n = -n;
x = 1/x;
}
return pow(x, n);
}
public double pow(double x,int n){
if(x == 0.0 && n != 1){
return 0.0;
}else if(x == 1.0 || n == 0){
return 1.0;
}else{
double result = pow(x, n/2);
if(Math.abs(result) < 0.0000001){
result = 0;
}
result *= result;
if(n % 2 != 0){
result *= x;
}
return result;
}
}
S
使结果不超过阈值的最小除数
public int smallestDivisor(int[] nums, int threshold) {
//上限是最大数，下限是1
Arrays.sort(nums);
int left = 1;
int right = nums[nums.length - 1];
while(left < right){
int mid = left + (right - left)/2;
int ans = getans(nums, mid);
if(ans > threshold){
//ans大了，证明现在的mid小
left = mid + 1;
}else{
right = mid;
}
}
return left;
}
public int getans(int[] nums,int mid) {
int ans = 0;
for(int i = 0;i < nums.length;i ++){
if(nums[i] % mid == 0){
ans += nums[i]/mid;
}else{
ans += ((nums[i]/mid) + 1);
}
//ans += (int)Math.ceil((double)nums[i]/(double)mid);
}
return ans;
}
搜索插入位置
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left < right){
int mid = left + (right - left)/2;
if(target > nums[mid]){
left = mid + 1;
}else{
right = mid;
}
}
//特殊情况考虑
if(left == (nums.length -1) && nums[left] < target){
return left + 1;
}
return left;
}
搜索二维矩阵
public boolean searchMatrix(int[][] matrix,int target){
if(matrix.length == 0||(matrix.length != 0 && matrix[0].length == 0)){
return false;
}else{
int row = 0;
int col = matrix[0].length - 1;
while(row < matrix.length && col >= 0){
if(matrix[row][col] == target){
return true;
}else if(matrix[row][col] < target){
row ++;
}else if(matrix[row][col] > target){
col --;
}
}
return false;
}
}
搜索旋转数组
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left < right){
int mid = left + (right - left)/2;
if(nums[left] > nums[mid]){
//当前处在降序状态
if(target > nums[mid] && target <= nums[right]){
left = mid + 1;
}else{
right = mid;
}
}else{
//当前处在升序状态
if(target >= nums[left] && target <= nums[mid]){
right = mid;
}else{
left = mid +1;
}
}
}
if(nums[left] != target){
return -1;
}
return left;
}
X
稀疏数组搜索
public int findString(String[] words, String s) {
int left = 0;
int right = words.length -1;
while(words[left].equals("") && left < (words.length - 1)){
left ++;
}
while(words[right].equals("") && right >= 0){
right --;
}
while(left <= right){
//后面会有 left和right下标对应的字符串相等的对比
int mid = left + (right - left)/2;
int tem = mid;
while(words[mid].equals("") && mid >= left){
mid--;
}
if(mid >= left){
if(words[mid].compareTo(s) > 0){
right = mid - 1;
}else if(words[mid].compareTo(s) == 0){
return mid;
}else{
left = mid+ 1;
}
}else{
left = tem + 1;
}
}
return -1;
}
旋转数组的最小值
public int minArray(int[] numbers) {
if(numbers.length == 0){
throw new IllegalArgumentException();
}else if(numbers.length == 1){
return numbers[0];
}else{
int left = 0;
int right = numbers.length - 1;
while(left < right){
int mid = left + (right - left)/2;
//注意有可能会存在数组没有被旋转的情况，所以这个时候我们应该和最右边的数进行比较稳妥一些
if(numbers[mid] < numbers[right]){
right = mid;
}else if(numbers[mid] > numbers[right]) {
left = mid + 1;
}else{
//数组中可能存在有相等的元素
//当出现 nums[m]=nums[j]nums[m] = nums[j]nums[m]=nums[j] 时，
//一定有区间 [i,m][i, m][i,m] 内所有元素相等 或 区间 [m,j][m, j][m,j]内所有元素相等（或两者皆满足）
int min = Integer.MAX_VALUE;
for(int i = left;i <= right;i ++) {
min = Math.min(min,numbers[i]);
}
return min;
}
}
return numbers[left];
}
}
寻找峰值
public int findPeakElement(int[] nums){
//比较mid 和 mid + 1 的大小，
int left = 0;
int right = nums.length - 1;
while(left < right){
int mid = left + (right - left)/2;
if(nums[mid] < nums[mid + 1]){
//设想一种极端的情况，如果左边在递减，那就取最左边的数据
left = mid + 1;
}else{
//设想出一种极端的情况，如果右边一直在递增那就取最右边的数
right = mid;
}
}
return left;
}
寻找重复数
public int findDuplicate(int[] nums){
Arrays.sort(nums);
int left = 1;//最小的数
int right = nums.length - 1;//最大的数
while(left < right){
int mid = left + (right - left)/2;
int sum = getsum(nums, mid);
if(sum <= mid){
//注意这里是 <= 安全起见不写成==，因为会有多个重复的数字
left = mid + 1;
}else{
right = mid;
}
}
return left;
}
public int getsum(int[] nums,int tag){
int sum = 0;
for(int i = 0;i < nums.length;i++){
if(nums[i] > tag){
break;
}
sum ++;
}
return sum;
}
//这种方法只可以用来寻找在一个数组中只有一个数是重复的情况
public int findDuplicate1(int[] nums) {
//1到5，出现了6个数
int sum = 0;
for(int i = 0;i < nums.length;i++){
sum += nums[i];
sum = sum - (i+1);
}
return sum + nums.length;
}
Y
有序矩阵中的第K小的元素
public int kthSmallest(int[][] matrix, int k) {
if(matrix.length == 0 || matrix.length != 0 && matrix[0].length == 0){
throw new NullPointerException();
}else{
int left = matrix[0][0];
int right = matrix[matrix.length -1][matrix[0].length -1];
while(left < right){
int mid = left + (right - left)/2;
int row = 0;
int col = matrix[0].length - 1;
int count = 0;
while(row < matrix.length && col >= 0){
if(mid >= matrix[row][col]){
count += col + 1;
row ++;
}else{
col --;
}
}
if(count < k){
left = mid + 1;
}else{
right = mid;
}
}
return left;
}
}
有序数组中的唯一元素
public int singleNonDuplicate1(int[] nums){
int a = 0;
for(int i = 0;i < nums.length;i++){
a ^= nums[i];
}
return a;
}
public int singleNonDuplicate(int[] nums){
Arrays.sort(nums);
int left = 0;
int right = nums.length - 1;
while(left < right){
int mid = left + (right - left)/2;
if(nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1]){
return nums[mid];
}else{
if(nums[mid] == nums[mid + 1]){
if(mid % 2 == 0){
left = mid + 2;
}else{
right = mid - 1;
}
}else{
if(mid % 2 == 0){
right = mid - 2;
}else{
left = mid + 1;
}
}
}
}
return nums[left];
}
Z
在线选举
int[] persons;
int[] times;
int[] note;
public TopVotedCandidate(int[] persons, int[] times) {
//在times[i]时，票投给了person[i]
this.persons = persons;
this.times = times;
note = new int[times.length];
HashMap<Integer, Integer> map = new HashMap<>();
map.put(persons[0], 1);
int maxno = persons[0];
note[0] = persons[0];
for(int i = 1;i < persons.length;i++){
if(map.containsKey(persons[i])){
map.put(persons[i], map.get(persons[i]) + 1);
}else{
map.put(persons[i], 1);
}
if(map.get(maxno) <= map.get(persons[i])){
maxno = persons[i];
}
note[i] = maxno;
}
}
public int q(int t) {
int left = 0;
int right = times.length - 1;
while(left < right){
int mid = left + (right - left)/2;
if(times[mid] < t){
//如果当前的时间比 t小，那就需要向后面找一找
left = mid + 1;
}else{
right = mid;
}
//一个是mid+1,一个是mid这个是必须要保证的，负责将跳不出这个循环，
//如果有什么是不符合题意的，我们可以在后面来调整。
}
if(times[left] > t){
left--;
}
return note[left];
}
最长递增子序列
public int lengthOfLIS(int[] nums){
int len = nums.length;
if(len == 1){
return 1;
}
int[] tail = new int[nums.length];
int end = 0;
tail[end] = nums[0];
for(int i = 1;i < nums.length;i++){
if(tail[end] < nums[i]){
tail[++end] = nums[i];
}else{
//在已经存的tail数组里 找到nums[i]可以放的地方
int left = 0;
int right = end;
while(left < right){
int mid = left + (right - left)/2;
if(tail[mid] < nums[i]){
left = mid + 1;
}else{
right = mid ;
}
}
tail[left] = nums[i];
}
}
return ++end;
}
![Java String.format方法的简单使用[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)