ren2881971
V2EX  ›  算法

请教算法怎么入门??? 每次鼓起勇气上 leetcode 后,都要怀疑自己的智商。

  •  
  •   ren2881971 · May 10, 2016 · 16594 views
    This topic created in 3829 days ago, the information mentioned may be changed or developed.

    比如 这道题(据说很简单)

    Given an array and a value, remove all instances of that > value in place and return the new length.

    The order of elements can be changed. It doesn't matter what you leave beyond the new length. 以下是答案。

    class Solution {
    public:
        int removeElement(int A[], int n, int elem) {
            int i = 0;
            int j = 0;
            for(i = 0; i < n; i++) {
                if(A[i] == elem) {
                    continue;
                }
    
                A[j] = A[i];
                j++;
            }
    
            return j;
        }
    };
    

    我不明白为什么要加 A[j] = A[i]; 这行代码。 真心请教怎么入门。。

    Supplement 1  ·  May 10, 2016
    修正  Given an array and a value, remove all instances of that value in place and return the new length.

    Do not allocate extra space for another array, you must do this in place with constant memory.

    The order of elements can be changed. It doesn't matter what you leave beyond the new length.
    71 replies  •  2017-03-08 15:04:40 +08:00
    Crixs
    Crixs
    May 10, 2016
    1
    从题目来看,如果只是要返回新的数组长度,这行代码有没有都没有关系,只是新拷贝一遍数组而已,你也有新的实现方式
    ren2881971
    ren2881971
    OP
    May 10, 2016
    2
    @RockShake 我要是把那行去了 leetcode 就验证不过~
    kevinzhwl
    kevinzhwl
    May 10, 2016 via iPhone
    3
    要求的结果是 2 个
    Remove .....and return....
    Ulu
    Ulu
    May 10, 2016
    4
    维护两个 index : j 表示新的数组, i 表示旧的数组并用于遍历。在新的数组的位置 j 上只拷贝符合要求的数值并递增 j ,不然什么也不做。
    kindjeff
    kindjeff
    May 10, 2016 via iPhone
    5
    因为有两个要求第一个是 value in place
    Marfal
    Marfal
    May 10, 2016
    6
    看书先,没有什么比看书更快,密度更高的入门方式了。

    然后就是刷题+总结思考
    ren2881971
    ren2881971
    OP
    May 10, 2016
    7
    @kevinzhwl  好吧。。 不光是返回长度 还要remove。。。。
    songkaiape
    songkaiape
    May 10, 2016
    8
    @ren2881971 remove all instances of that > value in place , leetcode 上他本身有很多个 testcase 来验证你的提交所以这个估计是验证了处理后的字符串吧,之前用 python 做一个题目然后因为 python int 类型无上限然后就报错了,就是得加上整形上限限制才能通过
    lsmgeb89
    lsmgeb89
    May 10, 2016
    9
    这个不能再简单了吧……

    《算法导论》呗……
    Crixs
    Crixs
    May 10, 2016
    10
    @ren2881971 对的,要删除所有的大于数值,这个还是很简单的,多做题目就好了
    srlp
    srlp
    May 10, 2016 via iPhone
    11
    因为需要记录新数组长度,把不符合条件的元素移动到新长度以后的位置里面。
    zhujin
    zhujin
    May 10, 2016
    13
    有个疑问.可能本人英语不好.
    zhujin
    zhujin
    May 10, 2016❤️1
    14
    remove all instances of that > value in place
    这边 不是移除 > value 的值么? 为什么用==
    21grams
    21grams
    May 10, 2016 via Android
    15
    @zhujin 那是个换行符,根本不是大于号
    thinkmore
    thinkmore
    May 10, 2016
    16
    需要返回两个值
    ytmsdy
    ytmsdy
    May 10, 2016
    17
    这题都不涉及到算法好么,只是比较简单的模拟题。
    A[j]=A[i]
    然后 j++
    作者只是少开了一个数组,如果写成
    arraylist b=new arraylist();
    j=0;
    b[j]=a[i];
    j++
    Patiencec
    Patiencec
    May 10, 2016
    18
    这题跟算法没关系。。。算法导论、数据结构撸两遍
    Kv_se7en
    Kv_se7en
    May 10, 2016
    19
    不要怀疑,因为可能确实有问题。
    loading
    loading
    May 10, 2016
    20
    数据库部分如何解决呢?
    很多时候我都是在程序里进行的操作(怪自己 SQlL 渣),题目基本都是一句 SQL 搞定的。。。
    21grams
    21grams
    May 10, 2016❤️1
    21
    写不出来很正常,经验问题,但这种程度的代码都看不懂我觉得你需要思考一下职业规划。
    jasonlz
    jasonlz
    May 10, 2016
    22
    leetcode 上大多数题目都不需要很复杂的算法,基本上数据结构学的可以就可以解决大部分问题了。
    ren2881971
    ren2881971
    OP
    May 10, 2016
    23
    ren2881971
    ren2881971
    OP
    May 10, 2016
    24
    @21grams 职业规划没问题~ 目前尚可温饱。只是以前工作不用到算法而已。
    zhujin
    zhujin
    May 10, 2016
    25
    @21grams Duang...理解了.换行符啊...
    tvallday
    tvallday
    May 10, 2016
    26
    撸两三遍你就知道不是智商问题,而是努力问题。
    ren2881971
    ren2881971
    OP
    May 10, 2016
    27
    @ytmsdy 不明白 加上 A[j] = A[i]; 只能将 j 个过滤后的元素 保存到 A[] 中。 但 A[j,,,,n]中的元素还是保持之前的那样啊~
    ren2881971
    ren2881971
    OP
    May 10, 2016
    28
    @zhujin 我的失误 sorry
    ytmsdy
    ytmsdy
    May 10, 2016
    29
    @ren2881971 那你看他返回的长度,就返回了 j,也就是说到后面数据的解析就就解析到 j 为止。 j 到 n 的数据它才不管呢
    hxtheone
    hxtheone
    May 10, 2016❤️1
    30
    这行代码就是为了题干里的"value in place", 要把满足条件的值都移到数组中前 j 个位置上

    leetcode 上的题目至少 medium/easy 是相当简单的, 数据结构撑死了就链表二叉树, 算法方面更是 DP 默秒全, 把这些学会我觉得搞定 leetcode 上 2/3 的题完全没问题, 我这样的算法渣都已经撸了快一半的题了, 我工作中也不用都是业余自学, 共勉

    顺便求一记 star: https://github.com/MrHuxu/leetcode
    guoliang
    guoliang
    May 10, 2016❤️2
    31
    没关系,慢慢来。我的一点经验:

    #1 , 先理解问题,这道题看起来只要 return 一个 int , 可其实 OJ 会根据这个 int 去检查一开始输入的 array 有没有改变。
    想几个 input out ,最好包括一些 edge case
    #2. 然后再试着画一下数组,不要求写代码的话 你该怎么实现? #如果是面试,这时候就得说出来你的思路来了。
    再用前面的 input 代进来,在脑海里或者白板上跑一遍,确定可以拿到 output.
    #3. 写代码。
    #4. 跑 test case , 想想 time / space complexity ,再比对下别人写的。

    如果一时想不出思路,不要着急,再想想,实在不行再看答案,答案看不懂就把 input 放进去在脑海里/白板上跑,一直跑到自己明白每一行的用意。 再开始 #3.

    希望对你有帮助。

    hackerrank 也不错, test case 更多一些,可以找一些简单练练手感。
    ryd994
    ryd994
    May 10, 2016 via Android
    32
    不过论性能的话我觉得这样不好
    既然说了不需要保持顺序
    那直接从后面摘元素过来把不需要的覆盖掉就行
    减少写入次数
    manfay
    manfay
    May 10, 2016❤️1
    33
    @ren2881971 这种题先想想如果可以增加一个数组,能怎么写,然后再想怎么“偷工减料”省掉一个数组,这样思考就比较清晰了。

    这个题目说要 remove ,但看答案明显没有 remove ,题目表达是有点小问题的,但是算法意图很明显,把想要 remove 的都移到后面去了,真要 remove 也就很简单。

    在数据结构上, array 是固定长度(固定内存大小)的,相对于 list , list 是可变长度的。因此,如果要真的删掉一个元素并且真的改变其长度,就只能创建一个新 array 了。这题不让创建新的,结果就只能假 remove (移个位置)。
    ren2881971
    ren2881971
    OP
    May 10, 2016
    34
    @hxtheone 嚯~ js 算法 赞
    hxtheone
    hxtheone
    May 10, 2016
    35
    @ren2881971 工作太久都不怎么会 C/C++了 :D
    ren2881971
    ren2881971
    OP
    May 10, 2016
    36
    @manfay 懂了。。 假 remove 。 好吧、 了解意图了
    youxiachai
    youxiachai
    May 10, 2016
    37
    大家都不知道毛子的老牌 OJ 平台? http://codeforces.com/
    7timesonenight
    7timesonenight
    May 10, 2016
    38
    这玩意,其实没有那么玄乎。掌握了基本的几种算法思想后,熟能生巧,多写代码,注意细节处理。
    hitmanx
    hitmanx
    May 10, 2016
    39
    @manfay “这个题目说要 remove ,但看答案明显没有 remove ,题目表达是有点小问题的”

    题目写得很清楚了吧,这是更新后的题目。即使是原题,也写得很清楚。

    Given an array and a value, remove all instances of that value *in place* and return the new length.

    *Do not allocate extra space for another array, you must do this in place with constant memory. *

    The order of elements can be changed. It doesn't matter what you *leave beyond the new length.*
    ryd994
    ryd994
    May 10, 2016 via Android
    40
    @manfay 不懂你想要怎样才叫 remove
    用新值覆盖掉,旧的自然不存在了
    不是只有删掉格子才叫 remove
    数据不存在
    bravecarrot
    bravecarrot
    May 10, 2016 via iPhone❤️1
    41
    先弄明白基础的各个数据结构的特点与使用场景。
    然后就是看书了,
    算法导论,翻过一点,觉得挺好的,但是有时候是伪代码,可能不利于学习,推荐《程序员代码面试指南》每道题都有完整的代码实现,看题,思考,看答案,书合上,自己写,几个回合下来,自己就能刷题了。
    我做 leetcode 刚开始就是先看题目答案,理解以后,自己写,不会再循环。
    ren2881971
    ren2881971
    OP
    May 10, 2016
    42
    @hitmanx It doesn't matter what you leave beyond the new length 这句很重要~
    specita
    specita
    May 10, 2016
    43
    慢慢来吧,我也最近在做,我是按照 Acceptance 倒序做的,一开始也怀疑智商,多思考就好了
    zwhu
    zwhu
    May 10, 2016
    44
    『算法 第四版』 挺适合入门的,跟着例子和习题做一遍
    loryyang
    loryyang
    May 10, 2016
    45
    多练就好了,这种东西也是熟能生巧。记得做题目要踏实,要搞明白里面的每个知识点,每一行代码。
    看不懂的可以上论坛提问题,当然如果能够有几个小伙伴一起做,那是更好的
    Scicomath
    Scicomath
    May 10, 2016
    46
    我来说一下我的理解, 题目是想要把等于某个特定值的元素剔除掉, 并且返回新数组的长度.

    打个比方, 现在有十个萝卜, 十个坑, 一个萝卜占一个坑. 你现在想要把坏掉的萝卜剔除掉, 留下好的萝卜, 并且要返回好萝卜的个数. 假设现在有两个萝卜是坏掉的. 那么你最后就要把好萝卜都排到前八个坑里面, 然后返回八.

    那么要怎么做呢? 按照你给出的答案, 它是这么做的. 首先, 令 i=0, j=0,从前往后依次检查( for(i = 0; i < n; i++)), 如果发现第 i 个萝卜是坏的, 不管它继续看下一个. 如果发现第 i 个是好的, 就把它放到第 j(=0)个坑里(注意就算 j 个坑原来有萝卜可以覆盖掉), 然后 j++. 这样循环下去, 你会发现最后好的肯定都会排到前面, 坏的要么留在后面要么被覆盖了.
    Scicomath
    Scicomath
    May 10, 2016
    47
    @Scicomath 其实就是从前往后数, 发现满足条件的就一个一个往前面填.
    其实我觉得还有更好的方法, 就是把要剔除的往数组后面调(其实也不用调, 直接最后面的往前面覆盖就可以了) 因为剔除的一般要少一些, 所以效率应该要高一些
    sensui7
    sensui7
    May 10, 2016
    48
    他不说不许重亲斤笙朙数组吗? 他就用了 2 个指针, 你说的那行代码其实就是在原数组丄覆盖掉
    Lihz
    Lihz
    May 10, 2016
    49
    觉得吃力就一小口慢慢吃,一小口花式吃,多 review ,多思考,真不会再搜索
    matthewz
    matthewz
    May 10, 2016
    50
    推荐先看看算法第四版 看看怎么实现经典算法和数据结构
    这题属于 easy
    e1eph4nt
    e1eph4nt
    May 10, 2016
    51
    @matthewz http://www.v2ex.com/t/276992#reply1 我来卖书了,哈哈哈
    sheldoner
    sheldoner
    May 10, 2016
    52
    @Patiencec 真心请教 什么是算法,什么是数据结构...?还有冒泡排序是属于数据结构还是算法?
    sheldoner
    sheldoner
    May 10, 2016
    53
    @jasonlz 真心请教 什么是算法,什么是数据结构...?还有冒泡排序是属于数据结构还是算法?
    Patiencec
    Patiencec
    May 10, 2016 via iPhone
    54
    @sheldoner 确定不是在黑?都说排序了还问?你这不是编程学得不好而是语文学得不好啊亲。。。排序就是算法啊……数据结构就是字面意思啊,一个结构啊,链表,哈希表,树这些就是结构啊……
    sheldoner
    sheldoner
    May 10, 2016
    55
    @Patiencec 嘿嘿嘿
    sheldoner
    sheldoner
    May 10, 2016
    56
    求一起学 算法低 4 版的小伙伴啊,回复后可详聊....
    jasonlz
    jasonlz
    May 10, 2016
    57
    @sheldoner 如果不想当一辈子的 API 搬运工,好好把计算机基础课程学一遍,把计算机的基本知识体系建立起来,再说去看算法导论,刷 LeetCode 。
    ren2881971
    ren2881971
    OP
    May 10, 2016
    59
    @jasonlz 业务时间 玩下算法而已~ 没必要弄这么大动静吧。
    billion
    billion
    May 10, 2016 via iPad
    60
    这道题如果用 python 做,两行代码就搞定。
    msg7086
    msg7086
    May 10, 2016
    61
    @ren2881971 这些基础知识就是钱啊。
    macha
    macha
    May 10, 2016
    62
    这个题一定要看到数组顺序可以变,这样的话开两个指针一个在最前一个在最后,前面的指针碰到 value 就和后面的指针交换值,同时后面的指针前移一位。这样循环下去直到两个指针碰撞。最后新数组的长度就是前面那个指针跑过的长度。
    楼主可以先刷基础题,基础题刷完了才会有思路。不要怕被打击信心。
    ren2881971
    ren2881971
    OP
    May 10, 2016
    63
    @msg7086 我的意思是 从编码入手开始逐渐展开学习~ 而不是 上来就学些纯理论。。 容易受打击。毕竟不是上学。没那么多时间~
    ren2881971
    ren2881971
    OP
    May 10, 2016
    64
    @billion 发出来 学习下。
    ryerh
    ryerh
    May 10, 2016
    65
    心态捋正,菜鸟就菜鸟,基础不好就补基础,静不下心就不学。
    ren2881971
    ren2881971
    OP
    May 10, 2016
    66
    @ryerh 您说的基础是指 57 楼兄弟说的计算机知识体系?
    creatorYC
    creatorYC
    May 10, 2016
    67
    怀疑智商又有什么关系呢?难道不去刷就能代表这不是事实吗?所以不要怂,就是干
    LonelyWalker
    LonelyWalker
    May 11, 2016 via Android
    68
    数组传递的是引用啊,去掉肯定过不了的,唉。
    sheldoner
    sheldoner
    May 11, 2016 via Android
    69
    @jasonlz 现在不是不想努力,而是不知道怎么努力有什么好的成长路线么,有的话麻烦告知
    dev2dev
    dev2dev
    Mar 5, 2017
    70
    @sheldoner 很多事情要努力了之后才知道结果
    sheldoner
    sheldoner
    Mar 8, 2017
    71
    @dev2dev 赞!!!
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   5108 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 95ms · UTC 07:40 · PVG 15:40 · LAX 23:40 · JFK 02:40
    ♥ Do have faith in what you're doing.