Java教程

把数组排成最小的数字,划分字母区间,最小覆盖子串,验证回文字符串II

本文主要是介绍把数组排成最小的数字,划分字母区间,最小覆盖子串,验证回文字符串II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

面试题45:把数组排成最小的数字

输入一个正整数数组,把数组里所有的数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。这里自定义了一个排序规则。

class Solution {
public:
static int MyCompare(const string& s1,const string& s2){
    return s1+s2<s2+s1;
}
    string minNumber(vector<int>& nums) {
        int n=nums.size();
        string ret;
        if(n==0) return ret;
        vector<string> strnums;
        for(auto i:nums){
            strnums.push_back(to_string(i));
        }
        sort(strnums.begin(),strnums.end(),MyCompare);
       for(auto i:strnums){
           ret+=i;
       }
       return ret;
    }
};

C的代码

#include<bits/stdc++.h>
using namespace std;
const int g_MaxNumberLength=10;

char* g_strCombine1=new char[g_MaxNumberLength*2+1];
char* g_strCombine2=new char[g_MaxNumberLength*2+1];
int compare(const void* strNumber1, const void* strNumber2);
void PrintMinNumber(int *numbers,int length){
    if(numbers==nullptr||length<=0){
        return;
    }
    char** strNumbers=(char**) (new int[length]);
    for(int i=0;i<length;++i){
        strNumbers[i]=new char[g_MaxNumberLength+1];
        sprintf(strNumbers[i],"%d",numbers[i]);
    }
    qsort(strNumbers,length,sizeof(char*),compare);

    for(int i=0;i<length;++i){
        printf("%s",strNumbers[i]);
    }
    printf("\n");

    for(int i=0;i<length;++i){
        delete[] strNumbers[i];
    }
    delete[] strNumbers;
}
int compare(const void* strNumber1, const void* strNumber2){
    strcpy(g_strCombine1,*(const char**)strNumber1);
    strcat(g_strCombine1,*(const char**)strNumber2);

    strcpy(g_strCombine2,*(const char**)strNumber2);
    strcat(g_strCombine2,*(const char**)strNumber1);

    return strcmp(g_strCombine1,g_strCombine2);
}
int main(void)
{
 int a[5]={3,30,34,5,9};
 PrintMinNumber(a,5);

 return 0;
}

2021年7月24日,还是要好好写笔记,好一阵没有认真做笔记记录了,有时候看看博客感觉自己写的题其实也不那么少了,但是长进却不大。

2.力扣763题:Partitionlables

在网上看到的统计一个字符第一次和最后一次出现的位置的方法,最后一次的位置可以从后往前去算,加油加油,今天是学习的一天,下一周的周一到周四会在8:40到9点之间回家。

 题目是这样的:字符串S由小写字母组成,我们要把这个字符串划分为尽可能多的片段,同一个字母最多出现在一个片段中,用的是贪心策略,思路是:需要统计出每个字符最后一次出现的位置,然后遍历该字符串

//统计某个字符第一次出现的位置
char* strchr(char *p,char a) 
{
	int i;
	assert(p!=NULL);
	for(i=0;i<strlen(p);i++)
	{
		if(p[i]==a)
		return p+i;
	}
	return 0;
}

//统计某个字符第一次出现的位置
char* strrchr(char *p,char a) 
{
	int i;
	char *ret=p;
	assert(p!=NULL);
	for(i=strlen(p)-1;i>0;i--)
	{
		if(p[i]==a)
		return ret+i;
	}
    return 0;
}

反向迭代器:相比于正向迭代器只需要把begin和end换成rbegin和rend。关于unorder_map和map,我们希望可以是有序的(按照字母表索引的)可以使用map。不过这倒题目中,

