leetcode744：寻找比目标字母大的最小字母（find_smallest_letter_greater_than_target_744）

carloscn commented 1 year ago

问题描述

给你一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters 里至少有两个不同的字符。

返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。

示例 1：

输入: letters = ["c", "f", "j"]，target = "a" 输出: "c" 解释：letters 中字典上比 'a' 大的最小字符是 'c'。示例 2:

输入: letters = ["c","f","j"], target = "c" 输出: "f" 解释：letters 中字典顺序上大于 'c' 的最小字符是 'f'。示例 3:

输入: letters = ["x","x","y","y"], target = "z" 输出: "x" 解释：letters 中没有一个字符在字典上大于 'z'，所以我们返回 letters[0]。

提示：

2 <= letters.length <= 104 letters[i] 是一个小写字母 letters 按非递减顺序排序 letters 最少包含两个不同的字母 target 是一个小写字母

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/find-smallest-letter-greater-than-target

carloscn commented 1 year ago

问题分析

C语言版本

static int32_t find_letter(const char *str, char target, char *out)
{
    int32_t ret = 0;
    size_t len = 0;
    size_t left = 0, right = 0, pivot = 0;
    bool condition = true;

    UTILS_CHECK_PTR(str);
    UTILS_CHECK_PTR(out);
    UTILS_CHECK_LEN(len = strlen(str));

    left = 0;
    right = len - 1;

    while (left <= right) {
        pivot = left + (right - left) / 2;
        if (target < str[pivot]) {
            right = pivot - 1;
        } else {
            left = pivot + 1;
        }
    }
    LOG("the left is %zu, right is %zu, len is %zu\n", left, right, len);
    *out = str[left % len];

finish:
    return ret;
}

Rust版本

fn find_letter(instr: &str, target: u8) -> u8
{
    let mut left:usize = 0;
    let mut right:usize = instr.len() - 1;
    let mut pivot:usize;
    let mut ret:u8;
    let instr_array = instr.as_bytes();

    while left <= right {
        pivot = left + (right - left) / 2;
        if target < instr_array[pivot] {
            right = pivot - 1;
        } else {
            left = pivot + 1;
        }
    }
    ret = instr_array[left % instr.len()];

    return ret;
}

carloscn commented 1 year ago

code

https://github.com/carloscn/structstudy/blob/master/c_programming/str/n40_find_smallest_letter_greater_than_target_744.c https://github.com/carloscn/structstudy/blob/master/rust_programming/str/src/n40_find_smallest_letter_greater_than_target_744.rs

carloscn / structstudy