代码随想录_刷题笔记_第一次

数组 — 二分查找法

题目链接：704. 二分查找 - 力扣（LeetCode）

**题目要求：**给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例：

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4     

**注意：**使用二分查找法的前提条件（有序数组、无重复元素）

解法1（左闭右闭）： left <= middle <= right

int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;    // 右边是闭合，所以数组中对应的那一项必须存在
    int middle = 0;
    while(left <= right)         // left = right时，仍存在有效值
    {
        middle = (left + right) / 2;
        if(nums[middle] < target)
            left = middle + 1;         // 闭合区间，自然去除那一个不符合条件的项
        if(nums[middle] > target)
            right = middle -1;
        if(nums[middle] == target)
            return middle;
    }
    return -1;
}

解法2（左闭右开）： left <= middle < right

int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize;
    int middle = 0;
    while(left < right)        // left == right时，middle无值可取
    {
        middle = (left + right) / 2;
        if(nums[middle] < target)
            left = middle + 1;
        if(nums[middle] > target)
            right = middle;           // 不是闭合区间
        if(nums[middle] == target)
            return middle;
    }
    return -1;
}

数组 — 移除元素

题目链接：27. 移除元素 - 力扣（LeetCode）

**题目要求：**给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

**示例：**给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

**思路：**快慢指针（对应的是数组的下标），数组中移除元素，其实就是后面的值覆盖前面的值

解法：

int removeElement(int* nums, int numsSize, int val) {
    int fast = 0;
    int slow = 0;
    for(fast = 0; fast < numsSize; fast++)
    {
        if(nums[fast] != val)
            nums[slow++] = nums[fast];
    }
    return slow;
}

数组 — 有序数组的平方

题目链接：977. 有序数组的平方 - 力扣（LeetCode）

**题目要求：**给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例：

• 输入：nums = [-4,-1,0,3,10]
• 输出：[0,1,9,16,100]
• 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

**思路：**双指针（一个指针指向第一个元素，一个指针指向最后一个元素）（前提：有序排列，最外层的平方值一定大于内层的平方值）

解法：

int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int i, j;
    int k = numsSize - 1;
    *returnSize = numsSize;    // 返回数组中元素的数量
    int* result = (int*)malloc(sizeof(int) * numsSize);
    for(i = 0, j = numsSize - 1; i <= j; )
    {
        if((nums[i] * nums[i]) >= (nums[j] * nums[j]))
        {
            result[k--] = nums[i] * nums[i];
            i++;
        }
        else
        {
            result[k--] = nums[j] * nums[j];
            j--;
        }
    }
    return result;
}

对于解法的改进（直接在原数组进行更改）：

int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int i = 0;
    int j, k;
    *returnSize = numsSize;
    for(j = numsSize - 1; j >= 0; j--)
    {
        if((nums[i] * nums[i]) > (nums[j] * nums[j]))    // 这里不能写 >= , nums[i] = k 会将平方值覆盖(i = j)
        {
            k = nums[j];
            nums[j] = nums[i] * nums[i];
            nums[i] = k;
        }
        else
        {
            nums[j] = nums[j] * nums[j];
        }
    }
    return nums;
}

数组 — 长度最小的子数组|滑动窗口

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

**题目要求：**给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

• 输入：s = 7, nums = [2,3,1,2,4,3]
• 输出：2
• 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

**思路：**双指针，滑动窗口（right 是窗口的结束位置）

解法：

int minSubArrayLen(int target, int* nums, int numsSize) {
    int len = numsSize;
    int result = 0;
    int left = 0, right = 0;    // 滑动窗口的起始位置和结束位置
    for( ; right < numsSize; right++)     // 结束位置一直右移
    {
        result += nums[right];
        while(result >= target)    // 当大过标准值时，开始移动起始位置（一个一个移动）
        {
            len = (right - left + 1) < len ? (right - left + 1) : len;
            result -= nums[left];
            left++;
        }
    }
    if(result < target && left == 0)   // 当数组中的全部值相加都小于标准值时，返回 0
        return 0;
    return len;
}

数组 — 螺旋矩阵

