Участник:Rublev.mv

Материал из DISCOPAL
Перейти к: навигация, поиск

Рублев Максим Владимирович М05-906а

1) https://leetcode.com/problems/wiggle-subsequence/

 
class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums == null || nums.length==0)
        return 0;
    if(nums.length<2){
        return nums.length;
    }    
    int count=1;
    for(int i=1, j=0; i<nums.length; j=i, i++){
        if(nums[j]<nums[i]){
            count++;
            while(i<nums.length-1 && nums[i]<=nums[i+1]){
                i++;
            }
        }else if(nums[j]>nums[i]){
            count++;
            while(i<nums.length-1 && nums[i]>=nums[i+1]){
                i++;
            }
        }
    }
 
    return count;
 
    }
}


2) https://leetcode.com/problems/soup-servings/

 
class Solution {
    public double soupServings(int N) {
      Double[][] arr=new Double[N+1][N+1]; 
      return soup_serv(N, N, arr);  
    }
 
     public double soup_serv(int A, int B, Double[][] arr) {
        if (A <= 0 && B <= 0) return 0.5;     
        if (A <= 0) return 1.0;               
        if (B <= 0) return 0.0;               
        if (arr[A][B] != null) {
            return arr[A][B];
        }
        int[] arrA = {100, 75, 50, 25};
        int[] arrB = {0, 25, 50, 75};
        arr[A][B] = 0.0;
        for (int i = 0; i < 4; i++) {
            arr[A][B] += soup_serv(A - arrA[i], B - arrB[i], arr);
        }
        return arr[A][B] *= 0.25;
    } 
}
 

3) https://leetcode.com/problems/knight-dialer/

 
class Solution {
 public int knightDialer(int n) {
     int res=0;
     int sum_vect=0;
     int[][] hodi = { {1}, {0, 2}, {0, 1, 3, 4}, {2, 4}, { 0 } };
     int[] vect = { 1, 1, 1, 1, 1 };
  while ((n-2) > 0) {
    int[] vect1 = { 0, 0, 0, 0, 0 };
    for (int i = 0; i < 5; ++i) {
      for (int j : hodi[i])
        vect1[j] = (vect1[j] + vect[i]) % 1000000007;
    }
    vect = vect1;
  }
     sum_vect=vect[0] + vect[1] + vect[2] + vect[3] + vect[4];
     res=(int)(sum_vect % 1000000007);
   return res;
 }
}
 

4) https://leetcode.com/problems/longest-turbulent-subarray/

 
class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n=arr.length;
 
        if(n==1) return 1;
        int maximum = 0;
        int[] arr1 = new int[n];
 
        for(int i=0; i<n-1; i++){
            arr1[i]=Integer.compare(arr[i], arr[i+1]);
        }
 
        int m=arr1.length;
 
        for(int i=1, q=arr1[i]!=0?1:0; i<m; i++){
            if(arr1[i]==0){
                q=0;
                continue;
            }
 
            if ((arr1[i]+arr1[i-1])==0){
                q++;
            }else{
                q=1;
            }
 
            maximum = Integer.max(q, maximum);
        }
 
        return maximum+1;
    }
}
 

5) https://leetcode.com/problems/largest-sum-of-averages/

 
class Solution {
  public double largestSumOfAverages(int[] A, int K) {   
    int[] s = new int[A.length];
    s[0]=A[0];
    for (int i = 1; i < A.length; i++) {          
        s[i] = A[i] + s[i - 1];
    }
    return lsa(A, K, s, A.length, 0);
  }
  public double lsa(int[] A, int K, int[] s, int r, int l) {
    if (K == 1) {
       return ((double) (s[r - 1] - s[l] + A[l]) / (r- l));
    }
    double res=0.0;
    double tmp=0.0;
    for (int ind = l; ind + K <= r; ind++) {
    tmp= ((double) (s[ind] - s[l] + A[l]) / (ind - l + 1));   
    res = Math.max(res,tmp + lsa(A, K-1, s, r,ind+1));
    }
    return res;
 
    }
}
 

6)https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/

 
class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int n=s1.length();
        int m=s2.length();
        int len1 = 0;
        int len2 = 0;
 
        int[][] arr = new int[n+1][m+1];
        for(int i=1; i<=n; i++){
            arr[i][0] = arr[i-1][0] + (int)s1.charAt(i-1);
        }
        for(int j=1; j<=m; j++){
            arr[0][j] =arr[0][j-1] + (int)s2.charAt(j-1);
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    arr[i][j] = arr[i-1][j-1];
                } else {
                    len1 = (int)s1.charAt(i-1);
                    len2 = (int)s2.charAt(j-1);
                    arr[i][j] = Math.min(arr[i-1][j]+len1, arr[i][j-1]+len2);
                    arr[i][j] = Math.min(arr[i][j], arr[i-1][j-1]+len1+len2);
                }
            }
        }
        return arr[n][m];
    } 
 
}
 

7)https://leetcode.com/problems/minimum-cost-for-tickets/

 
import java.util.HashSet;
import java.util.Set;
 
class Solution {
 
    public int mincostTickets(int[] days, int[] costs) {
        int count_day=366;
        int[] min_price = new int[count_day];
        Set<Integer> Days = new HashSet<>();
 
        for(int day : days){
            Days.add(day);
        }
 
        for(int i = 1; i<count_day; i++){
            if(Days.contains(i)){
                int min = Math.min(min_price[Math.max(0,i-1)]+costs[0],
                                   min_price[Math.max(0,i-7)]+costs[1]);
                min_price[i]=Math.min(min, min_price[Math.max(0,i-30)]+costs[2]);
            }else {
                min_price[i]=min_price[i-1];
            }
        }
        return min_price[count_day-1];
    }
}