题目:给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足:
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。
我们的思路是,考虑到它的括号匹配,先进的后出,后进的先出,这就符合栈的进出,所以我们用栈的思想做;
下面看代码和注释:
char func(char ch)
{
if (ch == ')')
return '(';
else if (ch == ']')
return '[';
else if (ch == '}')
return '{';
else
return 0;
}
bool isValid(char* s)
{
int len = strlen(s);
//如果长度为奇数,直接返回false
if (len % 2 == 1)
{
return false;
}
//top记录栈顶的位置
int top = 0;
//创建一个栈
char stack[len + 1];
//从头开始循环
for (int i = 0; i < len; i++)
{
//将每个字符都传进func函数判断,若是左括号则进栈,返回0,栈顶往上走
//若是右括号,返回它对应的左括号,即弹出对应的左括号(出栈),因为先进的后出,后进的先出,栈顶往下
if (func(s[i]))
{
//这里要判断一开始就是不是右括号,若是,即top为0,直接返回false
//还要判断当前栈顶的下一个元素是否与当前的右括号匹配,若不相等也返回false
if (top == 0 || stack[top - 1] != func(s[i]))
{
return false;
}
top--;
}
else
{
stack[top] = s[i];
top++;
}
}
//判断当前栈是否为空,若栈里只有左括号没有右括号,左括号就没得抵消,当前的栈应该不为空,top==0为假,即为false
//若栈中的左括号全被抵消,top==0为真,返回true;
return top == 0;
}
题目:给你一个升序排列 的数组 nums ,请你原地 删除重复出现的元素,使每个元素只出现一次 ,返回删除后数组的新长度。元素的相对顺序应该保持一致 。
我们的思路是双指针,一个是fast,一个是slow,一开始两个都赋给1(fast和slow都是作为元素的下标),当fast和fast-1对应的元素相等,fast就往后走 ,直到它们不相等, 这就说明slow到fast-1对应的元素都是相等的,所以把fast对应的元素赋给slow对应的元素,slow再往后走;循环往复,直到fast大于数组长度,循环结束;
下面看代码和注释:
int removeDuplicates(int* nums, int numsSize)
{
//如果数组长度为0,返回0
if (numsSize == 0)
return 0;
//“双指针”问题,下标都从1开始
int fast = 1;
int slow = 1;
//当快的“指针”的下标小于数组长度继续
while (fast < numsSize)
{
//当fast下标对应的元素与它后一个元素不相等时,证明slow到fast-1的元素都是相等的;
//所以将slow下标对应的元素改成fast下标对应的元素,slow再跳到下一个去
if (nums[fast] != nums[fast - 1])
{
nums[slow] = nums[fast];
slow++;
}
//如果fast与fast-1对应的元素相等,fast往后走
fast++;
}
//返回slow的长度
return slow;
}