逐日OJ题_剑指offer数组篇（剑指offer04+剑指offer11+剑指offer21）
目录剑指 Offer 04二维数组中的查找
代码解析
剑指 Offer 11旋转数组的最小数字
代码解析1
代码解析2
剑指 Offer 21. 调解数组次序使奇数位于偶数前面
代码解析1
代码解析2
剑指 Offer 04二维数组中的查找
LCR 121. 寻找目的值 - 二维数组 - 力扣（LeetCode）
m*n 的二维数组 plants 记录了园林景观的植物排布情况，具有以下特性：
[*]每行中，每棵植物的右侧相邻植物不矮于该植物；
[*]每列中，每棵植物的下侧相邻植物不矮于该植物。
请判断 plants 中是否存在目的高度值 target。
示例 1：
<strong>输入：</strong>plants = [,,], target = 8
<strong>输出：</strong>true
示例 2：
<strong>输入：</strong>plants = [,], target = 4
<strong>输出：</strong>false
提示：
[*]0 <= n <= 1000
[*]0 <= m <= 1000
class Solution {
public:
bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {
}; 代码解析
这个在C语言写过类似的杨氏矩阵，重点是查找的过程是排除的过程，这里从右上角开始找：
class Solution {
public:
bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {
if(plants.size()<1 || plants.size()<1)
return false;
int x=0,y=plants.size()-1;
while(x < plants.size() && y >=0)
{
if(plants>target)
{
y--;
}
else if(plants<target)
{
x++;
}
else
{
return true;
}
}
return false;
}
}; 剑指 Offer 11旋转数组的最小数字
LCR 128. 库存管理 I - 力扣（LeetCode）
仓库管理员以数组 stock 情势记录商品库存表。stock 表现商品 id，大概存在重复。原库存表按商品 id 升序排列。现因突发情况必要进行商品告急调拨，管理员将这批商品 id 提前依次整理至库存表最后。请你找到并返回库存表中编号的 最小的元素 以便及时记录本次调拨。
示例 1：
<strong>输入：</strong>stock =<strong> </strong>
<strong>输出：</strong>3
示例 2：
<strong>输入：</strong>stock =
<strong>输出：</strong>1
提示：
[*]1 <= stock.length <= 5000
[*]-5000 <= stock <= 5000
class Solution {
public:
int stockManagement(vector<int>& stock) {
}; 代码解析1
线性探测：
class Solution {
public:
int stockManagement(vector<int>& stock) {
for (int i = 1;i < stock.size();i++)
{
if (stock < stock)
{
return stock;
}
}
return stock;
}
}; 代码解析2
二分查找+线性探测：
class Solution {
public:
int stockManagement(vector<int>& rotateArray) {
if (rotateArray.empty())
{
return 0;
}
int left = 0, right = rotateArray.size() - 1, mid = 0;
while (left < right)
{
if (right - left == 1) // 两个下标已经相邻了
{
mid = right;
break;
}
mid = left + ((right - left) >> 1); // 注意操作符优先级
if (rotateArray == rotateArray && rotateArray == rotateArray)
{ // 无法判定目标数据在mid左侧，还是右侧 -> 采用线性探测方式
int result = rotateArray;
for (int i = left + 1; i < right; i++)
{
if (result > rotateArray)
{
result = rotateArray;
}
}
return result;
}
if (rotateArray >= rotateArray)//说明mid在前半部分
{ //两者相等， 隐含条件rotateArray >= rotateArray
left = mid;
}
else// 说明mid在后半部分
{
right = mid;
}
}
return rotateArray;
}
}; 剑指 Offer 21. 调解数组次序使奇数位于偶数前面
LCR 139. 训练计划 I - 力扣（LeetCode）
教练使用整数数组 actions 记录一系列核心肌群训练项目编号。为增强训练意见意义性，必要将所有奇数编号训练项目调解至偶数编号训练项目之前。请将调解后的训练项目编号以 数组 情势返回。
示例 1：
<strong>输入：</strong>actions =
<strong>输出：</strong>
<strong>解释：</strong>为正确答案之一
提示：
[*]0 <= actions.length <= 50000
[*]0 <= actions <= 10000
class Solution {
public:
vector<int> trainingPlan(vector<int>& nums) {
}; 代码解析1
class Solution {
public:
vector<int> trainingPlan(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right)
{
while (left < right && nums % 2 == 1)
{
left++; // 找偶数
}
while (left < right && nums % 2 == 0)
{
right--; // 找奇数
}
if (left < right)
{
swap(nums, nums);
}
}
return nums;
}
}; 代码解析2
假如面试官要求奇数和奇数，偶数和偶数直接的相对位置稳固，就要用到插入排序的头脑，
代码就是从前往后找奇数，然后把找到的奇数前面的偶数团体往后移一步，把奇数放到前面。
这里还用到奇数按位与1即是1，偶数按位与1即是0的技巧，第一种代码也能用这个技巧
class Solution {
public:
vector<int> trainingPlan(vector<int>& nums) { // 相对位置不变版代码
int k = 0, size = nums.size(); // k记录放奇数的下标
for(int i = 0; i < size; ++i)
{
if(nums & 1) // 是奇数
{
int tmp = nums;
for(int j = i; j > k; --j) // 移动偶数
{
nums = nums;
}
nums = tmp;
}
}
return nums;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]