2018-06-10 00:05:58 yanglr2010 阅读数 219
  • C#急速入门

    Unity开发,C#绝对是基础中的基础,课程针对纯小白而设计,各种语言细节在课程里均有涉猎,从原理到实战,从底层到算法,你想了解的C#,这里应有尽有,除了讲解,还有练习,你说棒不棒,哈哈,当然如果你是有其他语言基础的同学,课程依然会让你收货满满。来吧,我们进入正题。

    16672 人正在学习 去看看 张建飞

版权声明: 本文为博主Bravo Yeung(知乎UserName同名)的原创文章,欲转载请先私信获博主允许,转载时请附上网址
http://blog.csdn.net/lzuacm。

C#版 - Leetcode 215. Kth Largest Element in an Array-题解

在线提交: https://leetcode.com/problems/kth-largest-element-in-an-array/

Description


Find the k th largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

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

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.



思路:
使用List,定义其Sort函数接口,取出第k大的值(List的第k-1个元素)即可。

已AC代码:

public class Solution
{
    public int FindKthLargest(int[] nums, int k)
    {
        int kthMax = 0;
        var list = new List<int>();
        foreach (var num in nums)
            list.Add(num);
        list.Sort((x, y) => -x.CompareTo(y));

        if (list.Count >= k)
            kthMax = list.ElementAtOrDefault(k-1);

        return kthMax;
    }
}

Rank:
You are here!
Your runtime beats 94.55 % of csharp submissions.


dotNET匠人 公众号名片

文末彩蛋

微信后台回复“asp”,给你:一份全网最强的ASP.NET学习路线图。


回复“cs”,给你:一整套 C# 和 WPF 学习资源!


回复“core”,给你:2019年dotConf大会上发布的.NET core 3.0学习视频!

2018-09-06 17:30:14 yanglr2010 阅读数 1295
  • C#急速入门

    Unity开发,C#绝对是基础中的基础,课程针对纯小白而设计,各种语言细节在课程里均有涉猎,从原理到实战,从底层到算法,你想了解的C#,这里应有尽有,除了讲解,还有练习,你说棒不棒,哈哈,当然如果你是有其他语言基础的同学,课程依然会让你收货满满。来吧,我们进入正题。

    16672 人正在学习 去看看 张建飞

C#版 - Leetcode 13. 罗马数字转整数 - 题解

Leetcode 13. Roman to Integer

在线提交:
https://leetcode.com/problems/roman-to-integer/

题目描述

罗马数字包含以下七种字符:IVXLCDM

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: "III"
输出: 3

示例 2:

输入: "IV"
输出: 4

示例 3:

输入: "IX"
输出: 9

示例 4:

输入: "LVIII"
输出: 58
解释: L = 50, V = 5, III = 3.

示例 5:

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

  ●  题目难度: 简单

分析:

只要考虑以下两种情况:

1.如果当前数字是最后一个数字,或者之后的数字比它小的话,则加上当前数字;

2.其他情况则减去这个数字.

已AC的代码:

    public class Solution
    {
        static readonly Dictionary<char, int> dict = new Dictionary<char, int>
        {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000}
        };

        public int RomanToInt(string s)
        {
            int sum = 0;
            for(int i = 0;i < s.Length;i++)
            {
                int currentValue = dict[s[i]];
                if(i == s.Length - 1 || dict[s[i + 1]] <= currentValue)
                    sum += currentValue;
                else
                    sum -= currentValue;
            }
            return sum;
        }
    }

Rank:

You are here! Your runtime beats 89.29% of csharp submissions.


dotNET匠人 公众号名片

文末彩蛋

微信后台回复“asp”,给你:一份全网最强的ASP.NET学习路线图。


回复“cs”,给你:一整套 C# 和 WPF 学习资源!


回复“core”,给你:2019年dotConf大会上发布的.NET core 3.0学习视频!

2018-07-14 07:10:35 yanglr2010 阅读数 1726
  • C#急速入门

    Unity开发,C#绝对是基础中的基础,课程针对纯小白而设计,各种语言细节在课程里均有涉猎,从原理到实战,从底层到算法,你想了解的C#,这里应有尽有,除了讲解,还有练习,你说棒不棒,哈哈,当然如果你是有其他语言基础的同学,课程依然会让你收货满满。来吧,我们进入正题。

    16672 人正在学习 去看看 张建飞

版权声明: 本文为博主Bravo Yeung(知乎UserName同名)的原创文章,欲转载请先私信获博主允许,转载时请附上网址
http://blog.csdn.net/lzuacm。


C#版 - Leetcode 10. 正则表达式匹配 - 题解
LeetCode 10. Regular Expression Matching


###在线提交
https://leetcode.com/problems/regular-expression-matching/

题目描述


给定一个字符串 (s) 和一个字符模式pattern §。实现支持 ‘.’’*’ 的正则表达式匹配。

'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。

匹配应该覆盖整个字符串 (s) ,而不是部分字符串。

说明:

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母,以及字符 ‘.’’*’

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

  ●  题目难度: Hard
- 通过次数:1.9K - 提交次数:10.5K - 贡献者:LeetCode

分析

首先,需要提及一个概念 - 克莱尼星号Kleene Star。

克莱尼星号(算子)

Kleene 星号算子,或称Kleene 闭包,德语称Kleensche Hülle,在数学上是一种适用于字符串或符号及字元的集合的一元运算,通常被称为自由幺半群结构(free monoid construction)。当 Kleene 星号算子被应用在一个集合VV 时,写法是 VV^{*}。它被广泛用于正则表达式,正则表达式由Stephen Kleene引入以描述某些自动机的特征,其中*表示“零或更多”次。

如果VV 是一组字符串,则 VV^{*}被定义为包含空字符串ϵ{\epsilon}VV 的最小超集,并在字符串连接操作下闭合。
如果VV 是一组符号或字符,则 VV^{*}VV 中符号上所有字符串的集合,包括空字符串ϵ{\epsilon}
集合 VV^{*}也可以描述为可以通过连接VV的任意元素生成的有限长度字符串集合,允许多次使用相同的元素。 如果VV 是空集ϕ\phi或单子集ϵ{\epsilon},则V={ϵ}V^{*}=\{\epsilon \}; 如果VV 是任何其他有限集,则 VV^{*}是可数无限集。 该算子用于生成语法或重写规则。

定义及标记法

假定
V0={ϵ}V_{0}=\{\epsilon \}, 其中ϵ{\epsilon}是空字符串。
递归的定义集合
${V_{i+1}={wv:w\in V_{i}\wedge v\in V},} $, 这里的 $ i>0$,

如果VV是一个形式语言,集合VV的第 ii次幂是集合 VV 同自身的 i 次串接的简写。就是说,ViV_{i}可以被理解为是从 VV 中的符号形成的所有长度为 ii 的字符串的集合。

所以在 VV上的 Kleene 星号运算的定义是 V=i=0+Vi={ε}VV2V3{ V^{*}=\bigcup _{i=0}^{+\infty }V_{i}=\left\{\varepsilon \right\}\cup V\cup V^{2}\cup V^{3}\cup \ldots }。就是说,它是从VV中的符号生成的所有可能的有限长度的字符串的搜集。

例子

Kleene 星号算子应用于字符串集合的例子:
{“ab”, “c”}* = {ε, “ab”, “c”, “abab”, “abc”, “cab”, “cc”, “ababab”, “ababc”, “abcab”, “abcc”, “cabab”, “cabc”, “ccab”, “ccc”, …}
Kleene 星号应用于字元集合的例子:
{‘a’, ‘b’, ‘c’}* = {ε, “a”, “b”, “c”, “aa”, “ab”, “ac”, “ba”, “bb”, “bc”, …}

推广

