数组：内存空间连续，数据类型统一，下标从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;
// }
}
69x 的平方根
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;
}
}