当前位置： 首页 > article >正文

力扣hot100第三天

article 2025/2/21 9:13:18

238.除自身以外数组的乘积

题目

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
在这里插入图片描述题意：求数组除了某个元素之外所有元素的乘积
思路：和接雨水一模一样，只不过取最大值换成了数值相乘

代码

class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] left = new int[n];//用于存储每个位置左侧所有元素的乘积。
left[0] = 1;//初始化第一个位置为1，因为第一个元素左侧没有其他元素。
for (int i = 1; i < n; i++) {
left[i] = nums[i - 1] * left[i - 1];
}
int right = 1;
int[] ans = new int[n];
for (int i = n - 1; i >= 0; i–) {
ans[i] = right * left[i];
right *= nums[i];
}
return ans;
}
}

41.缺失的第一个正数

题目

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
在这里插入图片描述

代码

class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;

    for (int i = 0; i < len; i++) {
        while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
        //nums[i] <= len：确保当前数字在有效范围内（即不大于数组长度）。
            // 满足在指定范围内、并且没有放在正确的位置上，才交换
            // 例如：数值 3 应该放在索引 2 的位置上
            swap(nums, nums[i] - 1, i);
        }
    }

    // [1, -1, 3, 4]
    for (int i = 0; i < len; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    // 都正确则返回数组长度 + 1
    return len + 1;
}

private void swap(int[] nums, int index1, int index2) {
    int temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
}

}

矩阵

73.矩阵置零

题目

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
在这里插入图片描述

代码

class Solution {
public void setZeroes(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
List row = new ArrayList<>();
List coloum = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
row.add(i);
coloum.add(j);
}
}
}
for (Integer r : row) {
for (int i = 0; i < m; i++) {
matrix[r][i] = 0;
}
}
for (Integer c : coloum) {
for (int i = 0; i < n; i++) {
matrix[i][c] = 0;
}
}
}
}

54.螺旋矩阵

题目

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
在这里插入图片描述

代码

class Solution {
public List spiralOrder(int[][] matrix) {
List ans = new ArrayList<>();
int m = matrix.length, n = matrix[0].length;
int left = 0, right = n - 1, top = 0, bottom = m - 1;
while (left <= right && top <= bottom) {
// 从左到右
for (int i = left; i <= right; i++) {
ans.add(matrix[top][i]);
}
top++;
// 从上到下
for (int i = top; i <= bottom; i++) {
ans.add(matrix[i][right]);
}
right–;
// 从右到左
if (top <= bottom) {
for (int i = right; i >= left; i–) {
ans.add(matrix[bottom][i]);
}
}
bottom–;
// 从下到上
if (left <= right) {
for (int i = bottom; i >= top; i–) {
ans.add(matrix[i][left]);
}
}
left++;
}
return ans;
}
}

48.旋转图像

题目

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
在这里插入图片描述
思路：先交换再转置

代码

class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
int[] t = matrix[i];
matrix[i] = matrix[n - i - 1];
matrix[n - i - 1] = t;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int t = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = t;
}
}
}
}

240.搜索二维矩阵II

题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 在这里插入图片描述题意：在行列均有序的矩阵中查找目标值target，如果存在返回true，否则返回false
    思路：Z字查找，类似于将矩阵看成一颗二叉排序树，右上角为根节点，左孩子和右孩子分别小于和大于根节点

代码

class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int n = matrix.length;
int m = matrix[0].length;
int row = 0;
int col = m - 1;
while (row < n && col >= 0) {
if (matrix[row][col] == target) return true;
else if (matrix[row][col] > target) col–;
else row++;
}
return false;
}
}

链表

160.相交链表

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
在这里插入图片描述

代码

class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int len1 = 0;
int len2 = 0;
ListNode p = headA;
ListNode q = headB;
while (p != null) {
p = p.next;
len1++;
}
while (q != null) {
q = q.next;
len2++;
}
p = headA;
q = headB;
if (len1 >= len2) {
for (int i = 0; i < len1 - len2; i++) {
p = p.next;
}
} else {
for (int i = 0; i < len2 - len1; i++) {
q = q.next;
}
}
while (p != q) {
p = p.next;
q = q.next;
}
return p;
}
}
两个链表同时遍历，当两个指针指向不同节点时向后遍历，当遇到空时，即某一链表遍历到了结尾，将此指针指向另一个链表的头部，然后继续遍历，直到两个指针相等。可以用一个等式来说明。
在这里插入图片描述
如图所示的A和B链表，假设A和B不重叠的长度分别为a和b，重叠的部分长度为c，那么两个链表同步遍历时想要同时到达c1点，就需要经过相同的路径，可以让A链表的指针走a+c+b的长度，B链表的指针走b+c+a的长度，这样两个指针走过的路径相同，且能够到达同一个点，具体做法就表现为某一链表遍历到尾部时开始遍历另一个链表。这里有一个情况就是假如两个链表没有交点怎么办，没有交点等于上述等式中的c=0，那么a+b=b+a依然成立，最终指向的都为null，依然会跳出循环。写了下代码，非常精简。
优化
class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode p = headA;
ListNode q = headB;
while (p != q) {
//使用双指针法，p和q分别遍历两个链表。
p = p == null ? headB : p.next;
q = q == null ? headA : q.next;
}
return p;
}
}

206.反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
在这里插入图片描述

代码

/**

  • 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 reverseList(ListNode head) {
    ListNode prev = null;
    ListNode cur = head;
    ListNode temp = null;
    while (cur != null) {
    temp = cur.next;// 保存下一个节点
    cur.next = prev;
    prev = cur;
    cur = temp;
    }
    return prev;
    }
    }

class Solution {
public ListNode reverseList(ListNode head) {
ListNode h = new ListNode();
ListNode p = head;
while (p != null) {
ListNode next = p.next; 保存当前节点的下一个节点
p.next = h.next; 将当前节点插入到新链表的头部
h.next = p; 更新新链表的头节点
p = next; 移动指针p到下一个节点
}
}
return h.next;
}
}

234.回文链表

题目

在这里插入图片描述

代码

/**

  • 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 boolean isPalindrome(ListNode head) {
    ListNode mid = middleNode(head);
    ListNode head2 = reverseList(mid);
    while (head2 != null) {
    if (head.val != head2.val) { // 不是回文链表
    return false;
    }
    head = head.next;
    head2 = head2.next;
    }
    return true;

    }
    // 876. 链表的中间结点
    private ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    }
    return slow;
    }

    // 206. 反转链表
    private ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
    ListNode nxt = cur.next;
    cur.next = pre;
    pre = cur;
    cur = nxt;
    }
    return pre;
    }

}

141.环形链表

题目

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
在这里插入图片描述
题意：判断一个链表是否存在环
思路：快慢指针，一个指针走一步，另一个指针走两步，当两个指针相遇即可判定存在环，如果其中一个指针指向空则说明不存在环。

代码

class Solution {
public boolean hasCycle(ListNode head) {
ListNode p = head;
ListNode q = head;
while (q != null && q.next != null) {
p = p.next;
q = q.next.next;
if (p == q) return true;
}
return false;
}
}


http://www.kler.cn/a/546251.html

相关文章：

  • css: 针对属性left/right/top/bottom为啥设置transition动画不起作用
  • 企业文件共享中的权限管理与安全风险防范
  • 渗透利器：Burp Suite 联动 XRAY 图形化工具.（主动扫描+被动扫描）
  • 常用架构图：业务架构、产品架构、系统架构、数据架构、技术架构、应用架构、功能架构及信息架构
  • 使用Redis实现分布式锁，基于原本单体系统进行业务改造
  • 机器学习入门-读书摘要
  • Webpack和Vite插件的开发与使用
  • 二、OpenSM排障----实战生产
  • ADC入门准备（十）：信号与系统知识回顾
  • Linux Mem -- Where the mte store and check in the real hardware platform
  • 如何下载AndroidStudio的依赖的 jar，arr文件到本地
  • JVM类加载和垃圾回收（详细）
  • 【RAG落地利器】Weaviate、Milvus、Qdrant 和 Chroma 向量数据库对比
  • 群体智能优化：粒子群算法（PSO）详解与实战
  • 如何在微信小程序中添加动画效果
  • Python爬虫实战：利用代理IP获取招聘网站信息
  • Vue 2 路由指南：从基础到高级
  • 机器学习 - 线性模型
  • 在springboot加vue项目中加入图形验证码
  • 【linux】文件与目录命令 - ln