哺乳类的博客


  • 首页

  • 标签

  • 归档

ARTS打卡:第二十四周

发表于 2019-10-21 | 分类于 ARTS

ARTS打卡:第二十四周

每周完成一个ARTS:

  1. Algorithm:每周至少做一个 leetcode 的算法题
  2. Review:阅读并点评至少一篇英文技术文章
  3. Tip:学习至少一个技术技巧
  4. Share:分享一篇有观点和思考的技术文章

Algorithm

Review

Tip

Share

本周分享知秋大大带来的:Spring Reactor 全新解读系列 2019-2020 全集 (更新中)

ARTS打卡:第二十三周

发表于 2019-10-21 | 分类于 ARTS

ARTS打卡:第二十三周

每周完成一个ARTS:

  1. Algorithm:每周至少做一个 leetcode 的算法题
  2. Review:阅读并点评至少一篇英文技术文章
  3. Tip:学习至少一个技术技巧
  4. Share:分享一篇有观点和思考的技术文章

Algorithm

15. 3Sum(Medium)

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

1
2
3
4
5
6
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

链接: https://leetcode.com/problems/3sum/

解题思路

  1. 暴力破解:使用三重遍历来做,最后需注意结果集的去重,时间复杂度为O(n³),这种解法我就不写出来了
  2. 数组排序 + 双指针
    • 先将数组进行排序
    • 选数组最左的值作为 c,由于要符合 a+b+c=0,所以 c 值必须小于0
    • 使用首尾指针,分别指代a和b,首尾指针双向移动,找出符合公式a+b=-c的 a、b值

代码实现

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
44
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 边界条件
if(nums == null || nums.length < 3){
return null;
}
// 数组排序
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for(int i = 0; i < nums.length - 2; i++) {
// 因为数组是有序的,所以 nums[i] 是最小值,如果 nums[i] > 0,则无解,不符合 a+b+c = 0,c = nums[i]
if(nums[i] > 0) {
break;
}
// i == 0 || nums[i] != nums[i -1] 目的是防重
if(i == 0 || nums[i] != nums[i -1]){
// 选择数组最左的值作为 c,即 -c = sum = a + b,定义首尾指针
int sum = 0 - nums[i], first = i + 1, tail = nums.length - 1;
while(first < tail) {
// a + b = -c
if(nums[first] + nums[tail] == sum){
result.add(Arrays.asLsit(nums[i], nums[first], nums[tail]));
// 去重
while(first < tail && nums[first] == nums[first+1]){
++first;
}
while(first < tail && nums[tail] == nums[tail-1]){
--tail;
}
++first;
--tail;
} else if (nums[tail] + nums[tail] < sum){
// a + b < -c 则需移动首指针
++first;
} else {
// a + b > -c 则需移动尾指针
--tail;
}
}
}
}
return result;
}
}

ps:LeetCode的这道题是有问题的,题目中强调:答案中不可以包含重复的三元组,但是加入三元组的判重条件,又会导致通过不了(:зゝ∠),所谓的不可以包含重复的三元组,就是不能 [0,0,0],所以下面的答案是没有三元组的判重条件的

结果:

Runtime: 25 ms, faster than 98.84% of Java online submissions for 3Sum.

Memory Usage: 45.5 MB, less than 96.47% of Java online submissions for 3Sum.

复杂度:

时间复杂度:O(n²)

空间复杂度:O(1)

Review

本周阅读:

《 Disruptor: High performance alternative to bounded queues for exchanging data between concurrent threads 》,通过阅读这篇技术论文,我们就能知道 Disruptor 它试图解决什么问题,并能了解 Disruptor 这个并发框架为什么那么快的原因。

扩展阅读:

《Dissecting the Disruptor: What’s so special about a ring buffer?》

《Dissecting the Disruptor: How do I read from the ring buffer?》

Tip

这次分享如何在Linux下进行抓包,在Windows下进行抓包,可以点击查看这篇文章:《Wireshark使用详解以及HTTP抓包》。

在Linux下抓包,可以采用 tcpdump

安装命令:yum install tcpdump

简单分享几个命令:

  1. 监控指定网卡上的所有数据

    1
    $ tcpdump -i eth0
  2. 查看指定IP上的进出流量

    1
    $ tcpdump host x.x.x.x
  3. 根据来源和目标进行筛选,

    1
    2
    3
    $ tcpdump src x.x.x.x 
    $ tcpdump dst x.x.x.x
    ps: src = source, dst=destination
  1. 将捕获的数据包保存至文件或读取数据包文件。

    1
    2
    3
    4
    # 使用 -w 保存至文件
    $ tcpdump port 80 -w capture_file
    # 使用 -r 读取文件
    $ tcpdump -r capture_file

想要了解更多内容,小伙伴们可以点击查看:《A tcpdump Tutorial with Examples — 50 Ways to Isolate Traffic》,不想看英文的小伙伴可以点击查看这篇译文:[译]tcpdump 示例教程。

Share

本周继续分享 simviso 团队译制的《斯坦福编译原理》系列视频,这周已更新至25集,感兴趣的小伙伴们,赶紧追起来呀,合集地址:【国外精选视频课】斯坦福编译原理(中文翻译) 合集 更新中。

ARTS打卡:第二十二周

发表于 2019-10-07 | 分类于 ARTS

ARTS打卡:第二十二周

每周完成一个ARTS:

  1. Algorithm:每周至少做一个 leetcode 的算法题
  2. Review:阅读并点评至少一篇英文技术文章
  3. Tip:学习至少一个技术技巧
  4. Share:分享一篇有观点和思考的技术文章

Algorithm

19. Remove Nth Node From End of List(Medium)

问题描述

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

1
2
3
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

链接:https://leetcode.com/problems/remove-nth-node-from-end-of-list/

解题思路

普通思路:

  1. 先遍历计算出这个链表的节点数 count

  2. 因为 n 是指链表的倒数第 n 个节点,所以链表的第 (count - n + 1)个节点就是我们要删除的节点

进阶思路:

采用快慢指针的思想,只需使用一趟扫描实现:

  1. 为了方便理解以及写代码,我们先虚设一个节点,作为起始节点,它的后继节点指向头结点。
  2. 使用两个指针,一个是慢指针 slow,指向起始节点,一个是快指针,指向慢指针 slow 前 n + 1 个节点
  3. 同时移动两个指针,在移动过程中,保持两指针之间间隔 n 个节点,直至快指针 fast 移至 尾部节点的后继节点处。
  4. 这时慢指针 slow 指向的是目标节点的前驱节点,紧接着只需将慢指针指向的节点的后继节点指向目前节点的后继节点即可。

