Codility 网站练习题

时间：2023-02-13 10:32:08

Lesson1.2:FrogJmp

https://codility.com/demo/results/trainingGWCV2Z-YYS/

int solution(int X, int Y, int D) {
    // write your code in C99'
    int diff = Y - X;
    if(diff % D == 0)
        return diff /D;
    else
        return diff / D + 1;
}

Lesson1.3:PermMissingElem

https://codility.com/demo/results/trainingFSS3GC-SUR/

https://codility.com/demo/results/trainingYPCVGU-2PV/

class Solution {
    public int solution(int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        if(A.Length == 0)
        return 1;
        int sum = 1;
        for(int i = 1; i < A.Length; i ++)
        {
            sum += i + 1;
            A[0] += A[i];
        }
        sum += A.Length +1;
        return sum - A[0];
    }
}


Lesson 2.1:FrogRiverOne  

https://codility.com/demo/results/training9Y7N9S-UDT/ 

这个英文 题目有点。。。 一次性100分不容易

class Solution {
    public int solution(int X, int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
         if(A.Length == 1)
        {
            return A[0] == X ? 0 : -1;
        }

        bool[] array = new bool[X];
        array[A[0] - 1] = true;
        A[0] = 1;
        for(int i = 1;i < A.Length; i ++)
        {
            if(array[A[i] - 1] == false)
            {
                A[0] += 1;
                array[A[i] - 1] = true;
            }
            if(A[0] >= X)
                return i;
        }
        return -1;
    }
}


Lesson 2.2 : 

https://codility.com/demo/results/trainingFM9S6F-HGD/  

数组会出现重复数据。。。 1 4 1


https://codility.com/demo/results/trainingMGUKDA-PRT/ 

题目要求很细致 时间复杂度和空间复杂度 注意清楚了 基本不会出错 如果试图更简洁，如我第一个代码，则出现了其他bug

class Solution {
    public int solution(int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int sum = 0;
        for (int i = 0; i < A.Length;i ++)
        {
            sum +=  i + 1 - A[i];
        }
        if(sum == 0)
            return 1;
        return 0;       
    }
}
class Solution {    public int solution(int[] A) {        // write your code in C# 6.0 with .NET 4.5 (Mono)        bool[] flagArray = new bool[A.Length];        int sum = 0;        for (int i = 0; i < A.Length;i ++)        {            if(A[i] > A.Length || flagArray[A[i] - 1] == true)            {                return 0;  //值大于A.Length 有相同元素            }            sum +=  i + 1 - A[i];         //这里不需要计算sum了，有上面的就ok了 懒得改了            flagArray[A[i] - 1] = true;        }        if(sum == 0)            return 1;        return 0;      }}

Lesson 2.3 :MissingInteger

class Solution {
    public int solution(int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        bool[] flags = new bool[A.Length];
        for(int i = 0; i < A.Length; i ++)
        {
            if(A[i] > 0 && A[i] <= A.Length)
            {
                if(flags[A[i] - 1] == false)
                    flags[A[i] -1] = true;
            }
        }
        
        for(int i = 0; i < flags.Length; i ++)
        {
            if(flags[i] == false)
                return i + 1;
        }
        return A.Length + 1;  // 数组里全是true   [1,2,3] 注意这儿
    }
}

Lesson 2.4: MaxCounters  88分，最糟糕的情况 时间复杂度是 m*n,不符合意义 另：这题理解题意用了20多分钟，在思考如何优化。。。。

class Solution {
    public int[] solution(int N, int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int[] result = new int[N];
        int max = 0;
        //int total = 0;
        for(int i = 0; i < A.Length; i ++)
        {
            if(A[i] == N + 1)
            {
                for(int j = 0; j < result.Length; j ++)  //最坏情况 每次进来循环
                {
                    result[j] = max;
                }
            }
            else if(A[i] >= 1 && A[i] <= N)   //因为限制了输入，其实此处直接else即可
            {
                result[A[i] - 1] += 1;
                if(max < result[A[i] - 1])
                {
                    max = result[A[i] - 1];
                }
            }
        }

        return result;
    }
}

 

MaxCounters
class Solution {
    public int[] solution(int N, int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int[] result = new int[N];  
        int max = 0;  
        int total = 0;  
        for(int i = 0; i < A.Length; i ++)  
        {  
            if(A[i] == N + 1)  
            {              
                //记录上次所以数组应该修改的值
                total = max;
            }  
            else if(A[i] >= 1 && A[i] <= N)   //因为限制了输入，其实此处直接else即可  
            {  
                if(result[A[i] - 1] >= total)
                {
                    result[A[i] - 1] += 1;  
                }
                else
                {
                    result[A[i] - 1] = total +1;
                }

                if(max < result[A[i] - 1])  
                {  
                    max = result[A[i] - 1];  
                }  
            }  
        }     
        for(int i = 0 ; i < result.Length; i ++)
        {
            if(result[i] < total)
                result[i] = total;
        }      
        return result;   
    }
}

Lesson 3.1CountDiv

class Solution {
    public int solution(int A, int B, int K) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int count = B / K - A / K;
        if(A % K != 0)
            return count;
        return count  + 1;
    }
}


Lesson 3.2  PassingCars

90分，极大数检测会出 count可能会超出int范围了

class Solution {
    public int solution(int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)

