反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
代码:
思路和翻转整数数组的思路一致，两个指针分别从前后开始扫描，进行交换。
void reverseString(char* s, int sSize) {
// 用反转数组相同的方式
int i;
for (i = 0; i < sSize / 2; i++) {
char temp = s[sSize - 1 - i];
s[sSize - 1 - i] = s[i];
s[i] = temp;
}
}
整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
代码:
int reverse(int x){
long count=0;
while(x!=0){
// 翻转整数
count=count*10+x%10;
x=x/10;
}
return count>2147483647||count<-2147483648?0:count; // 直接给出范围判断是否溢出
}
字符串中的第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例:
s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2.
**注意事项：**您可以假定该字符串只包含小写字母。
代码：
本题我用暴力法做的，在时间上不是很理想。
二重循环，外层遍历的元素与内层遍历的除本身外的元素进行比较，find表示是否找到相同的数，find=0就说明第i个元素只有一个，同时置have=1表示存在这样的元素。返回其索引。
int firstUniqChar(char * s) {
// 得到长度
int len = strlen(s);
int have = 0;
int i, j;
for (i = 0; i < len; i++) {
int find = 0;
for (j = 0; j < len; j++) {
if (i == j) continue;
if (s[i] == s[j]) {
find = 1;
break;
}
}
if (find == 0) {
have = 1;
break;
}
}
return have ? i : -1;
}
另外，其他人用了更好的方法，也就是使用辅助数组，记录每个元素出现的次数，在上一篇数组内容中也出现了这个方法。我想到这个方法时，没有考虑周全，误以为在遍历辅助数组时，只能从i=0 to n遍历，导致不能确定第一个为1就是第一个元素。但是，完全可以按照原数组的元素排列进行遍历，也就是将s[i]-'a'作为遍历指针。
int firstUniqChar(char * s){
int i, len = strlen(s);
// 构造辅助数组
int p[26];
memset(p, 0, sizeof(int) * 26);
// 首先根据原数组的元素出现情况进行填充
for(i = 0; i < len; i++){
p[s[i] - 'a']++;
}
// 再由 s[i]-'a' 作为遍历指针遍历辅助数组，寻找第一个只出现一次的元素
for(i = 0; i < len; i++){
if(p[s[i] - 'a'] == 1)
return i;
}
return -1;
}
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明: 你可以假设字符串只包含小写字母。
进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
代码:
这道题目让我想到了高中化学学的同分异构体，也就是所有对应的字母个数相同，但是排列方式不同。所以本道题采用辅助数组的形式，分别统计字符串s和t中每个字母出现的次数，接着再比较两个辅助数组是否相同即可。
bool isAnagram(char * s, char * t) {
int lens = strlen(s);
int lent = strlen(t);
if (lens != lent)return false; // 如果长度不相等，之间返回错误
// 下面用两个辅助数组，分别记录两个字符串中，每个字母出现的次数
int temps[26], tempt[26];
memset(temps, 0, sizeof(int) * 26);
memset(tempt, 0, sizeof(int) * 26);
// 开始统计数量
int i;
for (i = 0; i < lens; i++) {
temps[s[i] - 'a']++;
tempt[t[i] - 'a']++;
}
// 比较辅助数组
bool is = true;
for (i = 0; i < 26; i++) { // 注意这个数组是26个元素
if (temps[i] != tempt[i]) {
is = false;
break;
}
}
return is;
}
验证回文字符串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
**说明：**本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
代码:
- 构造函数
islod()来判断现读取到的字符是否为字母或者数字； - 现对字符串的字母进行大小写统一转换，便于比较，这里全部转为小写字母；
- 使用双指针分别从头和尾进行遍历，对于既不是数字也不是字母的字符忽略，然后比较两个指针所指元素是否相同。
bool islod(char c) {
return
((c >= 'a'&&c <= 'z') || (c >= 'A'&&c <= 'Z') || (c >= '0'&&c <= '9')) ? true : false;
}
bool isPalindrome(char * s) {
int lens = strlen(s);
bool re = true;
// 首先进行大小写转化方便判断
int p;
for (p = 0; p < lens; p++)
if (s[p] >= 'A'&&s[p] <= 'Z') s[p] += 32;
int f, l;
for (f = 0, l = lens - 1; f < l; f++, l--) {
// 首先需要判断是否是有效字符
while (!islod(s[f]) && f < l ) f++; // 循环直到 f 为合法字符
while (!islod(s[l]) && f < l ) l--; // 循环直到 l 为合法字符
// 然后判断一下f l避免越界
if ( !(f < l) ) break;
// 再进行判断
if (s[f] != s[l]) {
re = false;
break;
}
}
return re;
}
字符串转换整数(atoi)
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
- 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
- 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
- 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
- 本题中的空白字符只包括空格字符
' '。 - 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
代码:
这个题目写了很久，最后…还是学习学习别人写的吧…这个判断溢出的方法真的很巧妙，在以前都是直接暴力判断溢出的，因为很多题目假设只有32位，所以直接用数判断未免属于不合法的手段。
int myAtoi(char * str) {
// 移除开头的空格
while (*str == ' ') ++str; // 此时 str 指向第一个不为空格的字符
// 如果带有正负号，记录正负性
int flag = 1;
if (*str == '-') {
flag = -1;
++str;
} else if (*str == '+')
++str;
int ret = 0;
// 因为只能使用 32 位 int，因此将 ret 乘 10 后再与 INT_MAX 比较可能会溢出
// 因此使用 ret 与 INT_MAX/10 比较
int div = INT_MAX / 10;
while (*str <= '9' && *str >= '0') {
int dig = *str - '0';
// 若 ret 比 div 小，则 ret * 10 + dig 也一定小于 INT_MAX，不会溢出
// 若 ret 与 div 相等，只有 dig 比 8 小时不会溢出
// 此处本来需要正负分开讨论，INT_MAX 个位是 7，INT_MIN 个位是 8
// -INT_MIN 在 int 中会溢出，当 dig == 8 时直接当作溢出处理
if (ret < div || (ret == div && dig < 8)) {
ret = ret * 10 + dig;
++str;
}
// 溢出，根据正负性返回值
else
return (flag == 1 ? INT_MAX : INT_MIN);
}
return flag * ret;
}
实现strStr()
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
代码:
KMP，双100%，永远滴神！我觉得书上讲的都比较含糊，可以找视频来看一下这个算法，主要是求next数组。
/* 前缀表 */
void prefix_table(char pattern[], int prefix[], int n) {
prefix[0] = 0;
int len = 0;
int i = 1;
while (i < n) {
if (pattern[i] == pattern[len]) {
len++;
prefix[i] = len;
i++;
}
else {
if (len > 0) {
len = prefix[len - 1];
}
else {
prefix[i] = len;
i++;
}
}
}
}
/* 左移前缀表 */
void move_prefix_table(int prefix[], int n) {
int i;
for (i = n - 1; i > 0; i--) {
prefix[i] = prefix[i - 1];
}
prefix[0] = -1;
}
/* kmp search */
int kmp_search(char text[], char pattern[]) {
int n = strlen(pattern);
int m = strlen(text);
int *prefix = malloc(sizeof(int)*n);
prefix_table(pattern, prefix, n);
move_prefix_table(prefix, n);
/*
text[i] len(text) = m
pattern[j] len[pattern] = n
*/
int i = 0, j = 0;
while (i < m) {
if (j == n - 1 && text[i] == pattern[j]) {
/*printf("%d", i - j);
j = prefix[j];*/
return i - j;
}
if (text[i] == pattern[j]) {
i++;
j++;
}
else {
j = prefix[j];
if (j == -1) {
i++;
j++;
}
}
}
return -1;
}
int strStr(char * haystack, char * needle) {
int lenn = strlen(needle);
if (lenn == 0) {
return 0;
}
return kmp_search(haystack, needle);
}
外观数列
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", “one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。
注意：整数序列中的每一项将表示为一个字符串。
示例 1:
输入: 1
输出: "1"
解释：这是一个基本样例。
示例 2:
输入: 4
输出: "1211"
解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组，"2" 可以读作 "12"，也就是出现频次 = 1 而 值 = 2；类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起，也就是 "1211"。
代码:
这个题目比较有意思。
使用了两个数组，数组res作为结果项和初始项，数组tmp作为对res处理后的进行保存的中间项，然后每一轮结束时，将数组tmp的内容复制到res中，再下一轮以res作为初始串进行处理。
char * countAndSay(int n) {
char *res = (char*)malloc(sizeof(char) * 5000);
char *tmp = (char*)malloc(sizeof(char) * 5000);
res[0] = '1'; res[1] = '\0'; // res 初始化为 "1"
int len = 1; // len 为 res 的有效长度
while (--n) {
int i = 0, j = 0;
while (i < len) { // 对 res 的每位字符 c 进行报数
int count = 1;
char c = res[i++];
while (i < len && res[i] == c) // 计算本轮报数结果，即本轮有几个 c
i++, count++;
tmp[j++] = count + '0'; // 将报数结果存入 tmp
tmp[j++] = c;
}
tmp[j] = '\0';
strcpy(res, tmp); // 将 tmp 复制到 res，并更新 res 长度
len = j;
}
return res;
}
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
代码:
本题使用暴力法，但是由于公共前缀的问题，使用暴力法的时间表现还可以。求最短的元素，以其长度为基准进行搜索。然后双重循环求公共前缀。
char * longestCommonPrefix(char ** strs, int strsSize) {
if(strsSize==0) {
char *p = "";
return p;
}
if(strsSize==1) return strs[0];
// 先找出最短的元素
int minlen = strlen(strs[0]);
int i;
for (i = 1; i < strsSize; i++) {
if (minlen > strlen(strs[i])) {
minlen = strlen(strs[i]);
}
}
// 循环求解找最长公共前缀
int front, j;
bool valid = true;
for (front = 0; front < minlen; front++) {
for (j = 0; j < strsSize - 1; j++) {
if (strs[j][front] != strs[j + 1][front]) {
valid = false;
break;
}
}
if (!valid) break;
}
// 此时，front为 最长公共前缀的长度,假设最大1000
char res[1000];
char *restr = res;
memset(res, 0, sizeof(res));
printf("%d", strlen(res));
int k;
for (k = 0; k < front; k++) {
res[k] = strs[0][k];
}
return restr;
}
我这样做麻烦了…列垂直扫描不用那么麻烦。唉 ):
char * longestCommonPrefix(char ** strs, int strsSize){
if(strsSize==0) return ""; //如果字符串数组为空，直接返回""
for(int i=0;i<strlen(strs[0]);i++){ //i表示列，strlen(strs[0])表示第一个字符串长度
for(int j=1;j<strsSize;j++){ //j表示行
if(strs[0][i]!=strs[j][i]){ //如果比较字符串的第i列不同，该列结束，直接跳出
strs[0][i]='\0';
break;
}
}
}
return strs[0];
}
作者：cmtsa
链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/cchui-zhi-sao-miao-chao-duan-dai-ma-by-cmtsa/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。