笔试编程题记录

我好想睡觉啊 / 2023-08-21 / 原文

笔试编程题记录
- 移除元素
- 小球回弹
- 打家劫舍【二】

笔试编程题记录

移除元素

题目：移除数组中指定的元素，只能原地删除，返回移除后数组的长度。

解题思路：快慢指针法，非目标元素就覆盖前一个元素，并返回快指针。

#include<iostream>
#include<vector>
using namespace std;
int removeElment(vector<int>&nums, int val);

int main()
{
    vector<int> nums = {3, 2, 2, 3};
    int target = 3;
    int len = removeElment(nums, target);
    cout << len;
    return 0;
}

int removeElment(vector<int> &nums, int val){
    int n = nums.size();
    int fast = 0;
    for(int slow = 0;slow<n;slow++)
    {
        if(nums[slow] != val){
            nums[fast] = nums[slow];
            fast += 1;
        }
    }
    for(int i = 0;i < fast;i++)
        cout << nums[i];
    cout << endl;
    return fast;
}

小球回弹

一小球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在第n次落下时，共经过多少米？第n次反弹多高？（n<=10）

解题思路：模拟即可，用两个变量记录小球的总路线长度和每次反弹起来的高度

#include<iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int init_n = n;
    if(n > 10){
        cout << "please input smaller n!" << endl;
    }

    double sum = 0, hight = 100;

    while(n){
        sum += hight;
        hight/=2;
        n--;
        if(n){sum+=hight;}
    }
    cout << "共经过" <<sum<<"米，"<<"第"<<init_n<<"次反弹"<<hight<<"米"<<endl;
    return 0;
}

打家劫舍【二】

题目：你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。
给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

解题思路：计算前n-1个最大不相邻数的和与后n-1个最大不相邻数的和，然后再比较取最大。

#include <iostream>
using namespace std;

int main() {
    int n, res = 0;
    cin >> n;
    int arr[n], dp[n];
    for (int i = 0; i < n; ++i) cin >> arr[i];
    // 时间复杂度O(N)，空间复杂度O(N)
    dp[0] = arr[0], dp[1] = max(dp[0], arr[1]);
    for (int i = 2; i < n - 1; ++i) dp[i] = max(dp[i - 2] + arr[i], dp[i - 1]);
    res = dp[n - 2];

    dp[0] = 0, dp[1] = arr[1];
    for (int i = 2; i < n; ++i) dp[i] = max(dp[i - 2] + arr[i], dp[i - 1]);
    res = max(res, dp[n - 1]);
    cout << res;
    return 0;
}