LeetCode[14/20/21]最长公共前缀、有效的括号、合并两个有效链表C/C++——第二天

题目描述[简单]：
编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1：

输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”
示例 2：

输入：strs = [“dog”,“racecar”,“car”]
输出：“”
解释：输入不存在公共前缀。

遍历strs数组，通过一个for先遍历第一层，然后通过for遍历第二层，使得strs变成一个二位数组，一个单词占一行，我们只需要遍历第一个元素的字符串个数就ok了，因为我们寻找的公共前缀，没必要搜寻超过第一个元素长度的字符 了，没有意义。
当我们遍历到最后一列时就可以停止便利，亦或者时当遍历到第j列时，第i行于第一个字符串不同，也要停止再遍历了。
最后要返回字符串，可以利用substr()函数。

class Solution {
public:
    string longestCommonPrefix(vector& strs) {
 if (strs.size() == 0) {//判断字符串是否为空
     return "";
    }
    for (int i = 0; i < strs[0].size() ; ++i) {
        char c = strs[0][i];
        for (int j = 1; j < strs.size() ; ++j) {
            if (i == strs[j].size() || strs[j][i] != c) {
                return strs[0].substr(0, i);
                }
            }
        }
        return strs[0];
    }
};

题目简述[简单]：
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”
输出：true

实例2：
输入：s = “(]”
输出：false

这种判断是否成对出现的用栈是最方便的，栈的思想就是先进后出。当遇到匹配的括号对时，我们将这对括号从栈中删除，即让其出栈，如果最后栈为空，那么它是有效的括号，反之不是。

使用了哈希表来判断是否能够形成括号，从而决定进行入栈操作还是出栈操作。

class Solution {
public:
    bool isValid(string s) {
      unordered_map m{{'(',1},{'[',2},{'{',3},
                                {')',4},{']',5},{'}',6}};
        stack st;
        bool istrue = true;
        for(char c:s){
            int flag = m[c];
            if(flag >= 1 && flag<=3) 
               st.push(c);
            else if(!st.empty()&&m[st.top()]==flag-3) 
               st.pop();
            else {
                istrue=false;
                break;}
        }
        if(!st.empty()) istrue=false;
        return istrue;
    }
};

1. 首先建立哈希表,依次保存三个不同的开括号(对应键值分别为1,2,3)与三个不同的闭括号(对应键值分别为4,5,6),栈(只放入开括号,若遇到对应的闭括号,则出栈)，还要设定一个bool值,判断是否顺利入栈(比如第一个就是闭括号,必然错误),且开始默认为真。
2. 通过for遍历string字符串
   1. 若遇到开括号,入栈
   2. 在栈非空时,且遇到对应闭括号,出栈
   3. 否则(此时隐含表达为’这是个闭括号’),则bool值为假
3. 如果栈非空时,则说明闭括号少了,bool为假
4. 返回bool值

题目描述[容易]：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

实例1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

递归：顾名思义，自己调用自己。
当两个链表都为空时，表示我们对链表已合并完成，此时停止递归。
递归条件：通过判断 list1 和 list2 头结点哪个更小，然后将较小结点的 next 指针指向其余结点的合并结果。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
       if (list1 == NULL) {//如果list1为空，就只用输出list2
            return list2;
        }
        if (list2 == NULL) {//如果list2为空，就只用输出list1
            return list1;
        }
        if (list1->val <= list2->val) {//如果list1的头结点小于list2
            list1->next = mergeTwoLists(list1->next, list2);//list1的下一个结点指向lIst1->next和 list2 中值较小的那个结点 相当于每次拆除 list1，list2 链表首节点中值最小的那个首结点，跟前面拼接过的新链表相连，直到 list1 和 list2 当中有一个为空，就将剩余的另一个链表接到新链表后面。
            return list1;
        }
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
};

时间复杂度：O(m+n)