ARTS打卡：第十九周

每周完成一个ARTS：

Algorithm：每周至少做一个 leetcode 的算法题

Review：阅读并点评至少一篇英文技术文章

Tip：学习至少一个技术技巧

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()🤣

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，讲解转自

/**
 * 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

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 算法来实现

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

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

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

ARTS打卡：第十九周

Algorithm

28. 实现 strStr() (简单)

解题思路

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

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

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

Review

Tip

Share

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