leetcode刷题记录---2019.9.7 int转二进制存string数组,驼峰匹配字符串（逻辑简单），无重复字符最长字串（数组hash），优先级队列合并k有序链表链表求和对称二叉树

95 阅读 0 评论 63 点赞

我是靠谱客的博主踏实煎饼，最近开发中收集的这篇文章主要介绍leetcode刷题记录---2019.9.7 int转二进制存string数组,驼峰匹配字符串（逻辑简单），无重复字符最长字串（数组hash），优先级队列合并k有序链表链表求和对称二叉树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

综述

子串能表示从1到n的二进制串（int转化成二进制并存string）

驼峰式匹配（对vector中的每一个query遍历，与模式串的每个字符依次匹配）

无重复字符的最长子串（m[s[i]]为0是指第i个元素还没有出现过，不为0表示已经出现过的位置，与左边界进行比较，选择更新边界或者更新长度）

合并k个排序链表（优先级队列如何使用？运算符重载，链表操作）

两数之和（注意两数是逆序存放，先求长度，再在短的后面补0）

对称的二叉树（1.自己定义一种遍历方式，对称的前序遍历，即DRL。2.考虑nullptr进去，因为如果每个节点都相同，两个遍历结果也相同了。都不为空true，有一个为空false，两值不同false，递归左右&&右左）

1.子串能表示从1到n数字的二进制串

参考：https://blog.csdn.net/qq_27060423/article/details/88946491

题目描述：给定一个二进制字符串（0，1数组）和一个整数N，如果从1到N这些数字的二进制表示全是给定二进制串的子串，那么返回true。

示例 1：

输入：S = "0110", N = 3
输出：true

示例 2：

输入：S = "0110", N = 4
输出：false

string::npos:表示一个常数，size_t的最大值，容器用这个来表示不存在的位置。

不管和哪个运算符一起使用，p&0x01必须加括号！！！

思路：针对每一个数字，先进行转化成二进制并放入string数组:

string temp("");

while(k){temp+=((k&0x01)+'0');k = k>>1;}

调整放入的顺序：reverse(temp.begin(),temp.end());

判断是否能够在给定的S中找到，if(S.find(temp) == string::npos){return false;}

class Solution {
public:
    bool queryString(string S, int N) {
        //if(S.length()<1||S.length()>1000||N<1||N>1000000000) return false;
        for(int i =0;i<=N;i++){
            string temp("");
            int k = i;
            while(k){
                temp+= ((k&0x01)+'0');
                k = k>>1;
            }
            reverse(temp.begin(),temp.end());
            if(S.find(temp) == string::npos){
                return false;
            }
        }
        return true;
    }
};

2.驼峰式匹配

题目描述：给定两个参数，第一个参数是queries，vector数组，里面存放着匹配串。

参考：https://blog.csdn.net/qq_27060423/article/details/89433142

第二个参数是，给定的模式串。

规则是：可以往模式串中插入小写字母，可以在任何位置插入任意个包括0个。判断vector中存放的匹配串能否被匹配到。

返回值是一个vector，存放每个匹配串是否可以被匹配，true或者false

示例 1：

输入：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
输出：[true,false,true,true,false]
示例：
"FooBar" 可以这样生成："F" + "oo" + "B" + "ar"。
"FootBall" 可以这样生成："F" + "oot" + "B" + "all".
"FrameBuffer" 可以这样生成："F" + "rame" + "B" + "uffer".
示例 2：

输入：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
输出：[true,false,true,false,false]
解释：
"FooBar" 可以这样生成："Fo" + "o" + "Ba" + "r".
"FootBall" 可以这样生成："Fo" + "ot" + "Ba" + "ll".
示例 3：

输出：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT"
输入：[false,true,false,false,false]
解释：
"FooBarTest" 可以这样生成："Fo" + "o" + "Ba" + "r" + "T" + "est".

思路：1.把核心抽象出去。2.注意vector<bool>类型，如何赋值？必须用push_back。

3.核心是判断一个字符串和模式串是否匹配

遍历字符串for(int i = 0;i<str.length();++i)

如果遇到和模式串中第一个字符一样的，模式串移动到下一个。if(k<pattern.length()&&pattern[k] == str[i]){k++;}

如果不一样，并且字符串中为大写字符，直接false。else{if(strt[i]<'Z'&&str[i]>'A') return false;}

遍历结束后，如果模式串刚好遍历完一遍if(k == pattern.length())说明匹配！

最后如果k不与模式串长度相等，false；

class Solution {
public:
     bool panduan(string str,string pattern){
        int k = 0;
        for(int i = 0;i<str.length();++i){
            if(str[i] == pattern[k]&&k<pattern.length()){
                k++;
            }else{
                if(str[i]>='A'&&str[i]<='Z') return false;
            }
        }
        if(k == pattern.length()) return true;
        return false;
    }   
    vector<bool> camelMatch(vector<string>& queries, string pattern) {
        vector<bool> result;
        for(int i = 0;i<queries.size();++i){
            bool temp = panduan(queries[i],pattern);
            result.push_back(temp);
            
        }
        return result;
    }
   
    
};

3.无重复字符的最长子串

