洛谷P1601 高精精度加法

题目描述

高精度加法，相当于 a+b problem，不用考虑负数。

输入格式

分两行输入。$a,b \leq 10^{500}$。

输出格式

输出只有一行，代表 $a+b$ 的值。

样例

样例输入 #1

1
1

样例输出 #1

2

样例输入 #2

1001
9099

样例输出 #2

10100

提示

$20\%$ 的测试数据，$0\le a,b \le10^9$；

$40\%$ 的测试数据，$0\le a,b \le10^{18}$。

解题思路

整体思路：通过字符串读入输入值，通过模拟竖式计算结果

读入输入值

scanf("%s%s", num1, num2);    // cin >> num1 >> num2;

将字符串反转

通常竖式由个位开始计算，依次向前。但是程序读入数据后第一位为最高位，而个位在最后一位，为了使其适应人类的计算方式，我们将字符串进行反转。

void reverseString(char *str) {
    int len = strlen(str);               // 获取字符串长度
    for (int i = 0; i < len / 2; i++) {  // 进行循环，将第一位和最后一位对换
        char temp = str[i];
        str[i] = str[len - i - 1];
        str[len - i - 1] = temp;
    }
}

模拟竖式求解

char* addStrings(char *num1, char *num2) {
    static char result[MAX_DIGITS];
    int carry = 0;           // 进位
    int i = 0;               // 设置循环索引，用于存储计算到第几位

    int len1 = strlen(num1); // 计算 num1 的长度
    int len2 = strlen(num2); // 计算 num2 的长度
    reverseString(num1);     // 将 num1 进行字符串反转
    reverseString(num2);     // 将 num2 进行字符串反转

    /* 从最低位开始逐位相加 */
    while (i < len1 || i < len2 || carry) {
        /* 从输入字符串中获取当前位的数字，如果已经到达字符串末尾，则设为 0 */
        int x = (i < len1) ? (num1[i] - '0') : 0;
        int y = (i < len2) ? (num2[i] - '0') : 0;

        /* 将当前位的数字与进位相加 */
        int sum = x + y + carry;
        carry = sum / 10;             // 计算进位
        result[i] = (sum % 10) + '0'; // 将当前位的和转为字符存入结果数组

        /* 更新索引 */
        i++;
    }

    result[i] = '\0';      // 在结果数组末尾加上字符串结束标志
    reverseString(result); // 反转结果字符串以获得正确的输出顺序

    return result;
}

完整代码

#include <stdio.h>
#include <string.h>

#define MAX_DIGITS 1000  

/* 反转字符串 */
void reverseString(char *str) {
    int len = strlen(str);               // 获取字符串长度
    for (int i = 0; i < len / 2; i++) {  // 进行循环，将第一位和最后一位对换
        char temp = str[i];
        str[i] = str[len - i - 1];
        str[len - i - 1] = temp;
    }
}

/* 模拟竖式求解 */
char* addStrings(char *num1, char *num2) {
    static char result[MAX_DIGITS];
    int carry = 0;           // 进位
    int i = 0;               // 设置循环索引，用于存储计算到第几位

    int len1 = strlen(num1); // 计算 num1 的长度
    int len2 = strlen(num2); // 计算 num2 的长度
    reverseString(num1);     // 将 num1 进行字符串反转
    reverseString(num2);     // 将 num2 进行字符串反转

    /* 从最低位开始逐位相加 */
    while (i < len1 || i < len2 || carry) {
        /* 从输入字符串中获取当前位的数字，如果已经到达字符串末尾，则设为 0 */
        int x = (i < len1) ? (num1[i] - '0') : 0;
        int y = (i < len2) ? (num2[i] - '0') : 0;

        /* 将当前位的数字与进位相加 */
        int sum = x + y + carry;
        carry = sum / 10;             // 计算进位
        result[i] = (sum % 10) + '0'; // 将当前位的和转为字符存入结果数组

        /* 更新索引 */
        i++;
    }

    result[i] = '\0';      // 在结果数组末尾加上字符串结束标志
    reverseString(result); // 反转结果字符串以获得正确的输出顺序

    return result;
}

int main() {
    char num1[MAX_DIGITS], num2[MAX_DIGITS], ans[MAX_DIGITS];

    /* 读入用户输入 */
    scanf("%s%s", num1, num2);

    strcpy(ans, addStrings(num1, num2));  // 将 addStrings(num1, num2) 中的值赋予 ans

    printf("%s\n", ans);

    return 0;
}

