【LeetCode】﹝原地算法ி﹞数组、链表、二叉树相关题目

淩亂°似流年 2022-11-18 02:13 127阅读 0赞

## 【LeetCode】﹝原地算法ி﹞数组、链表、二叉树相关题目 ##

### 文章目录 ###

*   *  【LeetCode】﹝原地算法ி﹞数组、链表、二叉树相关题目
     *   *  奇偶链表★★
         *  矩阵置零★★
         *  删除有序数组中的重复项★
         *  
         *  删除有序数组中的重复项II★★
         *  二叉树展开为链表★★

### 奇偶链表★★ ###

[328. 奇偶链表][328.]

【**题目**】给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 `O(1)`，时间复杂度应为 `O(nodes)`，`nodes` 为节点总数。

**说明:**

*  应当保持奇数节点和偶数节点的相对顺序。
 *  链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

【**示例**】

输入: 1->2->3->4->5->NULL
    输出: 1->3->5->2->4->NULL

【**解题思路**】

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode oddEvenList(ListNode head) {
        
            if (head == null || head.next == null || head.next.next == null) {
        
                return head;
            }
            ListNode odd = head, even = head.next;
            ListNode node = head.next;
            while (odd.next != null && even.next != null) {
        
                odd.next = even.next;
                odd = odd.next;
                even.next = odd.next;
                even = even.next;
            }
            odd.next = node;
            return head;
        }
    }

--------------------

### 矩阵置零★★ ###

[73. 矩阵置零][73.]

【**题目**】给定一个 `m x n` 的矩阵，如果一个元素为 `0` ，则将其所在行和列的所有元素都设为 `0` 。请使用 **原地** 算法。

进阶：

一个直观的解决方案是使用 `O(mn)` 的额外空间，但这并不是一个好的解决方案。  
一个简单的改进方案是使用 `O(m + n)` 的额外空间，但这仍然不是最好的解决方案。  
你能想出一个仅使用常量空间的解决方案吗？

提示：

*  `m == matrix.length`
 *  `n == matrix[0].length`
 *  `1 <= m, n <= 200`
 *  `-231 <= matrix[i][j] <= 231 - 1`

【**示例**】

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
    输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

【**解题思路**】

class Solution {
        
        public void setZeroes(int[][] matrix) {
        
            int m = matrix.length, n = matrix[0].length;
            
            //判断第一行和第一列是否含有0
            boolean rowHaveZero = false;
            boolean colHaveZero = false;
            for(int i = 0; i < n; i++) {
        
                if(matrix[0][i] == 0) {
        
                    rowHaveZero = true;
                    break;
                }
            }
            for(int i = 0; i < m; i++) {
        
                if(matrix[i][0] == 0) {
        
                    colHaveZero = true;
                    break;
                }
            }
    
            //用第一行和第一列作为行列置为0的标记
            for(int i = 1; i < m; i++) {
        
                for(int j = 1; j < n; j++) {
        
                    if(matrix[i][j] == 0) {
        
                        matrix[i][0] = 0;
                        matrix[0][j] = 0;
                    }
                }
            }
    
            //将对应行置为0
            for(int i = 1; i < m; i++) {
        
                if(matrix[i][0] == 0) {
        
                    for(int j = 1; j < n; j++) {
        
                        matrix[i][j] = 0;
                    }
                }
            }
            //将对应列置为0
            for(int i = 1; i < n; i++) {
        
                if(matrix[0][i] == 0) {
        
                    for(int j = 1; j < m; j++) {
        
                        matrix[j][i] = 0;
                    }
                }
            }
    
            //若初始第一行和第一列有0则将其置为0
            if(rowHaveZero) {
        
                for(int i = 0; i < n; i++) {
        
                    matrix[0][i] = 0;
                }
            }
            if(colHaveZero) {
        
                for(int i = 0; i < m; i++) {
        
                    matrix[i][0] = 0;
                }
            }
        }
    }

--------------------

### 删除有序数组中的重复项★ ###

[26. 删除有序数组中的重复项][26.]

【**题目**】给你一个有序数组 `nums` ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 `O(1)` 额外空间的条件下完成。

**提示：**

