最近有空閒著就刷點Leetcode題目做一做，發現有些題目還是挺有意思，挺tricky的。下面這三道題，每一道題初看起來都是so easy！但是再細分析起來，它們都有些小技巧，不能走尋常思路，而是要針對性的運行一些小技巧。
一、圖像旋轉問題
初看起來，圖像旋轉其實是圖像幾何變換中一個非常常規的操作。其實就是根據“線性代數”中的方法，將原像素矩陣乘以一個旋轉變換矩陣就可以實現圖像的任意角度旋轉。這一點可以參考我的著作《數字圖像處理原理與實踐（MATLAB版）》中的“3.6 圖像的旋轉”。當然，這是一種通用的算法，它可以實現圖像的任意角度旋轉。但是本題中特別點明“in-place”，下面是維基百科給出的解釋：
In computer science, an in-place algorithm is an algorithm which transforms input using a data structure with a small amount of extra storage space. The input is usually overwritten by the output as the algorithm executes.
說白了，就是要求空間占用最小。所以通用的做法就行不通了。仔細觀察一個像素矩陣旋轉90度，不難發現其中的規律：結果矩陣其實是原矩陣沿水平軸做鏡像翻轉，再沿主對角線翻轉。例如
11 12 13 14 23 24 25 26 23 19 15 11
15 16 17 18 19 20 21 22 24 20 16 12
19 20 21 22 → 15 16 17 18 → 25 21 17 13
23 24 25 26 11 12 13 14 26 22 18 14
最後給出示例代碼如下。
class Solution {
public:
void swap(int& a, int& b)
{
int tmp;
tmp = b;
b = a;
a = tmp;
}
void rotate(vector >& matrix) {
if (matrix.empty()) return;
int n = matrix.size(), i = 0, tmp;
for (; i < n/2; ++i) {
for (int j = 0; j < n; ++j)
swap(matrix[i][j], matrix[n-1-i][j]) ;
}
i = 0;
for (; i < n; ++i) {
for (int j = 0; j < i; ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
};
二、2的冪次問題
這道題考察的是位操作。不妨來觀察一下2的次方數的二進制寫法的特點：
1 2 4 8 16 ....
1 10 100 1000 10000 ....
發現規律了嗎？易見，如果一個數是2的次方數的話，那麼它的二進數必然是最高位為1，其它都為0。所以你可以
每次判斷最低位是否為1，然後向右移位，最後統計1的個數即可判斷是否是2的次方數。但我們給出一種更簡便的方法，只需一行代碼就可以達成：如果將原數減1的話，則最高位會降一位，其余為0的位現在都為變為1，那麼我們把兩數相與，就會得到0，用這個性質也能來解題。
下面是示例代碼。
class Solution {
public:
bool isPowerOfTwo(int n) {
return (n > 0) && (!(n & (n - 1)));
}
};
三、主元素問題
這道題沒有復雜度要求，所以如果僅僅是解決問題來說，這道題的解題方法不下三種。最最簡單的，你或許會想到：遍歷數組中的每一個元素，然後用另外一張Table來記錄每一個不同元素出現的次數，然後從這張表中找到想要的結果。現在這種方法的時間復雜度是O(n)，但空間復雜度也是O(n)。能否設計一種線性時間復雜度的算法，而不占用額外的空間呢？Boyer和Moore在下面這部著作中提出了一種非常有效的算法——Linear Time Majority Vote Algorithm.
MJRTY - A Fast Majority Vote Algorithm, with R.S. Boyer. In R.S. Boyer (ed.), Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1991, pp. 105-117.
Boyer和Moore合作的另外一個著名算法就是大名鼎鼎的 BM 模式匹配算法。盡管KMP名聲也很大，但現實中使用的更多的模式匹配算法都是基於BM的演進算法。
二人給出的Vote Algorithm描述如下：
Sweep down the sequence starting at the pointer position shown above.
When sweeping, maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.
When we move the pointer forward over an element e:
When we are done, the current candidate is the majority element, if there is a majority.
簡單點講，就是按順序掃描一個串，最開始計數器置為0，並保存一個current candidate，當遇到一個相同的元素，計數器就+1，遇到不同的元素，計數器就-1。如果計數器為0了，就將current candidate置為當前所描到的元素e。根據這個規則當掃描完成後，所得之結果就是Majority Element. 例如
Step1:
A A A C C B B C C C B C C
^
?:0
Step2:
A A A C C B B C C C B C C
^
A:1
Step3:
A A A C C B B C C C B C C
^
A:2
Step4:
A A A C C B B C C C B C C
^
A:3
Step5:
A A A C C B B C C C B C C
^
A:2
Step6:
A A A C C B B C C C B C C
^
A:1
Step7:
A A A C C B B C C C B C C
^
?:0
Step8:
A A A C C B B C C C B C C
^
B:1
（我們省略了後續的步驟）繼續下去，最終就會得到結果C。
當然，該算法有效的前提是，Majority Element確實存在。
下面是示例代碼。
class Solution {
public:
int majorityElement(vector& nums) {
int elem = 0;
int count = 0;
for(int i = 0; i < nums.size(); i++) {
if(count == 0) {
elem = nums[i];
count = 1;
}
else {
if(elem == nums[i])
count++;
else
count--;
}
}
return elem;
}
};
