leetcode_day1

二分查找

之前用C++刷过不止一遍，所以这次用java重写，没想到遇到了语法问题，尴尬……

• 参数给的int[] nums，跟C的普通数组一样吗？那我怎么得到长度呢？java有sizeof()吗？
• 我第一时间想递归，但是怎么传被分割后的数组呢？

搜索学习一波后了解到，java的int[]类型可以获取长度，具体见下：

java数组语法小记

length属性

• length是数组的一个属性，用于获取数组的长度。
• 这是数组对象的一个公共属性，不是类的成员。

例如：

int[] nums = {1, 2, 3, 4, 5}; 
System.out.println(nums.length); // 输出数组的长度：5

### 其他可用的操作

虽然length是唯一一个直接通过点符号.访问的数组属性，但数组对象还可以通过一些标准的类库方法进行操作。例如：

1. Arrays 类：

   Arrays 类提供了许多静态方法来操作数组，例如排序、搜索、比较、填充等。

   import java.util.Arrays; 
   int[] nums = {3, 1, 4, 1, 5}; 
   Arrays.sort(nums); // 对数组进行排序
   System.out.println(Arrays.toString(nums)); // 将数组转换为字符串并输出：[1, 1, 3, 4, 5]

2. System 类：

   System 类提供了一些方法来进行数组的复制等操作。
   int[] nums = {1, 2, 3, 4, 5}; 
   int[] copy = new int[nums.length];
   System.arraycopy(nums, 0, copy, 0, nums.length); // 复制数组

3. Collections 类（适用于对象数组）： 对于对象数组，可以使用 Collections 类的方法进行排序、搜索等操作，但对于基本类型数组（如 int[]），需要使用 Arrays 类的方法。

数组的其他特性

• 数组是对象：
  在Java中，所有的数组类型都是对象，并且继承自 java.lang.Object 类。

• 多维数组：

  int[][] matrix = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
  System.out.println(matrix.length); // 输出二维数组的行数：3 
  System.out.println(matrix[0].length); // 输出二维数组的第一行的列数：3

  • Java支持多维数组，通过嵌套数组的方式实现。

• 无法改变大小：

  ArrayList<Integer> list = new ArrayList<>(); 
  list.add(1); list.add(2); 
  System.out.println(list.size()); // 输出列表的大小：2

• 数组一旦创建，其大小是固定的。如果需要一个可以动态调整大小的数组，可以使用 ArrayList 或其他集合类。

代码实现（递归版）

至于具体算法细节，仍然是carl所教的左闭右开和左闭右闭

左闭右开

class Solution {
    public int search(int[] nums, int target) {
        return searchHelp(0, nums.length - 1, nums, target);
    }
    public int searchHelp(int begin, int end, int[] nums, int target) {
        if(begin == end) {
            return target == nums[begin] ? begin : -1;
        }
        int mid = (end - begin) / 2 + begin;
        if(target <= nums[mid]) return searchHelp(begin, mid, nums, target);
        else return searchHelp(mid + 1, end, nums, target);
    }
}

左闭右闭

class Solution {
    public int search(int[] nums, int target) {
        return searchHelp(0, nums.length, nums, target);
    }
    public int searchHelp(int begin, int end, int[] nums, int target) {
        if(begin >= end - 1) {
            if(begin > end - 1) return -1;
            else return target == nums[begin] ? begin : -1;
        }
        int mid = (end - begin) / 2 + begin;
        if(target < nums[mid]) return searchHelp(begin, mid, nums, target);
        else return searchHelp(mid , end, nums, target);
    }
}

# 二分拓展——在排序数组中查找元素的第一个和最后一个位置

题目链接

还没做此题时，算法群中有人讨论，瞄到了“二分定位然后发散找边界”的思路，窃以为很有道理，然另一群友diss：“全是一样的就成了\(O(n)\)了”，有道理哈。

自己做的时候的确直觉想到"二分定位然后发散"的思路，但是有意避免，于是想到两次二分分别定左右边界。下附代码，与官方题解区别在于，官方使用了一个lower标志位来区分左右边界，把两次二分合成一个方法。而我的代码直接写了两次，把等号换地方。记得第一次二分后把right弄回去。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int[] ans = new int[]{-1, -1};
        while(left <= right) {
            int mid = (right - left) / 2 + left;
            if(nums[mid] < target) {
                left = mid + 1;
            }
            else if(nums[mid] >= target) {
                right = mid - 1;
            }
        }
        if(left >= nums.length || nums[left] != target) return ans;
        else ans[0] = left;
        right = nums.length - 1;
        while(left <= right) {
            int mid = (right - left) / 2 + left;
            if(nums[mid] <= target) {
                left = mid + 1;
            }
            else if(nums[mid] > target) {
                right = mid - 1;
            }
        }
        ans[1] = right;
        return ans;
    }
    
}

移除元素

此题貌似是力扣新手村的一道题，以前错过多次，感叹于自己的菜，于是这次还记得解法，但仍然没有一把AC，在去重的时候没有考虑好只有一个元素和空表的情况。

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0, right = nums.length - 1;
        if(nums.length == 0) return 0;
        else while(right >= 0 && nums[right] == val) right--;
        while(left < right) {
            while(nums[right] == val && left < right) right--;
            while(nums[left] != val && left < right) left++;
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }

        return right + 1;
    }
}

第一天打卡，希望能够坚持下去，同时笔者还在看dolphinscheduler，看不懂啊……想参加开源之夏，但是好像截止前连项目都看不懂，抓紧时间，加油加油！

(更新：想peach了，没参加成，申请书都没写完，明年一定)

ps 算法群里遇到一个问题，在遍历数组的时候，fast < nums.size()就AC，fast <= nums.size() - 1就RE，原来是因为：

vector的size方法返回的是无符号整数，减一之后不会变-1，而是变大，条件就无效了。

空vector才会碰见的坑，长见识了。

​