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;
}
}
