字節跳動
首先,我們先來看一下字節跳動官網的招聘信息。在招聘首頁上寫著這麼一句話。“和優秀的人,做有挑戰的事”。
其次,我們可以看一下它招聘的研發職位要求,我這邊找了兩個,一個後臺研發,一個廣告算法兩個職位。在職位描述中,可以看到數據結構和數據算法是必備項。
最後,就算不為了進入字節跳動,如果你抽一定的時間來學習算法,也可以加強自己的思維邏輯能力,對自己的技能提升也有非常大的幫助,會一門技術就多一條出路。
字節跳動初面筆試算法題目-字符串反轉
方法一,JAVA語言特性
看到這樣的題目,首先我們應該想到使用最基礎的方法來解決這個問題。利用JAVA語言提供的特性,比如先通過String的split()方法拆分,然後集合工具類Collections.reverse()方法,最後再返回字符串。那如何實現呢?請看代碼;
<code>publicstatic
void main(String
[] args) {String
str
="the sky is blue"
;String
[] strs =str
.split("\\s+"
); List<String
> strLists = Arrays.asList(strs); Collections.reverse(strLists);str
=String
.join(" "
, strLists); System.out.println(str
); }/<code>
如果你沒有過算法學習,那麼你應該想到使用上訴的方法來解決這個問題。上述的代碼很簡單,使用的都是純工具類以及一些特定的API來解決這個。在上述代碼中可能會有一些朋友不清楚String.jion這個方法。因此我在這裡科普一下這個JDK1.8出的特性。
StringJoiner:通過JDK源碼我們可以發現,這個類有兩個構造器。五個公有方法。首先我們來看這兩個構造器,其實構造器一還是通過構造器二來實現的。因此我只以構造器二做講解。
<code>public
StringJoiner(CharSequence delimiter) {this
(delimiter,""
,""
); }public
StringJoiner(CharSequence delimiter, CharSequence prefix, CharSequence suffix) { Objects.requireNonNull(prefix,"The prefix must not be null"
); Objects.requireNonNull(delimiter,"The delimiter must not be null"
); Objects.requireNonNull(suffix,"The suffix must not be null"
);this
.prefix = prefix.toString();this
.delimiter = delimiter.toString();this
.suffix = suffix.toString();this
.emptyValue =this
.prefix +this
.suffix; }/<code>
StringJoiner構造器的三個參數,delimiter表示以什麼樣的方式來連接字符,比如上述代碼中,我使用的是“ ”來連接單詞字符。prefix,和suffix表示拼接後的字符串以什麼方式開始和結束。比如下面的例子,是不是非常簡單。
另外,在這個算法題中,我使用的是String.join()方法,其實join方法的底層實現也是使用的StringJoiner。我這邊貼上源碼,大家可以自己看一下,有興趣的朋友還可以研究一下StringJoiner的其它方法。
<code>public
static
Stringjoin
(CharSequence delimiter, Iterable extends CharSequence> elements
) { Objects.requireNonNull(delimiter); Objects.requireNonNull(elements); StringJoiner joiner =new
StringJoiner(delimiter);for
(CharSequence cs: elements) { joiner.add
(cs); }return
joiner.toString(); }/<code>
方法二,雙指針
雙指針的核心思想就是:一個指針負責循環遍歷,另一個指針負責條件處理
那針對於本題,如何用雙指針解法呢?請看下面源碼。我將原理以及解釋都放在代碼中,方便大家理解。只要大家記住一點,雙指針的特性即可,學會靈活使用雙指針,可以解決很多類似的算法題型。
<code>public
static
void main(String
[] args) {String
str="the sky is blue"
; intright
= str.length() -1
; intleft
=right
;StringBuilder
res = newStringBuilder
();while
(left
>=0
) {while
(left
>=0
&& str.charAt(left
) != ' ')left
--; res.append(str.substring(left
+1
,right
+1
) +" "
);while
(left
>=0
&& str.charAt(left
) == ' ')left
--;right
=left
; }System
.out.println
(res.toString
().trim()); }/<code>
方法三,雙端隊列實現
實現原理:因為雙端隊列可以支持從隊列頭部插入的方法,所以我們可以將字符串中的單詞一個一個進行處理,然後將每一個單詞push到隊列的頭部,再將隊列轉成字符串即可。原理圖如下所示
實現代碼:
<code>public
static
void
main
(String[] args)
{ String str="the sky is blue"
;int
left =0
;int
right = str.length() -1
; Dequedeque
=new
ArrayDeque(); StringBuilder word =new
StringBuilder();while
(left <= right) {char
charStr = str.charAt(left);if
((word.length() !=0
) && (charStr ==' '
)) {deque
.offerFirst(word.toString()); word.setLength(0
); }else
if
(charStr !=' '
) { word.append(charStr); } ++left; }deque
.offerFirst(word.toString()); System.out.println(String.join(" "
,deque
)); }/<code>
其實,只要你明白了雙端隊列的原理以及特性,解決此類問題也非常簡單,當然本題還有很多種其它的解法。留個大家自行探索。
結語
像BAT這種互聯網大廠面試算法的本質就是看你的思路。當你的邏輯思維清楚,寫代碼也不過就幾分鐘的事情。因此,紮實的算法基礎和紮實的語言基礎很重要,因為算法只是解決問題的手段,需要的是從眾多算法中找出最優算法的能力。
關鍵字: delimiter StringJoiner 算法