问题思考

  • 1- strcpy是什么？

    C语言无法直接使用=将一个字符数组的值赋予另一个字符数组，我们需要使用strcpy 函数来复制一个字符串到另一个字符串。

    你可以把strcpy(ans, addStrings(num1, num2));简单的理解为ans = addStrings(num1, num2);，当然，后者在C语言中是不正确的。

  • 2- 为什么使用char*

    addStrings 函数的返回类型应为 char*，而不是 char。因为它返回一个字符串，而不是一个字符。

  • 3- 为什么在addStrings函数中使用static char而不是char

    static char 和 char 在C语言中有明显的区别：

    1. 存储类型：

      • char：声明一个字符变量，它的生存期与所在函数的生存期相同，当函数执行完毕时，该变量会被销毁。
      • static char：static 用于改变变量的存储类型，使其成为静态变量。静态变量的生存期在整个程序的运行期间都存在，它在首次进入声明它的函数时被初始化，然后保留其值直到程序结束。

    2. 作用范围：

      • char：通常在局部作用域内定义，只能在所在函数中访问。
      • static char：静态变量可以在声明它的函数以及其他函数中访问。

    3. 初始化：

      • char：在函数中声明的普通字符变量通常不会自动初始化，它们的值是不确定的（垃圾值）。
      • static char：静态字符变量会在第一次进入声明它的函数时自动初始化为零或'\0'（空字符）。

    4. 用途：

      • char：通常用于声明普通的局部字符变量，用于存储特定的字符数据。
      • static char：静态字符变量通常用于在函数调用之间保留值，例如，用于记录函数调用的计数或在递归函数中保持状态。

    总之，static char 是具有静态存储期的字符变量，其生存期跨越函数调用，而 char 是普通的自动字符变量，其生存期限定在所在函数的执行期间。

  • 4- 上面的三个问题不好理解，是否有其它解决办法？

    当然，如果不涉及返回值的问题当然也就不存在这些问题了，下面是一个简单的参考：

    void addStrings(char *num1, char *num2, char *result) { ... }

int main(){
    ...
    addStrings(num1, num2, result);
    ...
}

    我们让addStrings直接把值写入了result，所以自然也不必担心返回值和作用域的问题了。

    • 使用该方法的完整代码示例：

      #include <stdio.h>
#include <string.h>

#define MAX_DIGITS 1000

/* 反转字符串 */
void reverseString(char *str) {
    int len = strlen(str);               // 获取字符串长度
    for (int i = 0; i < len / 2; i++) {  // 进行循环，将第一位和最后一位对换
        char temp = str[i];
        str[i] = str[len - i - 1];
        str[len - i - 1] = temp;
    }
}

/* 模拟竖式求解 */
void addStrings(char *num1, char *num2, char *result) {
    int carry = 0;           // 进位
    int i = 0; // 设置循环索引，用于存储计算到第几位

    int len1 = strlen(num1); // 计算 num1 的长度
    int len2 = strlen(num2); // 计算 num2 的长度
    reverseString(num1);     // 将 num1 进行字符串反转
    reverseString(num2);     // 将 num2 进行字符串反转

    /* 从最低位开始逐位相加 */
    while (i < len1 || i < len2 || carry) {
        /* 从输入字符串中获取当前位的数字，如果已经到达字符串末尾，则设为 0 */
        int x = (i < len1) ? (num1[i] - '0') : 0;
        int y = (i < len2) ? (num2[i] - '0') : 0;

        /* 将当前位的数字与进位相加 */
        int sum = x + y + carry;
        carry = sum / 10;             // 计算进位
        result[i] = (sum % 10) + '0'; // 将当前位的和转为字符存入结果数组

        /* 更新索引 */
        i++;
    }

    result[i] = '\0';      // 在结果数组末尾加上字符串结束标志
    reverseString(result); // 反转结果字符串以获得正确的输出顺序
}

int main() {
    char num1[MAX_DIGITS], num2[MAX_DIGITS], result[MAX_DIGITS];

    /* 读入用户输入 */
    scanf("%s%s", num1, num2);

    addStrings(num1, num2, result);

    printf("%s\n", result);

    return 0;
}

或者，你也可以选择在外部声明全局变量，这样也可以规避函数返回值的问题。

尽管全局变量在某些情况下可能是有用的，但应该谨慎使用，并且应该遵循一些最佳实践，如将全局变量声明为static以限制其作用域，以及尽量减少全局变量的数量。在大多数情况下，应该优先使用局部变量和参数传递来确保代码的可维护性和可扩展性。

LeetCode7: 整数反转

题目描述：

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。

解题思路：

