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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3104 天前的主题，其中的信息可能已经有所发展或是发生改变。

比如这道题（据说很简单）

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

2016-05-10 09:02:58 +08:00

从题目来看，如果只是要返回新的数组长度，这行代码有没有都没有关系，只是新拷贝一遍数组而已，你也有新的实现方式

ren2881971

2016-05-10 09:06:38 +08:00

@RockShake 我要是把那行去了 leetcode 就验证不过~

kevinzhwl

2016-05-10 09:11:18 +08:00 via iPhone

要求的结果是 2 个
Remove .....and return....

Ulu

2016-05-10 09:13:03 +08:00

维护两个 index ： j 表示新的数组， i 表示旧的数组并用于遍历。在新的数组的位置 j 上只拷贝符合要求的数值并递增 j ，不然什么也不做。

kindjeff

2016-05-10 09:13:31 +08:00 via iPhone

因为有两个要求第一个是 value in place

Marfal

2016-05-10 09:13:44 +08:00

看书先，没有什么比看书更快，密度更高的入门方式了。

然后就是刷题+总结思考

ren2881971

2016-05-10 09:13:56 +08:00

@kevinzhwl 　好吧。。　不光是返回长度　还要ｒｅｍｏｖｅ。。。。

songkaiape

2016-05-10 09:14:00 +08:00

@ren2881971 remove all instances of that > value in place ， leetcode 上他本身有很多个 testcase 来验证你的提交所以这个估计是验证了处理后的字符串吧，之前用 python 做一个题目然后因为 python int 类型无上限然后就报错了，就是得加上整形上限限制才能通过

lsmgeb89

2016-05-10 09:15:16 +08:00

这个不能再简单了吧……

《算法导论》呗……

RockShake

2016-05-10 09:18:50 +08:00

@ren2881971 对的，要删除所有的大于数值，这个还是很简单的，多做题目就好了

srlp

2016-05-10 09:24:06 +08:00 via iPhone

因为需要记录新数组长度，把不符合条件的元素移动到新长度以后的位置里面。

n6DD1A640

2016-05-10 09:26:52 +08:00

https://www.coursera.org/course/algs4partI

硬广

zhujin

2016-05-10 09:36:42 +08:00

有个疑问.可能本人英语不好.

zhujin

2016-05-10 09:37:22 +08:00

remove all instances of that > value in place
这边不是移除 > value 的值么? 为什么用==

21grams

2016-05-10 09:40:40 +08:00 via Android

@zhujin 那是个换行符，根本不是大于号

thinkmore

2016-05-10 09:42:59 +08:00

需要返回两个值

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

2016-05-10 09:49:57 +08:00

这题跟算法没关系。。。算法导论、数据结构撸两遍

Kv_se7en

2016-05-10 09:54:36 +08:00

不要怀疑，因为可能确实有问题。

loading

2016-05-10 10:06:46 +08:00

数据库部分如何解决呢？
很多时候我都是在程序里进行的操作（怪自己 SQlL 渣），题目基本都是一句 SQL 搞定的。。。

21grams

2016-05-10 10:07:21 +08:00

写不出来很正常，经验问题，但这种程度的代码都看不懂我觉得你需要思考一下职业规划。

jasonlz

2016-05-10 10:16:09 +08:00

leetcode 上大多数题目都不需要很复杂的算法，基本上数据结构学的可以就可以解决大部分问题了。

ren2881971

2016-05-10 10:22:31 +08:00

@Kv_se7en 哭

ren2881971

2016-05-10 10:23:52 +08:00

@21grams 职业规划没问题～目前尚可温饱。只是以前工作不用到算法而已。

zhujin

2016-05-10 10:28:35 +08:00

@21grams Duang...理解了.换行符啊...

tvallday

2016-05-10 10:29:40 +08:00

撸两三遍你就知道不是智商问题，而是努力问题。

ren2881971

2016-05-10 10:30:33 +08:00

