leetcode 数组，链表，跳表

2020-04-27 本文已影响0人韩who

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

方法一： loop的时候,统计0的个数，有0就移动数组，最后，将在数组后面补0

方法二：直接弄一个新的数组，一旦有非0的数，就把数放入新数组中，同时统计0的个数

方法三：在数组中进行交换，有一个指针j指向放非0数的位置，遍历数组，一旦有非0的数就与i交换

//第三种
class Solution {
   public void moveZeroes(int[] nums) {
         int j = 0;//记录要放非0数的位置
         for(int i=0; i< nums.length; i++){
             //非0情况，与到0就继续循环
             if(nums[i]!=0){
                 nums[j] = nums[i];
                 if(i!=j){
                     //交换后，需要把值替换为0
                     nums[i] = 0;
                 }
                 j++;
             }
         }
    }
}

class Solution {
   public void moveZeroes(int[] nums) {
       for(int i =0; i< nums.length-1; i++){
           for(int j = i+1; j < nums.length; j++){
               if(nums[i]==0 && nums[j] !=0){
                    nums[i] = nums[j];
                    nums[j] = 0;
               }
           }
       }
   }

}

11. 盛最多水的容器

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

image

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

方法一：暴力法，两层循环解决

方法二：两边夹逼，每次把最左以及最右中比较矮的棒子向内移动移动，

暴力法

此处可以总结一个遍历数组的常见方法

   for(int i=0; i<height.length-1; i++){
      for(int j=i+1; j<height.length;j++ ){     
    }   
}

//暴力   
public int maxArea(int[] height) {
         int area  = 0;
         for(int i=0; i<height.length-1; i++){
             for(int j=i+1; j<height.length;j++ ){
                 //  找出面积最大的即可
                 int temp = (j-i)*Math.min(height[j],height[i]);
                  area =Math.max(temp,area);
             }
         }
         return area;
     }

此处可以总结一个数组左右指针逼近的框架

//其中一种 
for(int i=0, j=len;  i<j;){
    
    //i与j在循环里面判断是否加或者减
      i++;
      j--;
  }


//另一种方式
int i =0;
int j = len;
whiel(i<j){
    i++;
    j--
}

  //夹逼法
  public int maxArea(int[] a) {
        int max  = 0;
        for(int i=0, j=a.length-1;  i<j;){
            //面积最大，则需要把矮一点的棒子挪动
             int minheight = a[i] < a[j] ?a[i++] : a[j--];
             max = Math.max(max,(j-i+1)*minheight); 
        }
        return max;

    }

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶
2 阶
示例 2：

输入： 3
输出： 3
解释：有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

斐波那契是有两种方式，

一种是自顶向下（递归），有递归栈的内存消耗，

一种是自底向上（循环实现），占用内存少，

这道题使用递归实现，但是超时,使用 dp[] 进行对数据的临时存储，还是内存不足

    public int climbStairs(int n) {
        int[] dp = new int[n+2];
        dp[1] = 1;
        dp[2] = 2;
        return chk(n,dp);
    }

    public int chk(int n , int[] dp){
       if(n==1 || n==2){
            return n;
        }
        else{
            dp[n] = chk(n-1,dp)+chk(n-2,dp);
            return dp[n];
        }

    }

使用自底向上的方法

   public int climbStairs(int n) {
        if(n==1 || n==2){
            return n;
        }
        int f1=1,f2=2,f3=3;
        for(int i=3; i<=n;i++){
            f3 = f1+f2;
            f1 = f2;       
            f2 = f3;
            
        }
           return f3;
   }

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

暴力，三重循环，没有去重，记住搜索数组框架

   public List<List<Integer>> threeSum(int[] nums) {
        ArrayList<List<Integer>> list = new ArrayList();
        for(int i=0; i<nums.length-2; i++){
            for(int  j = i+1; j< nums.length-1; j++){
                for(int k=j+1; k<nums.length;k++){
                    if (nums[i]+nums[j] + nums[k] == 0) {
                         ArrayList<Integer> li  = new ArrayList();
                         li.add(nums[i]);
                         li.add(nums[j]);
                         li.add(nums[k]);
                         list.add(li);
                    }
                }

            }
        }
        return list;

    }

排序后，使用双指针进行扫描以及去重

/**
     * 双指针方法，左右指针扫描
     * @param nums
     * @return
     */
   class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            ArrayList<List<Integer>> list = new ArrayList();
             if(nums == null || nums.length < 3) return list;

            Arrays.sort(nums);
            for(int i = 0; i< nums.length-2; i++){
              
                if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
                 if(i > 0 && nums[i] == nums[i-1]) continue; // 去重

                int left = i+1, right = nums.length-1;
                while(left < right){
                    int sum = nums[i] + nums[left] + nums[right];
                    if(sum==0){
                        ArrayList<Integer> li = new ArrayList();
                        li.add(nums[i]); li.add(nums[left]);li.add(nums[right]);
                        list.add(li);
                        left++;right--; 
                        //去重
                        while(nums[left] == nums[left-1] && left < right) left++;
                        while(nums[right] ==nums[right+1] && left < right) right--;

                         

                        

                    }
                    if(sum<0){
                        left++;
                    }
                    if(sum>0){
                        right--;
                    }
                }
               

            }
            return list;


        }
    }

141. 环形链表

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

image

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

image

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

image

快慢指针，一个走在前面，一个走在后面

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null || head.next==null) return false;
        ListNode low = head;
        ListNode fast = head.next;
        while(low!=fast){
            if(low==null || fast==null || fast.next==null){
                return false;
            }
            low =  low.next; 
            fast = fast.next.next;
            
        }
        return true;
        
    }
}