给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
方法1 ： 直接排序 - 将数组nums中的数平方后直接输出。示例：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
知识点：Java的Arrays类中的sort()方法，该方法是Arrays类的静态方法，在需要对数组进行排序时使用。
class Solution {
public int[] sortedSquares(int[] nums) {
int[] a = new int[nums.length];
for(int i = 0 ; i < nums.length ; i++ ){
a[i] = nums[i] * nums[i];
}
Arrays.sort(a);
return a;
}
}
class Solution {
public int[] sortedSquares(int[] nums) {
int[] a = new int[nums.length];
int l = 0 , r = nums.length - 1 ;//左右指针
int x = nums.length-1 ;
while( l <= r){ //循环判断条件
//逆序插入 如果右边数值较大 则将较大数值插入 右指针向左移动
if( nums[l] * nums[l] <= nums[r] * nums[r]){
a[x] = nums[r] * nums[r];
r--;
}else{
a[x] = nums[l] * nums[l] ;
l++;
}
x--; //对应的x插入以后 x的位置也将移动
}
return a;
}
}
189. 旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
进阶：
方法一：使用额外空间示例 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]
class Solution {
public void rotate(int[] nums, int k) {
int[] a = nums.clone();;
for( int i = 0 ; i < nums.length ; i++){
nums[(i+k) % nums.length] = a[i] ;
}
}
}
注意点：
class Solution {
public void rotate(int[] nums, int k) {
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 s,int e) {
while( s < e ){
int a = nums[s];
nums[s] = nums[e];
nums[e] = a;
s++;
e--;
}
}
}
注意：
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n;
int count = gcd(k, n);
for (int start = 0; start < count; ++start) {
int current = start;
int prev = nums[start];
do {
int next = (current + k) % n;
int temp = nums[next];
nums[next] = prev;
prev = temp;
current = next;
} while (start != current);
}
}
public int gcd(int x, int y) {
return y > 0 ? gcd(y, x % y) : x;
}
}
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
方法：使用双指针示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
思路：设置两个指针， i 指针遍历数组，当nums[i]不为零时，赋值给 j 指针所指的位置。然后，i 指针遍历结束以后将 j 指针后续的所有位置置零即可。
class Solution {
public void moveZeroes(int[] nums) {
int l = 0;
for(int i = 0 ; i < nums.length ;i++){
if(nums[i]!=0){
nums[l++] = nums[i];
}
}
for(int j = l ; j
167. 两数之和 II - 输入有序数组
给定一个已按照 非递减顺序排列 的整数数组 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]
方法：双指针
class Solution {
public int[] twoSum(int[] numbers, int target) {
int l=0 , r=numbers.length-1;
while(l<=r){
if(numbers[l]+numbers[r]>target)
r--;
else if(numbers[l]+numbers[r]
归纳总结：
- 双指针：其需要充分利用数组有序这一特征，在某些情况下简化一些运算。
常见应用：两数之和，判断链表是否有环，奇偶排序，求单链表的中间元素，给出n个数问最多能组成多少个三角形。 - 二分查找：使用二分查找的重要条件需要有序的顺序表。
541. 反转字符串II
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于 k 个，则将剩余字符全部反转。
- 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例 1：
输入：s = “abcdefg”, k = 2
输出：“bacdfeg”
示例 2：
输入：s = “abcd”, k = 2
输出：“bacd”
方法：双指针法
步骤：
- 1 首先将字符串转化为字符数组。
- 2 处理好左指针，它从0位开始，每隔2k个位跳转，可放在for循环中声明。
- 3 处理右指针
· 首先，右指针应该在左指针的基础上往后移动k位。（ l - r = k ）需要有k位的位差
· 如果当最后没有k位时，后续的字符也需要反转，因此右指针的取值为 Math.min(ch.length-1,l+k-1)
class Solution {
public String reverseStr(String s, int k) {
char[] sc = s.toCharArray();
for(int l=0 ; l
557. 反转字符串III
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例：
输入：“Let’s take LeetCode contest”
输出：“s’teL ekat edoCteeL tsetnoc”
方法：双指针
步骤：
- 1 将字符串转化为字符数组。
- 2 使用for循环判断空格的位置，left从0开始，right为i-1的位置。
- 3 判断有空格时进行反转。
- 4 注意！ 需要对最后一个单词单独进行反转，因为最后一个单词后没有空格！
class Solution {
public String reverseWords(String s) {
char[] sc = s.toCharArray();
int l = 0 ,count=0;
for(int i = 0 ; i
876. 链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
方法1 ：使用数组实现
对链表进行遍历的同时将遍历到的元素一次放入数组中，然后取对应的中间节点即可。
class Solution {
public ListNode middleNode(ListNode head) {
//数组
ListNode[] a = new ListNode[100];
int count = 0 ;
while( head != null) {
a[count++]=head;
head = head.next;
}
return a[count/2];
}
}
- 时间复杂度：O(N)，其中 N 是给定链表中的结点数目。
- 空间复杂度：O(N)，即数组a用去的空间。
方法2：单指针
使用单指针解题，首先使用单指针对链表进行进行遍历，记录结点数。然后第二次遍历找到中间结点，然后返回。
class Solution {
public ListNode middleNode(ListNode head) {
//单指针
int count = 0 ; //用来记录链表的结点数
ListNode a = head ;
while(a != null){//第一次遍历 确定节点个数
++count;
a = a.next;
}
int k = 0 ;
a = head ;
while( k < count/2){//第二次遍历 找到中间节点。
++k;
a = a.next;
}
return a;
}
}
- 时间复杂度：O(N)，其中N是给定链表的结点数目。
- 空间复杂度：O(1)，只需要常数空间存放变量和指针。
方法3：快慢指针
使用两个指针来遍历链表，快指针一次走两步，慢指针一次走一步，当快指针到达链表末端时，慢指针刚好到达队中。
class Solution {
public ListNode middleNode(ListNode head) {
//快慢指针
ListNode f = head;
ListNode s = head;
while( f != null && f.next != null ){
s = s.next;
f = f.next.next;
}
return s;
}
}
- 时间复杂度：O(N)，其中N是给定链表的结点数目。
- 空间复杂度：O(1)，只需要常数空间存放slow和fast两个指针。
19. 删除链表的倒数第n个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
方法：双指针扫描
整体思路：让快指针先移动n步，然后前后指针共同移动直至快指针到达尾部。
- 设置预先指针pre，为了防止只有一个结点且要被删除的情况。
- 设预先指针 pre 的下一个节点指向 head，设前指针为 start，后指针为 end，二者都等于 pre
- start 先向前移动n步
- 之后 start 和 end 共同向前移动，此时二者的距离为 n，当 start 到尾部时，end 的位置恰好为倒数第 n 个节点
- 因为要删除该节点，所以要移动到该节点的前一个才能删除，所以循环结束条件为 start.next != null
- 删除后返回 pre.next，为什么不直接返回 head 呢，因为 head 有可能是被删掉的点
- 时间复杂度：O(n)
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre = new ListNode(0);//初始化一个节点值为0的空结点
pre.next = head;
ListNode f = pre , s = pre ;
for(int i=n ; i>-1 ; i--){
f = f.next;
}
while(f != null){
s = s.next;
f = f.next;
}
s.next = s.next.next;
return pre.next;
}
}
