程序员进阶之算法练习(三十四)LeetCode专场

前言

LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 1、2、3题都是Medium的难度,大概是头条的面试题水准; 4、5题是Hard的难度,但是可以用取巧的做法,实现难度降到Medium和Easy的难度;

正文

1、3Sum

题目链接 题目大意:给出一个数组nums,数组包括n个整数(可能有重复); 现在需要从数组中选择三个数a、b、c,使得a+b+c=0; 输出所有可能性的组合;(重复的只输出一次)

Example:
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

题目解析:

题目可以分解为两个子问题: 1、找到整数a、b、c,使得a+b+c=0; 2、重复的a、b、c只输出一次;

子问题1同样可以分解为两个问题:1、找到两个整数a、b,判断c=-a-b的数字是否存在; 那么可以用两个for循环确定a、b,再用一个for循环判断c=-a-b是否存在; 复杂度较高,但是可以解决,考虑子问题2; 子问题2可以通过缓存已经存在的解,每次进行遍历匹配解决; 至此,我们有一个不太优化的解决方案。

优化思路: a、b、c重复因为有a+b+c=0的条件,只要a、b相同,则c必然相同; 那么可以先对数组nums排序,得到有序的数组; 接着对于每个数字nums[i],从[i+1, n]区间选出两个数字x和y(x<y),使得nums[i]+x+y=0;(a=nums[i], b=x, c=y) 可以知道,随着x的增大,y会不断变小;那么从i+1开始向右选择x,从n开始向左选择y,可以在O(N)的复杂度内遍历完所有组合; 当枚举完a=nums[i]的可能后,令a=nums[k],k>i并且nums[k]!=nums[i],这样也可以在O(N)的复杂度内遍历完a的所有可能; 总的时间复杂度是O(N^2);

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>>  ret;
        sort(nums.begin(), nums.end());
        int n = (int)nums.size();
        int i = 0;
        while (i < n) {
            int x = i + 1;
            int y = n - 1;
            while (x < y) {
                int sum = nums[i] + nums[x] + nums[y];
                if (sum == 0) {
                    vector<int> tmp = {nums[i], nums[x], nums[y]};
                    ret.push_back(tmp);
                    while (x < n) {
                        ++x;
                        if (tmp[1] != nums[x]) {
                            break;
                        }
                    }
                }
                else if (sum < 0) {
                    ++x;
                }
                else { // sum > 0
                    --y;
                }
            }
            
            while (i < n) {
                ++i;
                
                if (nums[i] != nums[i - 1]) break;
            }
        }
        
        return ret;
    }
}leetcode;

2、Generate Parentheses

题目链接 题目大意: 给出一个整数n,求n对括号组成的,所有可能的合法字符串;

例如,n=3,则有:

Example:
 [
 "((()))",
 "(()())",
 "(())()",
 "()(())",
 "()()()"
 ]

题目解析:

合法的字符串指的是左右括号数量相同,并且每一个左括号,都能在其右边找到一个右括号; 类似")("这样就是不合法的字符串。 理解定义之后,考虑长度为2*n的字符串中第i个字符应该怎么填: 假设此刻已经具有的左括号有left个,右括号有right个; 如果left>right,比如说"(()",则可以放左括号=>"(()(",也可以放右括号=>"(())" 如果left==right,比如说"(())",那么只能放左括号=>"(())" 如果left<right,此时为不合法序列,我们不应该出现这种情况;

在此过程中,需要注意保证左右括号的数量不要超过n个;

class Solution {
public:
    
    void dfs(vector<string> &ret, string &str, int left, int right) {
        if (left > 0) {
            str.push_back('(');
            dfs(ret, str, left - 1, right);
            str.pop_back();
        }
        
        if (left < right && right > 0) { // 必须保证right > left,这样的字符串才是合法的
            str.push_back(')');
            dfs(ret, str, left, right - 1);
            str.pop_back();
        }
        
        if (left == 0 && right == 0) {
            ret.push_back(str);
        }
        
        
    }
    
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        string tmp;
        dfs(ret, tmp, n, n);
        return ret;
    }
}leetcode;

3、Kth Largest Element in an Array

题目链接 题目大意

一个存放乱序整数的数组,找到数组中第k大的数字;

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

题目解析:

从样例的数据可以看出,第k大就是从小到大排序,第k个的数字; 那么一种简单的办法就是对数组进行排序,然后输出第k个数字;

还有一种做法是建一个大小为k的最大堆,然后遍历数组,把每个数字放进堆中,如果堆大小超过k,则弹出堆顶的数字; 这样一轮过后,就有一个大小为k的最大堆,堆顶就是第k大的数字;

最后是一种理论(平均)最优解法,从数组中取第一个数字x,遍历数组,按照<x和>x分成两组left和right; 如果left==k-1,那么数字x就是第k大数字; 如果left<k-1,那么从right中继续这个筛选过程;(注意right中筛选不是第k个大,要去掉left+1的数量) 如果left>k-1,那么从left中继续这个筛选过程;

这里附上最简单的实现,两行代码;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

4、Number of Digit One

题目链接 题目大意: 给出一个数字n(n<1000),求出在区间[1, n]中所有数字中,1的数量。

