字节跳动
首先,我们先来看一下字节跳动官网的招聘信息。在招聘首页上写着这么一句话。“和优秀的人,做有挑战的事”。
其次,我们可以看一下它招聘的研发职位要求,我这边找了两个,一个后台研发,一个广告算法两个职位。在职位描述中,可以看到数据结构和数据算法是必备项。
最后,就算不为了进入字节跳动,如果你抽一定的时间来学习算法,也可以加强自己的思维逻辑能力,对自己的技能提升也有非常大的帮助,会一门技术就多一条出路。
字节跳动初面笔试算法题目-字符串反转
方法一,JAVA语言特性
看到这样的题目,首先我们应该想到使用最基础的方法来解决这个问题。利用JAVA语言提供的特性,比如先通过String的split()方法拆分,然后集合工具类Collections.reverse()方法,最后再返回字符串。那如何实现呢?请看代码;
<code>public static void main(String[] args) { String str="the sky is blue"; //使用\\s+正则来以空格拆分字符串 String[] strs = str.split("\\s+"); //使用工具类Arrays.asList()将其转换为List集合 List strLists = Arrays.asList(strs); //使用Collections.reverse()方法反转内容 Collections.reverse(strLists); //使用StringJoiner来拼接反转后的字符串即可 str = String.join(" ", strLists); //打印str 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"); // make defensive copies of arguments 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对象中 res.append(str.substring(left + 1, right + 1) + " "); //跳动单词之间的空格 while(left >= 0 && str.charAt(left) == ' ') left--; // right 指向下个单词的尾字符,左指针继续前进 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 == ' ')) { // 将单词 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)); }/<code>
其实,只要你明白了双端队列的原理以及特性,解决此类问题也非常简单,当然本题还有很多种其它的解法。留个大家自行探索。
结语
像BAT这种互联网大厂面试算法的本质就是看你的思路。当你的逻辑思维清楚,写代码也不过就几分钟的事情。因此,扎实的算法基础和扎实的语言基础很重要,因为算法只是解决问题的手段,需要的是从众多算法中找出最优算法的能力。
關鍵字: delimiter 面试题 StringJoiner