字节跳动笔试算法面试题：JAVA语言的三种实现方式，哪一种最优？，

在招聘首页上写着这么一句话。“和优秀的人，做有挑战的事”。

 

其次，我们可以看一下它招聘的研发职位要求，我这边找了两个，一个后台研发，一个广告算法两个职位。在职位描述中，可以看到数据结构和数据算法是必备项。

 

 

最后，就算不为了进入字节跳动，如果你抽一定的时间来学习算法，也可以加强自己的思维逻辑能力，对自己的技能提升也有非常大的帮助，会一门技术就多一条出路。

字节跳动初面笔试算法题目-字符串反转

 

 

方法一：JAVA语言特性

看到这样的题目，首先我们应该想到使用最基础的方法来解决这个问题。

利用JAVA语言提供的特性，比如先通过String的split()方法拆分，然后集合工具类Collections.reverse（）方法，最后再返回字符串。

那如何实现呢？

请看代码：

public static void main(String[] args) {

String str="the sky is blue";

//使用\\s+正则来以空格拆分字符串

String[] strs = str.split("\\s+");

//使用工具类Arrays.asList()将其转换为List集合

List<String> strLists = Arrays.asList(strs);

//使用Collections.reverse()方法反转内容

Collections.reverse(strLists);

//使用StringJoiner来拼接反转后的字符串即可

str = String.join(" ", strLists);

//打印str

System.out.println(str);

}

如果你没有过算法学习，那么你应该想到使用上诉的方法来解决这个问题。上述的代码很简单，使用的都是纯工具类以及一些特定的API来解决这个。

在上述代码中可能会有一些朋友不清楚String.jion这个方法。因此我在这里科普一下这个JDK1.8出的特性。

 

StringJoiner：通过JDK源码我们可以发现，这个类有两个构造器。五个公有方法。首先我们来看这两个构造器，其实构造器一还是通过构造器二来实现的。因此我只以构造器二做讲解。

//构造器一

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");

// make defensive copies of arguments

this.prefix = prefix.toString();

this.delimiter = delimiter.toString();

this.suffix = suffix.toString();

this.emptyValue = this.prefix + this.suffix;

}

StringJoiner构造器的三个参数，delimiter表示以什么样的方式来连接字符，比如上述代码中，我使用的是“ ”来连接单词字符。prefix，和suffix表示拼接后的字符串以什么方式开始和结束。比如下面的例子，是不是非常简单。

 

另外，在这个算法题中，我使用的是String.join（）方法，其实join方法的底层实现也是使用的StringJoiner。我这边贴上源码，大家可以自己看一下，有兴趣的朋友还可以研究一下StringJoiner的其它方法。

publicstatic 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();

}

方法二：双指针

双指针的核心思想就是：一个指针负责循环遍历，另一个指针负责条件处理

那针对于本题，如何用双指针解法呢？

请看下面源码。我将原理以及解释都放在代码中，方便大家理解。只要大家记住一点，双指针的特性即可，学会灵活使用双指针，可以解决很多类似的算法题型。

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对象中

res.append(str.substring(left + 1, right + 1) + " ");

//跳动单词之间的空格

while(left >= 0 && str.charAt(left) == ' ') left--;

// right 指向下个单词的尾字符，左指针继续前进

right = left;

}

//去掉末尾的空格" "

System.out.println(res.toString().trim());

}

双端队列实现

实现原理：因为双端队列可以支持从队列头部插入的方法，所以我们可以将字符串中的单词一个一个进行处理，然后将每一个单词push到队列的头部，再将队列转成字符串即可。

原理图如下所示

 

实现代码：

publicstaticvoidmain(String[] args) {

String str="the sky is blue";

int left = 0;

int right = str.length() - 1;

//构建双端队列

Deque<String> deque = new ArrayDeque();

StringBuilder word = new StringBuilder();

while (left <= right) {

char charStr = str.charAt(left);

if ((word.length() != 0) && (charStr == ' ')) {

// 将单词 push 到队列的头部

deque.offerFirst(word.toString());

word.setLength(0);

} else if (charStr != ' ') {

word.append(charStr);

}

++left;

}

deque.offerFirst(word.toString());

System.out.println(String.join(" ", deque));

}

其实，只要你明白了双端队列的原理以及特性，解决此类问题也非常简单，当然本题还有很多种其它的解法。留给大家自行探索。

像BAT这种互联网大厂面试算法的本质就是看你的思路。当你的逻辑思维清楚，写代码也不过就几分钟的事情。

因此，扎实的算法基础和扎实的语言基础很重要，因为算法只是解决问题的手段，需要的是从众多算法中找出最优算法的能力。

已在知识星球更新源码解析如下：

 

 

 

领取步骤

1.加微信获取备注：博客园