每日一题

2025.3.30

栈专题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string makeGood(string s) {
    string res;
    for (char c : s) {
        if (!res.empty() && abs(res.back() - c) == 32) {
            res.pop_back(); // 删除上一个相反大小写的字母
        } else {
            res.push_back(c);
        }
    }
    return res;
}
};

如果栈空，直接插入；如果栈非空，比较当前插入的字符和栈内的字符ascii码差值是否为32，32为大小写关系。

左右元素和的差值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> leftRightDifference(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, 0), right(n, 0), res(n);
        
        for (int i = 1; i < n; ++i)
            left[i] = left[i - 1] + nums[i - 1];
        
        for (int i = n - 2; i >= 0; --i)
            right[i] = right[i + 1] + nums[i + 1];
        
        for (int i = 0; i < n; ++i)
            res[i] = abs(left[i] - right[i]);
        
        return res;
    }
};

非递减数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int cnt = 0;
        for (int i = 0;i<nums.size()-1;i++)
        {
            if (nums[i]>nums[i+1]){
                cnt++;
                if (cnt>1) return false;
                if (i>0 && nums[i-1]>nums[i+1]){
                    nums[i+1] = nums[i];
                }
                else nums[i] = nums[i+1];
            }
        }
        return true;
    }
};

关键在于你要去改，通过当前数的左右两边数来判断是要去改这个数大还是改这个数小，改完之后接着往下去比。
3 4 2 3，到了4，4大于2，发现num[i-1] > num[i+1] ，如果想要满足题目的非递减，那就要把num[i+1] = num[i]，把这个数字改大，现在序列变成了3 4 4 3，到了下一个i，4>3，这时候cnt++，就跳出循环了。
1 4 2 3，到了4，发现要把num[i]改小，所以num[i] = num[i+1]。

2025.3.31

颠倒二进制串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        vector <int> stk;
        for (int i = 0;i<32;i++)
        {
            stk.push_back(n&1);
            n>>=1;
        }
        uint32_t res = 0;
        for (int i = 0;i<32;i++)
        {
            res = (res<<1|stk[i]);
            
        }
        return res;
    }
};

用了位运算，第一个for循环让这整个字符串和1与（1写成二进制是000…001，所以只会剩下最后一位），然后把最后一位插入stk里；第二个for循环先让res左移一位(左移相当于后面补0，0补再多的0还是0)，不然会最后多一个0，因为初始化的时候我们已经给了一个0给他了，然后再和数组进行或运算。

2的幂

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n&(n-1))==0;
    }
};

今天运气真的好，又遇到了一道位运算，而且这个设计的真的很巧妙，以后遇到二进制/幂要想到位运算。 比如8和7，8是1000，7是0111，只要他是2的幂，就一定和他的差与为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <bitset>
using namespace std;

int main() {
    int a, b;
    cout << "输入两个整数：" << endl;
    cin >> a >> b;

    int result = a & b;

    cout << "第一个数 (" << a << ") 的二进制: " << bitset<32>(a) << endl;
    cout << "第二个数 (" << b << ") 的二进制: " << bitset<32>(b) << endl;
    cout << "两个数相与的结果: " << bitset<32>(result) << " (" << result << ")" << endl;

    return 0;
}

我们可以用这个程序来看看二进制出来的结果。

汉明距离

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingWeight(int n) {
        int cnt = 0;
        while(n!=0)
        {
            if (n & 1 == 1) cnt++;
            n >>= 1;
        }
        return cnt;
    }
};

已经初步掌握位运算了，还是挺开心。

赎金信

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int a[26] = {0};
        for (int i = 0; i < magazine.size(); i++) {
            a[magazine[i] - 'a']++;
        }
        for (int i = 0; i < ransomNote.size(); i++) {
            a[ransomNote[i] - 'a']--;
            if (a[ransomNote[i] - 'a'] < 0) return false;
        }
        return true;
    }
};

其实就是字符统计，统计看看资源够不够，但是这一题我一开始犯了一个错误，我定义的是char类型的数组，这有一个很严重的问题，char存储只能-127 ~ 128，如果同一个数多了，比如128，那再遇到下一个这个字母数组的值马上变成-127，问题就在这！
然后是要用字母-‘a’，因为a的ASCII码值为97，z的码值为122，差最多就是25，所以创一个26大小的就可以了。

汉明距离

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int hammingDistance(int x, int y) {
        int cnt = 0;
        int xorR = x^y;
        while (xorR>0)
        {
            cnt += xorR&1;
            xorR>>=1;
        }
        return cnt;
    }
};