题目链接：59. 螺旋矩阵 II - 力扣（LeetCode）

**题目要求：**给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例：

输入: 3

输出: [ [ 1, 2, 3 ] ,

​ [ 8, 9, 4 ] ,

​ [ 7, 6, 5 ] ]

解法：

int** generateMatrix(int n, int* returnSize, int** returnColumnSizes) {
    *returnSize = n;
    *returnColumnSizes = (int*)malloc(sizeof(int) * n);
    int startX = 0;
    int startY = 0;
    int offset = 1;      // 偏移值
    int x, y, z;
    int count = 1;
    int num = n / 2;    // 要转的圈数
    int** result = (int**)malloc(sizeof(int*) * n);
    for(z = 0; z < n; z++)
    {
        result[z] = (int*)malloc(sizeof(int) * n);
        (*returnColumnSizes)[z] = n;
    }
    while(num)        // 一圈一圈的写
    {
        x = startX;
        y = startY;
        for( ; y < startY + n - offset; y++)
        {
            result[x][y] = count++;     // 从左到右那一行
        }
        for( ; x < startY + n - offset; x++)
        {
            result[x][y] = count++;
        }
        for( ; y > startY; y--)
        {
            result[x][y] = count++;
        }
        for( ; x > startX; x--)
        {
            result[x][y] = count++;
        }
        startX++;
        startY++;
        offset += 2;
        num--; 
    }
    if(n % 2 == 1)     // 最中心还有一个数据
    {
        result[n / 2][n / 2] = count;
    }
    return result;
}

链表 — 移除链表元素

题目链接：203. 移除链表元素 - 力扣（LeetCode）

**题目要求：**给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

**思路：**虚拟头节点（避免删除原头节点和其它节点之间的差异）（移除节点，直接使前一个节点指向下一个节点）

解法1（使用原来的链表进行操作）

struct ListNode* removeElements(struct ListNode* head, int val) {
    typedef struct ListNode ListNode; 
    ListNode* tmp;
    // 当头节点的值等于 val 时，去除头节点
    while(head && head->val == val)
    {
        tmp = head;
        head = head->next;
        free(tmp);
    }
    ListNode* Chead = head;
    // Chead: 要判断的节点的上一个节点   Chead->next: 要判断的节点
    while(Chead && Chead->next)
    {
        if(Chead->next->val == val)
        {
            tmp = Chead->next;
            Chead->next = Chead->next->next;
            free(tmp);
        }
        else
        {
            Chead = Chead->next;
        }
    }
    return head;
}

解法2（虚拟头节点）

struct ListNode* removeElements(struct ListNode* head, int val) {
    typedef struct ListNode ListNode; 
    ListNode* Vhead = (ListNode*)malloc(sizeof(ListNode));
    Vhead->next = head;
    ListNode* cur = Vhead;
    while(cur->next != NULL)     // 每次判断的是 cur 节点的下一个节点（为了记录上一个节点）
    {
       if(cur->next->val == val)
       {
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            free(tmp);
       }
       else
       {
            cur = cur->next;
       }
    }
    head = Vhead->next;
    free(Vhead);
    return head;
}

链表 — 设计链表

题目链接：707. 设计链表 - 力扣（LeetCode）

题目要求：

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

• MyLinkedList() 初始化 MyLinkedList 对象。
• int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
• void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
• void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
• void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

**思路：**统一使用虚拟头节点的方式（添加一个头节点）

解法：（单链表，虚拟头文件节点）

typedef struct node{
    int val;
    struct node *next;
} MyLinkedList;


MyLinkedList* myLinkedListCreate() {    // 在 create 时就创建了虚拟头文件节点
    MyLinkedList* p = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    p->next = NULL;
    return p;
}

