面试题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;
}
}
};