前言
本文是題主準(zhǔn)備面試時記錄下的筆記整理而來悠就，稍顯粗陋，還請各位擼友勿噴哈堂鲜！
Topic
-
目錄
-
目標(biāo)
- 熟練使用常用數(shù)據(jù)結(jié)構(gòu)的基本操作
- 加深對常用算法與技巧的理解
- 面試
-
參考
- 《程序員面試金典》
- 《劍指offer》
- Leetcode
- 《結(jié)構(gòu)之法 --July》
數(shù)組篇
左旋字符串/數(shù)組
1.問題描述
- 給定一字符串
- 將串的前若干個元素移到串的尾部
2.例子
- "abcdefg",2 ==> "cdefgab"
3.Coding感想
- 關(guān)于三步反轉(zhuǎn)法
- 對每段都做了兩次反轉(zhuǎn)倚评，因此每段仍然有序
- 段與段之間反轉(zhuǎn)了順序
4.解決方案
(1) 暴力移位（By一個字符）
A. A[0]存入臨時變量tmp
B. 數(shù)組其余元素放到數(shù)組后面
C. 旋轉(zhuǎn)幾位散休，就執(zhí)行幾次A,B
(2) 三步反轉(zhuǎn)法
A. 要旋轉(zhuǎn)的位置將串分為兩段
B. 將這兩段分別進(jìn)行反轉(zhuǎn)
C. 對整個字符串反轉(zhuǎn)
Remove Duplicates
1.問題描述
- 定一個已排序數(shù)組
- 刪除重復(fù)元素
- 返回刪除后數(shù)組的長度
- 不能使用額外空間
2.例子
A = [1, 1, 2] ==> len = 2, A = [1, 2]
3.解決方案
-
兩個游標(biāo)遍歷數(shù)組
- 兩個游標(biāo)指向的值不等
- 游標(biāo)相鄰，則兩個游標(biāo)向前移動一位
- 游標(biāo)不相鄰园匹，快游標(biāo)值賦給慢游標(biāo)的下一位后雳刺，快游標(biāo)進(jìn)一位
- 相等則快游標(biāo)前進(jìn)一位
- 兩個游標(biāo)指向的值不等
-
STL-distance()-unique()
- distance(A, unique(A, A + n))
- 注意引入#include<algorithm>
- unique()
- 作用
- 刪除所有相鄰的重復(fù)元素
- 不是真的刪除，而是放后面
- 先排序后才能用unique（）
- 原型：unique（begin裸违，end）
- 返回去重后最后一個元素的地址
- 作用
- distance()
- 原型distance（begin, end）
- 返回兩參數(shù)間的間隔長度
-
STL-泛型模板-upper_bound()
- upper_bound()
- 定義
- 返回的在前閉后開區(qū)間查找的關(guān)鍵字的上界
- 返回一個迭代器掖桦，指向鍵值> key的第一個元素
- 原型：upper_bound(first, last, value)
- 定義
- lower_bound()
- 返回一個迭代器，指向鍵值>= key的第一個元素
- upper_bound()
4.Coding遇到的問題
gdb display 可否同時設(shè)置多個變量供汛？
-
使用string的append方法
- 原型：append(const value_type ptr)
- append( string s )
- append( "hello" )
- append(const char* c)
- 與 “strA + strB”的對比
- append更加靈活
- append效率相對較低
- 相關(guān)鏈接
- c++拼接字符串效率比較
- 原型：append(const value_type ptr)
-
char* c =new char(10); c = "hello";
- 如此賦值會有隱患: hello是常量枪汪，但c指向的是變量
- 應(yīng)定義為const char*
- 相關(guān)鏈接
- warning：deprecated conversion from string constant to 'char *'
常量指針 vs 指針常量
參見《effective c++》思維導(dǎo)圖筆記-
獲取數(shù)組的長度
- sizeof(array) / sizeof(array[0])
- 無法判斷數(shù)組是否為空涌穆，因?yàn)閿?shù)組一旦定義，里面便有隨機(jī)值
5.代碼示例：
/*************************************************************************
> File Name: 1_1.rm_duplicates_from_sorted_Array.cpp
> Description:
（1）給一個已排序數(shù)組
（2）刪除重復(fù)元素
（3）返回刪除后數(shù)組的長度
（4）不能使用額外空間料饥，必須用常量內(nèi)存
（5）A = [1,1,2] ==> len = 2, A = [1, 2]
> Conclusion:
（1）注重代碼優(yōu)化
（2）簡化判定條件
（3）快慢游標(biāo)遍歷數(shù)組
> Author: rh_Jameson
> Created Time: 2014年12月02日 星期二 12時03分26秒
************************************************************************/
#include<iostream>
#include<algorithm>
using namespace std;
//-------------------------------------原始版本：Acceped--------------------------------//
int removeDuplicatesOrigin(int A[],int n)
{
int p = 0,q = 1; //游標(biāo)p蒲犬，q
if(n <= 0) //判空 & 非法
{
return 0;
}
if(n == 1) //數(shù)組只有一個元素的情況
{
return 1;
}
while(q != n)
{
if(A[p] != A[q] && p == q - 1) //A[p]和A[q]不等且p，q相鄰時岸啡，p原叮，q向前移動一位
{
p++;
q++;
}
else if(A[p] != A[q] && p != q - 1) //A[p]和A[q]不等且p,q不相鄰時
{
p++; //p向前移動一位
A[p] = A[q]; //將數(shù)組A下標(biāo)q的值賦給下標(biāo)p的值
q++; //q向前移動一位
}
else if(A[p] == A[q]) //A[p]和A[q]相等時，q向前移動一位
{
q++;
}
}
return p + 1; //返回處理后數(shù)組的長度
}
//-------------------------------------優(yōu)化版本：Acceped--------------------------------//
int removeDuplicatesOptimize(int A[],int n)
{
int p = 0,q = 1; //游標(biāo)p巡蘸，q
if(n <= 0) //判空 & 非法
{
return 0;
}
while(q != n)
{
if(A[p] != A[q]) //A[p]和A[q]不等時奋隶，p，q向前移動一位
{
A[++p] = A[q]; //巧妙優(yōu)化悦荒，p唯欣，q相鄰，A[q] = A[q],p,q不相鄰搬味，A[p] = A[q]
q++;
}
else if(A[p] == A[q]) //A[p]和A[q]相等時境氢，q向前移動一位
{
q++;
}
}
return p + 1; //返回處理后數(shù)組的長度
}
//-------------------------------------優(yōu)化版本2：Acceped--------------------------------//
int removeDuplicatesOptimize(int A[],int n)
{
int p = 0,q = 1; //游標(biāo)p，q
if(n <= 0) //判空 & 非法
{
return 0;
}
while(q != n)
{
if(A[p] != A[q]) //A[p]和A[q]不等時碰纬，p萍聊，q向前移動一位
{
A[++p] = A[q]; //巧妙優(yōu)化，p悦析，q相鄰寿桨，A[q] = A[q],p,q不相鄰，A[p] = A[q]
}
q++;
}
return p + 1; //返回處理后數(shù)組的長度
}
//==================================參考代碼1：Accepted==================================//
/*
* 該參考代碼與上面優(yōu)化版本的代碼思路一直强戴，不再贅釋
*/
int removeDuplicatesLeetcode1(int A[],int n)
{
if(n <= 0)
{
return 0;
}
int index = 0;
for(int i = 1; i < n; ++i)
{
if( A[index] != A[i] )
{
A[++index] = A[i];
}
}
return index + 1;
}
//==================================參考代碼2：Accepted==================================//
/*
* 使用STL distance(),unique()方法
*/
int removeDuplicatesLeetcode2(int A[],int n)
{
return distance(A, unique(A, A + n) );
}
int main()
{
//removeDuplicates
int A[3] = {1,1,2};
cout << removeDuplicatesLeetcode2(A, 3) << endl;
}
Remove Duplicates II
1.問題描述
- 給一個已排序數(shù)組
- 刪除重復(fù)次數(shù)大于2的元素
- 返回刪除后數(shù)組的長度
- 不能使用額外空間
2.例子
A = [1,1,1,2,2,3] ==> A.len = 5, A = [1,1,2,2,3]
3.Coding感想
- 條件語句優(yōu)化技能有待提高
4.解決方案
- 思路與上一道差不多亭螟，區(qū)別是引入計(jì)數(shù)變量
- 在第一次出現(xiàn)重復(fù)時，做相應(yīng)處理
- 多次重復(fù)骑歹，只移動快游標(biāo)
- A[p] != A[q]時预烙，注意將count重置為1
5.代碼實(shí)例：
/*************************************************************************
> File Name: 1_2.remove_duplicatesII.cpp
> Description:
（1）給一個已排序數(shù)組
（2）刪除重復(fù)次數(shù)大于2的元素
（3）返回刪除后數(shù)組的長度
（4）不能使用額外空間
（5）A = [1,1,1,2,2,3] ==> A.len = 5,A = [1,1,2,2,3]
> Conclusion:
（1）條件語句優(yōu)化技能有待提高
（2）策略：
A.思路與上一道差不多，區(qū)別是引入計(jì)數(shù)變量
B.在第一次出現(xiàn)重復(fù)時道媚，做相應(yīng)處理
C.多次重復(fù)默伍，只移動快游標(biāo)
D.A[p] != A[q]時，注意將count重置為1
> Author: rh_Jameson
> Created Time: 2014年12月03日 星期三 13時23分00秒
************************************************************************/
#include<iostream>
using namespace std;
//============================原始版本：Accepted,88 ms==================================//
int removeDuplicates(int A[],int n)
{
int count = 1; //計(jì)數(shù)變量
int index = 0; //慢游標(biāo)
if(n <= 0) //判空衰琐，非法
{
return 0;
}
for(int i = 1; i < n; ++i)
{
/*慢游標(biāo)指向值不等于快游標(biāo)指向值時*/
if(A[index] != A[i])
{
A[++index] = A[i]; //慢游標(biāo)前進(jìn)一位也糊，將快游標(biāo)指向值賦給慢游標(biāo)指向值
if(count != 1) //重置count
{
count = 1;
}
}
/*慢游標(biāo)指向值等于快游標(biāo)指向值時*/
else if(count == 1) //第一次出現(xiàn)重復(fù)的處理
{
count++;
A[++index] = A[i];
}
else //多次重復(fù)的處理
{
count++;
}
}
return index + 1;
}
//============================優(yōu)化條件語句版本：Accepted,116 ms==================================//
int removeDuplicatesOpt(int A[],int n)
{
int count = 1; //計(jì)數(shù)變量
int index = 0; //慢游標(biāo)
if(n <= 0) //判空，非法
{
return 0;
}
for(int i = 1; i < n; ++i)
{
if(A[index] == A[i])
{
count++;
if(count == 2)
{
A[++index] = A[i];
}
}
else
{
A[++index] = A[i];
count = 1;
}
}
return index + 1;
}
//============================參考版本：Accepted,68ms===============================//
int removeDuplicates(int A[], int n) {
if(n <= 2) //小于2直接返回n
{
return n;
}
//直接從下標(biāo)2開始遍歷
int index = 2;
for(int i = 2; i < n; ++i)
{
if(A[index - 2] != A[i])
{
A[index++] = A[i];
}
}
return index;
}
int main()
{
int A[4] ={1,1,1,1};
// int A[6] = {1,1,1,2,2,3};
cout << removeDuplicatesOpt(A, 4);
return 0;
}
Search In Rotated Sorted Array
1.問題描述
- 給定一旋轉(zhuǎn)數(shù)組（數(shù)組分兩段羡宙，各段均已排序）
- 段邊界點(diǎn)不確定
- 給一關(guān)鍵字狸剃，查詢數(shù)組中是否有該關(guān)鍵字
- 有則返回下標(biāo)，無則返回-1
- 假設(shè)數(shù)組中無重復(fù)元素
- A = [4,5,6,7,0,1,2]
2.例子
A = [4,5,6,7,0,1,2], 搜索關(guān)鍵字：0 ==> return 4
3.解決方案
- 兩次折半策略
- 折半獲取邊界最大值
- 判斷關(guān)鍵字在哪一段順序序列上
- 在目標(biāo)順序序列上折半查找關(guān)鍵字
- 一次折半策略
- 折半mid,比較A[mid]和target
- mid將數(shù)組分兩段狗热，判斷target是在哪一段
- target沒找到或first與last未交錯钞馁，循環(huán)A,B
4.Coding遇到的問題與感想
- 折半查找算法實(shí)現(xiàn)需注意的細(xì)節(jié)及優(yōu)化
- 兩種情況[0,n),[0,n]
- right=n-1 => while(left <= right) => right=middle-1
- right=n => while(left < right) => right=middle;
- 注意（min + max）/ 2溢出問題
- 折半改變min或max時虑省，防止出現(xiàn)死循環(huán)
- 兩種情況[0,n),[0,n]
- 我想的策略復(fù)雜度為logn，但要兩次折半來實(shí)現(xiàn)僧凰，非最優(yōu)解法
5.代碼示例：
/*************************************************************************
> File Name: 1_3.search_in_rotated_sorted_array.cpp
> Description:
（1）給定一旋轉(zhuǎn)數(shù)組（數(shù)組分兩段探颈，各段均已排序）
（2）段邊界點(diǎn)不確定
（3）給一關(guān)鍵字，查詢數(shù)組中是否有該關(guān)鍵字
（4）有則返回下標(biāo)训措，無則返回-1
（5）假設(shè)數(shù)組中無重復(fù)元素
（6）A = [4,5,6,7,0,1,2]
> Conclusion:
（1）策略：
A.折半獲取邊界最大值
B.判斷關(guān)鍵字在哪一段順序序列上
C.在目標(biāo)順序序列上折半查找關(guān)鍵字
（2）折半查找算法實(shí)現(xiàn)需注意的細(xì)節(jié)及優(yōu)化
A.兩種情況[0,n),[0,n]
B.注意（min + max）/ 2溢出問題
C.折半改變min或max時伪节，防止出現(xiàn)死循環(huán)
（3）該策略復(fù)雜度為logn，但要兩次折半來
實(shí)現(xiàn)绩鸣，非最優(yōu)解法
（4）一次折半優(yōu)化策略：
A.折半mid,比較A[mid]和target
B.mid將數(shù)組分兩段怀大，判斷target是在哪一段
C.target沒找到或first與last未交錯，循環(huán)A,B
> Author: rh_Jameson
> Created Time: 2014年12月03日 星期三 16時16分33秒
************************************************************************/
#include<iostream>
using namespace std;
//====================兩次折半版本：Accepted呀闻，16 ms=========================//
//折半查找關(guān)鍵字
int binary_search(int A[], int &max, int &min, int target)
{
int mid;
while(min <= max)
{
//mid = (min + max) / 2; //常規(guī)折半
mid = min + (max - min) / 2; //防止（min + max）溢出
if(target > A[mid])
{
min = mid + 1;
}
else if(target < A[mid])
{
max = mid - 1;
}
else
{
return mid;
}
}
return -1;
}
//折半獲取邊界最大值leftMax
int binary_getMax(int A[], int &front, int &rear)
{
int mid;
while(front <= rear)
{
//mid = (front + rear) / 2;
mid = front + (rear - front) / 2; //防止溢出
//找到最大值，直接跳出循環(huán)
if( A[mid] > A[mid - 1] && A[mid] > A[mid + 1] ||
front == rear - 1 && A[mid] > A[mid + 1] ||
front == mid && rear == mid )
{
break;
}
//mid非最大值，進(jìn)行折半
if(A[mid] >= A[front])
{
front = mid + 1;
}
else
{
rear = mid - 1;
}
}
return mid;
}
int search(int A[],int n,int target)
{
if(n <= 0) //處理非法
{
return -1;
}
int front = 0;
int rear = n - 1;
//初始化邊界值
int leftMin = 0, leftMax, rightMin, rightMax = n-1;
leftMax = binary_getMax(A, front, rear); //折半獲取邊界最大值
rightMin = leftMax + 1;
//判斷目標(biāo)值在哪一段順序序列上
if(target > A[leftMin]) //折半查找需封裝
{
return binary_search(A, leftMax,leftMin,target); //折半查找左側(cè)順序序列
}
else if(target == A[leftMin])
{
return leftMin;
}
else
{
return binary_search(A, rightMax, rightMin, target); //折半查找右側(cè)順序序列
}
}
//==========================一次折半版本：Accepted,40ms===============================//
//折半mid,比較target，A[mid]
int searchOnce(int A[], int n, int target)
{
int first = 0, mid, last = n - 1;
while(first <= last) //first唆迁，last未交錯唐责，繼續(xù)循環(huán)
{
mid = first + (last - first) / 2;
if(target == A[mid])
{
return mid;
}
if(target == A[first])
{
return first;
}
else if(A[mid] >= A[first])
{
if(target > A[first] && target < A[mid])
{
last = mid - 1;
}
else
{
first = mid + 1;
}
}
else
{
if(target < A[first] && target > A[mid])
{
first = mid + 1;
}
else
{
last = mid - 1;
}
}
}
return -1;
}
int main()
{
//int A[7] = {4,5,6,7,0,1,2};
int A[2] = {3,1};
cout << searchOnce(A, 2, 1) << endl;
return 0;
}
1_6.matrix_rotate
1.問題描述
- N * N矩陣表示圖像
- 每像素4字節(jié)
- 實(shí)現(xiàn)圖像旋轉(zhuǎn)90度
- 不用額外空間
2.策略一：四點(diǎn)輪換法
- 遍歷行數(shù)N/2
- 將行中每個結(jié)點(diǎn)旋轉(zhuǎn)到相應(yīng)位置
- 通過tmp變量進(jìn)行輪換
- 時間復(fù)雜度O（N^2）
3.策略二：對角線替換
- 交換對角線兩邊元素
- 對每一列元素進(jìn)行逆置
- 逆時針旋轉(zhuǎn)繞橫軸
- 順時針旋轉(zhuǎn)繞縱軸
4.生成隨機(jī)數(shù)
- srand((int)time(NULL));
- r = rand() % 10
5.傳遞二維數(shù)組參數(shù)
- int a[10][10]
- int a[][10]
- 不可以用二級指針
- int** a;
- 相關(guān)網(wǎng)址：http://www.wutianqi.com/?p=1822
6.代碼示例：
/*************************************************************************
> File Name: Solution.h
> Description:
（1）問題描述
A.N * N矩陣表示圖像
B.每像素4字節(jié)
C.實(shí)現(xiàn)圖像旋轉(zhuǎn)90度
D.不用額外空間
> Conclusion:
（1）策略一：四點(diǎn)輪換法
A.遍歷行數(shù)N/2
B.將行中每個結(jié)點(diǎn)旋轉(zhuǎn)到相應(yīng)位置
C.通過tmp變量進(jìn)行輪換
D.時間復(fù)雜度O（N^2）
（2）策略二：對角線替換
A.交換對角線兩邊元素
B.對每一列元素進(jìn)行逆置
a.逆時針旋轉(zhuǎn)繞橫軸
b.順時針旋轉(zhuǎn)繞縱軸
（3）生成隨機(jī)數(shù)
A.srand((int)time(NULL));
B.r = rand() % 10
（4）傳遞二維數(shù)組參數(shù)
A.int a[10][10]
B.int a[][10]
C.不可以用二級指針
a.int** a;
b.相關(guān)網(wǎng)址：
http://www.wutianqi.com/?p=1822
> Author: rh_Jameson
> Created Time: 2014年12月14日 星期日 12時17分44秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
class Solution {
public:
void printMatrix(const int n,int a[][7]){
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
cout << a[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
//=======================矩陣旋轉(zhuǎn)：四點(diǎn)輪換法,Accepted=======================//
//逆時針旋轉(zhuǎn)90度
void matrix_rotate_reverse(const int n, int a[][7]){
if(n == 0){
cout << "空矩陣" << endl;
}
int col = n, len = n;
int midline = n / 2, tmp;
for(int i = 0; i < midline; ++i){
for(int j = i; j < col - 1 - i; ++j){
tmp = a[j][i];
a[j][i] = a[i][len - 1 - j];
a[i][len -1 -j] = a[len - 1 - j][len - 1 - i];
a[len - 1 - j][len - 1 - i] = a[len - 1 - i][j];
a[len - 1 - i][j] = tmp;
}
}
printMatrix(n, a);
}
//順時針旋轉(zhuǎn)90度
void matrix_rotateByExchg(const int n, int a[][7]){
if(n == 0){
cout << "空矩陣" << endl;
}
int col = n, len = n;
int midline = n / 2, tmp;
for(int i = 0; i < midline; ++i){
for(int j = i; j < col - 1 - i; ++j){
tmp = a[i][j];
a[i][j] = a[len - 1 - j][i];
a[len - 1- j][i] = a[len - 1 - i][len - 1 - j];
a[len - 1 - i][len - 1 - j] = a[j][len - 1 - i];
a[j][len - 1 - i] = tmp;
}
}
printMatrix(n, a);
}
//=====================矩陣旋轉(zhuǎn)：對角線替換,Accepted======================//
void swap(int &a, int &b){
int tmp;
tmp = a;
a = b;
b = tmp;
}
void matrix_rotate(const int n, int a[][7]){
int len = n;
//對角線兩側(cè)元素互換
for(int i = 0; i < len; ++i){
for(int j = i; j < len; ++j){
swap(a[i][j],a[j][i]);
}
}
//根據(jù)縱軸逆置元素
for(int line = 0; line < len; ++line){
for(int first = 0,last = len - 1; first < last; ++first, --last){
swap(a[line][first],a[line][last]);
}
}
printMatrix(n, a);
}
};
#endif
1_7.matrix_clear_zero
1.問題描述：
- M * N矩陣
- 若某個元素為0嚷兔，所在行與列均清零
2.解決策略
- 策略一：哈希表保存清零的行與列
- 遍歷矩陣
- 用map記錄元素為0的行, 列
- 對相應(yīng)行清零
- 相應(yīng)列清零
- 策略二：復(fù)用0行0列記錄要清零的行同衣，列
- 不用額外空間秫逝，直接復(fù)用0行0列的空間
- 判斷0行跟0列是否存在0金蜀，bool標(biāo)志真/假
- 遍歷其余行跟列
- 元素為0的行列护桦，存到0行0列的相應(yīng)位置
- 遍歷清零
- 檢測bool標(biāo)志贪染，判斷0行0列是否存在0
- 存在，則對0行 / 0列清零
3.Coding遇到的問題
- vector<vector<int> > m：
- 相當(dāng)于二維數(shù)組 m[i][j]
- 行數(shù)：m.size()
- 列數(shù)：m[0].size()
- m[i][j]形式涡拘，通過2個for循環(huán)可生成隨機(jī)矩陣
- vector形式不能生成
- 相關(guān)鏈接
- map & hashtable：
- C++ STL嚴(yán)格來說沒有實(shí)現(xiàn)哈希表結(jié)構(gòu)
- map底層是紅黑樹，訪問復(fù)雜度為logN
- 哈希表一般是常數(shù)時間訪問
- 性能：unordered_map > hash_map > map
- 需要有序關(guān)聯(lián)容器的話要用map
- 相關(guān)鏈接
- STL---hash_map
- c++ hash_map 詳細(xì)介紹
- map / hash_map / unordered_map 性能測試
- C++ STL中哈希表 hash_map介紹
4.代碼示例：
/*************************************************************************
> File Name: Solution.h
> Description:
（1）問題描述：
A.M * N矩陣
B.若某個元素為0据德，所在行與列均清零
> Conclusion:
（1）策略一：哈希表保存清零的行與列
A.遍歷矩陣
B.用map記錄元素為0的行, 列
C.對相應(yīng)行清零
D.相應(yīng)列清零
（2）策略二：復(fù)用0行0列記錄要清零的行鳄乏，列
A.不用額外空間跷车，直接復(fù)用0行0列的空間
B.判斷0行跟0列是否存在0，bool標(biāo)志真/假
C.遍歷其余行跟列
D.元素為0的行列橱野，存到0行0列的相應(yīng)位置
E.遍歷清零
F.檢測bool標(biāo)志朽缴，判斷0行0列是否存在0
G.存在，則對0行 / 0列清零
（3）vector<vector<int> > m：
A.相當(dāng)于二維數(shù)組 m[i][j]
B.行數(shù)：m.size()
C.列數(shù)：m[0].size()
D.m[i][j]形式水援，通過2個for循環(huán)可生成隨機(jī)矩陣
E.vector形式不能生成
F.http://blog.csdn.net/qingdujun/article/details/17499871
（4）map & hashtable：
A.C++ STL嚴(yán)格來說沒有實(shí)現(xiàn)哈希表結(jié)構(gòu)
B.map底層是紅黑樹密强，訪問復(fù)雜度為logN
C.哈希表一般是常數(shù)時間訪問
D.性能：unordered_map > hash_map > map
E.需要有序關(guān)聯(lián)容器的話要用map
F.http://blog.chinaunix.net/uid-20384806-id-3055333.html
G.http://yiluohuanghun.blog.51cto.com/3407300/1086355
H.http://blog.csdn.net/peter_teng/article/details/8433395
I.http://www.cnblogs.com/waytofall/archive/2012/06/04/2534386.html
> Author: rh_Jameson
> Created Time: 2014年12月14日 星期日 22時24分29秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
//#include<hash_map>
using namespace std;
class Solution {
public:
void printMatrix(int matrix[1][2]){
int col_num = 2;
int line_num = 1;
for(int i = 0; i < line_num; ++i){
for(int j = 0; j < col_num; ++j){
cout << matrix[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
//=====================map保存要清0的行與列：Accepted=====================//‘
void setZeroesByHash(int matrix[5][4]) {
int col_num = 4;
int line_num = 5;
map<int, int> col_map, line_map; //記錄清零的行與列
int col_zero = 0, line_zero = 0; //清零行，列的個數(shù)
//遍歷記錄清零的行與列
for(int i = 0; i < line_num; ++i){
for(int j = 0; j < col_num; ++j){
if(matrix[i][j] == 0){
line_map[++line_zero] = i;
col_map[++col_zero] = j;
}
}
}
int tmp;
//所在行清零
while(line_zero > 0){
tmp = line_map[line_zero];
for(int i = 0; i < col_num; ++i){
matrix[tmp][i] = 0;
}
--line_zero;
}
printMatrix(matrix);
//所在列清零
while(col_zero > 0){
tmp = col_map[col_zero];
for(int i = 0; i < line_num; ++i){
matrix[i][tmp] = 0;
}
--col_zero;
}
printMatrix(matrix);
}
//=====================不用額外空間實(shí)現(xiàn)：Accepted=====================//
void setZeroes(int matrix[1][2]) {
int col_num = 2;
int line_num = 1;
bool flag_line = false,flag_col = false;
//判斷第零行是否有0
for(int i = 0; i < col_num; ++i){
if(matrix[0][i] == 0){
flag_line = true;
break;
}
}
//判斷第零列是否有0
for(int i = 0; i < line_num; ++i){
if(matrix[i][0] == 0){
flag_col = true;
break;
}
}
//將出現(xiàn)0的行蜗元，列記錄到第0行和第零列上
for(int i = 1; i < line_num; ++i){
for(int j = 1; j < col_num; ++j){
if(matrix[i][j] == 0){
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
//清零
for(int i = 1; i < line_num; ++i){
for(int j = 1; j < col_num; ++j){
if(matrix[i][0] == 0 || matrix[0][j] == 0){
matrix[i][j] = 0;
}
}
}
//判斷第零行,第零列是否要清零
if(flag_line){
for(int i = 0; i < col_num; ++i){
matrix[0][i] = 0;
}
}
if(flag_col){
for(int i = 0; i < line_num; ++i){
matrix[i][0] = 0;
}
}
printMatrix(matrix);
}
};
#endif
