0%

今日任务

  • [] 每日一题(LC-1187)
  • [] LC-977 有序数组的平方
  • [] LC-209 长度最小的子数组
  • [] LC-59 螺旋数组II

每日一题LC-1187

LC-300

做每日一题前先做了一道LC-300, 因为LC-1187的题解说这道题可以用300的方法。
这道题DP不是最优解要n^2的时间复杂度,主要思想是DP记录以i元素结尾最长的严格递增子序列长度,这样遍历每个元素如果比之前的大就比较一下+1后和之前是不是最大的。最近很多这种题目啊,DP是检查以i为结尾的xxxx,可以整理一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int maxVal = dp[0];
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j <= i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxVal = Math.max(dp[i], maxVal);
}

return maxVal;
}
}

贪心做法,使用了O(n)的查找方式,如果用二分的话可以更加快
主要思路就是让ans数组中尽可能小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0)
return 0;

int[] ans = new int[nums.length + 1]; // 每个元素表示子序列长度为i时子序列中元素的最小值
int len = 1;
ans[1] = nums[0];

for (int i = 1; i < nums.length; i++) {
if (nums[i] > ans[len]) {
ans[++len] = nums[i];
} else {
int index = 0;
for (int j = len; j > 0; j--) {
if (ans[j] < nums[i]) {
index = j;
break;
}
}
ans[index + 1] = nums[i];
}
}

return len;
}
}

LC-1187 使数组严格递增

题目链接

今日任务:

数据理论基础

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

  1. 数组创建

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    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);
  3. Arrays类

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

双向双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
}
}

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
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

遇到好多遍了有点难度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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];
}
}

The Bad design

HUAWEI Matebook X Pro has a very bad camera design, please look my following poster.

新博客再次开张,最后还是选择了最为轻量级以及省心的hexo与github pages这套你几乎不需要任何东西的组合。

Read more »