C/C++每日一练(20230419) 插入区间、单词拆分、不同路径

#include <stdio.h>
#include <stdlib.h>
static int compare(const void *a, const void *b)
{
    return ((int *)a)[0] - ((int *)b)[0];
}
int **insert(int **intervals, int intervalsSize, int *intervalsColSize, int *newInterval,
             int newIntervalSize, int *returnSize, int **returnColumnSizes)
{
    int i, len = 0;
    int *tmp = (int*)malloc((intervalsSize + 1) * 2 * sizeof(int));
    for (i = 0; i < intervalsSize; i++)
    {
        tmp[i * 2] = intervals[i][0];
        tmp[i * 2 + 1] = intervals[i][1];
    }
    tmp[i * 2] = newInterval[0];
    tmp[i * 2 + 1] = newInterval[1];
    qsort(tmp, intervalsSize + 1, 2 * sizeof(int), compare);
    int **results = (int**)malloc((intervalsSize + 1) * sizeof(int *));
    results[0] = (int*)malloc(2 * sizeof(int));
    results[0][0] = tmp[0];
    results[0][1] = tmp[1];
    for (i = 1; i < intervalsSize + 1; i++)
    {
        results[i] = (int*)malloc(2 * sizeof(int));
        if (tmp[i * 2] > results[len][1])
        {
            len++;
      results[len][0] = tmp[i * 2];
      results[len][1] = tmp[i * 2 + 1];
        }
        else if (tmp[i * 2 + 1] > results[len][1])
        {
            results[len][1] = tmp[i * 2 + 1];
        }
    }
    len += 1;
    *returnSize = len;
    *returnColumnSizes = (int*)malloc(len * sizeof(int));
    for (i = 0; i < len; i++)
    {
        (*returnColumnSizes)[i] = 2;
    }
    return results;
}
int main(int argc, char* argv[])
{
  if (argc<3) return 1;
    int new_interv[2];
    new_interv[0] = atoi((char*)argv[1]);
    new_interv[1] = atoi((char*)argv[2]);
    int i, count = 0;
    int *size = (int*)malloc((argc - 3) / 2 * sizeof(int));
    int **intervals = (int**)malloc((argc - 3) / 2 * sizeof(int *));
    for (i = 0; i < (argc - 3) / 2; i++)
    {
        intervals[i] = (int*)malloc(2 * sizeof(int));
        intervals[i][0] = atoi((char*)argv[i * 2 + 3]);
        intervals[i][1] = atoi((char*)argv[i * 2 + 4]);
    }
    int *col_sizes;
    int **results = insert(intervals, (argc - 3) / 2, size, new_interv, 2, &count, &col_sizes);
    for (i = 0; i < count; i++)
    {
        printf("[%d,%d]\n", results[i][0], results[i][1]);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    bool wordBreak(string s, vector<string> &wordDict)
    {
        map<string, int> tmp;
        for (int i = 0; i < wordDict.size(); i++)
        {
            tmp[wordDict[i]]++;
        }
        int n = s.length();
        vector<bool> res(n + 1, false);
        res[0] = true;
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (res[j] && tmp[s.substr(j, i - j)])
                {
                    res[i] = true;
                    break;
                }
            }
        }
        return res[n];
    }
};
int main()
{
  Solution sol;
    string s = "leetcode";
  vector<string> wordDict = {"leet", "code"};
    cout << (sol.wordBreak(s, wordDict) ? "true" : "false") << endl;
    s = "applepenapple", wordDict = {"apple", "pen"};
  cout << (sol.wordBreak(s, wordDict) ? "true" : "false") << endl;
  s = "catsandog", wordDict = {"cats", "dog", "sand", "and", "cat"};
  cout << (sol.wordBreak(s, wordDict) ? "true" : "false") << endl;
  return 0;
}

#include <stdio.h>
#include <stdlib.h>
static int uniquePaths(int m, int n)
{
    int row, col;
    int *grids = (int*)malloc(m * n * sizeof(int));
    for (col = 0; col < m; col++)
    {
        grids[col] = 1;
    }
    for (row = 0; row < n; row++)
    {
        grids[row * m] = 1;
    }
    for (row = 1; row < n; row++)
    {
        for (col = 1; col < m; col++)
        {
            grids[row * m + col] = grids[row * m + col - 1] + grids[(row - 1) * m + col];
        }
    }
    return grids[m * n - 1];
}
int main()
{
    printf("%d\n", uniquePaths(3, 7));
    printf("%d\n", uniquePaths(3, 2));
    printf("%d\n", uniquePaths(7, 3));
    printf("%d\n", uniquePaths(3, 3));
    return 0;
}