1.1.2字符串
28. Implement strStr()
实现strStr()函数，给字符串s1，s2，返回s2在s1中首次出现的位置下标，找不到则返回-1
1. 举例子-画图-解题思路
28 (1).png
第一轮对比：
- 从s1中的第一个元素s1[0]开始与s2中的第一个元素s2[0]比较：h-l、e-l、l-l，发现s1[2]与s2[0]相等
- 从s1[3]开始与s2[1]比较：o-l，发现不等，本轮比较结束
第二轮对比：
- 继续从s1[3]开始与s2[0]比较：o-l、l-l，发现s1[4]与s2[0]相等
- s1[5]与s2[1]对比：l-l，两者相等，且s2到达末尾
- 返回下标4
2. 写核心逻辑代码
两个字符串间的字符比较问题，也会用到双重循环，只不过表达方式与数组的略有不同：
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比较时，没有必要比较heloll的最后一个l元素
for (int i = 0; i < hlength - nlength + 1; i++)
{
//要判断needle是否达到末尾，所以把j拿到for循环外面保存
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. 更优方案
KMP算法是一种更高效的字符串匹配算法，但其实现思路略复杂，我们后面再做介绍
5. 总结
1.1.3 链表
83. Remove Duplicates from Sorted List
给一个有序链表，删除其中重复的元素，使得每个元素的值只出现一次。
1.举例子-画图-解题思路
217-op (1).png
链表已经有序，所以只需要比较相邻两个元素值是否相等即可，相等时执行删除链表结点操作
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;
}
标准的删除链表结点操作，请小伙伴们熟记于心
3. 边界条件
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
//增加head为空或者只有一个结点时候的处理
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. 优化-无
5. 小结
怎样应对IT面试与笔试-（一）
怎样应对IT面试与笔试-（二）
怎样应对IT面试与笔试-（三）
怎样应对IT面试与笔试-（四）
怎样应对IT面试与笔试-（五）
怎样应对IT面试与笔试-（五-1）
怎样应对IT面试与笔试-（六）
怎样应对IT面试与笔试-（七）
怎样应对IT面试与笔试-（八）
怎样应对IT面试与笔试-（九）
怎样应对IT面试与笔试-（十）
怎样应对IT面试与笔试-（十一）
怎样应对IT面试与笔试-（十二）
怎样应对IT面试与笔试-（十三）
怎样应对IT面试与笔试-（十四）
怎样应对IT面试与笔试-（十五）
怎样应对IT面试与笔试-（十六）