首先映入本脉脑海的是这道题好简单啊，不就是把每位提出来然后反转一下。当然这不太像是lc评级中等的难度，我又仔细审了一遍题，额，这“不允许存储 64 位整数”是什么意思。看了一下题解，原来内存中不能出现超过2147483647的数，那就来吧。
其实首先想到的就是字符串反转，毕竟字符串反转多方便，然后只要把字符串和2147483647比较就好啦，字符串肯定不会超32位的lol
当然，还有一种办法就是每反转一位就判断一下下一位会不会超出范围。

代码1：

class Solution:
def reverse(self, x: int) -> int:
    num = x  # 将输入的整数赋值给变量num
    isNegative = False  # 初始化一个标志位，用于表示输入数字的正负
    if num < 0:  # 判断输入数字是否为负数
        isNegative = True  # 如果是负数，则将标志位置为True
        num = -num  # 取输入数字的绝对值
    str_num = str(num)  # 将数字转换为字符串
    reversed_str = str_num[::-1]  # 将字符串进行反转
    if len(str_num) > 10:  # 判断反转后的字符串长度是否大于10
        ans = 0  # 如果大于10，将结果置为0
    elif len(str_num) == 10:  # 如果字符串长度等于10
        if reversed_str > "2147483647":  # 判断反转后的字符串表示的数字是否大于32位有符号整数的最大值
            ans = 0  # 如果大于最大值，将结果置为0
        else:
            ans = int(reversed_str)  # 否则转换为整数
    else:  # 如果字符串长度小于10
        ans = int(reversed_str)  # 将反转后的字符串转换为整数
    if isNegative:  # 如果输入数字为负数
        ans = -ans  # 将结果置为负数
    return ans  # 返回结果

代码2（LeetCode官方题解）：

class Solution:
def reverse(self, x: int) -> int:
    INT_MIN, INT_MAX = -2**31, 2**31 - 1

    rev = 0
    while x != 0:
        # INT_MIN 也是一个负数，不能写成 rev < INT_MIN // 10
        if rev < INT_MIN // 10 + 1 or rev > INT_MAX // 10:
            return 0
        digit = x % 10
        # Python3 的取模运算在 x 为负数时也会返回 [0, 9) 以内的结果，因此这里需要进行特殊判断
        if x < 0 and digit > 0:
            digit -= 10

        # 同理，Python3 的整数除法在 x 为负数时会向下（更小的负数）取整，因此不能写成 x //= 10
        x = (x - digit) // 10
        rev = rev * 10 + digit
    
    return rev

学习笔记

Python如何反转字符串：

reversed_str = str_num[::-1]

[::-1]表示从头到尾以步长为-1的方式进行切片，实现了字符串的反转。

如何用字符串判断是否超过32位

reversed_str > "2147483647"这个判断是因为在Python中，字符串之间的比较是按照字典序进行的。因此，如果一个字符串表示的数字大于另一个字符串表示的数字，那么这两个字符串进行大小比较时，结果也会反映出数字的大小关系。在这里，"2147483647"是32位有符号整数的最大值，因此通过比较reversed_str与"2147483647"的大小关系，可以判断反转后的数字是否超出32位有符号整数的范围。

总结

不得不说，虽然确实不是一帆风顺，但是这道题在一众lc中等难度的题目里确实很简单orz

LeetCode 135 分发糖果

题目描述

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

思路

思路1

找到所有孩子中评分最低的发一个糖果，以这个孩子为界，将孩子分为两部分（如果有n个孩子评分一样低则分为n+1个部分），每部分再找出评分最低的孩子，如果这个孩子两侧没有已分到糖果的孩子，就给这个孩子1个糖果，如果两侧有已分到糖果的孩子，设较多的分得m个，则给这个孩子m+1个糖果。依此类推，直至所有孩子都分到糖果。

思路2

觉得上面的思路实现起来稍微复杂，于是研究了官方题解，思路为进行左右两次扫描，我的理解如下：

如果要保证每个相邻的孩子如果得分高就要分到更多糖果，只需要确保如果第n个同学的得分比第n-1个同学高就比第n-1个同学多分到至少一个糖果和如果比第n+1个同学高就比第n+1个同学多分到至少一个糖果即可。换句话说只要保证第n个同学与他左右的两个同学满足题目要求即可。所以我们第一步先从左至右扫描，如果n-1评分低于n，则给n多分一个糖果，否则就给他一个糖果。第二次从右至左的扫描类似，如果n+1的评分低于n则给n多分一个糖果，否则保留n的原有糖果数。

