客思吟商还怯。怨歌长、琼壶暗缺。——周密《玉京秋·烟水阔》楠少博客 阅读文章

LeetCode 第744题：寻找比目标字母大的最小字母

楠少
2022-04-03
6666666
8888888
Python
leetcode

摘要力扣744：寻找比目标字母大的最小字母； LeetCode744:Find Smallest Letter Greater Than Target。使用二分法解决该问题，一种手写，一种内置。语言 Python。

## 题目见文末
[LeetCode link](https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target/)
## 思路及题解
### 手写二分
#### 源码：
```python
class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        if letters[0] > target or letters[-1] <= target:
            return letters[0]
        start = 1
        end = len(letters)-1
        while start < end:
            mid = (start + end) // 2
            if letters[mid] > target:
                end = mid
            else:
                start = mid + 1
        return letters[start]
```
#### 执行结果
> 	40 ms, 16.9 MB

#### 解析
刚开始想到的就是二分查找，在查找之前，先排除两种情况：
1. 列表首位元素满足要求，返回该元素，程序结束。
2. 列表末位元素也不满足要求，返回首位元素，程序结束。
然后开始二分查找。

### 使用python内置函数

#### 源码
```python
class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        r = bisect_right(letters, target)
        if r == len(letters):
            r = 0
        return letters[r]
```
#### 执行结果
> 	44 ms, 16.9 MB

#### 解析
python 内置了二分算法操作的模块`bisect`，如果不想手写的话，也可以使用内置函数。
![模块结构](https://img-blog.csdnimg.cn/190ca4291d774308a4f47370034a8680.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5qWg5bCR56eR5oqA,size_20,color_FFFFFF,t_70,g_se,x_16 "模块结构")

根据题意：` sorted in non-decreasing order `，`the smallest character in the array that is larger than target `，所以使用 `bisect_right` 函数确定位置：
```python
def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.

Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        # Use __lt__ to match the logic in list.sort() and in heapq
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo
```

## 题目
### 英文版
#### [744. Find Smallest Letter Greater Than Target](https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target/)

Given a characters array `letters` that is sorted in **non-decreasing** order and a character `target`, return *the smallest character in the array that is larger than* `target`.

**Note** that the letters wrap around.

- For example, if `target == 'z'` and `letters == ['a', 'b']`, the answer is `'a'`.

**Example 1:**

```
Input: letters = ["c","f","j"], target = "a"
Output: "c"
```

**Example 2:**

```
Input: letters = ["c","f","j"], target = "c"
Output: "f"
```

**Example 3:**

```
Input: letters = ["c","f","j"], target = "d"
Output: "f"
```

**Constraints:**

- `2 <= letters.length <= 104`
- `letters[i]` is a lowercase English letter.
- `letters` is sorted in **non-decreasing** order.
- `letters` contains at least two different characters.
- `target` is a lowercase English letter.

### 中文版
#### [744. 寻找比目标字母大的最小字母](https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target/)

给你一个排序后的字符列表 `letters` ，列表中只包含小写英文字母。另给出一个目标字母 `target`，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

- 如果目标字母 `target = 'z'` 并且字符列表为 `letters = ['a', 'b']`，则答案返回 `'a'`

**示例 1：**

```
输入: letters = ["c", "f", "j"]，target = "a"
输出: "c"
```

**示例 2:**

```
输入: letters = ["c","f","j"], target = "c"
输出: "f"
```

**示例 3:**

```
输入: letters = ["c","f","j"], target = "d"
输出: "f"
```

**提示：**

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

上一篇：通知：系统账号服务正在升级，短期内无法登录。

下一篇：常州大学/教务系统/教室相关

文章评论

[ 聊聊技术聊聊自己 ]

在巴甫洛夫条件反射试验中：给定一条狗，每次摇铃后喂食，足够次数后，狗则听到铃声将会习惯性的分泌唾液，由此引发对铃声的依恋。延伸到实际，给定一个喜欢的妹子，每次见面赠与巴甫洛夫式的礼品或者零食，由此引发妹子的依恋。引入薛定谔的猫理论，在未表白前，妹子与自己一直处于一种“概率云”的状态，一旦表白则“概率云”将消失成为实际。在巴甫洛夫式后且未表白前，自己与妹子的关系为“既是恋人又不是恋人”的矛盾体。返回巴甫洛夫式试验中，在妹纸形成足够的依恋过后，则可以打破薛定谔 “概率云”的状态。这个谜一样的自己，这一刻薛定谔附体，带着量子论般深沉的哀愁，让她从此不能自拔! 自此创作 巴甫洛夫薛定谔把妹法，深藏功与名。

客思吟商还怯。怨歌长、琼壶暗缺。——周密《玉京秋·烟水阔》 楠少博客 阅读文章

LeetCode 第744题：寻找比目标字母大的最小字母

文章评论

客思吟商还怯。怨歌长、琼壶暗缺。——周密《玉京秋·烟水阔》楠少博客阅读文章