每日刷题(翻转+二分+BFS)

简介: 每日刷题(翻转+二分+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!  

相关文章
|
测试技术
【动态规划刷题 10】最大子数组和 III && 环形子数组的最大和
【动态规划刷题 10】最大子数组和 III && 环形子数组的最大和
|
机器学习/深度学习 算法
【动态规划刷题 9】最大子数组和 III && 环形子数组的最大和
【动态规划刷题 9】最大子数组和 III && 环形子数组的最大和
|
4天前
leecode刷题 翻转二叉树
给定一棵二叉树的根节点 `root`,翻转这棵二叉树并返回其根节点。通过递归交换每个节点的左右子树来实现翻转。示例 1:输入 `root = [4,2,7,1,3,6,9]`,输出 `[4,7,2,9,6,3,1]`。示例 2:输入 `root = [2,1,3]`,输出 `[2,3,1]`。示例 3:输入 `root = []`,输出 `[]`。树中节点数目范围在 [0, 100] 内,节点值范围为 -100 到 100。
|
6月前
【洛谷 P1443】马的遍历 题解(广度优先搜索)
该问题是一个棋盘上的马的最短路径问题。给定一个$n\times m$的棋盘和起点$(x, y)$,需要计算马到达棋盘上每个位置的最短步数。输入包含$n, m, x, y$,输出是一个矩阵,表示各位置的步数或未可达的$-1$。使用广度优先搜索(BFS)策略,从起点开始遍历,直到访问完所有可达位置。代码中定义了太阳数组表示马的移动方向,并通过队列实现BFS。最后输出格式要求每个数字左对齐且域宽为5。
44 0
|
6月前
|
存储 算法 数据可视化
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
|
7月前
|
算法 测试技术 C#
【单调栈】【区间合并】LeetCode85:最大矩形
【单调栈】【区间合并】LeetCode85:最大矩形
|
7月前
|
存储 算法
算法题解-翻转二叉树
算法题解-翻转二叉树
|
算法
并查集模板题
并查集模板题
50 0
|
Java
BFS广度优先遍历——Acwing 844. 走迷宫
BFS广度优先遍历——Acwing 844. 走迷宫
82 0
|
人工智能 算法 搜索推荐
LeetCode 周赛 338,贪心 / 埃氏筛 / 欧氏线性筛 / 前缀和 / 二分查找 / 拓扑排序
大家好,我是小彭。 上周末是 LeetCode 第 338 场周赛,你参加了吗?这场周赛覆盖的知识点很多,第四题称得上是近期几场周赛的天花板。
112 0