AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

Rust每日一练(Leetday0016) 全排列I\II、旋转图像

2024-01-30 41
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： Rust每日一练(Leetday0016) 全排列I\II、旋转图像

46. 全排列 Permutations

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


示例 2：

输入：nums = [0,1]

输出：[[0,1],[1,0]]


示例 3：

输入：nums = [1]

输出：[[1]]


提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

代码： 回溯法

fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut res: Vec<Vec<i32>> = Vec::new();
    if nums.len() == 0 {
        return res;
    }
    let mut used: Vec<bool> = vec![false; nums.len()];
    fn backtrack(path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, nums: &Vec<i32>, used: &mut Vec<bool>) {
        if path.len() == nums.len() {
            let tmp = path.clone();
            res.push(tmp);
            return;
        }
        for i in 0..nums.len() {
            if !used[i] {
                used[i] = true;
                path.push(nums[i]);
                backtrack(path, res, nums, used);
                path.pop();
                used[i] = false;
            }
        }
    }
    backtrack(&mut Vec::new(), &mut res, &nums, &mut used);
    return res;
}
fn main() {
    println!("{:?}", permute(vec![1, 2, 3]));
    println!("{:?}", permute(vec![0, 1]));
    println!("{:?}", permute(vec![1]));
}

输出：

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

[[0, 1], [1, 0]]

[[1]]

代码2： 字典序法

fn permute(nums: &mut [i32]) -> Vec<Vec<i32>> {
    let mut res = vec![];
    if nums.len() == 1 {
            res.push(nums.to_vec());
            return res;
        }
    nums.sort();
    loop {
        let tmp = nums.to_vec();
        res.push(tmp);
        let (mut i, mut j) = (nums.len() - 2, nums.len() - 1);
        while i > 0 && nums[i] >= nums[i + 1] {
            i -= 1;
        }
        if i == 0 && nums[i] >= nums[i + 1] {
            break;
        }
        while nums[j] <= nums[i] {
            j -= 1;
        }
        nums.swap(i, j);
        nums[i + 1..].reverse();
    }
    res
}
fn main() {
    let mut nums = [1, 2, 3];
    println!("{:?}", permute(&mut nums));
    let mut nums = [0, 1];
    println!("{:?}", permute(&mut nums));
    let mut nums = [1];
    println!("{:?}", permute(&mut nums));
}

代码3： DFS

fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
    fn dfs(nums: &Vec<i32>, index: usize, p: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, used: &mut Vec<bool>) {
        if index == nums.len() {
            let temp = p.clone();
            res.push(temp);
            return;
        }
        for i in 0..nums.len() {
            if !used[i] {
                used[i] = true;
                p.push(nums[i]);
                dfs(nums, index + 1, p, res, used);
                p.pop();
                used[i] = false;
            }
        }
    }
    if nums.len() == 0 {
        return vec![];
    }
    let mut used: Vec<bool> = vec![false; nums.len()];
    let mut p: Vec<i32> = vec![];
    let mut res: Vec<Vec<i32>> = vec![];
    dfs(&nums, 0, &mut p, &mut res, &mut used);
    return res;
}
fn main() {
    println!("{:?}", permute(vec![1, 2, 3]));
    println!("{:?}", permute(vec![0, 1]));
    println!("{:?}", permute(vec![1]));
}

47. 全排列 II Permutations II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]

输出：

[[1,1,2],

[1,2,1],

[2,1,1]]


示例 2：