直接使用下标操作存在一个危险的副作用:如果该键不在map容器中,那么下标操作会插入一个具有该键的新元素。但是大多数情况下,使用者并不想插入一个容器本不存在的key。

 这道题目采取贪心策略,思路如下:

  • 先获得每个字母最后一次出现的下标位置,需要自建hashtable
  • 从左到右遍历字符串,遍历的同时维护当前片段的开始下标start和结束end
  • 对于每个访问到的字母c,end=max(end,endc)
  • 当访问到下标end时,当前片段访问结束,长度为end-start+1
  • 重复上述过程,直到遍历完字符串
    class Solution {
    public:
        vector<int> partitionLabels(string s) {
        int last[26];
         vector<int> res;
         for(int i=0;i<s.size();++i){
            last[s[i]-'a']=i;
         }
         int start=0, end=0;
         for(int i=0;i<s.size();++i){
            if(last[s[i]-'a']>end){
                end=last[s[i]-'a'];
            }//end=max(end,last[s[i-'a' ]
            if(i==end){
                        res.push_back(end-start+1);
                        start=end+1;
                       }
          }
          return res;
        }
    };

    注意:不要忘记在while的分支里break

3.滑动窗口

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。

注意:

对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

双指针主要用于遍历数组,两个指针指向不同的元素,从而协同完成任务。也可以延伸到多
个数组的多个指针。
若两个指针指向同一数组,遍历方向相同且不会相交,则也称为滑动窗口(两个指针包围的
区域即为当前的窗口),经常用于区间搜索。
若两个指针指向同一数组,但是遍历方向相反,则可以用来进行搜索,待搜索的数组往往是
排好序的。
 

 一篇不错的题解:

 注意这个最大的for循环是直到right超出了字符串s的范围

string s="ADOBECODEBANC";
    string t="ABC";
    vector<int> chars(128,0);
    vector<bool> flag(128,false);
    for(int i=0;i<t.size();++i){
        flag[t[i]]=true;
        chars[t[i]]++;
    }
    int cnt = 0, left = 0, min_l = 0, min_size = s.size() + 1;
    for(int right=0;right<s.size();++right){

        if(flag[s[right]]){//如果当前的字符是t中的字符,才有后面这一系列的
            //--chars[s[right]];//碰到T中的字符就进行减
            if(--chars[s[right]]>=0){
                ++cnt;//找到了一个满足条件的字符;对于<0的结果不会去++cnt
            }
            cout<<"cnt="<<cnt<<endl;
           // 若目前滑动窗口已包含T中全部字符,
           // 则尝试将l右移, 在不影响结果的情况下获得最短子字符串
            while(cnt==t.size()){
                if(right-left+1<min_size){
                    min_size=right-left+1;
                    min_l=left;
                    cout<<"临时的min_size="<<min_size<<endl;

                }
                if(flag[s[left]] && ++chars[s[left]]>0){//这里写的有问题???chars的这个条件判断出错
                    //++chars[s[left]];  一定注意这个条件,
                    --cnt;//之前忘了写的
                    cout<<"--cnt="<<cnt<<endl;
                }
                ++left;
                cout<<"left="<<left<<endl;
            }
        }
    }
    cout<<"min_l="<<min_l<<"  min_size="<<min_size<<endl;

string res=min_size>s.size()? "":s.substr(min_l,min_size);
cout<<"res="<<res;
    return 0;

输出的结果:这道题目要好好总结

 680.验证回文串II

此题不一样的是可以删除一个字符,这是一个变化点, 这是我第二次做的答案,执行用时好一些。注意flag的使用

class Solution {
public:
    bool validPalindrome(string s) {
        int i=0, j=s.size()-1;
        int flag=0, temp;
        while(i<j){
            if(s[i]==s[j]){
                ++i;
                --j;
            } 
            else{
                flag++;
                break;
            }    
        }
        int start, end;
        start=i;
        end=j;
        if(flag==1){
            start++;
            while(start<end){
                if(s[start]==s[end]){
                    ++start;
                    --end;
                }
                else{
                    cout<<"--"<<endl;
                    flag++;
                    break;
                }
            }
        }
        if(flag==2){
            start=i;
            end=j;
            --end;
            while(start<end){
                if(s[start]==s[end]){
                    ++start;
                    --end;
                }
                else{
                    flag++;
                    break;
                }
            }
        }
        cout<<flag<<endl;
        if(flag==3){
            return false;
        }
        else{
            return true;
        }
    }
};

这篇关于把数组排成最小的数字,划分字母区间,最小覆盖子串,验证回文字符串II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!