6人伦在线,69精品久久,久草69精品

20 表示數(shù)值的字符串? 馬上解題

題目描述

true："+100"，"5e2"，"-123"，"3.1416"，"-1E-16"

false："12e"，"1a3.14"，"1.2.3"，"+-5"，"12e+4.3"

解題思路

使用正則表達(dá)式進(jìn)行匹配。

[]? ：字符集合

()? ：分組

?? ：重復(fù) 0 ~ 1 次

+? ：重復(fù) 1 ~ n 次

*? ：重復(fù) 0 ~ n 次

.? ：任意字符

\\. ：轉(zhuǎn)義后的 .

\\d ：數(shù)字

21 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面? 馬上解題

題目描述

需要保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。

解題思路

方法一：創(chuàng)建一個(gè)新數(shù)組，時(shí)間復(fù)雜度 O(N)，空間復(fù)雜度 O(N)。

方法二：使用冒泡思想，每次都當(dāng)前偶數(shù)上浮到當(dāng)前最右邊。時(shí)間復(fù)雜度 O(N2)，空間復(fù)雜度 O(1)，時(shí)間換空間。

代碼

方法一：

方法二：

22 鏈表中倒數(shù)第 K 個(gè)結(jié)點(diǎn)? 馬上解題

解題思路

設(shè)鏈表的長(zhǎng)度為 N。設(shè)置兩個(gè)指針 P1 和 P2，先讓 P1 移動(dòng) K 個(gè)節(jié)點(diǎn)，則還有 N - K 個(gè)節(jié)點(diǎn)可以移動(dòng)。此時(shí)讓 P1 和 P2 同時(shí)移動(dòng)，可以知道當(dāng) P1 移動(dòng)到鏈表結(jié)尾時(shí)，P2 移動(dòng)到第 N - K 個(gè)節(jié)點(diǎn)處，該位置就是倒數(shù)第 K 個(gè)節(jié)點(diǎn)。

代碼

23 鏈表中環(huán)的入口結(jié)點(diǎn)? 馬上解題

題目描述

一個(gè)鏈表中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)。要求不能使用額外的空間。

解題思路

使用雙指針，一個(gè)指針 fast 每次移動(dòng)兩個(gè)節(jié)點(diǎn)，一個(gè)指針 slow 每次移動(dòng)一個(gè)節(jié)點(diǎn)。因?yàn)榇嬖诃h(huán)，所以?xún)蓚€(gè)指針必定相遇在環(huán)中的某個(gè)節(jié)點(diǎn)上。假設(shè)相遇點(diǎn)在下圖的 z1 位置，此時(shí) fast 移動(dòng)的節(jié)點(diǎn)數(shù)為 x+2y+z，slow 為 x+y，由于 fast 速度比 slow 快一倍，因此 x+2y+z=2(x+y)，得到 x=z。

在相遇點(diǎn)，slow 要到環(huán)的入口點(diǎn)還需要移動(dòng) z 個(gè)節(jié)點(diǎn)，如果讓 fast 重新從頭開(kāi)始移動(dòng)，并且速度變?yōu)槊看我苿?dòng)一個(gè)節(jié)點(diǎn)，那么它到環(huán)入口點(diǎn)還需要移動(dòng) x 個(gè)節(jié)點(diǎn)。在上面已經(jīng)推導(dǎo)出 x=z，因此 fast 和 slow 將在環(huán)入口點(diǎn)相遇。