Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II

这篇具有很好参考价值的文章主要介绍了Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II

目录

79. 单词搜索 Word Search  🌟🌟

80. 删除有序数组中的重复项 II Remove-duplicates-from-sorted-array-II  🌟🌟

81. 搜索旋转排序数组 II Search-in-rotated-sorted-array-II  🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏


79. 单词搜索 Word Search

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1:

Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true

示例 2:

Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出:true

示例 3:

Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出:false

提示:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

进阶:你可以使用搜索剪枝的技术来优化解决方案,使其在 board 更大的情况下可以更快解决问题?

代码:

fn exist(board: Vec<Vec<char>>, word: String) -> bool {
    let mut board = board;
    let m = board.len();
    let n = board[0].len();

    for i in 0..m {
        for j in 0..n {
            if search(&mut board, &word, i, j, 0) {
                return true;
            }
        }
    }

    false
}

fn search(board: &mut Vec<Vec<char>>, word: &String, i: usize, j: usize, k: usize) -> bool {
    if k == word.len() {
        return true;
    }
    if i >= board.len() || j >= board[i].len() || board[i][j] != word.chars().nth(k).unwrap() {
        return false;
    }
    let c = board[i][j];
    board[i][j] = '#'; // 标记已访问

    if search(board, word, i + 1, j, k + 1)
        || search(board, word, i, j + 1, k + 1)
        || search(board, word, i - 1, j, k + 1)
        || search(board, word, i, j - 1, k + 1)
    {
        return true;
    }
    board[i][j] = c; // 还原
    false
}

fn main() {
    let board = vec![
        vec!['A', 'B', 'C', 'E'],
        vec!['S', 'F', 'C', 'S'],
        vec!['A', 'D', 'E', 'E'],
    ];
    println!("{}", exist(board, String::from("ABCCED")));
}

输出:

true
true
false


80. 删除有序数组中的重复项 II Remove-duplicates-from-sorted-array-II

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 最多出现两次 ,返回删除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1:

输入:nums = [1,1,1,2,2,3]
输出:5, nums = [1,1,2,2,3]
解释:函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

示例 2:

输入:nums = [0,0,1,1,1,1,2,3,3]
输出:7, nums = [0,0,1,1,2,3,3]
解释:函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

提示:

  • 1 <= nums.length <= 3 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 已按升序排列

相关题目: 26. 删除有序数组中的重复项

代码:

fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
    if nums.len() <= 2 {
        return nums.len() as i32;
    }
    let mut i = 1;
    for j in 2..nums.len() {
        if nums[j] != nums[i - 1] {
            i += 1;
            nums[i] = nums[j];
        }
    }
    (i + 1) as i32
}

fn main() {
    let mut nums = vec![1, 1, 1, 2, 2, 3];
    println!("{}", remove_duplicates(&mut nums));

    let mut nums = vec![0, 0, 1, 1, 1, 1, 2, 3, 3];
    println!("{}", remove_duplicates(&mut nums));
}

输出:

5
7


81. 搜索旋转排序数组 II Search-in-rotated-sorted-array-II

已知存在一个按非降序排列的整数数组 nums ,数组中的值不必互不相同。

在传递给函数之前,nums 在预先未知的某个下标 k0 <= k < nums.length)上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ,请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ,则返回 true ,否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1:

输入:nums = [2,5,6,0,0,1,2], target = 0
输出:true

示例 2:

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

提示:

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -10^4 <= target <= 10^4

进阶:

  • 这是​搜索旋转排序数组​(题号33)的延伸题目,本题中的 nums  可能包含重复元素。
  • 这会影响到程序的时间复杂度吗?会有怎样的影响,为什么?

代码:

fn search(nums: &Vec<i32>, target: i32) -> bool {
    let (mut left, mut right) = (0, nums.len() - 1);
    while left <= right {
        let mid = left + (right - left) / 2;
        if nums[mid] == target {
            return true;
        }
        // 无法确定左右区间是否有序,只能缩小范围
        if nums[left] == nums[mid] && nums[mid] == nums[right] {
            left += 1;
            if right > left {
                right -= 1;
            }
        } else if nums[left] <= nums[mid] { // 左区间有序
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else { // 右区间有序
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    false
}

fn main() {
    let nums = vec![2, 5, 6, 0, 0, 1, 2];
    println!("{}", search(&nums, 0));
    println!("{}", search(&nums, 3));
}

输出:

true
false


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力! 

🌟 收藏,你的青睐是我努力的方向! 

评论,你的意见是我进步的财富!  

 主页:https://hannyang.blog.csdn.net/

Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II

Rust每日一练 专栏

(2023.5.16~)更新中...

Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II

Golang每日一练 专栏

(2023.3.11~)更新中...

Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II

Python每日一练 专栏

(2023.2.18~2023.5.18)暂停更

Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II

C/C++每日一练 专栏

(2023.2.18~2023.5.18)暂停更

Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II

Java每日一练 专栏

(2023.3.11~2023.5.18)暂停更文章来源地址https://www.toymoban.com/news/detail-478739.html

到了这里,关于Rust每日一练(Leetday0027) 单词搜索、删除重复项II、搜索旋转排序数组II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Rust每日一练(Leetday0024) 爬楼梯、简化路径、编辑距离

    目录 70. 爬楼梯 Climbing Stairs  🌟 71. 简化路径 Simplify Path  🌟🌟 72. 编辑距离 Edit Distance  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 假设你正在爬楼梯。需要  n  阶你才能到达楼顶。

    2024年02月13日
    浏览(39)
  • Rust每日一练(Leetday0031) 解码方法、复原 IP 地址

    目录 91. 解码方法  Decode Ways  🌟🌟 93. 复原 IP 地址 Restore IP Addresses  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 一条包含字母  A-Z  的消息通过以下映射进行了  编码  : 要  解码  已编码的消息,所有

    2024年02月09日
    浏览(35)
  • Rust每日一练(Leetday0022) 最小路径和、有效数字、加一

    目录 64. 最小路径和 Minimum Path Sum  🌟🌟 65. 有效数字 Valid Number  🌟🌟🌟 66. 加一 Plus One  🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给定一个包含非负整数的  m  x  n  网格  grid  ,请找

    2024年02月08日
    浏览(36)
  • Rust每日一练(Leetday0012) 首末位置、插入位置、有效数独

    目录 34. 查找元素的首末位置 Find-first-and-last-position-of-element-in-sorted-array  🌟🌟 35. 搜索插入位置 Search Insert Position  🌟 36. 有效的数独 Valid Sudoku  🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专

    2024年02月09日
    浏览(45)
  • Rust每日一练(Leetday0029) 柱状图、最大矩形、扰乱字符串

    目录 84. 柱状图中最大的矩形 Largest-rectangle-in-histogram  🌟🌟🌟 85. 最大矩形 Maximal Rectangle  🌟🌟🌟 87. 扰乱字符串 Scramble String  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给定  n

    2024年02月09日
    浏览(46)
  • Golang每日一练(leetDay0102) 删除无效的括号、累加数

    目录 295. 数据流的中位数 Find-median-from-data-stream 🌟🌟🌟 301. 删除无效的括号 Remove Invalid Parentheses 🌟🌟🌟 306. 累加数 Additive Number 🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 中位数 是有

    2024年02月10日
    浏览(44)
  • Golang每日一练(leetDay0102) 数据流中位数、删除无效括号、累加数

    目录 295. 数据流的中位数 Find-median-from-data-stream 🌟🌟🌟 301. 删除无效的括号 Remove Invalid Parentheses 🌟🌟🌟 306. 累加数 Additive Number 🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 中位数 是有

    2024年02月12日
    浏览(52)
  • 【LeetCode-SQL每日一练】—— 196. 删除重复的电子邮箱

    🙋‍♂️大家好呀,我是 超梦 。大家可以叫我 小梦 ~ 小伙伴们都知道,不管是在学习中还是日常工作中,几乎天天是要跟 数据库 打交道的,为了更好的操作数据库,我们的 SQL知识储备 是必不可少的。想要掌握好SQL,那少不了每天的练习与学习。接下来小梦会带领小伙伴

    2023年04月08日
    浏览(51)
  • Golang每日一练(leetDay0004)

    目录 10. 正则表达式匹配 Regular Expression Matching  🌟🌟🌟 11. 盛最多水的容器 Container with most water  🌟🌟 12. 整数转罗马数字 Integer to Roman  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给你一个字符串 

    2023年04月08日
    浏览(51)
  • Golang每日一练(leetDay0052)

    目录 153. 寻找旋转排序数组中的最小值 Find Minimum In Rotated Sorted Array  🌟🌟 154. 寻找旋转排序数组中的最小值 II Find Minimum In Rotated Sorted Array II  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 已知一个长度为

    2024年02月02日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包