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=)