32. 最长有效括号
https://leetcode.cn/problems/longest-valid-parentheses/
typedef struct {
char a[30005];
int index[30005];
int top, index_top;
} stack;
int longestValidParentheses(char* s) {
int mark[30005] = {0};
stack A;
A.top = 0, A.index_top = 0;
int num = 0, num_temp = 0, i;
for (i = 0; * (s + i) != '\0'; i++) {
if (*(s + i) == '(') {
A.a[A.top++] = '(';
A.index[A.index_top++] = i;
} else {
if (A.top > 0 && A.a[A.top - 1] == '(') {
A.top--;
mark[A.index[(A.index_top--) - 1]] = 1;
mark[i] = 1;
}
}
}
for (int j = 0; j < i; j++) {
if (mark[j] == 1)num_temp++;
else {
if (num_temp > num)num = num_temp;
num_temp = 0;
}
}
if (num_temp > num)num = num_temp;
return num;
}1. 栈辅助匹配括号对
使用栈记录未匹配的左括号
'('的位置及其索引。当遇到左括号时，将其压入栈
a，并记录其索引到index数组中。当遇到右括号
')'时，检查栈是否非空且栈顶是左括号：若匹配成功，弹出栈顶的左括号，并标记该左括号和当前右括号的位置为有效（在
mark数组中标记为1）。
2. 标记有效位置
通过栈操作，所有匹配成功的括号对的位置会被标记为
1，无效的位置保持为0。
3. 统计最长连续有效长度
遍历
mark数组，统计连续为1的最大长度，即为最长有效括号子串的长度。
8. 字符串转换整数 (atoi)https://leetcode.cn/problems/string-to-integer-atoi/
int myAtoi(char* s) {
int length = strlen(s), q = 0, flag = 0;
while (q < length && s[q] == ' ')q++;
if (q < length && (s[q] == '-' || s[q] == '+')) {
flag = (s[q] == '+') ? 0 : 1;
q++;
}
long long int a = 0;
while (q < length && s[q] >= '0' && s[q] <= '9') {
if (a > (INT_MAX - (s[q] - '0')) / 10)return flag ? INT_MIN : INT_MAX;
a = a * 10 + s[q] - '0';
q++;
}
return flag ? -a : a;
}使用
long long int类型的变量a作为中间结果，避免在计算过程中溢出。溢出检查 ：在每次将新数字字符加入
a之前，检查是否会导致a超过INT_MAX的范围。如果
a > (INT_MAX - digit) / 10，说明再乘以 10 并加上当前数字digit就会溢出，此时直接返回INT_MIN或INT_MAX（根据符号flag）。
累加数字 ：将当前字符转换为数字后，累加到
a中。索引后移 ：继续处理下一个字符。
5. 最长回文子串https://leetcode.cn/problems/longest-palindromic-substring/
char* longestPalindrome(char* s) {
int length = strlen(s);
int max = 0, index;
for (int i = 0; i < length; i++) {
int left = i, right = i;
{
while (left >= 0 && right < length && s[left] == s[right]) {
left--, right++;
}
}
if (right - left - 1 > max) {
max = right - left - 1;
index = i;
}
left = i, right = i+1;
{
while (left >= 0 && right < length && s[left] == s[right]) {
left--, right++;
}
}
if (right - left - 1 > max) {
max = right - left - 1;
index = i;
}
}
int start,end;
if(max%2==1){
start=index-((max+1)/2-1);
end=index+((max+1)/2-1);
}
else {
start=index-(max/2-1);
end=index+max/2;
}
for(int i=start,j=0;i<=end;i++,j++){
s[j]=s[i];
}
s[max]='\0';
return s;
}回文子串的中心可以是单个字符（奇数长度）或两个字符之间的空隙（偶数长度）。代码通过遍历每个字符，分别扩展两种情况：
奇数长度回文 ：以当前字符
i为中心，向左右扩展。偶数长度回文 ：以当前字符
i和i+1之间的空隙为中心，向左右扩展。
每次扩展时，比较左右字符是否相等，直到不再匹配为止。记录扩展后的最大回文长度和对应的中心位置。