【Leetcode -704.二分查找 -709.转换成小写字母 -717.1比特与2比特字符】

简介: 【Leetcode -704.二分查找 -709.转换成小写字母 -717.1比特与2比特字符】

Leetcode -704.二分查找

题目:给定一个 n 个元素有序的(升序)整型数组nums和一个目标值 target,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 - 1。

示例 1:

输入: nums = [-1, 0, 3, 5, 9, 12], target = 9

输出 : 4

解释 : 9 出现在 nums 中并且下标为 4

示例 2 :

输入 : nums = [-1, 0, 3, 5, 9, 12], target = 2

输出 : -1

解释 : 2 不存在 nums 中因此返回 - 1

提示:

你可以假设 nums 中的所有元素是不重复的。

n 将在 [1, 10000]之间。

nums 的每个元素都将在 [-9999, 9999]之间。

思路是双指针分别从数组的头和尾开始遍历,每次用中间指针 mid 判断与 target 的大小关系,等于则返回下标 mid ;中间下标对应的值比 target 大就更新右指针,收缩右边范围;中间下标对应的值比 target 小就更新左指针,收缩左边的范围,直到找到;找不到则返回 -1;

int search(int* nums, int numsSize, int target)
    {
        //双指针下标
        int left = 0, right = numsSize - 1;
        //当左指针小于等于右指针循环继续
        while (left <= right)
        {
            // mid 取left和right的中间下标,left + (right - left) / 2 是为了防止溢出
            int mid = left + (right - left) / 2;
            //如果中间下标等于 target 返回下标
            //如果中间下标大于 target,将中间下标-1赋给右指针
            //如果中间下标小于 target,将中间下标+1赋给左指针
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        //如果找不到,返回-1
        return -1;
    }

Leetcode -709.转换成小写字母

题目:给你一个字符串 s ,将该字符串中的大写字母转换成相同的小写字母,返回新的字符串。

示例 1:

输入:s = “Hello”

输出:“hello”

示例 2:

输入:s = “here”

输出:“here”

示例 3:

输入:s = “LOVELY”

输出:“lovely”

提示:

1 <= s.length <= 100

s 由 ASCII 字符集中的可打印字符组成

思路是,在ASCII表中小写字母比对应的大写字母大32,直接转换即可;

char* toLowerCase(char* s)
    {
        //遍历字符串,直接将大写字母加上32,即可转换成小写字母
        for (int i = 0; i < strlen(s); i++)
        {
            if (s[i] >= 'A' && s[i] <= 'Z')
            {
                s[i] += 32;
            }
        }
        return s;
    }

Leetcode -717.1比特与2比特字符

题目:有两种特殊字符:

第一种字符可以用一比特 0 表示

第二种字符可以用两比特(10 或 11)表示

给你一个以 0 结尾的二进制数组 bits ,如果最后一个字符必须是一个一比特字符,则返回 true 。

示例 1:

输入: bits = [1, 0, 0]

输出 : true

解释 : 唯一的解码方式是将其解析为一个两比特字符和一个一比特字符。

所以最后一个字符是一比特字符。

示例 2 :

输入:bits = [1, 1, 1, 0]

输出:false

解释:唯一的解码方式是将其解析为两比特字符和两比特字符。

所以最后一个字符不是一比特字符。

提示 :

1 <= bits.length <= 1000

bits[i] 为 0 或 1

思路是 i 从0开始遍历,每次走的步长是当前元素的值+1,因为当遇到字符 1 的时候,需要走两步;当遇到字符 0 的时候需要走一步;最后判断 i 走的总步长是否等于数组除去最后一个字符 0 后的长度;

bool isOneBitCharacter(int* bits, int bitsSize)
    {
        // i 从0开始遍历,到数组的倒数第二个结束,遍历的步长就是当前元素的值+1
        // 因为字符 1 不能单独作一个字符,所以遇到字符 1 肯定是会与它后面的字符组成特殊字符,所以遇到字符1,i每次要走两步
        // 而字符 0 只能单独作为一个字符,所以遇到字符 0 ,i每次走一步
        //因为要判断这个数组中的结束字符是否是 1比特位的,所以就除去最后一位字符,判断 i 走的总步长是否等于除去最后一位的数组的长度,等于则返回true;否则返回false
        int i = 0;
        while (i < bitsSize - 1)
        {
            i += bits[i] + 1;
        }
        return i == bitsSize - 1;
    }
目录
相关文章
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
1月前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
1月前
|
算法 数据可视化 数据挖掘
深入解析力扣162题:寻找峰值(线性扫描与二分查找详解)
深入解析力扣162题:寻找峰值(线性扫描与二分查找详解)
|
1月前
|
存储 算法 数据可视化
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
|
1月前
|
存储 算法 数据可视化
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)
|
23天前
|
索引
821.字符的最短距离-力扣(LeetCode)
821.字符的最短距离-力扣(LeetCode)
12 0
|
27天前
|
存储 算法 程序员
力扣经典150题第三十一题:无重复字符的最长子串
力扣经典150题第三十一题:无重复字符的最长子串
12 0
|
2月前
|
算法 索引
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
|
1月前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
1月前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串