每日刷题（翻转+二分+BFS）

一、局部翻转+整体翻转

题目链接：剑指 Offer 58 - II. 左旋转字符串

题目描述：

       字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

       示例 1：

输入: s = "abcdefg", k = 2

输出: "cdefgab"

       示例 2：

输入: s = "lrloseumgh", k = 6

输出: "umghlrlose"

       限制：

• 1 <= k < s.length <= 10000

本题思路：

 使用 整体反转+局部反转 就可以实现「反转单词顺序」的目的。当然，你使用先整体还是先局部翻转得到的效果都是一样的！

       这里使用先局部后整体的思路：（时间复杂度O(n),空间复杂度 O(1)）

               反转前 n 个字符

               反转 n 到末尾的字符

               反转整个字符串

char* reverse(char* s, int start, int end) {
    while (start < end) {
        char temp = s[start];
        s[start++] = s[end];
        s[end--] = temp;
    }
    return s;
}
char* reverseLeftWords(char* s, int n){
    int len = strlen(s);
    //反转前 n 个字符
    s = reverse(s, 0, n - 1);
    //反转 k 到末尾的字符
    s = reverse(s, n, len - 1);
    //反转整个字符串
    s = reverse(s, 0, len - 1);
    return s;
}

二、二分查找

题目链接：剑指 Offer 53 - I. 在排序数组中查找数字 I

题目描述：

       统计一个数字在排序数组中出现的次数。

  示例 1:

输入: nums = [5,7,7,8,8,10]

, target = 8

输出: 2

       示例 2:

输入: nums = [5,7,7,8,8,10]

, target = 6

输出: 0

       提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

本题思路：

一种是暴力，一种是二分法求边界

       暴力法当然简单，一个for循环就搞定了。那为什么我还把这道简单题放到这里呢？因为我们需要做的是以简答题来体现我们思想递进的过程。

       于是我们就想到了二分法，这里是使用了两次二分。一次找到x元素最左边位置，一次找到x元素最右边的位置，最终返回的是右边的位置减左边的位置 + 1。当数组大小为零时候特殊处理，返回0。

暴力法

int search(int* nums, int numsSize, int target){
    int cn=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]==target)
        {
            cn++;
        }
    }
    return cn;
}

二分法

int L(int *nums, int x, int size)
{
    int l=0, r=size-1, mid=0;
    while( l < r ) {
        mid = l + (r-l)/2;
        if( nums[mid] >= x ) r = mid;
        else l = mid + 1;
    }
    return nums[l] == x?l:0;
}
int R(int *nums, int x, int size)
{
    int l=0, r=size-1, mid=0;
    while( l < r ) {
        mid = l + (r-l)/2 + 1;
        if( nums[mid] <= x ) l = mid;
        else r = mid - 1;
    }
    return nums[l] == x?l:-1;
}
int search(int* nums, int numsSize, int target){
    if( !numsSize ) return 0;
    return R(nums,target,numsSize) - L(nums,target,numsSize) + 1;
}

三、BFS—广度优先算法

题目链接：剑指 Offer 32 - I. 从上到下打印二叉树

题目描述：

       从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

    例如:

给定二叉树: [3,9,20,null,null,15,7],

   3

  / \

 9  20

   /  \

  15   7

 返回：

[3,9,20,15,7]

       提示：

节点总数 <= 1000

本题思路：

       运用队列来实现BFS。需要注意二叉树空的情况，返回NULL，这里有个*returnsize也是需要反回的，所以开始先设置其为0，然后后面再返回一次。这里队列遍历时也需要注意要用个中间的变量来存储之前遍历的节点，以此来模拟触发BFS进队列的功能。

#define MAX_SIZE 1001
int* levelOrder(struct TreeNode* root, int* returnSize)
{
    *returnSize=0;
    if(root==NULL)
    return NULL;//为空情况
    struct TreeNode* queue[MAX_SIZE];//初始化
    memset(queue,0,sizeof(struct TreeNode*));
    int *ren=(int*)malloc(sizeof(int)*MAX_SIZE);
    int ret=0,front=0,rear=0;
    queue[rear++]=root;//先进一个，保证进入循环
    while(front<rear)//BFS
    {
        struct TreeNode* tmp=queue[front++];
        ren[ret++]=tmp->val;
        if(tmp->left!=NULL)
        queue[rear++]=tmp->left;
        if(tmp->right!=NULL)
        queue[rear++]=tmp->right;
    }
    *returnSize=ret;
    return ren;
}

     感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！