今日任务:

数据理论基础

Carl哥主要介绍了一些数据的基础知识和C++中数组的一些操作。那么我来总结一下Java中数组的操作。
参考连接
首先需要注意的是在Java中数组一旦被创建长度就固定了。

数组创建

int[] anArray; //声明一个数组
int[] anArray = new int[10]; //创建一个长度为10的数组
int[] arr = {1, 2, 3};
int[] arr = new int[]{1, 2, 3};

深拷贝与浅拷贝

int[] arr = {1, 2, 3};
int[] arr2 = arr;
arr2[0] = 4;
System.out.println(arr[0]); // 4

int[] arr = {1, 2, 3};
int[] arr2 = Arrays.copyOf(arr, arr.length);
arr2[0] = 4;
System.out.println(arr[0]); // 1

// using System.arraycopy
int[] arr = {1, 2, 3};
int[] arr2 = new int[arr.length];
System.arraycopy(arr, 0, arr2, 0, arr.length);

Arrays类

int[] arr = {1, 2, 3};
System.out.println(Arrays.toString(arr)); // [1, 2, 3]
System.out.println(Arrays.equals(arr, arr2)); // true
System.out.println(Arrays.binarySearch(arr, 2)); // 1
// fill
int[] arr = new int[10];
Arrays.fill(arr, 1);

// sort
int[] arr = {1, 2, 3};
Arrays.sort(arr);

// copyOfRange
int[] arr = {1, 2, 3};
int[] arr2 = Arrays.copyOfRange(arr, 0, 2);
System.out.println(Arrays.toString(arr2)); // [1, 2]

LC-704

第一种方法：左闭右闭区间

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

        return -1;
    }
}

第二种方法：左闭右开区间
还是第一种比较方便好想哈哈。

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

        return -1;
    }
}

LC-27

双向双指针

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

        return left;
    }
}

快慢指针

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            } 
        }

        return slow;
    }
}s

每日一题 LC-1043

遇到好多遍了有点难度

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int[] dp = new int[arr.length + 1];
        for (int i = 1; i < dp.length; i++) {
            int max = arr[i - 1];
            for (int j = i; j >= 0 && j >= i - k; j--) {
                dp[i] = Math.max(dp[i], dp[j] + max * (i - j));
                if (j > 0)
                    max = Math.max(max, arr[j - 1]);
            }
        }

        return dp[arr.length];
    }
}

Sean, the sheep🐑

代码随想录训练营 Day 01 / 60

数据理论基础

LC-704

LC-27

每日一题 LC-1043