字節跳動筆試真題第三彈,2021第一天從算法題開始吧!

2021-01-14 TechFlow

大家好,今天是2021年的第一天,讓我們鼓足幹勁大幹一場。今天我們選擇的依然是字節跳動2019年的筆試題,題目來源於牛客網。

這道題難度同樣不是很大,但是非常考驗基礎,基礎稍稍不夠紮實的同學很有可能寫出了算法,但是依然會陷入各種問題當中無法AC。我個人覺得差不多是LeetCode Medium水平的難度,但是需要大家有點耐心,開動腦筋反覆思考。

題目連結:https://www.nowcoder.com/question/next?pid=16516564&qid=362293&tid=40247384

好了,我們不多說廢話,直接來看題吧。


題意


我叫王大錘,是一名特工。我剛剛接到任務:在字節跳動大街進行埋伏,抓捕恐怖分子孔連順。和我一起行動的還有另外兩名特工,我提議

為了相互照應,我們決定相距最遠的兩名特工間的距離不超過D。

我特喵是個天才! 經過精密的計算,我們從X種可行的埋伏方案中選擇了一種。這個方案萬無一失,顫抖吧,孔連順!

……

萬萬沒想到,計劃還是失敗了,孔連順化妝成小龍女,混在cosplay的隊伍中逃出了字節跳動大街。只怪他的偽裝太成功了,就是楊過本人來了也發現不了的!

請聽題:給定N(可選作為埋伏點的建築物數)、D(相距最遠的兩名特工間的距離的最大值)以及可選建築的坐標,計算在這次行動中,大錘的小隊有多少種埋伏選擇。

注意:

三個特工是等價的:即同樣的位置組合(A, B, C) 只算一種埋伏方法,不能因「特工之間互換位置」而重複使用

輸入描述:
第一行包含空格分隔的兩個數字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)

第二行包含N個建築物的的位置,每個位置用一個整數(取值區間為[0, 1000000])表示,從小到大排列(將字節跳動大街看做一條數軸)

輸出描述:
一個數字,表示不同埋伏方案的數量。結果可能溢出,請對 99997867 取模

輸入例子1:
4 3
1 2 3 4

輸出例子1:
4

例子說明1:
可選方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)

輸入例子2:
5 19
1 10 20 30 50

輸出例子2:
1

例子說明2:
可選方案 (1, 10, 20)

題解


首先我們來理一下題目當中出現的幾個點,我們要算的是特工埋伏的方法數。特工埋伏需要固定3個特工,並且要求特工之間的距離小於D。

題目當中還說特工之間是等價的,如果大家敏感的話,這其實是一道排列組合問題,準確的說是一道組合問題。這和n球裡任意取3個出來有多少種組合本質上是一樣的,如果大家還記得組合公式的話套一下就可以了:

這裡的k固定了是3,我們代入進去可以簡化為:

首先,由於題目當中說的是特工分布在一條大街上,我們可以把大街看成是橫坐標軸,每一個特工就是坐標軸上的一個點。由於題目當中限定了3個特工之間的距離不超過D,其實也就是最左側和最右側的距離小於D。我們可以想像有一個長度為D的線段在這個坐標軸上滑動,窗口內的特工數量就是n。

由於特工的位置是固定的,所以這個n是很好算的。假如我們用一個數組sum來存儲從0開始到當前位置一共包含的特工數,那麼區間[x, x+D]範圍內的特工數量其實就等於sum[x+D]-sum[x]。這裡我們可以通過差分數組來搞定,也可以使用樹狀數組,我這裡用了樹狀數組,其實沒有必要,因為不涉及更新操作。

所以接下來我們要做的就是把這個窗口從最左側往右滑動就可以了,每次窗口內特工變化的時候,我們計算一下構成的組合數累加在一起就可以了。進一步我們可以想到,其實我們只需要關心窗口的左邊緣,我們把窗口的左邊緣和特工重疊,這樣能夠使得窗口內的特工數量儘可能多。

