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

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

29. 两数相除
    给定两个整数，被除数 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);}
};

30. 串联所有单词的子串
    给定一个字符串 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;}
};

31. 下一个排列
    实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
    如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
    必须原地修改，只允许使用额外常数空间。
    以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
    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());}
};

32. 最长有效括号
    给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

本题可以采用动态规划解决，即每次向后滑动，然后若出现（）则+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;        }
};

33. 搜索旋转排序数组
    假设按照升序排序的数组在预先未知的某个点上进行了旋转。
    ( 例如，数组 [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;  //没找到}
};

34. 在排序数组中查找元素的第一个和最后一个位置
    给定一个按照升序排列的整数数组 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};}
};

35. 搜索插入位置
    给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    你可以假设数组中无重复元素。

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

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;}
};

36. 有效的数独
    判断一个 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题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---