Leetcode 169：求众数

代码实现1

int partition(vector<int>& nums, int left, int right){ int start = left, end = right; int povit = nums[start]; while (start < end) { while ((start < end) && (nums[end] >= povit)) --end; nums[start] = nums[end]; while ((start < end) && (nums[start] < povit)) ++start; nums[end] = nums[start]; nums[start] = povit; } return start;}int majorityElement(vector<int>& nums) { int nlen = nums.size(); int k = nlen / 2; int start = 0, end = nlen - 1; int target = 0; while (start <= end) { int mid = partition(nums, start, end); if (mid == k ) { target = nums[mid]; break; } else if (mid > k ) end = mid; else start = mid + 1; } return target;}

代码实现2

int majorityElement(vector<int>& nums) {    int can = nums[0], count = 1;    for (int i = 1; i < nums.size(); i++)    {        if (count == 0)        {            can = nums[i];            count = 1;        }        else if (nums[i] == can) {            ++count;        }        else { --count; }                }    return can;}

Leetcode 198：打家劫舍

解题思路

dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])

代码实现

int rob(vector<int>& nums) {    vector<int>dp(nums.size() + 1, 0);    for (int i = 1; i <= nums.size(); i++)    {        if (i == 1) {            dp[i] = nums[i-1];        }else            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);    }    return dp[nums.size()];}