Leetcode 8 移除元素、顏色分類、單詞搜索
移除元素

雙指針問題。可以同時(shí)啟兩個(gè)指針從左向右進(jìn)行遍歷,一個(gè)指針為slow,一個(gè)指針為fast。slow指針和fast指針同時(shí)從下標(biāo)為0的位置開始移動(dòng),如果slow指針指向的值為val,則fast指針向后移動(dòng)找到第一個(gè)不是val的值,賦值給slow指向的元素,隨后slow,fast都自增。不過,這種方法可能存在不必要的復(fù)制操作
為了解決這個(gè)問題,而且返回的數(shù)組沒有強(qiáng)調(diào)需要保持原來的相對順序。所以可以使用一個(gè)在頭的指針left,一個(gè)在尾部的指針right。如果left指向的值為val,將right的值賦值給left指向的元素,right--。假設(shè)right賦值來值還是val,還會進(jìn)行后續(xù)的循環(huán);如果指向的值不是val,left++。具體的代碼如下:

顏色分類

三種顏色的元素(旗子)需要按照顏色排序。開始直接手寫了一個(gè)快速排序,不出意外直接超時(shí)。其中一種爭取的方法是使用將0先移動(dòng)的到開頭的位置,然后將1移動(dòng)到0之后。三種顏色,兩次循環(huán)即可:

單詞搜索
直接dfs+回溯,回溯的時(shí)候記得恢復(fù)已經(jīng)訪問過的元素即可。
標(biāo)簽: