微软笔试2022.8.25

1.Challenge 1 description
Write a function solution that, given an integer N, returns the maximum possible value obtainable by deleting one ‘5’ digit from the decimal representation of N. It is guaranteed that N will contain at least one ‘5’ digit. Examples:

1. Given N = 15958,the function should return 1958.
   2.Given N = -5859,the function should return -589.
   3.Given N =-5000,the function should return 0. After deleting the ‘5’, the only digits in the number are zeroes, so its value is 0. Assume that:
   ·N is an integer within the range [-999,995…999,995];
   ·N contains at least one ‘5’ digit in its decimal representation;·N consists of at least two digits in its decimal representation.
   In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

题意：求删除一个整数N中的一个5之后，最大的整数。

比如，N = 15958,返回1958.

#include
#include
using namespace std;

int main(){
    int n;
    cin >> n;
    string s = to_string(n);
    //cout<
    int maxnum = INT_MIN;
    for(int i = 0; i < s.size(); i++){
        string temp = s;
        if(temp[i] == '5'){
            temp.erase(i,1);
            maxnum = max(maxnum,atoi(temp.c_str())); 
        }
        //cout<
    }
    cout<<maxnum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2. Challenge 2 description
   Write a function solution that, given an array A consisting ofN integers, returns the number of fragments of A whose sum equals 0(that is,pairs(PQ)such that P≤Q and the sum A[P]+A[P+1] +…. +A[Q] is 0). The function should return -1 if this number exceeds 1,000,000,000. Examples:
   1.Given A=[2,-2,3,0,4,-7the function should return 4, as explained on this picture:

2.Given A =[0,0,…, 0] of length 100,000, the function should return -1. Write an efficient algorithm for the following assumptions:
N is an integer within the range [1…100,000):
each element of array A is an integer within the range[-10,000…10,000].

题意：求等于0的子序列有多少个

using namespace std;
typedef long long ll;

ll sum[100100];
unordered_map<ll, int> cnt;
int solution(vector<int> &A) {
    // write your code in C++ (C++14 (g++ 6.2.0))
    sum[0] = A[0];
    long long ans = 0; 
    cnt[sum[0]] ++;
    if(sum[0] == 0) ans ++;
    for(int i = 1; i < A.size(); i ++) {
        sum[i] = sum[i-1] + A[i];
        if(sum[i] == 0) {
            ans += cnt[0] + 1;
            cnt[0] ++;
            continue;
        }
        ans += cnt[sum[i]];
        cnt[sum[i]] ++;
    }
    if(ans > (ll)1e9) return -1;
    return (int)ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.等差数列
同力扣原题：
https://leetcode.cn/problems/arithmetic-slices/solution/

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) {
            return 0;
        }

        int d = nums[0] - nums[1], t = 0;
        int ans = 0;
        // 因为等差数列的长度至少为 3，所以可以从 i=2 开始枚举
        for (int i = 2; i < n; ++i) {
            if (nums[i - 1] - nums[i] == d) {
                ++t;
            }
            else {
                d = nums[i - 1] - nums[i];
                t = 0;
            }
            ans += t;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24