字数统计: 4.4k字   |   阅读时长: 20分

leetcode-hot-100-3

200. 岛屿数量 - 力扣（LeetCode）

给你一个由 ‘1’（陆地）和 ‘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
class Solution {
public:
    void dfs(vector<vector<char>>& grid, int r, int c) {
        int nr = grid.size();
        int nc = grid[0].size();
        grid[r][c] = '0';
        if(r - 1 >= 0 && grid[r - 1][c] == '1') dfs(grid, r - 1, c);
        if(c - 1 >= 0 && grid[r][c - 1] == '1') dfs(grid, r, c - 1);
        if(r + 1 < nr && grid[r + 1][c] == '1') dfs(grid, r + 1, c);
        if(c + 1 < nc && grid[r][c + 1] == '1') dfs(grid, r, c + 1);
    }
    int numIslands(vector<vector<char>>& grid) {
        int num = 0;
        for(int r = 0; r < grid.size(); r++) {
            for(int c = 0; c < grid[0].size(); c++) {
                if(grid[r][c] == '1') {	//深度优先，如果检测到1，就将周围的1都变成0
                    num++;
                    dfs(grid, r, c);
                }
            }
        }
        return num;
    }
};

234. 回文链表 - 力扣（LeetCode）

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

就是把链表的值都拷贝到vector中，然后用双指针判断回文。

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:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;
        while (head != nullptr) {
            vals.push_back(head->val);
            head = head->next;
        }
        for (int i = 0, j = vals.size() - 1; i < j; ++i, --j) {
            if (vals[i] != vals[j]) {
                return false;
            }
        }
        return true;
    }
};

208. 实现 Trie (前缀树) - 力扣（LeetCode）

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

Trie Tree 的实现 (适合初学者)🌳 - 实现 Trie (前缀树) - 力扣（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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Trie {
private:
    bool isEnd;
    Trie* next[26];
public:
    Trie() {
        isEnd = false;
        memset(next, 0, sizeof(next));
    }
    
    void insert(string word) {
        Trie* node = this;
        for (char c : word) {
            if (node->next[c-'a'] == NULL) {
                node->next[c-'a'] = new Trie();
            }
            node = node->next[c-'a'];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        Trie* node = this;
        for (char c : word) {
            node = node->next[c - 'a'];
            if (node == NULL) {
                return false;
            }
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie* node = this;
        for (char c : prefix) {
            node = node->next[c-'a'];
            if (node == NULL) {
                return false;
            }
        }
        return true;
    }
};

215. 数组中的第K个最大元素 - 力扣（LeetCode）

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> q;      //从大到小顺序排
        for (const auto &num: nums) {
            if (q.size() < k) {
                q.push(num);
            } else if (q.top() < num) {
                q.pop();
                q.push(num);
            }
        }
        return q.top();
    }
};

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

核心思路就是先序遍历的第一个元素就是根节点，中序遍历根节点左面值为左子树节点，右边的值为右子树节点，不停的递归调用。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    unordered_map<int, int> index;

public:
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if(preorder_left > preorder_right || inorder_left > inorder_right) {
            return nullptr;
        }
        int preorder_root = preorder_left;
        int inorder_root = index[preorder[preorder_root]];
        int lefttreeSize = inorder_root - inorder_left;
        int righttreeSize = preorder.size() - lefttreeSize - 1;
        TreeNode *root = new TreeNode(preorder[preorder_root]);
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + lefttreeSize, inorder_left, inorder_root - 1);
        root->right = myBuildTree(preorder, inorder, preorder_left + lefttreeSize + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;

    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        //构建哈希映射
        for(int i = 0; i < n; i++) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

114. 二叉树展开为链表 - 力扣（LeetCode）

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

用组存先序遍历的结果，然后将数据节点构成新树，注意要传vec的引用

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    public:
    void flatten(TreeNode* root) {
        vector <TreeNode*> vec;
        preorderTraversal(root, vec);
        TreeNode* cur = root;
        for(int i = 1; i < vec.size(); i++) {
            cur->left = NULL;
            cur->right = vec[i];
            cur = cur->right;
        }
    }

    void preorderTraversal(TreeNode* root, vector<TreeNode*> &vec) {        //注意这里要传引用
        if (root != NULL) {
            vec.push_back(root);
            preorderTraversal(root->left, vec);
            preorderTraversal(root->right, vec);
        }
    }
};

