LeetCode100 数组|189. 轮转数组 238. 除自身以外数组的乘积

189. 轮转数组

题目： 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

题目链接： 189. 轮转数组
解题思路及代码：

空间o(1) 超时

class Solution {
  //超时
    public void rotate(int[] nums, int k) {
      System.out.println(nums.length);
      if(k<=nums.length/2){
        int temp;
        while(k>0){
            temp=nums[nums.length-1];
            for(int i=nums.length-1;i>0;i--){
                nums[i]=nums[i-1];
            }
            nums[0]=temp;
            k--;
        }
      }else{
        int temp;
        int count=nums.length-k;
        while(count>0){
          temp=nums[0];
          for(int i=0;i<nums.length-1;i++){
            nums[i]=nums[i+1];
          }
          nums[nums.length-1]=temp;
          count--;
        }
      }
        
    }
}

需通过两次翻转达到效果
当 nums=[1,2,3,4,5,6,7] k=3 时
1.翻转所有 nums=[7,6,5,4,3,2,1]
2.翻转 0到k nums=[5，6，7，4,3,2,1]
3.翻转 k到nums.length-1 nums [5,6,7,1,2,3,4]

class Solution {
    public void rotate(int[] nums, int k) {
      k=k%nums.length;//这里可能被反复翻转 但每翻转num.length次结果都一样
      reverseArray(nums,0,nums.length-1);
      reverseArray(nums,0,k-1);
      reverseArray(nums,k,nums.length-1);
        
    }
    public void reverseArray(int nums[],int begin,int end){
      int temp;
      while(begin<end){
          temp=nums[begin];
          nums[begin]=nums[end];
          nums[end]=temp;
          end--;
          begin++;
      }

    }
    //两次翻转

}

238. 除自身以外数组的乘积-前缀积

题目：给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

题目链接： 238. 除自身以外数组的乘积

class Solution {
    //前缀乘积*后缀乘积
    public int[] productExceptSelf(int[] nums) {
        int[] resultArray=new int[nums.length];
        int[] left=new int[nums.length];
        int[] right=new int[nums.length];
        Arrays.fill(left, 1);
        Arrays.fill(right,1);
        int result=1;
        for(int i=1;i<nums.length;i++){
          result=result*nums[i-1];
          left[i]=result;
        }
        result=1;
        for(int i=nums.length-2;i>=0;i--){
          result=result*nums[i+1];
          right[i]=result;
        }
         for(int i=0;i<nums.length;i++){
            resultArray[i]=right[i]*left[i];
         }
         return resultArray;
    }

}