数字问题-LeetCode 492、495、496、498、500、501、504、506
数字问题-LeetCode 492、495、496、498、500、501、504、506
作者：TeddyZhang，公众号：算法工程师之路
数字问题：
LeetCode # 492 495 496 498 500 501 504 506
1
编程题
【LeetCode #492】构造矩形
作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：
- 你设计的矩形页面必须等于给定的目标面积。
- 宽度 W 不应大于长度 L，换言之，要求 L >= W 。
- 长度 L 和宽度 W 之间的差距应当尽可能小。 你需要按顺序输出你设计的页面的长度 L 和宽度 W
class Solution {
public:
vector<int> constructRectangle(int area) {
int w = sq(area);
while(area % w != ) w--;
return {area/w, w};
}
private:
int sq(int area) { // 牛顿法
long x = area;
while(x*x > area) {
x = (x + area/x)/;
}
return x;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/construct-the-rectangle
【LeetCode #495】提莫攻击
在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄，他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。现在，给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间，你需要输出艾希的中毒状态总时长。
你可以认为提莫在给定的时间点进行攻击，并立即使艾希处于中毒状态。
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
if (timeSeries.size() == )
return ;
int sum = ;
for (int i = ; i < timeSeries.size() - ; ++i)
sum += min(duration, timeSeries[i + ] - timeSeries[i]);
return sum + duration;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/teemo-attacking
【LeetCode #496】下一个更大元素 I
给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。
示例 1: 输入: nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出: [-1,3,-1]
解题思路：使用哈希表保存nums1在nums2中的索引值，然后进行遍历比较即可！如果存在更大的元素，则跳出循环，否则输出值-1.
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
unordered_map<int, int> hashmap;
int idx = ;
for(auto num: nums2) {
hashmap[num] = idx++;
}
vector<int> res;
for(int i = ; i < m; i++) {
for(int j = hashmap[nums1[i]]; j < n; j++) {
if (nums2[j] > nums1[i]) {
res.push_back(nums2[j]);
break;
} else {
if (j == n-1) {
res.push_back(-1);
}
}
}
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/next-greater-element-i
【LeetCode #498】对角线遍历
给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。
示例: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,4,7,5,3,6,8,9]
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
if (matrix.empty()) return {};
vector<int> res;
int m = matrix.size(), n = matrix[].size(), s = ;
res.push_back(matrix[][]);
while(s < m+n+) {
if (s % ) {
for(int i = max(s-n+, ); i <= min(m-1, s); ++i)
res.push_back(matrix[i][s-i]);
} else {
for(int i = min(s, m-1); i >= max(s-n+, ); --i)
res.push_back(matrix[i][s-i]);
}
++s;
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/diagonal-traverse
【LeetCode #500】键盘行
给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。
示例： 输入: ["Hello", "Alaska", "Dad", "Peace"] 输出: ["Alaska", "Dad"]
解题思路：主要考察string.find函数，简单遍历即可
class Solution {
public:
vector<string> findWords(vector<string>& words) {
vector<string> WORDS = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
vector<string> res;
string tmp = "";
for(auto word: words) {
for(auto WORD: WORDS) { // 确定是哪一行
char ch = word[];
if (ch >= 'A' && ch <= 'Z')
ch = 'a' + ch - 'A';
if (WORD.find(ch) != WORD.npos) {
tmp = WORD;
}
}
int i = ;
for(; i < word.size(); i++) {
char ch = word[i];
if (ch >= 'A' && ch <= 'Z')
ch = 'a' + ch - 'A';
if (tmp.find(ch) == tmp.npos) { // 有一个字母没有找到
break;
}
}
if (i == word.size()) res.push_back(word);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/keyboard-row/
【LeetCode #501】二叉搜索树的众数
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义： 结点左子树中所含结点的值小于等于当前结点的值 结点右子树中所含结点的值大于等于当前结点的值 左子树和右子树都是二叉搜索树
class Solution {
public:
vector<int> findMode(TreeNode* root) {
vector<int> res;
if (!root) return res;
TreeNode* pre = nullptr;
int curTimes = , maxTimes = ;
inOrder(root, pre, curTimes, maxTimes, res);
return res;
}
private:
void inOrder(TreeNode* root, TreeNode*& pre, int& curTimes,
int& maxTimes, vector<int>& res) {
if (!root) return;
inOrder(root->left, pre, curTimes, maxTimes, res);
if (pre)
curTimes = (root->val == pre->val) ? curTimes+ : ;
if (curTimes == maxTimes)
res.push_back(root->val);
else if (curTimes > maxTimes) {
res.clear();
res.push_back(root->val);
maxTimes = curTimes;
}
pre = root;
inOrder(root->right, pre, curTimes, maxTimes, res);
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree
【LeetCode #504】七进制数
给定一个整数，将其转化为7进制，并以字符串形式输出。
示例 1: 输入: 100 输出: "202"
解题思路：七进制数，当num是负数时，可以先按照正数进行处理，然后再头部插入负号即可！
class Solution {
public:
string convertToBase7(int num) {
string res = "";
if (num == ) return "0";
int val = num;
num = abs(num);
while(num) {
res.insert(, to_string(num % ));
num /= ;
}
if (val < ) res.insert(, "-");
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/base-7/
【LeetCode #506】相对名次
给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（"Gold Medal", "Silver Medal", "Bronze Medal"）。
(注：分数越高的选手，排名越靠前。)
示例 1: 输入: [5, 4, 3, 2, 1] 输出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
class Solution {
public:
vector<string> findRelativeRanks(vector<int>& nums) {
int len = nums.size();
vector<string> res(len);
map<int, int> hashmap; // key有序, 从小到大
for(int i = ; i < nums.size(); i++) {
hashmap[nums[i]] = i;
}
for(auto it: hashmap) {
if (len == ) {
res[it.second] = "Bronze Medal";
len--;
} else if (len == ) {
res[it.second] = "Silver Medal";
len--;
} else if (len == ) {
res[it.second] = "Gold Medal";
} else
res[it.second] = to_string(len--);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/relative-ranks