LIXI.FUN

LIXI.FUN

做个有趣的人

0%

发表于 分类于

题目描述

给定一个字符串，只包含字母和数字，按要求找出字符串中的最长（连续）子串的长度，字符串本身是其最长的子串，子串要求：

  1. 只包含 1 个字母(a-z, A-Z) 其余必须是数字；
  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
class Solution {
    public int lengthOfLongestSubstring(String s) {

        boolean isAllLetter = true;
        boolean isAllNumber = true;

        int res = 0;

        int leftNumCount = 0;
        int rightNumCount = 0;

        for (int i = 0; i < s.length(); i++) {
            if (Character.isAlphabetic(s.charAt(i))) {
                isAllNumber = false;
                leftNumCount = rightNumCount;
                rightNumCount = 0;
            } else {
                isAllLetter = false;
                rightNumCount++;
            }
            res = Math.max(res, rightNumCount + leftNumCount + 1);
        }

        res = isAllLetter || isAllNumber ? -1 : res;

        return res;
    }
}

复杂度分析

  • 时间复杂度分析: O(n) 遍历了一遍字符串
  • 空间复杂度分析: O(1) 只用了有限个的标志变量

发表于 分类于

题目链接

700. 二叉搜索树的搜索

代码

  1. 递归

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution {
        public TreeNode searchBST(TreeNode root, int val) {
            if (root == null || root.val == val) {
                return root;
            } else if (root.val > val) {
                return searchBST(root.left, val);
            } else {
                return searchBST(root.right, val);
            }
        }
    }

  2. 迭代

    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution {
        public TreeNode searchBST(TreeNode root, int val) {
            TreeNode node = root;
            while (node != null && node.val != val) {
                node = node.val > val ? node.left : node.right;
            }
            return node;
        }
    }

复杂度分析

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

发表于 分类于

题目链接

701. 二叉搜索树中的插入操作

代码

  1. 递归

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
        public TreeNode insertIntoBST(TreeNode root, int val) {
            if (root == null) {
                return new TreeNode(val);
            }

            if (root.val > val) {
                root.left = insertIntoBST(root.left, val);
            } else {
                root.right = insertIntoBST(root.right, val);
            }

            return root;
        }
    }

  2. 迭代

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
        public TreeNode insertIntoBST(TreeNode root, int val) {
            if (root == null) {
                return new TreeNode(val);
            }

            TreeNode parent = root;
            TreeNode node = root;

            while (node != null) {
                parent = node;
                node = node.val > val ? node.left : node.right;
            }

            if (parent.val > val) {
                parent.left = new TreeNode(val);
            } else {
                parent.right = new TreeNode(val);
            }

            return root;
        }
    }

复杂度分析

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)