#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int lengthOfLongestSubstring(char* s);
int lengthOfLongestSubstring1(char* s);
int main(int argc, const char * argv[]) {
char s[] = "hello";
char *p = s;
int var = 20; /* 实际变量的声明 */
int *ip; /* 指针变量的声明 */
ip = &var;
///> 在这里 ip 和 p 所在的内存都是保存的地址 可以通过 他们保存的地址来访问值
printf(" *p的值：%c *s的值：%c *ip的值：%d p表示的字符串 %s \n",*p,*s,*ip,p); // *p的值：h *ip的值：20 p表示的字符串 hello
lengthOfLongestSubstring("pwwkew");
lengthOfLongestSubstring("au");
lengthOfLongestSubstring("bbbbb");
lengthOfLongestSubstring("abcabcbb");
lengthOfLongestSubstring("asdfghjklqwertyuiopmnbXCVBNM");
printf("---------- lengthOfLongestSubstring1 \n");
lengthOfLongestSubstring1("pwwkew");
lengthOfLongestSubstring1("au");
lengthOfLongestSubstring1("bbbbb");
lengthOfLongestSubstring1("abcabcbb");
lengthOfLongestSubstring1("asdfghjklqwertyuiopmnbXCVBNM");
printf("---------- %lu %f %f\n",sizeof(int),pow(2, 31) - 1,pow(2, 8) - 1);
return 0;
}
#pragma mark - 我的思路
///>给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 输入: "abcabcbb" 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
/*
C 字符串 C语言中没有字符串类型，只能使用间接的方法来表示
字符 char
字符数组 char str[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
依据数组初始化规则，您可以把上面的语句写成以下语句： 初始化的时候可以省略掉 数字
char greeting[] = "Hello";
当char *s = "hello";后,不能使用s[0]='a'；语句进行赋值。这是将提示内存不能为"written"。
当用char s[]="hello";后，完全可以使用s[0]='a'；进行赋值，这是常规的数组操作
*/
#pragma mark - 第一次解体
int lengthOfLongestSubstring1(char* s) {
int sLength = (int)strlen(s);
if (sLength == 0 || sLength == 1) {
return sLength;
}
int tempLen = 1;
char temp[128];
int forCount = 0;
///> 1 表示没有。2 表示有
int isHas = 1;
///> 我的思路 从第一个找到最长的 然后第二个最长的 最后结束
for (int i = 0; i < sLength; i++) {
forCount++;
if (i + tempLen < sLength) {
///> 重新初始化
memset(temp, 0, sizeof(temp));
for (int n = 0; n < tempLen; n++) {
temp[n] = s[i + n];
forCount++;
}
} else {
printf("tempLen: %d temp:%s forCount:%d \n",tempLen,temp,forCount);
return tempLen;
}
for (int j = i + tempLen; j < sLength; j++) {
forCount++;
char two = s[j];
///> 判断是否有值
isHas = 1;
for (int c = 0; c < strlen(temp); c++) {
if (two == temp[c]) {
isHas = 2;
forCount++;
break;
}
///> 判断里面是否有重复的
for (int m = c + 1; m < strlen(temp); m++) {
if (temp[m] == temp[c]) {
isHas = 2;
forCount++;
break;
}
}
}
///> 如果没有那么 len加1
if (isHas == 1) {
temp[tempLen] = two;
tempLen++;
} else {
break;
}
}
}
printf("tempLen: %d %s\n",tempLen,temp);
return 0;
}
#pragma mark - 第一次优化
///> 思路没问题 需要查看的是是否有重复的判断。你看啊。如果 第一次得到三个。那么就不需要判断小于三的了 少了很多次数
///> 其实主要消耗是 字串是否存在于字符串当中
int lengthOfLongestSubstring(char* s) {
int sLength = (int)strlen(s);
if (sLength == 0) {
return 0;
}
int len = 1;
int tempLen = 1;
char temp[128];
int forCount = 0;
///> 1 表示没有。2 表示有
int isHas = 1;
///> 我的思路 从第一个找到最长的 然后第二个最长的 最后结束
for (int i = 0; i < sLength; i++) {
///> 重新初始化
memset(temp, 0, sizeof(temp));
char one = s[i];
len = 1;
temp[len - 1] = one;
forCount++;
for (int j = i + 1; j < sLength; j++) {
forCount++;
///> 判断temp 是否含有字符 two
isHas = 1;
for (int c = 0; c < strlen(temp); c++) {
if (s[j] == temp[c]) {
isHas = 2;
forCount++;
break;
}
}
///> 如果没有那么 len加1
if (isHas == 1) {
temp[len] = s[j];
len++;
if (len >= tempLen) {
tempLen = len;
}
} else {
break;
}
}
}
printf("tempLen: %d temp:%s forCount:%d \n",tempLen,temp,forCount);
return tempLen;
}
#pragma mark - 官方答题 优化方法 就在。判断temp 是否含有字符 two 【使用hash表】
int officialLengthOfLongestSubstring(char* s) {
return 0;
}
有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
例如，数组为【4,3,5,4,3,3,6,7】 结果应该返回【5,5,5,4,6,7】
qmax的放入规则：
依次遍历arr窗口数组，qmax的队头始终存放遍历的最大值对应的下标：
若 下一个数组值 <= 当前队尾所存下标对应的数组值，则将此值对应的下标存入队尾；
若 下一个数组值 > 当前队尾所存下标对应的数组值，则将当前队尾弹出，继续放入规则。
qmax的弹出规则：
弹出只在队头弹出，弹出的是过期的队头最大值对应的下标
---------------------
创建一个双端队列满足。
保持 队头存的下标对应的数组值一直是当前的最大值
