Leetcode-20.有效的括号
题目:给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 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; }
Leetcode-26.删除有序数组中的重复项
题目:给你一个升序排列 的数组 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; }