Kleene 星号经常推广到任何幺半群 (M, $ \circ$),也就是,一个集合 M 和在 M 上的二元运算 $ \circ$ 有着:

  • (闭包) a,bM: abM\forall a,b\in M:~a\circ b\in M

  • (结合律) a,b,cM: (ab)c=a(bc)\forall a,b,c\in M:~(a\circ b)\circ c=a\circ (b\circ c)

  • (单位元) ϵM: aM: aϵ=a=ϵa{\displaystyle \exists \epsilon \in M:~\forall a\in M:~a\circ \epsilon =a=\epsilon \circ a}

如果 VM 的子集,则VV被定义为包含ϵ{\epsilon}(空字符串)并闭合于这个运算下的 V 的最小超集。接着VV自身是幺半群,并被称为“VV生成的自由幺半群”。这是上面讨论的 Kleene 星号的推广,因为在某个符号的集合上所有字符串的集合形成了一个幺半群(带有字符串串接作为二元运算)。


方法1:递归

如果没有Kleene星号(正则表达式的 * 通配符),问题会更容易一些 - 我们只需从左到右检查text的每个字符是否与模式pattern匹配。

当存在*时,我们可能需要检查text的许多不同后缀,看它们是否与模式pattern的其余部分匹配。 递归解法是表示这种关系的直接方法。

算法

如果没有Kleene星号,相应的Python代码将如下:

def match(text, pattern):
    if not pattern: return not text
    first_match = bool(text) and pattern[0] in {text[0], '.'}
    return first_match and match(text[1:], pattern[1:])

如pattern中存在*,则它将处于第二位置 pattern[1] 。 然后,我们可以忽略模式pattern的这一部分,或删除text中的匹配字符。 如果在任何这些操作之后我们在剩余的字符串上能匹配上,则初始输入是匹配的。相应的Java代码如下:

class Solution {
    public boolean isMatch(String text, String pattern) {
        if (pattern.isEmpty()) return text.isEmpty();
        boolean first_match = (!text.isEmpty() &&
                               (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

        if (pattern.length() >= 2 && pattern.charAt(1) == '*'){
            return (isMatch(text, pattern.substring(2)) ||
                    (first_match && isMatch(text.substring(1), pattern)));
        } else {
            return first_match && isMatch(text.substring(1), pattern.substring(1));
        }
    }
}

复杂度分析

  • 时间复杂度:将text和模式pattern的长度分别记作 TT, PP。 在最坏的情况下,调用match(text[i:], pattern[2j:])的次数将为 (i+ji)\binom{i+j}{i} ,将产生的字符串的时间复杂度阶数为 O(Ti)O(T - i)O(P2j)O(P - 2\cdot j) 。 因此,时间复杂度可表示为 i=0Tj=0P/2(i+ji)O(T+Pi2j)\sum_{i = 0}^T \sum_{j = 0}^{P/2} \binom{i+j}{i} O(T+P-i-2j)。 通过本文之外的一些努力,可证明这个复杂度可规约为 O((T+P)2T+P2)O\big((T+P)2^{T + \frac{P}{2}}\big)
  • 空间复杂度:对于每次的match调用,我们将创建上述的字符串,可能会创建重复项。 如果没有释放内存,这将总共需要的空间为$ O\big((T+P)2^{T + \frac{P}{2}}\big)$,即使实际上必需的不一样 PPTT的后缀所占空间仅为O(T2+P2)O(T^2 + P^2)

方法2:动态规划

由于该问题具有最优子结构 ,因此缓存中间结果是很自然的。 我们探索如何表示dp(i, j)text[i:]pattern[j:] 能否匹配上? 我们可以使用较短字符串的问题的解来表示当前字符串的解。

算法

我们继续进行与方法1相同的递归,除非因为调用只会用到match(text[i:], pattern[j:]) ,我们才使用dp(i, j) 来处理这些调用,省去了代价很高的字符串构建操作,且允许我们缓存中间结果。用Java实现的代码如下:

自底向上的方式(归纳法):

class Solution {
    public boolean isMatch(String text, String pattern) {
        boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
        dp[text.length()][pattern.length()] = true;

        for (int i = text.length(); i >= 0; i--){
            for (int j = pattern.length() - 1; j >= 0; j--){
                boolean first_match = (i < text.length() &&
                                       (pattern.charAt(j) == text.charAt(i) ||
                                        pattern.charAt(j) == '.'));
                if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                    dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
                } else {
                    dp[i][j] = first_match && dp[i+1][j+1];
                }
            }
        }
        return dp[0][0];
    }
}

自顶向下的方式(演绎法):

enum Result {
    TRUE, FALSE
}

class Solution {
    Result[][] memo;

    public boolean isMatch(String text, String pattern) {
        memo = new Result[text.length() + 1][pattern.length() + 1];
        return dp(0, 0, text, pattern);
    }

    public boolean dp(int i, int j, String text, String pattern) {
        if (memo[i][j] != null) {
            return memo[i][j] == Result.TRUE;
        }
        boolean ans;
        if (j == pattern.length()){
            ans = i == text.length();
        } else{
            boolean first_match = (i < text.length() &&
                                   (pattern.charAt(j) == text.charAt(i) ||
                                    pattern.charAt(j) == '.'));

            if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                ans = (dp(i, j+2, text, pattern) ||
                       first_match && dp(i+1, j, text, pattern));
            } else {
                ans = first_match && dp(i+1, j+1, text, pattern);
            }
        }
        memo[i][j] = ans ? Result.TRUE : Result.FALSE;
        return ans;
    }
}

自底向上的分析,是从具体到抽象,比如 已知数学公式,基于公式来coding,属于演绎法;自顶向下的分析,是从抽象到具体,属于归纳法。

自底向上

自底向上就是已经知道了所有递归边界,把所有可能的状态都算出来。基本步骤是一个拓扑排序的过程,从所有递归边界出发,当一个状态被所有可能的下层状态更新后,就用这个状态去更新后面的状态。直到所求的状态被彻底更新完成为止。

通俗地讲就是:从初始已知的状态出发,向外拓展,最后到达目标状态。

自顶向下:

自顶向下就是不考虑整个树结构,直接从要求的状态开始展开式子,如果式子中的某个状态的值还不清楚,就递归的从这个状态展开。递归结束后式子中的状态都被对应的值替换了,所求状态自然也就清楚了。

通俗地讲就是:从最终状态开始,找到可以到达当前状态的状态,如果该状态还没处理,就先处理该状态。

复杂度分析

  • 时间复杂度:将text和模式pattern的长度分别记作 TT, PP
    每次从 $ i=0, \cdots, T; j=0, … ,P<fontcolor=blue>dp(i,j)</font>范围内<font color=blue>dp(i, j)</font>的调用工作做完一次,所花的时间为O(1)$。因此,时间复杂度是 O(TP)O(T\cdot P)

  • 空间复杂度:该算法中使用的内存空间即为布尔值的缓存,占用的空间大小为O(TP)O(T\cdot P)。 因此,空间复杂度是 O(TP)O(T\cdot P)


    Reference:
    Regular Expression Matching - LeetCode Articles
    Kleene星号


dotNET匠人 公众号名片

文末彩蛋

微信后台回复“asp”,给你:一份全网最强的ASP.NET学习路线图。


回复“cs”,给你:一整套 C# 和 WPF 学习资源!


回复“core”,给你:2019年dotConf大会上发布的.NET core 3.0学习视频!

2018-09-07 10:01:21 yanglr2010 阅读数 1273
  • C#急速入门

    Unity开发,C#绝对是基础中的基础,课程针对纯小白而设计,各种语言细节在课程里均有涉猎,从原理到实战,从底层到算法,你想了解的C#,这里应有尽有,除了讲解,还有练习,你说棒不棒,哈哈,当然如果你是有其他语言基础的同学,课程依然会让你收货满满。来吧,我们进入正题。

    16672 人正在学习 去看看 张建飞

C#版 - Leetcode 12. 整数转罗马数字 - 题解

Leetcode 12. Integer to Roman

在线提交:
https://leetcode.com/problems/integer-to-roman/

题目描述

罗马数字包含以下七种字符: IVXLCDM

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个整数,将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:

输入: 3
输出: "III"

示例 2:

输入: 4
输出: "IV"

示例 3:

输入: 9
输出: "IX"

示例 4:

输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.
  ●  题目难度: 中等

分析:

使用贪心算法的思想,建立一个数表,每次通过查表找出当前的最大数,减去再继续查表。

已AC代码:

public class Solution
{
    public string IntToRoman(int num)
    {
        string res = String.Empty;
        List<int> val = new List<int> { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
        List<string> str = new List<string> { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        for(int i = 0;i < val.Count; ++i)
        {
            while(num >= val[i])
            {
                num -= val[i];
                res += str[i];
            }
        }
        return res;
    }
}

Rank:
You are here!
Your runtime beats 50.41% of csharp submissions.


dotNET匠人 公众号名片

文末彩蛋

微信后台回复“asp”,给你:一份全网最强的ASP.NET学习路线图。


回复“cs”,给你:一整套 C# 和 WPF 学习资源!


回复“core”,给你:2019年dotConf大会上发布的.NET core 3.0学习视频!

2018-06-10 00:37:49 yanglr2010 阅读数 211
  • C#急速入门

    Unity开发,C#绝对是基础中的基础,课程针对纯小白而设计,各种语言细节在课程里均有涉猎,从原理到实战,从底层到算法,你想了解的C#,这里应有尽有,除了讲解,还有练习,你说棒不棒,哈哈,当然如果你是有其他语言基础的同学,课程依然会让你收货满满。来吧,我们进入正题。

    16672 人正在学习 去看看 张建飞

版权声明: 本文为博主Bravo Yeung(知乎UserName同名)的原创文章,欲转载请先私信获博主允许,转载时请附上网址
http://blog.csdn.net/lzuacm。

C#版 - Leetcode 347. Top K Frequent Elements - 题解

在线提交: https://leetcode.com/problems/top-k-frequent-elements/

Description


Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.


思路:
使用字典Dictionary<int, int>存储每个数出现的次数,并对次数进行排序。有两种方法;
1.将Dictionary转为List,实现Sort的CompareTo方法;
2.使用Dictionary的OrderByDescending(f => f.value),并Take(k)。
由于转换为List后进行排序会让程序速度变慢,建议直接用后一种方法。

已AC代码:

public class Solution
{
    public IList<int> TopKFrequent(int[] nums, int k)
    {
        var dict = new Dictionary<int, int>();
        IList<int> result = new List<int>();
        foreach (var num in nums)
        {
            if (!dict.ContainsKey(num))
                dict.Add(num, 1);
            else dict[num]++;
        }
        var list = dict.ToList();
        list.Sort((x, y) => -x.Value.CompareTo(y.Value));

        if (list.Count >= k)
        {
            for (int i = 0; i < k; i++)
            {
                result.Add(list.ElementAtOrDefault(i).Key);
            }
        }           

        return result;
    }
}

改进版:

public class Solution
{
    public IList<int> TopKFrequent(int[] nums, int k)
    {
        var dict = new Dictionary<int, int>();
        IList<int> result = new List<int>();
        foreach (var num in nums)
        {
            if (!dict.ContainsKey(num))
                dict.Add(num, 1);
            else dict[num]++;
        }
        var list = dict.OrderByDescending(f => f.Value).Take(k).ToList();

        for (int i = 0; i < k; i++)
            result.Add(list.ElementAtOrDefault(i).Key);     

        return result;
    }
}

Rank:

You are here!
Your runtime beats 99.28 % of csharp submissions.


dotNET匠人 公众号名片

文末彩蛋

微信后台回复“asp”,给你:一份全网最强的ASP.NET学习路线图。


回复“cs”,给你:一整套 C# 和 WPF 学习资源!


回复“core”,给你:2019年dotConf大会上发布的.NET core 3.0学习视频!

c#学习c#学习c#学习

阅读数 7354

C#LeetCode刷题-队列

阅读数 12089

C#LeetCode刷题-设计

阅读数 12097

没有更多推荐了,返回首页