力扣题目训练（10）

2024年2月3日力扣题目训练

2024年2月3日第十天编程训练，今天主要是进行一些题训练，包括简单题3道、中等题2道和困难题1道。惰性太强现在才完成，不过之后我会认真完成的。

434. 字符串中的单词数

链接: 单词数
难度： 简单
题目：

运行示例：

思路：
判断单词个数也就是判断中间有多少个空格即可。
代码：

class Solution {
public:
    int countSegments(string s) {
        if(s.size() == 0) return 0;
        bool isblack = false;
        int count = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == ' ' ){
                if(!isblack && i != 0)   count++;
                isblack = true;
            }else isblack = false;
        }
        if(!isblack) count++;
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

441. 排列硬币

链接: 排列硬币
难度： 简单
题目：

运行示例：

思路：
根据等差数列求和公式可知，前 kkk 个完整阶梯行所需的硬币数量为
total=k×(k+1)/2
因此，这道题可以通过二分查找计算 n 枚硬币可形成的完整阶梯行的总行数。
代码：

class Solution {
public:
    int arrangeCoins(int n) {
        int left = 1;
        int right = n;
        while(left < right){
            int mid = (right - left + 1) / 2 + left;
            if((long long)  mid*(mid+1)/2 <= (long long)n) left = mid;
            else right = mid-1;
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

448. 找到所有数组中消失的数字

链接: 消失的数字
难度： 简单
题目：

运行示例：

思路：
这道题本质就是计数,所以只需要遍历计数即可。
代码：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> temp(nums.size(),0);
        vector<int> ans;
        for(int i = 0; i < nums.size(); i++){
            temp[nums[i]-1]++;
        }
        for(int i = 0; i < temp.size(); i++){
            if(temp[i] == 0) ans.push_back(i+1);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

116. 填充每个节点的下一个右侧节点指针

链接: 填充节点
难度： 中等
题目：

运行示例：

思路：
图的深拷贝是构建一张与原图结构，值均一样的图，但是其中的节点不再是原来图节点的引用。
这道题可以利用深度优先遍历解决。
代码：

class Solution {
public:
    unordered_map<Node*,Node*> visited;
    Node* cloneGraph(Node* node) {
        if(node == NULL) return node;
        if(visited.find(node) != visited.end()){
            return visited[node];
        }
        Node* cloneNode = new Node(node->val);
        visited[node] = cloneNode;
        for(auto neighbor : node->neighbors){
            cloneNode->neighbors.push_back(cloneGraph(neighbor));
        }
        return cloneNode;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

143. 重排链表

链接: 重排链表
难度： 中等
题目：

运行示例：

思路：
可以看出这个题是比较典型的题目，需要利用寻找链表中点 + 链表逆序 + 合并链表这几个点。
代码：

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next != NULL && fast->next->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = NULL;
        ListNode* curr = head;
        while(curr != NULL){
            ListNode* p = curr->next;
            curr->next = prev;
            prev = curr;
            curr = p;
        }
        return prev;
    }

    void mergeList(ListNode* l1, ListNode* l2) {
        ListNode* l1_tmp;
        ListNode* l2_tmp;
        while(l1 != NULL && l2 != NULL){
            l1_tmp = l1->next;
            l2_tmp = l2->next;
            l1->next = l2;
            l1 = l1_tmp;
            l2->next = l1;
            l2 = l2_tmp;
        }
    }

    void reorderList(ListNode* head) {
        if(head == NULL) return;
        ListNode*mid = middleNode(head);
        ListNode*l1 = head;
        ListNode*l2 = mid->next;
        mid->next = NULL;
        l2 = reverseList(l2);
        mergeList(l1,l2); 
    }
};
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

68. 文本左右对齐

链接: 文本左右对齐
难度： 困难
题目：

运行示例：

思路：
这道题就是根据要求进行判断添加空格即可。
代码：

class Solution {
public:
     string blank(int n) {
        return string(n, ' ');
    }
    string join(vector<string> &words, int left, int right, string sep) {
        string s = words[left];
        for (int i = left + 1; i < right; i++) {
            s += sep + words[i];
        }
        return s;
    }
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> ans;
        int right = 0; 
        int n = words.size();
        while(1){
            int left = right;
            int sumLen = 0; 
            while(right < n && sumLen+words[right].size()+right-left <= maxWidth){
                sumLen += words[right].size();
                right++;
            }
            if(right == n){
               string s = join(words, left, n, " ");
                ans.emplace_back(s + blank(maxWidth - s.size()));
                return ans;
            }
            int numWords = right - left;
            int numSpaces = maxWidth - sumLen;
            if(numWords == 1){
                ans.push_back(words[left]+blank(numSpaces));
                continue;
            }
            int avgspaces = numSpaces/(numWords-1);
            int extraspaces = numSpaces%(numWords-1);
            string s1 = join(words,left,left+extraspaces+1,blank(avgspaces+1));
            string s2 = join(words,left+extraspaces+1,right,blank(avgspaces));
            ans.push_back(s1 + blank(avgspaces) + s2);
        }
    }
};
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