小白的悟道
0%

发表于 分类于 Valine：

第一章　序章

关于LeetCode

LeetCode主要是用在面试中，在有限的时间内考验小镇做题家的算法能力

关于作者

万和晧是读研时的舍友，互相监督刷题卷一下嘿嘿

编程语言

万擅长用java, 晧用c++各写一遍

发表于 分类于 Valine：

根据时间复杂度的不同，大致分为3类：

  1. 时间复杂度O(n^2)的排序算法: 冒泡，选择，插入，希尔排序
  2. 时间复杂度O(nlogn)的排序算法: 快速，归并，堆排序
  3. 时间复杂度为线性的排序算法: 计数，桶排序，基数排序

快速排序(Quicksort)

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void quicksort(vector<int> &nums, int l ,int r) {
    if (l + 1 >= r) {
        return;
    }
    int first = l, last = r - 1, key = nums[first];
    while (fisrt < last) {
        while (fist < last && nums[last] >= key) {
            --last;
        }
        nums[first] = nums[last];
        while (fist < last && nums[first] <= key) {
            ++first;
        }
        nums[last] = nums[first];
    }
    nums[first] = key;
    quicksort(nums, l, first);
    quicksort(nums, first + 1, r);
}

java:

1
@houwanwan

发表于 分类于 Valine：

二分查找通常将待查找区间分为两部分并只取一部分继续查找，可以大大减少查找的复杂度。

求开方

  1. Sqrt(x) (Easy)

题目描述

　　给定一个非负整数，求它的开方，向下取整。

输入输出样例

　　输入是一个整数，输出一个整数。