代码实现

  1. 普通版实现:

    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
    class ListNode {
    int val;
    ListNode node;
    public ListNode(int val) {
    this.val = val;
    }
    }

    class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
    // 限制条件
    if (head == null || n <=0) {
    return head;
    }
    int count = 1;
    ListNode tmpNode = head;
    // 遍历链表
    while (tmpNode.next != null) {
    // 计算节点个数
    ++count;
    tmpNode = tmpNode.next;
    }
    tmpNode = head;
    int preTargetIndex = count - n;
    // 当 preTargetIndex == 0 时,即要删除头结点
    if (preTargetIndex == 0) {
    return tmpNode.next;
    }
    // 找到要删除的目标节点的上一个节点
    while (preTargetIndex > 1) {
    --preTargetIndex;
    tmpNode = tmpNode.next;
    }
    // 移除目标节点
    tmpNode.next = tmpNode.next.next;
    return head;
    }
    }

    结果:

    Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Nth Node From End of List.

    Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Remove Nth Node From End of List.

    复杂度:

    时间复杂度:O(n)

    空间复杂度:O(1)

  2. 进阶版:

    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
    class ListNode {
    int val;
    ListNode node;
    public ListNode(int val) {
    this.val = val;
    }
    }

    class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
    // 边界条件
    if (head == null || n <= 0) {
    return head;
    }
    // 虚设一个起始节点(哨兵节点),为了方便删除头结点的情况
    ListNode start = new ListNode(0);
    start.next = head;
    // 慢指针指向起始节点
    ListNode slow = start;
    ListNode fast = start;
    // 快指针指向慢指针的前 n 个节点
    for (int i = 0; i < n + 1; i++) {
    fast = fast.next;
    }
    // 遍历链表直至快指针 fast 移至尾部节点的后继节点处
    while (fast != null) {
    fast = fast.next;
    slow = slow.next;
    }
    // 删除节点
    slow.next = slow.next.next;
    return start.next;
    }
    }

    结果:

    Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Nth Node From End of List.

    Memory Usage: 34.6 MB, less than 100.00% of Java online submissions for Remove Nth Node From End of List.

    复杂度:

    时间复杂度:O(n)

    空间复杂度:O(1)

Review

本周回看了之前分享的几篇有关于 I/O 模型的文章:

  1. 《UNIX® Network Programming Volume 1, Third Edition: The Sockets Networking 》中的 6.2 I/O Models。

  2. Thousands of Threads and Blocking l/O:The Old Way to Write Java Servers Is New Again(and Way Better)

  3. Scalable IO in Java

  4. Boost application performance using asynchronous I/O

Tip

本周分享一个学习数据结构和算法的小技巧:通过 VisuAlgo 网站,可以看到动态可视化的数据结构和算法,结合动图,我们能更容易理解数据结构和算法的实现过程。

Share

最近的都在追 simviso 团队译制的《斯坦福编译原理》系列视频,哇哈哈哈,感兴趣的小伙伴们赶紧跟上鸭( ̄▽ ̄)”

【斯坦福编译原理】06 Cool语言概述 3

【斯坦福编译原理】07 词法分析 1

【斯坦福编译原理】08 词法分析 2

【斯坦福编译原理】09 词法分析 3 正则语言

【斯坦福编译原理】10 词法分析 4 Formal Language

ARTS打卡:第二十一周

发表于 2019-09-28 | 分类于 ARTS

ARTS打卡:第二十一周

每周完成一个ARTS:

  1. Algorithm:每周至少做一个 leetcode 的算法题
  2. Review:阅读并点评至少一篇英文技术文章
  3. Tip:学习至少一个技术技巧
  4. Share:分享一篇有观点和思考的技术文章

Algorithm

14. Longest Common Prefix(Easy)

问题描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

示例 1:

1
2
输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

1
2
3
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。
链接:https://leetcode.com/problems/longest-common-prefix/

解题思路

这个题的目的是找出所给数据组中的最长公共前缀,那我们可以在数组内任选一个字符串,拿它的所有前缀子串分别去匹配剩余的字符串的前缀,最后找出能够匹配所有剩余字符串的最长前缀子串即可。

代码实现

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
class Solution {
/**
*
* @param strs 输入的字符串数组
* @return
*/
public String longestCommonPrefix(String[] strs){
// 边界条件
if(strs == null || strs.length == 0){
return "";
}
// 任选一个字符串,我们这里选择第一个字符串,从最长的前缀子串开始(即字符串本身)
String s0 = strs[0];
// 遍历剩余的字符串,拿所选字符串的所有前缀子串去匹配
for(int i = 1; i < strs.length; i++){
// 当 strs[i].indexOf(s0) = 0,存在两种情况
// 1. 当前的 s0 能匹配 str[i]的前缀,所以终止循环,继续匹配下一个字符串
// 2. 当前的 s0 = "", String.indexOf("") = 0,证明所选字符串的所有前缀子串都不能匹配字符串 str[i] 的前缀,所以终止循环
while(strs[i].indexOf(s0) != 0){
// 当前 s0 不能匹配 strs[i]的前缀,拿次长的前缀子串去匹配
s0 = strs[0].subString(0, s0.length() - 1);
}
}
return s0;
}
}

执行结果:

Runtime: 0 ms, faster than 100.00% of Java online submissions for Longest Common Prefix.

Memory Usage: 37.5 MB, less than 87.13% of Java online submissions for Longest Common Prefix.

237. Delete Node in a Linked List(Easy)

问题描述

请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

现有一个链表 – head = [4,5,1,9],它可以表示为:

4 -> 5 -> 1 -> 9

示例 1:

1
2
3
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

示例 2:

1
2
3
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

说明:

  • 链表至少包含两个节点。

  • 链表中所有节点的值都是唯一的。

  • 给定的节点为非末尾节点并且一定是链表中的一个有效节点。

  • 不要从你的函数中返回任何结果。

链接:https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

解题思路

根据题意,我们是拿不到给定节点的前驱节点,只能拿到后继节点,那么实现删除节点思路就是将后继节点值覆盖当前节点,以此类推,直至尾节点,最后将尾节点置为null即可,我们可以通过递归来做。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public class ListNode {
int val;
ListNode next;

ListNode(int x) {
val = x;
}
}

public void deleteNode(ListNode node) {
// 从说明中可知:给定的节点为非末尾节点并且一定是链表中的一个有效节点。
node.val = node.next.val;
// 终止条件
if(node.next.next == null) {
node.next = null;
return;
} else {
// 递归公式
node = node.next;
deleteNode(node);
}
}
}

执行结果:

Runtime: 0 ms, faster than 100.00% of Java online submissions for Delete Node in a Linked List.

Memory Usage: 36.8 MB, less than 100.00% of Java online submissions for Delete Node in a Linked List.

Review

本周阅读的是:《Understanding Reactor Pattern: Thread-Based and Event-Driven》

作者开头从 thread-base(基于线程)架构和 event-driven(事件驱动)架构切入,然后具体介绍了Reactor Pattern。

基于线程的架构,即一个线程对应一个连接,适用于需要兼容非线程安全的库的程序,同时也指出了 thread-base 架构存在进程过于重量级、上下文切换缓慢和高内存消耗的情况,以及线程与连接一一对应的关系,导致了一旦存在大量的长连接,就会有大量的工作线程处于空闲等待状态,浪费了大量的内存堆栈。

