SouthLeetCode-打卡24年01月第4周

SouthLeetCode-打卡24年01月第4周

// Date : 2024/01/22 ~ 2024/01/28

022.设计链表 - 双链表

(1) 题目描述

022	#LeetCode.707.	#北岸计划	2024/01/22

(2) 题解代码

import java.util.List;class ListNode {int val;ListNode prev;ListNode next;ListNode(){this.val = 0;this.prev = null;this.next = null;}ListNode(int val){this.val = val;this.prev = null;this.next = null;}ListNode(int val, ListNode prev, ListNode next){this.val = val;this.prev = prev;this.next = next;}}public class MyLinkedList   {ListNode head;int length;public MyLinkedList  (){head = null;length = 0;}public int get(int index) {boolean lenValid = length > 0;boolean idxValid = index >= 0 && index < length ;int result;if(lenValid && idxValid){ListNode curr = head;for(int i=0 ; i<index ; i++){curr = curr.next;}result = curr.val;}else{result = -1;}return result;}public void addAtHead(int val) {if(length == 0){head = new ListNode(val);}else {int hVal = head.val;ListNode node = new ListNode(hVal);head.val = val;if(length > 1){node.next = head.next;head.next.prev = node;}head.next = node;node.prev = head;}length++;}public void addAtTail(int val) {ListNode node = new ListNode(val);if (head == null) {head = node;} else {ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;node.prev = cur;}length++;}public void addAtIndex(int index, int val) {if (index < 0 || index > length) {return; // 索引无效，不执行插入操作}if (index == 0) {addAtHead(val); // 在头部插入节点} else if (index == length) {addAtTail(val); // 在尾部插入节点} else {ListNode newNode = new ListNode(val);ListNode curr = head;int count = 0;while (count < index - 1) {curr = curr.next;count++;}newNode.prev = curr;newNode.next = curr.next;curr.next.prev = newNode;curr.next = newNode;length++;}}public void deleteAtIndex(int index) {boolean lenValid = length > 0;boolean idxValid = index >= 0 && index < length ;ListNode dummy = new ListNode();dummy.next = head;// head.prev = dummy; 不应该有这一句ListNode cur = head;ListNode pre = dummy;if(lenValid && idxValid){if(index == 0){head = head.next;}else{for(int i=0 ; i<index ; i++){cur = cur.next;pre = pre.next;}pre.next = pre.next.next;cur.prev = cur.prev.prev;}length--;}}}

023.搜索插入位置

(1) 题目描述

023	#LeetCode.35.	#北岸计划	2024/01/23

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

(2) 题解代码

class Solution {public int searchInsert(int[] nums, int target) {int length = nums.length;int left = 0;int right = length-1;int result;while(right - left > 1){int mid = (left + right)/2;if(nums[mid] > target){right = mid;}else if(nums[mid] < target){left = mid;}else{return mid;}}boolean found = nums[left] == target || nums[right] == target;boolean internal = nums[left] < target && nums[right] > target;if(found){result = nums[left] == target ? left : right;}else{if(internal){result = right;}else{result = nums[right] < target ? right+1 : left;}}return result;}
}

024.在排序数组中查找元素的第一个和最后一个位置

(1) 题目描述

024	#LeetCode.34.	#北岸计划	2024/01/24

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

(2) 题解代码

class Solution {void searchNearBy(int[] result,int[] nums,int target,int length,int pos){while(nums[pos] == target){if(--pos == -1){break;}}result[0] = ++pos;while(nums[pos] == target){if(++pos == length){break;}}result[1] = --pos;}public int[] searchRange(int[] nums, int target) {int length = nums.length;int[] result = {-1,-1};if(length == 0) return result;int left = 0;int right = length - 1;while(right - left > 1){int mid = (left + right) / 2;if(nums[mid] < target){left = mid;}else if(nums[mid] > target){right = mid;}else{searchNearBy(result,nums,target,length,mid);return result;}}boolean found = nums[left] == target || nums[right] == target;boolean internal = nums[left] < target && nums[right] > target;if(found){if(nums[left] == target){searchNearBy(result,nums,target,length,left);}else{searchNearBy(result,nums,target,length,right);}}else{// if(internal){//     result = right;// }else{//     result = nums[right] < target ? right+1 : left;// }}System.out.println(result[0]+"...."+result[1]);return result;}
}

025.x的平方根

(1) 题目描述

025	#LeetCode.69.	#北岸计划	2024/01/25

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

(2) 题解代码

class Solution {public int mySqrt(int x) {if (x == 0) return 0;long left = 0;long right = x;while (left < right) {long mid = left + (right - left + 1) / 2;if (mid * mid > x) {right = mid - 1;} else {left = mid;}}return (int) left;}
}

026.删除有序数组中的重复项

(1) 题目描述

026	#LeetCode.XX.	#北岸计划	2024/01/26

(2) 题解代码

class Solution {public int removeDuplicates(int[] nums) {if(nums == null || nums.length == 0) return 0;int left = 0;int right = 1;while(right < nums.length){if(nums[left] != nums[right]){if(right - left > 1){nums[left + 1] = nums[right];}left++;}right++;}return left + 1;}
}

027.有效的完全平方数

(1) 题目描述

027	#LeetCode.367.	#北岸计划	2024/01/26

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

(2) 题解代码

class Solution {int mySqrt(int x) {if (x == 0) return 0;long left = 0;long right = x;while (left < right) {long mid = left + (right - left + 1) / 2;if (mid * mid > x) {right = mid - 1;} else {left = mid;}}return (int) left;}public boolean isPerfectSquare(int num) {return mySqrt(num)*mySqrt(num) == num;}
}

028.移动零

(1) 题目描述

028	#LeetCode.283.	#北岸计划	2024/01/27

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

(2) 题解代码

class Solution {public void moveZeroes(int[] nums) {int length = nums.length;int j = 0;for(int i=0 ; i<length ; i++) {if(nums[i]!=0) {nums[j++] = nums[i];}}for(int i=j ; i<length ; i++) {nums[i] = 0;}}
}	

029.反转链表

(1) 题目描述

029	#LeetCode.206.	#北岸计划	2024/01/27

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

(2) 题解代码

class Solution{public ListNode reverseList(ListNode head) {if(head == null || head.next == null){return head;}ListNode pre = new ListNode();ListNode cur = new ListNode();ListNode post = new ListNode();pre = head;cur = head.next;post = cur.next;if(cur.next == null){cur.next = pre;pre.next = null;}else{boolean flag = true;while(post != null){if(flag){pre.next = null;flag = false;}cur.next = pre;pre = cur;cur = post;post = post.next;}cur.next = pre;}return cur;}
}

030.两两交换链表中的节点

(1) 题目描述

030	#LeetCode.24.	#北岸计划	2024/01/28

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。

你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

(2) 题解代码

class Solution {public ListNode swapPairs(ListNode head) {ListNode curr = head;List<Integer> list = new ArrayList<>();if(head == null) return null;while(curr != null){list.add(curr.val);curr = curr.next;}int length = list.size();int idx = 0;while(idx < length-1){int temp = list.get(idx);list.set(idx,list.get(idx+1));list.set(idx+1,temp);idx += 2;}ListNode newHead = new ListNode(list.get(0));curr = newHead;for(int i = 1; i < length; i++) {curr.next = new ListNode(list.get(i));curr = curr.next;}return newHead;}
}