最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

百度、阿里、腾讯、京东等面试算法题

XAMPP新闻 admin 634浏览 0评论

今天给大家分享的是字符串相关的算法面试题。现在进大厂,都会有算法面试题,不过因为算法和数据结构是有一定门槛的,所以想迈过这个门槛,慢慢积累然后反复看是一个可行的策略。

这个问题是Leetcode上的第151 道题:翻转字符串里的单词

zzzzzs72

这道题目的解题思路:

  • 清除字符串中无用的空格, 【将 ”  are you ok  ” 整理成 “are you ok”
  • 然后将处理好的字符串进行翻转,【将 ” are you ok ” 整理成 “ko uoy era”】
  • 分别将每个单词进行翻转,【将ko变成ok , uoy变成you, 将 era变成are】
  • 最后结果就是 “ ok you are” 整理:

1. 清除空格

2. 整个字符串翻转

3. 然后每个单词进行翻转

 

目标1. 清除字符串中无用的空格 swift 输入:s = " are you ok "

 输出:"are you ok" 要求:这里面无用的空格包括最前面、中间以及最后位置上的空格图片    

思路:

1.遍历字符串数组,如果不是" ",就加入到数组中
2.如果是" ",要判断之前是否也为空,如果是的就跳过,如果不是就将" "加入到数组中。【 因为两个单词之间可能会存在多个空格,但是处理完之后,只能出现一个空格,因此需要判断之前是否也为空 】

 func clearSpace(str: String) -> [Character] {
        var chars = [Character]()
        var space = true
        for c in str {
            if c != " " {
                chars += "\(c)"
                space = false
            } else if space == false {
                chars += " "
                space = true
            }
        }
        return chars
    }

代码里面的space 的作用就是为了实现【思路2】的判断逻辑。我们就用

s = "  are   you ok "

为例过一遍代码。

  • 开始为 " ",所以什么都不做,继续执行直到遍历到’a’
  • c = a,所以加入到chars数组,并且space标记为false,(这样标记的意义是:当遍历到r的时候,我们根据space = false的值就知道上一个结束的时候不是空格)。继续执行直到遍历到’e’
  • 接下来c = " ",但是space = false,所以chars += " ",然后space标记为true;继续执行,此时c = " ",根据代码,是不执行任何操作。继续执行直到c = y,回到第一步。

 

这里比较重要的一点是 space 初时值为 true。

下面是java的实现代码:

public String clearSpace(String s) {
      if (s == null) return "";
        char[] chars = s.toCharArray();
    boolean space = true;
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] != ' ') { // chars[i]是非空格字符
            chars[cur++] = chars[i];
            space = false;
        } else if (space == false) { // chars[i]是空格字符,chars[i - 1]是非空格字符
            chars[cur++] = ' ';
            space = true;
        }
    }
}

目标2. 翻转

这个很简单,代码如下:

func reverseString(_ chars: inout [Character], _ l: inout Int, _ r: inout Int) {
        r -= 1
        while l < r {
            let c = chars[l]
            chars[l] = chars[r]
            chars[r] = c
            l += 1
        }
    }

这段代码的意思就是将【 ” are you ok ” 整理成 “ko uoy era”】

整体实现:

class Solution {
    func reverseWords(_ s: String) -> String {
        var chars = [Character]()
        var space = true 
        for c in s {
            if c != " " {
                chars += "\(c)"
                space = false 
            } else if space == false {
                chars += " " 
                space = true 
            }
        }
        if space == true {
            chars.removeLast()
        }
        let count = chars.count
        reverseString(&chars, 0, count)
        var preIdx = -1
        for i in 0..<count {
            if chars[i] == " " {
                reverseString(&chars, preIdx+1, i)
                preIdx = i 
            }
        }
        reverseString(&chars, preIdx+1, count)
        var str = ""
        for c in chars {
            str += "\(c)"
        }
        return str
    }

    func reverseString(_ chars: inout [Character], _ l: Int, _ r: Int) {
        var b = l 
        var e = r - 1
        while b < e {
            let c = chars[b]
            chars[b] = chars[e]
            chars[e] = c
            b += 1
            e -= 1
        }
    }
}

总结:

今天我学到的解题思路就是一道算法题可以分解成子问题,然后处理完子问题后再组装一下,就能解出这道题。如果想通过面试,还是得靠做题,然后积累一些问题的解法。好了,今天就给大家分享这么多,希望能帮助到大家。

转载请注明:XAMPP中文组官网 » 百度、阿里、腾讯、京东等面试算法题

您必须 登录 才能发表评论!