今日头条-算法岗

昨天去头条面试了，意料之中的挂了23333

没怎么考察算法，就做了个自我介绍，简单介绍了一下项目，问了问ffm的原理，跟fm比起来有哪些优势

紧接着上了两道算法题，两道题都很基础，但自己真心不扎实，难怪人家看不上==

字符串翻转

给一个句子，把句子翻转但单词不翻转

input:"I am a coder"
output:"coder a am I"

对字符串、字符数组这里一直都很懵逼，看到题就知道自己写不出来了，挣扎了一会投降了==
而且我的重点都放在了要怎么读进来啊！不会读进来啊！怎么读啊！要好好看c++了啊喂！

思路

先翻转整个句子，再把每一个单词翻转过来。翻转字符串的时候前后对换，能减少一半的时间复杂度

代码

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
FILE *fin;

//反转字符串
void ReverseString(char *begin, char *end) {
    while (begin < end) {
        char temp = *begin;
        *begin = *end;
        *end = temp;
        begin++;
        end--;
    }
}

//反转句子
char* ReverseSentance(char *ch) {
    char *begin = ch;
    char *end = ch;

    while (*end != '\0')
        end++;
    end--;
    //反转整个句子
    ReverseString(begin, end);

    //逐个反转单词
    begin = ch;
    end = ch;
    while ((*begin != '\0')) {
        while ((*end != ' ') && (*end != '\0')) {
            end++;
        }
        ReverseString(begin, end - 1);
        if (*end != '\0') {
            end++;
        }
        begin = end;
    }
    return ch;
}

int main() {
    /*fin = fopen("test.txt", "r");
    char str[1024];
    int i = 0;
    while ((str[i] = getchar()) != '\n') {
        i++;
    } 
    int length = sizeof(str)/sizeof(str[0]);
    char *array = str;*/
    char a[] = "I am a coder";
    char *array = a;
    int length = sizeof(a) / sizeof(a[0]);
    cout << length;
    array = ReverseSentance(array);
    for (int i = 0; i < length-1; i++)
    {
        cout << *array;
        array++;
    }

    system("pause");
    return 0;
}

二分查找

给定一个有序数组和一个数字，统计该数字在数组中出现的次数

input:3
1 2 3 3 4 5 6
output:2

我想到了用二分查找来解决，然后我竟然找到了这个数字时候左右分别递归再找==

其实找到了之后就向左向右遍历就可以了，因为数组本身已经是有序的了嘛。。。。

关键思路

二分查找该数字是否在数组中出现，如果找到了就分别向左侧和右侧探测连续出现了几次

代码

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
FILE *fin;

//二分查找
int midfind(vector<int> &vec,int head,int tail,int n) {
    if (head > tail)
        return -1;
    else {
        int mid = (head + tail) / 2;
        if (vec[mid] == n)
            return mid;
        else if (vec[mid] < n) {
            return midfind(vec, mid + 1, tail, n);
        }
        else {
            return midfind(vec, head, mid - 1, n);
        }
    }
}

int main() {
    fin = fopen("test.txt", "r");
    int n;
    int temp;
    vector<int> vec;
    fscanf(fin,"%d",&n);
    while (fscanf(fin, "%d",&temp)!=EOF) {
        vec.push_back(temp);
    }
    int len = vec.size();
    int pos = midfind(vec, 0, len - 1, n);
    if (pos == -1)
        cout << "0" << endl;
    else {
        int pos1 = pos - 1;
        int pos2 = pos + 1;
        int sum = 1;
        while ((pos1>=0) && (vec[pos1]==n))
        {
            sum++;
            pos1--;
        }
        while ((pos2<len) && (vec[pos2] == n))
        {
            sum++;
            pos2++;
        }
        cout << sum << endl;
    }
    system("pause");
    return 0;
}

立flag 好好刷算法了要！！！！！基础很重要！