描述:大數(shù)加法
思路:減字符0，得到數(shù)值，兩數(shù)想加，取余，取進位。
? ? public String solve(String s, String t) {
? ? ? ? StringBuilder stringBuilder = new StringBuilder();
? ? ? ? int i = s.length() - 1, j = t.length() - 1, carry = 0;
? ? ? ? while (i >= 0 || j >= 0 || carry != 0) {
? ? ? ? ? ? int x = i < 0 ? 0 : s.charAt(i--) - '0';
? ? ? ? ? ? int y = j < 0 ? 0 : t.charAt(j--) - '0';
? ? ? ? ? ? int sum = x + y + carry;
? ? ? ? ? ? stringBuilder.append(sum % 10);//添加到字符串尾部
? ? ? ? ? ? carry = sum / 10;
? ? ? ? }
? ? ? ? return stringBuilder.reverse().toString();//對字符串反轉
? ? }
描述:重建鏈表
思路:1.快慢指針找到鏈表中點；2.反轉后半段鏈表；3.前后鏈表合并。
public class Solution {
? ? public void reorderList(ListNode head) {
? ? ? ? if (head == null || head.next == null || head.next.next == null) {
? ? ? ? return;
? ? }
? ? //找中點，鏈表分成兩個
? ? ListNode slow = head;
? ? ListNode fast = head;
? ? while (fast.next != null && fast.next.next != null) {
? ? ? ? slow = slow.next;
? ? ? ? fast = fast.next.next;
? ? }
? ? ListNode newHead = slow.next;
? ? slow.next = null;
? ?
? ? //第二個鏈表倒置，反轉后半部分鏈表
? ? newHead = reverseList(newHead);
? ?
? ? //鏈表節(jié)點依次連接
? ? while (newHead != null) {
? ? ? ? ListNode temp = newHead.next;
? ? ? ? newHead.next = head.next;
? ? ? ? head.next = newHead;
? ? ? ? head = newHead.next;
? ? ? ? newHead = temp;
? ? }
}
? ? private ListNode reverseList(ListNode head) {
? ? ? ? if (head == null) {
? ? ? ? ? ? return null;
? ? ? ? }
? ? ? ? ListNode tail = head;
? ? ? ? head = head.next;
? ? ? ? tail.next = null;
? ? ? ? while (head != null) {
? ? ? ? ? ? ListNode temp = head.next;
? ? ? ? ? ? head.next = tail;
? ? ? ? ? ? tail = head;
? ? ? ? ? ? head = temp;
? ? ? ? }
? ? ? ? return tail;
? ? }
}
描述:快慢指針找鏈表環(huán)入口節(jié)點
public ListNode EntryNodeOfLoop(ListNode pHead) {
? ? ? ? if(pHead == null) return null;
? ? ? ? // 定義快慢指針
? ? ? ? ListNode slow = pHead;
? ? ? ? ListNode fast = pHead;
? ? ? ? while(fast != null && fast.next != null){
? ? ? ? ? ? // 快指針是滿指針的兩倍速度
? ? ? ? ? ? fast = fast.next.next;
? ? ? ? ? ? slow = slow.next;
? ? ? ? ? ? // 記錄快慢指針第一次相遇的結點
? ? ? ? ? ? if(slow == fast) break;
? ? ? ? }
? ? ? ? // 若是快指針指向null，則不存在環(huán)
? ? ? ? if(fast == null || fast.next == null) return null;
? ? ? ? // 重新指向鏈表頭部
? ? ? ? fast = pHead;
? ? ? ? // 與第一次相遇的結點相同速度出發(fā)，相遇結點為入口結點
? ? ? ? while(fast != slow){
? ? ? ? ? ? fast = fast.next;
? ? ? ? ? ? slow = slow.next;
? ? ? ? }
? ? ? ? return fast;
? ? }
描述:判斷鏈表是否有環(huán)
思路:快慢指針
public boolean hasCycle(ListNode head) {
? ? ? ? if(head == null) return false;
? ? ? ? // 定義快慢指針
? ? ? ? ListNode slow = head;
? ? ? ? ListNode fast = head;
? ? ? ? while(fast != null && fast.next != null){
? ? ? ? ? ? // 快指針是滿指針的兩倍速度
? ? ? ? ? ? fast = fast.next.next;
? ? ? ? ? ? slow = slow.next;
? ? ? ? ? ? // 記錄快慢指針第一次相遇的結點
? ? ? ? ? ? if(slow == fast) return true;
? ? ? ? }
? ? ? ? return false;
? ? }
描述:二叉樹根節(jié)點到葉子節(jié)點的所有路徑和
思路:DFS
? ? public int sumNumbers(TreeNode root) {
? ? ? ? //如果根節(jié)點是空，直接返回0即可
? ? ? ? if (root == null)
? ? ? ? ? ? return 0;
? ? ? ? //兩個棧，一個存儲的是節(jié)點，一個存儲的是節(jié)點對應的值
? ? ? ? Stack<TreeNode> nodeStack = new Stack<>();
? ? ? ? Stack<Integer> valueStack = new Stack<>();
? ? ? ? //全局的，統(tǒng)計所有路徑的和
? ? ? ? int res = 0;
? ? ? ? nodeStack.add(root);
? ? ? ? valueStack.add(root.val);
? ? ? ? while (!nodeStack.isEmpty()) {
? ? ? ? ? ? //當前節(jié)點和當前節(jié)點的值同時出棧
? ? ? ? ? ? TreeNode node = nodeStack.pop();
? ? ? ? ? ? int value = valueStack.pop();
? ? ? ? ? ? if (node.left == null && node.right == null) {
? ? ? ? ? ? ? ? //如果當前節(jié)點是葉子結點，說明找到了一條路徑，把這條
? ? ? ? ? ? ? ? //路徑的值加入到全局變量res中
? ? ? ? ? ? ? ? res += value;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? //如果不是葉子節(jié)點就執(zhí)行下面的操作
? ? ? ? ? ? ? ? if (node.right != null) {
? ? ? ? ? ? ? ? ? ? //把子節(jié)點和子節(jié)點的值分別加入到棧中，這里子節(jié)點的值
? ? ? ? ? ? ? ? ? ? //就是父節(jié)點的值*10+當前節(jié)點的值
? ? ? ? ? ? ? ? ? ? nodeStack.push(node.right);
? ? ? ? ? ? ? ? ? ? valueStack.push(value * 10 + node.right.val);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (node.left != null) {
? ? ? ? ? ? ? ? ? ? nodeStack.push(node.left);
? ? ? ? ? ? ? ? ? ? valueStack.push(value * 10 + node.left.val);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return res;
? ? }
題目描述
給出一個升序排序的數(shù)組，將其轉化為平衡二叉搜索樹（BST）
思路:題目中所給的是一個升序排序的數(shù)組，所以一個大體流程就是根據(jù)一個中序遍歷的序列，還原出一個它對應的二叉樹。因為是中序遍歷的結果，所以元素的左邊都是以該元素為根節(jié)點的左子樹上的元素，元素的右邊都是以該元素為根節(jié)點的右子樹上的元素。
又因為是平衡的，所以先找出序列的中點，以中點的值生成根節(jié)點，他的左邊右邊相差不差過一個元素，即它的左子樹和右子樹的元素個數(shù)相差不超過一個，每次都安一樣的策略來找根節(jié)點，即左右子樹的高度相差不會超過1。
public class Solution {
? ? /**
? ? *
? ? * @param num int整型一維數(shù)組
? ? * @return TreeNode類
? ? */
? ? public TreeNode sortedArrayToBST (int[] nums) {
? ? ? ? // 判斷特殊情況， 數(shù)組為空，或數(shù)組上沒有元素，直接返回 null
? ? ? ? if (nums == null || nums.length == 0) {
? ? ? ? ? ? return null;
? ? ? ? }
? ? ? ? return process(nums, 0, nums.length - 1);
? ? }
? ? /**
? ? *
? ? * @param nums? 整個的有序數(shù)組
? ? * @param left? 數(shù)組的左邊界， 閉區(qū)間
? ? * @param right 數(shù)組的右邊界， 閉區(qū)間
? ? * @return nums[left ... right] 這個范圍的數(shù)組，轉成 BST 后的根節(jié)點
? ? */
? ? public TreeNode process(int[] nums, int left, int right) {
? ? ? ? // 左邊界 比 右邊界 大， 說明數(shù)組上沒有元素，直接返回 null
? ? ? ? if (left > right) {
? ? ? ? ? ? return null;
? ? ? ? }
? ? ? ? // 如果只有一個元素，就把它當成根節(jié)點直接返回
? ? ? ? if (left == right) {
? ? ? ? ? ? TreeNode root = new TreeNode(nums[left]);
? ? ? ? ? ? return root;
? ? ? ? }
? ? ? ? // nums[left ... right] 這個數(shù)組的長度
? ? ? ? int len = right - left + 1;
? ? ? ? // nums[left ... right] 這個數(shù)組的中點下標，這個下標里的元素值就是 BST 的根節(jié)點的值
? ? ? ? int mid = left + len / 2;
? ? ? ? TreeNode root = new TreeNode(nums[mid]);
? ? ? ? // 找出根節(jié)點的左子樹： 繼續(xù)遞歸用這個方法，找出左子樹上這個局部范圍的BST的根節(jié)點
? ? ? ? root.left = process(nums, left, mid - 1);
? ? ? ? // 找出根節(jié)點的右子樹： 繼續(xù)遞歸用這個方法，找出右子樹上這個局部范圍的BST的根節(jié)點
? ? ? ? root.right = process(nums, mid + 1, right);
? ? ? ? return root;
? ? }
}
題目描述
請實現(xiàn)一個函數(shù)，用來判斷一棵二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。
思路:
因為要比較左右結點是否對稱，因此可以通過BFS每次對一層的結點進行遍歷并比較是否對稱。
public class Solution {
? ? boolean isSymmetrical(TreeNode pRoot)
? ? {
? ? ? ? if(pRoot == null){
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? // 遞歸調(diào)用
? ? ? ? return recur(pRoot.left, pRoot.right);
? ? }
? ? // 遞歸函數(shù)功能：判斷左右兩個結點是否對稱相等
? ? private boolean recur(TreeNode left, TreeNode right) {
? ? ? ? // 沒有子節(jié)點，說明當前結點是葉子結點
? ? ? ? if(left == null) {
? ? ? ? ? ? return right == null;
? ? ? ? }
? ? ? ? // 沒有右子節(jié)點
? ? ? ? if(right == null) {
? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? // 左右結點不對稱
? ? ? ? if(left.val != right.val) {
? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? // 左子樹的右子樹和右子樹的左子樹相同即可
? ? ? ? return recur(left.right, right.left) && recur(left.left, right.right);
? ? }
}
