LeetCode题目练习记录 _数组和链表01 _20211007
26. 删除有序数组中的重复项
难度简单2247
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列
189. 旋转数组
难度中等1151
给定一个数组，将数组中的元素向右移动 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]
提示：
1 <= nums.length <= 2 * 104-231 <= nums[i] <= 231 - 10 <= k <= 105
方法一：使用额外的数组
func rotate(nums []int, k int) {
newNums := make([]int, len(nums))
for i,v := range nums {
newNums[(i+k)%len(nums)] = v
}
copy(nums,newNums)// 认识一个go语言自带的方法
}
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);// 认识一个java语言自带的方法
}
}
方法二：环状替换
func rotate(nums []int, k int) {
// 方法二：环状替换
n := len(nums)
k %= n
for start, count := 0,gdc(k,n);start < count;start++{
pre,cur := nums[start],start
for ok := true; ok; ok = cur != start {
next := (cur + k)% n
nums[next], pre, cur = pre, nums[next], next
}
}
}
// 其中gcd 指的是最大公约数
func gdc(a,b int) int {
for a != 0 {
a,b = b % a,a
}
return b
}
func rotate(nums []int, k int) {
// 方法二：环状替换
n := len(nums)
k %= n
for start, count := 0, 0; count<n; start++ {
pre,cur := nums[start],start
for ok := true; ok; ok = cur != start {
next := (cur + k)% n
nums[next], pre, cur = pre, nums[next], next
count++
}
}
}
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);
}
}
// 其中gcd 指的是最大公约数
public int gcd(int x,int y) {
return y > 0 ? gcd(y,x % y) : x;
}
}
class Solution {
public void rotate(int[] nums, int k) {
// 方法二：环状替换
int n = nums.length;
k = k % n;
int count = 0;
// 通过判断是否对所有元素实现了交换来实现退出循环
for (int start = 0;count < n; ++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;
count ++ ;
}while(start != current);
}
}
}
方法三：数组翻转
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;
}
}
}
func rotate(nums []int, k int) {
// 方法三：数组翻转
k %= len(nums)
reverse(nums)
reverse(nums[:k])
reverse(nums[k:])
}
func reverse(a []int) {
for i,n := 0, len(a); i< n/2; i++ {
a[i],a[n-1-i] = a[n-1-i],a[i]
}
}
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
// 递归
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) {
return l2;
}else if (l2 == null) {
return l1;
}else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else {
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 迭代法
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null){
if(l1.val < l2.val){
prev.next = l1;
l1 = l1.next;
}else{
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
// 递归
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}else if l2 == nil {
return l1
}
if l1.Val < l2.Val {
l1.Next = mergeTwoLists(l1.Next,l2)
return l1
}else{
l2.Next = mergeTwoLists(l2.Next,l1)
return l2
}
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
// 设立哑节点
dummy := &ListNode{}
curr := dummy
for l1 != nil && l2 !=nil{
if l1.Val < l2.Val {
curr.Next = l1
l1 = l1.Next
}else {
curr.Next = l2
l2 = l2.Next
}
curr = curr.Next
}
if l1 != nil {
curr.Next = l1
}else{
curr.Next = l2
}
return dummy.Next
}
88. 合并两个有序数组
难度简单1132收藏分享切换为英文关闭提醒反馈
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
方法一：直接合并后排序
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 方法一：直接合并后排序 方法二：双指针
for (int i=0;i != n; ++i){
nums1[m+i]=nums2[i];
}
Arrays.sort(nums1);
}
}
func merge(nums1 []int, m int, nums2 []int, n int) {
copy(nums1[m:],nums2)
sort.Ints(nums1)
}
方法二：双指针
func merge(nums1 []int, m int, nums2 []int, n int) {
// 方法二：双指针
sorted := make([] int, 0, m+n)
p1, p2 := 0, 0
for {
if p1 == m {
sorted = append(sorted, nums2[p2:]...)
break
}
if p2 == n {
sorted = append(sorted, nums1[p1:]...)
break
}
if nums1[p1] < nums2[p2] {
sorted = append(sorted, nums1[p1])
p1++
}else {
sorted = append(sorted,nums2[p2])
p2++
}
}
copy(nums1, sorted)
}
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 方法二：双指针
int p1 = 0, p2 = 0;
int[] sorted = new int[m+n];
int cur;
while(p1 < m || p2 < n) {
if(p1 == m) {
cur = nums2[p2++];
}else if (p2 == n) {
cur = nums1[p1++];
}else if(nums1[p1] < nums2[p2]) {
cur = nums1[p1++];
}else{
cur = nums2[p2++];
}
sorted[p1+p2-1] = cur;
}
for (int i=0; i != m + n; ++i) {
nums1[i] =sorted[i];
}
}
}
方法三：逆向双指针
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 方法三：逆向双指针
int p1 = m-1, p2 = n-1;
int tail = m+n -1;
int cur;
while(p1 >= 0 || p2 >= 0) {
if (p1 == -1){
cur = nums2[p2--];
}else if(p2 == -1){
cur = nums1[p1--];
}else if (nums1[p1] > nums2[p2]) {
cur = nums1[p1--];
}else {
cur = nums2[p2--];
}
nums1[tail--] = cur;
}
}
}
func merge(nums1 []int, m int, nums2 []int, n int) {
// 方法三：逆向双指针
for p1, p2, tail := m-1, n-1, m+n -1; p1 > 0 || p2 >= 0; tail-- {
var cur int
if p1 == -1 {
cur = nums2[p2]
p2--
}else if p2 == -1 {
cur = nums1[p1]
p1--
}else if nums1[p1] > nums2[p2] {
cur = nums1[p1]
p1--
}else {
cur = nums2[p2]
p2--
}
nums1[tail] = cur
}
}
1. 两数之和
难度简单12287
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
方法一：暴力枚举
class Solution {
// 方法一：暴力枚举
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i =0; i < n ;i++) {
for (int j = i+1; j < n; ++j){
if(nums[i] + nums[j] == target) {
return new int[]{i,j};
}
}
}
return new int[0];
}
}
func twoSum(nums []int, target int) []int {
// 方法一：暴力枚举
for i, x := range nums {
for j := i +1; j < len(nums); j++ {
if x + nums[j] == target {
return []int{i,j}
}
}
}
return nil
}
方法二：哈希表
class Solution {
// 方法二：哈希表
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer>hashtable = new HashMap<Integer,Integer>();
for (int i=0;i<nums.length; i++){
if(hashtable.containsKey((target - nums[i]))){
return new int[] {hashtable.get((target - nums[i])), i};
}
hashtable.put(nums[i],i);
}
return new int[0];
}
}
func twoSum(nums []int, target int) []int {
// 方法二：哈希表
hashTable := map[int]int{}
for i, x := range nums {
if p,ok := hashTable[target-x];ok {
return []int{p,i}
}
hashTable[x] = i
}
return nil
}
283. 移动零
难度简单1258
给定一个数组 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;
}
}
func moveZeroes(nums []int) {
left, right, n := 0, 0, len(nums)
for right < n {
if nums[right] != 0 {
nums[left], nums[right] = nums[right], nums[left]
left ++
}
right ++
}
}
方法二：覆盖 + 补0
func moveZeroes(nums []int) {
now,n := 0,0
m := len(nums)
for n<m {
if nums[n]!=0{
nums[now] = nums[n]
now++
}
n++
}
for i:=now ;i<m;i++ {
nums[i] = 0
}
}
66. 加一
难度简单763
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0]
输出：[1]
提示：
1 <= digits.length <= 1000 <= digits[i] <= 9
class Solution {
public int[] plusOne(int[] digits) {
for (int i= digits.length-1;i>=0;i--){
digits[i]++;
digits[i] = digits[i]%10;
if(digits[i]%10 != 0) return digits;
}
digits = new int[digits.length + 1];
digits[0] = 1;
return digits;
}
}
func plusOne(digits []int) []int {
for i := len(digits) -1;i != -1;i-- {
digits[i]++
if digits[i]/10 == 0 {
return digits
}
digits[i] = digits[i]%10
}
return append([]int{1},digits...)
}