2024秋招算法

21 阅读 0 评论 0 点赞

文章目录

参考资料
一数组
二链表
三哈希表
- 3.1 有效的字母异位词
- 3.2 两个数组的交集

参考资料

代码随想录 https://programmercarl.com/
LeetCode https://leetcode.cn/

一数组

1.1 二分查找

前提
有序数组，元素唯一（有重复元素，使用二分查找法返回的元素下标可能不是唯一）
思想
- 定义 target 是在一个在左闭右闭的区间里，也就是[left, right]
- while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
- if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
- 若要通过二分查找确定插入位置，则最后需判断nums[mid] > target，若是则mid为结果，若不是则mid + 1为结果

代码

// https://leetcode.cn/problems/binary-search/description/
class Solution {
	public:
	    int search(vector<int>& nums, int target) {
	        int left = 0, right = nums.size() - 1;
	        while (left <= right) {
	            int mid = left + (right - left)/2;
	            if (nums[mid] == target) {
	                return mid;
	            } 
	            if (nums[mid] < target) {
	                left = mid + 1;
	            }
	            if (nums[mid] > target) {
	                right = mid - 1;
	            }
	        }
	        return -1;
	    }
};

1.2 移除元素

前提
O(1)空间，不要求保留原顺序
思想
将要删除的元素用数组最后面的元素进行替换

代码

// https://leetcode.cn/problems/remove-element/description/
class Solution {
	public:
	    int removeElement(vector<int>& nums, int val) {
	        int left = 0, right = nums.size() - 1;
	        while (left <= right) {
	            if (nums[left] == val) {
	                nums[left] = nums[right];
	                right --;
	            } else {
	                 left ++;
	            }
	        }
	        // [0, right]为需要保留的元素，长度位right + 1
	        return right + 1;
	    }
};

1.3 长度最小的子数组

前提
O(1)空间，子数组连续
思想
定义区间[left, right)，当区间和sum < target时移动right，相反则记录当前区间长度right - left并移动left，直到right > 数组总长度时结束循环

代码

// https://leetcode.cn/problems/minimum-size-subarray-sum/description/
class Solution {
	public:
	    int minSubArrayLen(int target, vector<int>& nums) {
	        int left = 0, right = 0; // [left, right)
	        int sum = 0, ans = 0;
	        while (right <= nums.size()) {
	            if (sum < target) {
	            	// 此时right指针已达到末尾，且子数组和小于target
	            	// 结束循环
	                if (right ==  nums.size()) {
	                    break;
	                }
	                sum += nums[right];
	                right ++;
	            } else {
	                int len = right - left;
	                if (ans == 0) {
	                    ans = len;
	                } else {
	                    ans = ans > len ? len : ans;
	                }
	                sum -= nums[left];
	                left ++;
	            }
	        }
	        return ans;
	    }
};

1.4 螺旋矩阵

思想
关键在于方向的转换，并且需要记录行和列上还有多少是没有遍历过的，每次方向转换都需要减少一个待遍历的行或列

代码

// https://leetcode.cn/problems/spiral-matrix-ii/description/
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        // direction = 0 => 从左到右，direction = 1 => 从上到下
        // direction = 2 => 从右到左，direction = 3 => 从下到上
        int direction = 0;
        int row_count = n, col_count = n;
        int i_index = 0, j_index = 0; 
        int num = 1;

        // 初始化结果
        vector<vector<int>> res;
        for (int i = 0; i < n; i ++) {
            vector<int> r(n);
            res.push_back(r);
        }

        while (num <= n * n) {
            // printf("direction = %d\n", direction);
            switch(direction) {
                case 0:
                    // printf("case0, i = %d, j = %d\n", i_index, j_index);
                    for (int i = 0; i < col_count; i ++) {
                        res[i_index][j_index] = num;
                        j_index ++;
                        num ++;
                    }
                    i_index ++;
                    j_index --;
                    row_count --;
                    break;
                case 1:
                    // printf("case1, i = %d, j = %d\n", i_index, j_index);
                    for (int i = 0; i < row_count; i ++) {
                        res[i_index][j_index] = num;
                        i_index ++;
                        num ++;
                    }
                    i_index --;
                    j_index --;
                    col_count --;
                    break;
                case 2:
                    // printf("case2, i = %d, j = %d\n", i_index, j_index);
                    for (int i = 0; i < col_count; i ++) {
                        res[i_index][j_index] = num;
                        j_index --;
                        num ++;
                    }
                    j_index ++;
                    i_index --;
                    row_count --;
                    break;
                case 3:
                    // printf("case3, i = %d, j = %d\n", i_index, j_index);
                    for (int i = 0; i < row_count; i ++) {
                        res[i_index][j_index] = num;
                        i_index --;
                        num ++;
                    }
                    i_index ++;
                    j_index ++;
                    col_count --;
                    break;
            }
            direction ++;
            direction = direction % 4;
            // for (int i = 0; i < n; i ++) {
            //     for (int j = 0; j < n; j ++) {
            //         cout << res[i][j];
            //     }
            //     cout << endl;
            // }
        }
        return res;
    }
};