int myLinkedListGet(MyLinkedList* obj, int index) {
    if(index < 0)
        return -1;

    MyLinkedList* head = obj->next;  // obj->next 才是链表中下标为零的位置（最前面的那一个节点是虚拟头节点）

    while(index-- && head){
        head = head->next;
    }

    if(head)
        return head->val;
    return -1;
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    MyLinkedList* node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    node->next = obj->next;    // 先使得新加入的节点指向的下一个节点为原来的节点地址
    node->val = val;
    obj->next = node;             // 再使得原来节点的上一个节点所指向的下一个节点等于新加入的节点
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    MyLinkedList* node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    node->next = NULL;
    node->val = val;
    MyLinkedList* cur = obj;
    while(cur->next){        // 找到链表中原本的最后一个节点
        cur = cur->next;
    }
    cur->next = node;
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    if(index <= 0){
        myLinkedListAddAtHead(obj,val);
        return;
    }
    MyLinkedList* node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    node->val = val;
    //找第index-1个元素
    MyLinkedList* cur = obj->next;
    while(cur && --index){      // 注意这里是 --index，而不是 index--
        cur = cur->next;
    }

    if(cur){
        node->next = cur->next;
        cur->next = node;
    }
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    MyLinkedList* cur = obj;
    while(cur->next && index--){    // 找到要删除节点的上一个节点
        cur = cur->next;
    }
    if(cur->next){                  // 避免下表大于整个链表的长度
        MyLinkedList* tmp = cur->next;
        cur->next = tmp->next;
        free(tmp);
    }
}

void myLinkedListFree(MyLinkedList* obj) {
    MyLinkedList* head = obj->next;
    while(head){
        obj->next = head->next;
        free(head);
        head=obj->next;
    }
    free(obj);   // 删除虚拟头节点
}

链表 — 翻转链表

题目链接：206. 反转链表 - 力扣（LeetCode）

**题目要求：**给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

解法1：（双指针）

struct ListNode* reverseList(struct ListNode* head) {
    typedef struct ListNode ListNode;
    ListNode* cur  = head;
    ListNode* prep = NULL;
    while(cur){
        ListNode* tmp = cur->next;
        cur->next = prep; // 翻转方向
        prep = cur;       // 先移动 prep 
        cur = tmp;        // 在移动 cur
    }
    return prep;
}

解法二：（递归）

struct ListNode* reverse(struct ListNode* prep, struct ListNode* cur){
    if(!cur)
        return prep;     // 当cur为NULL时，就代表着prep此时指向原链表的最后一个节点
    struct ListNode* tmp = cur->next;
    cur->next = prep;    // 翻转链表
    return reverse(cur, tmp);    // 递归调用时，cur、tmp均向后移动一位
}

struct ListNode* reverseList(struct ListNode* head) {
    return reverse(NULL, head);
}

链表 — 两两交换链表中的节点

题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）

**题目要求：**给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。（若节点的数量为奇数，最后一个节点不做处理）

示例：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

输入：head = [1]
输出：[1]

解法：（虚拟头节点）

struct ListNode* swapPairs(struct ListNode* head) {
    typedef struct ListNode ListNode;
    ListNode* vhead = (ListNode*)malloc(sizeof(ListNode));
    vhead->next = head;
    ListNode* cur = vhead;                 // cur记录的是所交换的两个结点之前的那个节点
    while(cur->next && cur->next->next){   // cur->next 写在前面为了避免对空指针进行访问
        ListNode* left = cur->next;        // 注意一下这里的交换逻辑
        ListNode* tmp  = cur->next->next->next;
        cur->next = cur->next->next;
        (cur->next)->next = left;
        left->next = tmp;
        cur = cur->next->next;
    }   
    return vhead->next;
}

链表 — 删除链表倒数第n个节点

题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

**题目要求：**给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

**思路：**快慢指针，让快指针先移动 n+1 步

解法：

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    typedef struct ListNode ListNode;
    ListNode* vhead = (ListNode*)malloc(sizeof(ListNode));
    vhead->next = head;
    ListNode* fast = vhead;
    ListNode* slow = vhead;
    n++;
    for(int i = 0; i < n; i++){
        if(!fast)
            return -1;        // 避免要删除的节点超出链表的长度
        fast = fast->next;
    }
    while(fast){
        fast = fast->next;
        slow = slow->next; 
    }
    slow->next = slow->next->next;
    head = vhead->next;
    free(vhead);
    return head;
}