事件驱动结构,可以将线程与连接分隔开来,仅将线程用于特定的回调或处理程序上的事件。

Reactor Pattern 是事件驱动架构的一种实现技术,简单来说,就是用单线程对资源发出的事件进行循环阻塞,并将它们分发给相应的处理程序和回调。只要事件的处理程序和回调被注册了,就不需要阻塞 I/O,这种模式将模块化应用程序级别的代码与可重用的响应式实现解耦。

Reactor 和 Handlers 是 Reactor Pattern 架构的两个重要参与者。

  1. reactor 运行在一个独立的线程中,主要是用于将工作分发给对应的处理程序去处理 I/O 事件。

  2. handler 则是处理与 I/O事件有关的实际工作。

  3. reactor是通过分发适当的 handler 来处理I/O事件。Handlers执行非阻塞操作。

Reactor Pattern 的目的是允许事件驱动的应用程序,可以对来自一个或多的客户端请求进行多路复用和分发。

Tip

本周分享阿里开源的项目:Arthas

最近用的比较多的是 trace 命令,它可以显示方法内部调用路径,并输出方法路径上的每个节点上耗时。

在进行压测的时候,我们可以在后台执行 trace 命令(trace -j class-pattern method-pattern -n xxx > xxx/xxx.log &),等压测完毕后,解析输出的日志文件,可以算出指定方法的平均耗时、最小耗时和最大耗时;我们可以根据耗时情况,查看对应的代码,然后着手进行优化,这对我们在进行性能调优时,有一定的指导作用和帮助。

还有很多其他实用的命令,感兴趣的朋友们可以查看:《Arthas 用户文档》。

Share

本周继续分享 simviso 团队带来的《斯坦福编译原理》译制视频:

【斯坦福编译原理】01 编译器与解释器简介

【斯坦福编译原理】02 编译器结构

【斯坦福编译原理】03 编程语言的性价比

【斯坦福编译原理】04 Cool语言概述

【斯坦福编译原理】05 Cool语言概述 2

ps:知秋大大带领的 simviso 还在不断的更新,感兴趣的小伙伴们赶紧跟上鸭( ̄▽ ̄)”

ARTS打卡:第二十周

发表于 2019-09-09 | 分类于 ARTS

ARTS打卡:第二十周

每周完成一个ARTS:

  1. Algorithm:每周至少做一个 leetcode 的算法题
  2. Review:阅读并点评至少一篇英文技术文章
  3. Tip:学习至少一个技术技巧
  4. Share:分享一篇有观点和思考的技术文章

Algorithm

38. 报数

报数序列是一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:

1
2
3
4
5
1.     1
2. 11
3. 21
4. 1211
5. 111221

1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"), 即 21。
21 被读作 "one 2", "one 1" ("一个二" , "一个一"), 即 1211。

给定一个正整数 n(1 ≤ n ≤ 30),输出报数序列的第 n 项。

注意:整数顺序将表示为一个字符串。

示例 1:

1
2
输入: 1
输出: "1"

示例 2:

1
2
输入: 4
输出: "1211"

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-and-say

解题思路

这道题其实并不难,只要理解了题目的意思,这道题就很容易解出来了。

仔细阅读题目,你会发现从报数序列1开始,往后的序列,都是基于上一个报数序列来得出结果的;报数结果可以拆分两个数,一个是要报的数字,假设为:say,一个是要报数的个数,假设为 count,比如说1 被读作 "one 1" ("一个一"),那么 say = 1,count = 1,以此类推即可。

代码实现

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
class Solution {
public String countAndSay(int n) {
// 边界条件,当序列为1时,直接返回结果“1”
if (n == 1) {
return "1";
}
// 初始化序列
StringBuilder currSequence = new StringBuilder("1");
for (int i = 1; i < n; i++) {
// 初始化个数
int count = 1;
// 要报数的序列
char[] sequence = currSequence.toString().toCharArray();
// 重置结果序列
currSequence = new StringBuilder();
// 遍历要进行报数的序列,逐一报数
for (int j = 0; j < sequence.length; j++) {
// sequence[j] 可以看做是要报的数
// 报数完毕
if (j == sequence.length - 1) {
currSequence.append(count).append(sequence[j]);
break;
}
// 下一个要报的数,与当前报的数一样,数量 count+1
// 比如 11 ,say 为 1,count 为 2
if (sequence[j] == sequence[j + 1]) {
++count;
} else {
// 报下一个数
currSequence.append(count).append(sequence[j]);
// 重置要报的数的个数
count = 1;
}
}
}
return currSequence.toString();
}
}

执行结果:

执行用时 :3 ms, 在所有 Java 提交中击败了94.08%的用户

内存消耗 :34.9 MB, 在所有 Java 提交中击败了85.08%的用户

Review

这周分享:《Java Memory Management》

作者在文中深入的介绍了 Java的 内存管理机制,大致可以概括为以下几点:

  1. 介绍了Java 内存通常可分为 堆栈(Stack)和 堆(Heap)两块,且分别进行了说明
  2. 介绍了堆中对象引用的类型,可分为强引用(Strong Reference)、弱引用(Weak Reference)、软引用(Soft Reference)、幻想引用(Phantom Reference)。
  3. 结合图文,详细的说明了垃圾回收的过程。
  4. 介绍了垃圾收集器的类型,可分为:
    1. 串行化GC(Serial GC):一个单线程垃圾收集器,适用于数据量小的小型应用。启用选项:-XX:+UseSerialGC
    2. 并行化GC(Parallel GC):与 Serial GC 最大的区别在于 Parallel GC 是多线程进行垃圾回收的。启用选项:-XX:+UseParallelGC
    3. 高并发GC( Mostly concurrent GC),主要分为以下两种:
      1. Garbage First:具有高吞吐量和合理的应用程序暂停时间。启用选项:-XX:+UseG1GC
      2. Concurrent Mark Sweep:应用程序暂停时间保持在最小值。可以通过指定选项:-XX:+UseConcMarkSweepGC来使用它。JDK9开始,这种GC类型被声明为deprecated,不再推荐使用。

Tip

这周分享一些 Linux 命令:

  1. ulimit -n:查看系统默认的最大文件句柄数,系统默认是1024
  2. lsof -n|awk '{print $2}'|sort|uniq -c|sort -nr|more:查看当前进程打开了多少句柄数
  3. ulimit -HSn 4096:以root用户运行,H指定了硬性大小,S指定了软性大小,n表示设定单个进程最大的打开文件句柄数量。
  4. 设定句柄数量后,系统重启后,又会恢复默认值。如果想永久保存下来,可以修改.bash_profile文件,可以修改 /etc/profile 把上面命令加到最后。

应用场景:解决Linux系统报出 “too many open files” 的错误。

参考链接:

https://blog.csdn.net/lastsweetop/article/details/6440136

https://blog.csdn.net/lck5602/article/details/79670147

