Leetcode第227試合の週間試合の問題と解法

Leetcode第227週試合
1752.配列が並べ替えられ、回転して得られるかどうかを検査する

       `nums` 。`nums`      ，      `nums`   ，         。

   `nums`             （   0    ）  ，    `true` ；  ，   `false` 。

         **   ** 。

**  ：**      `A`     `x`               `B` ，      `A[i] == B[(i+x) % A.length]` ，   `%`      。

配列を前後に接続し、条件を満たすサブ配列があればtrue

を返す.

class Solution {
     
    public boolean check(int[] nums) {
     
        int len=nums.length;
        if(len==0||len==1)return true;
        int []source=new int[len*2];
        for(int i=0;i<len;i++){
     
            source[i]=nums[i];
        }
        for(int i=len,n=len*2;i<n;i++){
     
            source[i]=nums[i-len];
        }
        int start=0,end=1;
        while(end<len*2&&start-end!=len){
     
            for(;end<len*2;end++){
     
                if(source[end]<source[end-1])break;
            }
            
            if(end-start>=len)return true;
            start++;
            end=start+1;
        }
         if(end-start>=len)return true;
        return false;
    }
}

1753.石を除去した最大得点

          ，           `a`、`b`   `c`   **  **   。

          **      **        ，       `1`  。    **     **     ，    。

       `a` 、`b`   `c` ，        **    ** 。

貪欲なアルゴリズムは、毎回最も多い2つの山の中から

の値を取ります.

class Solution {
     
    public int maximumScore(int a, int b, int c) {
     
          int[]nums={
     a,b,c};
          Arrays.sort(nums);
          int zero=0;
          int count=0;
         for(int i=0;i<3;i++)
            if(nums[i]==0)
                zero++;
          while(zero<2){
     
              zero=0;
              nums[2]--;
              nums[1]--;
              count++;
              Arrays.sort(nums);
            for(int i=0;i<3;i++)
                if(nums[i]==0)
                 zero++;
          }
          return count;
    }
}

法則を探す

class Solution {
     
    public int maximumScore(int a, int b, int c) {
     
        if (a + b < c)
            return a + b;
        if (a + c < b)
            return a + c;
        if (b + c < a)
            return b + c;
        return (a + b + c) / 2; 
    }
}

1754.ディクショナリ順序の最大連結文字列を作成する

        word1   word2 。                 merge ：   word1   word2   ，              ：

	   word1   ，  word1            merge    ，     word1    。
  ，word1 = "abc"   merge = "dv" ，          ，word1 = "bc" ，   merge = "dva" 。
	   word2   ，  word2            merge    ，     word2    。
  ，word2 = "abc"   merge = "" ，          ，word2 = "bc" ，   merge = "a" 。
                      merge 。

           a   b        ，    a   b           ，a                 b        ，       a          b   。  ，"abcd"       "abcc"   ，                       ，  d              c   。

貪欲アルゴリズム解決,注意すべきは等しい場合

である.

class Solution {
     
    public String largestMerge(String w1, String w2) {
     
        char[] csa = w1.toCharArray(), csb = w2.toCharArray();
        int lena = csa.length, lenb = csb.length;
        char[] ans = new char[lena + lenb];
        int a = 0, b = 0, idx = 0;
        while(a < lena || b < lenb) {
     
            
            if(a >= lena) {
     
                ans[idx++] = csb[b++];
            } else if(b >= lenb) {
     
                ans[idx++] = csa[a++];
            } else if(csa[a] > csb[b]) {
     
                ans[idx++] = csa[a++];
            } else if(csa[a] < csb[b]) {
     
                ans[idx++] = csb[b++];                
            } else {
     
                //   
                if(look(w1.substring(a), w2.substring(b))) {
     
                    // a   b  
                    ans[idx++] = csa[a++];                    
                } else {
     
                    // b       
                    ans[idx++] = csb[b++];
                }
            }
        }
        
        return new String(ans);
    }
    
    public boolean look(String a, String b){
     
        return a.compareTo(b) > 0;
    }
    
}
 

1755.最も目標値に近いサブシーケンスと

         `nums`        `goal` 。

     `nums`         ，            `goal` 。    ，          `sum` ，    **      ** `abs(sum - goal)` 。

   `abs(sum - goal)`     **   ** 。

  ，                     （      ）      。

 

元の配列を左右の2つの配列に分割し、この2つの配列のすべてのサブシーケンスの和をそれぞれ計算します.上記とを並べ替えて、1つは小さいから大きいまで、1つは大きいから小さいまで、それから2つの配列を2つのポインタで遍歴して、答えを更新すればいいです.

class Solution {
     
    static int lower_bound(int[] g, int target) {
     
        /**
         * g   ≥target         [l,r)
         * */
        int l = 0, r = g.length;
        //if(target>g[r-1])return r;
        while (l + 1 < r) {
     
            int mid = l + (r - 1 - l) / 2;
            if (g[mid] < target) {
     
                l = mid + 1;
            } else if (g[mid] >= target) {
     
                r = mid + 1;
            }
        }
        return l;
    }

    public int minAbsDifference(int[] nums, int goal) {
     
        int n = nums.length;
        int n1 = (n + 1) / 2, n2 = n - n1;
        int[] f1 = new int[(1 << n1)], f2 = new int[(1 << n2)];
        for (int i = 0; i < (1 << n1); ++i) {
            //        
            for (int j = 0; j < n1; ++j) {
     
                if (((i >> j) & 1) == 1) {
     
                    f1[i] += nums[j];
                }
            }
        }
        for (int i = 0; i < (1 << n2); ++i) {
            //        
            for (int j = 0; j < n2; ++j) {
     
                if (((i >> j) & 1) == 1) {
     
                    f2[i] += nums[n1 + j];
                }
            }
        }
        Arrays.sort(f2);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < f1.length; ++i) {
            //  f1
            int target = goal - f1[i];
            int index = lower_bound(f2, target);    //    f2
            if (index < f2.length) {
     
                ans = min(ans, abs(f1[i] + f2[index] - goal));
            }
            if (index - 1 >= 0) {
     
                ans = min(ans, abs(f1[i] + f2[index - 1] - goal));
            }
        }
        return ans;
    }
}
 

    ：  （LeetCode）
  ：https://leetcode-cn.com/

ブログへようこそ:http://wy313.top/