刷题中级 - milkandbread/summary-interview GitHub Wiki

1 根据每日气温列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> st1;
        stack<int> st2;//保存st1对应的天数
        vector<int> results(T.size());
        for(int i=T.size()-1;i>=0;i--){
            int days=1;
            while(!st1.empty()&&st1.top()<=T[i]){
                st1.pop();
                days+=st2.top();
                st2.pop();
                
            }
            results[i] = st2.empty()? 0:days;
            st1.push(T[i]);
            st2.push(days);
          
        }
        return results;
    }
};

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int i=0,j=0;
        vector<int> vec;
        int flag =0;

        for(i=0;i<T.size();i++)
        {
            for(j=i+1;j<T.size();j++)
            {
                if(T[i]<T[j])
                {
                    vec.push_back(j-i);
                    break;
                }
            }
            if(T[i]>=T[j])
            {
                vec.push_back(0);
            }
        }
        return vec;
    }
};

2 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7] 输出: 49

class Solution {
public:
    int maxArea(vector<int>& height) {
        int max = 0;
        int i=0;
        int j = height.size()-1;
        while(i<j)
        {
            int min = height[i]>height[j]?height[j]:height[i];
            int tmp = min*(j-i);
            if(tmp>max)
            {
                max = tmp;
            }
            if(height[i]>height[j])
            {
                j--;
            }
            else 
            {
                i++;
            }
        }
        return max;
    }
};

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode vHead(0);
        ListNode *p = &vHead;
        int flag = 0;
        while (l1 || l2 || flag) {
            int tmp = 0;
            if (l1 != nullptr) tmp += l1->val;
            if (l2 != nullptr) tmp += l2->val;
            tmp += flag;
            
            flag = tmp / 10;
            tmp %= 10;
            
            ListNode *next = l1 ? l1 : l2;
            if (next == nullptr) {
                next = new ListNode(tmp);
            }
            next->val = tmp;
            
            p->next = next;
            p = p->next;
            l1 = l1 ? l1->next : nullptr;
            l2 = l2 ? l2->next : nullptr;
        }
        return vHead.next;
    }
};

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        struct ListNode *p, *q;
    p = q = head;
    n++;
    while (n-- && q)
        q = q -> next;
    if (n == 0)//要删除的是首结点
        return head -> next;
    while (q){
        p = p -> next;
        q = q -> next;
    }
    p -> next = p -> next -> next;
    return head;
    }
};

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

思路：定义两个变量left和right分别表示剩余左右括号的个数。如果在某次递归时，左括号的个数大于右括号的个数，说明此时生成的字符串中右括号的个数大于左括号的个数，即会出现')('这样的非法串，所以这种情况直接返回，不继续处理。如果left和right都为0，则说明此时生成的字符串已有3个左括号和3个右括号，且字符串合法，则存入结果中后返回。如果以上两种情况都不满足，若此时left大于0，则调用递归函数，注意参数的更新，若right大于0，则调用递归函数，同样要更新参数。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
       vector<string> res;
          generateParenthesisDFS(n, n, "", res);
          return res;
      }
      void generateParenthesisDFS(int left, int right, string out, vector<string> &res) {
          if (left > right) return;
         if (left == 0 && right == 0) res.push_back(out);
         else {
             if (left > 0) generateParenthesisDFS(left - 1, right, out + '(', res);
             if (right > 0) generateParenthesisDFS(left, right - 1, out + ')', res);
         } 
    }
};

刷题中级 - milkandbread/summary-interview GitHub Wiki

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️