过河

C++ 解法, 执行用时: 3ms, 内存消耗: 556KB, 提交时间: 2022-06-18

class Solution {
public:
    int crossRiver(int l, int s, int t, vector<int>& nums) {
        int before = 0,lst=0,end;
        int dp[20005];
        int rock[20005];
        sort(nums.begin(),nums.end());            
        memset(rock,0, sizeof(rock));
        memset(dp,-1, sizeof(dp));
        dp[0]=0;
        for(int num:nums)
            if(num<l){
                if((num-before)>2*s*t)
                {//printf("%d ",((num-before)%(s*t)+s*t)%9);
                 lst=(num-before)%(s*t)+s*t+lst;}
                else
                {//printf("%d ",((num-before)+lst)%9);
                 lst=(num-before)+lst;}
                rock[lst]=1;
                
                
                before=num;
            }else break;
        
         if((l-before)>2*s*t)
             end=(l-before)%(s*t)+s*t+lst;
         else
             l=(l-before)+l;
        for(int i=0;i<=end+t;i++){
            
            int mn=105;
            for(int j=s;j<=t;j++)
                if(i-j>=0&&dp[i-j]>-1) mn=min(dp[i-j]+rock[i],mn);
            if(mn!=105) dp[i] = mn;
        }
        int res=105;
        for(int i=end;i<end+t;i++)
            if(dp[i]>=0)res=min(res,dp[i]);
        return res;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 560KB, 提交时间: 2022-03-14

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param l int整型 
     * @param s int整型 
     * @param t int整型 
     * @param nums int整型vector 
     * @return int整型
     */
    
    int crossRiver(int l, int s, int t, vector<int>& nums) {
        // write code her
        int before = 0,lst=0,end;
        int dp[20005];
        int rock[20005];
        sort(nums.begin(),nums.end());
            
        memset(rock,0, sizeof(rock));
        memset(dp,-1, sizeof(dp));
        dp[0]=0;
        for(int num:nums)
            if(num<l){
                if((num-before)>2*s*t)
                {//printf("%d ",((num-before)%(s*t)+s*t)%9);
                 lst=(num-before)%(s*t)+s*t+lst;}
                else
                {//printf("%d ",((num-before)+lst)%9);
                 lst=(num-before)+lst;}
                rock[lst]=1;
                
                
                before=num;
            }else break;
        
         if((l-before)>2*s*t)
             end=(l-before)%(s*t)+s*t+lst;
         else
             l=(l-before)+l;
        for(int i=0;i<=end+t;i++){
            
            int mn=105;
            for(int j=s;j<=t;j++)
                if(i-j>=0&&dp[i-j]>-1) mn=min(dp[i-j]+rock[i],mn);
            if(mn!=105) dp[i] = mn;
            //printf("%d ",dp[i]);
        }
        int res=105;
        for(int i=end;i<end+t;i++)
            if(dp[i]>=0)res=min(res,dp[i]);
        return res;
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 432KB, 提交时间: 2022-07-13

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param l int整型
     * @param s int整型
     * @param t int整型
     * @param nums int整型vector
     * @return int整型
     */
    int crossRiver(int L, int S, int T, vector<int>& nums) {
        // write code here
        int M = nums.size();
        sort(nums.begin(), nums.end());

        if (S == T) {
            int cnt = 0;
            for (int i = 0; i < M; i++) {
                if (nums[i] % S == 0) {
                    cnt++;
                }
            }
            return cnt;
        }

        int river[10010];
        for (int i = 0; i < 10010; i++) {
            river[i] = 0;
        }
        int dist = 0;
        for (int i = 0, last = 0; i < M; i++) {
            if (nums[i] - last > 100) {
                dist += 100;
            } else {
                dist += nums[i] - last;
            }
            last = nums[i];
            river[dist] = 1;
        }

        int f[10010];
        f[0] = 0;
        for (int i = 1; i <= dist + 10; i++) {
            f[i] = 1e9;
            for (int j = S; j <= T; j++) {
                if (i - j >= 0) {
                    f[i] = min(f[i], f[i - j] + river[i]);
                }
            }
        }

        int res = 1e9;
        for (int i = dist + 1; i <= dist + 10; i++) {
            res = min(res, f[i]);
        }
        return res;
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 456KB, 提交时间: 2022-07-03

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param l int整型 
     * @param s int整型 
     * @param t int整型 
     * @param nums int整型vector 
     * @return int整型
     */
    int res = INT_MAX;
    unordered_set<int> destset;
    int end = 0;
    int crossRiver(int l, int s, int t, vector<int>& nums) {
        // write code here
        if(s == t){
            int step = 0;
            for(auto n : nums){
                if( n % t == 0) step ++;
            }
            return step;
        }
        sort(nums.begin(), nums.end());
        end = nums.back();
//         vector<int> dp(end + t + 1);
        int* dp;
        if(l > 2519){
            l = 2521;
            dp = new int[2521];
            for (auto num : nums) {
                dp[num % 2520] = 1;
            }
        }else{
            dp = new int[++l];
            for (auto num : nums) {
                dp[num] = 1;
            }
        }
        
        dp[0] = (nums[0] == 0 ? 1 : 0);
//         if(t == 1) dp[1] = 1;
//         else dp[1] = 0;
        for(int i = 1 ; i < s; i ++) dp[i] = INT_MAX;
        
        for(int i = s; i <= end + t && i <= l; i ++){
            int mn = INT_MAX;
            for(int j = s; j <= t; j ++){
                if(i - j >= 0){
                    mn = min(mn, dp[i - j]);
                }                      
            }
            dp[i] += mn;
//             else dp[i] = mn;
        }
//         for(int i = end; i < end+t && i <= l;i++)
//             if(dp[i]!= INT_MAX) res=min(res,dp[i]);
        return dp[--l];
//         return dp[l];
    }
    
//     void findMinStep(int l, int s, int t, int curl, int step){
//         if(curl > end) {
//             res = min(res, step);
//             return;
//         }
//         if(set.count(curl)) step ++;
//         for(int i = s; i <= t; i ++){
//             findMinStep(l, s, t, curl + i, step);
//         }
//     }
};

C 解法, 执行用时: 4ms, 内存消耗: 468KB, 提交时间: 2022-06-23

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param l int整型 
 * @param s int整型 
 * @param t int整型 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
void quickSort(int *nums, int start, int end) {
    if (start < end) {
        int rIndex = rand() % (end - start + 1) + start, tmp;
        tmp = nums[rIndex];
        nums[rIndex] = nums[start];
        nums[start] = tmp;
        
        int target = nums[start], i = start, j = end;
        while(i < j) {
            while(i < j && nums[j] > target) {
                j--;
            }
            if(i < j) {
                nums[i++] = nums[j];
            }
            while(i < j && nums[i] <= target) {
                i++;
            }
            if(i < j) {
                nums[j--] = nums[i];
            }
        }
        nums[i] = target;
        
        quickSort(nums, start, i - 1);
        quickSort(nums, i + 1, end);
    }
}

int min(int a, int b) {
    return a > b ? b : a;
}

int crossRiver(int l, int s, int t, int* nums, int numsLen ) {
    quickSort(nums, 0, numsLen - 1);
    
    if (s == t) {
        int count = 0;
        for (int i = 0; i < numsLen; i++) {
            if (nums[i] % s == 0) {
                count++;
            }
        }
        
        return count;
    } else {
        int lastNIndex = 0;

        int *dp = (int *)malloc(sizeof(int) * 10000); //(2 * t + 1)
        int j = 0, minDP, len = 10000;
        dp[0] = 0;

        int k = s * t, d = 0, x;
        if (nums[0] > k) {
            d = nums[0] - k;
            nums[0] -= d;
        }
        for (int i = 1; i < numsLen; i++) {
            x = nums[i] - d - nums[i - 1];
            if (x > k) {
                d += (x - k);
            }
            nums[i] -= d; 
        }

        x = l - d - nums[numsLen - 1];
        if (x > k) {
            d += (x - k);
        }
        l -= d;

        for (int i = 1; i < s; i++) {
            if (lastNIndex != numsLen && nums[lastNIndex] == i) {
                lastNIndex++;
            }
            dp[i] = 101;
        }
        for (int i = s; i <= t; i++) {
            if (lastNIndex != numsLen && nums[lastNIndex] == i) {
                lastNIndex++;
                dp[i] = 1;
            } else {
                dp[i] = 0;
            }
        }

        for (int i = t + 1; i <= (l + t - 1); i++) {
            minDP = 101;
            for (j = t; j >= s; j--) {
                minDP = min(minDP, dp[(i-j)%len]);
            }
            if (lastNIndex != numsLen && nums[lastNIndex] == i) {
                lastNIndex++;
                dp[i%len] = minDP + 1;
            } else {
                dp[i%len] = minDP;
            }
        }

        minDP = 101;
        for (int i = l; i <= (l + t - 1); i++) {
            minDP = min(minDP, dp[i%len]);
        }

        free(dp);
        
        return minDP;
    }
}

详情