Algorithm 第六周
LeetCode 682. Baseball Game 题目链接 解题语言 C
你现在是棒球比赛记录员。
给定一个字符串列表，每个字符串可以是以下四种类型之一：
1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
- "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
- "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
- "C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。
每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。
示例 1:
输入: ["5","2","C","D","+"]
输出: 30
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到2分。总和是：7。
操作1：第2轮的数据无效。总和是：5。
第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
第4轮：你可以得到5 + 10 = 15分。总数是：30。
参考代码
解题思路 ：每次操作的数字由数组 stack 存储 ，按照栈的思想每次从栈顶出栈 ，栈顶入栈。
int calPoints(char** ops, int opsSize) {
int sum = 0, temp;
int stack[opsSize];//C99 变长数组
int *p =stack;//定义指针指向数组的第一个元素
for (int i = 0; i < opsSize; i++, ops++)
{
switch (**ops)//**ops 表示的是指针所指向的字符数组的第一个字母
{
case '+':
temp = *p;
p--;
temp += *p;
sum += temp;
p += 2;
*p = temp;
break;
case 'D':
temp = *p;
temp *= 2;
sum += temp;
p++;
*p = temp;
break;
case'C':
temp = *p;
sum -= temp;
p--;
break;
default:
temp = atoi(*ops);//将字符串转化成数字 ，需要引入库 stblib.h
sum += temp;
p++;
*p = temp;
break;
}
}
return sum;
}
LeetCode 496. Next Greater Element I 题目链接 解题语言 C
给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
优化思路 ：将不必要的循环嵌套拆开 ，减少内存消耗
优化后代码
int* nextGreaterElement(int* findNums, int findNumsSize, int* nums, int numsSize, int* returnSize) {
int* p = (int *)malloc(sizeof(int)*findNumsSize);
*returnSize = findNumsSize;
int i = 0, j = 0;
while (i < findNumsSize)
{
j = 0;
int flag = 0;
while (*(nums + j) != *(findNums + i))//找到子集元素在合集中的索引
{
j++;
}
for (; j < numsSize; j++)
{
if (*(nums + j)>*(findNums + i))//找到元素右边第一个更大元素时结束循环
{
*(p + i) = *(nums + j); flag = 1;
break;
}
}
if (flag == 0)//如果没有找到更大素 ，则设为 -1
*(p + i) = -1;
i++;
}
return p;
}
优化前代码
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* nextGreaterElement(int* findNums, int findNumsSize, int* nums, int numsSize, int* returnSize) {
int* p = (int *)malloc(sizeof(int)*findNumsSize);
*returnSize = findNumsSize;
for (int i = 0; i < findNumsSize; i++)
{
for (int j = 0; j < numsSize; j++)
{
int flag = 0;
if (*(findNums + i) == *(nums + j))
{
for (int k = j; k < numsSize; k++)
{
if (*(nums + k) >*(nums + j))
{
//printf("%d ", *(nums + k));
*(p + i) = *(nums + k); flag = 1;
break;
}
}
if (flag == 0)
*(p + i) = -1;
}
}
}
return p;
}
