最长回文子串&最长子串&第K大的数字&atoi

这篇具有很好参考价值的文章主要介绍了最长回文子串&最长子串&第K大的数字&atoi。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

最长回文子串

最长回文子串&最长子串&第K大的数字&atoi

解题思路:中心扩散法

中心扩散法

其实,我们知道,对于回文子串来说,是对称的。也就是说,从中心开始,往左扩散,往右扩散,一直去比较左右两边,如果一样,就再去往左扩散,往后扩散,直到结束,如果出现不相等的情况,那就说明不是回文子串。我们来举个例子:

最长回文子串&最长子串&第K大的数字&atoi

接下来的问题是:怎么用代码去实现这个过程。

代码实现

我们遍历这个字符串的每一个字符,第一步,先找到上面的中间相同的a,先往左边找,看看有没有相同的,有的话就往左扩散,找到不相同的或者尽头,同理往右边扩散。第二步就是往左右两边同时对比是否相同:

char * longestPalindrome(char * s){
    int len = strlen(s);
    if(len==0)
    {
         return NULL;
    }
    //最大长度
    int maxLenth = 1;
    //起始下标
    int maxIndex = 0;
    for(int i = 0;i<len;i++)
    {
        //当前位置
        int curIndex = i;
        //左边
        int left = i;
        //右边
        int right = i;
        while(left!=0)
        {
            //相同往左边扩散
            if(s[left-1]==s[curIndex])
            {
                --left;
            }
            else
            {
                break;
            }
        }
        while(right!=len-1)
        {
            //相同往右边扩散
            if(s[right+1] == s[curIndex])
            {
                right++;
            }
            else
            {
                break;
            }
        }
        //往左右两边扩散
        while(left!=0&&right!=len-1)
        {
            if(s[left-1]==s[right+1])
            {
                left--;
                right++;
            }
            else
            {
                break;
            }
        }
        //更新变量
        if((right-left+1)>maxLenth)
        {
            maxLenth = right-left+1;
            maxIndex = left;
        }
    }
    char*str = (char*)malloc(sizeof(char)*(maxLenth+1));
    if(NULL == str)
    {
        return;
    }
    int j = 0;
    for(int i = maxIndex;i<=maxIndex+maxLenth-1;i++)
    {
        str[j++] = s[i];
    }
    str[j] = '\0';
    return str;
}

最长回文子串&最长子串&第K大的数字&atoi

至此,我们顺利通过了这道题。

无重复字符的最长子串

最长回文子串&最长子串&第K大的数字&atoi

这道题可以用数组哈希和滑动来进行解决。

定义left和right(初始化为0)这两个变量来记录左右的边界,让字符串中的每一个元素作为数组hash(初始化为0)的下标,我们以s[right]作为判断的条件,第一次出现就hash[s[right]]++,同时右边界往右走,既right++,如果出现重复,此时的hash对应的下标已经不是0了,我们就hash[s[left]]–,同时左边界left也要进行更新,left++.

定义count去记录right-left的最大值。接下来就是代码的实现了:

int lengthOfLongestSubstring(char * s){
    char hash[128];
    memset(hash,0,sizeof(hash));
    int left = 0,right = 0,count = 0;
    while(s[right])
    {
        if(hash[s[right]])
        {
            hash[s[left]]--;
            ++left;
        }
        else
        {
            hash[s[right]]++;
            ++right;
        }
        //更新count
        count  =count<(right-left)?(right-left):count;
    }
    return count;
}

最长回文子串&最长子串&第K大的数字&atoi

数组中的第 k 大的数字

最长回文子串&最长子串&第K大的数字&atoi

解题思路:利用堆的应用,topK问题。

题目是要找数组的第K大的数字,我们利用K个数建成一个小堆(向下调整算法)。剩下的数N-k个数我们去和堆顶进行比较,因为是要找第K大的数字,如果比堆顶大,我们就把堆顶替换,同时进行向下调整,最终堆顶就是第K大的数。

