一共三道題滥玷，兩道數(shù)組+上次剩下的一道字符串氏身。其中1、3題惑畴，有一定的難度蛋欣，需要思考。
像素翻轉(zhuǎn)
題目描述
有一副由NxN矩陣表示的圖像如贷，這里每個(gè)像素用一個(gè)int表示陷虎，請(qǐng)編寫(xiě)一個(gè)算法，在不占用額外內(nèi)存空間的情況下(即不使用緩存矩陣)杠袱，將圖像順時(shí)針旋轉(zhuǎn)90度泻红。
給定一個(gè)NxN的矩陣，和矩陣的階數(shù)N,請(qǐng)返回旋轉(zhuǎn)后的NxN矩陣,保證N小于等于500霞掺，圖像元素小于等于256。
測(cè)試樣例：
[[1,2,3],[4,5,6],[7,8,9]],3
返回：[[7,4,1],[8,5,2],[9,6,3]]
思路：
這題有兩種思路讹躯，難點(diǎn)還是在于不使用輔助空間菩彬。最容易想到的就是按層處理缠劝，每一層按照左->上，下->左骗灶，右->下惨恭，上->右的次序依次交換該行或列中的每一個(gè)元素，其中用臨時(shí)變量保存第一個(gè)用來(lái)替換的元素耙旦。時(shí)間復(fù)雜度是
第二個(gè)思路就很巧妙脱羡，先將第i行和第n-i-1行交換，然后經(jīng)過(guò)主對(duì)角線對(duì)稱交換免都。但是復(fù)雜度相近锉罐。
class Transform {
public:
vector<vector<int> > transformImage(vector<vector<int> > mat, int n) {
// write code here
/*
分圈考慮，從最外圈開(kāi)始
按照左->上绕娘，下->左脓规，右->下，上->右的次序依次交換元素
一直到最內(nèi)層
*/
for(int i=0; i<n/2; i++) { //正在處理第幾層
for(int j=i; j<n-1-i; j++) { //第i圈有n-i個(gè)元素
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;
}
};
清除行列
題目描述
請(qǐng)編寫(xiě)一個(gè)算法险领，若N階方陣中某個(gè)元素為0侨舆，則將其所在的行與列清零。
給定一個(gè)N階方陣int[]mat和矩陣的階數(shù)n绢陌，請(qǐng)返回完成操作后的int[][]方陣(C++中為vector<vector><int>>)挨下，保證n小于等于300，矩陣中的元素為int范圍內(nèi)脐湾。</int></vector></int></vector>
測(cè)試樣例：
[[1,2,3],[0,1,2],[0,0,1]]
返回：[[0,0,3],[0,0,0],[0,0,0]]
思路：
這題不難臭笆，坑在于不能遇到0就直接置0，不然后面處理同行列元素后都是0沥割。要先標(biāo)記耗啦，遍歷完全部的元素后置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;
}
};
翻轉(zhuǎn)子串
題目描述
假定我們都知道非常高效的算法來(lái)檢查一個(gè)單詞是否為其他字符串的子串机杜。請(qǐng)將這個(gè)算法編寫(xiě)成一個(gè)函數(shù)帜讲，給定兩個(gè)字符串s1和s2，請(qǐng)編寫(xiě)代碼檢查s2是否為s1旋轉(zhuǎn)而成椒拗，要求只能調(diào)用一次檢查子串的函數(shù)似将。
給定兩個(gè)字符串s1,s2,請(qǐng)返回bool值代表s2是否由s1旋轉(zhuǎn)而成。字符串中字符為英文字母和空格蚀苛，區(qū)分大小寫(xiě)在验，字符串長(zhǎng)度小于等于1000。
測(cè)試樣例：
"Hello world","worldhello "
返回：false
"waterbottle","erbottlewat"
返回：true
思路：
這題表述的其實(shí)不太清楚堵未，一開(kāi)始沒(méi)理解腋舌。其實(shí)表達(dá)的意思就是截取字符串放到字符串的結(jié)尾，截取的部分字符順序不變渗蟹。例如原字符串是ABCD块饺，截取A部分放到BCD之后變成BCDA赞辩。判斷是不是和原字符串的各部分相同就行了。
PS：是我見(jiàn)識(shí)太少了授艰，旋轉(zhuǎn)的意思就是循環(huán)左移辨嗽。
思路很巧妙，把ABCD和自己拼接起來(lái)變成ABCDABCD淮腾，如果符合題意糟需，那么“旋轉(zhuǎn)”后的字符串一定是ABCDABCD的一個(gè)字串，這樣一來(lái)谷朝，就變成了常見(jiàn)的尋找字串問(wèn)題洲押。可以直接用STL庫(kù)中的find()方法徘禁。當(dāng)然诅诱，自己寫(xiě)的話就要復(fù)現(xiàn)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;
}
};
