26.【算法五章-----02】

(一)、在元素中查找第一个和最后一个

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]

示例 3：

输入：nums = [], target = 0 输出：[-1,-1]

提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
通过次数618,661提交次数1,462,201
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码展示:

#include 
#include 
#include 
using namespace std;
int main()
{
	int n,a[10];
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	int target, m = 0;
	cin >> target;
	cout << "[";
	for (int i = 0; i < n; i++)
	{
		if (a[i] == target)
		{
			cout << i << ",";
			++m;
		}
	}
	cout << "]";
	if (m == 0)
	{
		system("cls");     //清除用的
		cout << "[-1,-1]" << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

(二)、旋转数组求下标

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1
。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1

示例 3：

输入：nums = [1], target = 0 输出：-1

代码展示:

#include 
using namespace std;
int main()
{
	cout << "请输入您旋转后的数组的个数为:" << endl;
	int n,a[10];
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	cout << "请输入您的目标值为:" << endl;
	int target,m=0;
	cin >> target;
	for (int i = 0; i < n; i++)
	{
		if (a[i] == target)
		{
			m++;
			cout << i << endl;
		}
	}
	if (m == 0)
	{
		cout << -1 << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

（三）、搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

代码展示：

#include 
using namespace std;
int main()
{
	int m, n, a[10][10];
	cout << "请输入这是一个m*n的矩阵" << endl;
	cin >> m >> n;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << "第" << i << "行" << j << "个元素为:" << endl;
			cin >> a[i][j];
		}
	}
	cout << "请输入目标值为:" << endl;
	int target,s=0;
	cin >> target;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (a[i][j] == target)
			{
				s++;
			}
	    }
    }
	if (s == 0)cout << false << endl;
	else cout << true << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

（四）、求最大值（和坐标）

问题描述：给您一个整型数组，请您判断在这个整型数组中最大值为多少且输出坐标.

#include 
using namespace std;
int main()
{
 int a[] = { 9,8,7 };
 int max = a[0];
 int sum = 0;
 int i;
 for ( i = 0; i <3; i++)
 {
  if (max >= a[i])
  {
  }
  else
  {
   max = a[i];
   sum =i;
  }
 }
 cout << "最大值为:" << max << "下表为:" << sum<< endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

(五)、【计算一个字符串和另一个字符串相等的次数】

问题描述：输入两个字符串 ，然后判断A字符串包含B字符串的几倍，如果没有就输出0，有的话就请您输出几倍？

#include 
#include 
using namespace std;
int main()
{
 int m = 0;
 string s1;
 cout <<"请输入第一个字符串的内容:" << endl;
 cin >> s1;
 cout << "请输入第二个字符串的内容:" << endl;
 string s2;
 cin >> s2;
 if (s1.length() < s2.length())
 {
  cout << "没有一个是相等的!" << endl;
 }
 else
 {
  for (int i = 0; i < s1.length(); i++)
  {
   for (int j = 0; j < s2.length(); j++)
   {
    if (s1[i + j] != s2[j])
    {
     break;
    }
    else{
     if (j == s2.length()-1)
     {
      m++;
      i += j;
     i--;
     }} }}
  cout << "有" << m << "个" << endl;
 }
 return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37