void Swap(int*p1,int*p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void AdjustDown(int*a,int n,int parent)
{
    int minChild = 2*parent+1;
    while(minChild<n)
    {
        if(minChild+1<n&&a[minChild+1]<a[minChild])
        {
            minChild++;
        }
        if(a[minChild]<a[parent])
        {
            Swap(&a[minChild],&a[parent]);
            parent = minChild;
            minChild = 2*parent+1;
        }
        else
        {
            break;
        }
    }
}

int findKthLargest(int* nums, int numsSize, int k){
    int* minHeap = (int*)malloc(sizeof(int)*k);
    if(minHeap == NULL)
    {
        exit(-1);
    } 
    else
    {
        for(int i = 0;i<k;i++)
        {
            minHeap[i] = nums[i];
        }
        for(int j = (k-1-1)/2;j>=0;j--)
        {
            AdjustDown(minHeap,k,j);
        }
        for(int i = k;i<numsSize;i++)
        {
            if(nums[i]>minHeap[0])
           {
              minHeap[0] = nums[i];
              AdjustDown(minHeap,k,0);
           }
        }
    }
    int ret = minHeap[0];
    free(minHeap);
    return ret;
}

最长回文子串&最长子串&第K大的数字&atoi

字符串转换整数 (atoi)

最长回文子串&最长子串&第K大的数字&atoi

一个非常有意思的题目,说难并不算难,但是要求还是蛮多的,注意看要求写代码就行了:

enum Status
{
	VALID,
	INVALID
}sta = INVALID;//默认非法

int myAtoi(char * s){
    long long  ret = 0;
	int flag = 1;
	assert(s);
	if (*s == '\0')
	{
		return 0;
	}
	while (isspace(*s))
	{
		s++;
	}
	if (*s == '+')
	{
		flag = 1;
		s++;
	}
	else if (*s == '-')
	{
		flag = -1;
		s++;
	}
	while (*s)
	{
		if (isdigit(*s))
		{
			//越界
			ret = ret * 10 + flag * (*s - '0');
			if (ret > INT_MAX)
			{
				return INT_MAX;
			}
            if(ret<INT_MIN)
            {
                return INT_MIN;
            }
		}
		else
		{
			return (int)ret;
		}
		s++;
	}
	if (*s == '\0')
	{
		sta = VALID;
	}
	return (int)ret;

}

最长回文子串&最长子串&第K大的数字&atoi


最长回文子串&最长子串&第K大的数字&atoi文章来源地址https://www.toymoban.com/news/detail-400271.html

到了这里,关于最长回文子串&最长子串&第K大的数字&atoi的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode刷题】最长回文子串

    📝个人主页:爱吃炫迈 💌系列专栏:数据结构与算法 🧑‍💻座右铭:道阻且长,行则将至💗 题目:最长回文子串 思路一:暴力 枚举每一个子串,找回文串,然后通过比较,找出最长的回文串。 会超时 学习更多的JavaScript字符串方法,例如上面代码中用到的 split() , joi

    2023年04月23日
    浏览(57)
  • leetcode 5 最长回文子串

    题目 给你一个字符串 s,找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 示例 输入:s = “babad” 输出:“bab” 解释:“aba” 同样是符合题意的答案。 解析 这道题和之前的那道回文的很像:647回文子串,求个数,解法还是动态

    2024年02月10日
    浏览(54)
  • 【LeetCode】5 . 最长回文子串

    思想 「中心扩散法」的基本思想是:遍历每一个下标,以这个下标为中心,利用「回文串」中心对称的特点,往两边扩散,看最多能扩散多远。 枚举「中心位置」时间复杂度为 O(N),从「中心位置」扩散得到「回文子串」的时间复杂度为 O(N),因此时间复杂度可以降到 O(N 2

    2024年02月10日
    浏览(31)
  • LeetCode刷题 | 647. 回文子串、516. 最长回文子序列

    给你一个字符串  s  ,请你统计并返回这个字符串中  回文子串  的数目。 回文字符串  是正着读和倒过来读一样的字符串。 子字符串  是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

    2024年02月12日
    浏览(44)
  • Day 57|647. 回文子串| 516.最长回文子序列

    ● 647. 回文子串 ● 516.最长回文子序列 ● 动态规划总结篇 难

    2024年02月16日
    浏览(45)
  • 算法刷题|647.回文子串、516.最长回文子序列

    题目:给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。 d

    2024年02月17日
    浏览(48)
  • 最长子串和回文子串相关的算法题解

    中等 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。 示

    2024年02月19日
    浏览(39)
  • 【算法Hot100系列】最长回文子串

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月04日
    浏览(36)
  • 力扣刷题笔记-05 最长回文子串

    半山腰有点拥挤,你要去山顶看看。 什么是回文 从左边出发,字符的顺序和从右边出发是一样的,比如aba,abba。那么基于这个理论,我们就可以想到解决方案: 找一个中心点,向两边出发,左右两边各移动一位,如果相同就证明是回文子串,不相同就停止,找下一个中心点

    2024年02月08日
    浏览(44)
  • 力扣题库刷题笔记5--最长回文子串

    1、题目如下: 2、个人Python代码实现:         首先想到的是通过类似冒泡排序的方式进行切片,然后判断切片的子字符串是否为回文字符串,然后记录出最长的回文字符串,代码如下:         可以看到,通过切片的方式,在字符串长度只有1的时候,会报错。当然,这里

    2024年02月09日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包