🎨程序员面试金典🎨

转自：🔥【github】

判定字符是否唯一

leetcode实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

解题思路

  • 首先想到哈希表统计各字母出现频率，只遍历一次，频率大于1就返回false。
    1
    2
    3
    4
    5
    6
    7
    8
    bool isUnique(string astr) {
        unordered_map<char, int> cnt;
        for (int i = 0; i < astr.size(); ++i) {
            cnt[astr[i]]++;
            if (cnt[astr[i]] > 1) return false;
        }
        return true;
    }
  • 如果面试官不想用哈希表，或者不能用额外的数据结构解题，就用一个整形数组代替来记录26个字母出现次数。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    bool isUnique(string astr) {
        int cnt[26];
        memset(cnt, 0, sizeof(int) * 26);
        for (int i = 0; i < astr.size(); ++i) {
            cnt[astr[i] - 'a']++;
            if (cnt[astr[i] - 'a'] > 1) return false;
        }
        return true;
    }
  • 但是对于这种统计只出现一次，或者两次的题，都能够给位运算符操作
  • 本题的思路是，把每个字母转换成二进制，例如 a-> 0001 b -> 0010 c-> 0100 d->1000一次类推剩下所有字母。
  • 还需要维护一个掩码mask，将遍历过的所有字母的二进制数合并起来(|=运算)，例如遍历了abcd,mask就等于1111,再次碰到a~d,就能通过&发现重复。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    bool isUnique(string astr) {
        int mask = 0;
        for (auto c : astr) {
            int num = 1 << (c - 'a');
            if (mask & num) return false;
            else mask |= num;
        }
        return true;
    }

判定是否互为字符重排

leetcode
给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

解题思路
  • 不用哈希表的方式，记录26个字母出现的频率，同时遍历两个字符串，一个加次数，一个减次数。最后看是否所有字母的次数为0。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        int cnt[26];
        memset(cnt, 0, sizeof(int) * 26);
        for (int i = 0; i < s1.size(); ++i) {
            cnt[s1[i] - 'a']++;
            cnt[s2[i] - 'a']--;
        }
        for (int i = 0; i < 26; ++i) {
            if (cnt[i] != 0 ) return false;
        }
        return true;
    }

URL化

leetcode
URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）

示例:

1
2
输入："Mr John Smith    ", 13
输出："Mr%20John%20Smith"

解题思路

  • 理解题意很重要，在原数组的基础上进行修改，两种思路：从头开始或从尾部开始，既然原字符串在结尾已经给我预留了足够多的空位，那更方便从尾部开始插入。
  • 维护两个指针，一个指向读入数据的位置（字符串真实长度的尾部），一个指向插入数据的位置（原字符串尾部）
  • 读入数据进行判断，是空格，就在尾部连续插入3个字符’0’’2’’%’,否则正常插入读入的数据。
  • 最后，将修改后的结果从字符串中提取出来，substr()从写入指针最后停止的位置开始提取到尾部。
  • substr()小技巧：如果没有指定长度或超出了源字符串的长度，则子字符串将延续到源字符串的结尾
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    string replaceSpaces(string S, int length) {
        int writePos = S.size() - 1;
        for (int i = 0; i < length; i++) {
            int readPos = length - 1 - i;
            if (S[readPos] != ' ') {
                S[writePos--] = S[readPos];
            } else {
                S[writePos--] = '0';
                S[writePos--] = '2';
                S[writePos--] = '%';
            }
        }
        if (writePos >= 0) {
            //S = S.substr(writePos + 1, S.size() - writePos - 1);
            S = S.substr(writePos + 1); 
        }
        return S;
    }

回文排列

leetcode
给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。

解题思路

  • 就是判断一个字符串能否变为一个回文串
  • 统计每个字符出现的次数，偶数次数一定能组成回文，而奇数次数的字符只能有一个。
    遍历每个字符，如果有2个以上包括2个的字母出现的次数为奇数，则不能变为回文。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    bool canPermutePalindrome(string s) {
        map<char, int> cnt;
        for (auto ch : s) {
            cnt[ch]++;
        }
        int res = 0;
        for (auto m : cnt) {
            if (m.second % 2) res++;
            if (res > 1) return false;
        }
        return true;
    }