比如[1, 2, 3, 4]這個樣例,顯然當窗口的左邊緣和1重疊的時候,能夠把4也覆蓋了,否則就會遺漏一些情況。很多人想到這裡就去寫代碼了,但是這裡藏了一個trick,當我們的窗口移動的時候,實際上會出現有一些組合重複的情況

比如說窗口長度是4,當前窗口內的特工是[1, 2, 3, 4],其中有一種組合是(2, 3, 4)。當我們窗口左側邊緣移動到2的時候,窗口內的特工是[2, 3, 4, 5],這裡同樣可以構成組合(2, 3, 4),這就構成了重複,我們需要去掉這一種方案。去的方法也很簡單,我們每次移動窗口的時候都記錄下移動之前的窗口右邊緣的位置。當我們移動之後,我們當前左側邊緣和上次右側邊緣中的特工是重複的,我們需要去掉相關情況。

比如說,我們移動之前是[1, 5, 6, 7],移動之後是[5, 6, 7, 8, 10, 12]。當前的左側邊緣是5,上次的右側邊緣是7,[5, 7]這個區間內的組合數就是重複的情況, 我們需要去掉。另外我們還需要注意一下邊界的事情,由於我們計算組合數需要用到三方的計算,而n最大是1e6,三次方之後就是1e18的範圍,顯然使用int是扛不住的,必須要用long long, long long的範圍是2e18,基本上注意這幾點就可以AC了。

最後,我們來看代碼。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include "time.h"
#include <functional>
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>=b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
#define pii pair<int, int>
using namespace std;
const int N=1000050;
const long long Mod=99997867;
int x, y;

int arr[N];

// 樹狀數組
int lowbit(int x) {
    return x & (-x);
}

void update(int x, int y) {
    for (int i = x; i < N; i += lowbit(i)) {
        arr[i] += y;
    }
}

int query(int x) {
    int ret = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        ret += arr[i];
    }
    return ret;
}

long long cal(long long x) {
    return x * (x-1) * (x-2) / (long long) 6;
}

int main() {
    int n, d;
    scanf("%d%d", &n, &d);
    vector<int> positions;
    rep(i, 0, n) {
        int u;
        scanf("%d", &u);
        u += 1;
        positions.push_back(u);
        update(u, 1);
    }
    long long ret = 0;

    int last = 0;
    for (int i = 0; i < positions.size(); i++) {
        int u = positions[i];
        
        long long num = query(u+d) - query(u-1);
        if (num < 3) continue;

        long long cur = cal(num);
        // 去掉重複的可能性
        if (last > u) {
            long long cnum = query(last) - query(u-1);
            cur -= cal(cnum);
        }
        ret = ((ret + cur) % Mod + Mod) % Mod;
        last = u + d;
    }
    printf("%lld\n", ret);
    return 0;
}

代碼裡有一個細節,我們在對最終結果進行取模的時候,不是直接% Mod,而是用了一個比較複雜的方式:ret = ((ret + cur) % Mod + Mod) % Mod;。這是因為我們直接取模在一些情況下可能會得到負數,會影響我們的結果,所以需要通過這種方式來確保得到的結果一定是正數。

