DOCSEARCHbyAlgolia
Submit Docs

xiaoluo776 Programming Notes

website·Indexed 29 days ago

https://xiaoluo776.github.io/

A collection of programming notes and algorithm implementations covering C and Java. Topics include data structures like linked lists and linear tables, C standard library usage (printf, limits.h, float.h), and common algorithms such as binary search, double pointers, sliding windows, and sorting methods (selection, insertion, and bubble sort).

Tokens
6.9K
Snippets
44
Records
48
Agent score
75%

What's inside xiaoluo776

  1. Insert a node at a specific position in a linked list

    To insert a node at position n:

    1. If n == 1, perform a head insertion.
    2. Otherwise, traverse the list to find the node at position n-1.
    3. Set the new node's next pointer to the current n-th node (temp2->next).
    4. Set the n-1-th node's next pointer to the new node.
    void Insert(int date, int n)
{
    struct Node* temp1 = (struct Node*)malloc(sizeof(struct Node));
    temp1->date = date;
    temp1->next = NULL;

    if (n == 1) {
        temp1->next = head;
        head = temp1;
        return;
    }

    struct Node* temp2 = head;
    for (int i = 0; i < n - 2; i++) {
        temp2 = temp2->next;
    }
    temp1->next = temp2->next;
    temp2->next = temp1;
}

  2. Calculate and print the size of a data type

    Use the sizeof operator to determine the size of a type or variable in bytes. The resulting size should be printed using the %zd format specifier.
    printf("%zd", sizeof(target));

  3. Advanced scanf input techniques and character suppression

    Use modifiers and scansets in scanf to control how input is read, including suppressing specific characters or reading strings with spaces.
    // 1. Suppress input: Use %* to read and discard data
int n;
scanf("%*d %*d %d", &n); // Discards first two integers, reads the third

// 2. Read string including spaces: Use scanset [^\n]
char ch[100];
scanf("%[^\n]", ch); // Reads until a newline is encountered

// 3. Limit field width
int a;
scanf("%4d", &a); // Reads maximum of 4 digits

// 4. Precise filtering with scansets
char str[100];
scanf("%[1-9]", str);    // Reads only digits 1-9
scanf("%[^1-9]", str);   // Reads everything EXCEPT digits 1-9

// 5. Suppress a range of characters
char ch;
scanf("%*[a-zA-Z]%s", ch); // Discards leading letters, then reads the string

  4. Print all elements of a linked list

    Traverse the linked list starting from the head pointer and print each node's value until a NULL pointer is encountered.
    void Print()
{
    struct Node* temp = head;
    printf("Linked list: ");
    while (temp != NULL)
    {
        printf("%d ", temp->date);
        temp = temp->next;
    }
    printf("\n\n");
}

  5. Insert a node at the head of a linked list

    To insert a new element at the beginning of the list, allocate memory for a new node, assign the value, and point the new node's next pointer to the current head. Then, update head to point to the new node.
    void Insert(int x)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->date = x;
    temp->next = head;
    head = temp;
}

  6. Initialize and destroy a sequential linear list

    Use InitList to allocate memory for a new linear list and set its length to 0. Use DestroyList to free the allocated memory and nullify the pointer.
    // Initialize empty list
void InitList (SqList** L) {
    (*L) = (SqList*)malloc(sizeof(SqList));
    (*L)->length = 0;
}

// Destroy list
void DestroyList (SqList** L) {
    free(*L);
    *L = NULL;
}

  7. Define a sequential linear list structure in C

    A sequential linear list is implemented using a fixed-size array and a length counter to track the number of elements currently stored.
    #define MAX_SIZE 100

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
} SqList;

  8. Avoid IndexOutOfBoundsException in sliding window loops

    When using a while loop to scan for a target value in an array, always check the array boundary (j < nums.length) before accessing the array element (nums[j]). Reversing this order can lead to an ArrayIndexOutOfBoundsException when the target value is at the very end of the array.
    // INCORRECT: May cause IndexOutOfBoundsException
while(nums[j] == target && j < nums.length) {
    j++;
}

// CORRECT: Boundary check comes first
while(j < nums.length && nums[j] == target) {
    j++;
}

  9. Manually free linked list memory

    To prevent memory leaks, iterate through the list and free each node individually. It is a best practice to set the pointer to NULL after freeing to improve program robustness and prevent accidental access.
    while (head != NULL)
{
    struct Node* temp = head;
    head = head->next;
    free(temp);
    temp = NULL;
}

  10. Sort squares of a sorted array using Two Pointers

    Given an integer array nums sorted in non-decreasing order, return a new array containing the squares of each number, also sorted in non-decreasing order. The implementation uses two pointers (one at the start and one at the end) to compare absolute values and fill the result array from back to front.
    class Solution {
    public int[] sortedSquares(int[] nums) {
        int k = nums.length - 1;
        int[] numsSort = new int[nums.length];
        int i = 0;
        int j = k;
        while (i <= j) {
            if (nums[j] * nums[j] > nums[i] * nums[i]) {
                numsSort[k--] = nums[j] * nums[j--];
            } else {
                numsSort[k--] = nums[i] * nums[i++];
            }
        }
        return numsSort;
    }
}

  11. Find first and last position of an element using Binary Search

    To find the range of a target value in a sorted array, you can use two binary search functions: one to find the left border and one to find the right border. The final range is derived by adjusting these borders. If the target is not found, the function returns [-1, -1].
    class Solution {
    int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // Case 1: Target not found
        if (leftBorder == -2 || rightBorder == -2) {
            return new int[] {-1, -1};
        }
        // Case 3: Target exists
        if (rightBorder - leftBorder > 1) {
            return new int[] {leftBorder + 1, rightBorder - 1};
        }
        // Case 2: Target not found
        return new int[] {-1, -1};
    }

    int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2;
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2;
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) {
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
}

  12. Find first and last position of an element in a sorted array using Binary Search

    Given a sorted integer array nums and a target value target, find the starting and ending position of the target. If the target is not found, return [-1, -1]. This is implemented using a binary search approach to find the left and right borders.
    class Solution {
    int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // Case 1: target not found
        if (leftBorder == -2 || rightBorder == -2) {
            return new int[] {-1, -1};
        }
        // ...
    }
}