1.5 在排序数组中查找元素的第一个和最后一个位置

代码

// https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ret(2, -1);
        // 有效区间[left, right]
        int left = 0, right = nums.size() - 1, mid;
        bool tag = false;
        while (left <= right) {
            mid = left + (right - left)/2;
            if (nums[mid] == target) {
                tag = true;
                break;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (!tag) return ret;
        // cout << left << " " <<  mid << " " << right  << endl;

        // [left, mid - 1] 中寻找小于target的元素
        int l = left, r = mid - 1, from = left;
        while (l <= r) {
            int m = l + (r - l)/2;
            if (nums[m] < target) {
                from = m;
                break;
            } else {
                r = m - 1;
            }
        }
        // 向右找到第一个等于target的元素
        while (nums[from] != target) from ++;

         // [mid + 1, right] 中寻找大于target的元素
        l = mid + 1;
        r = right;
        int to = right;
        while (l <= r) {
            int m = l + (r - l)/2;
            if (nums[m] > target) {
                to = m;
                break;
            } else {
                l = m + 1;
            }
        }
        // 向左找到第一个等于target的元素
        while (nums[to] != target) to --;
        ret[0] = from;
        ret[1] = to;
        return ret;
    }
};

二链表

2.1 移除链表元素

思想
移除链表中指定元素的关键在于找到被移除元素的上一个节点

代码

// https://leetcode.cn/problems/remove-element/description/
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
    	// 定义虚拟头节点，不需要对第一个节点进行特殊判断
        ListNode *dummy_head = new ListNode(-1, head);
        // 定义pre和cur，方便删除元素
        ListNode *pre = dummy_head;
        ListNode *cur = dummy_head->next;
        while (cur != NULL) {
            if (cur->val == val) {
                pre->next = cur->next;
                cur = pre->next;
            } else {
                pre = pre->next;
                cur = cur->next;
            }
        }
        return dummy_head->next;
    }
};

2.2 设计链表

思想
- 设计虚拟头节点可以简化对于第一个节点的操作
- 由题可知，大部分操作都需要找到下标的为index的节点的上一个节点，因此设计了getPre(int index)函数
- 设计尾节点可以降低addAtTail的时间复杂度，但是在链表变化时需要对其进行维护

代码

// https://leetcode.cn/problems/design-linked-list/
class MyListNode {    
public:
    int val;
    MyListNode *next;
    MyListNode(int val, MyListNode *next) {
        this->val = val;
        this->next = next;
    }
};

class MyLinkedList {
private:
    MyListNode *dummy_head;
    MyListNode *tail;
    int size;

    // 找到下标为index的上一个节点
    MyListNode *getPre(int index) {
        MyListNode *node = dummy_head;
        while (index > 0) {
            node = node->next;
            index --;
        }
        return node;
    }
public:
    MyLinkedList() {
        dummy_head = new MyListNode(-1, NULL);
        tail = NULL;
        size = 0;
    }
    
    int get(int index) {
        if (index >= size) {
            return -1;
        }
        MyListNode *node = getPre(index);
        return node->next->val;
    }
    
    void addAtHead(int val) {
        MyListNode *node = new MyListNode(val, NULL);
        node->next = dummy_head->next;
        dummy_head->next = node;
        if (tail == NULL) {
            tail = node;
        }
        size ++;
    }
    
