Convert Sorted List to Binary Search Tree(C++ code)

LeetCode Convert Sorted Array to Binary Search Tree, Oct 2 '12

难度2，出现频率3

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
思路： 每次找中间位置的node，设为root,左孩子是左半边的根，右孩子是右半边的根。
tips:左半边并不是以NULL node结束的，写判断条件的时候要注意。

TreeNode *findroot(ListNode *head, ListNode *tail){

    if(head == NULL) return NULL;

    if(head == tail) {

       TreeNode *root = new TreeNode(head->val);

      root->left = NULL; root->right = NULL;

      return root;

    }

    ListNode *slow = head, *fast = head->next;

    while(fast != tail && fast->next != tail){
     
       slow = slow->next;

       fast = fast->next->next;

    }

    TreeNode *root = new TreeNode(slow->next->val);

    root->left = findroot(head, slow);

    if(slow->next == tail) root->right = NULL;
    else root->right = findroot(slow->next->next, tail);
return root;


}

TreeNode *sortedListToBST(ListNode *head) {

      if(head == NULL) return NULL;

      ListNode *tail = head;

      while(tail->next != NULL) tail = tail->next;

      return findroot(head, tail);     

   }

3Sum Closest (C++ code)

 LeetCode: 3Sum Closest II
难度3，出现频率1
Given an array S of n integers, find three integers in S such that the sum closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

思路: 先排序，然后sliding window，记得每次更新最小和。 时间复杂度O(n^2), 空间O(1)。

int threeSumClosest(vector<int> &num, int target) { 

  int n = num.size(); 

  sort(num.begin(), num.end());

  int sum  = num[0] + num[1] + num[n-1] - target;

  for(int i = 0; i < n -2; i++){

      int start = i + 1, end = n - 1; 
      while(start < end){
                  int temp = num[i] + num[start] + num[end] - target;
                  if(abs(temp) < abs(sum)) sum = temp;
                  if(sum == 0) return target;
                  else if(temp > 0) end--;
                  else start++;
                  }  
  }
 return sum + target; 

} 

3Sum Closest III

Given an array S of n integers, find three integers in S that are closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum is 2. (-1 + 2 + 1 = 2).

求与给定点t距离最近的三个点的和--把点列表每个值x换成|x-t|，则原题转化为求最小的三个值的和---

只需要建三个元素的heap。但求和的时候需要的是x而非|x-t|，两个选择：

1，另建一个flag列表标明每个元素的正负--O(n) space, not good.

2,保持原列表，以|x-t|为条件进行比较。

思路2的c++ code: 

时间复杂度： O(n), 空间复杂度： O(1)

int threeSumClosest(vector<int> &num, int target){
   int sum = 0;
   int maxdist = INT_MAX, maxpt = 0;
 
   for(int i = 0; i < num.size(); i++){
     if(i < 3) {
       sum += num[i];
      }
     if(abs(num[i] - target) < maxdist){
        if(i >= 3){sum = sum + num[i] - num[maxpt];}
        maxdist = abs(num[i] - target);
        maxpt = i;
     }
   }
   return sum;
}