文章/答案/技术大牛

发布

社区首页 >专栏 >链表问题

链表问题

原创

大学里的混子

修改于 2019-04-08 02:56:09

48700

代码可运行

文章被收录于专栏：LeetCodeLeetCode

运行总次数：0

代码可运行

链表问题

一、next指针的赋值方法

二、链表反转

 public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null ) return head; 
        ListNode cur = head;
        ListNode next = null;
        ListNode pre = null;
           
        while(cur != null){
             next = cur.next;
             cur.next = pre;
             pre = cur;
             cur = next;
        }
        return pre;
    }

三、链表的复制问题

 public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead == null) return pHead;
        RandomListNode cur = pHead;
        RandomListNode next = null;
        
        while( cur != null){
            next = cur.next;
            cur.next = new RandomListNode(cur.label);
            cur.next.next = next;
            cur = next;
        }
        cur = pHead;
        RandomListNode copyNode = null; 
        
        while(cur != null){
            next = cur.next.next;
            copyNode = cur.next;
            copyNode.random = cur.random != null ? cur.random.next : null;
            cur = next; 
        }
        
        cur = pHead;
        RandomListNode res = cur.next;
        copyNode = cur.next;
        while(cur != null){
            next = cur.next.next;
            copyNode = cur.next;
            copyNode.next = next!= null? next.next :  null;
            cur.next = next;
            cur = next;
        }
        return res;
    }

24.Swap Nodes in Pairs

 public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        
        ListNode pre = new ListNode(0);
        ListNode dummy = pre;
        pre.next = head;
        ListNode next1 = null;
        ListNode next2 = null;
        ListNode next3 = null;
        while(pre.next != null && pre.next.next != null){
            next1 = pre.next;
            next2 = next1.next;
            next3 = next2.next;
            pre.next = next2;
            next2.next = next1;
            next1.next = next3;
            pre = next1;
        }
        return dummy.next;
    }

贪心算法

455.Assign Cookies

    public int findContentChildren(int[] g, int[] s) {
        // [1,2,3], [1,1]
        // child    cookies          
        // [1,2], [1,2,3]
        // child    cookies
        Arrays.sort(s);
        Arrays.sort(g);
        int res = 0;
        int index = 0;
        int i = 0;
        while(i < g.length && index < s.length){
            if(g[i] <= s[index]){
                res++;
                i++;
            }
            index++;
        } 
        return res;
    }

435.Non-overlapping Intervals

 
    class myComparator implements Comparator<Interval>{
        @Override
        public int compare(Interval arr1, Interval arr2){
            return arr1.end - arr2.end;
        }
    }
    
    public int eraseOverlapIntervals(Interval[] intervals) {
        if(intervals == null || intervals.length < 2) return 0;
        Arrays.sort(intervals, new myComparator());
        int count = 1;
        int preEnd = intervals[0].end;
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i].start < preEnd){
                continue;
            }
            preEnd = intervals[i].end;
            count++;
        }
        return intervals.length - count;
        
    }

452.Minimum Number of Arrows to Burst Balloons

    class myCom implements Comparator<int []>{
        @Override
        public int compare(int [] arr1, int[] arr2){
            return arr1[1] - arr2[1];
        }
    }
    
    public int findMinArrowShots(int[][] points) {
        if(points == null || points.length == 0) return 0;
        Arrays.sort(points, new myCom());
        int count = 1;
        int preEnd = points[0][1];
        for(int i = 1; i < points.length; i++){
            if(preEnd >= points[i][0]){
                continue;
            }
            count++;
            preEnd = points[i][1];
        }
        return count;
    }

406.Queue Reconstruction by Height(根据身高和序号重组队列)

身高降序，k增序

    public int[][] reconstructQueue(int[][] people) {
        if(people == null) return people;
        Arrays.sort(people, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
        List<int[]> queue = new ArrayList<>();
        for(int[] p : people){
            queue.add(p[1],p); // add(index, object);
        }
        return queue.toArray(new int[queue.size()][]);        
    }

763.Partition Labels（分隔字符串使同种字符出现在一起）

A stringSof lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

    public List<Integer> partitionLabels(String S) {
        List<Integer> list = new LinkedList<>();
        char[] chars = S.toCharArray();
        int[] index = new int[26];
        for(int i = 0; i < chars.length; i++){
            index[chars[i] - 'a'] = i;
        }
        int lastIndex = 0;   
        int j = 0;    
        for(int i = 0; i < chars.length; i++){
            j = Math.max(index[chars[i] - 'a'], j);
            if(i == j) {
                list.add(j - lastIndex + 1);
                j = j + 1;
                lastIndex = j;
            }
        }
        return list;
    }

605.Can Place Flowers

题目描述：花朵之间至少需要一个单位的间隔，求解是否能种下 n 朵花。

   public boolean canPlaceFlowers(int[] arr, int n) {
        int pre  = 0;
        int next = arr.length -1;
        int count= 0;
        for(int i = 0; i < arr.length; i++){
            if(arr[i] == 1) continue;
            pre = i == 0 ? 0 : arr[i - 1];
            next = i == arr.length - 1 ? 0 : arr[i + 1];
            if(pre == 0 && next == 0){
                count++;
                arr[i] = 1;
            } 
        }
        return count >= n;   
    }

665.Non-decreasing Array

题目描述：判断一个数组能不能只修改一个数就成为非递减数组。

在出现 nums[i] < nums[i - 1] 时，需要考虑的是应该修改数组的哪个数，使得本次修改能使 i 之前的数组成为非递减数组，并且 不影响后续的操作 。优先考虑令 nums[i - 1] = nums[i]，因为如果修改 nums[i] = nums[i - 1] 的话，那么 nums[i] 这个数会变大，就有可能比 nums[i + 1] 大，从而影响了后续操作。还有一个比较特别的情况就是 nums[i] < nums[i - 2]，只修改 nums[i - 1] = nums[i] 不能使数组成为非递减数组，只能修改 nums[i] = nums[i - 1]。

    public boolean checkPossibility(int[] nums) {
        if(nums == null) return false;
        int count = 0;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] >= nums[i - 1]){
                continue;
            }
            count++;
            if( i - 2 >= 0 && nums[i - 2] > nums[i]){
                nums[i] = nums[i -1]; 
            }else{
                nums[i -1] = nums[i];
            }
        }
        
        return count <= 1;
    }

