2020/9/2 15:00 奇安信笔试

第一题：斐波那契数列

这里就不放代码了

第二题：

相邻人口

题目大意：

给定一个拥有n个元素的数组

要求生成一个新数组，具有以下特征

1、新数组每个元素的值至少为1

2、原数组中任何一个元素的值如果大于相邻的元素，新数组中对应的值也应该大

3、原数组中的相同元素在新数组中可以不同。

求新数组所有元素最小的和为多少

例子：

3 2 4

生成

2 1 2

输出：5

3 2 4 3 3 3

生成

2 1 2 1 1 1

输出：8

思路：从小到大遍历原数组的值，然后判断是否大于周围的值：大于就需要更新新数组

因为是从小到大，所以，不会出现错乱的现象

100%代码

class Solution {
public:
    /**
     *
     * @param person int整型一维数组
     * @param personLen int person数组长度
     * @return int整型
     */
    int house(int* person, int personLen) {
        // write code here
        map<int, vector<int>>mp;
        for (int i = 0; i < personLen; i++) {
            mp[person[i]].emplace_back(i);
        }
        vector<int>num(personLen, 1);
        for (auto x : mp) {
            for (auto y : x.second) {
                if (y - 1 >= 0) {
                    if (person[y] > person[y - 1] && num[y] <= num[y - 1])num[y] = num[y - 1] + 1;
                }
                if (y + 1 < personLen) {
                    if (person[y] > person[y + 1] && num[y] <= num[y + 1])num[y] = num[y + 1] + 1;
                }
            }
        }
        long long ans = 0;
        for (auto x : num) {
            ans += x;
        }
        return ans;
    }
};

#笔试题目##奇安信#

全部评论

推荐最新楼层

牛客957013648号

算法工程师

请问这种是什么类型题，leetcode有类似的么？我笔试没有做出来，想练练

点赞回复

发布于 2020-09-02 17:26

拖泥带水

度小满_基础架构研发工程师

提供另一个思路 public int house(int[] person) { int n = person.length; if (n == 0) return 0; if (n == 1) return 1; //记录左侧开始的房子数量 int[] left = new int[n]; //记录右侧开始的房子数量 int[] right = new int[n]; left[0] = person[0] > person[1] ? 2 : 1; for (int i = 1; i < n; i++) { if (person[i] > person[i - 1]) left[i] = left[i - 1] + 1; else left[i] = 1; } right[n - 1] = person[n - 1] > person[n - 2] ? 2 : 1; for (int i = n - 2; i >= 0; i--) { if (person[i] > person[i + 1]) right[i] = right[i + 1] + 1; else right[i] = 1; } int total = 0; //取左侧和右侧的最大值 for(int i = 0; i<n; i++){ total += Math.max(left[i], right[i]); } return total; } }

点赞回复

发布于 2020-09-02 17:28