    void addAtTail(int val) {
        if (tail == NULL) {
            addAtHead(val);   
        } else {
            tail->next = new MyListNode(val, NULL);
            tail = tail->next;
            size ++;
        }
    }
    
    void addAtIndex(int index, int val) {
        // 如果 index 比长度更大，该节点将 不会插入 到链表中
        if (index > size) {
            return ;
        }
        // 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾
        if (index == size) {
            addAtTail(val);
        } else {
            MyListNode *node = new MyListNode(val, NULL);
            MyListNode *p = getPre(index);
            node->next = p->next;
            p->next = node;
            size ++;
        }
    }
    
    void deleteAtIndex(int index) {
        if (index >= size) {
            return ;
        }
        MyListNode *p = getPre(index);
        // 要删除的节点为尾节点，需要修改tail
        if (p->next == tail) {
            p->next = NULL;
            tail = p;
        } else {
            p->next = p->next->next;                
        }
        size --;
    }
};

2.3 反转链表

思想
- 为原链表添加虚拟头节点，删除节点时不需要维护头节点，简化操作（新链表的虚拟头节点同理）
- 反转链表主要分为节点断开和节点接入，分为两部分实现，可避免思路不清晰，导致链表成环（q->next = NULL可删除）

代码

// https://leetcode.cn/problems/reverse-linked-list/
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
    	// 为原链表添加虚拟头节点，方便节点的删除
        ListNode *dummy_head = new ListNode(-1, head);
        ListNode *p = dummy_head;
        // 为新链表添加虚拟头节点
        ListNode *new_head = new ListNode(-1);
        while (p->next != NULL) {
        	// 把节点从原链表断开
            ListNode *q = p->next;
            p->next = q->next;
            q->next = NULL;

			// 把节点接入到新链表的头部
            q->next = new_head->next;
            new_head->next = q;
        }
        return new_head->next;
    }
};

2.4 两两交换链表中的节点

思想
- 多定义变量可一定程度上简化操作（变量不用?）

代码

// https://leetcode.cn/problems/swap-nodes-in-pairs/description/
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummy_head = new ListNode(-1, head);
        ListNode *p = dummy_head;
        while (p->next != NULL && p->next->next != NULL) {
            // a和b为要进行交换的节点，c为后面的节点
            ListNode *a = p->next;
            ListNode *b = a->next;
            ListNode *c = b->next;

            // 将a和b从原链表中断开（为了方便理解，可省略）
            p->next = NULL;
            a->next = NULL;
            b->next = NULL;

            // 重新拼接
            p->next = b;
            b->next = a;
            a->next = c;

            p = a;
        }   
        return dummy_head->next;
    }
};

2.5 删除链表的倒数第N个节点

思想
先让fast跑n步，然后slow和fast再一起跑，fast到达末尾时，slow刚好为倒数第n+1个节点

代码

// https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy_head = new ListNode(-1, head);
        ListNode *fast = dummy_head;
        ListNode *slow = dummy_head;
        while (n > 0) {
            fast = fast->next;
            n --;
        }

        while (fast->next != NULL) {
            fast = fast->next;
            slow = slow->next;
        }

        slow->next = slow->next->next;

        return dummy_head->next;   
    }
};

2.6 链表相交

代码

// https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 计算链表A和B的节点数
        int a_count = 0;
        int b_count = 0;
        ListNode *p = headA;
        while (p != NULL) {
            a_count ++;
            p = p->next;
        }

        p = headB;
        while (p != NULL) {
            b_count ++;
            p = p->next;
        }
		
		// 若两个链表相差sub个节点，则让长的链表先跑sub步
        while (a_count > b_count) {
            headA  = headA->next;
            a_count --;
        }
        while (b_count > a_count) {
            headB = headB->next;
            b_count --;
        }
        // 两个链表同时往前，此时遇到的第一个相同节点即为结果
        while (headA != headB) {
            headA = headA->next;
            headB = headB->next;
        }
        return headA;
    }
};

2.7 环形链表II

思想
- 通过快慢指针法确定链表是否存在环，并找到环中的任意一个节点
- 遍历环，直至将环中的所有节点添加到set集合中
- 从head开始遍历，当节点存在与set集合中时，即为环的入口节点

