美文网首页
LeetCode Z 字形变换 rust

LeetCode Z 字形变换 rust

作者: liaozhiyuan | 来源:发表于2022-06-22 22:50 被阅读0次
    1. 题目:
      https://leetcode.cn/problems/zigzag-conversion/
      将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。
      比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:
    P   A   H   N
    A P L S I I G
    Y   I   R
    

    之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"。
    请你实现这个将字符串进行指定行数变换的函数:
    string convert(string s, int numRows);

    1. 思路:
    • 这道题的根本是计算Z字型的数组序列。
      也就是当遍历一个字符串的时候,如何计算出它需要填充到的数组坐标。
      这个坐标特征是:
      (0,0), (1,0), (2,0), (1,1), (0,2), (1,2), (2,2), (1,3), (0,4), (1,4), (2,4), (1,5), (0,6), (1,6)
      可以由此推算:y坐标一直不变,直到x自增到最后一排
      然后x开始自减,y开始自增,直到x自减到第一排,由此循环。
      也就是说x要从0下降至row行,再从row上升到0行,完成一次循环。则循环的步长是[0, 2(row-1)]。在x下降时,y坐标不变,在x上升时,y坐标自增。
    • 源码中,我们定义来一个ZConvert 结构来记录row到初始值,并且维护后续的迭代序列。当然也可以将ZConvert构造成一个迭代器用impl Iterator的方式来更优雅的遍历这个坐标序列。
    • 在源码中,我们使用map的方式,将String映射为一个Point序列:Vec<Point>.由此我们就完成了对字符的坐标标记工作。后续的points.sort_by是为了得到以多维数组顺序索引的序列。我们使用了自定义的compare函数的方式来比较他们的坐标。当然如果以空间换时间的方法,是可以预先定义好二维数组,并且将具体的每一个char直接填入的。这里的sort方法实际上是一个额外的负担。
      提交结果:

    执行用时:4 ms, 在所有 Rust 提交中击败了78.24%的用户
    内存消耗:2.2 MB, 在所有 Rust 提交中击败了61.77%的用户
    通过测试用例:
    1157 / 1157

    源码:

    use std::cmp::Ordering::*;
    #[derive(Debug)]
    struct Point {
        alph: char,
        x: i32,
        y: i32,
    }
    
    struct ZConvert {
        mid: i32,
        x: i32,
        y: i32,
    }
    
    impl ZConvert {
        fn new(row: i32) -> Self {
            ZConvert {
                mid: row - 1,
                x: 0,
                y: 0,
            }
        }
        fn get_next_coordinate(&mut self) -> (i32, i32) {
            if self.mid == 0 {
                self.y += 1;
                return (self.x,self.y)
            }
            let x: i32 = self.x % (2 * self.mid);
            self.x += 1;
            if x < self.mid {
                return (x, self.y);
            } else {
                self.y += 1;
                return (2 * self.mid - x, self.y - 1);
            }
        }
    }
    
    impl Solution {
        pub fn convert(s: String, num_rows: i32) -> String {
            let mut z = ZConvert::new(num_rows);
            let mut points = s
                .chars()
                .map(move |alph| {
                    let (x, y) = z.get_next_coordinate();
                    Point {
                        alph: alph,
                        x: x,
                        y: y,
                    }
                })
                .collect::<Vec<Point>>();
              points.sort_by(|p1, p2| {
                if p1.x < p2.x {
                    return Less;
                } else if p1.x > p2.x {
                    return Greater;
                } else {
                    if p1.y > p2.y {
                        return Greater;
                    } else if p1.y < p2.y {
                        return Less;
                    } else {
                        return Equal;
                    }
                }
            });
            return points.into_iter().map(|p| p.alph).collect::<String>();
        }
    }
    

    相关文章

      网友评论

          本文标题:LeetCode Z 字形变换 rust

          本文链接:https://www.haomeiwen.com/subject/pgtpvrtx.html