前言
本文是题主准备面试时记录下的笔记整理而来，稍显粗陋，还请各位撸友勿喷哈！
Topic
-
目标
- 熟练使用常用数据结构的基本操作
- 加深对常用算法与技巧的理解
- 面试
-
参考
- 《程序员面试金典》
- 《剑指offer》
- Leetcode
- 《结构之法 --July》
字符串篇
1_1.judge_char_unique_in_str
1.问题描述：
- 判断字符串中字符是否唯一
- 不使用额外数据结构（自定义数据结构）
2.解决策略
-
策略一：
- 根据字符的ASCII值进行排序
- 相邻索引比较
-
策略二：
- 定义bool类型数组，初始化置0
- 遍历字符串的每一字符
- 在数组相应位置，置1
- 如果出现对1置1的情况，返回false
-
策略三：
- 思路同二，换成位操作
- bool数组换成int bit[8]
- int ==> 32位
- 8 * 32 = 256
- str[i] / 32获取数组下标
- str[i] % 32获取偏移量
3.coding遇到的问题
- 相关头文件
- memset() ==> <cstring> / <string.h>
- a.原型：memset（void *s int ch, size_t n）
- b.例： memset(bit, 0, sizeof(bit))
- calloc() ==> <cstdlib>
- a.例：
(bool *)calloc(256, sizeof(bool));
- a.例：
- malloc() == <cstdlib>
- memset() ==> <cstring> / <string.h>
- 三整数a,b,c排序：
- judge a > b, y==>swap()
- judge a > c, y==>swap()
- judge b > c, y==>swap()
- 判断字符串是否为空的方法：
- s.empty()
- s == ""
- s.length() / s.size() == 0
- 动态数组初始化：
- g++编译器会自动初始化为0或NULL
- 其他变一起可能不会，需memset()
4.代码示例：
/*************************************************************************
> File Name: Solution.h
> Description:
（1）问题描述：
A.判断字符串中字符是否唯一
B.不使用额外数据结构（自定义数据结构）
> Conclusion:
（1）策略一：
A.根据字符的ASCII值进行排序
B.相邻索引比较
（2）策略二：
A.定义bool类型数组，初始化置0
B.遍历字符串的每一字符
C.在数组相应位置，置1
D.如果出现对1置1的情况，返回false
（3）策略三：
A.思路同二，换成位操作
B.bool数组换成int bit[8]
a.int ==> 32位
b.8 * 32 = 256
C.str[i] / 32获取数组下标
D.str[i] % 32获取偏移量
（4）相关头文件
A.memset() ==> <cstring> / <string.h>
a.原型：memset（void *s int ch, size_t n）
b.例： memset(bit, 0, sizeof(bit))
B.calloc() ==> <cstdlib>
a.例：
(bool *)calloc(256, sizeof(bool));
C.malloc() == <cstdlib>
(5) 三整数a,b,c排序：
A.judge a > b, y==>swap()
B.judge a > c, y==>swap()
C.judge b > c, y==>swap()
(6)判断字符串是否为空的方法：
A.s.empty()
B.s == ""
C.s.length() / s.size() == 0
(7)动态数组初始化：
A.g++编译器会自动初始化为0或NULL
B.其他变一起可能不会，需memset()
> Author: rh_Jameson
> Created Time: 2014年12月09日 星期二 10时49分53秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include<cstring> //memset
#include<cstdlib> //calloc/malloc
using namespace std;
class Solution {
public:
//================Bool数组位操作版===============//
bool Is_unique_str(string &s){
if(s.empty()){ //判空
return true;
}
int bit[8]; //8个整形变量，共256位
memset(bit, 0, sizeof(bit));
for(string::iterator i = s.begin(); i < s.end(); ++i){
int index = (int) *i / 32; //获取相应数组下标
int shift = (int) *i % 32; //获取相应偏移位数
if(bit[index] & 1 << shift){
return false;
}
bit[index] |= 1<< shift;
}
return true;
}
//================Bool数组STL形式版===============//
bool Is_unique_strSTL(string &s){
if(s.empty())
{
return true;
}
//memset置0
//bool flag[256];
//memset(flag,0,sizeof(flag));
//calloc置0
//bool* flag = (bool *)calloc(256, sizeof(bool));
//new,自动初始化置0，但有些编译器不自动初始化
bool* flag = new bool[256];
//bool* flag = new bool[256]();
for(string::iterator i = s.begin(); i < s.end(); ++i){
int tmp = (int) *i;
if(flag[tmp] == 0){
flag[tmp] = 1;
}
else{
return false;
}
}
delete[] flag;
return true;
}
//=====================Bool数组原始版=========================//
bool Is_unique_strOrigin(string &s){
if(s.empty())
{
return true;
}
bool flag[256];
memset(flag,0,sizeof(flag));
int len = s.size();
for(int i = 0; i < len; ++i){
int tmp = (int)s[i];
if(flag[tmp] == 0){
flag[tmp] = 1;
}
else{
return false;
}
}
return true;
}
//================字符排序版（nlogn）==================//
bool Is_unique_str_bySort(string &s){
if(s.empty()){
return true;
}
sort(&s[0],&s[0] + s.size());
int index = 0;
int len = s.size();
for(int i = 1; i < len; ++i){
if(s[index] == s[i]){
return false;
}
index++;
}
return true;
}
};
#endif
1_2.reverse_str
1.问题描述：
- 翻转一个NULL结尾的字符串
- "abcd" => "dcba"
2.解决策略
- 策略一：首尾索引交换
- 遍历字符获得尾下标
- 首尾两两交换
- 策略二：单索引法
- strlen()获取长度 再模2，赋给mid
- 遍历[0,mid)
- swap(i,n - i - 1)
3.coding遇到的问题
-
交换变量的方法：
- 求和交换
- 抑或交换
- 简洁美观，无需临时变量
- 编译效率无提升
- swap同一引用变量时，有bug
- swap(a, a) => a变为0
- 临时变量交换
-
空字符串处理：
- *str == "" or str == NULL or !str都不行
- 因为str本身有值，是一个内存地址
- 改为：str[0] == '\\0' / NULL 或 !str[0]
-
结束函数：
- return;
- exit();
- 某些平台下，return无法结束
4.代码示例：
/*************************************************************************
> File Name: Solution.h
> Description:
（1）问题描述：
A.翻转一个NULL结尾的字符串
B."abcd" => "dcba"
> Conclusion:
（1）策略一：首尾索引交换
A.遍历字符获得尾下标
B.首尾两两交换
（2）策略二：单索引法
A.strlen()获取长度 再模2，赋给mid
B.遍历[0,mid)
C.swap(i,n - i - 1)
（3）交换变量的方法：
A.求和交换
B.抑或交换
a.简洁美观，无需临时变量
b.编译效率无提升
c.swap同一引用变量时，有bug
d.swap(a, a) => a变为0
C.临时变量交换
（4）空字符串处理：
A. *str == "" or str == NULL or !str都不行
B. 因为str本身有值，是一个内存地址
C. 改为：str[0] == '\0' / NULL 或 !str[0]
（5）结束函数：
A.return;
B.exit();
C.某些平台下，return无法结束
> Author: rh_Jameson
> Created Time: 2014年12月09日 星期二 17时00分06秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
class Solution {
public:
void reverseBy2Index(char* str); //g++下传入只能是char[],而不能是char*
void reverse(char* str);
//通过抑或交换
void swapByXor(char &a, char &b);
//通过求和交换
void swapBySum(char &a, char &b);
//通过临时变量交换
void swapByTmp(char &a, char &b);
};
/*
* 省去临时变量，简洁美观，但效率木有提升
* swap（a，a）交换同一引用变量会出现bug
* 交换完，a变为0
*/
void Solution::swapByXor(char &a, char &b){
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
void Solution::swapBySum(char &a, char &b){
a = a + b;
b = a - b;
a = a - b;
}
void Solution::swapByTmp(char &a ,char &b){
char tmp = a;
a = b;
b = tmp;
}
//===========================一个指针版本=============================//
void Solution::reverse(char* str){
//空字符串处理
if(!str[0]){
cout << "空字符串！" << endl;
return;
}
int len = strlen(str);
int mid = len / 2;
for(int i = 0; i < mid; ++i){
swapBySum(str[i],str[len - i - 1]); //i 与 len - i - 1对应
}
cout << str << endl;
}
//============================首尾指针交换版=========================//
void Solution::reverseBy2Index(char* str){
/*
*空字符数组判空：
*str == "" or str == NULL or !str都不行
*因为str本身有值，是一个内存地址
*改为：str[0] == '\0' / NULL 或 !str[0]
*/
//空字符串处理
if(!str[0]){
cout << "空字符串！" << endl;
return;
}
int last = 0;
//遍历获取尾元素下标
while(str[last] != '\0'){
++last;
}
--last; //移去null结尾的字符
int first = 0;
int tmp;
//反转
while(first < last){
//swapByXor(str[first++], str[last--]);
swapBySum(str[first++], str[last--]);
//swapByTmp(str[first++], str[last--]);
}
cout << str << endl;
}
#endif
1_3.IsAnagrams
1.问题描述：
- 判断两个字符串是否是变位词
- 变位词定义：
- 单词字符，出现次数相同
- 位置不同
- "abcd" & "bcda" => true
2.coding遇到的问题
- STL sort()
- sort(begin,end)
- C++强制转换方法：
- static_cast<int>(obj);
- C++的string与char*的不同：
- string不能用指针访问
- *(str + i)，该访问方式报错
- 只能如此访问str[i]
- char*两种方式都行:
- str[i] & *(str + i)
- string不能用指针访问
3.解决策略
-
策略一（Wrong）：Bool数组
- 遍历strFrom每个字符
- 在Bool数组相应位置置1
- 遍历strTo每个字符
- 判断每个字符在bool数组中是否置1
- 不是，返回false
- 错误原因：为考虑重复元素，
- 如：baad & abbd => false
-
策略二：int数组
- 思路同一
- 一起遍历strFrom，strTo
- 每个字符，strFrom操作 + 1，strTp - 1
- 遍历int数组，如果为0，就返回true
- 最后一轮遍历费时间，如果是Unicode的话
-
策略三：排序
- strFrom跟strTo分别排序
- 再来一轮遍历，比较两者是否一样
-
策略四：int数组2
- 遍历strFrom
- strFrom每个字符，在int数组相应位置 + 1
- 遍历strTo
- strTo每个字符，在int数组相应位置 - 1
- 1后，判断值是否小于0，小于则返回false
4.代码示例：
/*************************************************************************
> File Name: Solution.h
> Description:
（1）问题描述：
A.判断两个字符串是否是变位词
B.变位词定义：
a,单词字符，出现次数相同
b.位置不同
C."abcd" & "bcda" => true
> Conclusion:
（1）策略一（Wrong）：Bool数组
A.遍历strFrom每个字符
B.在Bool数组相应位置置1
C.遍历strTo每个字符
D.判断每个字符在bool数组中是否置1
E.不是，返回false
F.错误原因：为考虑重复元素，
G.如：baad & abbd => false
（2）策略二：int数组
A.思路同一
B.一起遍历strFrom，strTo
C.每个字符，strFrom操作 + 1，strTp - 1
D.遍历int数组，如果为0，就返回true
E.最后一轮遍历费时间，如果是Unicode的话
（3）策略三：排序
A.strFrom跟strTo分别排序
B.再来一轮遍历，比较两者是否一样
（4）策略三：int数组2
A.遍历strFrom
B.strFrom每个字符，在int数组相应位置 + 1
C.遍历strTo
D.strTo每个字符，在int数组相应位置 - 1
E.- 1后，判断值是否小于0，小于则返回false
（5）STL sort()
A.sort(begin,end)
（6）C++强制转换方法：
A.static_cast<int>(obj);
（7）C++的string与char*的不同：
A.string不能用指针访问
a.*(str + i)，该访问方式报错
b.只能如此访问str[i]
B.char*两种方式都行:
a.str[i] & *(str + i)
> Author: rh_Jameson
> Created Time: 2014年12月10日 星期三 14时16分09秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
class Solution {
public:
bool IsAnagramsOrigin(string strFrom,string strTo);
bool IsAnagrams(string strFrom,string strTo);
bool IsAnagramsByIntArray(string strFrom,string strTo);
bool IsAnagramsBySort(string strFrom,string strTo);
};
//=============int数组优化版：Correct，空间开销适度=================//
bool Solution::IsAnagrams(string strFrom, string strTo){
if(strFrom.size() != strTo.size()){
return false;
}
int *flag = new int[256]();
//有些编译器对动态数组不会自动初始化，需手动置0
memset(flag, 0, sizeof(*flag));
int len = strFrom.size();
int index;
for(int i = 0; i < len; ++i){
index = static_cast<int>(strFrom[i]); //改c++强制转换
*(flag + index) += 1;
}
for(int i = 0; i< len; ++i){
index = static_cast<int>(strTo[i]);
*(flag + index) -= 1;
if(*(flag + index) < 0 ){
return false;
}
}
return true;
}
//===================排序版：时间nlogn，无需额外空间===================//
bool Solution::IsAnagramsBySort(string strFrom,string strTo){
if(strFrom.size() != strTo.size()){
return false;
}
sort( &strFrom[0], &strFrom[0] + strFrom.size() );
sort( &strTo[0], &strTo[0] + strTo.size() );
if(strFrom == strTo){
return true;
}
else{
return false;
}
}
//==================int数组版：Correct，空间开销大=====================//
bool Solution::IsAnagramsByIntArray(string strFrom, string strTo){
if(strFrom.size() != strTo.size()){
return false;
}
int *flag = new int[256]();
//有些编译器对动态数组不会自动初始化，需手动置0
memset(flag, 0, sizeof(*flag));
int len = strFrom.size();
int index,index2;
for(int i = 0; i < len; ++i){
index = static_cast<int>(strFrom[i]); //改c++强制转换
index2 = static_cast<int>(strTo[i]);
*(flag + index) += 1;
*(flag + index2) -= 1;
}
for(int i = 0; i< 256; ++i){
if(*(flag + i) != 0 ){ //数组全为0，则两者是变位词
return false;
}
}
return true;
}
//===================bool数组原始版：忽略重复元素，Wrong！==================//
bool Solution::IsAnagramsOrigin(string strFrom, string strTo){
if(strFrom.size() != strTo.size()){
return false;
}
bool *flag = new bool[256]();
//有些编译器对动态数组不会自动初始化，需手动置0
memset(flag, 0, sizeof(*flag));
int len = strFrom.size();
int index;
for(int i = 0; i < len; ++i){
//int index = (int) ( *(strFrom + i) ); //与char*不同，string中无法通过*(str + i)来访问
index = (int) strFrom[i]; //改c++强制转换
*(flag + index) = true;
}
for(int i = 0; i< len; ++i){
index = (int) strTo[i];
if(*(flag + index) != true){
return false;
}
}
return true;
}
#endif
1_4.str_replace_space
1.问题描述：
- 将字符串中的所有空格替换为%20
- 前提：首尾空格去除
- 不用额外空间
2.策略一：空格替换 & 移位
- 去除首尾空格 & 判空
- 遍历空格数目
- 重置字符串的大小，以及首尾iterator
- 遍历移位 & 替换
3.策略二：使用STL的replace方法
- 去除首尾空格 & 判空
- 遍历替换replace（pos, num, obj）
4.消除首尾空格关键代码：
- s.erase(0, s.find_first_not_of(' '))
- s.erase(s.find_last_not_of(' ') + 1, s.size() - 1);
- 不能写成erase（s.begin(),s.find_first_not_of(' ')）
- find_first_not_of()返回类型为：size_t,而非iterator
- find_last_not_of同样遵循C，D
5.resize（）原型：
- s.resize(size, "c")
- 例：s = "abc"; s.resiz(5,"d") ==> s = "abcdd"
6.代码示例：
/**********************************************************************************
> File Name: Solution.h
> Description:
(1)问题描述：
A.将字符串中的所有空格替换为%20
B.前提：首尾空格去除
C.不用额外空间
> Conclusion:
(1)策略一：空格替换 & 移位
A.去除首尾空格 & 判空
B.遍历空格数目
C.重置字符串的大小，以及首尾iterator
D.遍历移位 & 替换
(2)策略二：使用STL的replace方法
A.去除首尾空格 & 判空
B.遍历替换replace（pos, num, obj）
(3)消除首尾空格关键代码：
A. s.erase(0, s.find_first_not_of(' '))
B. s.erase(s.find_last_not_of(' ') + 1, s.size() - 1);
C.不能写成erase（s.begin(),s.find_first_not_of(' ')）
D.find_first_not_of()返回类型为：size_t,而非iterator
E.find_last_not_of同样遵循C，D
(4)resize（）原型：
A.s.resize(size, "c")
B.例：s = "abc"; s.resiz(5,"d") ==> s = "abcdd"
> Author: rh_Jameson
> Created Time: 2014年12月11日 星期四 09时26分22秒
**********************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
class Solution {
public:
//=====================使用stl中的相关方法========================//
string replace_space(string s){
if(s[0] == ' '){
s.erase(0, s.find_first_not_of(' '));
}
if(s[s.size() - 1] == ' '){
s.erase(s.find_last_not_of(' ') + 1, s.size() - 1);
}
int len = s.size();
for(int i = 1; i < len; ++i){
if(s[i] == ' '){
s.replace(i,1,"%20");
}
}
return s;
}
//========================空格替换 & 移位========================//
string replace_spaceOrigin(string s){
string::iterator first_iter = s.begin();
string::iterator last_iter = s.end() - 1;
//消除首尾空格
if(*first_iter == ' '){
//不能写成erase（s.begin(),s.find_first_not_of(' ')）
s.erase(0, s.find_first_not_of(' ')); //改' '
}
if(*last_iter == ' '){
s.erase(s.find_last_not_of(' ') + 1, s.size() - 1);
}
//先消除首尾空格，再判空
if(s.empty()){
cout << "空串或无实际意义的串" << endl;
return s;
}
//遍历获得空格数目
int blank_cnt = 0;
for(string::iterator i = s.begin(); i < s.end(); ++i){
if(*i == ' '){
blank_cnt++;
}
}
//计算移动几位
int mov_cnt = blank_cnt * 2;
//重置s的大小
s.resize(s.size() + mov_cnt,'='); //resize（size_value, fill_char）
last_iter = s.end() - mov_cnt - 1; //s中最后一个有意义的字符
first_iter = s.begin();
//s[s.size() + mov_cnt] = '\0';
//遍历移位
for(string::iterator i = last_iter; i >= first_iter; --i){
if(*i == ' '){ //替换空格
*(i + mov_cnt) = '0';
*(i + mov_cnt - 1) = '2';
*(i + mov_cnt - 2) = '%';
mov_cnt -= 2;
}
else{
*(i + mov_cnt) = *i; //移位赋值
}
}
return s;
}
};
#endif
1_5.str_compression
1.问题描述：
- 字符串压缩
- 将重复出现的字符转成数字形式
- "aabcccccaaa" ==> "a2b1c5a3"
2.策略一：原字符串操作法
- 不用额外空间
- 去除空格
- 判空
- 字符压缩
- 快慢索引指向值相等，cnt++，快索引向前移位
- 不等，则判断cnt是否等于1
- cnt == 1
- 慢索引向前移动一步
- 将快索引的值赋给慢索引的值
- 在慢索引处insert "1"
- 快索引向前移动一位
- cnt != 1
- 将cnt转成字符串并替换到慢索引的下一位置
- cnt置1
- 最后一组重复字符的处理
3.策略二：另开一字符串
- 去处空格 & 判空
- 字符压缩
- 快慢索引指向值相等，cnt++，快索引向前移位
- 不等，新字符串插入慢索引指向字符和cnt值
- 慢索引指向快索引指向值，cnt置1
- 最后一组重复字符的处理，同B，但仅作一次
4.itoa相关：
定义： 整型数值转为字符串
例： int n = 10；==》"10"
-
itoa函数
- 所属头文件<cstdlib>
- 原型：itoa（int_value,string_buf,base）
- base:进制,可选2,8,10,16
- linux下不可用
-
linux下如何使用itoa
- 自己写一个
- 用stringstream
- stringstream ss << int_value
- ss >> str
- c++ 11提供：string s = std::to_string(int_value);
5.字符串连接函数append()：
- strComp.append(s, idx, 1);
- strComp.append(s);
- 参见cplusplus.com
6.代码示例：
/********************************************************************************
> File Name: Solution.h
> Description:
（1）问题描述：
A.字符串压缩
B.将重复出现的字符转成数字形式
C."aabcccccaaa" ==> "a2b1c5a3"
> Conclusion:
（1）策略一：原字符串操作法
A.不用额外空间
B.去除空格
C.判空
D.字符压缩
a.快慢索引指向值相等，cnt++，快索引向前移位
b.不等，则判断cnt是否等于1
c.cnt == 1
*.慢索引向前移动一步
*.将快索引的值赋给慢索引的值
*.在慢索引处insert "1"
*.快索引向前移动一位
d.cnt != 1
*.将cnt转成字符串并替换到慢索引的下一位置
*.cnt置1
E.最后一组重复字符的处理
（2）策略二：另开一字符串
A.去处空格 & 判空
B.字符压缩
a.快慢索引指向值相等，cnt++，快索引向前移位
b.不等，新字符串插入慢索引指向字符和cnt值
c.慢索引指向快索引指向值，cnt置1
C.最后一组重复字符的处理，同B，但仅作一次
（3）itoa相关：
A.定义： 整型数值转为字符串
B.例： int n = 10；==》"10"
C.itoa函数
a.所属头文件<cstdlib>
b.原型：itoa（int_value,string_buf,base）
*.base:进制,可选2,8,10,16
c.linux下不可用
D.linux下如何使用itoa
a.自己写一个
b.用stringstream
*.stringstream ss << int_value
*.ss >> str
c.c++ 11提供：
string s = std::to_string(int_value);
d.
（4）字符串连接函数append()：
A.strComp.append(s, idx, 1);
B.strComp.append(s);
C.参见cplusplus.com
> Author: rh_Jameson
> Created Time: 2014年12月11日 星期四 15时10分23秒
***********************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
#include<sstream>
#include<cstdlib>
using namespace std;
class Solution {
public:
//int转string
string itoa(int n){
stringstream ss;
ss << n;
string tmp;
ss >> tmp;
/*linux下没有itoa函数
string tmp;
itoa(cnt, tmp, 10);
*/
//c++11才可以用
//string tmp = std::to_string(cnt);
return tmp;
}
//消除空格
void removeStrSpace(string &s){
string::iterator iter = s.begin();
string::iterator end = s.end();
while(iter < end){
if(*iter == ' '){
s.erase(iter);
}
else{
++iter;
}
}
}
//=======================不用额外字符串版本=====================//
//字符串压缩
string strCompressionBetter(string s){
//消除空格
removeStrSpace(s);
//判空
if(s.empty()){
cout << "空字符串" << endl;
}
//字符压缩
int cnt = 1, idx = 0, i;
string tmp;
for(i = 1; i < s.size(); ++i){
if(s[idx] == s[i]){
cnt++;
}
else{
if(cnt != 1){
tmp = itoa(cnt);
s.replace(++idx,1,tmp);
s[++idx] = s[i];
cnt = 1;
}
else{
s[++idx] = s[i];
s.insert(idx++,"1");
i++;
}
}
}
//最后的判断 & 处理
if(cnt == 1){
s[++idx] = s[i];
s.insert(idx++,"1");
}
if(cnt != 1){
tmp =itoa(cnt);
s.replace(++idx,1,tmp);
s[++idx] = s[i];
}
s.resize(idx);
return s;
}
//======================另开字符串版本====================//
//字符串压缩
string strCompression(string s){
//消除空格
removeStrSpace(s);
//判空
if(s.empty()){
cout << "空字符串" << endl;
}
//字符压缩
string strComp,tmp;
int idx = 0, i, cnt = 1, len = s.size();
/*快慢下标，相等，cnt++
* 不等，将s[idx]和cnt插入strComp中
*/
for(i = 1; i < s.size(); ++i){
if(s[idx] == s[i]){
cnt++;
}
else{
strComp.append(s, idx, 1);
tmp = itoa(cnt);
strComp.append(tmp);
//idx += cnt;
idx = i;
cnt = 1;
}
}
//最后重复一次处理
strComp.append(s, idx, 1);
tmp = itoa(cnt);
strComp.append(tmp);
return strComp;
}
};
#endif
1_6.matrix_rotate
1.问题描述
- N * N矩阵表示图像
- 每像素4字节
- 实现图像旋转90度
- 不用额外空间
2.策略一：四点轮换法
- 遍历行数N/2
- 将行中每个结点旋转到相应位置
- 通过tmp变量进行轮换
- 时间复杂度O（N^2）
3.策略二：对角线替换
- 交换对角线两边元素
- 对每一列元素进行逆置
- 逆时针旋转绕横轴
- 顺时针旋转绕纵轴
4.生成随机数
- srand((int)time(NULL));
- r = rand() % 10
5.传递二维数组参数
- int a[10][10]
- int a[][10]
- 不可以用二级指针
- int** a;
- 相关网址：
http://www.wutianqi.com/?p=1822
6.代码示例：
/*************************************************************************
> File Name: Solution.h
> Description:
（1）问题描述
A.N * N矩阵表示图像
B.每像素4字节
C.实现图像旋转90度
D.不用额外空间
> Conclusion:
（1）策略一：四点轮换法
A.遍历行数N/2
B.将行中每个结点旋转到相应位置
C.通过tmp变量进行轮换
D.时间复杂度O（N^2）
（2）策略二：对角线替换
A.交换对角线两边元素
B.对每一列元素进行逆置
a.逆时针旋转绕横轴
b.顺时针旋转绕纵轴
（3）生成随机数
A.srand((int)time(NULL));
B.r = rand() % 10
（4）传递二维数组参数
A.int a[10][10]
B.int a[][10]
C.不可以用二级指针
a.int** a;
b.相关网址：
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;
}
//=======================矩阵旋转：四点轮换法,Accepted=======================//
//逆时针旋转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);
}
//顺时针旋转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);
}
//=====================矩阵旋转：对角线替换,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;
//对角线两侧元素互换
for(int i = 0; i < len; ++i){
for(int j = i; j < len; ++j){
swap(a[i][j],a[j][i]);
}
}
//根据纵轴逆置元素
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的行, 列
- 对相应行清零
- 相应列清零
策略二：复用0行0列记录要清零的行，列
- 不用额外空间，直接复用0行0列的空间
- 判断0行跟0列是否存在0，bool标志真/假
- 遍历其余行跟列
- 元素为0的行列，存到0行0列的相应位置
- 遍历清零
- 检测bool标志，判断0行0列是否存在0
- 存在，则对0行 / 0列清零
3.Coding遇到的问题
- vector<vector<int> > m：
- 相当于二维数组 m[i][j]
- 行数：m.size()
- 列数：m[0].size()
- m[i][j]形式，通过2个for循环可生成随机矩阵
- vector形式不能生成
- 相关链接
- map & hashtable：
- C++ STL严格来说没有实现哈希表结构
- map底层是红黑树，访问复杂度为logN
- 哈希表一般是常数时间访问
- 性能：unordered_map > hash_map > map
- 需要有序关联容器的话要用map
- 相关链接
- STL---hash_map
- c++ hash_map 详细介绍
- 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.对相应行清零
D.相应列清零
（2）策略二：复用0行0列记录要清零的行，列
A.不用额外空间，直接复用0行0列的空间
B.判断0行跟0列是否存在0，bool标志真/假
C.遍历其余行跟列
D.元素为0的行列，存到0行0列的相应位置
E.遍历清零
F.检测bool标志，判断0行0列是否存在0
G.存在，则对0行 / 0列清零
（3）vector<vector<int> > m：
A.相当于二维数组 m[i][j]
B.行数：m.size()
C.列数：m[0].size()
D.m[i][j]形式，通过2个for循环可生成随机矩阵
E.vector形式不能生成
F.http://blog.csdn.net/qingdujun/article/details/17499871
（4）map & hashtable：
A.C++ STL严格来说没有实现哈希表结构
B.map底层是红黑树，访问复杂度为logN
C.哈希表一般是常数时间访问
D.性能：unordered_map > hash_map > map
E.需要有序关联容器的话要用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; //清零行，列的个数
//遍历记录清零的行与列
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);
}
//=====================不用额外空间实现：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;
}
}
//将出现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
1_8.Reverse Words In A String
1.问题描述
- 給一字符串s
- 将字符串s中的单词反转
- 不使用额外空间
2.例子
- "the sky is blue" ==> "blue is sky the"
3.解决方案
- 策略一：反转法
- 思路：
- 每个单词都反转一次
- 反转整个字符串
- 步骤：
- 消除头部空格
- 消除尾部空格
- 消除word间重复的空格
- 反转每个单词，最后反转整个字符串
- 思路：
- 优化策略：
- 思路：同一
- 步骤：
- 消除重复元素
- 判断首尾有无空格，有则删之
- 反转每个单词，最后反转整个字符串
4.Coding遇到的问题
-
C++获取字符串长度：
- 两种方式:str.length() / str.size()
- 使用C版本的string头文件，则调用strlen()
- 返回字符串实际长度，即不包括结束符
-
C++去除首尾空格：
- C++中没有相关的trim()方法
- 使用stl的相关函数实现
- 使用<ctype.h>(<cctype>)中的isspace遍历实现
- isspace() example
-
sizeof(string)与sizeof（int）不同
- int分配在栈，string分配空间在堆
- string的地址存在栈中
- sizeof(string)是string地址的大小
- sizeof(string)不同编译器/系统，大小不同
- 64位linux，g++：8
- 32位win，vc6.0：16
-
传递指针字符串（void fun（string* s））
- 传递的实际是字符串地址的地址
- 建议改为引用，即string& s
-
string.erase()使用
- erase(pos): 删除pos处的一个字符
- erase(pos,n): 删除pos处开始的n个字符
- erase(first,last) 删除first到last之间的字符
- first,last,pos为迭代器
5.代码示例：
/*************************************************************************
> File Name: Solution for Reverse Words in a String
> Description:
（1）问题描述：
A.給一字符串
B.将字符串中的单词逆转
C."the sky is blue" ==> "blue is sky the"
D.不使用额外空间
> Conclusion:
（1）策略一：反转法
A.思路：
a.每个单词都反转一次
b.反转整个字符串
B.消除头部空格
C.消除尾部空格
D.消除word间重复的空格
E.反转每个单词，最后反转整个字符串
（1.5）优化策略：
A.思路：同一
B.消除重复元素
C.判断首尾有无空格，有则删之
D.反转每个单词，最后反转整个字符串
（2）C++获取字符串长度：
A.两种方式:str.length()/str.size()
B.使用C版本的string头文件，则调用strlen()
C.返回字符串实际长度，即不包括结束符
（3）C++去除首尾空格：
A.C++中没有相关的trim()方法
B.使用stl的相关函数实现
C.使用<ctype.h>(<cctype>)中的isspace遍历实现
（4）sizeof(string)与sizeof（int）不同
A.int分配在栈，string分配空间在堆
B.string的地址存在栈中
C.sizeof(string)是string地址的大小
D.sizeof(string)不同编译器/系统，大小不同
a.64位linux，g++：8
b.32位win，vc6.0：16
（6）传递指针字符串（void fun（string* s））
A.传递的实际是字符串地址的地址
B.建议改为引用，即string& s
（7）string.erase()使用
A.erase(pos): 删除pos处的一个字符
B.erase(pos,n): 删除pos处开始的n个字符
C.erase(first,last) 删除first到last之间的字符
D.first,last,pos为迭代器
> Author: rh_Jameson
> Created Time: 2014年12月07日 星期日 17时10分20秒
************************************************************************/
#include<string>
#include<cctype>
#include <algorithm>
#include <functional>
#include <locale>
using namespace std;
class Solution {
public:
//反转函数
void reverse(int p, int q, string& s){
char tmp;
while(p < q){
tmp = s[p];
s[p++] = s[q];
s[q--] = tmp;
}
}
//======================反转法原始版：Accepted,44ms======================//
void reverseWordsOrigin(string &s) {
int p = 0, q = p;
//去除首部空格
while(s[0] == ' '){
if(s == ""){
break;
}
s.erase(s.begin());
}
//去除尾部空格
while(s[s.size() - 1] == ' '){
if(s == ""){
break;
}
s.erase(s.end() - 1);
}
//去除单词间重复空格
while(p < s.size()){
if(s[p] == ' ' && s[p] == s[p + 1]){
s.erase(s.begin() + p);
continue;
}
p++;
}
p = 0;
int len = s.size();
//逐个单词反转
while(q < len){
if(s[q] != ' '){
if(q == len - 1){
reverse(p, q, s);
}
q++;
}
else{
reverse(p, q - 1, s);
p = ++q;
}
}
//对整个字符串进行反转
reverse(0, len - 1, s);
}
//======================反转法首尾消除优化版：Accepted,44ms======================//
// trim from start
inline string <rim(string &s) {
s.erase(s.begin(), find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace))));
return s;
}
// trim from end
inline string &rtrim(string &s) {
s.erase(find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(), s.end());
return s;
}
// trim from both ends
inline string &trim(string &s) {
return ltrim(rtrim(s));
}
//main
void reverseWordsOpt(string &s) {
int p = 0, q = p;
//去除首尾空格
trim(s);
//去除单词间重复空格
while(p < s.size()){
if(s[p] == ' ' && s[p] == s[p + 1]){
s.erase(s.begin() + p);
continue;
}
p++;
}
p = 0; //重置索引p
int len = s.size();
//逐个单词反转
while(q < len){
if(s[q] != ' '){
if(q == len - 1){
reverse(p, q, s);
}
q++;
}
else{
reverse(p, q - 1, s);
p = ++q;
}
}
//对整个字符串进行反转
reverse(0, len - 1, s);
}
//======================反转法重复消除优化版：Accepted,44ms======================//
void reverseWords(string &s) {
int p = 0, q = p;
//去除单词间重复空格
while(p < s.size()){
if(s == "" ){
break;
}
if(s[p] == ' ' && s[p] == s[p + 1]){
s.erase(s.begin() + p);
continue;
}
p++;
}
if(s[0] == ' '){
s.erase(s.begin());
}
if(s[s.size() - 1] == ' '){
s.erase(s.end() - 1);
}
p = 0; //重置p
int len = s.size();
//逐个单词反转
while(q < len){
if(s == ""){
break;
}
if(s[q] != ' '){
if(q == len - 1){
reverse(p, q, s);
}
q++;
}
else{
reverse(p, q - 1, s);
p = ++q;
}
}
//对整个字符串进行反转
reverse(0, len - 1, s);
}
};
