LeetCode水题 - No.214,225,226,227,229,236,240,241

No.229

/* * @lc app=leetcode id=122 lang=cpp * * [122] Best Time to Buy and Sell Stock II */ // @lc code=start class Solution { public: // 取每个上坡差就可以了？ int maxProfit(vector<int>& prices) { int N = prices.size(); int ans = 0; for(int i=1;i<N;i++){ ans += max(0,prices[i] - prices[i-1]); } return ans; } }; // @lc code=end

No.227

/* * @lc app=leetcode id=120 lang=cpp * * [120] Triangle */ // @lc code=start class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int N = triangle.size(); if(N==0) return 0; int ans = 0x3fffffff; for(int i=1;i<N;i++){ triangle[i][0] += triangle[i-1][0]; for(int j=1;j<i;j++){ triangle[i][j] += min(triangle[i-1][j-1],triangle[i-1][j]); } triangle[i][i] += triangle[i-1][i-1]; } for(int i=0;i<N;i++){ ans = min(triangle[N-1][i],ans); } return ans; } }; // @lc code=end

No.226

/* * @lc app=leetcode id=119 lang=cpp * * [119] Pascal's Triangle II */ // @lc code=start class Solution { public: vector<int> getRow(int rowIndex) { vector<int> ans(rowIndex+1,0); ans[0] = 1; // 层 for(int i=1;i<=rowIndex;i++){ for(int j=i;j>0;j--){ ans[j] = ans[j] + ans[j-1]; } } return ans; } }; // @lc code=end

No.225

/* * @lc app=leetcode id=118 lang=cpp * * [118] Pascal's Triangle */ // @lc code=start class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> ans; if(numRows == 0) return ans; ans.push_back(vector<int>(1,1)); for(int i=1;i<numRows;i++){ int L = ans.back().size(); vector<int> t(L+1,0); t[0] = t.back() = 1; for(int i=1;i<L;i++){ t[i] = ans.back()[i-1] + ans.back()[i]; } ans.push_back(t); } return ans; } }; // @lc code=end

No.214

/* * @lc app=leetcode id=66 lang=cpp * * [66] Plus One */ // @lc code=start class Solution { public: vector<int> plusOne(vector<int>& digits) { vector<int> ans; int N = digits.size(); int mv = 1; int t; for(int i=N-1;i>=0;i--){ t = digits[i] + mv; if(t > 9){ ans.push_back(t - ); mv = 1; }else{ ans.push_back(t); mv = 0; } } if(mv > 0 ) ans.push_back(mv); return {ans.rbegin(),ans.rend()}; } }; // @lc code=end

No.236

/* * @lc app=leetcode id=169 lang=cpp * * [169] Majority Element */ // @lc code=start class Solution { public: int majorityElement(vector<int>& nums) { unordered_map<int,int> mp; int N = nums.size(); for(int i=0;i<N;i++){ mp[nums[i]] ++; if(mp[nums[i]] > N/2) return nums[i]; } return -1; } }; // @lc code=end

No.240

/* * @lc app=leetcode id=217 lang=cpp * * [217] Contains Duplicate */ // @lc code=start class Solution { public: bool containsDuplicate(vector<int>& nums) { unordered_map<int,bool> mp; int N = nums.size(); for(int i=0;i<N;i++){ if(mp[nums[i]]) return true; mp[nums[i]] = true; } return false; } }; // @lc code=end

No.241

/* * @lc app=leetcode id=219 lang=cpp * * [219] Contains Duplicate II */ // @lc code=start class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_map<int,int> mp; int N = nums.size(); int t; for(int i=0;i<N;i++){ t = mp[nums[i]]; if(t > 0 ){ if(i - t + 1 <= k) return true; } mp[nums[i]] = i+1; } return false; } }; // @lc code=end