今天有点小累，来两道easy题打卡吧，明天接着动态规划。

1 题目

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109
• 输入保证数组中一定有一个多数元素。

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

2 代码实现

c++

class Solution {
public:
    int majorityElement(vector<int>& nums) {
       unordered_map <int ,int > numsCount ;
       for (int num: nums){
        numsCount [num] ++ ;
        if (numsCount [num] > nums.size() / 2 ){
            return num ;
        }
    }
    return -1 ;
    }
};

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    const numsCount = new Map() ;
    const half = Math.floor(nums.length / 2 )

    for (const num of nums){
        numsCount.set(num, (numsCount.get(num) || 0) + 1);
        if (numsCount.get(num) > half){
            return num;
        }
    }
    return -1 ;
};

3 题目

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

4 代码实现

c++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int minPrice = INT_MAX ;
        int maxPro = 0 ;
        for (int i = 0 ; i < n ; i++){
            int curPro = prices[i] - minPrice ;
            minPrice = min (minPrice , prices[i]);
            maxPro = max (curPro , maxPro );
        }
        return maxPro ;
    }
};

js

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    const n = prices.length ;
    let minPrice = Number.MAX_SAFE_INTEGER ;
    let maxPro = 0 ;

    for (let i = 0 ; i < n ; i++){
        let curPro = prices[i] - minPrice ;
        minPrice = Math.min (minPrice , prices[i]);
        maxPro = Math.max(curPro , maxPro);
    }
    return maxPro ;
};

5 小结

纯打卡，没有太多内容，需要熟悉js的hash表写法。注意细节，这些题目非常简单。