数组 Leetcode 704 二分查找/Leetcode 59 螺旋矩阵/Leetcode 203移除链表元素

数组 Leetcode 704 二分查找

Leetcode 704

学习记录自代码随想录

二分法模板记忆，数值分析中牛顿迭代法

class Solution {public:
    int search(vector& nums, int target) { int left = 0, right = nums.size()-1;
        // 是否需要等于号，假设等于后看是否需要进循环以进行判断
        while(left <= right){ int mid = (left + right) / 2;
            if(nums[mid] < target){ left = mid + 1;
            }else if(nums[mid] > target){ right = mid - 1;
            }else{ return mid;
            }
        }
        return -1;
    }
};

Leetcode 59 螺旋矩阵

Leetcode 59

找出循环中的不变量。

class Solution {public:
    vector> generateMatrix(int n) { vector> res(n, vector(n, 0));
        // 每一圈循环开始坐标处
        int start_x = 0, start_y = 0;
        // 循环圈数
        int loop = n / 2;
        // 循环坐标值
        int i, j;
        // 每圈循环偏移值
        int offset = 1;
        // 填充数
        int cnt = 1;
        while (loop--) { i = start_x;
            j = start_y;
            // 本圈最上侧从左到右
            for (j; j < n - offset; j++) { res[i][j] = cnt++;
            }
            // 本圈最右侧从上到下
            for (i; i < n - offset; i++) { res[i][j] = cnt++;
            }
            // 本圈最下侧从右到左
            for (j; j >= offset; j--) { res[i][j] = cnt++;
            }
            // 本圈最左侧从下到上
            for (i; i >= offset; i--) { res[i][j] = cnt++;
            }
            start_x++;
            start_y++;
            offset += 1;
        }
        if (n % 2) { res[n / 2][n / 2] = cnt;
        }
        return res;
    }
};

Leetcode 203移除链表元素

Leetcode 203

要点：1.虚拟头节点：dummyhead->next = head;cur = dummyhead;

2.记得删除节点：循环条件为cur->next != nullptr，

if(cur->next->val == val){

temp = cur->next;

cur->next = cur->next->next;

delete temp;

}

3.最后head = dummyhead->next;delete dummyhead;return head;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {public:
    ListNode* removeElements(ListNode* head, int val) { ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* cur = dummyhead;
        while(cur->next != nullptr){ if(cur->next->val == val){ // 需要删除cur->next，先保存
                ListNode* temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            }else{ cur = cur->next;
            }
        }
        head = dummyhead->next;
        delete dummyhead;
        return head;
    }
};