HOT100-简单题3道

linwt · linwt · commit 3eafc4abca1c · 2022-02-08T20:29:14.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -16,5 +16,8 @@
 145. 二叉树的后序遍历
 155. 最小栈
 160. 相交链表
+169. 多数元素
+206. 反转链表
 226. 翻转二叉树
+234. 回文链表
 589. N叉树的前序遍历
diff --git a/leetcode_Java/Solution0169.java b/leetcode_Java/Solution0169.java
@@ -0,0 +1,121 @@
+// 多数元素
+
+
+/*
+排序：先排序，不管元素个数是奇数还是偶数，众数元素一定在中间位置
+ */
+class Solution {
+    public int majorityElement(int[] nums) {
+        Arrays.sort(nums);
+        return nums[nums.length/2];
+    }
+}
+
+
+/*
+哈希表：使用哈希表存放每个元素的出现次数，遍历哈希表获取出现次数最多的元素
+ */
+class Solution {
+    public int majorityElement(int[] nums) {
+        HashMap<Integer, Integer> map = new HashMap<>();
+        for (int num : nums) {
+            int count = map.getOrDefault(num, 0);
+            map.put(num, ++count);
+        }
+        int res = nums[0];
+        int maxCount = 0;
+        for (int num : map.keySet()) {
+            if (map.get(num) > maxCount) {
+                maxCount = map.get(num);
+                res = num;
+            }
+        }
+        return res;
+    }
+}
+
+
+/*
+投票：
+res表示临时众数，count表示该临时众数拥有的票数
+遍历数组，票数为0时，替换上一届的临时众数，将当前元素设为临时众数
+计算票数，如果当前元素与临时众数一样，则投赞成票，否则投反对票
+由于实际众数人多力量大，最后赞成票最多
+ */
+class Solution {
+    public int majorityElement(int[] nums) {
+        int res = nums[0];
+        int count = 0;
+        for (int num : nums) {
+            if (count == 0) {
+                res = num;
+            }
+            count += num == res ? 1 : -1;
+        }
+        return res;
+    }
+}
+
+
+/*
+计数：遍历数组元素，统计该元素出现次数，如果大于一半数组长度，则为众数
+ */
+class Solution {
+    public int majorityElement(int[] nums) {
+        int maxCount = nums.length / 2;
+        int res = nums[0];
+        for (int num : nums) {
+            if (count(nums, num) > maxCount) {
+                res = num;
+                break;
+            }
+        }
+        return res;
+    }
+
+    private int count(int[] nums, int num) {
+        int count = 0;
+        for (int i = 0; i < nums.length; i++) {
+            if (nums[i] == num) {
+                count++;
+            }
+        }
+        return count;
+    }
+}
+
+
+/*
+分治：数组对半拆分成多部分，两两统计比较谁出现次数更多，最后得到出现次数最多的众数
+ */
+class Solution {
+    public int majorityElement(int[] nums) {
+        return majorityElementRec(nums, 0, nums.length - 1);
+    }
+
+    private int majorityElementRec(int[] nums, int low, int high) {
+        if (low == high) {
+            return nums[low];
+        }
+        int mid = (high - low) / 2 + low;
+        int left = majorityElementRec(nums, low, mid);
+        int right = majorityElementRec(nums, mid + 1, high);
+        if (left == right) {
+            return left;
+        }
+        int leftCount = countInRange(nums, left, low, high);
+        int rightCount = countInRange(nums, right, low, high);
+        return leftCount > rightCount ? left : right;
+    }
+
+    private int countInRange(int[] nums, int num, int low, int high) {
+        int count = 0;
+        for (int i = low; i <= high; i++) {
+            if (nums[i] == num) {
+                count++;
+            }
+        }
+        return count;
+    }
+
+}
diff --git a/leetcode_Java/Solution0206.java b/leetcode_Java/Solution0206.java
@@ -0,0 +1,123 @@
+// 反转链表
+
+
+/**
+ * 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 reverseList(ListNode head) {
+        ListNode before = null, after;
+        while (head != null) {
+            after = head.next;
+            head.next = before;
+            before = head;
+            head = after;
+        }
+        return before;
+    }
+}
+
+
+/*
+递归：
+1、终止条件：节点为空 或 节点的下一节点为空
+2、方法功能：改变指针方向，返回新的头节点
+3、递归思路：
+   1）递归传入下一个节点，目的是为了到达最后一个节点，从尾到头改变链表节点连接的指针方向
+   2）原先 A → B，改变指针方向，变成 A ← B。 即使B指向A，断开A指向B
+   3）继续向上一层传递头节点，用于最终返回结果
+ */
+class Solution {
+    public ListNode reverseList(ListNode head) {
+        if (head == null || head.next == null) {
+            return head;
+        }
+        ListNode root = reverseList(head.next);
+        head.next.next = head;
+        head.next = null;
+        return root;
+    }
+}
+
+
+/*
+创建新链表：
+1、不改变原链表指针方向，遍历链表节点时，根据节点值创建新的节点，并赋值下一个节点的引用
+2、root表示新链表的头指针，新节点创建完成后，root指针指向新节点，继续创建和连接节点
+ */
+class Solution {
+    public ListNode reverseList(ListNode head) {
+        ListNode root = null;
+        for (; head != null; head = head.next) {
+            root = new ListNode(head.val, root);
+        }
+        return root;
+    }
+}
+
+
+/*
+逻辑同上，使用while替换for
+ */
+class Solution {
+    public ListNode reverseList(ListNode head) {
+        ListNode root = null;
+        while (head != null) {
+            root = new ListNode(head.val, root);
+            head = head.next;
+        }
+        return root;
+    }
+}
+
+
+/*
+栈：根据栈后进先出的特点，使用栈存放链表节点，弹出节点时改变节点的下一节点引用
+ */
+class Solution {
+    public ListNode reverseList(ListNode head) {
+        Stack<ListNode> stack = new Stack<>();
+        ListNode root = new ListNode(0);
+        ListNode temp = root;
+        while (head != null) {
+            stack.push(head);
+            head = head.next;
+        }
+        while (!stack.isEmpty()) {
+            temp.next = stack.pop();
+            temp = temp.next;
+        }
+        temp.next = null;
+        return root.next;
+    }
+}
+
+
+/*
+插入：遍历节点，将节点拿出来重新构造新的链表，每次节点都插入到新链表的头部，最终实现反转链表
+ */
+class Solution {
+    public ListNode reverseList(ListNode head) {
+        ListNode root = new ListNode(0);
+        ListNode temp = head;
+        while (head != null) {
+            head = head.next;
+            temp.next = root.next;
+            root.next = temp;
+            temp = head;
+        }
+        return root.next;
+    }
+}
diff --git a/leetcode_Java/Solution0234.java b/leetcode_Java/Solution0234.java
@@ -0,0 +1,97 @@
+// 回文链表
+
+
+/**
+ * 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 boolean isPalindrome(ListNode head) {
+        List<Integer> list = new ArrayList<>();
+        while (head != null) {
+            list.add(head.val);
+            head = head.next;
+        }
+        int l = 0, r = list.size() - 1;
+        while (l < r) {
+            if (list.get(l++) != list.get(r--)) {
+                return false;
+            }
+        }
+        return true;
+    }
+}
+
+
+/*
+递归：
+1、通过递归实现在链表上双指针判断首尾元素是否一样
+2、使用成员变量作为头部指针，该指针不受递归影响，每次判断完向后移动一步
+3、通过递归直接到达链表尾部指针，此时通过首尾指针判断元素是否一样，下一层递归结束后返回上一层，相当于尾部指针往前移动一步
+ */
+class Solution {
+    private ListNode left;
+
+    public boolean isPalindrome(ListNode head) {
+        left = head;
+        return recursivelyCheck(head);
+    }
+
+    private boolean recursivelyCheck(ListNode right) {
+        if (right == null) {
+            return true;
+        }
+        if (!recursivelyCheck(right.next)) {
+            return false;
+        }
+        if (right.val != left.val) {
+            return false;
+        }
+        left = left.next;
+        return true;
+    }
+}
+
+
+/*
+快指针走到末尾，慢指针刚好到中间，其中慢指针将前半部分反转，然后从中间到首尾比较
+原始：1 → 2 → 3 → 4 → 3 → 2 → 1
+反转：1 ← 2 ← 3 ← 4 → 3 → 2 → 1
+ */
+class Solution {
+    public boolean isPalindrome(ListNode head) {
+        if (head == null || head.next == null) {
+            return true;
+        }
+        ListNode slow = head, fast = head, pre = null, temp;
+        while (fast != null && fast.next != null) {
+            fast = fast.next.next;
+            temp = slow.next;
+            slow.next = pre;
+            pre = slow;
+            slow = temp;
+        }
+        if (fast != null) {
+            slow = slow.next;
+        }
+        while (pre != null && slow != null) {
+            if (pre.val != slow.val) {
+                return false;
+            }
+            pre = pre.next;
+            slow = slow.next;
+        }
+        return true;
+    }
+}