@ytmsdy 不明白加上 A[j] = A[i]; 只能将 j 个过滤后的元素保存到 A[] 中。但 A[j,,,,n]中的元素还是保持之前的那样啊~

ren2881971

2016-05-10 10:31:02 +08:00

@zhujin 我的失误　ｓｏｒｒｙ

ytmsdy

2016-05-10 10:32:45 +08:00

@ren2881971 那你看他返回的长度,就返回了 j,也就是说到后面数据的解析就就解析到 j 为止。 j 到 n 的数据它才不管呢

hxtheone

2016-05-10 10:42:43 +08:00

这行代码就是为了题干里的"value in place", 要把满足条件的值都移到数组中前 j 个位置上

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

顺便求一记 star: https://github.com/MrHuxu/leetcode

guoliang

2016-05-10 10:44:04 +08:00

没关系，慢慢来。我的一点经验：

#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

2016-05-10 10:48:46 +08:00 via Android

不过论性能的话我觉得这样不好
既然说了不需要保持顺序
那直接从后面摘元素过来把不需要的覆盖掉就行
减少写入次数

manfay

2016-05-10 10:51:18 +08:00

@ren2881971 这种题先想想如果可以增加一个数组，能怎么写，然后再想怎么“偷工减料”省掉一个数组，这样思考就比较清晰了。

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

在数据结构上， array 是固定长度（固定内存大小）的，相对于 list ， list 是可变长度的。因此，如果要真的删掉一个元素并且真的改变其长度，就只能创建一个新 array 了。这题不让创建新的，结果就只能假 remove （移个位置）。

ren2881971

2016-05-10 10:52:50 +08:00

@hxtheone 嚯～ js 算法赞

hxtheone

2016-05-10 10:56:35 +08:00

@ren2881971 工作太久都不怎么会 C/C++了 :D

ren2881971

2016-05-10 11:13:29 +08:00

@manfay 懂了。。假 remove 。好吧、了解意图了

youxiachai

2016-05-10 11:20:47 +08:00

大家都不知道毛子的老牌 OJ 平台? http://codeforces.com/

7timesonenight

2016-05-10 11:58:05 +08:00

这玩意，其实没有那么玄乎。掌握了基本的几种算法思想后，熟能生巧，多写代码，注意细节处理。

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

2016-05-10 13:02:58 +08:00 via Android

@manfay 不懂你想要怎样才叫 remove
用新值覆盖掉，旧的自然不存在了
不是只有删掉格子才叫 remove
数据不存在

bravecarrot

2016-05-10 13:30:05 +08:00 via iPhone

先弄明白基础的各个数据结构的特点与使用场景。
然后就是看书了，
算法导论，翻过一点，觉得挺好的，但是有时候是伪代码，可能不利于学习，推荐《程序员代码面试指南》每道题都有完整的代码实现，看题，思考，看答案，书合上，自己写，几个回合下来，自己就能刷题了。
我做 leetcode 刚开始就是先看题目答案，理解以后，自己写，不会再循环。

ren2881971

2016-05-10 13:34:58 +08:00

@hitmanx It doesn't matter what you leave beyond the new length 这句很重要~

specita

2016-05-10 14:09:37 +08:00

慢慢来吧，我也最近在做，我是按照 Acceptance 倒序做的，一开始也怀疑智商，多思考就好了

zwhu

2016-05-10 14:45:16 +08:00

『算法第四版』挺适合入门的，跟着例子和习题做一遍

loryyang

2016-05-10 14:49:30 +08:00

多练就好了，这种东西也是熟能生巧。记得做题目要踏实，要搞明白里面的每个知识点，每一行代码。
看不懂的可以上论坛提问题，当然如果能够有几个小伙伴一起做，那是更好的

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

2016-05-10 15:55:07 +08:00

@Scicomath 其实就是从前往后数, 发现满足条件的就一个一个往前面填.
其实我觉得还有更好的方法, 就是把要剔除的往数组后面调(其实也不用调, 直接最后面的往前面覆盖就可以了) 因为剔除的一般要少一些, 所以效率应该要高一些