赞
踩
数组就是一个集合。数组会用一些名为索引的数字来标识每项数据在数组中的位置,且在大多数编程语言中,索引是从 0 算起的。我们可以根据数组中的索引,快速访问数组中的元素。
数组中的元素在内存中是连续存储的,且每个元素占用相同大小的内存。
访问元素时间复杂度都是O(1),空间复杂度O(1),因为对于固定大小的数组,访问时间不随数组大小而变化。通过下标可直接访问。
修改元素:时间复杂度O(1),空间复杂度O(1),与n无关,通过下标可直接修改
插入元素和删除元素:时间复杂度O(1),空间复杂度O(1),插入和删除元素都需要移动后面的元素,因此随n变化。
给你一个大小为 m x n
的矩阵 mat
,请以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。
示例 1:
输入:mat = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,4,7,5,3,6,8,9]示例 2:
输入:mat = [[1,2],[3,4]]
输出:[1,2,3,4]
作题思路:
1.第一步:找规律,我们发现其每次遍历输出的x+y坐标的和是相等的。且当和为偶数的时候,是x递减,y递增,而当和为奇数的时候,是x递增,y递减。
[0,0] 0 偶数
[0,1],[1,0] 1 奇数
[2,0],[1,1],[0,2] 2 偶数
[1,2][2,1] 3 奇数
[2,2] 4 偶数2.第二步:查找遍历次数,不难发现其遍历的上限是m+n +1,此处m=M-1,n =N-1。
3.第三步:确定开始时,x位置和y的位置和结束时,x,y的位置。不难发现,
当为偶数的时候,如果x+y=i,i的值小于最大的行数,代表坐标x从i开始,y从0开始,如果i大于等于最大的行数,代表坐标x从m开始,y=i-m开始。
当为奇数的时候,如果x+y=i,i的值小于最大的列数,代表坐标y从i开始,x从0开始, 如果i大于等于最大的列数,代表坐标y从n开始,x=i-n开始
代码案例:
- class Solution
- {
- public:
- vector<int> findDiagonalOrder(vector<vector<int>> &mat)
- {
- int m = mat.size() - 1; // 横的长度
- int n = mat[0].size() - 1; // 竖的长度
-
- vector<int> returnvector;
- for (int i = 0; i < m + n + 1; i++)
- {
- if (i % 2 == 0) // 如果是偶数,其是向上遍历,因此其开始时候,x是大于y的,
- {
- int x = i < m ? i : m; // 如果i小于最大的行数,代表坐标x从i开始,y从0开始,如果i大于等于最大的行数,代表坐标x从m开始,y=i-m开始
- int y = i -x;
-
- while (x >= 0 && y <= n) // 注意x和y都不能越界
- {
- returnvector.push_back(mat[x][y]);
- x--;
- y = i - x;
- }
- }
- else if (i % 2 == 1) // 如果是奇数,则是向下遍历
- {
- int y = i < n ? i : n; // 如果i小于最大的列数,代表坐标y从i开始,x从0开始, 如果i大于等于最大的列数,代表坐标y从n开始,x=i-n开始
- int x = i - y;
-
- while (x <= m && y >= 0) // 注意x和y都不能越界
- {
-
- returnvector.push_back(mat[x][y]);
- y--;
- x = i - y;
- }
- }
- }
- return returnvector;
- }
- };
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1:
输入:s = ["h","e","l","l","o"]
输出:["o","l","l","e","h"]示例 2:
输入:s = ["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]
思路:
双指针:
双指针情形一:
指针向中间或两端移动,移动方向始终相对
双指针情形二:
指针向同侧移动,形成前后指针或快慢指针第一步:定义两个指针,一个指向头位置,一个指向末尾位置。
第二步:交换元素。
第三步:移动头尾指针。
代码案例:
- class Solution
- {
- public:
- void reverseString(vector<char> &s)
- {
- int stringsize = s.size();
- if (stringsize <= 0)
- {
- return;
- }
-
- int head = 0;
- int tail = stringsize - 1;
- while (head <tail)
- {
- swap(s[head],s[tail]);
- head ++;
- tail --;
- }
- }
- };
给定长度为 2n 的整数数组 nums ,你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。
示例 1:
输入:nums = [1,4,3,2]
输出:4
解释:所有可能的分法(忽略元素顺序)为:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4示例 2:
输入:nums = [6,2,6,5,1,2]
输出:9
解释:最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9
思路:
要求 sum = a + b + c +...的最大值,那就每一个加数都尽量往大了取。首先考虑所有数的最大值,但是显然这个值不合要求,因为这里的每个加数都是通过min最小值得到的,最大值没有比它更大的,无法实现。那就考所有元素中虑第二大的值,第二大的值如果要作为min值被选出,那就必须得和最大值在一个组。这也是所有加数所能取得到的最大值。
最大值和次大值被选在一个组,剩下的元素中又会有新的最大值和次大值。依次类推。
代码案例:
- class Solution
- {
- public:
- int arrayPairSum(vector<int> &nums)
- {
- int arraysize = nums.size();
- sort(nums.begin(), nums.end());
-
- int sum = 0;
-
- for (int i = 0; i < arraysize; i = i + 2)
- {
- sum += nums[i];
- }
-
- return sum;
- }
- };
给你一个下标从 1 开始的整数数组 numbers ,该数组已按非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数。
如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1:
输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。示例 2:
输入:numbers = [2,3,4], target = 6
输出:[1,3]
解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3]
思路:
需要找到两个符合要求的值,优先双指针。
首先,是一个递增排序,那么我们可以知道头尾相加,判断最大值和最小值的和是否等于目标值,如果大于目标值,则说明我们值找大了,那就要找到次第二最大值,作为新区间的最大值,然后继续判断是否等于目标值。
如果是小于目标值,则说明我们值找小了,因此需要找到次第二最小值,作为新区间的最小值,然后继续判断是否等于目标值。
当等于的时候,则输出值。
代码案例
- class Solution
- {
- public:
- vector<int> twoSum(vector<int> &numbers, int target)
- {
- int first = 0;
- int tail = numbers.size() - 1;
- vector<int> returnvector;
- while (first < tail)
- {
-
- if ((numbers[first] + numbers[tail]) == target) //首部尾部相加等于目标值,返回结果集
- {
- returnvector.push_back(first + 1);
- returnvector.push_back(tail + 1);
- return returnvector;
- }
- else if ((numbers[first] + numbers[tail]) > target)//首部尾部相加大于目标值,则说明尾部前移,值才能变小
- {
- tail--;
- }
- else if ((numbers[first] + numbers[tail]) < target)//首部尾部相加小于目标值,则首部后移,值才能变大
- {
- first++;
- }
- }
- return returnvector;
- }
- };
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k,要通过此题,您需要执行以下操作:
更改 nums 数组,使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。
输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2,_,_]
解释:你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要(因此它们并不计入评测)
思路:
运用双指针的快慢指针,只有快指针不等于目标值的时候,才将快指针指向的值赋值给慢指针指向的值。这样慢指针指向的值就全都是去除了目标值的值。
代码案例:
- class Solution
- {
- public:
- int removeElement(vector<int> &nums, int val)
- {
- int slow = 0;
- int numsize = nums.size();
-
- for (int fast = 0; fast < numsize; fast++)
- {
-
- if (nums[fast] != val)
- {
- nums[slow] = nums[fast];
- slow++;
- }
- }
-
- return slow;
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。