LeetCode刷题:散列表和字符串

本文最后更新于:10 个月前

关于散列表和字符串的 4 个必知必会的代码实现

散列表

  • 实现一个基于链表法解决冲突问题的散列表

  • 实现一个 LRU 缓存淘汰算法

字符串

  • 实现一个字符集,只包含 a~z26 个英文字母的 Trie

  • 实现朴素的字符串匹配算法

字符串题目

Reverse String (反转字符串)

思路

看到题目后首先想到的是双指针法,创建两个指针 headtail 分别指向字符串头部和尾部,交换两个指针所指元素,然后 head 往后 tail 往前,直到两指针相遇。

代码

public void reverseString(char[] s) {
    if (s.length == 0 || s.length == 1) {
        return;
    }
    int head = 0;
    int tail = s.length - 1;
    while (head < tail) {
        char temp = s[head];
        s[head] = s[tail];
        s[tail] = temp;
        head++;
        tail--;
    }
}

Reverse Words in a String(翻转字符串里的单词)

思路

从后往前遍历,遇到空格跳过,否则就记录下不是空格的位置,然后截取字串,放到临时字符串中

代码

public String reverseWords(String s) {
    if (s.length() == 0) {
        return s;
    }
    StringBuilder result = new StringBuilder();
    for (int i = s.length() - 1; i >= 0;) {
        int end = 0;
        if (s.charAt(i) == ' ') {
            i --;
            continue;
        }
        end = i + 1;
        while ((i >= 0) && s.charAt(i) != ' ') {
            i --;
        }
        result.append(s, i + 1, end);
        if (i > 0) {
            result.append(" ");
        }
    }
    return result.toString().trim();
}

String to Integer (atoi)(字符串转换整数 (atoi))

思路

题目说明上已经给出限制条件,但是还有很多条件没有给出,最后一步步提交踩着坑终于踩出来了。。。

代码

public int myAtoi(String str) {
    if (str == null || "".equals(str)) {
        return 0;
    }
    StringBuilder resultS = new StringBuilder();
    boolean isNegative = false;
    boolean isPositive = false;
    String newStr = str.trim();
    if ("".equals(newStr)) {
        return 0;
    }
    if ((newStr.charAt(0) < '0') || (newStr.charAt(0) > '9')) {
        if (newStr.charAt(0) != '+' && newStr.charAt(0) != '-') {
            return 0;
        } else {
            if (newStr.charAt(0) == '-') {
                isNegative = true;
            }
            if (newStr.charAt(0) == '+') {
                isPositive = true;
            }
        }
    }
    char[] chars = newStr.toCharArray();
    int i = isNegative | isPositive ? 1 : 0;
    
    for (; i < chars.length; i++) {
        char c = chars[i];
        if (c == '0') {
            chars[i] = '`';
        } else {
            break;
        }
    }
    i = isNegative | isPositive ? 1 : 0;
    for (; i < chars.length; i++) {
        char c = chars[i];
        if (c == '`') {
            continue;
        }
        if (resultS.length() > 10) {
            return isNegative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        }
        if (c >= '0' && c <= '9') {
            resultS.append(c);
        } else {
            break;
        }
    }
    if (resultS.length() == 0) {
        return 0;
    }
    long aLong = Long.parseLong(resultS.toString());
    if (isNegative) {
        aLong = - aLong;
    }
    if (aLong > Integer.MAX_VALUE) {
        return Integer.MAX_VALUE;
    }
    if (aLong < Integer.MIN_VALUE) {
        return Integer.MIN_VALUE;
    }

    return (int) aLong;
}

精简版代码

public int myAtoi2(String str) {
    str = str.trim();
    if (str.length() == 0) {
        return 0;
    }
    long sum = 0;
    int first = 0, n = str.length();
    int flag = 1;
    if (str.charAt(0) == '+') {
        first++;
    } else if (str.charAt(0) == '-') {
        first++;
        flag = -1;
    }
    for (int i = first; i < n; i++) {
        if (!Character.isDigit(str.charAt(i))) {
            return (int) sum * flag;
        }
        sum = 10 * sum + str.charAt(i) - '0';
        if (flag == 1 && sum > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        if (flag == -1 && (-1) * sum < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
    }
    return (int) sum * flag;
}


欢迎关注我的公众号😘