vlambda博客
学习文章列表

今日习题：替换所有的问号

链接:leetcode-cn.com/problems/replace-all-s-to-avoid-consecutive-repeating-characters

给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。

注意：你 不能 修改非 '?' 字符。

题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。

在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。

输入：s = "?zs"

输出："azs"

解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。

示例 2：

输入：s = "ubv?w"

输出："ubvaw"

解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。

思路：

题目简单粗暴 将字符串中的‘？’转为不与两边相同的小写字母；

一开始我的想法比较复杂 因为不知道如何选取字母让其满足不与两边相同 等看完官解后思路瞬间打开 一语惊醒梦中人！！！

官解思路--遇到‘？’ 从‘a','b','c' 三个字符中选择一个即可  也就是说提前选好三个字母 面对任何情况都有一个不重复的解！！！

想到这个思路后题目就简单多了

【1】字符串转化字符数组

【2】遍历查找’？‘

【3】存在’？‘ 遍历abc三个字符判断条件 当不满足连续时 continue 更换字符

【4】合适字符替换字符数组 返回String 类型字符串

java：

class Solution { public String modifyString(String s)  { char [] cs=s.toCharArray();//转化字符数组 int n=s.length();        for(int i=0;i<n;i++){//遍历查找‘？’ if(cs[i]=='?'){                for(char a='a';a<='c';a++){//使用for循环遍历 a b c 三个字符是否符合                    if((i>0&&cs[i-1]==a)||(i<n-1&&cs[i+1]==a))                    //当不满足 不重复条件时 a++ 即更换字符 continue; cs[i]=a;//for循环完成 替换字符 break; } }  }        return new String(cs);//强制转换类型 输出 }}

梅开二度 二分查找复习 

今日习题：第一个错误的版本

链接:leetcode-cn.com/problems/first-bad-version

有 n 个版本 [1, 2, ..., n]，找出第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。

当前版本没有错误返回 false 有错误返回true

简单的说 找到第一个 返回true的数值；

输入：n = 5, bad = 4

输出：4

解释：

调用 isBadVersion(3) -> false 

调用 isBadVersion(5) -> true 

调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1

输出：1

思路：

      顺序查找---> 二分查找

【1】定义l，r 左右指针；定义mid： l,r的中间值;

【2】停止条件 mid所在位置即为第一个true

【3】从左至右逼近 mid 返回为false时说明还没有出错 l 右移到mid+1；返回为true 说明此时已经出错 r左移到mid-1 当

【4】当l r 交叉时即r<l 时  l的位置是第一个true；返回l即可

java：

/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */
public class Solution extends VersionControl { public int firstBadVersion(int n) { int l=1,r=n,ans=0; while(l<=r){ int mid=l+((r-l)>>1); if(!isBadVersion(mid)) l=mid+1; else r=mid-1; } return l; }}

今日习题：搜索插入位置

链接:leetcode-cn.com/problems/search-insert-position

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

输入: nums = [1,3,5,6], target = 5

输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2

输出: 1

思路：

老规矩 顺序查找先实验二分：

【1】老一套 l，r左右指针 mid中间值

【2】判断mid和target的关系 左右指针向target逼近

【3】当以mid为下标的值小于target时 那么目标值一定在mid右方 所以使l=mid+1；同理  大于等于target时 目标值一定在mid左侧或mid位置 使r=mid-1；

【4】判断r是否还大于l 如果小于 说明两者重叠r在l左侧 即 l 位置为答案；

java：

class Solution { public int searchInsert(int[] nums, int target)  { int l=0,r=nums.length-1; while(l<=r){ int mid=((r-l)>>1)+l; if(nums[mid]<target) l=mid+1; else r=mid-1; } return l; }}

DFS-思路：

【1】dx dy 方向数组 创建队列que 记录数组长宽 mn；

【2】双重for循环开始遍历 当i，j表示位置的值为 1 时 即使岛屿时， 开始深度优先搜索 DFS 调用DFS函数 传递数组即当前位置 

    DFS函数：

            【1】 sum记录岛屿大小初始值为0；

            【2】记录当前位置是否为岛屿 是则sum++  并更改当前数值

            【3】for循环上下左右移动 在移动后的数组位置不越界且值为1的情况下 把移动后的位置再次调用DFS函数 并将返回值累加到sum中

            【4】返回sum；

【3】比较最大值返回即可

有更好更新更牛的方法敬请留言告诉我！！

——————————————————————

 “就算累死自己，也要卷死同学”

题外话：关于排版和颜色的设置，因为俺也是刚开始搞，有什么关于配色的文字的大小的建议希望大家不吝赐教！！！这次主要代码以文字的形式展现的，想自己运行的可以复制了！！

大大鼓励同学们留言给我，好歹给我留个念想，也不枉我熬到这么晚😭

大可随便转载，如有侵权或代码等描述错误，请及时联系