Share

本周继续分享simviso团队带来的优质翻译学习视频:《国外精选翻译课程之编译原理入门》

ARTS打卡:第十九周

发表于 2019-08-27 | 分类于 ARTS

ARTS打卡:第十九周

每周完成一个ARTS:

  1. Algorithm:每周至少做一个 leetcode 的算法题
  2. Review:阅读并点评至少一篇英文技术文章
  3. Tip:学习至少一个技术技巧
  4. Share:分享一篇有观点和思考的技术文章

Algorithm

28. 实现 strStr() (简单)

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

示例 1:

1
2
输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

1
2
输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf()) 定义相符。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/implement-strstr

解题思路

这是一道字符串匹配的问题,如果有了解过字符串匹配算法的小伙伴们,这道题肯定不在话下。

著名的字符串匹配算法有:BF算法(Brute Force 暴力匹配算法,又称朴素匹配算法。)、RK算法(Rabin-Karp BF算法的升级版) BM算法、KMP算法、AC算法等,出了AC算法外,其余算法都可以直接套用,拿来解这道题。

解法一:直接使用 String.indexOf()🤣

1
2
3
4
5
6
7
8
9
10
11
12
public class Soulation {
/**
* 利用现成的 Java API 来实现
*
* @param haystack
* @param needle
* @return
*/
public int strStr(String haystack, String needle) {
return haystack.indexOf(needle);
}
}

执行结果:

执行用时 :1 ms, 在所有 Java 提交中击败了99.25%的用户

内存消耗 :36.4 MB, 在所有 Java 提交中击败了82.76%的用户

哈哈哈,这种利用 API 解题,有很大取巧成分,身为三好青年的我们,还是要学习下源码的,源码取自JDK8,讲解转自

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/**
* Returns the index within this string of the first occurrence of the
* specified substring.
*
* <p>The returned index is the smallest value <i>k</i> for which:
* <blockquote><pre>
* this.startsWith(str, <i>k</i>)
* </pre></blockquote>
* If no such value of <i>k</i> exists, then {@code -1} is returned.
*
* @param str the substring to search for.
* @return the index of the first occurrence of the specified substring,
* or {@code -1} if there is no such occurrence.
*/
public int indexOf(String str) {
return indexOf(str, 0);
}

/**
* Returns the index within this string of the first occurrence of the
* specified substring, starting at the specified index.
*
* <p>The returned index is the smallest value <i>k</i> for which:
* <blockquote><pre>
* <i>k</i> &gt;= fromIndex {@code &&} this.startsWith(str, <i>k</i>)
* </pre></blockquote>
* If no such value of <i>k</i> exists, then {@code -1} is returned.
*
* @param str the substring to search for.
* @param fromIndex the index from which to start the search.
* @return the index of the first occurrence of the specified substring,
* starting at the specified index,
* or {@code -1} if there is no such occurrence.
*/
public int indexOf(String str, int fromIndex) {
return indexOf(value, 0, value.length,
str.value, 0, str.value.length, fromIndex);
}

/**
* Code shared by String and AbstractStringBuilder to do searches. The
* source is the character array being searched, and the target
* is the string being searched for.
*
* @param source the characters being searched.
* @param sourceOffset offset of the source string.
* @param sourceCount count of the source string.
* @param target the characters being searched for.
* @param fromIndex the index to begin searching from.
*/
static int indexOf(char[] source, int sourceOffset, int sourceCount,
String target, int fromIndex) {
return indexOf(source, sourceOffset, sourceCount,
target.value, 0, target.value.length,
fromIndex);
}

/**
* Code shared by String and StringBuffer to do searches. The
* source is the character array being searched, and the target
* is the string being searched for.
*
* @param source the characters being searched.
* @param sourceOffset offset of the source string.
* @param sourceCount count of the source string.
* @param target the characters being searched for.
* @param targetOffset offset of the target string.
* @param targetCount count of the target string.
* @param fromIndex the index to begin searching from.
*/
static int indexOf(char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}

char first = target[targetOffset];
// 计算最大比较范围
int max = sourceOffset + (sourceCount - targetCount);

for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
// 寻找在source中出现和target中第一个字符相等的位置
if (source[i] != first) {
while (++i <= max && source[i] != first);
}

/* Found first character, now look at the rest of v2 */
if (i <= max) {
// 找到第一个字符相等的位置后,比较剩余字符的位置
int j = i + 1;
// end 可以理解为 完全匹配的位置 = 第一个字符匹配的位置 + (要匹配字符串的长度 - 1)
int end = j + targetCount - 1;
// 开始比较字符
for (int k = targetOffset + 1; j < end && source[j]
== target[k]; j++, k++);
// 当 j = end 时,证明字符串已完全匹配
if (j == end) {
/* Found whole string. */
// 返回上面找到的在source中出现和target中第一个字符相等的位置
return i - sourceOffset;
}
}
}
// 找不到返回 -1
return -1;
}

解法二:利用 String.substring 和 Object.equals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
/**
* 利用 String.substring 和 Object.equals 来做
* 思路很简单,直接看代码就能理解了
* @param haystack
* @param needle
* @return
*/
public int strStr(String haystack, String needle) {
if (needle == null || needle.isEmpty()) {
return 0;
}
// 需要匹配的字符串的长度
int n = needle.length();
int i = 0;
while (i + n <= haystack.length()) {
if (haystack.substring(i, n + i).equals(needle)) {
return i;
}
++i;
}
return -1;
}
}

执行结果:

执行用时 :1 ms, 在所有 Java 提交中击败了99.25%的用户

内存消耗 :36.2 MB, 在所有 Java 提交中击败了83.48%的用户

解法三: 采用 BF 算法来实现

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
class Solution {
/**
* 采用 BF算法 来实现
* 思路:
* 很简单,将字符串 haystack 作为主串,将字符串 needle 作为 模式串,在主串中,检查起始位置分别是0、1、2....n-m 且长度为 m 的 n-m + 1 个子串,看有没有跟模式串匹配的
*
* @param haystack
* @param needle
* @return
*/
public int strStr2(String haystack, String needle) {
if (needle == null || needle.isEmpty()) {
return 0;
}
int z = 0;
while (z <= haystack.length() - needle.length()) {
int i;
for (i = 0; i < needle.length(); ++i) {
if (haystack.charAt(z + i) != needle.charAt(i)) {
break;
}
}
if (i != needle.length()) {
++z;
} else {
return z;
}
}
return -1;
}
}

执行结果:

执行用时 :4 ms, 在所有 Java 提交中击败了41.67%的用户

内存消耗 :36 MB, 在所有 Java 提交中击败了84.01%的用户

当然我们还可以采用RK算法、BM算法或KMP算法去做,不过步骤就比较繁琐,我就不列出来了,小伙伴,可以自行了解一下。

以下链接,是我的学习BM算法和AC算法的笔记,感兴趣的小伙伴们,也可以查看一下👀

