leetcode解题思路分析(二十八)200—206题

2024-09-05 05:08

本文主要是介绍leetcode解题思路分析(二十八)200—206题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  1. 岛屿数量
    给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
    岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

本题可用BFS或DFS求解

class Solution {
private: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 (r + 1 < nr && 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 (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);}public:int numIslands(vector<vector<char>>& grid) {int nr = grid.size();if (!nr) return 0;int nc = grid[0].size();int num_islands = 0;for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {++num_islands;dfs(grid, r, c);}}}return num_islands;}
};
class Solution {
public:int numIslands(vector<vector<char>>& grid) {int nr = grid.size();if (!nr) return 0;int nc = grid[0].size();int num_islands = 0;for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {++num_islands;grid[r][c] = '0';queue<pair<int, int>> neighbors;neighbors.push({r, c});while (!neighbors.empty()) {auto rc = neighbors.front();neighbors.pop();int row = rc.first, col = rc.second;if (row - 1 >= 0 && grid[row-1][col] == '1') {neighbors.push({row-1, col});grid[row-1][col] = '0';}if (row + 1 < nr && grid[row+1][col] == '1') {neighbors.push({row+1, col});grid[row+1][col] = '0';}if (col - 1 >= 0 && grid[row][col-1] == '1') {neighbors.push({row, col-1});grid[row][col-1] = '0';}if (col + 1 < nc && grid[row][col+1] == '1') {neighbors.push({row, col+1});grid[row][col+1] = '0';}}}}}return num_islands;}
};
  1. 数字范围按位与
    给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。

本题的精髓在于如何简化位操作的次数。首先我们应该关注较小的数,如果位数不同直接从小数开始看即可。其次,当数位相同的时候,找到不相同的位赋值为0即可


class Solution {
public:int rangeBitwiseAnd(int m, int n) {if (m == n || m == 0) {return m;} else if (floor(log(n)/log(2)) - floor(log(m)/log(2)) >= 1) {return 0;} else {int xorResult = n ^ m;int bits = floor(log(xorResult)/log(2)) + 1;return (m >> bits) << bits;}}
};
  1. 快乐数
    编写一个算法来判断一个数 n 是不是快乐数。
    「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。

该题涉及到可能有循环的情况,因此用快慢指针检测循环为佳

class Solution {
public:int bitSquareSum(int n) {int sum = 0;while(n > 0){int bit = n % 10;sum += bit * bit;n = n / 10;}return sum;}bool isHappy(int n) {int slow = n, fast = n;do{slow = bitSquareSum(slow);fast = bitSquareSum(fast);fast = bitSquareSum(fast);}while(slow != fast);return slow == 1;}
};
  1. 移除链表元素
    删除链表中等于给定值 val 的所有节点。
class Solution {public:ListNode* removeElements(ListNode* head, int val) {ListNode* sentinel = new ListNode(0);sentinel->next = head;ListNode *prev = sentinel, *curr = head, *toDelete = nullptr;while (curr != nullptr) {if (curr->val == val) {prev->next = curr->next;toDelete = curr;} else prev = curr;curr = curr->next;if (toDelete != nullptr) {delete toDelete;toDelete = nullptr;}}ListNode *ret = sentinel->next;delete sentinel;return ret;}
};
  1. 计数质数
    统计所有小于非负整数 n 的质数的数量。

采用厄拉多塞筛法:先把所有设为质数,然后依次排除其倍数

class Solution {
public:int countPrimes(int n) {int count = 0;//初始默认所有数为质数vector<bool> signs(n, true);for (int i = 2; i < n; i++) {if (signs[i]) {count++;for (int j = i + i; j < n; j += i) {//排除不是质数的数signs[j] = false;}}}return count;}
};
  1. 同构字符串
    给定两个字符串 s 和 t,判断它们是否是同构的。
    如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。
    所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。

本题有两种方法:采用一个map映射已有的字符,后面每个检查一遍是否映射相同。第二种方法是把字符对应转换为数字,然后比较两串数字

class Solution {
public:bool isIsomorphic(string s, string t) {if (s.empty() && t.empty())return true;for(int i = 0; i < s.size(); i++){if( s.find(s[i]) != t.find(t[i])) return false;}return true;       }
};
  1. 反转链表
    反转一个单链表。
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *next, *ptr, *prev;ptr = next = head;prev = NULL;while (ptr){next = ptr->next;ptr->next = prev;prev = ptr;ptr = next;}return prev;}
};
class Solution {
public:ListNode* reverseList(ListNode* head) {if (head == NULL || head->next == NULL) {return head;}ListNode* ret = reverseList(head->next);head->next->next = head;head->next = NULL;return ret;}
};

这篇关于leetcode解题思路分析(二十八)200—206题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1138032

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型,它综合考虑了土壤-水分-大气以及植被间的相互作用;是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程,使其能够精确的模拟土壤中水分的运动,而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者

MOLE 2.5 分析分子通道和孔隙

软件介绍 生物大分子通道和孔隙在生物学中发挥着重要作用,例如在分子识别和酶底物特异性方面。 我们介绍了一种名为 MOLE 2.5 的高级软件工具,该工具旨在分析分子通道和孔隙。 与其他可用软件工具的基准测试表明,MOLE 2.5 相比更快、更强大、功能更丰富。作为一项新功能,MOLE 2.5 可以估算已识别通道的物理化学性质。 软件下载 https://pan.quark.cn/s/57

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

衡石分析平台使用手册-单机安装及启动

单机安装及启动​ 本文讲述如何在单机环境下进行 HENGSHI SENSE 安装的操作过程。 在安装前请确认网络环境,如果是隔离环境,无法连接互联网时,请先按照 离线环境安装依赖的指导进行依赖包的安装,然后按照本文的指导继续操作。如果网络环境可以连接互联网,请直接按照本文的指导进行安装。 准备工作​ 请参考安装环境文档准备安装环境。 配置用户与安装目录。 在操作前请检查您是否有 sud

线性因子模型 - 独立分量分析(ICA)篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型,它们通过引入潜变量( latent variables \text{latent variables} latent variables)来更好地表征数据。其中,独立分量分析( ICA \text{ICA} ICA)作为线性因子模型的一种,以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &