Sean, the sheep🐑
0%

Posted on Views:

今日任务

  • [] 每日一题（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 使数组严格递增

题目链接

Posted on Views:

今日任务:

数据理论基础

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];
    }
}

Posted on Views:

The Bad design

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

Posted on In Views:

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

Read more »