一,字符串转化
将字符串转换成整数:atoi
将整数转换为字符串:itoa
浮点数与字符串的转换
1)字符串转化为整数
需要注意的地方:
考虑要缜密,注意是否为数字字符;
判断是否为NULL
开头的‘+’‘-’符号的判断
#include "stdio.h"
#include "string.h"
#include "assert.h"
int isDigit(char c)
{
if(c>='0'&&c<='9')
return 1;
else
return 0;
}
int myatoi(const char *str)
{
assert(str!=NULL);
int count=strlen(str);
int result=0;
int sign=1;
if(str[0]=='-')
{
sign=-1;
}
else if(str[0]=='+')
{
sign=1;
}
else if(isDigit(str[0]))
{
result=str[0]-'0';
sign=1;
}
for(int i=1;i<count;++i)
{
assert(isDigit(str[i]));
result=result*10+(str[i]-'0');
}
return result;
}
int main()
{
printf("%d\n",myatoi("123"));
}
别看一个这么简单的问题,实际要考虑的问题很多。还是看一下glibc的实现吧
#include "stdio.h"
#include "string.h"
#include "assert.h"
#define LONG_MAX 2147483647L
#define LONG_MIN (-2147483647L-1L)
long int _strtol_internal (const char *nptr, char **endptr, int base, int group)
{
//注意要使用unsigned long否则会发生溢出,因为long int最多2147483647L ,无法表示2147483648L
unsigned long int result = 0;
long int sign = 1;
//考虑前导空格
while (*nptr == ' ' || *nptr == '\t')
++nptr;
//考虑带有正负号
if (*nptr == '-')
{
sign = -1;
++nptr;
}
else if (*nptr == '+')
++nptr;
//如果出现非法输入
if (*nptr < '0' || *nptr > '9')
{
if (endptr != NULL)
*endptr = (char *) nptr;
return 0L;
}
//考虑进制
assert (base == 0);
base = 10;
if (*nptr == '0')
{
if (nptr[1] == 'x' || nptr[1] == 'X')
{
base = 16;
nptr += 2;
}
else
base = 8;
}
//防止非法字符
while (*nptr >= '0' && *nptr <= '9')
{
unsigned long int digval = *nptr - '0';
//防止溢出,如果溢出了long的表示范围,则置errno
if (result > LONG_MAX / 10 || (sign > 0 ? result == LONG_MAX / 10 && digval > LONG_MAX % 10 :
(result == ((unsigned long int) LONG_MAX + 1) / 10 && digval > ((unsigned long int) LONG_MAX + 1) % 10)))
{
errno = ERANGE;
return sign > 0 ? LONG_MAX : LONG_MIN;
}
result *= base;
result += digval;
++nptr;
}
return (long int) result * sign;
}
atoi函数就是这个函数讲第二个参数置为NULL,第三个参数置为10。不知道你注意到了那些空格,越界之类的判断没有。我同学说他写出来的代码最后就被要求加上了这些东西,最后还因此被卡掉了(说是考虑不够慎密,汗)。
2)itoa 函数的实现
char *itoa( int value, char *string,int radix);
先看一看使用:
#include <stdlib.h>
#include <stdio.h>
int main(void)
{
int number = 12345;
char string[25];
itoa(number, string, 10); //按十进制转换
printf("integer = %d string = %s\n", number, string);
itoa(number, string, 16); //按16进制转换
printf("integer = %d string = %s\n", number, string);
return 0;
}
整形转化为字符串(这里默认十进制的转换)
//整形转成字符串函数实现
//题目不难,重点考察面试者对问题考虑的全面程度
#include <iostream>
using namespace std;
void itoa_mf(int num,char str[])
{
int sign = num;
int i = 0;
int j = 0;
char temp[100];
if(sign < 0)//如果是负数就去掉符号,将-1234转成1234
{
num = -num;
}
do//转成字符串,1234转成"4321"
{
temp[i] = num % 10 + '0';
num /= 10;
i++;
}while(num > 0);
if(sign < 0)//如果是负数的话,加个符号在末尾,如:"4321-"
{
temp[i++] = '-';
}
temp[i] = '\0';
i--;
//将temp数组中逆序输入到str数组中
//将"4321-" ====> "-1234"
while(i >= 0)
{
str[j] = temp[i];
j++;
i--;
}
//字符串结束标识
str[j] = '\0';
}
int main()
{
int a = +123;
char s[100];
itoa_mf(a,s);
cout << s << endl;
}
二,找出字符串的最长子串,要求子串的所有字符相同
例如:str ="sssddddabcdef" 则输出字串为:dddd
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
char* GetSubstring(char* strSource)
{
char* strSubstring; //用于保存得到的子串,大小在找到最大子串后再确定,作为返回值
int nLen; //源字符串长度
int nCurPos; //当前统计字符串的头指针位置(相对于原字符串第一个字符的位置)
int nCurCount; //当前统计字符串的长度(有相同字符组成的子字符串)
int nPos; //当前最长的子串的头指针位置
int nCount; //当前最长的子串的长度
nLen = strlen(strSource);
//初始化变量
nCount = 1;
nPos = 0;
nCurCount = 1;
nCurPos = 0;
//遍历整个字符串
for(int i = 1; i < nLen; i++)
{
if(strSource[i] == strSource[nCurPos])//如果当前字符与子串的字符相同,子串长度增1
nCurCount++;
else //如果不相同,开始统计新的子串
{
if(nCurCount > nCount)//如果当前子串比原先最长的子串长,把当前子串信息(起始位置 + 长度)保留下来
{
nCount = nCurCount;
nPos = nCurPos;
}
//长度复值为1,新串的开始位置为i
nCurCount = 1;
nCurPos = i;
}
}
//为返回的子串分配空间(长度为nCount,由于要包括字符串结束符\0,故大小要加1)
strSubstring = (char*)malloc(nCount + 1);
//复制子串(用其他函数也可以)
for(int i = 0; i < nCount; i++)
strSubstring[i] = strSource[nPos + i];
strSubstring[nCount] = '\0';
return strSubstring;
}
int main()
{
//输入一个字符串strSource
char *strSource="absceeeecd";
char* strSubstring = GetSubstring(strSource);
printf("最长子串为:%s\n长度为:%d",strSubstring,strlen(strSubstring));
//释放strSubstring
free(strSubstring);
}
三,求两个字符串的最大公共子字符串
算法时间复杂度:O(n^2)
思想:两个字符串先从第一个字串的第一个字符开始,依次与第二个字串的各个位置字串比较字串
需要记录下最长公共子串在str1中的位置和子串长度
#include<iostream>
#include<cstring>
#include<cassert>
using namespace std;
void findMaxSubstr(const char * str1 , const char * str2 , char * maxSubstr)
{
assert((str1!=NULL)&&(str2!=NULL));
assert(maxSubstr!=NULL);
int maxPos=-1;
int maxLen=0;
int k;
for(int i=0; i<strlen(str1); i++)
{
for(int j=0; j<strlen(str2); j++)
{
if(str1[i]==str2[j])
{
for(k=1; (str1[i+k]==str2[j+k])&&(str1[i+k]!='\0'); k++)
;
if(k>maxLen)
{
maxPos=i;
maxLen=k;
}
}
}
}
if(maxPos==-1)
{
maxSubstr[0]='\0';
}
else
{
memcpy(maxSubstr , str1+maxPos , maxLen);
maxSubstr[maxLen]='\0';
}
}
int main()
{
char substr[20];
findMaxSubstr("tianshuai" , "mynameistianshuai" , substr);
cout<<substr<<endl;
return 0;
}
四,字符串查找并记录出现次数(普通与kmp)(观察strstr实现),替代
函数原型:extern char *strstr(char *str1, char *str2);
功能:找出str2字符串在str1字符串中第一次出现的位置(不包括str2的串结束符)
使用:printf("%s",strstr("tianshuai","shuai"));
输出:shuai
实现:
#include "stdio.h"
char *strstr(char *buf, char *sub)
{
register char *bp;
register char *sp;
if (!*sub)
return buf;
while (*buf)
{
bp = buf;
sp = sub;
do
{
if (!*sp)
return buf;
} while (*bp++ == *sp++);
buf += 1;//从下一个位置查找
}
return 0;
}
int main()
{
printf("%s",strstr("tianshuai","tian"));
}
求子串的个数只需要略微更改一下就可以
#include "stdio.h"
int strstr(char *buf, char *sub)
{
register char *bp;
register char *sp;
int count=0;
int pos=0;
if (!*sub)
return 0;
while (*buf)
{
bp = buf;
sp = sub;
pos=0;
do
{
pos++;
if (!*sp)
{
count++;
}
//return buf;
} while (*bp++ == *sp++);
buf += pos;//从下一个位置查找
}
return count;
}
int main()
{
printf("%d",strstr("tianshuai,tianshuai,tianshui","tian"));
}
五,解析一个字符串,对字符串中重复出现的字符,只在第一次出现时保留,就是去除重复的字符。
如:abdabbefgf -> abdefg。
根据字符集,建立一个flag数组用来表示是否出现过。
六,给出一个函数来输出一个字符串的所有排列
字典序生成算法问题:字典序
采用next_permutation的算法思想,首先进行一个字符重排序找到按字典序最小的那个字符序列,以它为开端逐步生成所有排列。
七,翻转字符串
参考例子
八,从一个字符串中找出第一个不重复字符
这个也比较简单,类似于5的方法。
九,去除字符串中相邻两个字符的重复
这个应该等价于题目5
十,判断字符串是否含有回文字符子串
枚举字符串的每个位置,作为回文串的中间位置(分偶数奇数两种情况),如果找到或者找不到都会立即停止,所以总的复杂度不超过O(n)
十一,求最长回文子串
dp
f[i][j] = f[i+1][j-1]
s[i] == s[j]
false s[i] != s[j]
当然这里有一个小小的限定,f[i][j]表示以i,j为首尾的回文串能否构成。然后再找到一个最长的就可以算法,复杂度O(n^2)。实际上这个问题只要枚举回文串的中间位置就可以了,这样实际上就跟10一样了。不过10只需判断是否存在,这需要找到最长的那个。
当然这个问题还有更快的算法:http://richardxx.yo2.cn/articles/kmp和extend-kmp算法.html
------------------------------------------------------引用开始------------------------------------------------------------------------
KMP的另外一个研究方向是Extend KMP(以下简称EK),它是说求得T与所有的S(i)的最长公共前缀(LCP),当然,要控制复杂度在线性以内。
EK我第一次听说是07年baidu校园招聘的笔试题中,它当时的题目是求最长回文子串,当然这是一个耳熟能详,路人皆知可以用Suffix Array很好解决的问题。事后听一个同学说他写了三个算法:Suffix Array,Suffix Tree和EK,当时就不明白EK是什么东西,但又没当面问他,于是这个东西就搁置了很久。知道后来北大的月赛一道题说可以用EK来做,我才终于从03年林希德的文章中开始认识到它,就像KMP一样,这个算法也一下就吸引了我。
设Q(i)表示T和S(i )的后缀的LCP,P(i)表示T和T(i)的后缀的LCP,那么和KMP一样,我们试图用P来求得Q,而P可以用自匹配求得,并且和求Q的过程相似。
我以求P为例简要说明一下。P(2)就直接匹配即可,从i = 3开始,如下:
设k < i,E(k) = k + P(k) - 1,且对所有j < i,有E(k) >= E(j)。
那么,当E(k) >= i时,便可以推知T(i) = T( i - k + 1 ),于是如果P( i - k + 1 ) < E(k) - i + 1,那么P(i) = P( i - k + 1),否则P(i) >= P( i - k + 1 ),从E(k)开始向后匹配到E(i),有P(i) = E(i) - i + 1,并且更新 k = i;
还有就是E(k) < i,肯定有E(k) = i - 1,不过这个不重要,重要的是直接从i开始做暴力匹配即可得到E(i),则P(i) = E(i) - i + 1,更新k = i。
希望我把EK说清楚了,不过这种东西还是自己推导一下有意思,而且记忆周期更长。
最后来罗列下题目。KMP的经典题目是POJ 2185,是要找最小覆盖矩形,如果你认为懂KMP了就去尝试它。EK的经典题是POJ 3376,有一定挑战;当然还有就是上面说的最长回文子串,提醒下用分治+EK来做是其中一种方法。
嗯,下次打算说下Suffix Array,主要是它那个传说中的线性DC3算法,不过我现在还没把握能不能简单的把它说清楚,姑且认为可以吧。
------------------------------------------------------引用结束------------------------------------------------------------------------
十二,字符串移位包含的问题
题目:给定两个字符串S1与S2,要求判定S2是否能够被通过s1作循环移位得到的字符串包含,例如,给定s1=AABCD与S2=CDAA,返回true;给定s1=ABCD 与 s2=ACBD,返回false.
直接枚举匹配或者比较s2能否匹配s1s1,以第一个为例也就是说比较AABCDAABCD和CDAA。
十三,strlen strcpy(注意重叠)
#include "stdio.h"
#include "assert.h"
char *strcpy (char *dest,const char *src)
{
assert(src!=NULL);
char *temp=dest;
while((*dest++=*src++)!='\0')
;
return dest;
}
int main()
{
char *dest;
char *src="tianshuai";
strcpy(dest,src);
printf("%s",dest);
}
上面这个比较复杂,再看FreeBsd的实现
char *strcpy(char * __restrict to, const char * __restrict from)
{
char *save = to;
for (; (*to = *from) != 0; ++from, ++to);
return(save);
}
十四,去掉中文中的英文字符
主要根据字节的第一位进行判断。
十五,求一个字符串中连续出现次数最多的子串
参考博文
相关推荐
这一部分的内容原本是打算在之后的字符串或者数组专题里面写的,但看着目前火热进行的各家互联网公司笔试面试中,出现了其中的一两个内容,就随即将这些经典问题整理整理,单写一篇发上来了。这里争取覆盖面广一些,...
列的字符串类型可以是什么?如何获取当前的 Mysql 版本?Mysql 中使用什么存储引擎?Mysql 驱动程序是什么?TIMESTAMP 在 UPDATE CURRENT_TIMESTAMP 数据类型上做什么?如何使用 Unix shell 登录 Mysql?myisamchk ...
国内天津大学的考研算法,值得下载。包含线性表、字符串、数组、树、图、查找排序、动态规划、概率组合等等
8、一个字符串类型的值能存储最大容量是多少? 9、为什么 Redis 需要把所有数据放到内存中? 10、Redis 集群方案应该怎么做?都有哪些方案? 11、Redis 集群方案什么情况下会导致整个集群不可用? 12、MySQL 里有 ...
8.字符型常量和字符串常量的区别 9. 构造器 Constructor 是否可被 override 10.重载和重写的区别 11.Java 面向对象编程三大特性: 封装 继承 多态 关于继承的3点 12.String StringBuffer 和 StringBuilder 的区别是...
字符串转换整数 (atoi) 没什么难度,不过leetcode上跑出来的结果还是挺高兴的,记录一下 执行用时:0 ms, 在所有 C++ 提交中击败了100.00%的用户 内存消耗:6.7 MB, 在所有 C++ 提交中击败了99.10%的用户 1月22日 ...
String是我们经常用到的一个类型,其实有时候觉得写程序是在反复的操作字符串,这是C的特点,在java中,jdk很好的封装了关于字符串的操作。主要讲的是三个类String 、StringBuffer 、 StringBuilder .这三个类...
leetcode 347 python Python Algorithm 按专题进行总结的常见算法面试题(LeetCode 为主),基于 Python 实现。 动态规划 数组 字符串 栈 链表 树 图 堆 设计 二进制
string是我们经常用到的一个类型,其实有时候觉得写程序是在反复的操作字符串,这是C的特点,在java中,jdk很好的封装了关于字符串的操作。主要讲的是三个类String 、StringBuffer 、 StringBuilder .这三个类基本...
第05部分:字符串 第06部分:二叉树 第07部分:树+贪心 第08部分:图的存储 第09部分:图搜索 第10部分:图的连通性 第11部分:图+贪心 第12部分:图的应用 第13部分:查找+分治 第14部分:数表查找 第15部分:简单...
leetcode 296 Algo2Offer 算法笔记。 笔面试算法题型分类及其解析 :diamond_suit: 链表专题 :diamond_suit: ...字符串专题 :diamond_suit: 数学类专题 :diamond_suit: 位运算专题 Leetcode及其解析 剑指offer
[数组、字符串、队列、堆栈、链表、树、图、尝试、堆、哈希表、向量] 算法 [排序、搜索、BFS、DFS] 概念 [位操作、内存、递归、动态规划、时间和空间复杂度] 项目 学习和实践的来源: 圣经:算法简介 AKA CLRS 破解...
字符串系列 链表系列 二叉树系列 排序系列 动态规划系列 设计系列 数学系列 其它系列 算法题型分类总结 1.冒泡排序: 原地排序,稳定排序(相邻元素大小相等时不交换),最好O(N),最坏O(N^2),平均O(N^2) 2.插入排序...
位运算系列动态规划系列 有效括号系列设计系列先锋和系列首要树并查集每日一题拓展跳表剪枝每日一题 字符串匹配每日一题 拓展翻译堆每日一题专题文章二分法每日一题拓展翻译 滑动窗口每日一题拓展翻译位运算搜索...
总结的一些代码,包括数组和字符串、树和链表; primary、middle、senior包是按照 总结的一些代码; 其中,primary是 ; middle是 ; senior是 ; 不得不说一下,力扣网按专题总结的这些** 真的很好** ,大家可以多看...
.NET 2.0中的字符串比较 小试ASP.NET 2.0的兼容性 为 asp.net 2.0 的菜单控件增加 target 属性 ASP.NET 2.0 的内部变化 常见的 ASP.NET 2.0 转换问题和解决方案 Asp.Net2.0无刷新客户端回调 体验.net 2.0 的优雅(1...