数学题合集

6. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、',' 和 '.' 组成
• 1 <= numRows <= 1000

C++

/*
找规律
4行的:
0     6      12        18
1   5 7   11 13    17
2 4   8 10   14 16
3     9      15

对于n行的, s中的第i个字符,对余数进行判断:
i%(2n-2) == 0 ----> row0
i%(2n-2) == 1 or 2n-2-1 ----> row1
i%(2n-2) == 2 or 2n-2-2 ----> row2
...
i%(2n-2) == n-1 ----> row(n-1)
==>

对 k = i%(2n-2)进行判断:
k<=n-1时候，s[i]就属于第k行
k>n-1时候，s[i]就属于2n-2-k行

最后将rows拼接起来就行了
*/
class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) return s;
        vector<string> rows(numRows);
        for(int i = 0; i < s.size(); i ++){
            int k = i%(2*numRows - 2);
            if(k <= numRows - 1){
                rows[k] += s[i];
            }
            else rows[2*numRows - 2- k] += s[i];
        }
        string res = "";
        for(auto elem : rows){
            res += elem;
        }
        return res;
    }
};

7. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321

示例 2：

输入：x = -123
输出：-321

示例 3：

输入：x = 120
输出：21

示例 4：

输入：x = 0
输出：0

提示：

• -231 <= x <= 231 - 1

C++

class Solution {
public:
    int reverse(int x) {
        if(!x) return 0; 
        string res;
        if(x < 0) res += '-';
        while(x != 0){
            int temp = x % 10;
            res += to_string(abs(temp));
            x = x / 10;
        }
        return stol(res) > INT_MAX || stol(res) <INT_MIN ? 0 : stol(res); // string -> long
    }
};

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

C++

• 我们想要让指针移动后的容器面积增大，就要使移动后的容器的高尽量大，所以我们选择高较小的那个指针进行移动，这样我们就保留了容器较高的那条边，放弃了较小的那条边，以获得有更高的边的机会

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0;
        int r = height.size() - 1;
        int res = 0;
        while(l < r){
            res = max(res, (r - l) * min(height[l], height[r]));
            if(height[l] <= height[r]) l ++;
            else r --;
        }
        return res;
    }
};

238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请不要使用除法，且在 O(*n*) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

C++

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        int left = 1, right = 1;     //left：左边累乘积，right：右边累乘积
        vector<int> res(n, 1);
        
        for(int i = 0; i < n; ++ i)    //最终每个元素其左右乘积进行相乘得出结果
        {
            res[i] *= left;       //乘以其左边的乘积
            left *= nums[i];
            
            res[n - 1 - i] *= right;  //乘以其右边的乘积 取n - 1, n - 2, ..., 2, 1, 0
            right *= nums[n - 1 - i];
        }
        
        return res;
    }
};