124. 二叉树中的最大路径和 - 力扣（LeetCode）

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

二叉树中的最大路径和 - 二叉树中的最大路径和 - 力扣（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
28
29
30
31
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int result = INT_MIN;
public:
    int maxGain(TreeNode* root) {
        if(root == nullptr) {
            return 0;
        }
        int leftGain = max(maxGain(root->left), 0);
        int rightGain = max(maxGain(root->right), 0);
        int totalGain = root->val + leftGain + rightGain;
        result = max(result, totalGain);
        return root->val + max(leftGain, rightGain);    //节点最大的贡献一定是节点加上它的左子树或者它的右子树,只能取一边，只用这个节点是根节点时才可能左右都算
        //return totalGain;
    }
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return result;
    }
};

621. 任务调度器 - 力扣（LeetCode）

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的 最短时间 。

【任务调度器】C++ 桶子_配图理解 - 任务调度器 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    static bool cmp(int x, int y)
    {
	return x > y;
    }

    int leastInterval(vector<char>& tasks, int n) {
        int len = tasks.size();
        vector<int> vec(26);
        for(char c : tasks) 
            ++vec[c-'A'];
        sort(vec.begin(),vec.end(), cmp);
        int cnt=1;      //最后一排的个数
        while(cnt < vec.size() && vec[cnt] == vec[0]) cnt++;  //如果有两个个元素都有最多个，最后一排就要加一
        return max(len, cnt + (n + 1) * (vec[0] - 1) );  //返回按桶排和所有元素较大的那个,len较大代表没有待命阶段
    }
};

581. 最短无序连续子数组 - 力扣（LeetCode）

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

微信截图_20200921203355.png

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
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        //一段中间有无序序列、其余部分有序的数组满足
        //max和min并非数组中的最大最小值，而是我们路途中遇到的最大最小值
        //从左往右走，max值一定会连续增加；若不增加，说明这一段无序
            //max初始值为nums[0]，因为我们是从左往右走
        //从右往左走，min值一定会连续降低；若不降低，说明这一段无序
            //min初始值为nums[len-1]，因为我们是从右往左走
        //因此，我们可以两次遍历，从而找出无序的左右边界
        //第一次： 正序遍历，找到最后一个值小于我们连续更新的max值的位置
        //第二次： 逆序遍历，找到最后一个值大于我们连续更新的min值的位置
        int len = nums.size();
        //找end
        int max = nums[0];
        //end为-1，表示这个数组没有无序字段
        int end = -1;
        for (int i = 0; i < len; ++i)
        {
            //逆序了
            if (nums[i] < max)
            {
                end = i;
            }
            //这才是正常的
            else
            {
                max = nums[i];
            }
        }

        //找begin
        int min = nums[len - 1];
        //begin为0，是为了与end初始值为-1联动
        int begin = 0;
        for (int i = len - 1; i >= 0; --i)
        {
            if (nums[i] > min)
            {
                begin = i;
            }
            //正常情况
            else
            {
                min = nums[i];
            }
        }

        //为什么要+1？ 因为本来从index i 到index j，就是有j-i + 1个数字的
        return end - begin + 1; //同时也对应了正好全是顺序的情况
    }
};

560. 和为 K 的子数组 - 力扣（LeetCode）

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

注意是连续子数组

方法一：两层循环，但是会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count = 0;
        for(int start = 0; start < nums.size(); start++) {
            int sum = 0;
            for(int end = start; end >= 0; end--) {
                sum = sum + nums[end];
                if(sum == k) count++;
            }
        }
        return count;
    }
};

方法二：前缀树的方法

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count = 0, n = nums.size();
        vector<int> prefix(n, 0); //以i元素结尾的[0,i]区间前缀和
        prefix[0] = nums[0];
        for(int i = 1; i < n; i++){
            prefix[i] = prefix[i - 1] + nums[i];  //求前缀和的通向公式
        }
        unordered_map<int,int> prefixMap; //key为前缀和,val为次数
        prefixMap[0] = 1; //这里是为了当prefix[i]刚好等于k时，能为count数组加上1
        for(int i = 0; i < n; i++){ // [j:i]区间的前缀和为k, prefix[i] - prefix[j - 1] = k
            if(prefixMap.find(prefix[i] - k) != prefixMap.end()){ //0<=j<=i
                count += prefixMap[prefix[i] - k];
            }
            prefixMap[prefix[i]]++; //不能提前计算前缀和,只能一边计算一边统计前缀和数量,因为要保证0<=j<=i
        }
        return count;
    }
};