就是使用异或，不同位异或结果是1，然后统计1的个数就可以了。
第N个泰波那契数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int tribonacci(int n) {
        if (n==0) return 0;
        if (n==1) return 1;
        if (n==2) return 1;
        
        else
        {
            int a = 0,b=1,c=1;
            for (int i = 3;i<=n;i++)
            {
            int temp = a+b+c;
            a = b;
            b = c;
            c = temp;
            }
            return c;
        }
    }
};

其实就是斐波那契额递归的优化版，用递归太耗费时间了，我们在n大于3的时候用for循环，找到规律f(n) = f(n-3)+f(n-2)+f(n-1)，最后输出f(n)

2025.4.1

有效地山脉数组

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
            int size = arr.size();
            if (size<3) return false;
            int i = 0;
            while (i + 1<size && arr[i]<arr[i+1]) i++;
            if (i==0 || i == size-1) return false;
            while (i + 1<size && arr[i]>arr[i+1]) i++;
            return i == size-1;
        }
    };
  • 先从头开始往上爬，找峰顶
  • 再从峰顶往下走；
  • 最后判断是否正好走到结尾。

元素计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int countElements(vector<int>& nums) {
        vector <int> num (nums);
        sort(num.begin(),num.end());
        int max = num[nums.size()-1];
        int min = num[0];
        int cnnt = 0;
        for (int i = 0 ; i<nums.size() ;i++)
        {
            if (num[i]!=max && num[i]!= min) cnnt++;
        }
        return cnnt;
    }
};

就是去找非最大和非最小的元素。
数字小镇中的捣蛋鬼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums) {
        unordered_map <int,int> count;
        for (int num : nums)
        {
            count[num]++;
        }
        vector <int> res;
        for (auto &a : count)
        {
            if (a.second==2)
            {
                res.push_back(a.first);
            }
        }
        return res;
    }
};

哈希表，键值对的问题。
特别注意：unordered_map不能通过下标去访问，而是通过键去访问数据的
快乐数

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
class Solution {
public:
    int getValue(int n){
        int sum = 0;
        while(n)
        {
            sum += pow(n%10,2);
            n/=10;
        }
        return sum;
    }


    bool isHappy(int n) {
        unordered_set <int> s;
        while(1)
        {
            int sum = getValue(n);
            if (sum==1) return true;
            if (s.find(sum)!=s.end()) return false;
            else s.insert(sum);
            n = sum;
        }
    }
};

find返回的是迭代器的值，迭代器可以理解为一个指向该元素的指针，当迭代器返回的值是a.end()代表没有找到这个元素，所以我们在判断条件中使用s.find(num)得到的是一个迭代器的值，而不是布尔值，如果它不等于s.end()，那就说明已经存在了。 s.end()指向的是最后一个元素的下一个位置
当我们进入无限循环的时候去想想哈希表的思路，哈希表可以快速查找。

只出现一次的数字

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int a : nums)
        {
            res =a^res;
        }
        return res;
    }
};

①任何数和自己异或就是0，最后剩下的那个数就是只出现过一次。
②用map，出现就值+1，去遍历值为1的。
多数元素Ⅱ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int times = nums.size() / 3;
        vector<int> a;
        map<int, int> m;
        for (auto c : nums) {
            m[c]++;
        }
        for (auto &p : m) {
            if (p.second > times) {
                a.push_back(p.first);
            }
        }
        return a;
    }
};

哈希表使用的已经比较熟练了，现在问题在于对map的取键值对语法总是忘记，以后就规范用auto，auto自动推导为迭代器，然后用.访问符就可以访问键/值了。

2025.4.2

同构字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map <char,char> ms,mt;
        for (int i = 0;i<s.length();i++)
        {
            char a = s[i],b = t[i];
            if (ms.count(a)&&ms[a]!=b || mt.count(b)&&mt[b]!=a) return false;
            ms[a] = b;
            mt[b] = a;
        }
        return true;
    }
};

哈希表的运用，双射，如果我在a中找到了这个字符，并且我的映射不等于b中的字符，就return false
单词规律

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
class Solution {
public:
    vector <string> Split(string &s)
    {
        vector<string> words;
        istringstream iss(s);
        string word;
        while(iss>>word)
        {
            words.push_back(word);
        }
        return words;
    }
    
    bool wordPattern(string pattern, string s) {
        unordered_map <char,string> m;
        unordered_map <string,char> m1;
        vector<string> cc = Split(s);
        for (int i = 0;i<pattern.size();i++)
        {
            if (pattern.size()!=cc.size()) return false;
            char a = pattern[i];
            string b = cc[i];
            if (m.count(a)&&m[a]!=b || m1.count(b)&&m1[b]!=a) return false;
            m[a] = b;
            m1[b] = a;
        }
        return true;
    }
};

