算法题解-字符串+数组-CCI

一共三道题，两道数组+上次剩下的一道字符串。其中1、3题，有一定的难度，需要思考。

像素翻转

题目描述
有一副由NxN矩阵表示的图像，这里每个像素用一个int表示，请编写一个算法，在不占用额外内存空间的情况下(即不使用缓存矩阵)，将图像顺时针旋转90度。
给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于500，图像元素小于等于256。
测试样例：
[[1,2,3],[4,5,6],[7,8,9]],3
返回：[[7,4,1],[8,5,2],[9,6,3]]
思路：
这题有两种思路，难点还是在于不使用辅助空间。最容易想到的就是按层处理，每一层按照左->上，下->左，右->下，上->右的次序依次交换该行或列中的每一个元素，其中用临时变量保存第一个用来替换的元素。时间复杂度是
第二个思路就很巧妙，先将第i行和第n-i-1行交换，然后经过主对角线对称交换。但是复杂度相近。

class Transform {
public:
    vector<vector<int> > transformImage(vector<vector<int> > mat, int n) {
        // write code here
        /*
        分圈考虑，从最外圈开始
        按照左->上，下->左，右->下，上->右的次序依次交换元素
        一直到最内层
        */
        for(int i=0; i<n/2; i++) { //正在处理第几层
            for(int j=i; j<n-1-i; j++) { //第i圈有n-i个元素
                int tmp = mat[i][j];
                mat[i][j] = mat[n-j-1][i];//左->上
                mat[n-j-1][i] = mat[n-i-1][n-j-1];//下->左
                mat[n-i-1][n-j-1] = mat[j][n-i-1];//右->下
                mat[j][n-i-1] = tmp;//上->右
            }
        }
        return mat;
    }
};

清除行列

题目描述
请编写一个算法，若N阶方阵中某个元素为0，则将其所在的行与列清零。
给定一个N阶方阵int[]mat和矩阵的阶数n，请返回完成操作后的int[][]方阵(C++中为vector<vector><int>>)，保证n小于等于300，矩阵中的元素为int范围内。</int></vector></int></vector>
测试样例：
[[1,2,3],[0,1,2],[0,0,1]]
返回：[[0,0,3],[0,0,0],[0,0,0]]
思路：
这题不难，坑在于不能遇到0就直接置0，不然后面处理同行列元素后都是0。要先标记，遍历完全部的元素后置0。

class Clearer {
public:
    vector<vector<int> > clearZero(vector<vector<int> > mat, int n) {
        // write code here
        vector<bool> col(n, false);
        vector<bool> raw(n, false);
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(mat[i][j] == 0) {
                    col[i] = true;
                    raw[j] = true;
                }
            }
        }
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(col[i] || raw[j])
                    mat[i][j] = 0;
            }
        }
                
        return mat;
    }
};

翻转子串

题目描述
假定我们都知道非常高效的算法来检查一个单词是否为其他字符串的子串。请将这个算法编写成一个函数，给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成，要求只能调用一次检查子串的函数。
给定两个字符串s1,s2,请返回bool值代表s2是否由s1旋转而成。字符串中字符为英文字母和空格，区分大小写，字符串长度小于等于1000。
测试样例：
"Hello world","worldhello "
返回：false

"waterbottle","erbottlewat"
返回：true
思路：
这题表述的其实不太清楚，一开始没理解。其实表达的意思就是截取字符串放到字符串的结尾，截取的部分字符顺序不变。例如原字符串是ABCD，截取A部分放到BCD之后变成BCDA。判断是不是和原字符串的各部分相同就行了。
PS：是我见识太少了，旋转的意思就是循环左移。
思路很巧妙，把ABCD和自己拼接起来变成ABCDABCD，如果符合题意，那么“旋转”后的字符串一定是ABCDABCD的一个字串，这样一来，就变成了常见的寻找字串问题。可以直接用STL库中的find()方法。当然，自己写的话就要复现KMP算法了。

class ReverseEqual {
public:
    bool checkReverseEqual(string s1, string s2) {
        // write code here
        s1 = s1 + s1;
        if(s1.find(s2) != s1.npos)
            return true;
        else 
            return false; 
    }
};