Skip to content

代码随想录

参考资料

代码随想录 - 系统刷题, 总结的很棒 - 5

数组

力扣 no.704

二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
};
  • 前提为有序无重复
  • 区间的定义 (循环不变量) 为两种, 左闭右闭或左闭右开
  • 左闭右闭, while 使用 <=, if (nums [middle]>target) right 赋值为 middle-1
  • 左闭右开, while 使用 <, if (nums [middle]>target) right 赋值为 middle

力扣 no.27

移除元素

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};
  • 双指针法
  • 快指针寻找新数组的元素, 慢指针指向更新新数组下标的位置
  • 首尾指针, 从数组两端向中间移动可以将 \(n+k\) 优化到 \(n\)

力扣 no.977

有序数组的平方

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j,因为最后要处理两个元素
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};
  • 双指针法, 一开始我以为要合并相等项呢 (其实也差不多)

力扣 no.209

长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)
            }
        }
        // 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};
  • 滑动窗口法

力扣 no.59

螺旋矩阵 II

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次,例如n为奇数3,那么loop = 1 只是循环一圈,矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置,例如 :n为3, 中间的位置就是(1,1),n为5,中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度,每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j; j < n - offset; j++) {
                res[i][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候,起始位置要各自加1, 例如 :第一圈起始位置是(0, 0),第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话,需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};
  • 模拟, 坚持循环不变量原则, 左闭右开

卡码网 no.58

区间和

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, a, b;
    cin >> n;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) cin >> vec[i];
    while (cin >> a >> b) {
        int sum = 0;
        // 累加区间 a 到 b 的和
        for (int i = a; i <= b; i++) sum += vec[i];
        cout << sum << endl;
    }
}
  • 前缀和

卡码网 no.44

开发商购买土地\ n*m 个区块拥有权值, 所有区块分配给 A 和 B\ 只允许将区域按横向或纵向划分成两个子区域, 求 A 和 B 的最小权值之差\

#include <iostream>
#include <vector>
#include <climits>

using namespace std;
int main () {
    int n, m;
    cin >> n >> m;
    int sum = 0;
    vector<vector<int>> vec(n, vector<int>(m, 0)) ;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> vec[i][j];
            sum += vec[i][j];
        }
    }

    int result = INT_MAX;
    int count = 0; // 统计遍历过的行
    for (int i = 0; i < n; i++) {
        for (int j = 0 ; j < m; j++) {
            count += vec[i][j];
            // 遍历到行末尾时候开始统计
            if (j == m - 1) result = min (result, abs(sum - count - count));

        }
    }

    count = 0; // 统计遍历过的列
    for (int j = 0; j < m; j++) {
        for (int i = 0 ; i < n; i++) {
            count += vec[i][j];
            // 遍历到列末尾的时候开始统计
            if (i == n - 1) result = min (result, abs(sum - count - count));
        }
    }
    cout << result << endl;
}
  • 求前缀和的过程中可解

链表

力扣 no.203

移除链表元素

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头结点
        while (head != NULL && head->val == val) { // 注意这里不是if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 删除非头结点
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};
  • 虚拟头节点/递归/朴素, 解法很多

力扣 no.707

设计链表

//get(index)：获取链表中第 index 个节点的值 如果索引无效, 则返回-1
//addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点 插入后, 新节点将成为链表的第一个节点 
//addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素
//addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点 如果 index 等于链表的长度, 则该节点将附加到链表的末尾 如果 index 大于链表长度, 则不会插入节点 如果index小于0, 则在头部插入节点
//deleteAtIndex(index)：如果索引 index 有效, 则删除链表中的第 index 个节点
  • 略

力扣 no.206

翻转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};
  • 迭代/递归

力扣 no.24

两两交换链表中的节点

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* temp = dummyHead;
        while (temp->next != nullptr && temp->next->next != nullptr) {
            ListNode* node1 = temp->next;
            ListNode* node2 = temp->next->next;
            temp->next = node2;
            node1->next = node2->next;
            node2->next = node1;
            temp = node1;
        }
        ListNode* ans = dummyHead->next;
        delete dummyHead;
        return ans;
    }
};
  • easy

力扣 no.19

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

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        head=new ListNode(0,head);
        ListNode *s(head),*q(head);
        for(;n>-1;n--) q=q->next;
        while(q){
            q=q->next;
            s=s->next;
        }
        s->next=s->next->next;
        return head->next;
    }
};
  • 双指针加哑节点

力扣 no.160

判断两个链表相交点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}
// 双指针正解真的巧妙,指针走完后交换到另一个链表的头节点
// 把三段距离设为abc,一个走完是a+c,另一个b+c,交换链表,走同样距离刚好是a+b+c,刚好在交点处
  • 用哈希 / 对齐太简单, 不说了

力扣 no.142

环形链表 II

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr) {
            slow = slow->next;
            if (fast->next == nullptr) {
                return nullptr;
            }
            fast = fast->next->next;
            if (fast == slow) {
                ListNode *ptr = head;
                while (ptr != slow) {
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr;
    }
};
  • 快慢指针
  • s 到达环入口时 (f - 环入口) 一定等于 s 与 f 相遇时 (环入口 - s) 设为距离 c
  • 链表头到环入口距离一定为整数倍的环长 + c

哈希表

力扣 no.242

给定两个字符串 s 和 t, 编写一个函数来判断 t 是否是 s 的字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        int m[26]={0},l(0);
        if(s.size()==t.size()) l=s.size();
        else return 0;
        for(int i(0);i<l;i++){
            m[s[i]-'a']++;m[t[i]-'a']--;
        }
        for(int i(0);i<26;i++){
            if(m[i]) return 0;
        }
        return 1;
    }
};
  • easy

力扣 no.349

给定两个数组 nums1 和 nums2, 返回它们的交集

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> s(nums1.begin(),nums1.end());
        unordered_set<int> res;
        for(int i(0);i<nums2.size();i++){
            if(s.find(nums2[i])!=s.end()) res.insert(nums2[i]);
        }
        return vector<int>(res.begin(),res.end());
    }
};
  • unordered_set 秒杀

力扣 no.202

快乐数

class Solution {
    int happy(int n){
        int sum;
        for(sum=0;n>0;n/=10) sum+=(n%10)*(n%10);
        return sum;
    }
public:
    bool isHappy(int n) {
        map<int,bool> m;
        while(n!=1){
            n=happy(n);
            if(m[n]) return 0;
            m[n]=1;
        }
        return 1;
    }
};
  • 直接哈希非常简单
  • 快慢指针判断环更好!!!
  • 正解: 数学角度, 这道题其实只能存在一个环, 硬编码那个环, 然后只要到达环中某一个数字就返回 0

力扣 no.1

两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            // 遍历当前元素，并在map中寻找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果没找到匹配对，就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};
  • 无需多言

力扣 no.454

四数相加 II

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> umap; //key:a+b的数值，value:a+b数值出现的次数
        // 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
        for (int a : A) {
            for (int b : B) {
                umap[a + b]++;
            }
        }
        int count = 0; // 统计a+b+c+d = 0 出现的次数
        // 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
        for (int c : C) {
            for (int d : D) {
                if (umap.find(0 - (c + d)) != umap.end()) {
                    count += umap[0 - (c + d)];
                }
            }
        }
        return count;
    }
};
  • \(O(n^2)\) 记录 \(a+b\) 的和, 然后 \(O(n^2)\) 遍历 \(c+d\) 看是否有相反数

在`