LeetCode算法之路

自己记录一下吧

https://leetcode.cn/problems/two-sum/
两层for循环暴力搜索会有很多重复操作，如：target = 10, nums = [1,8,3,2]
当 i = 1 时，j会依次搜索8、3、2，然后返回，继续搜索 i = 8 时，j依次搜索3、2。
可以看到，当 i = 1 时，已经搜索到了nums中存在2，而当 i = 8 时，还需要从头搜索nums中是否存在2，因此，可以建立一个unordered_map用来存储之前已经被搜索到的元素，以元素作为key值，元素的下标位置作为value值。
2022年6月17日 14:50

https://leetcode.cn/problems/merge-two-sorted-lists/
Point：
链表数据结构： 当前值：p->val；下一节点：p->next；链表后移：p = p->next
新建链表：ListNode* preHead = new ListNode(-1); preHead表示链表的头，此外还需一个指针ListNode* prev = preHead;用来遍历该链表，否则最后返回结果的时候会丢失头的位置（本质是一个指针）。
迭代解法：
新建一个链表，比较当前p1->val 和 p2->val的大小，不断连接到新链表上
2022年6月17日 15:56

https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/
解法一：双指针迭代
定义两个前后指针，不断的将两指针局部的连接关系反转

ListNode* reverseList(ListNode* head) {
        if(head==nullptr || head->next ==nullptr) return head;
        ListNode* pre = head;
        ListNode* cur = nullptr;
        while(pre!=nullptr)
        {
        	//必须首先将pre->next的位置保存下来，否则当进行局部反转时，pre->next关系会丢失
            ListNode* temp = pre->next; 
            pre->next = cur;//连接关系局部反转
            cur = pre;//双指针后移
            pre = temp;
        }
        return cur;
    }

2022年6月18日 20:38

https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
Point： string的长度是固定的，若想用三个char类型的‘%’，‘2’，‘0’代替‘ ’，需要对string进行扩容

string s1,s2;
s1.size()//获取字符串长度
s1 + s2;//可将两个字符串拼接在一起
s1.resize();
s1[]//可通过下标访问 
s1.substr(int pos = 0,int n ) //返回pos开始的n个字符组成的字符串

2022年6月19日 18:17