本文算法用C语言实现，编译环境是xcode。这里提供的方案仅供参考，如果有问题，欢迎指正。
括号匹配检验：假设表达式中允许包含两种括号，圆括号与方括号。其嵌套顺序随意，即([]())或者[([][])]都是正确的。而这[(]或者(()])或者([())都是不正确的格式。每日气温：根据每日气温列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。进制转换：给定一个十进制非零数字，将它转换为要求的进制，并输出。爬楼梯问题：假设你正在爬楼梯，需要n阶你才能到达楼顶。每次你可以爬1或2个台阶，你有多少种不同的方法可以爬到楼顶呢？(给定 n 是一个正整数)去除重复字母：给你一个仅包含小写字母的字符串，请去除字符串中重复的字母，使得每个字母只出现一次，需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
一、括号匹配检验
题目：假设表达式中允许包含两种括号，圆括号与方括号。其嵌套顺序随意，即([]()) 或者[([][])]都是正确的。而这[(]或者(()])或者([())都是不正确的格式。
例如：考虑以下括号的判断：[ ( [ ] [ ] ) ]。
思路：我们可以利用栈的特性，先进先出思想解决问题。
栈的代码实现：
typedef char SElemType;
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode;
typedef struct LinkStack{
StackNode *top;
int count;
}LinkStack;
int InitStack(LinkStack *S){
S->top = (StackNode *)malloc(sizeof(StackNode));
if (S->top == NULL) {
return 0;
}
S->top->next = NULL;
S->count = 0;
return 1;
}
int ClearStack(LinkStack *S){
StackNode *node = S->top;
if (node) {
StackNode *temp = node->next;
free(node);
node = temp;
}
S->count = 0;
return 1;
}
int Push(LinkStack *S, SElemType e){
StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
if (!temp) {
return -1;
}
temp->data = e;
temp->next = S->top;
S->top = temp;
S->count++;
return 1;
}
int Pop(LinkStack *S, SElemType *ele){
if (!S->top->next) {
return 0;
}
*ele = S->top->data;
StackNode *temp = S->top->next;
free(S->top);
S->top = temp;
S->count --;
return 1;
}
算法实现：
/**
思路：
1. 遍历[0，strlen(string)-1]
2. 遇到'['、'('，入栈
3. 遇到']'、')'，出栈，检查sting[i]和出栈数据是否配对
4. 遍历结束，判断栈是否为空，为空则匹配成功。
*/
int CheckData(LinkStack *S, char *string){
while (*string) {
char str = *string++;
SElemType tempData;
if (str == '[' || str == '(') {
Push(S, str);
}else if(str == ']'){
int res = Pop(S, &tempData);
if (res == 0 || tempData != '[') {
return 0;
}
}else if(str == ')'){
int res = Pop(S, &tempData);
if (res == 0 || tempData != '(') {
return 0;
}
}else{
return 0;
}
}
if (S->count > 0) {
return 0;
}
return 1;
}
int main(int argc, const char * argv[]) {
LinkStack stack;
char *sss = "[[()[()()]]";
InitStack(&stack);
int a = CheckData(&stack, sss);
if (a == 1) {
printf("括号匹配成功！\n");
}else{
printf("括号匹配失败！\n");
}
ClearStack(&stack);
return 0;
}
二、每日气温
题目：根据每日气温列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置0来代替。
例如：给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。提示：气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数
2.1 思路：暴力法
两层循环，第一层，从
i=0开始遍历（最后一个默认结果为0）；第二层从j=i+1开始，一直找到比i大的数据，结果为result[i] = j-i。
代码实现：
/*
1.创建一个result 结果数组，默认reslut[TSize-1] = 0;
2.从第 i=0 个元素遍历到最后一个元素[0,tSize-1];
2.1 遍历元素[j=i+1,TSize]
如果当前T[j]>T[i],则result[i] = j-i; 如果当前T[j]已经是最后一个元素,则默认result[i] = 0;
2.2 如果当前i >0 并且当前的元素和上一个元素相等,则没有必要继续循环. 如果result[i-1]等于0,则直接将result[i] = 0；否则result[i] = result[i-1]-1;
*/
int *dailyTemperatere(int *T, int tSize){
int *result = (int*)malloc(sizeof(int) * tSize);
result[tSize-1] = 0;
for (int i = 0; i<tSize-1; i++) {
//如果i和i-1的相等，那么直接用result[i-1]-1获取值
if (i > 0 && T[i] == T[i-1]) {
result[i] = (result[i-1] == 0 ? 0 : (result[i-1]-1));
}else{
for (int j=i+1; j<tSize; j++) {
//如果j > i，直接下标相减，得到结果。
if (T[j] > T[i]) {
result[i] = j - i;
break;
}
//如果遍历到最后，依然没有结果，i直接赋值0。
if (j == tSize-1) {
result[i] = 0;
}
}
}
}
return result;
}
int main(int argc, const char * argv[]) {
int test[10]= {3, 5, 2, 4, 6, 6, 9, 4, 2}; //1 3 1 1 2 1 0 0 0
int *result = dailyTemperatere(test, 9);
for (int i = 0; i < 9;i++ ) {
printf("%d ",result[i]);
}
printf("\n");
return 0;
}
2.2 思路：跳跃法
代码实现：
/*
1、创建一个result结果数组，默认reslut[TSize-1] = 0;
2、从TSize-2个元素遍历到第一个元素[TSize-2,0];
2.1、从[j = i+1,TSize]遍历, j+=result[j],利用已经有结果的位置进行跳跃,减少遍历次数
T[i]<T[j],那么Result = j - i
若reuslt[j] == 0,则表示后面不会有更大的值,那么当前值就应该也是0;
注意：因为是从右往左遍历，所以result[j]肯定已经有解
*/
int *dailyTemperatere(int *T, int tSize){
int *result = (int*)malloc(sizeof(int) * tSize);
result[tSize-1] = 0;
for (int i=tSize-1; i>=0; i--) {
for (int j=i+1; j<tSize; j+=result[j]) {
if (T[i] < T[j]) {
result[i] = j - i;
break;
}else{
if (result[j] == 0) {
result[i] = 0;
break;
}
}
}
}
return result;
}
下图可配合思考
每日温度-跳跃法.png
2.3 思路：栈
代码实现：
/*
1. 初始化result数组，并赋初值0；
2. 初始化一个栈stackIndex，栈中存储的是元素的索引值;
3. 遍历整个温度数组从[0,TSize];
3.1. 如果栈顶元素<当前元素,则将 [当前元素索引index - 栈顶元素index]，计算完毕则将当前栈顶元素移除;
出栈后,只要栈不为空，继续比较,直到栈顶元素不能满足T[i] > T[stack_index[top-1]]
3.2. 如果当前的栈为空；或，当前的元素小于栈顶元素；都直接入栈;
3.3. while循环结束后,当前元素也需要入栈;
*/
int *dailyTemperatere(int *T, int tSize){
int *result = (int*)malloc(sizeof(int) * tSize);
for (int i=0; i<tSize; i++) {
result[i] = 0;
}
int *stackIndex = (int *)malloc(sizeof(int) * tSize);
int top = 0;
for (int i=0; i<tSize; i++) {
printf("\n循环第%d次,i = %d\n",i,i);
// 若当前元素大于栈顶元素，栈顶元素出栈。即温度升高了，所求天数为两者下标的差值。
while (top>0 && T[i] > T[stackIndex[top-1]]) {
int tIndex = stackIndex[top-1];
result[tIndex] = i - tIndex;
top--;
printf("tIndex = %d; result[%d] = %d, top = %d \n",tIndex,tIndex,result[tIndex],top);
}
stackIndex[top] = i;
top++;
printf(" top = %d \n",top);
}
return result;
}
进制转换：
三、进制转换
题目：给定一个十进制非零数字，将它转换为要求的进制，并输出。
例如：十进制的97，转换为二进制1 1 0 0 0 0 1。
代码实现：
void exchange(int T){
int *result = (int *)malloc(sizeof(char) * 100);
int top = -1;
while (T) {
int temp = T % 2;
result[++top] = temp;
T = T/2;
}
//出栈打印数据
while (top >= 0) {
printf("%d ", result[top--]);
}
}
为了帮助理解，简化问题。也可以将获取
二进制，先改为获取十进制，即把2改为10。
四、爬楼梯问题
题目：假设你正在爬楼梯，需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶，你有多少种不同的方法可以爬到楼顶呢？(给定 n 是一个正整数)
例如：
1个台阶:11
2个台阶:21-1，2
3个台阶:31-1-1，1-2，2-1
4个台阶:51-1-1-1，1-1-2，1-2-1，2-1-1，2-2
4.1 递归
以下情况，我们可以考虑用
递归解决问题：
定义是递归的，如，阶乘、斐波拉契数列等。类似这种复杂问题，若能够分解成几个简单且解法相同或类似的子问题，这种分治法可以使问题简单且有规律，同时必须有一个明确的出口，便可以递归求解。- 数据结构是递归的
- 问题的解法是递归的，如Hanoi塔问题。
思路：
假设有n个台阶，共有f(n)种方式；
如果第一步，走1步，那此时共有f(n-1)种方式；
如果第一步，走2步，那此时共有f(n-2)种方式；
总结：因为每一步都只有两种方式，所以可以简化为，f(n) = f(n-1) + f(n-2)。
代码实现：
int climbStairsz(int n){
if(n<1) return 0;
if (n == 1) return 1;
if (n == 2) return 2;
int result = climbStairsz(n-1) + climbStairsz(n-2);
return result;
}
4.2
参考4.1，代码实现可以优化为：
int climbStairsz(int n){
int *sum = (int *)malloc(sizeof(int) * (n+1));
sum[0] = 0;
sum[1] = 1;
sum[2] = 2;
for (int i = 3; i <= n; i++) {
sum[i] = sum[i-1] + sum[i-2];
}
return sum[n];
}
五、去除重复字母
题目：给你一个仅包含小写字母的字符串，请去除字符串中重复的字母，使得每个字母只出现一次，需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
例如：
-
bcabc你应该返回abc，而不是bca，cab； -
cbacdcbc应该返回acdb，而不是cbad，bacd，adcb。
思路：以下文字描述，仅供参考
假设字符串 s = {b c a b c}，去重后的存入栈stack = {}并返回；首先从左至右遍历s；
-
b，此时stack为空，入栈，stack = {b}; -
c，stack没有c，且c>b，入栈，stack = {b c}； -
a，遍历stack
3.1. stack没有a，但是a<c，此时a后面还有c，即c出现的次数不为1；
3.1.1. 移除c，stack = {b}。
3.2. 继续遍历stack = {b}，a<b，此时a后面还有b，即b出现的次数不为1；
3.2.1. 移除b，stack = {};
3.3. 此时stack为空，a，入栈，stack = {a}; -
b，同上比较； -
c，同上比较。 -
stack = {a b c}，结束并返回结果。
代码实现：
char *removeDuplicateLetters(char *s){
//1、特殊情况处理
if (s==NULL || strlen(s)==0) {
return "#";
}
if (strlen(s) == 1) {
return s;
}
//2、记录字母出现次数
int length = (int)strlen(s);
//记录字符串中每个字母出现的次数，小写字母总共26个
char record[26] = {0};
for (int i=0; i<length; i++) {
int letterIndex = s[i]-'a';
record[letterIndex]++;
}
//3、字符串stack，最终去重、字典序最小的字符串
char *stack = (char *)malloc(sizeof(char) * length*2);
//memset(void *s, int ch, size_t n) 将stack的空间填充0;
memset(stack, 0, length*2 * sizeof(char));
int top = -1;
//4、遍历，入栈
for (int i=0; i<length; i++) {
//4.1、isExist 标记, 判断当前字符是否存在栈中;
int isExist = 0;
//遍历stack，判断当前字符s[i]是否已经入栈
for (int j=0; j<=top; j++) {
if (stack[j] == s[i]) {
isExist = 1;
break;
}
}
if (isExist == 1) {
//如果已经入栈，那么s[i]的次数 -1；
record[s[i]-'a']--;
}else{
//4.2.2
//如果不存在，则准备入栈
//如果s[i]比栈顶元素小，且栈顶元素的次数还不为0，那就出栈，循环比较。直到条件不成立，入栈
// 如当前stack = {c, j, y}, s[i] = d，且j和y的次数不为0，那就是后面还有，那就把j和y出栈，并把出现次数-1，d入栈。
// 此时，stack = {c, d}
while (top > -1 && stack[top] > s[i] && record[stack[top]-'a'] > 1) {
record[stack[top]-'a']--;
top--;
}
stack[++top] = s[i];
}
}
return stack;
}
以上代码仅供参考，如有问题，欢迎指正、交流学习。
网友评论