977. 有序陣列的平方
給你一個按 非遞減順序 排序的整數陣列 nums，回傳 每個數字的平方 組成的新陣列，要求也按 非遞減順序 排序，
示例 1：
輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方后，陣列變為 [16,1,0,9,100]
排序后，陣列變為 [0,1,9,16,100]
示例 2：
輸入：nums = [-7,-3,2,3,11]
輸出：[4,9,9,49,121]
提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104nums已按 非遞減順序 排序
class Solution {
public int[] sortedSquares(int[] nums) {
int length=nums.length-1;
int[] arr=new int[length+1];
int left=0;
int right=length;
while(left<=right){
if(nums[left]*nums[left]<nums[right]*nums[right]){
arr[length--]=nums[right]*nums[right];
right--;
}else{
arr[length--]=nums[left]*nums[left];
left++;
}
}
return arr;
}
}
反思
這道題思路不難，但是要注意的是陣列邊界的問題，
設定的新陣列的長度應該跟原陣列的一樣長，那么接下來就是雙指標的用法，這題需要注意的就是要以非遞減，那么我們應該留意陣列中是否有負數，如果有負數，應該怎么辦，
最主要需要判斷的是負數的平方和正數的平方哪個大，這樣才好排序，設定兩個指標，一個指向原陣列的頭，一個指向尾，比較頭尾兩個數平方的大小，大的先插入新陣列的尾部，（如果是尾部的大，那么指標左移，如果是頭部的大，那么指標右移），時間復雜度是O(n)
189. 輪轉陣列
給你一個陣列，將陣列中的元素向右輪轉 k 個位置，其中 k 是非負數，
示例 1:
輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右輪轉 1 步: [7,1,2,3,4,5,6]
向右輪轉 2 步: [6,7,1,2,3,4,5]
向右輪轉 3 步: [5,6,7,1,2,3,4]
示例 2:
輸入：nums = [-1,-100,3,99], k = 2
輸出：[3,99,-1,-100]
解釋:
向右輪轉 1 步: [99,-1,-100,3]
向右輪轉 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 10 <= k <= 105
思路
將需要移動的k長度陣列直接拷貝到臨時陣列里，再在原陣列的基礎上，先把length-k個數往后移動k個位置，再從臨時陣列把數賦到原陣列的前k個位置
class Solution {
public void rotate(int[] nums, int k) {
k=k%nums.length;
if(k==0){
return;
}
int[] arr=Arrays.copyOfRange(nums,nums.length-k,nums.length);
for(int i=nums.length-1;i>=k;i--){
nums[i]=nums[i-k];
}
for(int i=0;i<k;i++){
nums[i]=arr[i];
}
}
}
反思
該題思路應該是沒問題，但是要在代碼實作上踩坑，
在變化原陣列時要考慮陣列的長度問題，k位置的數要不要包含，
其他的佇列等方法可以之后再進行解決
283. 移動零
給定一個陣列 nums，撰寫一個函式將所有 0 移動到陣列的末尾，同時保持非零元素的相對順序，
請注意 ，必須在不復制陣列的情況下原地對陣列進行操作，
示例 1:
輸入: nums = [0,1,0,3,12]
輸出: [1,3,12,0,0]
示例 2:
輸入: nums = [0]
輸出: [0]
提示:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
思路
快慢指標：快指標用來處理資料，慢指標用來標記處理好的資料，快指標不斷右移，快指標不為0的數賦值給慢指標處，處理完之后將慢指標后面的數值賦0
class Solution {
public void moveZeroes(int[] nums) {
int slow=0;
for(int fast=0;fast<=nums.length-1;fast++){
if(nums[fast]!=0){
nums[slow]=nums[fast];
slow++;
}
}
for(int j=slow;j<=nums.length-1;j++){
nums[j]=0;
}
}
}
反思
關于邊界問題
注意陣列的最后一個數也要遍歷到
167. 兩數之和 II - 輸入有序陣列
給你一個下標從 1 開始的整數陣列 numbers ，該陣列已按 非遞減順序排列 ，請你從陣列中找出滿足相加之和等于目標數 target 的兩個數，如果設這兩個數分別是 numbers[index1] 和 numbers[index2] ，則 1 <= index1 < index2 <= numbers.length ，
以長度為 2 的整數陣列 [index1, index2] 的形式回傳這兩個整數的下標 index1 和 index2，
你可以假設每個輸入 只對應唯一的答案 ，而且你 不可以 重復使用相同的元素，
你所設計的解決方案必須只使用常量級的額外空間，
示例 1：
輸入：numbers = [2,7,11,15], target = 9
輸出：[1,2]
解釋：2 與 7 之和等于目標數 9 ，因此 index1 = 1, index2 = 2 ，回傳 [1, 2] ，
示例 2：
輸入：numbers = [2,3,4], target = 6
輸出：[1,3]
解釋：2 與 4 之和等于目標數 6 ，因此 index1 = 1, index2 = 3 ，回傳 [1, 3] ，
示例 3：
輸入：numbers = [-1,0], target = -1
輸出：[1,2]
解釋：-1 與 0 之和等于目標數 -1 ，因此 index1 = 1, index2 = 2 ，回傳 [1, 2] ，
提示：
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers按 非遞減順序 排列-1000 <= target <= 1000- 僅存在一個有效答案
思路
雙指標的用法，題中給的非遞減可以作為參考，如果左右相加大于目標值，右指標左移，如果小于目標值，左指標右移；
最后取下標時一定要記得+1
class Solution {
public int[] twoSum(int[] numbers, int target) {
int l=0;
int r=numbers.length-1;
int[] arr=new int[2];
while(l<=r){
if(numbers[l]+numbers[r]<target){
l++;
}else if(numbers[l]+numbers[r]>target){
r--;
}else{
arr[0]=l+1;
arr[1]=r+1;
return arr;
}
}
return null;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/539170.html
標籤：其他