*  `0 <= nums.length <= 3 * 104`
 *  `-104 <= nums[i] <= 104`
 *  `nums` 已按升序排列

【**示例**】

输入：nums = [0,0,1,1,1,2,2,3,3,4]
    输出：5, nums = [0,1,2,3,4]
    解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

【**解题思路**】

指针

class Solution {
        
        public int removeDuplicates(int[] nums) {
        
            if (nums == null) return 0;
            if (nums.length < 2) return nums.length;
            int i = 1, k = 1;
            while (i < nums.length) {
        
                if (nums[i] != nums[i - 1]) {
        
                    nums[k++] = nums[i];
                }
                i++;
            }
            i = k; 
            while (i < nums.length) {
        
                nums[i++] = 0;
            }
            return k;
        }
    }

--------------------

###  ###

### 删除有序数组中的重复项II★★ ###

[80. 删除有序数组中的重复项 II][80. _ II]

【**题目**】给你一个有序数组 `nums` ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 `O(1)` 额外空间的条件下完成。

**说明**：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

**提示：**

*  `0 <= nums.length <= 3 * 104`
 *  `-104 <= nums[i] <= 104`
 *  `nums` 已按升序排列

【**示例**】

输入：nums = [0,0,1,1,1,1,2,3,3]
    输出：7, nums = [0,0,1,1,2,3,3]
    解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

【**解题思路**】

class Solution {
        
        public int removeDuplicates(int[] nums) {
        
            if (nums == null || nums.length == 0) return 0;
            if (nums.length < 3) return nums.length;
            int le = 1, i = 1;
            int count = 1;
            while (i < nums.length) {
        
                if (nums[i] == nums[i - 1]) {
        
                    count++;
                } else {
        
                    count = 1;
                }
                if (count <= 2) {
        
                    nums[le++] = nums[i];
                }
                i++;
            }
            return le;
        }
    }

**简化版**

注意是`nums[j] != nums[j + 2]`，是向后比较，如果是向前比较（`nums[j] != nums[j - 2]`），此时前面的值已经更新了。

class Solution {
        
        public int removeDuplicates(int[] nums) {
        
            int i = 0;
            for (int j = 0; j < nums.length; j++) {
        
                if (j > nums.length - 3 || nums[j] != nums[j + 2]) {
        
                    nums[i++] = nums[j];
                }
            }
            return i;
        }
    }

--------------------

### 二叉树展开为链表★★ ###

[114. 二叉树展开为链表][114.]

【**题目**】给你二叉树的根结点 `root` ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 `TreeNode` ，其中 `right` 子指针指向链表中下一个结点，而左子指针始终为 `null` 。  
展开后的单链表应该与二叉树 先序遍历 顺序相同。

**提示**：

*  树中结点数在范围 `[0, 2000]` 内
 *  `-100 <= Node.val <= 100`

**进阶**：你可以使用原地算法（`O(1)` 额外空间）展开这棵树吗？

【**示例**】

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]

输入：root = []
    输出：[]
    -------------------------------------------
    输入：root = [1,2,5,3,4,null,6]
    输出：[1,null,2,null,3,null,4,null,5,null,6]

【**解题思路**】

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */

方法一：递归（逆后续遍历）

class Solution {
        
        TreeNode pre = null;
    
        public void flatten(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            flatten(root.right);
            flatten(root.left);
            root.left = null;
            root.right = pre;
            pre = root;
        }
    }

方法二：迭代

class Solution {
        
        public void flatten(TreeNode root) {
        
            while (root != null) {
        
                if (root.left != null) {
        
                    TreeNode lnode = root.left;
                    TreeNode rnode = root.right;
                    TreeNode node = lnode;
                    while (node.right != null) {
        
                        node = node.right;
                    }
                    node.right = rnode;
                    root.right = lnode;
                    root.left = null;
                }
                root = root.right;
            }
        }
    }

> 注：参考力扣热评

[328.]: https://leetcode-cn.com/problems/odd-even-linked-list/
[73.]: https://leetcode-cn.com/problems/set-matrix-zeroes/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/3a7b02f371f946d9bfc5fd7dc3ed8dd5.png
[26.]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
[80. _ II]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/
[114.]: https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/62d76b81781c4478b143fb11626cdb60.png