daily note

2026-5-18

今天记录一下昨天写的一道快速排序和快速选择的题目，之前都是用python写的，现在要转成c++了的，感觉还是不是很适应的，所以尽量坚持每天记录下来。

• 快速排序

void quick_sort(vector<int> &nums, int left, int right){
    if (left >= right){
        return;
    }
    int pivot = nums[left+(right-left)/2];
    int i = left - 1;
    int j = right + 1;
    while(i < j){
        do i++; while(nums[i] < pivot);
        do j--; while(nums[j] > pivot);
        if (i < j){
            swap(nums[i], nums[j]);
        }
    }
    quick_sort(nums, left, j);
    quick_sort(nums, j+1, right);
}

• 快速排序（python）

def quick_sort(nums,left,right):
    if left>=right:
        return
    pivot = nums[left+(right-left)//2]
    nums_left = [x for x in nums if x < pivot]
    nums_mid = [x for x in nums if x == pivot]
    nums_right = [x for x in nums if x > pivot]
    return quick_sort(nums_left,0,len(nums_left)-1) + nums_mid + quick_sort(nums_right,0,len(nums_right)-1)

• 快速选择

int quikc_select(vector<int> &nums, int left; int right, int k){
    if (left >= right){
        return nums[left];
    }

    int pivot = nums[left+(right-left)/2];
    int i = left - 1;
    int j = right + 1;
    while(i < j){
        do i++; while(nums[i] < pivot);
        do j--; while(nums[j] > pivot);
        if (i < j){
            swap(nums[i], nums[j]);
        }
    }
    if(j >= k){
        return quikc_select(nums, left, j, k);
    }
    else{
        return quikc_select(nums, j+1, right, k);
    }
}

2026-5-19

• 双指针

双指针往往用来解决数组两侧的问题，可以使用党项指针，双向指针，快慢指针等

// 双指针
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;

int main(){
    string line;
    getline(cin, line);
    stringstream ss(line);
    vector<int> nums;
    int num;
    while(ss >> num){
        nums.push_back(num);
    }
    
    int left = 0; right = nums.size()-1;
    int target;
    cin >> target;
    nums.sort(nums.begin(), nums.end());
    while(left < right){
        int sum = nums[left] + nums[right];
        if (sum == target){
            cout << left << " " << right << endl;
            break;>>>>
        }
        else if (sum < target){
            left ++;
        }
        else{
            right --;
        }
    }
    if (left >= right){
        cout << "No solution" << endl;
    }
}

#include <vector>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
// 快慢指针，可以用来判断是否有环的存在；
struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
}

bool hasCycle(ListNode *head){
    ListNode *fast = head;
    ListNode *slow = head;
    while (fast != nullptr && fast->next != nullptr){
        if (fast == slow){
            return true;
        }
        fast = fast->next->next;
        slow = slow->next;
    }
    return false;
}

int main(){
    string line;
    getline(cin, line);
    stringstream ss(line);
    ListNode *tail = nullptr;
    while(ss >> num){
        if(tail == nullptr){
            tail = new ListNode(num);
        }
        else{
            ListNode *node = new ListNode(num);
            tail->next = node;
            tail = node;
        }
    }

    bool result = hasCycle(tail);
    if (result){
        cout << "有环" << endl;
    }
    else{
        cout << "无环" << endl;
    }
}

2026-5-20

• 二分法，二分法往往用来解决有序数组的问题，可以用来寻找目标值，寻找边界值等
• 一道dfs的题目，感觉还是不太熟练的，还是需要多练习的

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;

int main(){
    string line;
    getline(cin, line);
    stringstream ss;
    vector<int> nums;
    int num;
    while(ss >> nunm){
        nums.push_back(num);
    }
    int target;
    cin >> target;
    bool found = false;
    int left = 0, right = nums.size() - 1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if (nums[mid] == target){
            cout << mid << endl;
            break;
        }
        else if(nums[mid] <target){
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
    }
    if (!found){
        cout << "Not found" << endl;
    }
}

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

list1 = list(map(int, input().split()))
target = int(input())
result = binary_search(list1, target)
if result != -1:
    print(result)
else:
    print("Not found")

# dfs解决岛屿数量的问题
# 随便来个岛屿作为例子
matrix = [[1, 1, 0, 0, 0],
          [1, 1, 0, 0, 0],
          [0, 0, 1, 0, 0],
          [0, 0, 0, 1, 1]]

def dfs(matrix, i, j):
    rows = len(matrix)
    columns = len(matrix[0])
    index = [[-1,0], [1,0], [0,-1], [0,1]]
    matrix[i][j] = 0
    for inx in index:
        x = i + inx[0]
        y = j + inx[1]
        if x in range(rows) and y in range(columns) and matrix[x][y] == 1:
            dfs(matrix, x, y)

rows = len(matrix)
columns = len(matrix[0])
if rows == 0:
    print(0)
count = 0

for x in range(rows):
    for y in range(columns):
        if matrix[x][y] == 1:
            dfs(matrix, x, y)
            count += 1
print(count)

#include <vector>
#include <iostream>
#include <string>
using namespace std;

vector<vector<int>> matrix = {{1, 1, 0, 0, 0},
                              {1, 1, 0, 0, 0},
                              {0, 0, 1, 0, 0},
                              {0, 0, 0, 1, 1}};

void dfs(vector<vector<int>> &matrix, int x, int y){
    matrix[x][y] = 0;
    int rows = matrix.size();
    int columns = matrix[0].size();
    if ( x - 1 >= 0 and matrix[x-1][y] == 1){
        dfs(matrix, x-1, y);
    }
    if ( x + 1 < rows and matrix[x+1][y] == 1){
        dfs(matrix, x+1, y);
    }
    if ( y - 1 >= 0 and matrix[x][y-1] == 1){
        dfs(matrix, x, y-1);
    }
    if ( y + 1 < columns and matrix[x][y+1] == 1){
        dfs(matrix, x, y+1);
    }
}


int main(){
    int rows = matrix.size();
    int columns = matrix[0].size();
    int ans = 0;
    if (rows == 0){
        ans = 0;
    }
    for(int x = 0; x < rows; x++){
        for(int y = 0; y < columns; y++){
            if (matrix[x][y] == 1){
                dfs(matrix, x, y);
                ans++;
            }
        }
    }
    cout << ans << endl;
}