有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
方法一：直接排序
思路与算法
方法一：直接排序（自己想到的）
思路与算法
最简单的方法就是将数组 nums 中的数平方后直接排序。
代码
class Solution {public int[] sortedSquares(int[] nums) {int[] ans = new int[nums.length];for (int i = 0; i < nums.length; ++i) {ans[i] = nums[i] * nums[i];}Arrays.sort(ans);return ans;}}
复杂度分析
时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。
空间复杂度：O(logn)。除了存储答案的数组以外，我们需要 O(logn) 的栈空间进行排序。
方法二：双指针
思路与算法
方法一没有利用「数组nums 已经按照升序排序」这个条件。显然，如果数组 nums 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组 nums 中的所有数都是负数，那么将每个数平方后，数组会保持降序。
由于我们得到了两个已经有序的子数组，因此就可以使用归并的方法进行排序了。具体地，使用两个指针分别指向位置 \textit{neg}neg 和 \textit{neg}+1neg+1，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。当某一指针移至边界时，将另一指针还未遍历到的数依次放入答案。
代码
class Solution {public int[] sortedSquares(int[] nums) {int n = nums.length;int negative = -1;for (int i = 0; i < n; ++i) {if (nums[i] < 0) {negative = i;} else {break;}}int[] ans = new int[n];int index = 0, i = negative, j = negative + 1;while (i >= 0 || j < n) {if (i < 0) {ans[index] = nums[j] * nums[j];++j;} else if (j == n) {ans[index] = nums[i] * nums[i];--i;} else if (nums[i] * nums[i] < nums[j] * nums[j]) {ans[index] = nums[i] * nums[i];--i;} else {ans[index] = nums[j] * nums[j];++j;}++index;}return ans;}}
复杂度分析
时间复杂度：O(n)O(n)，其中 nn 是数组 \textit{nums}nums 的长度。
空间复杂度：O(1)O(1)。除了存储答案的数组以外，我们只需要维护常量空间。
方法三：双指针
思路与算法
同样地，我们可以使用两个指针分别指向位置 00 和 n-1n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况，读者可以仔细思考其精髓所在。
代码
class Solution {public int[] sortedSquares(int[] nums) {int n = nums.length;int[] ans = new int[n];for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {if (nums[i] * nums[i] > nums[j] * nums[j]) {ans[pos] = nums[i] * nums[i];++i;} else {ans[pos] = nums[j] * nums[j];--j;}--pos;}return ans;}}
复杂度分析
- 时间复杂度：O(n)O(n)，其中 nn 是数组 \textit{nums}nums 的长度。
- 空间复杂度：O(1)O(1)。除了存储答案的数组以外，我们只需要维护常量空间。
旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
进阶：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
使用额外的数组
我们可以使用额外的数组来将每个元素放至正确的位置。用 nn 表示数组的长度，我们遍历原数组，将原数组下标为 ii 的元素放至新数组下标为 （i+k)mod n 的位置，最后将新数组拷贝至原数组即可。
class Solution {public void rotate(int[] nums, int k) {int n = nums.length;int[] newArr = new int[n];for (int i = 0; i < n; ++i) {newArr[(i + k) % n] = nums[i];}System.arraycopy(newArr, 0, nums, 0, n);}}
复杂度分析
- 时间复杂度： O(n)O(n)，其中 nn 为数组的长度。
- 空间复杂度： O(n)O(n)。
数组翻转
| 操作 | 结果 |
|---|---|
| 原始数组 | 1 2 3 4 5 6 7 |
| 翻转所有元素 | 7 6 5 4 3 2 1 |
| 翻转[0，k mod n-1]区间的元素 | 5 6 7 4 3 2 1 |
| 翻转[k mod n,n-1]区间的元素 | 5 6 7 1 2 3 4 |
class Solution {public void rotate(int[] nums, int k) {k %= nums.length;reverse(nums, 0, nums.length - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.length - 1);}public void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start += 1;end -= 1;}}}
复杂度分析
- 时间复杂度：O(n)O(n)，其中 nn 为数组的长度。每个元素被翻转两次，一共 nn 个元素，因此总时间复杂度为 O(2n)=O(n)O(2n)=O(n)。
- 空间复杂度：O(1)O(1)。
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
题解是用了双指针的方式来解决这个问题；使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length, left = 0, right = 0;
while (right < n) {
if (nums[right] != 0) {
swap(nums, left, right);
left++;
}
right++;
}
}
public void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
我当时的想法是，找到数组中不为零的数，按照顺序重新排列，最后没有数的位置补零即可，因为省去了交换的，会节省比较多的时间，也有点走题目漏洞的感觉
class Solution {
public void moveZeroes(int[] nums) {
int indexNow = 0;
int indexNum = 0;
int m = nums.length;
while(indexNum<m){
if(nums[indexNum] != 0) {
nums[indexNow++] = nums[indexNum];
}
++indexNum;
}
for(int i = indexNow; i < m; i++){
nums[i] = 0;
}
}
}
两数之和——输入有数有序数组
给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
最开始的想法是想确定一个数，在找到另一个数，后来发现这种方法太费时间，但是后来官方还是给出了这种解法的题解（当时就觉得每个数都要找一遍很费时间，就没有细化的想下去。）
class Solution {
public int[] twoSum(int[] numbers, int target) {
for (int i = 0; i < numbers.length; ++i) {
int low = i + 1, high = numbers.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] == target - numbers[i]) {
return new int[]{i + 1, mid + 1};
} else if (numbers[mid] > target - numbers[i]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return new int[]{-1, -1};
}
}
我还是比较热衷有第二种双指针的解法
class Solution {
public int[] twoSum(int[] numbers, int target) {
int low = 0, high = numbers.length - 1;
while (low < high) {
int sum = numbers[low] + numbers[high];
if (sum == target) {
return new int[]{low + 1, high + 1};
} else if (sum < target) {
++low;
} else {
--high;
}
}
return new int[]{-1, -1};
}
}
反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：[“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]
示例 2：
输入：[“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]
这题什么都不要说了，就记录一下
class Solution {
public void reverseString(char[] s) {
int n = s.length;
for (int left = 0, right = n - 1; left < right; ++left, --right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}
}
反转字符串中的单词
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例：
输入：”Let’s take LeetCode contest”
输出：”s’teL ekat edoCteeL tsetnoc”
刚开始就想到了不好的东西导致解题思路一直不对，仔细读了题干发现，和上道题不一样，可以开辟新的空间。
开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串，就能得到翻转后的结果
//
class Solution {
public String reverseWords(String s) {
StringBuffer ret = new StringBuffer();
int length = s.length();
int i = 0;
while (i < length) {
int start = i;
while (i < length && s.charAt(i) != ' ') {
i++;
}
for (int p = start; p < i; p++) {
ret.append(s.charAt(start + i - 1 - p));
}
while (i < length && s.charAt(i) == ' ') {
i++;
ret.append(' ');
}
}
return ret.toString();
}
}
后来查了百度，发现，可以利用toCharArray()方法将字符串转变成数组
class Solution {
public String reverseWords(String s) {
char[] array = s.toCharArray();
int start = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == ' ') {
reverse(array, start, i - 1);
start = i + 1; // 更新start为下一个单词的左索引
continue;
}
if (i == array.length - 1) {
reverse(array, start, i);
}
}
return new String(array);
}
private void reverse(char[] array, int l, int r) {
while (l < r) {
char temp = array[l];
array[l] = array[r];
array[r] = temp;
l += 1;
r -= 1;
}
}
}
若有收获，就点个赞吧
0 人点赞
