Leetcode 8 移除元素、颜色分类、单词搜索
移除元素

双指针问题。可以同时启两个指针从左向右进行遍历,一个指针为slow,一个指针为fast。slow指针和fast指针同时从下标为0的位置开始移动,如果slow指针指向的值为val,则fast指针向后移动找到第一个不是val的值,赋值给slow指向的元素,随后slow,fast都自增。不过,这种方法可能存在不必要的复制操作
为了解决这个问题,而且返回的数组没有强调需要保持原来的相对顺序。所以可以使用一个在头的指针left,一个在尾部的指针right。如果left指向的值为val,将right的值赋值给left指向的元素,right--。假设right赋值来值还是val,还会进行后续的循环;如果指向的值不是val,left++。具体的代码如下:

颜色分类

三种颜色的元素(旗子)需要按照颜色排序。开始直接手写了一个快速排序,不出意外直接超时。其中一种争取的方法是使用将0先移动的到开头的位置,然后将1移动到0之后。三种颜色,两次循环即可:

单词搜索
直接dfs+回溯,回溯的时候记得恢复已经访问过的元素即可。