Array相关LeetCode题目笔记

11. 盛最多水的容器

  • 题目描述:

    给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
    
    说明:你不能倾斜容器。
    
     
    
    示例 1:
    
    
    
    输入:[1,8,6,2,5,4,8,3,7]
    输出:49 
    解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
    示例 2:
    
    输入:height = [1,1]
    输出:1
    示例 3:
    
    输入:height = [4,3,2,1,4]
    输出:16
    示例 4:
    
    输入:height = [1,2,1]
    输出:2
     
    
    提示:
    
    n = height.length
    2 <= n <= 3 * 104
    0 <= height[i] <= 3 * 104
    
    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/container-with-most-water
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
    
  • 解题思路:

    一看题,最原始的方法,双层for循环遍历到ok,时间复杂度应该是O(n^2)。看官方和大佬解题思路,soga,关于Array类型的题要考虑到双指针,上代码:
    
    class Solution {
        public int maxArea(int[] height) {
        //第一个指针,指向数组第一个数,也就是下标为0的数
            int left = 0;
            //第二个指针,指向数组最后一个数,为啥俩个指针要这样放嘞,因为这样他们的长度就是最长的,高度再论
            int right = height.length - 1;
            //假设最大面积为0,为啥嘞,防止height=[0]这样的数组出现
            int maxArea = 0;
            while (left < right) {//可以找出最大面积的条件
                {
                    int area = Math.min(height[right], height[left]) * (right - left);
                    maxArea = Math.max(maxArea, area);
                    if (height[right] >= height[left]) {//谁的高度低,移动谁的指针
                        ++left;
                    } else {
                        --right;
                    }
                }
            }
            return maxArea;
        }
    }
    时间复杂度:O(n),空间复杂度O(1)
    

283. 移动零

  • 题目描述:

    给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
    
    示例:
    
    输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]
    说明:
    
    必须在原数组上操作,不能拷贝额外的数组。
    尽量减少操作次数。
    
    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/move-zeroes
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
    
  • 解题思路:

    第一思路:循环,把非0的都循环出来放在另一个数组,最后再给它补上0。可实施。but人家不让拷贝额外的数组,删除它这个下标的元素?普通数组,初始化时大小就固定了,想念List,那就一个个移动下标,最坏从头移开始移动,时间复杂度O(n)。看题解,题解老哥脑回路niu
    class Solution {
        public void moveZeroes(int[] nums) {
            //之后用j来记录非0元素下标
            int j = 0;
            for(int i = 0;i < nums.length;i++){
                if(nums[i] != 0){//非0就记录它
                    nums[j++] = nums[i];//j++而不是++j是有原因的 这步等价于nums[j] = nums[i];j++
                }
            }
            //上面把非0的都移到前面了,开始补0操作,为啥不是i=j+1呢,因为上面的j++了
            for(int i = j;i < nums.length;i++){
                nums[i] = 0;
            }
        }
    }
    时间复杂度:O(n),空间复杂度O(1)
    

70. 爬楼梯

  • 题目描述:

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    
    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
    
    注意:给定 n 是一个正整数。
    
    示例 1:
    
    输入: 2
    输出: 2
    解释: 有两种方法可以爬到楼顶。
    1.  1 阶 + 1 阶
    2.  2 阶
    示例 2:
    
    输入: 3
    输出: 3
    解释: 有三种方法可以爬到楼顶。
    1.  1 阶 + 1 阶 + 1 阶
    2.  1 阶 + 2 阶
    3.  2 阶 + 1 阶
    
    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/climbing-stairs
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
    
  • 解题思路:

    第一思路:找规律
    1个台阶:1  1种
    2个台阶:1+1或2 2种
    3个台阶:1+1+1、2+1、1+2  3种
    4个台阶:1+1+1+1、2+1+1、1+2+1、1+2+1、2+2  5种
    好像是斐波拉基数列,那就是f(n) = f(n-1) + f(n-2),最差时间复杂度O(2^n),注定超时啊,看题解后自己理解了下
    class Solution {
        public int climbStairs(int n) {
            //只有1个台阶,直接返回1
            if (n == 1) {
                return 1;
            }
            //同上,直接返回2,为啥这么写,因为题目已经给出的
            if (n == 2) {
                return 2;
            }
            //为什么是n+1而不是n呢,因为此时的下标+1对应的才是台阶数,数组下标是从0开始的
            int[] dp = new int[n + 1];
            //1个台阶和2个台阶已知,为啥没有dp[0]呢,因为题目说明是正整数
            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i < n + 1; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }
    }
    

1. 两数之和

  • 题目描述:

    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。
    
    你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
    
    你可以按任意顺序返回答案。
    
    
    
    示例 1:
    
    输入:nums = [2,7,11,15], target = 9
    输出:[0,1]
    解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
    
    示例 2:
    
    输入:nums = [3,2,4], target = 6
    输出:[1,2]
    
    示例 3:
    
    输入:nums = [3,3], target = 6
    输出:[0,1]
    
    
    
    提示:
    
        2 <= nums.length <= 104
        -109 <= nums[i] <= 109
        -109 <= target <= 109
        只会存在一个有效答案
    
    进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?
    
  • 解题思路:

    第一思路:双层for循环
    class Solution {
        public int[] twoSum(int[] nums, int target) {
            int n = nums.length;
            for (int i = 0; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    if (nums[i] + nums[j] == target) {
                        return new int[]{i, j};
                    }
                }
            }
            return new int[0];
        }
    }
    时间复杂度:O(n^2)
    于是有了另一个idea
    class Solution {
        public int[] twoSum(int[] nums, int target) {
            Map<Integer,Integer> map = new HashMap<>();
            for(int i = 0;i < nums.length;i++){
                if(map.containsKey(target - nums[i])){
                    return new int[]{map.get(target-nums[i]),i};
                }
                map.put(nums[i],i);
            }
            return new int[0];
        }
    }
    利用hashmap的key不能重复,完美。事件复杂度O(n)
    

15. 三数之和

  • 题目描述:

    给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
    
    注意:答案中不可以包含重复的三元组。
    
    
    
    示例 1:
    
    输入:nums = [-1,0,1,2,-1,-4]
    输出:[[-1,-1,2],[-1,0,1]]
    
    示例 2:
    
    输入:nums = []
    输出:[]
    
    示例 3:
    
    输入:nums = [0]
    输出:[]
    
    
    
    提示:
    
        0 <= nums.length <= 3000
        -105 <= nums[i] <= 105
    
    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/3sum
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
    
  • 解题思路:

    考虑的太多,想着可以参考俩数之和来搞,但是还得去重。
    class Solution {
      public List<List<Integer>> threeSum(int[] nums) {
          List<List<Integer>> list = new ArrayList<>();
          int len = nums.length;
          //判断空数组和数组长度小于3的,这种数组根本不符合描述
          if(nums == null || len < 3){
              return list;
          }
          //排好序,方便后续比较
          Arrays.sort(nums);//事件复杂度O(NlogN)
          //事件复杂度O(N)
          for(int i = 0;i < len;i++){
              //因为是排好序的数组,target都大于0了,那left+right肯定大于0
              if(nums[i] > 0){
                  break;
              }
              //排除重复的
              if(i > 0 && nums[i] == nums[i - 1]){
                  continue;
              }
              int r = len - 1;
              int l = i + 1;
              while (l < r){
                  int sum = nums[i] + nums[r] + nums[l];
                  if(sum == 0){
                      list.add(Arrays.asList(nums[i],nums[r],nums[l]));
                      //还是判断重复
                      while (l < r && nums[r] == nums[r - 1]){
                          r--;
                      }
                      while(l < r && nums[l] == nums[l + 1]){
                          l++;
                      }
                      l++;
                      r--;
                  }
                  else if(sum > 0) {
                      r--;
                  }else {
                      l++;
                  }
              }
          }
          return list;
      }
    

}

Q.E.D.


一个热爱生活的95后精神小伙