leetcode解题思路分析（五）29-36题

2024-09-05 05:18
文章标签 leetcode 29 36 解题 思路 分析

本文主要是介绍leetcode解题思路分析（五）29-36题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  1. 两数相除
    给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
    返回被除数 dividend 除以除数 divisor 得到的商。

本题思路倒是不难，既然不能用乘除法和mod，那使用减法是理所当然的，唯一需要考虑的是边界溢出情况

class Solution {
public:int divide(int dividend, int divisor) {int i = 0;bool minus = false;if (dividend == INT_MIN){           if (divisor == - 1)return INT_MAX;else if (divisor == 1)return INT_MIN;else if (divisor == INT_MIN)return 1; }else if (divisor == INT_MIN)return 0;if (dividend < 0 && divisor > 0){minus = true;divisor = - divisor;}else if (dividend > 0 && divisor < 0){minus = true;dividend = - dividend;}dividend = dividend > 0 ? -dividend : dividend;divisor = divisor > 0 ? -divisor : divisor;while (dividend <= divisor && dividend <= 0){dividend -= divisor;i++;}if (minus)return -i;return i;}
};

但是这种做法会遇到超时问题，因此需要思考更优秀的做法：每次让除数翻倍，多的部分递归去继续从原始除数处理

  1. 避免溢出和对于被除数和除数一些特殊判定以加快运算速度和避免出错
  2. 采用被除数减除数来做到除的效果
  3. 采用除数自增翻倍的思想加快减法的速度
  4. 考虑到符号和可能的溢出，这里将除数和被除数转换为负数进行运算，同时传递运算结果的符号
class Solution {
public:int subDivide(int dividend, int divisor, bool minus){int i = 0, times = 1;int originDivisor = divisor;while (dividend <= divisor && dividend <= 0){dividend -= divisor;i += times;           if (dividend >= divisor){break;}divisor += divisor;times += times;}if (dividend > originDivisor){if (minus)return -i;elsereturn i;}else{if (minus)return -i + subDivide(dividend, originDivisor, minus);elsereturn i + subDivide(dividend, originDivisor, minus);}}int divide(int dividend, int divisor) {int i = 0, times = 1, left = 0;bool minus = false;if (dividend == INT_MIN){if (divisor == -1)return INT_MAX;else if (divisor == 1)return INT_MIN;else if (divisor == INT_MIN)return 1;}else if (divisor == INT_MIN)return 0;else if (divisor == 1)return dividend;else if (divisor == -1)return -dividend;if (dividend < 0 && divisor > 0){minus = true;divisor = -divisor;}else if (dividend > 0 && divisor < 0){minus = true;dividend = -dividend;}else if (dividend > 0 && divisor > 0){divisor = -divisor;dividend = -dividend;                        }return subDivide(dividend, divisor, minus);}
};
  1. 串联所有单词的子串
    给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

本题主要在于关注以下几点：
（1）完全匹配意味着寻找s中长度为words总长的窗口，采用滑动窗口进行处理
（2）由于串联顺序并未规定，因此采用哈希表是很合理的做法
（3）哈希表中key为单次，value为words中出现次数，滑动窗口去查找目前有多少个该类单次，如果恰好满足则数量+1

class Solution {
public:vector<int> findSubstring(string s, vector<string> &words) {//特殊情况直接排除if(s.empty() || words.empty())return {};//存放结果的数组vector<int> result;//单词数组中的单词的大小，个数，以及总长度int one_word = words[0].size();int word_num = words.size();//int all_len = one_word * word_num;//建立单词->单词个数的映射unordered_map<string, int> m1;for(const auto &w:words)m1[w]++;for(int i = 0; i < one_word; ++i){//left和rigth表示窗口的左右边界，count用来统计匹配的单词个数int left = i, right = i, count = 0;unordered_map<string, int> m2;//开始滑动窗口while(right + one_word <= s.size()){//从s中提取一个单词拷贝到wstring w = s.substr(right, one_word);right += one_word;//窗口右边界右移一个单词的长度if(m1.count(w) == 0){//此单词不在words中，表示匹配不成功,然后重置单词个数、窗口边界、以及m2count = 0;left = right;m2.clear();}else{//该单词匹配成功，添加到m2中m2[w]++;count++;    while(m2.at(w) > m1.at(w))//一个单词匹配多次，需要缩小窗口，也就是left右移{string t_w = s.substr(left, one_word);count--;m2[t_w]--;left += one_word;}if(count == word_num)result.push_back(left);}}}return result;}
};
  1. 下一个排列
    实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
    如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
    必须原地修改，只允许使用额外常数空间。
    以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
    1,2,3 → 1,3,2
    3,2,1 → 1,2,3
    1,1,5 → 1,5,1

本题的主要思路是倒叙查找到第一个不满足递减的数，然后与右侧比它大的最少的数交换，之后右侧排序获得最小排列，即为下一个更大的排列

class Solution {
public:void nextPermutation(vector<int>& nums) {int size = nums.size();int ptr = nums[size - 1];for (int i = size - 2; i >= 0; i--){//找到了一个比右侧小的数if (nums[i] < ptr){//找到它在右侧的位置并替换for (int j = size - 1; j >= i + 1; j--){if (nums[j] > nums[i]){int tmp = 0;tmp = nums[j];nums[j] = nums[i];nums[i] = tmp;sort(nums.begin() + i + 1, nums.end());break;}}return;}elseptr = nums[i];}sort(nums.begin(), nums.end());}
};
  1. 最长有效括号
    给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

本题可以采用动态规划解决，即每次向后滑动，然后若出现（）则+2， 若出现))则需要检测))之前最优子结构前是否有多的(，有的话则+2

class Solution {
public:int longestValidParentheses(string s) {if (s.size() == 0)return 0;int maxans = 0;int dp[s.length()] = {0};for (int i = 1; i < s.length(); i++) {if (s[i] == ')') {if (s[i - 1] == '(') {dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;} else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;}maxans = max(maxans, dp[i]);}}return maxans;        }
};
  1. 搜索旋转排序数组
    假设按照升序排序的数组在预先未知的某个点上进行了旋转。
    ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
    搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
    你可以假设数组中不存在重复的元素。
    你的算法时间复杂度必须是 O(log n) 级别。

