Leetcode - Array

2114. Maximum Number of Words Found in Sentences

주어진 문장들에서 가장 많은 단어를 갖는 문장의 단어수는?

Input: sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
Output: 6

/**
1. Constraints
 1 <= s[i] <= 100
 1 <= sentencesSize <= 100

2. Ideas & complexcity
 - count space -> O(N) / O(1)
 - save frequency to hashtable, then count table[space] -> O(N) / O(N)
 - using strtok(s, ' ') -> O(N) , O(1)

3. code

4. test cases
 - sentnese is single char
 - 
*/

int mostWordsFound(char ** sentences, int sentencesSize){
    int max = 0;
    for (int i = 0; i < sentencesSize; i++) {
        int cnt = 0, j = 0;
        while (sentences[i][j] != '\0') {
            if (sentences[i][j++] == ' ')
                cnt++;
        }
        if (cnt > max)
            max = cnt;
    }
    return max + 1;
}

35. Search Insert Position

주어진 정렬된 배열에 target값이 존재하면 idx출력, 없다면 target값이 추가되어야 할 idx출력

Input: nums = [1,3,5,6], target = 2
Output: 1

/**
1. Constraints
 - int, can be negative
 - -10000 <= target, num[i] <= 10000
 - 1 <= num.lenth <= 10000 (no 0 length)
 - nums[] is ascending order
 - must be logN
 
2. Ideas
 - binary search -> O(logN) / O(1) 
 
3. coding
 - use standard library bsearch() -> (X)
 - implement bsearch()
   - input same with bsearch() / return: index

4. test cases
 - target include or not include
 - target idx is left/right
 - check the negative number
 - all of nums[] are same, and some num[i] are duplicated

*/
int searchInsert(int* nums, int numsSize, int target){
    int left = 0, right = numsSize - 1;
    
    while (left <= right) {
        //int mid = left + (right - left) / 2;
        int mid = (right + left) / 2;
        if (target == nums[mid])
            return mid;
        if (target < nums[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}