题目描述：给定一个字符串，求出不含有重复字符的最大子串的长度

参考：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-gpe3dbj/

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

思路：代码很简单，但是很难想。

本题分三步实现（利用数组实现hash查找）：

1.遍历，并判断字符是否已出现及位置是否合理。if(m[s[i]]!=0&&m[s[i]]>left)。不合理的话更新边界

2.如果没出现或者出现的位置在边界左边，更新子串长度。else mlen = max(mlen,i-left+1)

3.更新该字符在字符串中的位置。偏移一个。。m[s[i]] = i+1;

数组里面存放的是每个字符在字符串中的位置i。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int m[256] = {0};        //用来存储每个字符在字符串中的位置，有256个字符
        int mlen = 0;            //记录结果
        int left = 0;            //左边界
        for(int i = 0;i<s.length();++i){  
            if(m[s[i]]!=0 && m[s[i]]>left) left = m[s[i]];  //如果该字符出现过，并且出现在左边界后面，即s[left,i]之间。。那么“不重复子字符串”的条件就无法满足。。更新左边界
            else mlen = max(mlen,i-left+1);    //否则，说明该字符未出现过或者不在当前统计子字符串，更新长度，i-left+1
            m[s[i]] = i+1;        //更新该字符在字符串中的位置。。。。为0，没出现过，，所以整体加一
        }
        return mlen;
    }
};

4.合并k个排序链表

题目描述：合并k个排好序的链表，返回合并后的链表，分析时间空间复杂度。

本题用到了优先级队列，需明确优先级队列的使用方法。

priority_queue<元素类型，容器类型，比较方式（默认为<,可通过重载默认运算符的方式传入）>

思路：1.定义优先级队列比较方式。并声明优先级队列。

2.k个头节点入队，定义返回指针head。

3.定义p，q指针，一个指向队首元素，一个负责连接起来。

#include <queue>

class Solution {
public:
    //最小优先级优先
    struct ListNodeCompare{
        bool operator()(ListNode* a,ListNode* b){
            if(a== NULL &&b!=NULL){
                return false;
            }
            if(a!=NULL && b== NULL){
                return false;
            }
            return a->val>b->val;
            
        }
        
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()){
            return NULL;
        }
        //优先队列
        priority_queue<ListNode*,vector<ListNode*>,ListNodeCompare> queue;
        for(auto p:lists){
            if(p != NULL){
                queue.push(p);
            }
        }
        ListNode* p = NULL;
        ListNode* q = NULL;
        ListNode* head = NULL;
        if(!queue.empty()){
            head = queue.top();
            queue.pop();
        }
        if(head->next != NULL){
            queue.push(head->next);
        }
        p = head;
        while(!queue.empty()){
            q = queue.top();
            queue.pop();
            if(q->next != NULL){
                queue.push(q->next);
            }
            p->next = q;
            p = p->next;
        }
        return head;
    }
};

5.两数相加

题目描述：给定两个非空的链表，用来表示非负整数，他们各自的位数是按照逆序

每个节点智能存1位数字，如果把这两个数加起来，会返回一个新的链表来表示他们的和。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

思路：

1.获取每个链表的长度。

2.在短的链表的后面补零。

3.对齐相加，考虑进位。

//先统计两个链表的长度，短的补0
        ListNode* p = l1;
        ListNode* q = l2;
        int len1 = 1;
        int len2 = 1;
        while(p->next!=nullptr){len1++;p = p->next;}
        while(q->next!=nullptr){len2++;q = q->next;}
        if(len1>len2){int len = len1-len2;while(len){q->next =new ListNode(0);q = q->next;len--;cout<<"1111111"<<endl;}}
        if(len1<len2){int len = len2-len1;while(len){p->next =new ListNode(0);p = p->next;len--;cout<<"222222"<<endl;}}
        ListNode* l3 = new ListNode(-1);
        ListNode* w = l3;
        p = l1; q = l2;
        bool count = false;
        int i = 0;
//对齐相加
        while(p!=nullptr&&q!=nullptr){
            i = p->val+q->val+count;
            w->next = new ListNode(i%10);
            count = i>=10?true:false;
            w = w->next;
            p = p->next;
            q = q->next;
        }
//如果最后有进位，加一
        if(count){
            w->next = new ListNode(1);
            w = w->next;
        }
        return l3->next;
}

6.对称的二叉树

题目描述：给定一棵二叉树，判断其是否是对称二叉树，对称的定义是，如果这棵二叉树和他的镜像一样，那么他是对称的。

思路：前序遍历和改进的前序遍历结果是否一样？即DLR和DRL结果是否一样？并且需要把所有nullptr考虑进来！

bool DuichenCore(treeNode* pNode1, treeNode* pNode2) {
	if (pNode1 == nullptr&&pNode2 == nullptr) { return true; }
	if (pNode1 == nullptr || pNode2 == nullptr) { return false; }
	if (pNode1->data != pNode2->data) { return false; }
	return DuichenCore(pNode1->pLeft, pNode2->pRight)&&DuichenCore(pNode1->pRight,pNode2->pLeft);
}

bool isDuichen(treeNode* root) {
	return DuichenCore(root, root);
}