543. 二叉树的直径 - 力扣（LeetCode）

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

本题和124题类似

给定二叉树

1
2
3
4
5
    1
   / \
  2   3
 / \     
4   5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int result = INT_MIN;
public:
    int depthNode(TreeNode* root) {
        if(root == NULL) {
            return 0;
        }
        int leftdepth = depthNode(root->left);
        int rightdepth = depthNode(root->right);
        int rootdepth = 1 + leftdepth + rightdepth;
        result = max(result, rootdepth);
        return 1 + max(leftdepth, rightdepth);
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int depth = depthNode(root);
        return result - 1;
    }
};

461. 汉明距离 - 力扣（LeetCode）

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingDistance(int x, int y) {
        int ret = x ^ y;      //异或剩下1的个数就是二进制位不同的位置的数目
        int ans = 0;        //answer 记录1的个数
        while(ret){         //每一次运算消去一个1，直到为0终止循环
            ret = (ret - 1) & ret;   // ret= ret & (ret-1); 进行与操作
            ans++;
        }
        return ans;
    }
};

448. 找到所有数组中消失的数字 - 力扣（LeetCode）

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        unordered_set <int> set;
        vector <int> result;
        for(int i = 0; i < nums.size(); i++) {
            set.insert(nums[i]);
        }
        for(int i = 1; i <= nums.size(); i++) {
            if(set.count(i) == 0) {
                result.push_back(i);
            }
        }
        return result;
    }
};

437. 路径总和 III - 力扣（LeetCode）

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

核心思路就是两层递归，pathSum递归确定每次的路径根节点，rootSum递归确定了根节点时这个根节点的可能路径有几条

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 //思路：递归，找到节点下面所有可能的值
class Solution {
public:
    int rootSum(TreeNode* root, long targetSum) {    //确定路径中的根节点后判断有多少满足题意的，树中的每一个节点都可能作为路径中的根节点
        if(root == nullptr) {
            return 0;
        }
        int result = 0;
        if(root->val == targetSum) {
            result = result + 1;
        }
        result = result + rootSum(root->left, targetSum - root->val);
        result = result + rootSum(root->right, targetSum - root->val);
        return result;
    }
    int pathSum(TreeNode* root, long targetSum) {
        if(root == nullptr) {
            return 0;
        }
        int result = rootSum(root, targetSum);
        result = result + pathSum(root->left, targetSum);   //递归的遍历，以树中的每一个节点为路径中的根节点
        result = result + pathSum(root->right, targetSum);
        return result;
    }
};

394. 字符串解码 - 力扣（LeetCode）

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

img

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 decodeString(string s) {
	//两个栈分别压int res和用pair
	stack<pair<int, string>> sta;
	int num = 0; string res = "";
	//循环检查字符串
	for (int i = 0; i < s.size(); i++) {
		//遇到数字则存入num
		if (s[i] >= '0'&&s[i] <= '9') {
			num *= 10;
			num += (s[i] - '0');//这里括号是否需要
		}
		else if (s[i] == '[') {//遇到[压栈数字和字符串，置零置空
			sta.push(make_pair(num, res));
			num = 0;
			res = "";
		}
		else if (s[i] == ']') {//遇到]出栈数字和字符串，组装
			int n = sta.top().first;//n指示的是res的循环次数，不是a的
			string a = sta.top().second;
			sta.pop();
			for (int i = 0; i < n; i++)  a = a + res; //循环n次
			res = a;
		}
		else {//遇到字符存入字符
			res += s[i];
		}		
	}
	return res;
    }
};

338. 比特位计数 - 力扣（LeetCode）

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

第奇数个元素对比偶数就是最后一位加了1，而对于偶数右移一位后1的个数不变

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

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

这一定是一个<br><br>很长很长的一生啊