字節跳動中級算法機試題，三種JAVA方法中，哪一種算法最優？頭條網

字節跳動中級算法機試題，三種JAVA方法中，哪一種算法最優？

2021-03-28 19:31:35 佚名

字節跳動

首先，我們先來看一下字節跳動官網的招聘信息。在招聘首頁上寫著這麼一句話。“和優秀的人，做有挑戰的事”。

其次，我們可以看一下它招聘的研發職位要求，我這邊找了兩個，一個後臺研發，一個廣告算法兩個職位。在職位描述中，可以看到數據結構和數據算法是必備項。

最後，就算不為了進入字節跳動，如果你抽一定的時間來學習算法，也可以加強自己的思維邏輯能力，對自己的技能提升也有非常大的幫助，會一門技術就多一條出路。

字節跳動初面筆試算法題目-字符串反轉

方法一，JAVA語言特性

看到這樣的題目，首先我們應該想到使用最基礎的方法來解決這個問題。利用JAVA語言提供的特性，比如先通過String的split()方法拆分，然後集合工具類Collections.reverse（）方法，最後再返回字符串。那如何實現呢？請看代碼；

<code>public static
 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
 String join
(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";
         
        int right
 = str.length() - 1;
        int left
 = right;
         
        StringBuilder
 res = new StringBuilder();
        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;
         
        Deque deque
 = 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>