V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ren2881971
V2EX  ›  算法

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

  •  
  •   ren2881971 · 2016-05-10 08:52:04 +08:00 · 14770 次点击
    这是一个创建于 2964 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    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]; 这行代码。 真心请教怎么入门。。

    第 1 条附言  ·  2016-05-10 10:21:53 +08:00
    修正  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 条回复    2017-03-08 15:04:40 +08:00
    RockShake
        1
    RockShake  
       2016-05-10 09:02:58 +08:00
    从题目来看,如果只是要返回新的数组长度,这行代码有没有都没有关系,只是新拷贝一遍数组而已,你也有新的实现方式
    ren2881971
        2
    ren2881971  
    OP
       2016-05-10 09:06:38 +08:00
    @RockShake 我要是把那行去了 leetcode 就验证不过~
    kevinzhwl
        3
    kevinzhwl  
       2016-05-10 09:11:18 +08:00 via iPhone
    要求的结果是 2 个
    Remove .....and return....
    Ulu
        4
    Ulu  
       2016-05-10 09:13:03 +08:00
    维护两个 index : j 表示新的数组, i 表示旧的数组并用于遍历。在新的数组的位置 j 上只拷贝符合要求的数值并递增 j ,不然什么也不做。
    kindjeff
        5
    kindjeff  
       2016-05-10 09:13:31 +08:00 via iPhone
    因为有两个要求第一个是 value in place
    Marfal
        6
    Marfal  
       2016-05-10 09:13:44 +08:00
    看书先,没有什么比看书更快,密度更高的入门方式了。

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

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

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

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

    #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
        32
    ryd994  
       2016-05-10 10:48:46 +08:00 via Android
    不过论性能的话我觉得这样不好
    既然说了不需要保持顺序
    那直接从后面摘元素过来把不需要的覆盖掉就行
    减少写入次数
    manfay
        33
    manfay  
       2016-05-10 10:51:18 +08:00   ❤️ 1
    @ren2881971 这种题先想想如果可以增加一个数组,能怎么写,然后再想怎么“偷工减料”省掉一个数组,这样思考就比较清晰了。

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

    在数据结构上, array 是固定长度(固定内存大小)的,相对于 list , list 是可变长度的。因此,如果要真的删掉一个元素并且真的改变其长度,就只能创建一个新 array 了。这题不让创建新的,结果就只能假 remove (移个位置)。
    ren2881971
        34
    ren2881971  
    OP
       2016-05-10 10:52:50 +08:00
    @hxtheone 嚯~ js 算法 赞
    hxtheone
        35
    hxtheone  
       2016-05-10 10:56:35 +08:00
    @ren2881971 工作太久都不怎么会 C/C++了 :D
    ren2881971
        36
    ren2881971  
    OP
       2016-05-10 11:13:29 +08:00
    @manfay 懂了。。 假 remove 。 好吧、 了解意图了
    youxiachai
        37
    youxiachai  
       2016-05-10 11:20:47 +08:00
    大家都不知道毛子的老牌 OJ 平台? http://codeforces.com/
    7timesonenight
        38
    7timesonenight  
       2016-05-10 11:58:05 +08:00
    这玩意,其实没有那么玄乎。掌握了基本的几种算法思想后,熟能生巧,多写代码,注意细节处理。
    hitmanx
        39
    hitmanx  
       2016-05-10 12:43:45 +08:00
    @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
        40
    ryd994  
       2016-05-10 13:02:58 +08:00 via Android
    @manfay 不懂你想要怎样才叫 remove
    用新值覆盖掉,旧的自然不存在了
    不是只有删掉格子才叫 remove
    数据不存在
    bravecarrot
        41
    bravecarrot  
       2016-05-10 13:30:05 +08:00 via iPhone   ❤️ 1
    先弄明白基础的各个数据结构的特点与使用场景。
    然后就是看书了,
    算法导论,翻过一点,觉得挺好的,但是有时候是伪代码,可能不利于学习,推荐《程序员代码面试指南》每道题都有完整的代码实现,看题,思考,看答案,书合上,自己写,几个回合下来,自己就能刷题了。
    我做 leetcode 刚开始就是先看题目答案,理解以后,自己写,不会再循环。
    ren2881971
        42
    ren2881971  
    OP
       2016-05-10 13:34:58 +08:00
    @hitmanx It doesn't matter what you leave beyond the new length 这句很重要~
    specita
        43
    specita  
       2016-05-10 14:09:37 +08:00
    慢慢来吧,我也最近在做,我是按照 Acceptance 倒序做的,一开始也怀疑智商,多思考就好了
    zwhu
        44
    zwhu  
       2016-05-10 14:45:16 +08:00
    『算法 第四版』 挺适合入门的,跟着例子和习题做一遍
    loryyang
        45
    loryyang  
       2016-05-10 14:49:30 +08:00
    多练就好了,这种东西也是熟能生巧。记得做题目要踏实,要搞明白里面的每个知识点,每一行代码。
    看不懂的可以上论坛提问题,当然如果能够有几个小伙伴一起做,那是更好的
    Scicomath
        46
    Scicomath  
       2016-05-10 15:49:45 +08:00
    我来说一下我的理解, 题目是想要把等于某个特定值的元素剔除掉, 并且返回新数组的长度.

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

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