动态规划

198.House Robber

    public int rob(int[] nums) {
        if(nums == null || nums.length < 1) return 0;
       // pre1 pre2 cur
        int pre1 = 0;
        int pre2 = 0;
        int cur = 0;
        for(int i = 0; i < nums.length; i++){
            cur = Math.max(pre1 + nums[i], pre2);
            pre1 = pre2;
            pre2 = cur;
        }      
        return cur;
    }

213.House Robber II

    public int rob(int[] nums) {
        if(nums == null || nums.length < 1) return 0;
        if(nums.length < 2) return nums[0];
        return Math.max(rob(nums, 0, nums.length - 2) , rob(nums, 1, nums.length - 1));
    }
    
    private static int rob(int[] nums, int start, int end){
//         pre1  pre2 cur
        int pre1 = 0;
        int pre2 = 0;
        int cur = 0;
        for(int i = start; i <= end; i++){
            cur = Math.max(pre1 + nums[i], pre2);
            pre1 = pre2;
            pre2 = cur;
        }
        return cur;
    }

413.Arithmetic Slices

dp[i] 表示以 A[i] 为结尾的等差递增子区间的个数。

在 A[i] - A[i - 1] == A[i - 1] - A[i - 2] 的条件下，{A[i - 2], A[i - 1], A[i]} 是一个等差递增子区间。如果 {A[i - 3], A[i - 2], A[i - 1]} 是一个等差递增子区间，那么 {A[i - 3], A[i - 2], A[i - 1], A[i]} 也是等差递增子区间，dp[i] = dp[i-1] + 1。

    public int numberOfArithmeticSlices(int[] A) {
        if(A == null || A.length < 3) return 0;
        int[] dp = new int[A.length];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i < A.length; i++){
            if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]){
                dp[i] = dp[i - 1] + 1;
            }
        }
        int total = 0;
        for(int i = 0; i < dp.length; i++){
            total += dp[i];
        }
        return total;
    }

343.Integer Break

  public int integerBreak(int n) {
            if(n <= 0) return 0;
            // dp[i] = max(dp[i], j * dp[i - j], j *(i - j)) 
            int[] dp = new int[n + 1];
            dp[1] = 1;
            for(int i = 2; i <= n; i++){
                for(int j = 1; j < i; j++){
                    dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j *(i - j)));
                }
            }
            return dp[n];
        }

300.Longest Increasing Subsequence

dp[i] = dp[j] + 1 ( j < i && arr[j] < arr[i])

 	public int lengthOfLIS(int[] arr) {
        if(arr == null || arr.length < 1) return 0;
        // dp[i] = dp[j] + 1  (  j < i &&  arr[j] < arr[i])
        int[] dp = new int[arr.length];
        for(int i = 0; i < arr.length; i++){
           dp[i] = 1; 
           for(int j = 0; j < i; j++){
               if(arr[j] < arr[i]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);                 
               }               
           }
        }    
        int res = dp[0];
        for(int i = 0; i < dp.length; i++){
            if(res < dp[i]) res = dp[i];
        }
        return res;
    }

一组整数对能够构成的最长链

    public int findLongestChain(int[][] pairs) {
        if(pairs == null || pairs.length < 1 || pairs[0].length < 1) return 0;
        Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
        int n = pairs.length;
        int [] dp = new int[n];
        int res = 0;
        for(int i = 0; i < pairs.length; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(pairs[i][0] > pairs[j][1]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            } 
            res = Math.max(res, dp[i]);
        }
        return res;
    }

376.Wiggle Subsequence

    public int wiggleMaxLength(int[] nums) {
        if(nums == null || nums.length < 1) return 0;
        int up = 1;
        int down = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > nums[i-1]){
                up = down + 1;
            }else if(nums[i] < nums[i - 1]){
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }

0-1 背包

有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。

定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：

第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。
第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w] + v。

第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：

public int knapsack(int W, int N, int[] weights, int[] values) {
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = 1; j <= W; j++) {
            if (j >= w) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[N][W];
}

230.Kth Smallest Element in a BST

 public int kthSmallest(TreeNode root, int k) {
        int[] m = new int[2];
        m[0] = k;
        helper(root, m);
        return m[1];
    }

    public void helper(TreeNode root, int[] k){
        if(root == null || k[0] < 0) return;
        helper(root.left, k);
        k[0]--;
        if(k[0] == 0) {
            k[1] = root.val;
            return;
        }
        helper(root.right, k);
    }