输入：nums = [1,2,3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

代码1：  回溯法

fn permute_unique(nums: Vec<i32>) -> Vec<Vec<i32>> {
    fn backtrack(path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, nums: &Vec<i32>, used: &mut Vec<bool>) {
        if path.len() == nums.len() {
            let tmp = path.clone();
            res.push(tmp);
            return;
        }
        for i in 0..nums.len() {
            if used[i] || (i > 0 && !used[i - 1] && nums[i] == nums[i - 1]) {
                continue;
            }
            used[i] = true;
            path.push(nums[i]);
            backtrack(path, res, nums, used);
            path.pop();
            used[i] = false;
        }
    }
    let mut nums_copy = nums.clone();
    nums_copy.sort();
    let mut used: Vec<bool> = vec![false; nums.len()];
    let mut path: Vec<i32> = vec![];
    let mut res: Vec<Vec<i32>> = vec![];
    backtrack(&mut path, &mut res, &nums_copy, &mut used);
    return res;
}
fn main() {
    println!("{:?}", permute_unique(vec![1, 1, 2]));
    println!("{:?}", permute_unique(vec![1, 2, 3]));
}

输出：

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

代码2：  字典序法

fn permute_unique(nums: &mut [i32]) -> Vec<Vec<i32>> {
    let mut res = vec![];
    if nums.is_empty() {
        return res;
    }
    nums.sort();
    let len = nums.len();
    let (mut i, mut j) = (len - 2, len - 1);
    loop {
        let tmp = nums.to_vec();
        res.push(tmp);
        while i > 0 && nums[i] >= nums[i + 1] {
            i -= 1;
        }
        if i == 0 && nums[i] >= nums[i + 1] {
            break;
        }
        while j > 0 && nums[j] <= nums[i] {
            j -= 1;
        }
        if nums[j] == nums[i] && j > i + 1 {
            continue;
        }
        nums.swap(i, j);
        nums[i + 1..].reverse();
        if i == 0 && j == 1 {
            break;
        }
        i = len - 2;
        j = len - 1;
    }
    res
}
fn main() {
    let mut nums = [1, 1, 2];
    println!("{:?}", permute_unique(&mut nums));
    let mut nums = [1, 2, 3];
    println!("{:?}", permute_unique(&mut nums));
}

代码3：  DFS

fn permute_unique(nums: &mut [i32]) -> Vec<Vec<i32>> {
    let mut res = vec![];
    if nums.is_empty() {
        return res;
    }
    let mut used = vec![false; nums.len()];
    let mut p = vec![];
    nums.sort();
    dfs(nums, 0, &mut p, &mut res, &mut used);
    res
}
fn dfs(nums: &[i32], index: usize, p: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, used: &mut [bool]) {
    if index == nums.len() {
        res.push(p.clone());
        return;
    }
    for i in 0..nums.len() {
        if !used[i] {
            if i > 0 && nums[i] == nums[i - 1] && !used[i - 1] {
                continue;
            }
            used[i] = true;
            p.push(nums[i]);
            dfs(nums, index + 1, p, res, used);
            p.pop();
            used[i] = false;
        }
    }
}
fn main() {
    let mut nums = [1, 1, 2];
    println!("{:?}", permute_unique(&mut nums));
    let mut nums = [1, 2, 3];
    println!("{:?}", permute_unique(&mut nums));
}
fn permute_unique(nums: Vec<i32>) -> Vec<Vec<i32>> {
    fn dfs(nums: &[i32], index: usize, p: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, used: &mut [bool]) {
        if index == nums.len() {
            res.push(p.clone());
            return;
        }
        for i in 0..nums.len() {
            if !used[i] {
                if i > 0 && nums[i] == nums[i - 1] && !used[i - 1] {
                    continue;
                }
                used[i] = true;
                p.push(nums[i]);
                dfs(nums, index + 1, p, res, used);
                p.pop();
                used[i] = false;
            }
        }
    }
    if nums.is_empty() {
        return vec![];
    }
    let mut nums_copy = nums.clone();
    nums_copy.sort();
    let mut res: Vec<Vec<i32>> = vec![];
    let mut used = vec![false; nums.len()];
    dfs(&nums_copy, 0, &mut vec![], &mut res, &mut used);
    res
}
fn main() {
    println!("{:?}", permute_unique(vec![1, 1, 2]));
    println!("{:?}", permute_unique(vec![1, 2, 3]));
}

48. 旋转图像 Rotate Image

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在

原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]

输出：[[7,4,1],[8,5,2],[9,6,3]]


示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]

输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]


提示：

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

代码1： 转置加翻转

先转置矩阵，然后翻转每一行即可得到顺时针旋转 90 度后的矩阵。

fn rotate(matrix: &mut Vec<Vec<i32>>) {
    let n = matrix.len();
    // 转置矩阵
    for i in 0..n {
        for j in i..n {
            let temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    // 翻转每一行
    for i in 0..n {
        for j in 0..n / 2 {
            let temp = matrix[i][j];
            matrix[i][j] = matrix[i][n - j - 1];
            matrix[i][n - j - 1] = temp;
        }
    }
}
fn main() {
    let mut matrix = vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]];
    rotate(&mut matrix);
    println!("{:?}", matrix);
    let mut matrix = vec![vec![5, 1, 9, 11], vec![2, 4, 8, 10], vec![13, 3, 6, 7], vec![15, 14, 12, 16]];
    rotate(&mut matrix);
    println!("{:?}", matrix);
}