一次编辑

leetcode
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

示例

1
2
3
4
5
输入: 
first = "pale"
second = "ple"
输出: True

解题思路

  • 能够通过增删换一次操作使两个字符相同的前提一定是，两个字符个数绝对差不超过1.
  • 使用两个指针同时遍历两个字符，字幕相同就继续同时往后遍历
  • 如果发现字母不同，cnt++记录需要操作的次数。
  • 删除操作实质上就是指针跳过这个字符。至于是哪个指针进行跳过，就要就比较哪个字符串比较长，就删除哪个字符串的字符。
  • 如果两个字符串长度相等，就只能进行替换操作，替换完，两个指针是要同时前进的
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    bool oneEditAway(string first, string second) {
        int len1 = first.size(), len2 = second.size();
        if (abs(len1 - len2) > 1) return false;
        int p1 = 0, p2 = 0;
        int cnt = 0;
        while (p1 <= len2 && p2 <= len2) {
            if (first[p1] == second[p2]) {
                p1++,p2++;continue;
            }
            len1 == len2 ? p1++,p2++ : len1 > len2 ? p1++ : p2++;
            cnt++;
            if (cnt > 1) return false;
        }
        return true;
    }

字符串压缩

leetcode
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

示例

1
2
输入："aabcccccaaa"
输出："a2b1c5a3"

解题思路

  • 遍历字符串，先取第一个字符作为当前值，从下标1开始遍历，统计与当前字符相等的个数。
  • 当遍历不相等的字符时，更新当前值和个数
  • 注意：因为每次遍历到不同的字符时，指针都会指向下一个字符，因此当遍历到最后一个字符时，需要跟字符串结尾的\0进行比较，所以遍历边界就不能再是i < s.size()应改为i < size() + 1。让i可以指向\0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
string compressString(string S) {
    if (S.size() <= 1) return S;
    char cur = S[0];
    string res = "";
    for (int i = 1; i < S.size() + 1; ++i) {
        int cnt = 1;
        res += cur;
        while (i < S.size() && S[i] == cur) cnt++, i++;
        cur = S[i];
        res += to_string(cnt);
    }
    return S.size() > res.size() ? res : S;
}

旋转矩阵

leetcode
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
不占用额外内存空间能否做到？

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
  • 最简单的方式就是使用辅助矩阵，只要找到翻转后位置的对应关系即可，第row行变为第col行，第col列变为第n-1-row列（倒数的row列）
  • matrix[j][n-1-i] = matrix[i][j]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        auto newMat = matrix;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                newMat[j][n - 1 - i] = matrix[i][j];
            }
        }
        matrix = newMat;
        return;
    }
  • 如果面试要求原地进行翻转，首先要知道matrix[j][n-1-i] = matrix[i][j]会覆盖掉第2个点，
  • 第一：因此我们需要先旋转第2个点，但第2点又会覆盖第3个点，所以先旋转第3点，第3点会覆盖第4点，第4个点刚好就是第1个点，形成一个循环，这样我们先记录第1个点，将后面得点依次覆盖，即可完成4个点得同时旋转。
  • 第二：因为一次旋转4个点，所以我们需要知道遍历哪些点才能不重复。偶数边矩阵：最左上角的小矩阵，奇数矩阵：因为多了中间一列，所以选择最左上角的小矩阵 + 中间列。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
  • 用对折翻转代替旋转，这种算法除非做过原题，一般是想不到
  • 先水平翻转，再对角线翻转
  • 注意：翻转需要两个元素：1、翻转前后点得对应关系。2、枚举需要遍历的点。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix[i][j], matrix[n - 1 - i][j]);
            }
        }
        // 对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        return;
    }

零矩阵

leetcode
编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

