刷题记录

Problem: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the  definition of LCA on Wikipedia : “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow  a node to be a descendant of itself ).” _______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4 For example, the lowest common ancestor (LCA) of nodes  5  and  1  is  3 . Another example is LCA of nodes  5  and  4  is  5 , since a node can be a descendant of itself according to the LCA definition. Analysis: Find p and q in left and right subtrees.  1. find both p and q in right and left subtree, lca is current node 2. One of the subtrees has result, lca is the one.  Solution: /** * Definition for ...

6/11/2018 update: Why use R value instead of L when len is odd? Because cutR starts  with nums1.length, the mid point drops on right, so that the right part has more numbers. 这道题到道理懂，会实现。但是为什么这样实现还是一头雾水。为什么cutL要从length开始，二分条件是cutL <= cutR? -------------------------------------------------------------------------------------------------------------------------- 01/19/2018 Problem: There are two sorted arrays  nums1  and  nums2  of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 Analysis: L1 L2 nums1: 3 5 | 8 9 cut1: 2 nums2: 1 2 7 | 10 11 12 cut2: 3 R1 R2 nums3: 1 2 3 4 5 7 | 8 9 10 11 12 See the above table. If the cuts reach median, L1, L2, R1 and R2 satisfy the below conditions: L1 <= R2 R1 <= L2 Then use binar...

Problem: Reverse a linked list from position  m  to  n . Do it in one-pass. Note:  1 ≤  m  ≤  n  ≤ length of list. Example: Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL 5/1/2017 update: 第三遍是自己想出来的one pass。 主要是搞清楚怎么把m 到n reverse过后的头和尾和原链表链接起来。 class Solution { public ListNode reverseBetween ( ListNode head, int m, int n) { ListNode dummy = new ListNode ( 0 ); dummy . next = head; ListNode prev = dummy; ListNode beforeM = null; for ( int i = 0 ; i < m - 1 ; i ++ ) { prev = prev . next; } beforeM = prev; prev = prev . next; ListNode cur = prev . next, tail = prev; for ( int i = 0 ; i < n - m; i ++ ) { ListNode next = cur . next; cur . next = prev; prev = cur; cur = next; }...