[leetcode]数据结构-线性表

线性表简单题

（简单）删除链表中重复元素

给定一个已排序的链表的头 head（注意是无头结点的链表，上来第一个结点就是存放第一个元素） ， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表 。

示例 1：

输入：head = [1,1,2] 输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3] 输出：[1,2,3]

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) { //删除链表中重复的元素
        ListNode* cur = head; //当前节点
        while (cur && cur->next) { //当前节点和下一个节点都不为空
            if (cur->val == cur->next->val) { //如果当前节点的值和下一个节点的值相等
                cur->next = cur->next->next; //当前节点的下一个节点指向下下个节点
            } else {
                cur = cur->next; //当前节点指向下一个节点
            }
        }
        return head; //返回头节点
    }
};

（简单）反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2] 输出：[2,1]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 反转链表
        ListNode* pre = nullptr; // 前驱节点
        ListNode* cur = head; // 当前节点
        while (cur != nullptr) { // 遍历链表
            ListNode* next = cur->next; // 保存下一个节点
            cur->next = pre; // 反转
            pre = cur; // 更新pre
            cur = next; // 更新cur
        }
        return pre;
    }
};

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None # 前驱节点
        cur = head # 当前节点
        while cur: # 遍历链表
            next = cur.next # 保存下一个节点
            cur.next = pre # 反转
            pre = cur # 更新pre
            cur = next # 更新cur
        return pre

（中等）旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4 输出：[2,0,1]

首先我们要知道，在经过旋转之后最终的头结点是哪一个，我们只需要断掉对应头结点的指针即可，最后返回头结点，就是旋转之后的链表了。

struct ListNode* rotateRight(struct ListNode* head, int k){
    if(head == NULL || k == 0) return head;   //如果给进来的链表是空的，或者说k为0，那么就没必要再继续了
    struct ListNode * node = head;
    int len = 1;
    while (node->next) {   //先来算一波链表的长度
        node = node->next;
        len++;
    }
      if(k == len) return head;   //如果len和k长度一样，那也没必要继续了
  
    node->next = head;   //将链表连起来变成循环的，一会再切割
    int index = len - k % len;  //计算头结点最终位置
  
      node = head;
    while (--index) node = node->next;
    head = node->next;    //找到新的头结点
    node->next = NULL;   //切断尾部与头部
    return head;  //返回新的头结点
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
                //特判
        if (head == nullptr || head->next == nullptr || k == 0) return head;
        //计算链表长度
        int len = 0;
        ListNode* p = head;
        while (p != nullptr) {
            len++;
            p = p->next;
        }
        //计算实际需要移动的次数
        k = k % len;
        if (k == 0) return head;
        //找到倒数第k+1个结点
        ListNode* q = head;
        for (int i = 0; i < len - k - 1; i++) {
            q = q->next;
        }
        //找到最后一个结点
        ListNode* r = head;
        while (r->next != nullptr) {
            r = r->next;
        }
        //进行旋转
        r->next = head;
        head = q->next;
        q->next = nullptr;
        return head;
    }
};

（简单）有效的括号

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

有效字符串需满足：

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

示例 1：

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

示例 2：

输入：s = “(]” 输出：false

题干很明确，就是需要我们去对这些括号完成匹配，如果给定字符串中的括号无法完成一一匹配的话，那么就表示匹配失败。实际上这种问题我们就可以利用栈这种数据结构来解决，我们可以将所有括号的左半部分放入栈中，当遇到右半部分时，进行匹配，如果匹配失败，那么就失败，如果匹配成功，那么就消耗一个左半部分，直到括号消耗完毕。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = [] # 栈  val stack = Stack<Char>() , kotlin
        for i in s:   for (i in s) {
            if i == '(':    if (i == '(') {
                stack.append(')')   stack.push(')')
            elif i == '[':
                stack.append(']')
            elif i == '{':
                stack.append('}') 
            elif stack == [] or stack.pop() != i:  else if (stack.isEmpty() || stack.pop() != i) {
                return False
        return stack == [] # 栈空,说明所有的左括号都有匹配的右括号  return stack.isEmpty()

#include <stack>
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (char c : s) { //元素类型 元素变量:数组名/容器名) 用来遍历数组/容器
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                if (st.empty()) return false;
                char top = st.top();
                st.pop();
                if (c == ')' && top != '(') return false;
                if (c == ']' && top != '[') return false;
                if (c == '}' && top != '{') return false;
            }
        }
        return st.empty();
    }
};

（简单）第 k 个缺失的正整数

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。

请你找到这个数组里第 k 个缺失的正整数。

示例 1：

输入：arr = [2,3,4,7,11], k = 5
输出：9
解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        if(arr.empty() || k < arr[0]) return k; //提前返回
       int left = 0, right = arr.size() - 1;
       while(left <= right){
           int mid = left + (right - left) / 2;
           if(arr[mid] - mid - 1 < k) left = mid + 1;
           else right = mid - 1;
       }
       return k + left; 
        // int i = 0;
        // while(i < arr.size() && arr[i] - i - 1 < k) i++; //线性扫描
        // return k + i;

        // for (int i = 0; i < arr.size(); ++i)  if(arr[i] <= k) k++;//每出现一个 <= k 的数字, 意味着少了一个缺失的数字, k+1
        // return k;
    }
};