[LeetCode] Search Insert Position 解题报告

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

» Solve this problem

[解题思路]
跟经典的二分查找相比，只是多了一个条件：
if(mid>left && A[mid]>target && A[mid-1]<target)


[Code]

1:  int searchInsert(int A[], int n, int target) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int l=0, r=n-1;  
5:      while(l<=r)  
6:      {  
7:        int mid = (l+r)/2;  
8:        if(A[mid] == target) return mid;  
9:        if(mid>l && A[mid]>target && A[mid-1]<target ) return mid;  
10:        if(A[mid] > target)  
11:        {  
12:          r= mid-1;  
13:        }  
14:        else  
15:        {  
16:          l=mid+1;  
17:        }        
18:      }  
19:      return l;  
20:    }  

[LeetCode] Search in Rotated Sorted Array II 解题报告

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

» Solve this problem

[解题思路]
确实有影响。比如，上一题(http://fisherlei.blogspot.com/2013/01/leetcode-search-in-rotated-sorted-array.html)的程序中默认如果A[m]>=A[l],那么[l,m]为递增序列的假设就不能成立了，比如如下数据
[1,3,1,1,1]
所以，要是想增强该假设，有两个选择
1. 对于每一个递增序列，遍历之，确认。
2. 找到pivot点，然后确定对应序列搜索。


不写代码了。


Update: 3/18/2013. add the implementation
重新想了一下，其实不需要这么复杂。如果A[m]>=A[l]不能确定递增，那就把它拆分成两个条件
1. A[m]>A[l]  递增
2. A[m] ==A[l] 确定不了，那就l++，往下看一步即可。

实现如下

1:       bool search(int A[], int n, int target) {  
2:            int start = 0;  
3:            int end = n-1;  
4:            while(start <= end)  
5:            {  
6:                 int mid = (start+end)/2;  
7:                 if(A[mid] == target) return true;  
8:                 if(A[start] < A[mid])  
9:                 {  
10:                      if(target>=A[start] && target<A[mid])  
11:                           end = mid-1;  
12:                      else   
13:                           start = mid+1;  
14:                 }  
15:                 else if(A[start] > A[mid])  
16:                 {  
17:                      if(target>A[mid] && target<=A[end])  
18:                           start = mid+1;  
19:                      else  
20:                           end = mid-1;  
21:                 }  
22:                 else //skip duplicate one, A[start] == A[mid]  
23:                      start++;  
24:            }  
25:            return false;  
26:       }  

[LeetCode] Search in Rotated Sorted Array 解题报告

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

» Solve this problem


[解题思想]
同样是二分，难度主要在于左右边界的确定。需要结合两个不等式：
1. A[m] ? A[left]
2. A[m] ? target
具体逻辑看code。

[Code]

1:       int search(int A[], int n, int target) {   
2:            // Start typing your C/C++ solution below   
3:            // DO NOT write int main() function   
4:            int l = 0, r = n-1;   
5:            while(l<=r)   
6:            {   
7:                 int m = (l+r)/2;   
8:                 if(A[m] == target) return m;   
9:                 if(A[m]>= A[l])   
10:                 {   
11:                      if(A[l]<=target && target<= A[m])   
12:                      r=m-1;   
13:                      else   
14:                      l = m+1;       
15:                 }   
16:                 else   
17:                 {   
18:                      if(A[m] >= target || target>= A[l])   
19:                      r = m-1;    
20:                      else   
21:                      l = m+1;   
22:                 }   
23:            }   
24:            return -1;   
25:       }   

Update 08/23/2014
See the comments from reader. Add a graph and also change the code a bit for readability(See highlight code in red).

The general idea is, to use some in-equations to distinguish below 3 conditions, and decide the new range of binary search.

1:       int search(int A[], int n, int target) {    
2:            int l = 0, r = n-1;    
3:            while(l<=r)    
4:            {    
5:                 int m = (l+r)/2;    
6:                 if(A[m] == target) return m;    
7:                 if(A[m]>= A[l])    
8:                 {    
9:                      if(A[l]<=target && target< A[m])    
10:                           r=m-1;    
11:                      else    
12:                           l = m+1;      
13:                 }    
14:                 else    
15:                 {    
16:                      if(A[m]< target && target<=A[r])    
17:                           l = m+1;    
18:                      else    
19:                           r = m-1;   
20:                 }    
21:            }    
22:            return -1;    
23:       }    

[LeetCode] Search for a Range 解题报告

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

» Solve this problem


[解题思路]
首先二分，然后根据二分的坐标分别往前和往后找找即可。

[Code]

1:       vector<int> searchRange(int A[], int n, int target) {  
2:            // Start typing your C/C++ solution below  
3:            // DO NOT write int main() function  
4:            vector<int> range;  
5:            int index = searchTarget(A, 0, n-1, target);  
6:            if(index == -1)  
7:            {  
8:                 range.push_back(-1);  
9:                 range.push_back(-1);  
10:            }  
11:            else  
12:            {  
13:                 int is = index;  
14:                 while(is>0 && A[is-1] == A[index]) is--;  
15:                 int ie = index;  
16:                 while(ie<n-1 && A[ie+1] == A[index]) ie++;  
17:                 range.push_back(is);  
18:                 range.push_back(ie);        
19:            }  
20:            return range;  
21:       }  
22:       int searchTarget(int A[], int start, int end, int target)  
23:       {  
24:            if(start > end) return -1;  
25:            int mid = (start+end)/2;  
26:            if(A[mid] == target) return mid;  
27:            if(A[mid]<target)  
28:            return searchTarget(A, mid+1, end, target);  
29:            else  
30:            return searchTarget(A, start, mid-1, target);      
31:       }  

[Note]
1. Line 6
错误的写成，"if(index = -1)", 少了个=号，结果老是输出[-1,-1].


Update: 07/15/2013 Refactor the code
看了一下评论，Jarvis很关注最差时间复杂度。其实从题目上来说，它更关注是平均复杂度。上面的算法在最差情况下复杂度是O(n)，但是平均复杂度是O(lgn)。
如果想实现最差复杂度也是O(lgn)，也很简单，做两次二分就可以了，第一次二分找出最左边的边界，第二次二分找出最右边的边界，这样，无论平均还是最差都是O(lgn)。

实现如下：

1:    vector<int> searchRange(int A[], int n, int target) {  
2:      vector<int> result;  
3:      result.push_back(-1);  
4:      result.push_back(-1);    
5:      // find the low bound of the range, O(lgn)  
6:      int start =0, end =n-1;  
7:      while(start < end)  
8:      {  
9:        int mid = (start + end)/2;  
10:        if(A[mid] < target)  
11:        {  
12:          start = mid + 1;  
13:          continue;  
14:        }  
15:        end = mid;  
16:      }      
17:      int low_bound = A[start] == target? start:-1;  
18:      if(low_bound == -1)  
19:      {  
20:        return result;  
21:      }  
22:      // find the high bound of the range, O(lgn)  
23:      start =low_bound, end =n;  
24:      while(start < end)  
25:      {  
26:        int mid = (start + end)/2;  
27:        if(A[mid] > target)  
28:        {  
29:          end = mid;  
30:          continue;  
31:        }            
32:        start = mid+1;  
33:      }  
34:      int high_bound = start-1;  
35:      result.clear();  
36:      result.push_back(low_bound);  
37:      result.push_back(high_bound);  
38:      return result;      
39:    }  

[LeetCode] Scramble String 解题报告

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

» Solve this problem

[解题思路]
首先想到的是递归，简单明了，对两个string进行partition，然后比较四个字符串段。但是递归的话，这个时间复杂度比较高。然后想到能否DP，但是即使用DP的话，也要O(n^3)。想想算了，还是在递归里做些剪枝，这样就可以避免冗余计算：

• 对于每两个要比较的partition，统计他们字符出现次数，如果不相等返回。

 上网搜了一下，有人说可以O(n)做出来。http://www.mitbbs.com/article_t/JobHunting/32114513.html
但是我没办法证明他这个算法的正确性。感觉这道题应该有O(n)的解法，一时想不出来。

1:       bool isScramble(string s1, string s2) {   
2:            // Start typing your C/C++ solution below   
3:            // DO NOT write int main() function   
4:            if(s1.size() != s2.size()) return false;   
5:            int A[26];   
6:            memset(A,0,26*sizeof(A[0]));   
7:            for(int i =0;i<s1.size(); i++)   
8:            {   
9:                 A[s1[i]-'a']++;   
10:            }   
11:            for(int i =0;i<s2.size(); i++)   
12:            {   
13:                 A[s2[i]-'a']--;   
14:            }   
15:            for(int i =0;i<26; i++)   
16:            {   
17:                 if(A[i] !=0)   
18:                 return false;   
19:            }   
20:            if(s1.size() ==1 && s2.size() ==1) return true;   
21:            for(int i =1; i< s1.size(); i++)   
22:            {   
23:                 bool result= isScramble(s1.substr(0, i), s2.substr(0, i))   
24:                      && isScramble(s1.substr(i, s1.size()-i), s2.substr(i, s1.size()-i));   
25:                 result = result || (isScramble(s1.substr(0, i), s2.substr(s2.size() - i, i))   
26:                      && isScramble(s1.substr(i, s1.size()-i), s2.substr(0, s1.size()-i)));   
27:                 if(result) return true;   
28:            }   
29:            return false;   
30:       }   

[LeetCode] Rotate List 解题报告

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

» Solve this problem

[解题思路]

首先从head开始跑，直到最后一个节点，这时可以得出链表长度len。然后将尾指针指向头指针，将整个圈连起来，接着往前跑len – k%len，从这里断开，就是要求的结果了。

[Code]

1:    ListNode *rotateRight(ListNode *head, int k) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      if(head == NULL || k ==0) return head;  
5:      int len =1;  
6:      ListNode* p = head,*pre;  
7:      while(p->next!=NULL)  
8:      {  
9:        p = p->next;  
10:        len++;      
11:      }  
12:      k = len-k%len;  
13:      p->next = head;  
14:      int step =0;  
15:      while(step< k)  
16:      {  
17:        p = p->next;  
18:        step++;  
19:      }  
20:      head = p->next;  
21:      p->next = NULL;  
22:      return head;  
23:    }  

[Note]
注意K大于len的可能。

[LeetCode] Rotate Image 解题报告

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

» Solve this problem

[解题思路]
如下图，首先沿逆对角线翻转一次，然后按x轴中线翻转一次。

[Code]

1:    void rotate(vector<vector<int> > &matrix) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int len = matrix[0].size();  
5:      for(int i =0; i<len-1; i++)  
6:      {  
7:        for(int j=0;j<len-i;j++)  
8:        {  
9:          swap(matrix[i][j], matrix[len-1-j][len-1-i]);  
10:        }  
11:      }  
12:      for(int i =0; i<len/2; i++)  
13:      {  
14:        for(int j=0;j<len;j++)  
15:        {  
16:          swap(matrix[i][j], matrix[len-i-1][j]);  
17:        }  
18:      }  
19:    }  
20:    void swap(int& a1, int&a2)  
21:    {  
22:      int temp = a1;  
23:      a1=a2;  
24:      a2=temp;  
25:    }