istringstream 是 C++ 标准库 中的类，用于从字符串中像从流（例如 cin）中一样提取数据。它常用于字符串的“切割”或格式化读取。

  • iss >> word 会跳过空格，自动提取下一个以空格分隔的单词。
  • 也可以提取数字等，比如：int x; iss >> x;
  • 适合用来解析以空格、换行等分隔的字符串数据。
    要保证他是双向映射的，所以需要两个哈希表来维护。

2025.4.9

不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];
        //vector <vector<int>> dp(m,vector<int>(n,1));
        for (int i = 0;i<m;i++)
        {
            for (int j = 0;j<n;j++)
            {
               if (i==0) dp[i][j] = 1;
               else if (j==0) dp[i][j] = 1;
               else dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }
};

我们可以先从一维的动态规划数组理解，斐波那契数列1 1 2 3 5 8……dp[0] = 1，dp[1] = 1,从2开始往后的就是dp[i] = dp[i-1]+dp[i-2]
现在是二维的图，就要去分成小的子问题，用子问题倒推回最难的问题，画一个表格就一目了然了。

看这张图，只能向右或者向下移动，那我们把机器人旁边的格子设为终点，机器人有几条路可以到终点呢？只有一条，机器人斜对角也就是dp[i-1][j-1] = dp[i][j-1] + dp[i-1][j]两种方案合起来。

2025.4.10

移除元素

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.size(); ++fast) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};

用快慢指针法，先判断当前这个数字是不是想要的值，如果不是就让它往后滚动。

反转字符串中的元音字母

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
class Solution {
public:
    bool isvowel(char c)
    {
        c = tolower(c);
        return (c=='a' || c=='e' || c=='i' || c=='o' || c=='u');
    }

    string reverseVowels(string s) {
        int left = 0;
        int right = s.size()-1;
        while(left<right)
        {
            while(right>left && !isvowel(s[left])) left++;
            while(right>left && !isvowel(s[right])) right--;
            if (right>left)
            {
                swap(s[left],s[right]);
                left++;
                right--;
            }
        }
        return s;
    }
};

用双指针来实现，两边都去找元音，都找到了就交换。

2025.4.11