今天的文章就到這裡,衷心祝願大家每天都有所收穫。如果還喜歡今天的內容的話,請來一個三連支持吧~(點讚、在看、轉發

相關焦點

  • 五分鐘學編程:怎樣才能學好筆試面試最愛考察的算法
    第二次認識算法,還是在研究生期間找實習工作的時候,面試的時候總有一些關於算法知識的考察,這些算法題比之前自己學數據結構的時候要更難一些,比如要讓你描述一下快排的過程,或者是二分查找的過程,由於是電話面試居多,一般都不會考察太複雜的問題。第三次認識算法,是在面試了頭條這類對算法要求極高的公司之後。
  • 第三屆字節跳動夏令營開啟全球報名 中外頂級科學家親自授課
    第三屆字節跳動夏令營開啟全球報名 中外頂級科學家親自授課四川新聞網  作者:王雷  2020-07-11 提高頂尖高校在校學生在計算機領域的專業度
  • 筆試 | 字節跳動 最優連續子序列
    字節跳動08.09筆試:最優連續子序列給定一個長度為n的整數序列<=10^5)輸出描述樣例輸入樣例輸出樣例輸入樣例輸出分析做這個題之前我們先看看另外一個問題轉到這個題上來,這個要求的是最大交替和。
  • 不要神化字節跳動:字節跳動的新業務發展並不均衡
    今天的網際網路圈,對字節跳動有一種近乎誇張的推崇,似乎這家急速增長公司無所不能、四處出擊、來勢洶洶,儼然一種「地球人都無法阻止字節跳動」擴張的陣勢。各類媒體對字節跳動的速度、算法、打法、布局、戰略也趨近於誇張的過度解讀,於是字節跳動這家公司也有意無意在某種意義上被神化。
  • 當字節跳動跳入教育領域:一場模仿遊戲?
    在走了一系列彎路之後,作為字節跳動的第三條增長曲線,教育業務目前還看不到破局的苗頭。投放慣例被打破,兩倍薪資挖人沒有人懷疑張一鳴做事的決心。伴魚創始人兼CEO、字節跳動產品創始合伙人黃河對AI財經社回憶,字節跳動在2015年前沒有動過做教育的想法。
  • 字節跳動VS騰訊:世紀之戰
    字節跳動運用算法推薦技術,解決的是內容極大豐富和用戶注意力有限的矛盾。2018年,以抖音、快手為代表的短視頻平臺迅速崛起,擠佔了騰訊系的用戶時長大盤。再來看字節跳動。字節跳動在走當年微信相反的路,微信從「關係鏈」做起,先連接人,再將人與內容連接,進而連接一切。而字節跳動則從信息分發開始,先分發信息和內容,再觸達用戶情感,進而再努力連接「人」。
  • 備戰期末|100道高中數學選擇填空真題訓練!7大考點!元旦刷題吧
    今天是2021年元旦的第一天假期,相信很多高中生們在家裡也得到了很好的休息和調整!但是我們可不能就此鬆懈下來,具體高考的時間越來越近了,所以我們要時刻讓自己對題目有著一個「緊張感」,那就要不停的「刷題」,從各種類型的題型中,「查漏補缺」,尋找目前自己的不足之處!
  • ...優先級提至最高、學小米模式,字節跳動能否再次「大力出奇蹟」?
    在負責字節跳動的教育業務之前,陳林曾是今日頭條CEO,並負責社交(飛聊、多閃)、懂車帝、Lark 等創新業務。如今,教育對於他,又是另一個創新而陌生的領域。 字節跳動布局教育行業已經兩年時間,這期間,外界對這家「算法公司」做教育業務的猜忌和懷疑並不少,但除去張一鳴在八周年信中對教育業務的描述,字節官方鮮少向外傳達業務進展,直到這第一場教育品牌發布會。
  • 哪是什麼「字節跳動」 簡直就是「財富跳動」!一則上市傳聞引發A股...
    遺憾的是,字節跳動採用的是AB股權結構,一開始就盯準了海外上市,沒有從國內工商信息資料可以表明張一鳴等股權比例,也無法就此推測出字節跳動團隊將獲得多少身家。但是年輕的字節跳動,則是在所有領域,跟所有對手短兵相接。一開始做內容和騰訊纏鬥時間長,現在要做電商雲業務,和阿里也難免一戰。作為一個佔用時間的公司,字節跳動的傳統優勢是廣告,這很簡單,和百度以及臉書很相似,有流量就有廣告。
  • 2021安徽教師招聘考試筆試如何備考?
    安徽教師考編考試網為您發布2021安徽教師招聘考試筆試如何備考?,同步安徽教師考試網信息:2021教師考編課程。更多關於教師招聘筆試培訓,教師考編筆試培訓,教師考編筆試課程,安徽教師考編課程的信息內容,請關注安徽教師考編考試網以及安徽華圖,值得信賴!2021安徽教師招聘考試筆試如何備考?
  • 2021國網招聘考試筆試來襲,考前做到這三點萬無一失!
    2021國網招聘考試筆試來襲,考前做到這資格審查結束之後就是筆試啦!相信大家準備了這麼久,一定也對筆試充滿期待了吧~今天就來和大家簡單聊一聊關於國網招聘筆試的考前準備。1、保持手感其實考前的看書已經作用不是很大了,臨時抱佛腳反而會增加心態的壓力,建議考前翻一翻自己的錯題本,歸納一下自己的常見錯誤,再做一套真題或模擬題,保持手感即可。2、心態心態的重要性不言而喻。
  • 字節跳動否認進軍社區團購;李國慶談小米高管屌絲論:意思沒錯,要換...
    :「今日買菜」等消息不實近日,有傳聞稱字節跳動成立一級部門,入局社區團購。並稱新事業部可能命名為「今日優選」「今日買菜」或「跳動優選」。字節跳動方面表示,公司沒有進軍社區團購的計劃,也沒有開展「今日買菜」及相關業務的意向。
  • 字節跳動:開源Fedlearner框架,廣告投放增效209%
    前不久,字節跳動聯邦學習技術團隊也開源了自研的聯邦學習平臺 Fedlearner 。據介紹,字節跳動聯邦學習平臺 Fedlearner 已經在電商、金融、教育等行業多個落地場景實際應用。字節跳動聯邦學習技術負責人吳迪在接受 InfoQ 專訪時表示,聯邦學習面臨的困難更多是如何為客戶爭取可感知的最大商業價值,不同行業的夥伴,其產品特點和價值訴求各不相同。
  • 做遊戲,字節跳動是認真的,也是艱難的
    配圖來自Canva近日,字節跳動宣布旗下中重度遊戲平臺「朝夕光年」即將啟用官網,並將啟用全新的「NUVERSE」作為自己的英文品牌。朝夕光年(又名Ohayoo),是字節跳動旗下的休閒遊戲發行平臺,也是字節跳動遊戲布局的頭號戰將。
  • 「海外員工:字節跳動讓世界刷新對中國的認知」
    不久前的年會上,字節跳動創始人張一鳴做了題為「Hello World」的主題演講,表示「全球化」是字節跳動2018年的年度關鍵詞。隨著字節跳動旗下各線產品出海,這家公司國際化崗位的工作機會也隨之劇增,越來越多的外籍員工選擇加入字節跳動這個大家庭。對於他們而言,在字節跳動工作是一種怎樣的體驗?
  • 頭條、抖音後,誰是字節跳動的新引擎?
    僅僅兩個月時間,字節跳動所面對的世界已經換了一副面孔。焦慮、艱難時刻、打壓、求生,媒體開始在報導中給字節跳動貼上這些新的標籤。 面對輿論漩渦,字節跳動雖未做回應,但近期卻動作頻頻。 除了海外「滅火」,字節跳動正在加大加深對國內各業務板塊的挖掘,包括遊戲、教育、電商等。
  • 從30人公司到估值超1000億美元,字節跳動如何成為全球獨角獸?
    字節跳動應用的是人工智慧技術,通過「算法+內容」打造「流量+數據」打造自己的核心競爭力。 雖然字節跳動估值已經超過1000億美元,但是字節跳動一開始也只是個30人的小公司。
  • 西瓜視頻:字節之外,艱難跳動
    靠著字節跳動這兩棵流量大樹,西瓜視頻過去四年走得相對平穩,焦慮是從今年開始的。年初B站破圈,後來知乎視頻、微博視頻、好看視頻也恨不得將知識科普的標籤貼腦門上。西瓜視頻一面買版權,一面UGC(對外稱是PGC),競爭對手早已從B站擴大到了愛優騰。字節最不缺的就是對手,但急於用流量和金錢扶植存量內容,還得慎之又慎。
  • 字節跳動舉辦 AI 實踐訓練營,報名已正式啟動
    事項:開展 AI 夏令營
  • 字節跳動不再沉默:我們被臉書抹黑!
    昨晚,TikTok母公司字節跳動在其官方帳號發布了一則動態,稱被Facebook抹黑。全文如下:字節跳動始終致力於成為一家全球化公司。在這個過程中,我們面臨著各種複雜和難以想像的困難,包括緊張的國際政治環境、不同文化的碰撞與衝突、 競爭對手Facebook的抄襲和抹黑。