经过这样的两次扫描，我们就可以确保每个同学的左右说满足题意的，进而确保了整个班的同学都会满意。

思路3

在看完官方题解后我钻起了牛角尖：到底能不能只扫描一次就确定需要的糖果数呢？

经过了不懈尝试，答案是肯定的，思路如下：

从头扫描，如果某一段序列是递增的，则这段序列中第n个同学应分到n个糖果，如果发现某一段序列是递减的，那么第n个同学应分到1个糖果，并给这个序列的前n-1个同学每人补发一个糖果，即增加n个糖果。特别的，如果某个极值点是极大值点，那么在计算它的递减序列时要判断它后面的递减序列是否长于之前的递增序列，如果是，要给位于极大值点的同学补发相应数量的糖果。

思路4

希望进一步优化思路3，我们发现只要某一段的n个评分是递增或者递减的，那么这一段的糖果数量在一般情况下应该是n*(n+1)/2的，我们只需要找到极值点并计算他们的长度即可。

代码

思路2代码

int candy(int* ratings, int ratingsSize) {
    int left[ratingsSize];
    for (int i = 0; i < ratingsSize; i++) {
        if (i > 0 && ratings[i] > ratings[i - 1]) {
            left[i] = left[i - 1] + 1;
        } else {
            left[i] = 1;
        }
    }
    int right = 0, ret = 0;
    for (int i = ratingsSize - 1; i >= 0; i--) {
        if (i < ratingsSize - 1 && ratings[i] > ratings[i + 1]) {
            right++;
        } else {
            right = 1;
        }
        ret += fmax(left[i], right);
    }
    return ret;
}

思路3代码

int candy(int* ratings, int n) {
  if(n < 2) return n;
  int up = 0, down = 0, peak = 1, sum = 1;
  for(int i = 1; i < n; i++) {
    if(ratings[i] > ratings[i-1]) { // 如果是上升的趋势
      up++;                         // 记录上升的次数
      down = 0;                     // 下降的次数清零
      peak = up + 1;                // 记录最近的峰值
      sum += 1 + up;                // 计算总和
    } else if(ratings[i] == ratings[i-1]) { // 如果是相等的
      peak = 1;                     // 峰值清零
      up = 0;                       // 上升次数清零
      down = 0;                     // 下降次数清零
      sum += 1;                     // 总和加一
    } else {                        // 如果是下降的趋势
      up = 0;                       // 上升次数清零
      down++;                       // 下降次数加一
      sum += down + (peak > down ? 0 : 1); // 总和加上下降次数并判断是否超过峰值
    }
  }
  return sum;
}

总结

作为一道LeetCode困难难度的题，还是需要经过一段时间的思考才能给出比较好的方法，会尝试能否补全所有思路的代码。

LeetCode 42 接雨水

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路

思路1

逐行判断，从第一行开始循环判断最高的柱子的高度次，每次循环找到这一高度中第一个和最后一个不为空的柱子，那么这两根柱子之间的每根柱子只要小于当前循环判断的高度，那么就可以累计一个单位的雨水。
这一思路的时间复杂度比较高，遇到大规模数据时会超时。

思路2

使用双指针，从数组的两端开始向中间遍历。对于每个位置：

  • 如果左端的高度小于右端的高度，那么我们移动左指针，并更新左边最高的高度（leftMax）。如果当前位置的高度小于leftMax，它就能接到水，其量为leftMax减去当前高度。
  • 如果左端的高度大于等于右端的高度，那么我们移动右指针，并更新右边最高的高度（rightMax）。如果当前位置的高度小于rightMax，它也能接到水，其量为rightMax减去当前高度。

代码实现

代码1

int trap(int* height, int heightSize){
    bool isTop;
    int layer = 1, begin, end, ans = 0;
    do{
        isTop = true;
        begin = end = -1;
        for(int i = 0; i < heightSize; i++){
            if(height[i] >= layer){
                if(begin == -1) begin = i;
            }
            if(height[heightSize - i - 1] >= layer){
                if(end == -1) end = heightSize - i - 1;
            }
            if(begin != -1 && end != -1){
                isTop = false;
                break;
            }
        }
        if(!isTop)
            for(int i = begin + 1; i < end; i++)
                if(height[i] < layer) ans++;
        layer++;
    }while(!isTop);

    return ans;
}

代码2

int trap(int* height, int heightSize) {
    int left = 0, right = heightSize - 1;
    int leftMax = 0, rightMax = 0;
    int ans = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                ans += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                ans += rightMax - height[right];
            }
            right--;
        }
    }
    
    return ans;
}
最后修改：2023 年 12 月 30 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