1
2
Input: 8
Output: 2

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int mySqrt(int a) {
    if (a == 0) return 0;
    int l = 1, r = a, mid, sqrt;
    while (l <= r) {
        mid = l + (r - 1) / 2;
        sqrt = a / mid;
        if (sqrt == mid) {
            return mid;
        } else if (mid > sqrt) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return r;
}

java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//注意int强转long的用法
class Solution {
    public int mySqrt(int x) {
        int l = 0;
        int r = x;
        int ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if ((long)mid * mid <= x) {
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}

查找区间

  1. Find First and Last Position of Element in Sorted Array (Medium)

题目描述

　　给定一个增序的整数数组和一个值，查找该值第一次和最后一次出现的位置。

输入输出样例

　　输入是一个数组和一个值，输出为该值第一次出现的位置和最后一次出现的位置(从0开始);如果不存在该值，则两个返回值都设为-1。

1
2
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3, 4]

c++:

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
28
29
30
31
32
33
34
35
vector<int> searchRange(vector<int>& nums, int target) {
    if (nums.empty()) return vector<int>{-1, -1};
    int lower = lower_bound(nums, target);
    int upper = upper_bound(nums, target) - 1;
    if (lower == nums.size() ## nums[lower] != target) {
        retrun vector<int>{-1, -1};
    }
}

int lower_bound(vector<int>& nums, int target) {
    int l = 0, r = nums.size(), mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (nums[mid] >= target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

int upper_bound(vector<int>& nums, int target) {
    int l = 0, r = nums.size(), mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (nums[mid] > target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

java:

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
28
29
30
//拆解为两个二分查找，注意收敛边界
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = binarySearch(nums, target, true);
        int right = binarySearch(nums, target, false);
        return new int[]{left, right};
    }

    public int binarySearch(int[] nums, int target, Boolean leftFlag) {
        int result = -1;
        if (nums.length <= 0) {
            return result;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target && leftFlag && (0 == mid || nums[mid - 1] < nums[mid])) {
                return mid;
            } else if (nums[mid] == target && !leftFlag && (mid == nums.length - 1 || nums[mid + 1] > nums[mid])) {
                return mid;
            } else if ((leftFlag && nums[mid] >= target) || (!leftFlag && nums[mid] > target)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
}

旋转数组查找数字

  1. Search in Rotated Sorted Array (Medium)

题目描述

　　一个原本增序的数组被首尾相连后按某个位置断开（如[1,2,2,3,4,5]->[2,3,4,5,1,2],在第一位和第二位断开），我们称其为旋转数组。给定一个值，判断这个值是否存在于这个为旋转数组中。

输入输出样例

　　输入是一个数组和一个值，输出是一个布尔值，表示数组中是否存在于这个旋转数组中。

1
2
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

c++:

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
bool search(vector<int>& nums, int target) {
    int start = 0, end = nums.size() - 1;
    while (start < end) {
        mid = (start + end) / 2;
        if (nums[mid] == target) {
            return true;
        }
        if (nums[start] == nums[mid]) {
            ++start;
        } else if (nums[mid] <= nums[end]) {
            if (target > nums[mid] && target <= nums[end]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        } else {
            if (target >= nums[start] && target < nums[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
    }
    return flase;
}

java:

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
28
29
30
31
32
33
34
35
//注意区分有序空间
class Solution {
    public boolean search(int[] nums, int target) {
//        nums = [2,5,6,0,0,1,2]
        int left = 0;
        int right = nums.length - 1;
        boolean res = false;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[left] < nums[mid]) { //在前面升区间上
                if (nums[mid] < target) {
                    left = mid + 1;//一定对的，因为它右边的大
                } else if (nums[left] > target) {//左边的最小值的大于它，可能在右边
                    left = mid + 1;
                } else {//否则一定在左边
                    right = mid - 1;
                }
            } else if (nums[left] > nums[mid]) {
//                nums = [2,5,6,0,0,1,2]
                if (nums[mid] > target) { //在后面升区间上
                    right = mid - 1;//一定对的，小的在左边
                } else if (nums[right] < target) {
                    right = mid - 1;//最右边的最大值还没达到最大值，在左边
                } else {
                    left = mid + 1;
                }
            } else {
                left++;
            }
        }
        return res;
    }
}

发表于 更新于 分类于 Valine：

kaka从入门到精通（window版本）—图文详细

kafka在分布式消息中间件中具有举足轻重的地位，能够实时收集大量的数据，下面我们开始详细介绍。

下载kafka

访问网站https://kafka.apache.org/downloads

点击下载 kafka_2.12-3.1.0.tgz这个版本

阅读全文 »

发表于 更新于 分类于 Valine：

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。

Two Sum

  1. Input array is sorted (Easy)

题目描述

　　在一个增序的整数数组里找到两个数，使它们的和为给定值。已知有且只有一对解。

输入输出样例

　　输入是一个数组和一个给定值。输出是两个数的位置，从１开始计数。

1
2
Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]

c++:

1
2
3
4
5
6
7
8
9
vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0, r = numbers.size() - 1, sum;
    while (l < r) {
        sum = numbers[l] + numbers[r];
	if (sum == target) break;
	if (sum < target) ++l;
 	else --r;
    }
    return vector<int>{l + 1, r + 1};

java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] indexs = new int[2];
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            if ((numbers[left] + numbers[right]) == target) {
                indexs[0] = left + 1;
                indexs[1] = right + 1;
                break;
            } else if ((numbers[left] + numbers[right]) > target) {
                right--;
            } else {
                left++;
            }
        }
        return indexs;
    }
}

归并两个有序数组

  1. Merge Sorted Array (Easy)

题目描述

　　给定两个有序数组，把两个合并成一个。

输入输出样例

　　输入是两个数组和他们分别的长度m和n。其中第一个数组的长度被延长至m+n,多出的n位被0填充。题目要求把第二个数组归并到第一个数组上，不需要开辟额外空间。

1
2
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2, 5, 6], n = 3
Output: nums1 = [1,2,2,3,5,6]

c++:

1
2
3
4
5
6
7
8
9
void merge(vector<int>& nums1, vector<int>& nums2, int m, int n) {
    int pos = m-- + n-- - 1;
    while (m >= 0 && n >= 0) {
        nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
    }
    while (n >=0) {
        nums1[pos--] = num2[n--];
    }
}

java:

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 void merge(int[] nums1, int m, int[] nums2, int n) {
        int len = m + n;
        for (int i = len - 1; i >= 0; i--) {
            if (m == 0 && n == 0) {
                return;
            }
            if (n <= 0 && m > 0) {
                nums1[i] = nums1[m - 1];
                m--;
                continue;
            }
            if (m <= 0 & n > 0) {
                nums1[i] = nums2[n - 1];
                n--;
                continue;
            }
            if (nums1[m - 1] > nums2[n - 1]) {
                nums1[i] = nums1[m - 1];
                m--;
            } else {
                nums1[i] = nums2[n - 1];
                n--;
            }
        }
    }
}

快慢指针

  1. Linked List Cycle (Medium)

题目描述

给定一个链表，如果有环路，找出环路的开始点。

输入输出样例

　　输入是一个链表，输出是链表的一个节点，如果没有环路，返回一个空指针。
　　链表数据结构:

1
2
3
4
5
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode *detectCycle(ListNode *head) {
    ListNode *fast = head, *slow = head;
    do {
        if (!fast || !fast->next) return nullptr;
        fast = fast -> next -> next;
	slow = slow -> next;
    } while (fast != slow);

    while (fast != next) {
        fast = fast -> next;
        slow = slow -> slow;
    }
    return fast;
}

java:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * f=2s
 * f=s+nb
 * s=nb
 * f=2nb
 * k=a+nb
 * 简直就是数学题
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        ListNode result = null;
//        第一次相遇
        while (true) {
            slow = slow.next;
            fast = fast.next;
            if (fast == null) {
                return null;
            } else {
                fast = fast.next;
            }
            if (fast == null) {
                return null;
            }
            if (slow == fast) {
                break;
            }
        }
        fast = head;
//        第二次相遇
        while (true) {
            if (slow == fast) {
                return slow;
            }
            slow = slow.next;
            fast = fast.next;
        }
    }
}