解题思路

  • 暴力法；先全部遍历，找到并记录全部0的行列坐标。
  • 第二次只遍历这些0的位置，模拟操作：往上下左右四个方向进行置0操作。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.size() == 0) return;
        int row = matrix.size();
        int col = matrix[0].size();
        vector<pair<int,int>> indexs;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (matrix[i][j] == 0) {
                    indexs.push_back(pair<int, int>(i, j));
                }
            }
        }

        if (indexs.size() == row * col) return;
        for (auto it : indexs) {
            int i = it.first;
            int j = it.second;
            int i1 = i;
            while (++i1 < row) {
                matrix[i1][j] = 0;
            }
            int i2 = i;
            while (--i2 >= 0) {
                matrix[i2][j] = 0;
            }
            int j1 = j;
            while (++j1 < col) {
                matrix[i][j1] = 0;
            } 
            int j2 = j;
            while (--j2 >= 0) {
                matrix[i][j2] = 0;
            }
        }
    }
  • 同样是先记录所以出现0的行和列，然后第二次遍历时，判断当前行或者列是否是需要置0的
  • 需要两个bool数组，记录每个行或列是否是需要置0的行
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        bool isZeroRow[n], isZeroCol[m];
        memset(isZeroRow, 0, sizeof(bool) * n);
        memset(isZeroCol, 0, sizeof(bool) * m);
        // 统计哪些行，列需要全置位0
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (matrix[i][j] == 0) {
                    isZeroRow[i] = true;
                    isZeroCol[j] = true;
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (isZeroRow[i] || isZeroCol[j]) 
                    matrix[i][j] = 0;
            }
        }
    }

字符串轮转

leetcode
字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。

解题思路

  • 两个思路，一种暴力的方式，旋转s2，判断s1 和s2是否相等，不相等继续旋转s2
  • 使用C库int strcmp(const char* s1, const char* s2)字符串需要转换为char*类型，且strcmp是采用逐位相减来判断的，返回0表示相等，大于0表示大于s1 > s2，
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    bool isFlipedString(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1.empty()) return true;
        int n = s1.size();
        for (int i = 0; i < n; ++i) {
            char temp = s2[n - 1];
            for (int j = n - 1; j - 1 >= 0; --j) {
                s2[j] = s2[j - 1];
            }
            s2[0] = temp;
            if (strcmp(s1.c_str(), s2.c_str()) == 0) return true;
        }
        return false;
    }

  • 思路二：既然是循环字符串，就一定要想到拼接思想，通过s1 + s1 拼接后找是否存在s2子串的方式
  • 找子串有两种方式：1、分割出子串string substr(int index, int count)需要参数位置和个数,返回分割的子串，进行比较
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    bool isFlipedString(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1.empty()) return true;
        int n = s1.size();
        s2 = s2 + s2;
        for (int i = 0; i < n; ++i) {
            if (s1[0] == s2[i] && s1 == s2.substr(i, n)) 
                return true;
        }
        return false;
    }
  • 2、或使用stl库得find函数找子串，找到返回首个字符的下标，否则返回npos
    1
    2
    3
    4
    5
    bool isFlipedString(string s1, string s2) {
        // slt
        if (s1.size() != s2.size()) return false;
        return (s1 + s1).find(s2) != string::npos;
    }

移除重复节点

leetcode
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例

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

解题思路

  • 本题是对未排序的链表进行删重，所以需要先遍历一遍记录不重复的有哪些值。
  • 第二次遍历针对非记录中的进行删除
  • 链表的删除需要前驱，所以head结点我们也需要新建一个前驱，删除结点的操作最好都是枚举遍历前驱，当前结点通过前驱获得。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    ListNode* removeDuplicateNodes(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* pre = dummy;
        unordered_set<int> hash;
        while (pre->next) {
            ListNode* cur = pre->next;	// 获取待删除结点
            if (hash.find(cur->val) == hash.end()) {    // 没有找到
                hash.insert(cur->val);
                pre = pre->next;		// 只有遇到新元素才更新
            } else	
                pre->next = pre->next->next; 
        }
        return dummy->next;
    }

返回倒数第 k 个节点

leetcode
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
注意：本题相对原题稍作改动

示例

1
2
输入： 1->2->3->4->5 和 k = 2
输出： 4