https://github.com/zyszero/awesome-java-algo/blob/master/src/main/java/com/zys/data/structure/BM.java

https://github.com/zyszero/awesome-java-algo/blob/master/src/main/java/com/zys/data/structure/AC.java

Review

本周阅读:The JVM Architecture Explained

作者在文中详细的介绍了JVM的体系结构以及JVM不同组件,感兴趣的小伙们可以自行查阅。

Tip

最近遇到一个问题,在这里记录一下解决方案。

背景:存在主从两台服务器,主机做 nfs的服务端,从机做客户端;由于服务器IP的更换,导致 nfs服务端了挂了,nfs客户端直接卡死,导致尝试访问挂载目录、df -h等操作都会使终端卡住,ctrl+c也不能强行退出,尝试过 kill - 9 也不起作用。

解决办法:先是采用 umount -f NFS挂载目录命令(-f 强制卸载),然后报device is busy的错误,然后尝试umount -l NFS挂载目录 命令(-l 当设备空闲时,进行umount),等了一会,发现 umount 成功了,还可以先用命令ps aux 来查看占用设备的程序PID,然后用命令kill来杀死占用设备的进程,最后进行 umount 。

原因:

nfs服务器/网络挂了,nfs客户端默认采用hard-mount选项,而不是soft-mount。他们的区别是
soft-mount: 当客户端加载NFS不成功时,重试retrans设定的次数.如果retrans次都不成功,则放弃此操作,返回错误信息 “Connect time out”
hard-mount: 当客户端加载NFS不成功时,一直重试,直到NFS服务器有响应。hard-mount 是系统的缺省值。在选定hard-mount 时,最好同时选 intr , 允许中断系统的调用请求,避免引起系统的挂起。当NFS服务器不能响应NFS客户端的 hard-mount请求时, NFS客户端会显示
“NFS server hostname not responding, still trying”
————————————————
原文链接:https://blog.csdn.net/BrotherDong90/article/details/51735632

参考的博客:

https://blog.csdn.net/BrotherDong90/article/details/51735632

https://my.oschina.net/LastRitter/blog/1542610

https://blog.csdn.net/xiyangyang8/article/details/49725039

Share

本周分享 simviso 团队翻译制作的:《编译原理入门之编译阶段概述》

让我们跟随知秋大大一起学习的吧😄~

ARTS打卡:第十八周

发表于 2019-08-04 | 分类于 ARTS

ARTS打卡:第十八周

每周完成一个ARTS:

  1. Algorithm:每周至少做一个 leetcode 的算法题
  2. Review:阅读并点评至少一篇英文技术文章
  3. Tip:学习至少一个技术技巧
  4. Share:分享一篇有观点和思考的技术文章

Algorithm

8. String to Integer (atoi) (Medium)

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

  • Only the space character ' ' is considered as whitespace character.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

Input: “42”
Output: 42

Example 2:

Input: “ -42”
Output: -42
Explanation:

The first non-whitespace character is ‘-‘, which is the minus sign.

Then take as many numerical digits as possible, which gets 42.

Example 3:

Input: “4193 with words”
Output: 4193
Explanation: Conversion stops at digit ‘3’ as the next character is not a numerical digit.

Example 4:

Input: “words and 987”
Output: 0
Explanation: The first non-whitespace character is ‘w’, which is not a numerical digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: “-91283472332”
Output: -2147483648
Explanation: The number “-91283472332” is out of the range of a 32-bit signed integer.Thefore INT_MIN (−231) is returned.

@DevDocshttps://leetcode.com/problems/string-to-integer-atoi/

题意(译文)

请你来实现一个 atoi 函数,使其能将字符串转换成整数。

首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。

注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。

在任何情况下,若函数不能进行有效的转换时,请返回 0。

说明:

假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/string-to-integer-atoi

解题思路(1)

仔细阅读题目,我们可以从中得出这道题的限制条件:

  1. 函数需要过滤开头的空格字符,直到寻找到第一个非空格的字符为止
  2. 第一个非空字符为正或者负号时,需要保留,与之后的数字组合起来
  3. 有效整数部分之后,出现非数字字符,返回前面的有效整数部分(emm….这一点,根据题意,我根本看不出来,是多次踩坑后,得来的血泪经验,巨坑….)
  4. 假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,返回0
  5. 只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1];如果超出范围,则返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

根据以上的限制,我们的解题思路就可以这样:

  1. 借鉴上周的解题思路,由于ASCII 码表加上拓展集共256个字符,所以我们可以定义一个长度为256的整形数组来模拟散列表,下标为字符的值,数组的值用于标识字符。
  2. 根据限制条件来写判断条件,详情请查看实现代码

代码实现(1)

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
public class Solution{
private static final int map[] = new int[256];

static {
// 初始化字符 '0' - '9'
for (int i = 0; i < 10; i++) {
map[i + '0'] = i + 1;
}
}

public int myAtoi(String str) {
if(str == null){
return 0;
}
// 去掉字符串首尾的空格
String trim = str.trim();
if (trim.isEmpty()) {
return 0;
}
// 将字符串转成字符数组
char[] chars = trim.toCharArray();
// 用于标识数字的正负 1 代表的是正数,-1代表的是负数
int sign = 1;
// 限制条件2
int start = 0;
if (chars[0] == '-') {
sign = -1;
start++;
}else if (chars[0] == '+'){
start++;
}
// 表示遇到有效数字字符个数
int count = 0;
StringBuilder tmp = new StringBuilder();
for (int i = start; i < chars.length; i++) {
// 限制条件3,count != 0表示有效字符存在了;map[chars[i]] = 0 表示当前字符不是‘0’-‘9’
if (count != 0 && map[chars[i]] == 0) {
break;
}
// 限制条件4
if (map[chars[i]] == 0 && count == 0) {
return 0;
}
// 当前字符属于‘0’-‘9’,需要保存起来
if (map[chars[i]] != 0) {
// 有效字符+1
count++;
tmp.append(chars[i]);
}
}
// 将有效数字字符串转成数组,不直接强转的原因是,存在限制条件5,可能会溢出
char[] cChars = tmp.toString().toCharArray();
int result = 0;
int length = 0;
// 从数值的低位遍历至高位
for (int i = cChars.length - 1; i >= 0; i--) {
// 转成有效数字
int c = cChars[i] - '0';
int newResult = result + c * (int) StrictMath.pow(10, length);
// 判断溢出的方法,当新值➗当前位数后,得到的结果与当前的数字不一致,那么就是出现溢出的情况了,假设字符串为“8678”, 8/1 = 8, 78/10 = 7,以此类推,只有溢出时,才会不一致
if (newResult / (int) StrictMath.pow(10, length) != c) {
// 根据正负,返回不同的结果
if (sign > 0) {
return Integer.MAX_VALUE;
} else {
return Integer.MIN_VALUE;
}
}
result = newResult;
++length;
}
// 相当于 result * 1 或 result * -1
return result * sign;
}
}

运行结果(1)

Runtime: 3 ms, faster than 25.42% of Java online submissions for String to Integer (atoi).

Memory Usage: 37 MB, less than 81.37% of Java online submissions for String to Integer (atoi).

emm….解是解出来了,但结果就不怎么理想了,代码也太冗余了点

解题思路(2)

与解题思路(1)一致,代码上进行调整,减少for循环,降低时间复杂度,详情查看代码实现。

代码实现(2)

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
44
45
46
47
public class Solution{
private static final int map[] = new int[256];

static {
// 初始化字符 '0' - '9'
for (int i = 0; i < 10; i++) {
map[i + '0'] = i + 1;
}
}

public int myAtoi(String str) {
if (str == null) {
return 0;
}
// 去掉字符串首尾的空格
String s = str.trim();
if (s.isEmpty()) {
return 0;
}
// 用于标识数字的正负 1 代表的是正数,-1代表的是负数;start 表示开始的下标;result表示数字的累加结果
int sign = 1, start = 0, result = 0;
// 满足限制条件2
if (s.charAt(0) == '-') {
sign = -1;
start++;
} else if (s.charAt(0) == '+') {
start++;
}
// 当遍历字符为无效字符时,终止遍历
while (start < s.length() && map[s.charAt(start)] != 0) {
// 将当前字符转为数值
int num = s.charAt(start) - '0';
// 当前累加数值大于 Integer.MAX_VALUE / 10,那么接下来,继续累加必然会溢出
// 还需排除一种特殊情况,当前累加数值等于 Integer.MAX_VALUE / 10,需要比较接下来的累加值是否大于 Integer.MAX_VALUE的最后一位数,大于则溢出
if (result > Integer.MAX_VALUE / 10 ||
(result == Integer.MAX_VALUE / 10 && num > Integer.MAX_VALUE % 10)) {
// 根据标识,判断是Integer.MAX_VALUE还是Integer.MIN_VALUE
return sign > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
// 数值累加
result = result * 10 + num;
// 往前继续遍历
start++;
}
return result * sign;
}
}

运行结果和复杂度分析(2)

运行结果

Runtime: 1 ms, faster than 100.00% of Java online submissions for String to Integer (atoi).

Memory Usage: 36 MB, less than 100.00% of Java online submissions for String to Integer (atoi).

复杂度分析

时间复杂度:O(n),n是有效字符长度

空间复杂度:O(1)

Review

本周分享:How To Ask Questions The Smart Way

对应的简体中文翻译版:提问的智慧

经久不衰的文章,很值得我们再看一遍。

Tip

本周分享从《SQL必知必会》专栏中,学习到的索引知识和SQL调优的Tip:

ps:思维导图中的图片都来源于专栏,以上是学习笔记

Share

本周分享:Spring Leader分享:Spring Framework之再探Core Container 上

OpenLDAP 的安装与部署 - Linux

发表于 2019-08-03 | 分类于 OpenLDAP

OpenLDAP 的安装与部署 - Linux

OpenLDAP 是什么?

OpenLDAP 是一款轻量级目录访问协议(Lightweight Directory Access Protocol, LDAP), 属于开源集中账号管理架构的实现,且支持众多系统版本,被广大互联网公司所采用。

LDAP 具有两个国家标准,分别是 X.500 和 LDAP。OpenLDAP 是基于 X.500 标准的,而且去除了 X.500 复杂的功能并且可以根据自我需求定制额外扩展功能,但是 X.500 也有不同之处,例如 OpenLDAP 支持 TCP/IP 协议等,目前 TCP/IP 是 Internet 上访问互联网的协议。

OpenLDAP 则直接运行在更简单和更通用的 TCP/IP 或其他可靠的传输协议层上,避免了在 OSI 会话层和表示层的开销,使连接的建立和包的处理更简单、更快,对于互联网和企业网应用更理想。LDAP 提供并实现目录服务的信息服务,目录服务是一种特殊的数据库,对于数据的读取、浏览、搜索有很好的效果。目录服务一般用来包含基于属性的描述性信息并支持精细复杂的过滤功能,但 OpenLDAP 目录服务不支持通用数据库的大量更新操作所需要的复杂的事务管理或回滚策略等。

OpenLDAP 默认以 Berkeley DB 作为后端数据库,Berkeley DB 数据库主要以散列的数据类型进行数据存储,如以键值对的方式进行存储。Berkeley DB 是一类特殊的数据库,主要作用于搜索、浏览、更新查询操作,一般用于一次写入数据、多次查询和搜索有很好的效果。Berkeley DB 数据库时面向查询进行优化,面向读取进行优化的数据库。Berkeley DB 不支持事务性数据库(MySQL、MariDB、Oracle 等)所支持的高并发的吞吐量以及复杂的事务操作。

OpenLDAP 目录中的信息是按树形结构进行组织的,具体信息存储在条目(entry)中,条目可以看成关系数据库中的表记录,条目是具有区别名(Distinguished Name,DN)的属性(attribute),DN 是用来引用条目,DN 相当于关系型数据库(MySQL 等)中的主键(primary key),是唯一的。属性由类型(type)和一个或多个值(value)组成,相当于关系型数据库中字段的概念。

来源:https://wiki.shileizcc.com/confluence/display/openldap/OpenLDAP

安装 OpenLDAP

  1. 使用 yum 安装(推荐)

    命令:yum -y install openldap compat-openldap openldap-clients openldap-servers openldap-servers-sql openldap-devel migrationtools

  2. 使用下载好的rpm进行安装(无网/内网环境下推荐)

    先在可以联网的机器下,下载好对应的 rpm 文件,然后拷贝到无网/内网环境下的机器。

    1. 先确保目标机器有安装好yum,需要用yum对下载好的rpm 进行本地安装,好处在于无需明确rpm的安装顺序,仅使用rpm 命令来安装,依照依赖顺序,一个一个安装rpm,很反人类。

    2. 在能联网的机器上通过yum 下载rpm,需要先安装yum-plugin-downloadonly

      命令:yum -y install yum-plugin-downloadonly

  3. yum-plugin-downloadonly 安装完成后,通过以下命令下载rpm

    命令:yum -y install --downloadonly --downloaddir=/xxx openldap compat-openldap openldap-clients openldap-servers openldap-servers-sql openldap-devel migrationtools

    注意:–downloaddir=/xxx指定rpm的下载目录

    ldap - 1.png

    ldap - 2.png

    ldap - 3.png

    注意:

    我的虚拟机已经安装了一些rpm,实际上所需的 rpm包不止这些。

    yum -y install --downloadonly --downloaddir=/xxx rpm_name :这个命令是有缺陷的,就是系统已有的rpm包,不会重复下载,所以建议在一个比较干净的虚拟机做这个事情。

  4. 通过 yum localinstall /usr/openldap/rpm/*.rpm 来安装 rpm

    ldap - 4.png

配置 OpenLDAP

查看 OpenLDAP 的版本

安装成功后,使用以下命令查看 OpenLDAP 的版本信息

slapd -VV

配置 OpenLDAP 的登录信息

  1. 需要先产生密码

    命令:slappasswd -s 12345678

    记录结果,这是加密后的结果:{SSHA}rjewoTmrrSYQGis4YddObtvK88G/amXy

  2. 创建用户跟根节点

    修改/etc/openldap/slapd.d/cn=config目录下的olcDatabase={2}hdb.ldif文件

例如,创建如下根节点、用户名称和密码

1
2
3
olcSuffix: c=cn
olcRootDN: cn=test,c=cn
olcRootPW: {SSHA}rjewoTmrrSYQGis4YddObtvK88G/amXy

其中:

1
2
3
olcSuffix: 为根节点
olcRootDN: 为访问LDAP的管理员
olcRootPW: 新增项,是步骤一产生的加密后的密码

将下图:

改为:

  1. 修改olcDatabase={1}monitor.ldif文件

    执行命令:vi olcDatabase\=\{1\}monitor.ldif

    将下图:

    改为:

    保存退出

  2. 进行校验

    使用slaptest -u,对配置内容进行校验

    checksum校验码出错无所谓,最后一句可行即可。

  3. 修改ldap.conf配置文件

    文件路径:/etc/openldap/ldap.conf

    将下图:

    改为:

    注意:URL后的内容填写服务器域名或者IP+端口(端口不写就是采用默认:389的),我填写的是自己虚拟机的地址。

  4. 重启OpenLDAP

    使用以下命令进行重启

    1
    2
    3
    systemctl restart slapd

    systemctl status slapd

用 ApacheDirectoryStudio 连接 OpenLDAP

可以采用 ApacheDirectoryStudio 工具测试连接是否成功。

Hostname:是步骤5写的URI

Port:缺省值是389,如果自行改了,则用改的那个

账户用步骤二设置的值,密码用步骤一加密之前的值

设置完后,点finish,出现最后一张图的情况,就是成功了

ARTS打卡:第十七周

发表于 2019-07-21 | 分类于 ARTS

ARTS打卡:第十七周

每周完成一个ARTS:

  1. Algorithm:每周至少做一个 leetcode 的算法题
  2. Review:阅读并点评至少一篇英文技术文章
  3. Tip:学习至少一个技术技巧
  4. Share:分享一篇有观点和思考的技术文章

Algorithm

125. Valid Palindrome(Easy)

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: “A man, a plan, a canal: Panama”
Output: true

Example 2:

Input: “race a car”
Output: false

@DevDocsleetcode.com/problems/valid-anagram

题意

给定一个字符串,判断它是否是回文,只考虑字母数字字符且忽略大小写。

注意:为了解决这个问题,我们将空字符串定义为有效的回文。

解题思路(1)

这题很简单,根据题意,得出以下两个限制条件:

  1. 只考虑字母数字字符且忽略大小写
  2. 将空字符串定义为有效的回文

那么解法就显而易见了:

  1. 通过正则表达式过滤掉除字母数字之外的字符,并将字母全部转为小写字母
  2. 将字符串翻转后,进行比较即可

代码实现(1)

1
2
3
4
5
6
7
8
9
10
class Solution {
public boolean isPalindrome(String s){
// 通过正则过滤掉除字母数字之外的字符,并将字母全部转为小写字母
String s1 = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
// 利用 StringBuilder#reverse() API 翻转字符串
String s2 = new StringBuilder(s1).reverse().toString();
// 比较两个字符串
return s1.equals(s2);
}
}

运行结果和复杂度分析(1)

运行结果:

Runtime: 18 ms, faster than 23.43% of Java online submissions for Valid Palindrome.

Memory Usage: 37.8 MB, less than 96.94% of Java online submissions for Valid Palindrome.

复杂度分析:

暂未清楚如何分析….🕊

解题思路(2)

借鉴散列表的思想,换一个解题角度出发(嘿嘿嘿,是不是发现跟上周的解题思路类似呢😜):

  1. ASCII 码表加上拓展集共256个字符,所以我们可以定义一个长度为256的整形数组来模拟散列表,下标为字符的值,数组的值用于标识字符。
  2. 字母或数字字符对应数组存储的值,是唯一的,其余字符皆为0,这样就不用过滤除字母或数字之外的字符了。
  3. 头尾指针遍历比较

结合代码,更容易理解哟(^U^)ノ~YO

代码实现(2)

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
44
45
46
47
48
49
class Solution{
// 定义一个长度为256的整形数组来模拟散列表,下标为字符的值,数组的值用于标识字符(ASCII 码表加上拓展集共256个字符)。
private static final int[] map = new int[256];

// 初始化整形数组,字母或数字字符对应数组存储的值,要唯一的,其余字符皆为0,这样就不用过滤除字母或数字之外的字符了。
static {
for (int i = 0; i < 10; i++) {
// 初始化数字字符的值,+ 1 是为了值不出现 0
map[i + '0'] = i + 1;
}
for (int i = 0; i < 26; i++) {
// 初始化字母的值,并做大小写忽略处理,值相同即可
map[i + 'a'] = map[i + 'A'] = 11 + i;
}
}

public boolean isPalindrome(String s) {
// 换成字符数组
char[] pChars = s.toCharArray();
// 头尾指针
int start = 0, end = pChars.length - 1;
// sV 头指针指向的值,eV 尾指针指向的值
int sV, eV;
while (start < end) {
sV = map[pChars[start]];
eV = map[pChars[end]];
// sV != 0 代表 pChars[start] 是字母或数字字符
if (sV != 0 && eV != 0) {
// 值不相同,pChars[start] != pChars[end] 即字符不同
if (sV != eV) {
return false;
}
start++;
end--;
} else {
// 如果头指针指向的字符是字母或数字字符之外的字符,则往前移动头指针
if (sV == 0) {
start++;
}
// 如果尾指针指向的字符是字母或数字字符之外的字符,则往后移动尾指针
if (eV == 0) {
end--;
}
}
}
return true;

}
}

运行结果和复杂度分析(2)

结果:

Runtime: 1 ms, faster than 100.00% of Java online submissions for Valid Palindrome.

Memory Usage: 37.7 MB, less than 98.83% of Java online submissions for Valid Palindrome.

时间复杂度:O(n)

空间复杂度:O(n)

Review

本周阅读的是:Java (JVM) Memory Model – Memory Management in Java

作者在文中通俗的介绍了:Java内存模型、Java内存管理、Java 垃圾回收、Java 内存监控的命令与工具以及关于垃圾回收调优的建议,值得小伙伴们一看。

部分笔记如下:

JVM笔记

Tip

本周分享:OpenLDAP 的安装与部署 - Linux

Share

本周分享:从单体应用到微服务的开发旅程

ARTS打卡:第十六周

发表于 2019-07-14 | 分类于 ARTS

ARTS打卡:第十六周

每周完成一个ARTS:

  1. Algorithm:每周至少做一个 leetcode 的算法题
  2. Review:阅读并点评至少一篇英文技术文章
  3. Tip:学习至少一个技术技巧
  4. Share:分享一篇有观点和思考的技术文章

Algorithm

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = “anagram”, t = “nagaram”
Output: true

Example 2:

Input: s = “rat”, t = “car”
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

@DevDocsleetcode.com/problems/valid-anagram

题意

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

说明:
你可以假设字符串只包含小写字母。

解题思路(1)

  1. 首先要清楚什么是字母异位词;两个单词如果包含相同的字母,次序不同,则称为字母易位词(anagram)
  2. 由题意可得,我们可以假设字符串只包含小写字母
  3. 由已知的1、2,我们可以快速的得出一个解法:将字符串分别分割为两个字符数组,然后分别进行字符排序,最后两个字符数组进行一一比对,就可以判断出是不是字母异位词了,当然,我们要加上限制条件,当字符串为空或两个字符串长度不等时,字符串 t 肯定不是字符串 s 的字母异位词。

代码实现(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean isAnagram(String s, String t) {
// 边界条件 1. 当字符串为空或两个字符串长度不等时 false
if (s == null || t == null || s.length() != t.length()) {
return false;
}
// 2. 分别将字符串分解为字符数组
char[] sChars = s.toCharArray();
char[] tChars = t.toCharArray();
// 3. 对字符数组进行排序后,进行一一比对即可
Arrays.sort(sChars);
Arrays.sort(tChars);
for (int i = 0; i < sChars.length; i++) {
if (sChars[i] != tChars[i]) {
return false;
}
}
return true;
}
}

运行结果和复杂度分析(1)

运行结果:
Runtime: 6 ms, faster than 43.67% of Java online submissions for Valid Anagram.
Memory Usage: 37.5 MB, less than 72.58% of Java online submissions for Valid Anagram.

复杂度分析:
时间复杂度:假设 Arrays.sort 的时间复杂度为 O(nlogn),最后排序的时间复杂度为 O(n),那么最终的时间复杂度为 O(nlogn)。
空间复杂度:取决于字符串的长度,这里假设为 O(n)

解题思路(2)

借鉴散列表的思想,换一个解题角度出发:

  1. 根据题意我们可以得出,给予的字符串的字符范围是 a - z,即26个字母
  2. 那么我们就可以用一个整形数组来进行存储字母,通过下标标识‘字母’,值表示字母出现的次数
  3. 数组下标如是何标识字母呢?我们可以结合 ASCII 码表来得出, 使用(当前字母 - a)的值为下标
  4. 这样我们就可以通过数组下标和值,推断出字符串 t 是不是字符串 s 的字母异位词
  5. 如果还没想出具体怎么做,嘻嘻😀,结合代码实现来理解,你会一瞬间恍然大悟的😜。

代码实现(2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public boolean isAnagram(String s, String t) {
// 边界条件 1. 两字符串长度不一致,则返回 false
if (s.length() != t.length()) {
return false;
}
// 定义一个整数数组,模拟散列表
int[] table = new int[26];
// 遍历字符串字符
for (int i = 0; i < s.length(); i++) {
// 一个字符串的字符对应的值进行 + 1 操作
// 另一个字符串的字符对应的值进行 - 1 操作
table[s.charAt(i) - 'a']++;
table[t.charAt(i) - 'a']--;
}
for (int i = 0; i < table.length; i++) {
// 如果两个字符串是由相同数量且相等的字符组成,那么字符对应数组内的值,应该为0,因为两个字符串遍历字符时,分别做的是+1和-1的操作
if (table[i] != 0) {
return false;
}
}
return true;
}
}

运行结果和复杂度分析(2)

运行结果:
Runtime: 4 ms, faster than 78.57% of Java online submissions for Valid Anagram.
Memory Usage: 36.2 MB, less than 99.41% of Java online submissions for Valid Anagram.

复杂度分析:
时间复杂度:只有两个遍历,即时间复杂度为 O(n)
空间复杂度:只额外使用了 数组 table[26],所以空间复杂度为 O(1)

解题思路(3)

我们作为新生代的三好青年,当然要想想有没有比解法二更快的解法啦🤣~
我们可以从解法(2)出发,在此基础上进行优化,比如char 和 int 之间存在隐式转换,那么我们可以直接将字符作为 int[] 的下标,去掉 String.charAt() - ‘a’ 的消耗。

代码实现(3)

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
class Solution {
public boolean isAnagram(String s, String t) {
// 边界条件 1. 两字符串长度不一致,则返回 false
if (s == null || t == null || s.length() != t.length()) {
return false;
}
// ASCII 码表加上拓展集共256个字符,所以我们定义一个长度为256的整数数组来模拟散列表
int[] table = new int[256];
for (char c : s.toCharArray()) {
// 一个字符串的字符对应的值进行 + 1 操作
table[c]++;
}
for (char c : t.toCharArray()) {
// 另一个字符串的字符对应的值进行 - 1 操作
table[c]--;
}
for (int val : table) {
// 如果两个字符串是由相同数量且相等的字符组成,那么字符对应数组内的值,应该为0,因为两个字符串遍历字符时,分别做的是+1和-1的操作
if (val != 0) {
return false;
}
}
return true;
}
}

运行结果和复杂度分析(3)

运行结果:
Runtime: 2 ms, faster than 99.82% of Java online submissions for Valid Anagram.
Memory Usage: 36.4 MB, less than 99.35% of Java online submissions for Valid Anagram.

复杂度分析:
时间复杂度:只有两个遍历,即时间复杂度为 O(n)
空间复杂度:只额外使用了整形数组 table[256],所以空间复杂度为 O(1)

Review

本周阅读的是:What is Test-Driven Development (TDD)?

作者在文中介绍了什么是TDD(测试驱动开发)?并详细阐述了为什么TDD(测试驱动开发)在企业应用程序中是很重要的,以及对测试用例的覆盖率,进行了讨论,作者认为测试用例的覆盖率无需时刻做到100%,100%的代码覆盖率,不应该成为追求的目标,应该视业务场景而定,比如复杂的业务,可能需要做到90%,简单新功能,可能做到50%就可以了。

Tip

本周分享 Intellij IDEA 的两个快捷键:

  1. Ctrl+F12:可以快速定位到当前类的任何方法和变量。
    Ctrl+F12
  2. Alt+F7:Find Usages,从名字上就可以看出来了,可以快速的定位到类或方法或变量的任何被引用的地方。
    Find Usages

Share

本周分享:Spring Boot vs. Spring MVC vs. Spring: How Do They Compare?
译文可以看这篇:Spring、Spring MVC、Spring Boot三者的关系还傻傻分不清楚?

123
渴望飞的哺乳类

渴望飞的哺乳类

愿你仗剑走天涯,归来仍是少年

28 日志
5 分类
5 标签
© 2019 渴望飞的哺乳类
由 Hexo 强力驱动
|
主题 — NexT.Gemini v5.1.4
本站访客数 人次 访问总量 次