怎样应对IT面试与笔试-(二)

怎样应对IT面试与笔试-(二)

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,发现...

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 

基于上面模板,我们写出题目的核心代码(haystack是s1,needle是s2)

int hlength = haystack.length(), nlength = needle.length();
//heloll与ll比较时,没有必要比较heloll的最后一个l元素
for (int i = 0; i 
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 
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面试与笔试-(十六)

文章来源于互联网:怎样应对IT面试与笔试-(二)

0

评论0

鱼翔浅底,鹰击长空,驼走大漠
没有账号? 注册  忘记密码?