代码

// https://leetcode.cn/problems/linked-list-cycle-ii/
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 通过快慢指针法确定链表是否存在环，并找到环中的任意一个节点
        ListNode *fast = head;
        ListNode *slow = head;
        bool tag = false;
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                tag = true;
                break;
            }
        }
		
        if (tag) {
        	// 此时fast和slow都是环中的节点，遍历环，直至将环中的所有节点添加到`set`集合中
            set<ListNode*> st;
            while (st.find(fast) == st.end()) {
                st.insert(fast);
                fast = fast->next;
            }
            
            // 从`head`开始遍历，当节点存在与`set`集合中时，即为环的入口节点
            while (st.find(head) == st.end()) {
                head = head->next;
            }
            return head;
        } else {
            return NULL;
        }
    }
};

最优解法

// https://leetcode.cn/problems/linked-list-cycle-ii/solutions/12616/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        bool tag = false;
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                tag = true;
                break;
            }
        }
        if (!tag) return NULL;

        fast = head;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

三哈希表

3.1 有效的字母异位词

思想
- 两个字符串长度不同，直接返回false
- 遍历字符串s，使用map统计第一个字符串s中每各字符出现的次数
- 遍历字符串t，若字符不存在于map中，则返回false；存在则进行减操作，当字符次数减为0时，从map移除
- map为空则表示两个字符串是字母异位词
- （进阶）由于题目中说明字符串都由小写字母组成，那么我们可以将所有字符映射到长度为26的数组，简化操作

代码（基础解法）

// https://leetcode.cn/problems/valid-anagram/description/
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        map<char, int> mp;
        for (int i = 0; i < s.length(); i ++) {
            char key = s[i];
            auto it = mp.find(key);
            if (it != mp.end()) {
                it->second += 1;
            } else {
                mp.insert(pair<char, int>(key, 1));
            }
        }

        for (int i = 0; i < t.length(); i ++) {
            char key = t[i];
            auto it = mp.find(key);
            if (it == mp.end()) {
                return false;
            } else {
                if (it->second == 0) {
                    return false;
                } else if (it->second == 1) {
                    mp.erase(it);
                } else {
                    it->second -= 1;
                }
            }
        }

        return mp.empty();
    }
};

最优解法

// https://leetcode.cn/problems/valid-anagram/description/
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        vector<int> mp(26, 0);

        for (char c : s) {
            mp[c - 'a'] ++;
        }
        for (char c : t) {
            mp[c - 'a'] --;
        }
        for (int c : mp) {
            if (c != 0) return false;
        }

        return true;
    }
};

3.2 两个数组的交集

代码

// https://leetcode.cn/problems/intersection-of-two-arrays/
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret;
        set<int> st;
    	// 将nums1的所有元素添加到set中，会自动去重
        for (int num : nums1) {
            st.insert(num);
        }
		
		// 遍历nums2，判断元素是否存在st中，存在则是两个数组的交集，添加到结果数组ret中
		// 为防止元素重复添加，需要将其从st中移除
        for (int num : nums2) {
            if (st.find(num) != st.end()) {
                ret.push_back(num);
                st.erase(num);
            }
        }

        return ret;
    }
};

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处：免费源码网-免费的源码资源网站 » 2024秋招算法

点赞(0) 打赏

本文分类：文章资讯
本文标签：2024秋招算法
浏览次数：21 次浏览
本文链接：https://freeymw.com/article/18924.html

评论列表共有 0 条评论

暂无评论

2024秋招算法

文章目录

参考资料

一 数组

1.1 二分查找

1.2 移除元素

1.3 长度最小的子数组

1.4 螺旋矩阵

1.5 在排序数组中查找元素的第一个和最后一个位置

二 链表

2.1 移除链表元素

2.2 设计链表

2.3 反转链表

2.4 两两交换链表中的节点

2.5 删除链表的倒数第N个节点

2.6 链表相交

2.7 环形链表II

三 哈希表

3.1 有效的字母异位词

3.2 两个数组的交集

评论列表 共有 0 条评论

发表评论 取消回复

一数组

二链表

三哈希表

评论列表共有 0 条评论

发表评论取消回复