反转链表

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
/**
 * 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 *p = nullptr;
    	ListNode *cur = head;
    	while (cur!=nullptr)
    	{
    		ListNode *temp = cur->next;
    		cur->next = p;
    		p = cur;
    		cur = temp;
		}
		return p;
    }
};

采用头插法，不要自己空想一个头出来！！！！！现在全世界没人比我更懂链表！

2025.4.12

移除链表元素

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
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *p = head;
        ListNode *q = new ListNode();
        ListNode *dummy = new ListNode();
        dummy->next = head;
        q = dummy;
        
        while (p != nullptr) {
            if (p->val == val) {
                ListNode *cur = p->next;
                q->next = cur;  // 这里更新了q指向的节点，跳过p
                delete p;       // 删除p节点
                p = cur;        // p继续前进
            } else {
                p = p->next;
                q = q->next;
            }
        }

        ListNode* newHead = dummy->next;  // 返回新头节点
        delete dummy;  // 删除虚拟头节点
        return newHead;
    }
};

现在应该彻底搞懂链表到底是什么了，其实不是链表的知识不懂，是函数传参出现了问题，这个函数传进来的是一个head节点，它指向链表的头部，而不是传一个链表进来，函数前几行定义了一个虚拟的头节点，让前后两个指针往后遍历。最后返回的时候不能return q，因为q节点已经遍历完链表了啊。

删除链表倒数的第N个节点

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
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode(0,nullptr);
        dummy->next = head;
        ListNode *pre = dummy;
        ListNode *q = dummy;
        int cnt =0;
        while (cnt!=n)
        {
            if (q!=nullptr)
            {
                q = q->next;
            }
            cnt++;
        }
        while(q->next!=nullptr)
        {
            pre = pre->next;
            q = q->next;
        }
        ListNode *toDelete = pre->next;
        pre->next = toDelete->next;
        delete toDelete;
        return dummy->next;
    }
};

现在已经把函数传参的问题解决了，以后要多画图，像今天蓝桥杯画图就解决出来了，然后是找到倒数第N个节点，我们先虚构出一个头节点，让一个指针先走N步，然后两个指针一起往后挪动，如果前面的指针下一个是空，那说明我们后面出发的指针下一位置就是要删除节点了，我们就采用删除节点的方法，创建一个新指针指向要被删除的节点，再把链表连接起来。

2025.4.13

合并两个有序链表

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
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *dummy = new ListNode();
        ListNode *newlink = dummy;
        ListNode *p = list1;
        ListNode *q = list2;
        while (p!=nullptr && q!=nullptr)
        {
            if (p->val >= q->val)
            {
                newlink->next = q;
                q = q->next;
                newlink = newlink->next;
            }
            else if (q->val >= p->val)
            {
                newlink->next = p;
                p = p->next;
                newlink = newlink->next;
            }
        }
        if (p==nullptr)
        {
            newlink->next = q;
        }
        else if (q==nullptr)
        {
            newlink->next = p;
        }
        ListNode *res = dummy->next;
        delete dummy;
        return res;
    }
};

今天对链表的掌握程度更上一层楼了，记住要画图进行需求分析，这样不容易乱，还有在堆内存的释放。

逆波兰表达式求值

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
36
37
38
39
40
41
class Solution {
public:
    int cal(int left,int right,char a)
    {
        switch(a)
        {
            case '+':
                return left+right;
            case '-':
                return left - right;
            case '*':
                return left*right;
            case '/':
                return left/right;
        }
        return 0;
    }

public:
    int evalRPN(vector<string>& tokens) {
        stack <int> s;
        for (auto a : tokens)
        {
            if (a.size()==1&&
                (a[0]=='+'||a[0]=='-'||a[0]=='/'||a[0]=='*'))
                {
                    int right = s.top();
                    s.pop();
                    int left = s.top();
                    s.pop();
                    int val = cal(left,right,a[0]);
                    s.push(val);
                }
            else
            {
                s.push(stoi(a));
            }
        }
        return s.top();
    }
};

逆波兰表达式也就是后缀求值，遇到数字就入栈，遇到符号就从栈里面取出两个数字进行运算。先pop出来的值作为等号右边的值，后pop出来的是等号左边的值。

排序数组
希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for (int gap = nums.size()/2;gap>0;gap/=2)
        {
            for (int i = gap;i<nums.size();i++)
            {
                int val = nums[i];
                int j = i - gap;
                for ( ; j>=0 ; j-=gap)
                {
                    if (val >= nums[j])
                    {
                        break;
                    }
                    nums[j+gap] = nums[j];
                }
                nums[j + gap] = val;
            }
        }
        return nums;
    }
};

后面慢慢更其它的。

2025.4.14

反转字符串中的单词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string reverseWords(string s) {
        istringstream ss(s);
        vector<string> res;
        string word;
        while (ss>>word)
        {
            res.push_back(word);
        }
        string sres;
        if (res.size()==1) return res[0];
        else
        {
            for (int i = res.size()-1;i>0;i--)
            {
                sres += res[i]+' ';
            }
            sres +=res[0];
        }
        return sres;
    }
};

用istringstream读取原字符串，然后将分割出来的单词插入进数组，反向遍历。
删除字符串中的所有相邻重复项

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 Solution {
public:
    string removeDuplicates(string s) {
        stack <char> res;
        for (int i = 0;i<s.length();i++)
        {
            if(res.empty())
            {
            	res.push(s[i]);	
			}
			else
			{
				if (res.top()==s[i])
            	{
                res.pop();
            	}
            	else
            	{
                res.push(s[i]);
            	}
			}
            
        }
        string ans;
        while(!res.empty())
        {
            ans += res.top();
            res.pop();
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

栈的应用，很简单。
相交链表

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int cnt1 = 0,cnt2 = 0;
        ListNode *p = headA;
        ListNode *q = headB;
        while (p!=nullptr)
        {
            cnt1++;
            p = p->next;
        }
        while (q!=nullptr)
        {
            cnt2++;
            q = q->next;
        }
        if (cnt1 >= cnt2)
        {
            p = headA;
            q = headB;
            int dif = cnt1 - cnt2;
            while (dif > 0)
            {
                p = p->next;
                dif--;
            }
            while (p!=nullptr && q!=nullptr)
            {
                if (p==q)
                {
                    return p;
                }
                q = q->next;
                p = p->next;
            }
        }
        else if (cnt2 > cnt1)
        {
            p = headA;
            q = headB;
            int dif1 = cnt2 - cnt1;
            while (dif1 > 0)
            {
                q = q->next;
                dif1--;
            }
            while (p!=nullptr && q!=nullptr)
            {
                if (p==q)
                {
                    return q;
                }
                p = p->next;
                q = q->next;
            }
        }
        return nullptr;
    }
};

相交链表很有意思，在它们没有相交之前，如果第一个链表比第二个链表长，那就让长链表的指针先往下走这些差值，然后开始进行比较。
字符串相加

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
class Solution {
public:
    string addStrings(string num1, string num2) {
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        int maxsize = max(num1.size(),num2.size());
        vector <int> res(maxsize+1);
        for (int i = 0;i<maxsize;i++)
        {
            int a = i < num1.size() ? num1[i] - '0' : 0;
            int b = i < num2.size() ? num2[i] - '0' : 0;
            res[i] += a + b;
        }
        for (int i = 0;i<maxsize-1;i++)
        {
            if (res[i]>=10)
            {
                res[i+1] += (res[i])/10;
                res[i]%=10;
            }
        }
        string resS;
        int j = res.size()-1;
        while(j>0&&res[j]==0) j--;
        for (;j>=0;j--)
        {
            resS += to_string(res[j]);
        }
        
        return resS;
    }
};

其实就是在问你，如果超出了long long范围的加法，你怎么办？
用两个字符串来倒序相加，加进结果数组，如果这个数字大于等于10表明要进位，那就/=10，然后留下进位后的数，最后找前导0，找第一个非0元素，没找到就一直–

2025.4.15

排序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector <int> nums;
        ListNode *p = head;
        while (p!=nullptr)
        {
            nums.push_back(p->val);
            p = p->next;
        }
        if (nums.size()==0) return head;
        sort(nums.begin(),nums.end());
        ListNode *q = new ListNode();
        ListNode *dummy = q;
        for (int num : nums)
        {
            dummy->next = new ListNode(num);
            dummy = dummy->next;
        }
        return q->next;
    }
};

排序用快排，先将链表中的所有数字取出来放到vector里，然后sort排序，最后使用for (int)遍历，不要用i来遍历，因为vector会自动扩容

2025.4.16

独一无二的出现次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map <int,int> m;
        for (auto a:arr)
        {
            m[a]++;
        }
        for (auto a:m)
        {
            for (auto b:m)
            {
                if (a.first!=b.first && a.second==b.second)
                {
                    return false;
                }
            }
        }
        return true;
    }
};

用哈希表存储每一个数字出现的次数，然后两重循环遍历个数。
第一个出现两次的字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    char repeatedCharacter(string s) {
        unordered_map<char,int> m;
        for (auto a:s)
        {
            auto it = m.find(a);
            if (it==m.end())
            {
                m.emplace(a,1);
            }
            else return a;
        }
        return ' ';
    }
};

思路：去遍历哈希表里是否有过这个字母（数字），如果没有，就把它添加进去，如果有，就说明是我们刚刚添加过的，它就是第二次出现的！
数组中第k个最大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> q;
        for (int i = 0;i<k;i++)
        {
            q.push(nums[i]);
        }
        for (int i = k; i<nums.size();i++)
        {
            if (nums[i]>q.top())
            {
                q.pop();
                q.push(nums[i]);
            }
        }
        return q.top();
    }
};

使用优先队列来实现，默认的优先队列是一个大顶堆，我们用大根堆来找前k个最小的数，如果想要设置为小根堆，需要priority_queue<int,vector,greater>，这是去找前k个最大的数；最后我们return q.top()即可得到第k个最大/最小的数

2025.4.18

树的前序、中序、后续遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void InOrder(TreeNode *node,vector<int> &ans)
    {
        if (node!=nullptr)
        {
            InOrder(node->left,ans);
            ans.push_back(node->val);
            InOrder(node->right,ans);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        InOrder(root,ans);
        return ans;
    }
};

也是终于进入到树了，采用递归的思想去解决问题。

二叉树的层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void dfs(TreeNode *node,int level,vector<vector<int>>&ans)
    {
	    if (node==nullptr) return;
    	if (level == ans.size()) ans.push_back({});
    	ans[level].push_back(node->val);
    	dfs(node->left,level+1,ans);
	    dfs(node->right,level+1,ans);
    }

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        dfs(root,0,ans);
        return ans;
    }
};

这里使用的是vector<vector>,使用ans.size()返回的是这个二维数组的（行）层数，一开始行数为0，就创建一行，接下来递归调用，在当前level层里push node的数值。

子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> res;
        void Res(int i,vector<int> &nums,vector<int> &path)
        {
            if (i==nums.size())
            {
                res.push_back(path);
                return;
            }
            else
            {
                path.push_back(nums[i]);
                Res(i+1,nums,path);
                path.pop_back();
                Res(i+1,nums,path);
            }
        }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> path;
        Res(0,nums,path);
        return res;
    }
};

今天开始学习回溯算法，回溯其实就是一直递归，递归到了子集树的叶子节点就处理这个子集，如果没有递归到这个子集，就处理选择或者不选择