滑动窗口

  1. Minimum Window Substring (Hard)

题目描述

给定两个字符串S和T,求S中包含T所有字符的最短连续子字符串的长度, 同时要求时间复杂度不得超过O(n)。

输入输出样例

输入是两个字符串S和T,输出是一个S字符串的子串。

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
28
29
30
31
32
33
34
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

c++:
```c++
string minWindow(string S, string T) {
    //先统计T中的字符情况
    vector<int> chars(128, 0);
    vector<bool> flags(128, false);
    for (auto i : T) {
        ++chars[i];
        flags[i] = true;
    }
    //先确定S是否包含T,再滑动窗口
    int cnt = 0, l = 0, min_l = 0, min_size = S.size() + 1;
    for (auto r : S) {
        if (flags[r]) {
            if (--chars[r] > 0)
                ++cnt;
        //s都包含T后，探索最短字符串
            while (cnt == T.size()) {
                if (r - l + 1 < min_size) {
                    min_l = l;
                    min_size = r - l + 1;
                }
                if (flags[S[l]] && ++chars[S[l]] > 0) {
                    --cnt;
                }
                ++l;
            }
        }            
    }
    return min_size < S.size() ? "" : S.substr(min_l, min_size);
}

java:

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
28
29
30
class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> hs = new HashMap<Character, Integer>();
        HashMap<Character, Integer> ht = new HashMap<Character, Integer>();
        String ans = "";
        for (int i = 0; i < t.length(); i++) {
            ht.put(t.charAt(i), ht.getOrDefault(t.charAt(i), 0) + 1);
        }
        Integer cnt = 0;
        Integer max = Integer.MAX_VALUE;
        for (int i = 0, j = 0; j < s.length(); j++) {
            hs.put(s.charAt(j), hs.getOrDefault(s.charAt(j), 0) + 1);
            if (ht.containsKey(s.charAt(j)) && ht.get(s.charAt(j)) >= hs.get(s.charAt(j))) {
                cnt++;
            }
            while (i < j && (!ht.containsKey(s.charAt(i)) || ht.get(s.charAt(i)) < hs.get(s.charAt(i)))) {
                hs.put(s.charAt(i), hs.get(s.charAt(i)) - 1);
                i++;
            }
            if (cnt == t.length()) {
                Integer cur = j - i + 1;
                if (cur < max) {
                    max = cur;
                    ans = s.substring(i, j + 1);
                }
            }
        }
        return ans;
    }
}

发表于 更新于 分类于 Valine：

springboot集成Swagger（springdoc-openapi-ui版本）—图文详细

对于快速迭代的软件开发，会导致软件文档中的API不能及时更新，不同项目组之间的代码协同问题出现了较大的挑战，因此本文简单实验springboot集成swagger动态生成文档，可以边开发代码边生成文档，由于springfox版本老旧已经不在维护，本文使用springdoc方式集成。

使用IDEA快速搭建springboot项目

如果已经搭建好了springboot项目可以跳过这一步

点击左上角菜单New，选择Project

image-20220425221200143

使用Spring Initializr方式创建springboot项目，选择jdk为本地安装的1.8版本，点击下一步

阅读全文 »

发表于 更新于 分类于 Valine：

ELK搭建开源日志系统（window版本）—图文详细

日志对于排查错误非常重要，使用linux命令awk sed grep find等命令查询日志非常麻烦，而且很难做数据分析，使用免费开源的ELK可以支撑大规模的日志检索，本文将一步步教怎么快速搭建一个window版本的ELK日志收集系统。

下载elasticsearch、logstash、kibana、filebeat

注意同一系列的版本要一样，防止出现版本不兼容问题，本文使用7.16.0版本，在window系统演示

下载elasticsearch

访问地址为：https://www.elastic.co/cn/downloads/past-releases

点击Donload下载

image-20220418221506034

阅读全文 »

发表于 更新于 分类于 Valine：

贪心算法采用贪心的策略，保证每步都是局部最优，最终达到全局最优

分配问题

455.Assign Cookies (Easy)

题目描述

　　有一群孩子和一堆饼干，每个孩子都有一个饥饿度，每个饼干都有一个大小，每个孩子只能吃最多一个饼干，且只有饼干的大小大于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。

输入输出样例

　　输入两个数组，分别代表孩子们的饥饿度和饼干的大小。输出最多有多少孩子可以吃饱的数量。

1
2
Input: [1, 2], [1, 2, 3]
Output: 2　　

c++:

1
2
3
4
5
6
7
8
9
10
int findContentChildren(vector<int>& children, vector<int>& cookies) {
    sort(children.begin(), children.end());
    sort(cookies.begin(), cookies.end());
    int child = 0, cookie = 0;
    while (child < children.size() && cookie < cookies.size()) {
        if (children[child] <= cookies[cookie]) ++child;
        ++cookie;
    }
    return child;
}

java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        int max = 0;
        Arrays.sort(g);
        Arrays.sort(s);
        for (int i = 0, j = 0; i < s.length & j < g.length; i++) {
            if (g[j] <= s[i]) {
                max++;
                j++;
            }
        }
        return max;
    }
}
阅读全文 »

发表于 更新于 分类于 Valine：

IDEA调试spring框架源码—图文详细

spring源码是java学习的核心，如果我们想要修改源码，例如加一些注释什么的，需要会编译源码，因此本文一步步教大家如何编译spring框架源码。

下载spring框架源码到本地

发表于 更新于 分类于 Valine：

ubuntu1604使用Clion调试openjdk8

  作为java开发工程师，大家都知道源码中有很多naive方法，这些方法看不到源码，底层jdk源码使用c语言编写。Oracle Jdk是闭源的看不到源码，OpenJdk是Oracle Jdk的开源版本，据说，两者代码基本一致。因此本篇博客给大家介绍如何使用clion编译器调试openjdk源码。

  整个过程还是遇到了各种各样的困难，为了使广大读者少走弯路，将编译通过的经验总结在这个帖子，希望大家多多指教。

  为了能够更好的复现结果，防止因环境或者其他原因导致编译失败，先请大家一步一步跟着我的步骤执行。

所需软件（可以自行在官网下载）

链接：https://pan.baidu.com/s/1ppPLww7cp32vCdFvchbTEg

提取码：35hc

安装虚机

1
2
对于window环境的读者可以安装虚拟，在虚机的环境下安装ubuntu1604系统。如果已经是ubuntu1604系统则忽
略此步骤。此步骤比较简单，请使用百度等搜索引擎自行安装。
阅读全文 »