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