L1-二分查找,合并排序数组

Posted on | In |

二分查找

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。
在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。

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:
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    int binarySearch(vector<int> &nums, int target) {
        // write your code here
        int len=nums.size();
        int start=0,end=len-1;
        while(start <= end){
            int mid = start + (end - start) / 2;
            if(nums[mid] == target){
                for(int i = mid - 1; i >= 0; i--){
                    if(nums[i] == target){
                        mid = i;
                    }
                }
                return mid;
            }else if(nums[mid] > target){
                end =  mid - 1;
            }else {
                start = mid + 1;
            }
        }
        return -1;
    } 
};

合并排序数组

给出A=[1,2,3,4]，B=[2,4,5,6]，返回 [1,2,2,3,4,4,5,6]

考虑 A,B has elements left

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    /**
     * @param A: sorted integer array A
     * @param B: sorted integer array B
     * @return: A new sorted integer array
     */
vector<int> mergeSortedArray(vector<int> &A, vector<int> &B)
{
            if (A.empty()) return B;
        if (B.empty()) return A;
    // write your code here
    vector<int> c;
    int aLen=A.size(),bLen=B.size();
    int i=0,j=0;
    while(i<aLen&&j<bLen)
    {
        if(A[i]<=B[j])
        {
            c.push_back(A[i]);
            i++;
        }
        else
        {
            c.push_back(B[j]);
            j++;
        }

    }
     // A has elements left
        while (i < aLen) {
            c.push_back(A[i]);
            i++;
        }
     // B has elements left
    while(j<bLen)
    {
        c.push_back(B[j]);
        j++;
    }

    return c;
}

};

Fizz Buzz 问题

给你一个整数n. 从 1 到 n 按照下面的规则打印每个数：

如果这个数被3整除，打印fizz.
如果这个数被5整除，打印buzz.
如果这个数能同时被3和5整除，打印fizz buzz.

很简单 注意以下判断顺序，先判断是否能被15整除，再判断能被55整除，最后判断能否被3整除 若非限制，可以用vector,ArrayList,或者stringbuilder的追加方法返回字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    /**
     * @param n: An integer
     * @return: A list of strings.
     */
    vector<string> fizzBuzz(int n) {
        // write your code here
        vector<string> c;
        for(int i=1;i<=n;i++){
    if(i%3==0&&i%5==0) c.push_back("fizz buzz");
    else
    {
        if(i%3==0) c.push_back("fizz");
        else if(i%5==0) c.push_back("buzz");
        else c.push_back(to_string(i));
    }
   
    }
    return c;
}};