陣列：記憶體空間連續，資料型別統一，下標從0開始
二分查找
704
class Solution {
public int search(int[] nums, int target) {
// 方法一：暴力解法
// for(int i = 0; i < nums.length; i++){
// if(nums[i] == target){//找到目標值
// return i;
// }
// }
// return -1;
// 方法二：二分查找（元素有序且無重復元素），使用迭代，執行速度快，但是記憶體消耗大
// return binarySearch(nums, target, 0, nums.length-1);
// 方法三：二分查找，參考代碼隨想錄的左閉右閉區間
// 上來先處理邊界條件
if(target < nums[0] || target > nums[nums.length - 1]){
return -1;
}
int left = 0;
int right = nums.length - 1;//右閉區間
int mid = (left + right) >> 1;
while(left <= right){//因為取得陣列區間左右都是閉的，所以取等號的時候也能滿足條件，還不需要退出回圈
if(target == nums[mid]){
return mid;
}else if(target < nums[mid]){
right = mid -1;//往左區間縮
}else{
left = mid +1;
}
mid = (left + right) >> 1;
}
return -1;
}
// public int binarySearch(int[] nums, int target, int start, int end){
// int mid = (start+end)/2;
// int find = -1;
// if(start > end){//沒有找到
// return -1;
// }
// if(target == nums[mid]){
// return mid;
// }else if(target < nums[mid]){
// find = binarySearch(nums, target, start, mid-1);
// }else{
// find = binarySearch(nums, target, mid+1, end);
// }
// return find;
// }
}
69、x的平方根
class Solution {
public int mySqrt(int x) {
// 使用二分查找
int left = 0;
int right = x;
int ans = -1;
while(left <= right){
int mid = (left + right) >> 1;
if((long)mid*mid <= x){
ans = mid;
left = mid + 1;
}else{
right = mid - 1;
}
}
return ans;
}
}
367、有效的完全平方數
class Solution {
public boolean isPerfectSquare(int num) {
int left = 0, right = num;
while(left <= right){
int mid = (left + right) >> 1;
if((long) mid * mid == num){
return true;
}else if((long) mid * mid < num){
left = mid + 1;
}else{
right = mid - 1;
}
}
return false;
}
}
移除元素
27
class Solution {
public int removeElement(int[] nums, int val) {
// 原地移除，所有元素
// 陣列內元素可以亂序
// 方法一：暴力解法，不推薦，時間復雜度O(n^2)
// int right = nums.length;//目標陣列長度，右指標
// for(int i = 0; i < right; i++){
// if(val == nums[i]){
// right--;//找到目標數值，目標數長度減一，右指標左移
// for(int j = i; j < right; j++){
// nums[j] = nums[j + 1];//陣列整體左移一位（陣列元素不能洗掉，只能覆寫）
// }
// i--;//左指標左移
// }
// }
// return right;
// 方法二：快慢指標，時間復雜度O(n)
// int solwPoint = 0;
// for(int fastPoint = 0; fastPoint < nums.length; fastPoint++){
// if(nums[fastPoint] != val){
// nums[solwPoint] = nums[fastPoint];
// solwPoint++;
// }
// }
// return solwPoint;
// 方法三：注意元素的順序可以改變，使用相向指標，時間復雜度O(n)
int rightPoint = nums.length - 1;
int leftPoint = 0;
while(rightPoint >= 0 && nums[rightPoint] == val){
rightPoint--;
}
while(leftPoint <= rightPoint){
if(nums[leftPoint] == val){
nums[leftPoint] = nums[rightPoint--];
}
leftPoint++;
while(rightPoint >= 0 && nums[rightPoint] == val){
rightPoint--;
}
}
return leftPoint;
}
}
26、洗掉排序陣列中的重復項
class Solution {
public int removeDuplicates(int[] nums) {
// 相對順序一致，所以不能使用相向指標，
// 考慮使用快慢指標
if(nums.length == 1){
return 1;
}
int slowPoint = 0;
for(int fastPoint = 1; fastPoint < nums.length; fastPoint++){
if(nums[slowPoint] != nums[fastPoint]){
nums[++slowPoint] = nums[fastPoint];
}
}
return slowPoint + 1;
}
}
283、移動零
class Solution {
public void moveZeroes(int[] nums) {
// 要保持相對順序，不能用相向指標
int slowPoint = 0;
for(int fastPoint = 0; fastPoint < nums.length; fastPoint++){
if(nums[fastPoint] != 0){
nums[slowPoint++] = nums[fastPoint];//所有非零元素移到左邊
}
}
for(; slowPoint < nums.length; slowPoint++){
nums[slowPoint] = 0;//把陣列末尾置零
}
}
}
844、比較含退格的字串
class Solution {
public boolean backspaceCompare(String s, String t) {
// 從前往后的話不確定下一位是不是"#"，當前位需不需要消除，所以采用從后往前的方式
int countS = 0;//記錄s中"#"的數量
int countT = 0;//記錄t中"#"的數量
int rightS = s.length() - 1;
int rightT = t.length() - 1;
while(true){
while(rightS >= 0){
if(s.charAt(rightS) == '#'){
countS++;
}else{
if(countS > 0){
countS--;
}else{
break;
}
}
rightS--;
}
while(rightT >= 0){
if(t.charAt(rightT) == '#'){
countT++;
}else{
if(countT > 0){
countT--;
}else{
break;
}
}
rightT--;
}
if(rightT < 0 || rightS < 0){
break;
}
if(s.charAt(rightS) != t.charAt(rightT)){
return false;
}
rightS--;
rightT--;
}
if(rightS == -1 && rightT == -1){
return true;
}
return false;
}
}
有序陣列的平方
977
class Solution {
public int[] sortedSquares(int[] nums) {
// 用相向的雙指標
int[] arr = new int[nums.length];
int index = arr.length - 1;
int leftPoint = 0;
int rightPoint = nums.length - 1;
while(leftPoint <= rightPoint){
if(Math.pow(nums[leftPoint], 2) > Math.pow(nums[rightPoint], 2)){
arr[index--] = (int)Math.pow(nums[leftPoint], 2);
leftPoint++;
}else{
arr[index--] = (int)Math.pow(nums[rightPoint], 2);
rightPoint--;
}
}
return arr;
}
}
長度最小的子陣列
209
class Solution {
public int minSubArrayLen(int target, int[] nums) {
// 注意是連續子陣列
// 使用滑動視窗，實際上還是雙指標
int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
for(int right = 0; right < nums.length; right++){
sum += nums[right];
while(sum >= target){
result = Math.min(result, right - left + 1);
sum -= nums[left++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
904、水果成籃
class Solution {
public int totalFruit(int[] fruits) {
// 此題也可以使用滑動視窗
int maxNumber = 0;
int left = 0;
Map<Integer, Integer> map = new HashMap<>();//用哈希表記錄被使用的籃子數量，以及每個籃子中的水果數量
for(int right = 0; right < fruits.length; right++){
map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);//往籃子里面放水果
while(map.size() > 2){//放進去的水果不符合水果型別
map.put(fruits[left], map.get(fruits[left]) - 1);
if(map.get(fruits[left]) == 0){
map.remove(fruits[left]);
}
left++;
}
maxNumber = Math.max(maxNumber, right - left + 1);
}
return maxNumber;
}
}
螺旋矩陣 II
59
class Solution {
public int[][] generateMatrix(int n) {
// 方法一：直接按序輸出
int[][] arr = new int[n][n];
int top = 0;
int buttom = n - 1;
int left = 0;
int right = n - 1;;
int index = 1;
while(left <= right && top <= buttom && index <= n*n){
for(int i = left; i <= right; i++){
arr[top][i] = index++;
}
top++;
for(int i = top; i <= buttom; i++){
arr[i][right] = index++;
}
right--;
for(int i = right; i >= left; i--){
arr[buttom][i] = index++;
}
buttom--;
for(int i = buttom; i >= top; i--){
arr[i][left] = index++;
}
left++;
}
return arr;
}
}
54
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int top = 0;
int buttom = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
List<Integer> list = new ArrayList<Integer>();
while(left <= right && top <= buttom){
for(int i = left; i <= right; i++){
if(top <= buttom)
list.add(matrix[top][i]);
}
top++;
for(int i = top; i <= buttom; i++){
if(left <= right)
list.add(matrix[i][right]);
}
right--;
for(int i = right; i >= left; i--){
if(top <= buttom)
list.add(matrix[buttom][i]);
}
buttom--;
for(int i = buttom; i >= top; i--){
if(left <= right)
list.add(matrix[i][left]);
}
left++;
}
return list;
}
}
29 、順時針列印矩陣
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix.length == 0){
return new int[0];
}
int top = 0;
int buttom = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
int[] arr = new int[matrix.length*matrix[0].length];
int index = 0;
while(left <= right && top <= buttom){
for(int i = left; i <= right; i++){
if(top <= buttom)
arr[index++] = matrix[top][i];
}
top++;
for(int i = top; i <= buttom; i++){
if(left <= right)
arr[index++] = matrix[i][right];
}
right--;
for(int i = right; i >= left; i--){
if(top <= buttom)
arr[index++] = matrix[buttom][i];
}
buttom--;
for(int i = buttom; i >= top; i--){
if(left <= right)
arr[index++] = matrix[i][left];
}
left++;
}
return arr;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/525860.html
標籤：Java
下一篇：學習筆記——處理請求與回應的介面（HttpServletRequest、HttpServletResponse）