        int count = 0;
        int zeroCount = 0;
        for(int i = A.Length -1; i >= 0 ; i --)
        {
            if(A[i] == 0)
            {
                count += A.Length - i - 1 - zeroCount;
                zeroCount ++;
            }
        }
        if(count > 1000000000)
            return -1;
        return count;
    }
}

PassingCars  极端情况下的超越int型范围，有时候确实不好判断，但我们多想一步，代码就更完善一点，有时间就是一点区别 

class Solution {
    public int solution(int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)

        int count = 0;
        int zeroCount = 0;
        for(int i = A.Length -1; i >= 0 ; i --)
        {
            if(A[i] == 0)
            {
                count += A.Length - i - 1 - zeroCount;
                if(count > 1000000000)       //正序和逆序遍历代码一样，区别是逆序此处count是累计的真实值，所以此处可以直接判断
                return -1;                   //正常情况下 这俩者代码没有多大区别，特殊边界情况很难碰到，写算法时就要注意

                zeroCount ++;
            }
        }
        if(count > 1000000000)
            return -1;
        return count;
    }
}

Lesson 3.3

MinAvgTwoSlice  常规解法 Correctness 100。  Perfomance 20。。。

class Solution {
    public int solution(int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int minIndex = 0;
        double minAve = (A[0] + A[1]) / 2.00;
        for(int i = 0; i < A.Length - 1; i ++)
        {
            int sum = A[i];
            for(int j = i + 1; j < A.Length; j ++)
            {
                sum += A[j];
                double ave = sum / ( (j - i + 1) * 1.00);
                if(minAve > ave)
                    {
                        minIndex = i;
                        minAve = ave;
                    }
            }
        }
        return minIndex;
    }
}
  MinAvgTwoSlice 
class Solution {
    public int solution(int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int minIndex = 0;
        double minAve = (A[0] + A[1]) / 2.00;
        for(int i = 0; i < A.Length - 1; i ++)
        {
            int sum = A[i];
            for(int j = i + 1; j < A.Length; j ++)
            {
                if(j != i + 1 && minAve < A[j])   //在这里优化 如果后一个数小于当前平均数 则后面的平均值肯定不会更小 或者有其它更小的序列
                    break;                        //这里加上一句逻辑判断 效率提高很多 但是如何验证小逻辑的正确性？如何有更科学的优化？

                sum += A[j];
                double ave = sum / ( (j - i + 1) * 1.00);
                if(minAve > ave)
                {
                    minIndex = i;
                    minAve = ave;
                }
            }
        }
        return minIndex;
    }
}

MinAvgTwoSlice   这里的数学逻辑 如何验证正确？这个代码虽然100分，但是在数学验证上，有待啊。。。

class Solution {
    public int solution(int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int minIndex = 0;
        double minAve = (A[0] + A[1]) / 2.00;
        for(int i = 0; i < A.Length - 1; i ++)
        {
            int sum = A[i];
            for(int j = i + 1; j < A.Length; j ++)
            {
                if(j != i + 1 && minAve <= A[j])   //《= 差之毫厘 失之千里 
                    break;

                sum += A[j];
                double ave = sum / ( (j - i + 1) * 1.00);
                if(minAve > ave)
                {
                    minIndex = i;
                    minAve = ave;
                }
            }
        }
        return minIndex;
    }
}

//此处转换为数学问题，一目了然

 数组 ...a...bc...d...

if      ave(a...b)  <= ave(c...d)                                           c...d代表后面连续的1个或多个值

=》  ave(a...b)  <=  ave(a...d)

so 这种情况下 无论如何 ave(a...b)最小值都是成立的，不需要接着做下面的判断

if  ave(a...b)  > ave(c...d)

这种情况下 后面数组肯定会存在ave 小于当前ave的数列，不需要接着做下面的判断

=》此处可以break

用数学的方法证明时间复杂度为O(n)。。。 待



GenomicRangeQuery



标签：
相关文章