OJ每日练习（2）

Posted on | In

题目名称

  1. Search in Rotated Sorted Array（Leetcode #33)
  2. Search in Rotated Sorted ArrayⅡ ( Leetcode #81）
  3. 二维数组查找（剑指offer #4）
  4. 替换空格（剑指offer #5）

Search in Rotated Sorted Array（Leetcode #33)

题目描述

Suppose an array sorted in ascending order 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.Your algorithm’s runtime complexity must be in the order of O(log n).

解题思路

本题数组不含有重复元素，此外指定时间复杂度为O(logn)，必须采用二分。本题的关键在于：若nums[m]>=nums[l]，则[l,m]必为升序。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int search(vector<int>& nums, int target) {
        size_t first = 0;
        size_t last = nums.size();
        while(first<last){
            size_t mid = first+(last-first)/2;
            if(nums[mid]==target)
                return mid;
            if(nums[first]<=nums[mid]){//写<亦可,为下一题做准备
                if(nums[first]<=target && target<nums[mid])
                    last=mid;
                else
                    first = mid+1;
            }
            else{
                if(nums[mid]<target && target<=nums[last-1])
                    first = mid+1;
                else
                    last = mid;
            }
        }
        return -1;
    }
};

扩展

本题还有一种解法，即首先二分找出最小元素（必为翻转点），此后利用传统二分查找即可。找出最小元素的算法如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.empty()) return -1;
        else if(nums.size()==1) return 0;
        size_t lo = 0; 
        size_t hi = nums.size() - 1; 
        while (lo < hi) {
            size_t mid = lo+(hi-lo)/2; 
            if (nums[mid] > nums[mid + 1]) 
                return nums[mid + 1];      
            if (nums[hi] < nums[mid]) 
                lo = mid + 1;
            else 
                hi = mid;
        }  
        return lo;
    }
};

（本方案结合下题，稍加改进即可解决剑指offer#11）。如果当前需要寻找旋转（且带有重复元素）数组的max，笔者认为需要将比对区间由[mid,hi]改为[lo,mid]，此想法尚未验证。

Search in Rotated Sorted ArrayⅡ ( Leetcode #81）

题目描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).You are given a target value to search. If found in the array return true, otherwise return false.

解题思路

在本题中允许重复，因此若nums[m]>=nums[l]，则[l,m]为升序的推论不成立(见上一题解决方案Line10）。反例为：[1,2,1,1,1];
我们将nums[m]>=nums[l]分为两种可能：

  1. nums[m]>nums[l],则区间[l,m]必为升序
  2. nums[m]==nums[l],自增l，观察结果

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if(nums.empty()) return false;
        if(nums.size()==1) return nums[0]==target;
        size_t first=0;
        size_t last=nums.size();
        while(first<last){
            size_t mid = first+(last-first)/2;
            if(nums[mid]==target)
                return true;
            if(nums[first]<nums[mid]){
                if(nums[first]<=target && target<nums[mid])
                    last=mid;
                else
                    first=mid+1;
            }
            else if(nums[first]==nums[mid])
                ++first;
            else{
                if(nums[mid]<target && target<=nums[last-1])
                    first=mid+1;
                else
                    last=mid;
            }
        }
        return false;
    }
};

二维数组查找

题目描述

现有一二维数组，元素按照每一行从左向右递增，每一列从上向下的规律排序完毕，试以线性时间完成元素查找。

解题思路

从左下角或右上角开始查找即可。试以左下角为例，小则向上，大则向右。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int i = array.size()-1;
        int j = 0;
        while(i>=0 && j!=array[i].size()){
            if(array[i][j]==target)
                return true;
            else if(array[i][j]<target)
                ++j;
            else --i;
        }
        return false;
    }
};

替换空格

题目描述

将某字符串内所有空格替换为”%20”。

解题思路

暴力法需要对线性表进行反复插入，造成不必要的开销。应当预判替换完毕的线性表长度，然后倒序遍历字符串完成拷贝操作。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void replaceSpace(char *str, int length) {
	    int count = 0;
	    char* cur = str;
	    while (*cur != '\0')
		    if (*cur++ == ' ') count++;
	    int newlength = length + count * 2;
	    char* last = str + newlength - 1;
	    char* rcur = str + length - 1;
	    while (count) {
		    if (*rcur != ' ')
		    	*last-- = *rcur--;
		    else {
			    count--;
			    *last-- = '0';
			    *last-- = '2';
		        *last-- = '%';
			    rcur--;
		    }
	    }
    }
};