[977. 有序数组的平方](https://leetcode-cn.com/problems/squares-of-a-sorted-array/)——简单
题目描述img题解复杂度分析方法二：双指针复杂度分析 [189. 轮转数组](https://leetcode-cn.com/problems/rotate-array/)——中等
题目描述题解方法一：使用额外的数组**复杂度分析**方法二： [283. 移动零](https://leetcode-cn.com/problems/move-zeroes/)——简单
题目描述题解方法一：方法二：双指针复杂度分析 [167. 两数之和 II - 输入有序数组](https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/)——简单
题目描述img题解复杂度分析方法二：二分查找复杂度分析 [344. 反转字符串](https://leetcode-cn.com/problems/reverse-string/)——简单
题目描述img题解方法一：倒叙输出复杂度分析img方法二：reserve()反转复杂度分析方法三：双指针复杂度分析 [557. 反转字符串中的单词 III](https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/)——简单
题目描述img题解方法一：字符串分割反转复杂度分析 [876. 链表的中间结点](https://leetcode-cn.com/problems/middle-of-the-linked-list/)——简单
题目描述题解思路：方法一：快慢指针法复杂度分析方法二：List数组 [19. 删除链表的倒数第 N 个结点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)——中等
题目描述题解方法一：双指针复杂度分析
977. 有序数组的平方——简单 题目描述 题解方法一：直接排序
class Solution {
public int[] sortedSquares(int[] nums) {
for (int i = 0; i < nums.length; i++) {
nums[i] = nums[i]*nums[i];
}
Arrays.sort(nums);
return nums;
}
}
复杂度分析
时间复杂度：O(nlogn)，其中 nn 是数组 nums 的长度。空间复杂度：O(logn)。除了存储答案的数组以外，我们需要 O(logn) 的栈空间进行排序。 方法二：双指针
class Solution {
public int[] sortedSquares(int[] nums) {
int arr[] = new int [nums.length];
for (int i = 0,j=nums.length-1,k=nums.length-1;i<=j;) {
if (nums[i]*nums[i]>nums[j]*nums[j]) {
arr[k]=nums[i]*nums[i];
i++;
}
else {
arr[k]=nums[j]*nums[j];
j--;
}
k--;
}
return arr;
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是数组nums 的长度。空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。
189. 轮转数组——中等 题目描述 题解 方法一：使用额外的数组
我们可以使用额外的数组来将每个元素放至正确的位置。用 nn 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (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)，其中 nn 为数组的长度。空间复杂度： O(n)。 方法二：
将原数组从后往前的k个数取出，放入新数组，再将原数组的剩余前面的数取出放入新数组后面
class Solution {
public void rotate(int[] nums, int k) {
int arr[]=new int[nums.length];
if(k>nums.length) {
k=k%nums.length;
}
for (int i = nums.length-k,j=0; i < nums.length; i++) {
arr[j]=nums[i];
j++;
}
for (int i = 0,j=k; i
283. 移动零——简单
题目描述
题解
方法一：
//思路：设置一个index，表示非0数的个数，循环遍历数组，
// 如果不是0，将非0值移动到第index位置,然后index + 1
//遍历结束之后，index值表示为非0的个数，再次遍历，从index位置后的位置此时都应该为0
class Solution {
public void moveZeroes(int[] nums) {
int index=0;
for (int i = 0; i < nums.length; i++) {
if (nums[i]!=0) {
nums[index]=nums[i];
index++;
}
}
for (int i = index; i < nums.length; i++) {
nums[index] = 0;
index++;
}
}
}
方法二：双指针
class Solution {
public void moveZeroes(int[] nums) {
int left = 0;
int right =0;
while (right
复杂度分析
167. 两数之和 II - 输入有序数组——简单
题目描述
题解
方法一：双指针
class Solution {
public int[] twoSum(int[] numbers, int target) {
// int arr [] = new int [2];
int left = 0;
int right = numbers.length-1;
while (left
复杂度分析
方法二：二分查找
class Solution {
public int[] twoSum(int[] numbers, int target) {
// int arr[] = new int [2];
for (int i = 0; i < numbers.length; i++) {
int low = i+1;
int high = numbers.length-1;
while (low<=high) {
int middle = low +(high-low)/2;
if (numbers[middle]==target-numbers[i]) {
return new int[]{i + 1, middle + 1};
}else if (numbers[middle]>target-numbers[i]) {
high=middle-1;
}else {
low=middle+1;
}
}
}
return new int[0];
}
}
复杂度分析
344. 反转字符串——简单
题目描述
题解
方法一：倒叙输出
class Solution {
public void reverseString(char[] s) {
StringBuffer sb = new StringBuffer();
for (int i = s.length-1; i >=0; i--) {
sb.append(s[i]);
}
for(int i=0;i
复杂度分析
方法二：reserve()反转
class Solution {
public void reverseString(char[] s) {
StringBuffer sb = new StringBuffer();
for(int i=0;i
复杂度分析
方法三：双指针
class Solution {
public void reverseString(char[] s) {
int p1 = 0;
int p2 = s.length-1;
char a;
while (p1
复杂度分析
557. 反转字符串中的单词 III——简单
题目描述
题解
方法一：字符串分割反转
class Solution {
public String reverseWords(String s) {
StringBuffer sb = new StringBuffer();
String a[] = s.split(" ");
for (int i = 0; i < a.length; i++) {
StringBuffer sb2 = new StringBuffer(a[i]);
sb2 = sb2.reverse();
if (i!=a.length-1) {
sb.append(sb2+" ");
}else {
sb.append(sb2);
}
}
s = sb.toString();
return s;
}
}
复杂度分析
876. 链表的中间结点——简单
题目描述
题解
思路：
方法一：快慢指针法
快指针q每次走2步，慢指针p每次走1步，当q走到末尾时p正好走到中间。
class Solution {
public ListNode middleNode(ListNode head) {
ListNode p1 = head;
ListNode p2 = head;
while (p2!=null&&p2.next!=null) {
p1 = p1.next;
p2 = p2.next.next;
}
return p1;
}
}
复杂度分析
方法二：List数组
class Solution {
public ListNode middleNode(ListNode head) {
List list = new ArrayList<>();
while (head!=null) {
list.add(head);
head = head.next;
}
int middle = list.size();
middle = middle/2;
return list.get(middle);
}
}
19. 删除链表的倒数第 N 个结点——中等
题目描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
示例 2：
示例 3：
题解
方法一：双指针
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode p1 = head;
ListNode p2 = head;
if (head==null||head.next==null) {
return null;
}
// 先让快指针走n步
for(int i=0;i
复杂度分析
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）