來自北京大學NOIP金牌選手yxc的常用代碼模板2,Java初級工程師面試題

程序員小秘境 2021-09-18 05:47:21 阅读数:465

北京大 北京 noip 金牌 yxc

if (tt == N) tt = 0;

// 從隊頭彈出一個數

hh ++ ;

if (hh == N) hh = 0;

// 隊頭的值

q[hh];

// 判斷隊列是否為空

if (hh != tt)

{

}


#### [](
)5.單調棧
**常見模型:找出每個數左邊離它最近的比它大/小的數**

  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.

int tt = 0;

for (int i = 1; i <= n; i ++ )

{

while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;

}


#### [](
)6\. 單調隊列
**常見模型:找出滑動窗口中的最大值/最小值**

  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.

int hh = 0, tt = -1;

for (int i = 0; i < n; i ++ )

{

while (hh <= tt && check_out(q[hh])) hh ++ ; // 判斷隊頭是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;

}


#### [](
)7.KMP

  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.

// s[]是長文本,p[]是模式串,n是s的長度,m是p的長度

求模式串的Next數組:

for (int i = 2, j = 0; i <= m; i ++ )

{

while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;

}

// 匹配

for (int i = 1, j = 0; i <= n; i ++ )

{

while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功後的邏輯
}

}


#### [](
)8.Trie樹

  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.

int son[N][26], cnt[N], idx;

// 0號點既是根節點,又是空節點

// son[][]存儲樹中每個節點的子節點

// cnt[]存儲以每個節點結尾的單詞數量

// 插入一個字符串

void insert(char *str)

{

int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;

}

// 查詢字符串出現的次數

int query(char *str)

{

int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];

}


#### [](
)9.並查集
**(1)樸素並查集:**

  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.

int p[N]; //存儲每個點的祖宗節點

// 返回x的祖宗節點
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化,假定節點編號是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合並a和b所在的兩個集合:
p[find(a)] = find(b);

**(2)維護size的並查集:**

  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.

int p[N], size[N];

//p[]存儲每個點的祖宗節點, size[]只有祖宗節點的有意義,錶示祖宗節點所在集合中的點的數量
// 返回x的祖宗節點
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化,假定節點編號是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}
// 合並a和b所在的兩個集合:
size[find(b)] += size[find(a)];
p[find(a)] = find(b);

**(3)維護到祖宗節點距離的並查集:**

  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.

int p[N], d[N];

//p[]存儲每個點的祖宗節點, d[x]存儲x到p[x]的距離
// 返回x的祖宗節點
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化,假定節點編號是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
// 合並a和b所在的兩個集合:
p[find(a)] = find(b);
d[find(a)] = distance; // 根據具體問題,初始化find(a)的偏移量

#### [](
)10.堆

  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.

// h[N]存儲堆中的值, h[1]是堆頂,x的左兒子是2x, 右兒子是2x + 1

// ph[k]存儲第k個插入的點在堆中的比特置

// hp[k]存儲堆中下標是k的點是第幾個插入的

int h[N], ph[N], hp[N], size;

// 交換兩個點,及其映射關系

void heap_swap(int a, int b)

{

swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);

}

void down(int u)

{

int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}

}

void up(int u)

{

while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}

}

// O(n)建堆

for (int i = n / 2; i; i – ) down(i);


#### [](
)11.一般哈希
**(1) 拉鏈法**

  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.

int h[N], e[N], ne[N], idx;

// 向哈希錶中插入一個數
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希錶中查詢某個數是否存在
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;
return false;
}

**(2) 開放尋址法**

  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.

int h[N];

// 如果x在哈希錶中,返回x的下標;如果x不在哈希錶中,返回x應該插入的比特置

最後

按照上面的過程,4個月的時間剛剛好。當然Java的體系是很龐大的,還有很多更高級的技能需要掌握,但不要著急,這些完全可以放到以後工作中邊用別學。

學習編程就是一個由混沌到有序的過程,所以你在學習過程中,如果一時碰到理解不了的知識點,大可不必沮喪,更不要氣餒,這都是正常的不能再正常的事情了,不過是“人同此心,心同此理”的暫時而已。

道路是曲折的,前途是光明的!”

來自北京大學NOIP金牌選手yxc的常用代碼模板2,Java初級工程師面試題_程序員

來自北京大學NOIP金牌選手yxc的常用代碼模板2,Java初級工程師面試題_後端_02

 CodeChina開源項目:【一線大廠Java面試題解析+核心總結學習筆記+最新講解視頻】

版权声明:本文为[程序員小秘境]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210918054720558R.html