解题思路

  • 两个思路，第一快慢指针法，第二翻转链表，但是时间复杂度相对较高
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int kthToLast(ListNode* head, int k) {
        if (head == NULL) return -1;
        ListNode* slow = head;
        ListNode* fast = head;
        while (k--)
            fast = fast->next;
        while (fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow->val;
    }
  • 翻转链表法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int kthToLast(ListNode* head, int k) {
        ListNode* cur = head;
        ListNode* pre = NULL;
        while (cur) {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        k--;    // 第k个元素，跳k-1次就可以
        while (k--) {
            pre = pre->next;
        }
        return pre->val;
    }

删除中间节点

leetcode
实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。

示例

1
2
输入：单向链表a->b->c->d->e->f中的节点c
结果：不返回任何数据，但该链表变为a->b->d->e->f

解题思路

  • 此题题意难以理解，意思是一般我们删除链表的某一个结点都通过遍历到待删除结点的前驱，通过更改前驱指针进行删除
    本题的目的是，只给你当前待删除的结点指针，完成原地删除操作。
  • 思路是，将当前结点替换为它的后继结点，即更新它的值和next指针
    1
    2
    3
    4
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
  • 结点的本质是结构体，通过将后继的内存内容直接覆盖掉当前待删除结点内存空间完成替换。
    1
    2
    3
    void deleteNode(ListNode* node) {
        *node = *(node->next);
    }

分割链表

leetcode
编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。

示例

1
2
输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8

解题思路

  • 读懂题意就很难，大致目的是根据x值将一个链表分成两条链表，其中一个是大于等于x的值组成的，另一条是小于x的值，分割完后再进行前后拼接。
  • 用到的技巧就是分割和组装链表
  • 新建链表需要得是头结点和用于遍历的指针，插入时用尾插法
  • 组装链表将其中一条链表尾部next指针指向另一条链表的第一个元素，最后在尾部添加NULL完成组装。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    ListNode* partition(ListNode* head, int x) {
        ListNode* small = new ListNode(-1);
        ListNode* big = new ListNode(-1);
        ListNode* cur = head;
        ListNode* smallCur = small;
        ListNode* bigCur = big;
        while (cur) {
            if (cur->val < x) {
                smallCur->next = cur;
                smallCur = smallCur->next;
            } else {
                bigCur->next = cur;
                bigCur = bigCur->next;
            }
            cur = cur->next;
        }
        smallCur->next = big->next;
        bigCur->next = NULL;
        return small->next;
    }

链表求和

leetcode
给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。

示例

1
2
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912

解题思路

  • 两个指针分别遍历两个链表，将其中的数相加，大于10的部分作为进位参与下一轮的求和，个位数即为新结点的值
  • 关键在于边界条件，当其中一条链表遍历结束后，指向了null，因此将它的值全部赋予0，继续参与之后每轮的求和。
  • 当两链表全部遍历结束后，再次判断还有没有剩余的进位，如果有就最后新建一个结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* p1 = l1;
    ListNode* p2 = l2;
    int sum = 0;
    int c = 0;

    ListNode* preHead = new ListNode(-1);
    ListNode* cur = preHead;
    while (p1 || p2) {
        int val1 = p1 == NULL ? 0 : p1->val;
        int val2 = p2 == NULL ? 0 : p2->val;
        sum = val1 + val2 + c;
        c = sum / 10;
        int val = sum % 10;
        ListNode* node = new ListNode(val);
        cur->next = node;
        cur = cur->next;
        if(p1) p1 = p1->next;
        if(p2) p2 = p2->next;
    }

    if (c != 0) {
        ListNode* node = new ListNode(c);
        cur->next = node;
    }

    return preHead->next;
}

回文链表

leetcode
编写一个函数，检查输入的链表是否是回文的。

解题思路

  • 翻转一半的链表进行逐点比较。
  • 先用快慢指针寻找中间点，为了方便奇数偶数链表的统一，我们新建头结点开始遍历。这样当快指针结束时，慢指针正好指向后一半链表的前驱上，无论是否是奇数偶数链表。
  • 翻转链表用了头插法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    bool isPalindrome(ListNode* head) {
        if (!head) return true;
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* slow = dummy;
        ListNode* fast = dummy;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        ListNode* pre = NULL;
        ListNode* cur = slow->next;
        while (cur) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }

        while (head && pre) {
            if (head->val != pre->val) return false;
            head = head->next;
            pre = pre->next;
        }
        return true;
    }

