首页 > 其他分享 >【LBLD】二维数组的花式遍历技巧

【LBLD】二维数组的花式遍历技巧

时间:2023-04-03 15:46:54浏览次数:41  
标签:p2 lower 遍历 int bound LBLD left 花式 size

【LBLD】二维数组的花式遍历技巧

151. 反转字符串中的单词

  • 思路:
    • 反转整个字符串
    • 然后反转每个单词
class Solution {
public:
    string reversePartString(string s, int a, int b) {
        if (a < 0 || b >= s.size()) {
            cout << "索引错误!" << endl;
        }
        int p1 = a, p2 = b;
        char c = 0;
        while (p1 < p2) {
            c = s[p1];
            s[p1] = s[p2];
            s[p2] = c;
            p1++; p2--;
        }
        return s;
    }

    string reverseWords(string s) {
        // 清除空格
        int p1 = 0, p2 = 0;
        while (p2 < s.size()) {
            if (s[p2] != ' '
                || (p2-1 >= 0 && p2+1 < s.size()) && s[p2-1] != ' ') {
                s[p1] = s[p2];
                p1++;
                p2++;
            }
            else while (p2 < s.size() && s[p2] == ' ') {
                p2 ++;
            }
        }
        if (s[p1-1] == ' ') p1--;
        while (p1 < s.size()) {
            s.erase(p1);
        }
        // 反转整个字符串
        s = reversePartString(s, 0, s.size()-1);
        // 反转每个单词
        p1 = 0; p2 = 0;
        while (p2 < s.size()) {
            while (s[p2] != ' ' && p2 < s.size()) {
                p2++;
            }
            s = reversePartString(s, p1, p2-1);
            p1 = ++p2;
        }
        return s;
    }
};

48. 旋转图像

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        // 对角
        int temp = -1;
        for (int a=0; a<matrix.size(); a++) {
            for (int b=a; b<matrix.size(); b++) {
                temp = matrix[a][b];
                matrix[a][b] = matrix[b][a];
                matrix[b][a] = temp;
            }
        }
        // 垂直
        int p1 = 0, p2 = matrix.size()-1;
        for (int a=0; a<matrix.size(); a++) {
            p1 = 0; p2 = matrix.size()-1;
            while (p1 < p2) {
                temp = matrix[a][p1];
                matrix[a][p1] = matrix[a][p2];
                matrix[a][p2] = temp;
                p1++; p2--;
            }
        }
    }
};

54. 螺旋矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int left_bound = -1, right_bound = n;
        int upper_bound = -1, lower_bound = m;
        vector<int> res;
        while (res.size() < m * n) {
            // 从左向右
            for (int i=left_bound+1; i<right_bound; i++) {
                res.push_back(matrix[upper_bound+1][i]);
            }
            upper_bound++;
            if (upper_bound+1 >= lower_bound) break;
            // 从上向下
            for (int i=upper_bound+1; i<lower_bound; i++) {
                res.push_back(matrix[i][right_bound-1]);
            }
            right_bound--;
            if (left_bound+1 >= right_bound) break;
            // 从右向左
            for (int i=right_bound-1; i>left_bound; i--) {
                res.push_back(matrix[lower_bound-1][i]);
            }
            lower_bound--;
            if (upper_bound+1 >= lower_bound) break;
            // 从下向上
            for (int i=lower_bound-1; i>upper_bound; i--) {
                res.push_back(matrix[i][left_bound+1]);
            }
            left_bound++;
            if (left_bound+1 >= right_bound) break;
        }
        return res;
    }
};

59. 螺旋矩阵 II

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));
        int i = 1;
        int i_bound = n*n;
        int left = 0, right = n-1;
        int upper = 0, lower = n-1;
        while (i <= i_bound) {
            for (int j=left; j<=right; j++) {
                res[upper][j] = i;
                i++;
            }
            upper++;
            if (i > i_bound) break;
            for (int j=upper; j<=lower; j++) {
                res[j][right] = i;
                i++;
            }
            right--;
            for (int j=right; j>=left; j--) {
                res[lower][j] = i;
                i++;
            }
            lower--;
            for (int j=lower; j>=upper; j--) {
                res[j][left] = i;
                i++;
            }
            left++;
        }
        return res;
    }
};

标签:p2,lower,遍历,int,bound,LBLD,left,花式,size
From: https://www.cnblogs.com/yangxuanzhi/p/17283233.html

相关文章

  • LeetCode 145 二叉树的后序遍历
    LeetCode|145.二叉树的后序遍历给你一棵二叉树的根节点root,返回其节点值的后序遍历。示例1:1\2/3输入:root=[1,null,2,3]输出:[3,2,1]示例2:输入:root=[]输出:[]示例3:输入:root=[1]输出:[1]提示:树中节点的数目在范围[0,10......
  • 2023-04-02 桥和割点以及图的遍历树
    桥和割点以及图的遍历树1什么是桥定义对于无向图,如果删除了一条边,整个图联通分量数量就会变化,则这条边称为桥(Bridge)。桥意味着图中最脆弱的关系应用交通系统比如两个城市上海和南京仅通过长江大桥相连,如果长江大桥被毁坏了,那么两个城市就分开各自为战了社交网络......
  • 二叉树的前序遍历
    LeetCode|144二叉树的前序遍历给你二叉树的根节点root,返回它节点值的 前序 遍历。示例1:1\2/3输入:root=[1,null,2,3]输出:[1,2,3]示例2:输入:root=[]输出:[]示例3:输入:root=[1]输出:[1]示例4:1/2输入:root=......
  • PAT甲级真题1020.树的遍历
    翻译和代码思路:Acwing一个二叉树,树中每个节点的权值互不相同。现在给出它的后序遍历和中序遍历,请你输出它的层序遍历。输入格式第一行包含整数N,表示二叉树的节点数。第二行包含N个整数,表示二叉树的后序遍历。第三行包含N个整数,表示二叉树的中序遍历。输出格式输出一......
  • 102.二叉树的层序遍历
    给你一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)classTreeNode{public:intval;TreeNode*left;TreeNode*right;TreeNode():val(NULL),left(nullptr),right(nullptr){}TreeNode(intx):val(x),left(nullptr),rig......
  • 二叉树的前中后序遍历(非递归)
    classTreeNode{public:intval;TreeNode*left;TreeNode*right;TreeNode():val(NULL),left(nullptr),right(nullptr){}TreeNode(intx):val(x),left(nullptr),right(nullptr){}};classSolution{public:vector<int>preorderTra......
  • day14| 94.二叉树的中序遍历;144.二叉树的前序遍历;145.二叉树的后序遍历
    94.二叉树的中序遍历 思路:1.找出重复的子问题这个重复的子问题是:先遍历左子树、再取根节点、最后遍历右子树2.确定终止条件当节点为空是,返回 代码如下:#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,......
  • jQuery遍历_02
       ......
  • jQuery遍历_01
         ......
  • Python遍历时删除元素问题(附深拷贝与浅拷贝介绍)
    问题有时候,我们希望用Python遍历一个列表(或其他可迭代对象),如果其中有我们不需要的元素就把它删除并继续遍历。如以下代码段,我们本希望打印1、3,可最后却只打印了1。a=[1,2,3]foriina:ifi==2:a.remove(i)else:print(i)分析其实,之所以......