输出：

[[7, 4, 1], [8, 5, 2], [9, 6, 3]]

[[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]

代码2： 分块翻转

将矩阵分成四个部分，并将每个部分按顺时针旋转 90 度。

fn rotate(matrix: &mut Vec<Vec<i32>>) {
    let n = matrix.len();
    // 转置矩阵
    for i in 0..n {
        for j in i..n {
            let temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    // 翻转每一行
    for i in 0..n {
        for j in 0..n / 2 {
            let temp = matrix[i][j];
            matrix[i][j] = matrix[i][n - j - 1];
            matrix[i][n - j - 1] = temp;
        }
    }
}
fn main() {
    let mut matrix = vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]];
    rotate(&mut matrix);
    println!("{:?}", matrix);
    let mut matrix = vec![vec![5, 1, 9, 11], vec![2, 4, 8, 10], vec![13, 3, 6, 7], vec![15, 14, 12, 16]];
    rotate(&mut matrix);
    println!("{:?}", matrix);
}

代码3： 对角线变换+水平翻转

将矩阵分成四个部分，并将每个部分按顺时针旋转 90 度。

fn rotate(matrix: &mut Vec<Vec<i32>>) {
    let row = matrix.len();
    if row <= 0 {
        return;
    }
    let column = matrix[0].len();
    // 对角线变换
    for i in 0..row {
        for j in i + 1..column {
            let temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    // 竖直轴对称翻转
    let half_column = column / 2;
    for i in 0..row {
        for j in 0..half_column {
            let temp = matrix[i][j];
            matrix[i][j] = matrix[i][column - j - 1];
            matrix[i][column - j - 1] = temp;
        }
    }
}
fn main() {
    let mut matrix = vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]];
    rotate(&mut matrix);
    println!("{:?}", matrix);
    let mut matrix = vec![vec![5, 1, 9, 11], vec![2, 4, 8, 10], vec![13, 3, 6, 7], vec![15, 14, 12, 16]];
    rotate(&mut matrix);
    println!("{:?}", matrix);
}

翻转+旋转原理C代码 

/*
* clockwise rotate 顺时针旋转
* first reverse up to down, then swap the symmetry
* 1 2 3      7 8 9      7 4 1
* 4 5 6 => 4 5 6 => 8 5 2
* 7 8 9      1 2 3      9 6 3
*/
void rotate(vector > &matrix) {
    reverse(matrix.begin(), matrix.end());
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = i + 1; j < matrix[i].size(); ++j)
            swap(matrix[i][j], matrix[j][i]);
    }
}
/*
* anticlockwise rotate 逆时针旋转
* first reverse left to right, then swap the symmetry
* 1 2 3      3 2 1      3 6 9
* 4 5 6 => 6 5 4 => 2 5 8
* 7 8 9      9 8 7      1 4 7
*/
void anti_rotate(vector > &matrix) {
    for (auto vi : matrix) reverse(vi.begin(), vi.end());
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = i + 1; j < matrix[i].size(); ++j)
                swap(matrix[i][j], matrix[j][i]);
        }
}

🌟每日一练刷题专栏🌟

✨持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！

🌟 收藏，你的青睐是我努力的方向！

✎ 评论，你的意见是我进步的财富！  

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

 Rust每日一练 专栏

（2023.5.16~）更新中...

Golang每日一练 专栏

（2023.3.11~）更新中...

Python每日一练 专栏

（2023.2.18~2023.5.18）暂停更

C/C++每日一练 专栏

（2023.2.18~2023.5.18）暂停更

Java每日一练 专栏

（2023.3.11~2023.5.18）暂停更


