1.1.2字符串
28. Implement strStr()
實(shí)現(xiàn)strStr()函數(shù)螟凭，給字符串s1板熊，s2帘饶，返回s2在s1中首次出現(xiàn)的位置下標(biāo)甜无，找不到則返回-1
1. 舉例子-畫圖-解題思路
第一輪對比：
- 從s1中的第一個(gè)元素s1[0]開始與s2中的第一個(gè)元素s2[0]比較：h-l柳譬、e-l喳张、l-l，發(fā)現(xiàn)s1[2]與s2[0]相等
- 從s1[3]開始與s2[1]比較：o-l美澳，發(fā)現(xiàn)不等销部，本輪比較結(jié)束
第二輪對比：
- 繼續(xù)從s1[3]開始與s2[0]比較：o-l、l-l制跟，發(fā)現(xiàn)s1[4]與s2[0]相等
- s1[5]與s2[1]對比：l-l舅桩，兩者相等，且s2到達(dá)末尾
- 返回下標(biāo)4
2. 寫核心邏輯代碼
兩個(gè)字符串間的字符比較問題雨膨，也會用到雙重循環(huán)江咳，只不過表達(dá)方式與數(shù)組的略有不同：
for (int i = 0; i < s1.length(); ++i)
{
for (int j = 0; j < s2.length(); ++j)
{
//判斷邏輯
}
}
基于上面模板，我們寫出題目的核心代碼（haystack是s1哥放，needle是s2）
int hlength = haystack.length(), nlength = needle.length();
//heloll與ll比較時(shí)歼指，沒有必要比較heloll的最后一個(gè)l元素
for (int i = 0; i < hlength - nlength + 1; i++)
{
//要判斷needle是否達(dá)到末尾，所以把j拿到for循環(huán)外面保存
int j = 0;
for (; j < nlength; j++)
{
if (haystack[i + j] != needle[j])
break;
}
if (j == nlength) return i;
}
return -1;
3. 完善邊界條件并提交代碼
class Solution {
public:
int strStr(string haystack, string needle) {
//增加邊界條件
if (needle.empty()) return 0;
if(haystack.empty()) return -1;
int hlength = haystack.length(), nlength = needle.length();
for (int i = 0; i < hlength - nlength + 1; i++) {
int j = 0;
for (; j < nlength; j++)
if (haystack[i + j] != needle[j])
break;
if (j == nlength) return i;
}
return -1;
}
};
4. 更優(yōu)方案
KMP算法是一種更高效的字符串匹配算法甥雕，但其實(shí)現(xiàn)思路略復(fù)雜踩身，我們后面再做介紹
5. 總結(jié)
1.1.3 鏈表
83. Remove Duplicates from Sorted List
給一個(gè)有序鏈表，刪除其中重復(fù)的元素社露，使得每個(gè)元素的值只出現(xiàn)一次挟阻。
1.舉例子-畫圖-解題思路
鏈表已經(jīng)有序，所以只需要比較相鄰兩個(gè)元素值是否相等即可，相等時(shí)執(zhí)行刪除鏈表結(jié)點(diǎn)操作
2.寫核心邏輯代碼
ListNode *start = head;
while(start && start->next)
{
if(start->val == start->next->val)
{
ListNode* tmp = start->next;
start->next = start->next->next;
delete tmp;
}
else
start = start->next;
}
標(biāo)準(zhǔn)的刪除鏈表結(jié)點(diǎn)操作附鸽，請小伙伴們熟記于心
3. 邊界條件
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
//增加head為空或者只有一個(gè)結(jié)點(diǎn)時(shí)候的處理
if(!head || !head->next)
return head;
ListNode *start = head;
while(start && start->next)
{
if(start->val == start->next->val)
{
ListNode* tmp = start->next;
start->next = start->next->next;
delete tmp;
}
else
start = start->next;
}
return head;
}
};
4. 優(yōu)化-無
5. 小結(jié)
怎樣應(yīng)對IT面試與筆試-（一）
怎樣應(yīng)對IT面試與筆試-（二）
怎樣應(yīng)對IT面試與筆試-（三）
怎樣應(yīng)對IT面試與筆試-（四）
怎樣應(yīng)對IT面試與筆試-（五）
怎樣應(yīng)對IT面試與筆試-（五-1）
怎樣應(yīng)對IT面試與筆試-（六）
怎樣應(yīng)對IT面試與筆試-（七）
怎樣應(yīng)對IT面試與筆試-（八）
怎樣應(yīng)對IT面試與筆試-（九）
怎樣應(yīng)對IT面試與筆試-（十）
怎樣應(yīng)對IT面試與筆試-（十一）
怎樣應(yīng)對IT面試與筆試-（十二）
怎樣應(yīng)對IT面試與筆試-（十三）
怎樣應(yīng)對IT面試與筆試-（十四）
怎樣應(yīng)對IT面試與筆試-（十五）
怎樣應(yīng)對IT面試與筆試-（十六）
