贪心算法 day07

1.最优除法

链接：. - 力扣（LeetCode）

题目思路： 

代码：

class Solution {
     public  static   String optimalDivision(int[] nums) {
        int n = nums.length;
        StringBuffer st = new StringBuffer();
        if(n == 1){
            return st.append(nums[0]).toString();
        }
        if(n == 2){
            return (st.append(nums[0]).append("/").append(nums[1])).toString();
        }
        st.append(nums[0]+"/"+"(");
        for (int i = 1; i < n; i++) {
            if(i == n - 1){
                st.append(nums[n - 1]+")");
            }else{
                st.append(nums[i]+"/");
            }



        }
        return st.toString();
    }
}

2.跳跃游戏 II

链接：. - 力扣（LeetCode）

思路： 

代码：

    public static int jump(int[] nums) {
      int left = 0,right = 0,ret = 0,maxPos = 0,n = nums.length;
      while(left <= right){
          if(maxPos >= n - 1){
              return ret;
          }
          for(int i = left;i <= right;i++){
              maxPos = Math.max(maxPos,nums[i]+i);
          }
          left = right + 1;
          right = maxPos;
          ret++;
      }
      return -1;
    }

3.跳跃游戏1

链接：. - 力扣（LeetCode）

思路：和上一题差不多，只是当无法到达最后一下标时left会大于right无法进入循环返回false

class Solution {
    public boolean canJump(int[] nums) {
      int left = 0,right = 0,maxPos = 0,n = nums.length;
      while(left <= right){
          if(maxPos >= n - 1){
              return true;
          }
          for(int i = left; i <= right;i++){
              maxPos = Math.max(maxPos,nums[i]+i);
          }
          left = right + 1;
          right = maxPos;
      }
      return false;
    }

}