力扣爆刷第163天之TOP100五連刷81-85（回文鏈表、路徑和、最長重復子數組）

一、234. 回文鏈表

題目鏈接：https://leetcode.cn/problems/palindrome-linked-list/description/
思路：判斷鏈表是否是回文鏈表，也是經典題目了，一般對于鏈表來說基本操作就是快慢指針，通過快慢指針尋找鏈表的中間節點，然后把后一半鏈表翻轉，頭插法或者尾插法都可以，這樣前一半和后一半的鏈表都正序了，就可以逐一比較了，只要相等即可。

class Solution {public boolean isPalindrome(ListNode head) {ListNode root = new ListNode(-1, head);ListNode slow = root, fast = root;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}ListNode t = new ListNode();fast = slow.next;slow.next = null;slow = fast;while(slow != null) {ListNode p = slow.next;slow.next = t.next;t.next = slow;slow = p;}slow = head;fast = t.next;while(fast != null) {if(slow.val != fast.val) return false;slow = slow.next;fast = fast.next;}return true;}}

二、112. 路徑總和

題目鏈接：https://leetcode.cn/problems/path-sum/description/
思路：求路徑總和，也就是存不存在一條路徑上的總和等于目標和，這個尋找的過程類似于回溯，找到就OK了，找不到回溯返回，可以把累加和添加在函數的參數里，這樣可以省去遞歸的撤銷代碼。

class Solution {boolean flag = false;public boolean hasPathSum(TreeNode root, int targetSum) {traverse(root, targetSum, 0);return flag;}void traverse(TreeNode root, int targetSum, int sum) {if(root == null || flag) return ;if(root.left == null && root.right == null && sum + root.val == targetSum) flag = true;traverse(root.left, targetSum, sum + root.val);traverse(root.right, targetSum, sum + root.val);}
}

三、169. 多數元素

題目鏈接：https://leetcode.cn/problems/majority-element/description/
思路：求數組中的多數元素，何為多數元素，即數量超過總個數的一半即為多數，可以利用這一特性，采用計數法，用一個變量計數，另一個變量記錄元素值，元素值相同就計數，不同就減，減到0，就替換元素，非常簡單，利用計數法。

class Solution {public int majorityElement(int[] nums) {int num = 0, t = 0;for(int i : nums) {if(num == 0) t = i;if(i == t) num++;else num--;}return t;}
}

四、662. 二叉樹最大寬度

題目鏈接：https://leetcode.cn/problems/maximum-width-of-binary-tree/description/
思路：求二叉樹的最大寬度，本題對于寬度的定義是每一層中最左邊的節點和最右邊的節點所組成的區間中的所有節點的個數，包括null節點，所以可以采取給二叉樹編碼的方式，給每一個節點編碼，并且記錄下每一層第一個向下突破深度的節點，即可根據節點編號計算寬度。

class Solution {List<Integer> list = new ArrayList<>();int max = 1;public int widthOfBinaryTree(TreeNode root) {traverse(root, 0, 0);return max;}void traverse(TreeNode root, int id, int deep) {if(root == null) return ;if(list.size() == deep) {list.add(id);}else{max = Math.max(max, id - list.get(deep)+1);}traverse(root.left, id * 2 + 1, deep + 1);traverse(root.right, id * 2 + 2, deep + 1);}}

五、718. 最長重復子數組

題目鏈接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
思路：求最長重復子數組，也是很經典的動態規劃題目，子數組是連續的，定義dp[i][j]表示以nums1[i]和nums2[j]為結尾的最長重復子數組的長度，根據定義來看，如果nums1[i] == nums2[j] 那么dp[i][j] = dp[i-1][j-1]，這是因為如果結尾相等，那么他們的長度自然依賴于上一個狀態，如果不等自然是0。

class Solution {public int findLength(int[] nums1, int[] nums2) {int m = nums1.length, n = nums2.length, max = 0;int[][] dp = new int[m+1][n+1];for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(nums1[i] == nums2[j]) {dp[i+1][j+1] = dp[i][j] + 1;}if(dp[i+1][j+1] > max) max = dp[i+1][j+1];}}return max;}
}