Example:
 Given n = 13,
 Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

题目解析:

因为数字n比较小,考虑直接通过数学方式来解决。 例如数字315,可以分割成个十百三个位数上1的数量来分别统计; 个位数:315个1; 十位数:31个10; 百位数:3个100; 每个位数上可能有0、1、大于1的情况,(x+8)/10可以过滤出大于1的情况;

在特别考虑每个位数为1的情况,比如315中的十位数; 上面的统计方式还漏掉了310~315的三种情况,这种情况可以用x%i + 1来过滤出来。

class Solution {
public:
    int countDigitOne(int n) {
        int ret = 0;
        for (long long i = 1; i <= n; i *= 10) {
            ret += (n / i + 8) / 10 * i; // 对应位数上1的数量;
            if (n / i % 10 == 1) {
                ret += n % i + 1;
            }
        }
        return ret;
    }
}leetcode;

其他解法: 题目正解的做法是采用 数位dp的思想。 先预处理出1, 10, 100, 1000 ... 这些数字以下的1的数量; 再从左到右遍历n的字符,求出1的数量。 这才是hard难度的解法,但是学习价值不大。

5、Find Median from Data Stream

题目链接 题目大意: 实现一个数据结构,其中有两个函数: 1、addNum 添加一个数字; 2、findMedian 找到已有数字的中位数;

Example:
 addNum(1)
 addNum(2)
 findMedian() 返回 1.5
 addNum(3)
 findMedian() 返回 2

题目解析:

插入,可以用链表; 找中位数,可以用朴素的遍历; 这样,每次的时间复杂度O(N)。

另外一种简单的实现是:把链表分成两部分,维护一个最大堆,一个最小堆。 这样只要每次看看数字的大小,分别放到左右两个堆就行; 为了方便寻找中位数,要保证最大堆和最小堆的size大小差别不超过1;

每次操作的复杂度都是O(logN);

struct Node {
    int first, second;
    Node(){}
    Node(int f, int s) {
        first = f;
        second = s;
    }
    bool operator < (const Node tmp) const {
        if (first != tmp.first) {
            return first > tmp.first;
        }
        else {
            return second > tmp.second;
        }
    }
};


class MedianFinder {
    
public:
    priority_queue<int> little;
    priority_queue<int, vector<int>, greater<int> > big;
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        little.push(num);
        big.push(little.top());
        little.pop();
        if (little.size() < big.size()) {
            little.push(big.top());
            big.pop();
        }
        cout << findMedian() << endl;
    }
    
    double findMedian() {
        double ret = 0.0;
        if (little.size() == big.size()) {
            ret = (little.top() + big.top()) / 2.0;
        }
        else {
            ret = little.top();
        }
        return ret;
    }
}leetcode;

其他解法: 老老实实用链表+遍历。

总结

做LeetCode的题目有一些数据结构一定要掌握,就是堆! 算法面试题无非就是问思路和实现,堆是一种高效的数据结构,解题的基础数据结构工具之一,同时具备使用非常简单的特点。 熟悉常用数据结构和具体使用场景,比如说题目2用到了栈的思想,题目3是堆的思想,题目5是链表的实现。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能头条

写算法,用 C++ 还是用 Java ,差别大吗?

今天带来的文章,是 GitChat 签约作者王晓华在不断被读者吐槽:“好好一本算法书为什么要用 C++ 来写” 时,万般无奈下憋出来的。

2692
来自专栏CDA数据分析师

Python迭代和迭代器详解

一个对象,物理或者虚拟存储的序列。list,tuple,strins,dicttionary,set以及生成器对象都是可迭代的,整型数是不可迭代的。如果你不确定...

2099
来自专栏机器学习算法与Python学习

动画+原理+代码,解读十大经典排序算法

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

1523
来自专栏工科狗和生物喵

【计算机本科补全计划】《C++ Primer》:数组全解!!

正文之前 其实我的《C++ Primer》 已经看到第五章了,但是因为码字比较费时间,所以暂时没有迅速更新实在是对不住,但是没办法, 总不能一天拿出五六个小时来...

36010
来自专栏Crossin的编程教室

【Python 第72课】map 函数

来看两个问题: 1. 假设有一个数列,如何把其中每一个元素都翻倍? 2. 假设有两个数列,如何求和? 第一个问题,普通程序员大概会这么写: lst_1 = [...

31710
来自专栏python小白到大牛

安利一波Python编程中非常实用的那些黑魔法

编者按:Python是机器学习的主流语言,没有之一。今年5月,它首次在PYPL排行榜上超越JAVA,成为全球第一大编程语言。而一个月后,Stack Overfl...

1312
来自专栏人工智能LeadAI

排序算法对比、总结(Python代码)

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

4058
来自专栏我的技术专栏

图说C++对象模型:对象内存布局详解

3433
来自专栏极客慕白的成长之路

视觉直观感受 7 种常用的排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

834
来自专栏阿凯的Excel

Python读书笔记19(函数与返回值)

为什么计算机与程序可以简化我们的工作量,因为我们只需要了解输入输出即可,不需要关心中间的计算过程。 那我们今天就聊一下如何使用函数输出返回值。 我们设想有一个函...

2966

扫码关注云+社区

领取腾讯云代金券