剑指offer习题集2
2024-08-21 12:37:05
1.把数组排成最小的数
class Solution {
public:
static bool compare(const string& s1, const string& s2) {
string t1 = s1 + s2;
string t2 = s2 + s1;
return t1 <= t2? true : false;
}
string PrintMinNumber(vector<int> numbers) {
string str;
int i, len = numbers.size();
if (len<) return str;
string res;
vector<string> vt;
for (i = ;i<len;++i) {
stringstream stream;
stream << numbers[i];
stream >> str;
vt.push_back(str);
}
sort(vt.begin(), vt.end(), compare);
for (i = ;i<len;++i)
res += vt[i];
return res;
}
};
这里使用string会比使用char*更加快捷方便。
另外使用sort而不是qsort，主要是sort是qsort的升级，且参数更少，不需要制定每个参数占据的内存空间大小。
2.字符流中第一个不重复的字符
少有的一遍通过的程序，眼泪都快流下来了
class Solution
{
public: Solution():index(){ //初始化位置
for(int i=;i<;++i)
pos[i]=-;
} //Insert one char from stringstream
void Insert(char ch)
{
if(pos[ch]==-)
pos[ch]=index;
else if(pos[ch]>=)
pos[ch]=-; ++index;
} //return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
char res='#';
int minv=1e8,i; //设置字符串max值
for(i=;i<;++i){
if(pos[i]>=&&pos[i]<minv){ //若是当前位置小于min,则对min进行更新
res=(char)i;
minv=pos[i];
}
} return res;
} private:
int index;
int pos[];
};
3.求滑动窗口最大值
还是不能一遍通过，而且思维定式，真的很难找到错误的
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
int i,j,k,len=num.size();
vector<int> result;
if(len<size||size==)
return result;
int max=num[];
for(i=;i<size;++i){ //先寻找第一个窗口的最大值
if(max<num[i])
max=num[i];
}
result.push_back(max);
for(i=;i<=(len-size);++i){
j=i+size-;
if(num[j]<max){
//判断最大值是否移出滑动窗口
if(num[i-]!=max)
result.push_back(max);
else{ //确定最大值被移出滑动窗口,重新确定最大值
max=num[i];
for(k=i;k<=j;++k){
if(num[k]>max)
max=num[k];
}
result.push_back(max);
}
}else{
result.push_back(num[j]);
max=num[j];
}
}
return result;
}
};
4.表示数值的字符串（最耗人心力的程序，没有之一）
有空多做几遍，绝对练耐心
class Solution {
public:
bool isdigit(const char& ch){
if(ch<=''&&ch>='')
return true;
else return false;
}
void scandigits(char** str){
while(**str!='\0'&&isdigit(**str))
++(*str);
}
bool isexpand(char** str){
if(**str!='E'&&**str!='e')
return false;
++(*str);
if(**str=='+'||**str=='-')
++(*str);
if(**str=='\0')
return false;
scandigits(str);
return (**str=='\0')?true:false;
}
bool isNumeric(char* strt)
{
if(NULL==strt)
return false;
bool digit=true;
char *str=strt;
//排除符号干扰,找到第一个数字
while(str){
if(*str=='+'||*str=='-'){
++str;break;
}else if(isdigit(*str)){
break; //找到第一个数字
}
}
if(*str=='\0') return false;
scandigits(&str);
if(*str!='\0'){
//针对小数进行处理
if(*str=='.'){
++str;
scandigits(&str);
if(*str=='e'||*str=='E')
digit=isexpand(&str);
}else if(*str=='E'||*str=='e'){
digit=isexpand(&str);
}else{
digit=false;
}
}
return digit&&(*str=='\0');
}
};
5.字符串的排列
《剑指offer》上针对的是无重复字符串的全排列递归做法。
下面贴的是对重复字符进行处理了的全排列递归做法，为了通过测试集，对字符串进行了排序。
class Solution {
public:
vector<string> Permutation(string str) {
vector<string> res;
int len=str.length();
if(==len) return res;
else if(==len){
res.push_back(str); return res;
}
int left=,right=len-;
Permutation(str,left,right,res);
sort(res.begin(),res.end());
return res;
}
//递归实现字符交换
void Permutation(string& str,int left,int right,vector<string>& res){
if(left==right){
res.push_back(str);
}else{
for(int i=left;i<=right;++i){
if(isswap(str,left,i)){
swap(str[i],str[left]);
Permutation(str,left+,right,res);
swap(str[i],str[left]);
}
}
}
}
private:
void swap(char& a,char& b){
char t=a;a=b;b=t;
}
bool isswap(const string& str,const int& left,const int& right){
for(int i=left;i<right;++i)
if(str[i]==str[right])
return false;
return true;
}
};
后续会添加相应的非递归做法。
另外，此题可以扩展为多个子问题，待后续一一解决。
6.求旋转数组的最小数
没有通过测试集，不过自行调试，觉得程序应该是正确的啊
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int len = rotateArray.size();
if ( == len) return ;
else if ( == len) return rotateArray[];
int left = , right = len - , mid;
while (rotateArray[left] >= rotateArray[right]) {
if (right - left == ) {
mid = right;break;
}
mid = left + (right - left) / ;
//如果下标为left/right/mid指向的三个数字相等
if (rotateArray[left] == rotateArray[right] &&
rotateArray[left] == rotateArray[mid]) {
//顺序查找最小元素
return mininorder(rotateArray, left, right);
}
if (rotateArray[mid] >= rotateArray[left]) {
left = mid;
}
else if (rotateArray[mid] <= rotateArray[right]) {
right = mid;
}
}
return rotateArray[mid];
}
private:
int mininorder(const vector<int>& rotateArray, const int& left, const int& right) {
int min = rotateArray[left];
for (int i = left + ;i <= right;++i) {
if (rotateArray[i]<min)
min = rotateArray[i];
}
return min;
}
};
7.扑克牌顺子
class Solution {
public:
bool IsContinuous( vector<int> numbers ) {
int len=numbers.size();
if(len<=) return false;
//进行排序
sort(numbers.begin(),numbers.end());
int i=,zeronum=,gap,numgap=;
for(i=;i<len;i++){
if(numbers[i]==)
++zeronum;
else break;
}
//从非零的下一个位置开始进行计算
for(i=i+;i<len;++i){
gap=numbers[i]-numbers[i-];
if(==gap)
return false;
else if(==gap)
continue;
else{
numgap+=gap-;
}
}
if(numgap<=zeronum)
return true;
else return false;
}
};
8.丑数
此题真的不太好理解，需要重复练习几遍方能理解贯通。
class Solution {
public:
int GetUglyNumber_Solution(int index) {
if(==index) return ;
else if(==index) return ;
long long *uglynum=new long long[index];
uglynum[]=;
int nextuglyindex=;
long long min,*p1=uglynum,*p2=uglynum,*p3=uglynum;
while(nextuglyindex<index){
min=minnum(*p1*,*p2*,*p3*);
uglynum[nextuglyindex]=min;
while(*p1*<=uglynum[nextuglyindex])
++p1;
while(*p2*<=uglynum[nextuglyindex])
++p2;
while(*p3*<=uglynum[nextuglyindex])
++p3;
++nextuglyindex;
}
int res= (int)uglynum[nextuglyindex-];
delete[] uglynum;
return res;
}
private:
long long minnum(const long long& num1,const long long& num2,const long long& num3){
long long min=(num1<num2)?num1:num2;
return (num3<min)?num3:min;
}
};
9.正则表达式匹配
class Solution {
public:
bool match(char* str, char* pattern)
{
if(NULL==str||pattern==NULL)
return false;
else return matchstr(str,pattern);
}
private:
bool matchstr(char* str,char* pattern){
if(*str=='\0'&&*pattern=='\0')
return true;
if(*str!='\0'&&*pattern=='\0')
return false;
if(*(pattern+)=='*'){
if(*pattern==*str||(*pattern=='.'&&*str!='\0'))
return matchstr(str+,pattern+)
|| matchstr(str+,pattern)
|| matchstr(str,pattern+);
else return matchstr(str,pattern+);
}
if(*str==*pattern||(*pattern=='.'&&*str!='\0'))
return matchstr(str+,pattern+);
return false;
}
};
return使用||返回几个可能结果，状态之间的变化，简直不能再赞了
10.树的子结构
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
bool HasSubtree(TreeNode* root1, TreeNode* root2)
{
bool res=false; if(root1!=NULL&&root2!=NULL){
if(root1->val==root2->val){
res=judgetree(root1,root2);
}
if(!res)
res=HasSubtree(root1->left,root2);
if(!res)
res=HasSubtree(root1->right,root2);
} return res;
} private:
bool judgetree(TreeNode* root1, TreeNode* root2){
if(root2==NULL)
return true; if(root1==NULL)
return false; if(root1->val!=root2->val)
return false; return judgetree(root1->left,root2->left)&&
judgetree(root1->right,root2->right);
}
};
以后看看能不能改进，避免递归调用。
11.栈的压入弹出
class Solution {
public:
bool IsPopOrder(vector<int> push, vector<int> pop) {
bool res = false;
int len = push.size();
if (len != pop.size() || len <= ) return res;
stack<int> sdata;
vector<int>::iterator nextpush = push.begin(), nextpop = pop.begin();
while (nextpop - pop.begin() < len)
{
while (sdata.empty() || sdata.top() != *nextpop)
{
if (nextpush - push.begin() == len)
break;
sdata.push(*nextpush);
++nextpush;
}
if (sdata.top() != *nextpop)
break;
sdata.pop();
nextpop++;
}
if (sdata.empty() && nextpop - pop.begin() == len)
res = true;
return res;
}
};
12.二叉搜索树的后序遍历序列
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sdata) {
int len = sdata.size();
if (len <= ) return false;
return judgeBST(sdata, , len - );
}
private:
bool judgeBST(vector<int>& sdata, int left, int right) {
if (right - left < ) return false;
int i, j, root = sdata[right];
for (i = left;i < right;++i) {
if (sdata[i] > root)
break;
}
for (j = i;j < right;++j) {
if (sdata[j] < root)
return false;
}
bool leftsign = true, rightsign = true;
if (i > left) //表示有左子树
leftsign = judgeBST(sdata, left, i - );
if (i < right) //表示有右子树
rightsign = judgeBST(sdata, i, right - );
return (leftsign&&rightsign);
}
};
13.按之字形顺序打印二叉树
class Solution {
public:
vector<vector<int>> Print(TreeNode* root)
{
vector<vector<int>> res;
if (NULL == root)
return res;
int i, left, right, nextlevel = , tobepush = ;
vector<int> vtmp;
std::queue<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty())
{
TreeNode *nodetmp = nodes.front();
vtmp.push_back(nodetmp->val);
if (nodetmp->left)
{
++nextlevel;
nodes.push(nodetmp->left);
}
if (nodetmp->right)
{
++nextlevel;
nodes.push(nodetmp->right);
}
nodes.pop();
--tobepush;
if ( == tobepush)
{
res.push_back(vtmp);
vtmp.clear();
tobepush = nextlevel;
nextlevel = ;
}
}
for (i = ; i < res.size(); i += )
{
left = ;right = res[i].size() - ;
while (left < right)
{
swap(res[i][left], res[i][right]);
++left;--right;
}
}
return res;
}
private:
void swap(int& a, int& b)
{
int tmp = a;a = b;b = tmp;
}
};
14.判断二叉树是否对称
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
if (NULL == pRoot)
return true;
else return judgeSymmetrical(pRoot->left, pRoot->right);
}
private:
bool judgeSymmetrical(TreeNode* left, TreeNode* right)
{
if (NULL == left&&NULL == right)
return true;
if (NULL == left || NULL == right)
return false;
if (left->val != right->val)
return false; //注意此处不能判断相等返回true,因为下面还要进行判断
return judgeSymmetrical(left->left, right->right)
&& judgeSymmetrical(left->right, right->left);
}
};
很完美的思路，通过前序序列进行判断。
15.二叉树的序列化和反序列化
class Solution {
public:
char* Serialize(TreeNode *root)
{
string str;
Serialize(root, str);
int i,len = str.length();
char *res = new char[len + ];
for (i = ; i < len; i++)
res[i] = str[i];
res[i] = '\0';
return res;
}
TreeNode* Deserialize(char *str)
{
if (NULL == str || *str == '\0')
return NULL;
int left = ;
string numstr(str);
TreeNode* head = Deserialize(numstr, left);
return head;
}
private:
void Serialize(TreeNode *root, string& str)
{
if (NULL == root)
{
str += "#,"; return;
}
else
{
ostringstream ost;
ost << root->val;
str += ost.str() + ',';
}
Serialize(root->left, str);
Serialize(root->right, str);
}
bool readstr(string& str,int& left, int& num)
{
if (str[left] == '#')
{
left += ; //退后至下一个数字
return false;
}
else
{
string tmp;
while (str[left] != ',' && str[left] != '\0')
{
tmp += str[left++];
}
++left;
num = atoi(tmp.c_str());
return true;
}
}
TreeNode* Deserialize(string& numstr,int& left)
{
int num;
if (readstr(numstr, left, num))
{
TreeNode* root = new TreeNode(num);
root->left = Deserialize(numstr, left);
root->right = Deserialize(numstr, left);
return root;
}
return NULL;
}
};
16.二叉搜索树的第K个节点
class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, unsigned int k)
{
if (NULL == pRoot || k == )
return NULL;
return KthTreeNode(pRoot, k);
}
private:
TreeNode* KthTreeNode(TreeNode* root, unsigned int& k)
{
TreeNode* target = NULL;
if (root->left != NULL)
target = KthTreeNode(root->left, k);
if (NULL == target)
{
if (k == )
target = root;
--k;
}
if (NULL == target&&root->right != NULL)
target = KthTreeNode(root->right, k);
return target;
}
};
根据中序遍历的方式实现寻找。
最新文章
- SlidingMenu 侧滑菜单的用法
- CF750E New Year and Old Subsequence
- 不错的判断 UITextView 内容不超过20个字符串的方法
- sscanf函数和正则表达式
- Eclipse小技巧
- centos下安装python
- 在PHP中如何使用消息列队
- [leetcode]352. Data Stream as Disjoint Intervals
- UML[1] UML类图关系（泛化 、继承、实现、依赖、关联、聚合、组合）（转）
- appium新版本不支持findElementByName，切换到findElementByAndroidUIAutomator
- Java应用开发的一条经验
- thinkphp框架的相关总结
- python 绘图pylab
- aspectj 表达式 execution切点函数
- ESLint 配置说明
- JDK1.8 LocalDateTime 时间类与字符互转
- web前端安全的三个关键点
- Objective-C中的一些特殊的数据类及NSLog的输出格式
- Hibernate之mappedBy与@JoinColumn
- CANVAS实现调色板 之 我的第一个随笔