文章标签：
Java
Rust
C++
Python
Go
关键词：
Java字符串
Java统计
HannYang
目录
相关文章
喵手
|
19天前
|
存储 安全 Java
Java零基础-字符串详解
【10月更文挑战第18天】Java零基础教学篇，手把手实践教学！
喵手
95 60
土木林森
|
3月前
|
安全 Java API
【Java字符串操作秘籍】StringBuffer与StringBuilder的终极对决！
【8月更文挑战第25天】在Java中处理字符串时，经常需要修改字符串，但由于`String`对象的不可变性，频繁修改会导致内存浪费和性能下降。为此，Java提供了`StringBuffer`和`StringBuilder`两个类来操作可变字符串序列。`StringBuffer`是线程安全的，适用于多线程环境，但性能略低；`StringBuilder`非线程安全，但在单线程环境中性能更优。两者基本用法相似，通过`append`等方法构建和修改字符串。
土木林森
64 1
wljslmz
|
3月前
|
算法 Java
在 Java 中如何从第一个字符串中删除第二个字符串中存在的字符
【8月更文挑战第23天】
wljslmz
212 0
众所周知
|
9天前
|
缓存 算法 Java
本文聚焦于Java内存管理与调优，介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中，性能优化至关重要。本文聚焦于Java内存管理与调优，介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术，开发者可显著提升应用性能和稳定性。
众所周知
30 6
java冯坚持
|
1月前
|
Java 数据库
案例一：去掉数据库某列中的所有英文，利用java正则表达式去做，核心：去掉字符串中的英文
这篇文章介绍了如何使用Java正则表达式从数据库某列中去除所有英文字符。
java冯坚持
46 15
小强在此
|
1月前
|
Java
JAVA易错点详解(数据类型转换、字符串与运算符)
JAVA易错点详解(数据类型转换、字符串与运算符)
小强在此
50 4
刘大猫.
|
2月前
|
Java 数据库
java小工具util系列1：日期和字符串转换工具
java小工具util系列1：日期和字符串转换工具
刘大猫.
51 3
刘大猫.
|
2月前
|
SQL Java 索引
java小工具util系列2：字符串工具
java小工具util系列2：字符串工具
刘大猫.
18 2
bzf4tpxf3rljg
|
2月前
|
存储 移动开发 Java
java核心之字符串与编码
java核心之字符串与编码
bzf4tpxf3rljg
21 2
蓝易云
|
2月前
|
Java
Java实现：将带时区的时间字符串转换为LocalDateTime对象
通过上述方法，你可以将带时区的时间字符串准确地转换为 `LocalDateTime`对象，这对于处理不需要时区信息的日期和时间场景非常有用。
蓝易云
725 4

热门文章

最新文章

  • 1
    Rust 笔记：Rust 语言中使用 vector（向量）
  • 2
    Serverless时代Rust即将称王，详解C、Java、Go、Rust高并发背后的技术？
  • 3
    性能的极致,Rust的加持,Zed-Dev编辑器快速搭建Python3.10开发环境
  • 4
    Rust 大展拳脚的新兴领域：机密计算
  • 5
    Rust 笔记：Rust 语言中哈希结构（哈希映射，HashMap）、集合（哈希集，HashSet）及其使用
  • 6
    2021 年 Rust 生态版图调研报告 | 星辰大海（下篇）
  • 7
    使用Rust开发命令行工具
  • 8
    Rust vs Go:常用语法对比(十)（2）
  • 9
    【Rust中的所有权系统深入解析】A Deep Dive into Rust‘s Ownership System
  • 10
    Rust 开发命令行工具（上）（三）
  • 1
    java接口防爬虫
    129
  • 2
    day14：Java零基础-条件运算符
    40
  • 3
    Java并发编程中的锁机制与性能优化
    50
  • 4
    深入理解Java虚拟机：垃圾收集机制的演变与最佳实践
    50
  • 5
    《手把手教你》系列基础篇（九十五）-java+ selenium自动化测试-框架之设计篇-java实现自定义日志输出（详解教程）
    294
  • 6
    Java并发编程之线程池深度解析
    62
  • 7
    Java中的并发编程：从基础到高级
    64
  • 8
    Java并发编程中的线程安全性与性能优化
    55
  • 9
    《手把手教你》系列基础篇（九十四）-java+ selenium自动化测试-框架设计基础-POM设计模式实现-下篇（详解教程）
    46
  • 10
    Spring Boot框架在java领域的优势
    77

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计
  • Java编程入门
  • Java面向对象编程
  • Java高级编程

    • 相关电子书

    更多
  • Spring Cloud Alibaba - 重新定义 Java Cloud-Native
  • The Reactive Cloud Native Arch
  • JAVA开发手册1.5.0

    • 相关实验场景

    更多
  • 基于ECS搭建Java Web开发环境
  • 使用Aliyun Java Intializr进行项目开发
  • 搭建Java Web开发环境
  • 部署基于Dragonwell的Java运行环境
  • 阿里云平台上进行Java程序的编译与运行
    • 下一篇
    阿里云OSS设置跨域访问