看到log n的事件复杂度其实就提示了要使用二分法解决。本题的难点在于数组进行了一次不确定位置的旋转，但是旋转后依然是两部分升序的组合，这就存在一个必然性：旋转点假设为a和b之间，则b成为了新数组第一个数，a成为了末尾数。因为b大于a和a之前的数，所以我们判断中间点如果小于b，则证明旋转后的片段小于一半，即在左边，否则在右边。

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int mid = left + (right-left)/2;while(left <= right){if(nums[mid] == target){return mid;}if(nums[left] <= nums[mid]){  //左边升序if(target >= nums[left] && target <= nums[mid]){//在左边范围内right = mid - 1;}else{//只能从右边找left = mid+1;}}else{ //右边升序if(target >= nums[mid] && target <= nums[right]){//在右边范围内left = mid +1;}else{//只能从左边找right = mid-1;}}mid = left + (right-left)/2;}return -1;  //没找到}
};
  1. 在排序数组中查找元素的第一个和最后一个位置
    给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
    你的算法时间复杂度必须是 O(log n) 级别。
    如果数组中不存在目标值，返回 [-1, -1]。

由题目可知采取二分法解决。在升序排序数组中每次比较中间值然后讨论即可

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if (nums.size() == 0)return {-1, -1};int begin = 0, end = nums.size() - 1;if (nums[begin] > target || nums[end] < target)return {-1, -1};while (begin <= end){if (nums[begin] == target && nums[end] == target){vector<int> ret = {begin, end};return ret;}int mid = (begin + end) / 2; if (nums[mid] < target)begin = mid + 1;else if (nums[mid] > target)end = mid - 1;else{begin = mid;end = mid;while (begin >= 0 && nums[begin] == target){begin--;}while (end < nums.size() && nums[end] == target){end++;}vector<int> ret = {begin + 1, end - 1};return ret;               }if (nums[begin] > target || nums[end] < target){return {-1, -1};}}return {-1, -1};}
};
  1. 搜索插入位置
    给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    你可以假设数组中无重复元素。

做完上题之后这题简直太简单了，一样的二分法

class Solution {
public:int searchInsert(vector<int>& nums, int target) {if (nums.size() == 0 || nums[0] > target)return 0;int begin = 0, end = nums.size() - 1;if (nums[end] < target)return end + 1;while (begin <= end){int mid = (begin + end) / 2;if (nums[mid] == target)return mid;else if (nums[mid] < target)begin = mid + 1;else end = mid - 1;}return nums[begin] > target ? begin : begin + 1;}
};
  1. 有效的数独
    判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
    数字 1-9 在每一行只能出现一次。
    数字 1-9 在每一列只能出现一次。
    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

本题可以采用暴力遍历法，这样空间成本小，但是时间成本较高。如果作为平衡的话，采用三个数组记录每一位所在位置的值，一次遍历即可解决三个条件的判断，但是空间成本较高

class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {int cols[9][9] = {0}, rows[9][9] = {0}, blocks[9][9] = {0};for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] != '.'){int data = board[i][j] - '0';cols[i][data - 1]++;rows[j][data - 1]++;blocks[(i / 3) * 3 + j / 3][data - 1]++;if(cols[i][data - 1] > 1 || rows[j][data - 1] > 1|| blocks[(i / 3) * 3+ j / 3][data - 1] > 1){return false;}}}}return true;    }
};

这篇关于leetcode解题思路分析（五）29-36题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1138051。

相关文章

哈希leetcode-1

哈希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索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

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

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

MOLE 2.5 分析分子通道和孔隙

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

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

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）篇

线性因子模型 - 独立分量分析（ICA）篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型，它们通过引入潜变量（ latent variables \text{latent variables} latent variables）来更好地表征数据。其中，独立分量分析（ ICA \text{ICA} ICA）作为线性因子模型的一种，以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

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 &
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2