944. Delete Columns to Make Sorted

tags: Easy、Sort

You are given an array of n strings strs, all of the same length.
The strings can be arranged such that there is one on each line, making a grid.
For example, strs = ["abc", "bce", "cae"] can be arranged as follows:
abc
bce
cae
You want to delete the columns that are not sorted lexicographically. In the above example (0-indexed), columns 0 ('a', 'b', 'c') and 2 ('c', 'e', 'e') are sorted, while column 1 ('b', 'c', 'a') is not, so you would delete column 1.
Return the number of columns that you will delete.

解法:

int minDeletionSize(char** strs, int strsSize) {
    int result = 0;
    int col_len = strlen(strs[0]);

    for (int j = 0; j < col_len; j++) {
        for (int i = 1; i < strsSize; i++) {
            if (strs[i][j] - strs[i-1][j] < 0) {
                result++;
                break;
            }
        }
    }
    return result;
}

977. Squares of a Sorted Array

tags: Easy、Sort

　Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

解法1:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void bubbleSort (int* array, int arraySize)  {
    for (int i = 0; i < arraySize-1; i++) {
        for (int j = 0; j < arraySize-1-i; j++) {
            if (array[j] > array[j+1]) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int* sort = (int*)calloc(numsSize, sizeof(int));
    *returnSize = numsSize;

    for (int i = 0; i < numsSize; i++) {
        sort[i] = pow(nums[i], 2);
    }
    bubbleSort(sort, numsSize);

    return sort;
}

解法2:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void squareSort (int* array, int* sort, int arraySize)  {
    int left = 0;
    int right = arraySize - 1;
    int pos = arraySize - 1;

    while (left <= right) {
        if (abs(array[left]) > abs(array[right])) {
            sort[pos] = pow(array[left], 2);
            left++;
        } 
        else {
            sort[pos] = pow(array[right], 2);
            right--;
        }
        pos--;
    }

}
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int* sort = (int*)calloc(numsSize, sizeof(int));
    *returnSize = numsSize;
    squareSort(nums, sort, numsSize);
    return sort;
}

2089. Find Target Indices After Sorting Array

tags: Easy、Sort

You are given a 0-indexed integer array nums and a target element target.
A target index is an index i such that nums[i] == target.
Return a list of the target indices of nums after sorting nums in non-decreasing order. If there are no target indices, return an empty list. The returned list must be sorted in increasing order.

解法1:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void bubbleSort(int* array, int arraySize) {
    for (int i = 0; i < arraySize-1; i++) {
        for (int j = 0; j < arraySize-1; j++) {
            if (array[j] > array[j+1]) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            } 
        }
    }
}

int* targetIndices(int* nums, int numsSize, int target, int* returnSize) {
    int* result = (int*)calloc(numsSize, sizeof(int));
    bubbleSort(nums, numsSize);
    int index = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == target) {
            result[index++] = i;
        }
    }
    *returnSize = index;
    return result;
}

1351. Count Negative Numbers in a Sorted Matrix

tags: Easy、Sort

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

解法:

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int count = 0;
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < *gridColSize; j++) {
            if (grid[i][j] < 0) {
                count++;
            }
        }
    }
    return count;
}