链表相交

leetcode
给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。

解题思路

  • 判断两个链表是否相交，经典做法拼接两个链表，即当第一个链表遍历结束后继续从第二条头部遍历，第二条链表同样如此
  • 这样两个链表相等的长度，当两个指针指向同一块地址时，不是null就是相交点。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return NULL;
        ListNode* p1 = headA;
        ListNode* p2 = headB;
        while (p1 != p2) {
            p1 = p1 == NULL ? headB : p1->next;
            p2 = p2 == NULL ? headA : p2->next;
        }
        return p1; 
    }

环路检测

leetcode
给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。
有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。

解题思路

  • 题目要我们除了要判断是否是环路，还要返回环路的头部结点
  • 判断是否环路使用快慢指针，当快指针追上慢指针时即为环路
  • 寻找头部就需要数学推导，结论就是当快指针追上慢指针后，让快指针从头开始走，步数和慢指针相同，两指针会在环头部相遇。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    ListNode *detectCycle(ListNode *head) {
        if (!head) return NULL;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) { // 有环
                fast = head;
                while (fast != slow) {
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }
        return NULL;
    }

栈的最小值

leetcode
请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

解题思路

  • 维护两个栈，数据栈和扎顶储存当前数据栈中的最小值的最小栈
  • 入栈时判断入栈元素是否比当前数据中的最小值还小，还小就如栈。
  • 出栈时需要判断出栈元素是否刚好就是当前数据中的最小值，是就同步出栈。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    class MinStack {
    public:
        stack<int> data;
        stack<int> minSck;
        MinStack() {}
        
        void push(int x) {
            data.push(x);
            if (minSck.empty()) {
                minSck.push(x);
            } else {
                if (minSck.top() >= x)
                    minSck.push(x);
            }
        }
        
        void pop() {
            if (data.empty()) return;
            if (data.top() == minSck.top()) {
                data.pop();
                minSck.pop();
            } else {
                data.pop();
            }
        }
        
        int top() {
            return data.top();
        }
        
        int getMin() {
            return minSck.top();
        }

化栈为队

leetcode
实现一个MyQueue类，该类用两个栈来实现一个队列。

解题思路

  • 队列是先进先出，栈先进后出，所以通过两个栈反转实现先进先出
  • 出栈的时候先反转栈内的数据，将数据栈全部如辅助栈中，pop的数据就是辅助栈的栈顶元素。
  • 只有当辅助栈弹空时，再继续反转数据栈内的数据进入辅助栈补充
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int pop() {
        if (helpSck.empty()) {
            while (!dataSck.empty()) {
                helpSck.push(dataSck.top());
                dataSck.pop();
            }
        }
        int res = helpSck.top();
        helpSck.pop();
        return res;
    }


    int peek() {
        if (helpSck.empty()) {
            while (!dataSck.empty()) {
                helpSck.push(dataSck.top());
                dataSck.pop();
            }
        }
        return helpSck.top();
    }

栈排序

leetcode
栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。

解题思路

  • 本题相当于对栈内的元素进行排序，维护栈顶到栈底从小到大排序
  • 因此栈顶遇到比它大的数时，先弹出比他小的元素到辅助栈中，直到到他的合适位置后，再将辅助栈内的元素倒入原栈中。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    void push(int val) {
        while(!s1.empty() && s1.top() < val){
            s2.push(s1.top());
            s1.pop();
        }
        s1.push(val);
        while(!s2.empty()){
            s1.push(s2.top());
            s2.pop();
        }
    }

    void pop() {
        if(!s1.empty())
            s1.pop();
    }

    int peek() {
        if(!s1.empty())
            return s1.top();
        return -1;
    }

    bool isEmpty() {
        return s1.empty();
    }