1.搜索插入位置
https://leetcode-cn.com/problems/search-insert-position/
class Solution {
public int searchInsert(int[] nums, int target) {
int left=0,right=nums.length-1;
while(left<=right){
int mid=(left+right)/2;
if(nums[mid]<target){
left=mid+1;
}else if(nums[mid]>target){
right=mid-1;
}else{
return mid;
}
}
return left;
}
}
2.搜索二維矩陣
https://leetcode-cn.com/problems/search-a-2d-matrix/
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0)
return false;
int row = 0, col = matrix[0].length-1;
while(row < matrix.length && col >= 0){
if(matrix[row][col] < target)
row++;
else if(matrix[row][col] > target)
col--;
else
return true;
}
return false;
}
3.洗掉排序陣列重復項
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
public int removeDuplicates(int[] nums) {
// 使用雙指標
if(nums==null || nums.length == 1){
return nums.length;
}
int i = 0,j =1;
while(j<nums.length){
if(nums[i]==nums[j]){
j++;
}else{
i++;
nums[i]=nums[j];
j++;
}
}
return i+1;
}
4.鏈表的中間節點
https://leetcode-cn.com/problems/middle-of-the-linked-list/
public ListNode middleNode(ListNode head) {
ListNode p = head, q = head;
while (q != null && q.next != null) {
q = q.next.next;
p = p.next;
}
return p;
}
5.愛生氣的書店老板
https://leetcode-cn.com/problems/grumpy-bookstore-owner/
/*
首先 找到不改變的時候客人就滿意的數量和 同時更新陣列
這樣問題就轉變為 求陣列指定長度最大和的問題
時間復雜度 O(n) 空間復雜度為O（1）
*/
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int x) {
int sum = 0, len = customers.length;
for (int i = 0; i < len; i++) {
if (grumpy[i] == 0){
sum += customers[i];
customers[i] = 0;
}
}
int num = customers[0];
int maxval = customers[0];
for (int i = 1; i < len; i++){
if (i < x) num = num + customers[i];
else num = num + customers[i] - customers[i - x];
maxval = Math.max(maxval, num);
}
return (sum + maxval);
}
}
6.滑動視窗最大值
https://leetcode-cn.com/problems/sliding-window-maximum/
/*
思路： 遍歷陣列 L R 為滑窗左右邊界 只增不減
雙向佇列保存當前視窗中最大的值的陣列下標 雙向佇列中的數從大到小排序，
新進來的數如果大于等于佇列中的數 則將這些數彈出 再添加
當R-L+1=k 時 滑窗大小確定 每次R前進一步L也前進一步 保證此時滑窗中最大值的
陣列下標在[L，R]中，并將當前最大值記錄
舉例： nums[1，3，-1，-3，5，3，6，7] k=3
1：L=0，R=0，佇列【0】 R-L+1 < k
佇列代表值【1】
2: L=0,R=1, 佇列【1】 R-L+1 < k
佇列代表值【3】
解釋：當前數為3 佇列中的數為【1】 要保證佇列中的數從大到小 彈出1 加入3
但佇列中保存的是值對應的陣列下標 所以佇列為【1】 視窗長度為2 不添加記錄
3: L=0,R=2, 佇列【1，2】 R-L+1 = k ,result={3}
佇列代表值【3，-1】
解釋：當前數為-1 佇列中的數為【3】 比佇列尾值小 直接加入 佇列為【3，-1】
視窗長度為3 添加記錄記錄為隊首元素對應的值 result[0]=3
4: L=1,R=3, 佇列【1，2，3】 R-L+1 = k ,result={3，3}
佇列代表值【3，-1,-3】
解釋：當前數為-3 佇列中的數為【3，-1】 比佇列尾值小 直接加入 佇列為【3，-1，-3】
視窗長度為4 要保證視窗大小為3 L+1=1 此時隊首元素下標為1 沒有失效
添加記錄記錄為隊首元素對應的值 result[1]=3
5: L=2,R=4, 佇列【4】 R-L+1 = k ,result={3，3，5}
佇列代表值【5】
解釋：當前數為5 佇列中的數為【3，-1，-3】 保證從大到小 依次彈出添加 佇列為【5】
視窗長度為4 要保證視窗大小為3 L+1=2 此時隊首元素下標為4 沒有失效
添加記錄記錄為隊首元素對應的值 result[2]=5
依次類推 如果隊首元素小于L說明此時值失效 需要彈出
*/
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums==null||nums.length<2) return nums;
// 雙向佇列 保存當前視窗最大值的陣列位置 保證佇列中陣列位置的數按從大到小排序
LinkedList<Integer> list = new LinkedList();
// 結果陣列
int[] result = new int[nums.length-k+1];
for(int i=0;i<nums.length;i++){
// 保證從大到小 如果前面數小 彈出
while(!list.isEmpty()&&nums[list.peekLast()]<=nums[i]){
list.pollLast();
}
// 添加當前值對應的陣列下標
list.addLast(i);
// 初始化視窗 等到視窗長度為k時 下次移動在洗掉過期數值
if(list.peek()<=i-k){
list.poll();
}
// 視窗長度為k時 再保存當前視窗中最大值
if(i-k+1>=0){
result[i-k+1] = nums[list.peek()];
}
}
return result;
}
}
吳邪，小三爺，混跡于后臺，大資料，人工智能領域的小菜鳥，
更多請關注
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/250084.html
標籤：其他
上一篇：演算法 - 鏈表操作題目套路