【Day19】LeetCode算法刷题（附带解题思路、代码注释详细） 【777. 在LR字符串中交换相邻字符】 【54. 螺旋矩阵】

class Solution {
    public boolean canTransform(String start, String end) {
        int n = start.length();    //获取字符串长度，方便遍历
        int i = 0,j = 0;           //用i表示start字符串下标，用j表示end字符串下标

        while(i < n && j < n){     //同时遍历
            while(i < n && start.charAt(i) == 'X'){//跳过start字符串中的‘X’
                ++i;
            }
            while(j < n && end.charAt(j) == 'X'){  //跳过end字符串中的‘X’
                ++j;
            }

            if(i < n && j < n){
                //忽略掉‘X’字符发现剩下的字符不对应，说明无法通过交换相邻字符获得
                if(start.charAt(i) != end.charAt(j)){ 
                    return false;
                }
//当我们按照前面的步骤遍历，根据规则：一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。
//当start字符串遍历到L或者R，都因该是XL或RX，而end字符串是LX或XR
//所以当start遍历到L，下标i应该 大于等于 end字符串的下标j，因为start中XL的`L`在`X`之后
//所以当start遍历到R，下标i应该 小于等于 end字符串的下标j，因为start中RX的`R`在`X`之前
//所以遇到不符合上述描述的情况，搜可以返回false了
                char ch = start.charAt(i);
                if(ch == 'L' && i < j || ch == 'R' && i > j){
                    return false;
                }
                ++i;++j;
            }
        }
        //当我们遍历到最后，一个字符串已经遍历完成，剩下一个字符串遍历到最后一个元素
        //我们按照上述的操作推演一下，就知道这最后一个元素会是'X'，否则返回false
        while(i < n && i < j){
            if(start.charAt(i) != 'X')
            return false;
            ++i;
        }
        while(j < n && j < i){
            if(end.charAt(j) != 'X')
            return false;
            ++j;
        }
        //两个字符串遍历完无异常，就说明start可以通过交换相邻字符获得end，返回true
        return true;
    }
}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();       //创建集合，记录顺时针螺旋顺序

        //如果矩阵为空或不含元素，返回空集合
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) 
        return list;

        //获取矩阵的长度rows与高度cols
        int rows = matrix.length;
        int cols = matrix[0].length;
        //定义一个标记矩阵flag，与matrix大小一致，用于标记相同位置上被遍历过的元素
        boolean[][] flag = new boolean[rows][cols];
        //定义一个用于翻转矩阵的二维数组
        //第一行代表向右遍历
        //第二行代表向下遍历
        //第三行代表向左遍历
        //第四行代表向上遍历
        int[][] move = {{0,1},{1,0},{0,-1},{-1,0}};
        //记录当前行、当前列和遍历方向的下标index
        int row = 0,col = 0,index = 0;

        for(int i = 0;i < rows*cols;++i){
            //开始遍历，标记遍历过的位置
            list.add(matrix[row][col]);
            flag[row][col] = true;

            //记录下一位置的行下标和列下标
            int nextRow = row + move[index][0];
            int nextCol = col + move[index][1];

            //如果下一个位置越界或者被遍历过
            if(nextRow < 0 || nextRow >= rows ||
               nextCol < 0 || nextCol >= cols ||
               flag[nextRow][nextCol]){
                   //翻转矩阵进行螺旋遍历
                   index = (index+1)%4;
               }
            
            //向后一个位置挪动
            row += move[index][0];
            col += move[index][1];
            
        }
        return list; //返回按照顺时针螺旋顺序存放元素的集合
        
    }
}