2019-11-13 96 views 评论

Leetcode题目解析（191113）：169&198

标签：leetcode

Leetcode 169：求众数

题目描述

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。

示例

示例1：
输入: [3,2,3]
输出: 3

示例2：
输入: [2,2,1,1,1,2,2]
输出: 2

解题思路1

由于众数是出现次数大于n/2的数字，所以第n/2个数字已经是众数。故可以采用快速排序方法。

代码实现1

int partition(vector&lt;int&gt;&amp; nums, int left, int right)
{
    int start = left, end = right;
    int povit = nums[start];
    while (start &lt; end)
    {
        while ((start &lt; end) &amp;&amp; (nums[end] &gt;= povit))
            --end;
        nums[start] = nums[end];
        while ((start &lt; end) &amp;&amp; (nums[start] &lt; povit))
            ++start;
        nums[end] = nums[start];
        nums[start] = povit;
    }
    return start;
}

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

}

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;

}

复杂度1

运行时间

时间复杂度：O(nlogn)。空间复杂度：O(1)。

解题思路2

参见：https://leetcode-cn.com/problems/majority-element/solution/du-le-le-bu-ru-zhong-le-le-ru-he-zhuang-bi-de-qiu-/

代码实现2

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

<br />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;

}

复杂度2

运行时间

时间复杂度：O(n)总共只有一个循环，因此时间复杂度为 O(n)。
空间复杂度：O(1)只需要常数级别的额外空间，因此空间复杂度为 O(1)。

Leetcode 198：打家劫舍

题目描述

是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例

示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解题思路

动态规划，状态转移方程为

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

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

代码实现

<br />int rob(vector&lt;int&gt;&amp; nums) {
    vector&lt;int&gt;dp(nums.size() + 1, 0);
    for (int i = 1; i &lt;= 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()];
}