《代码随想录》刷题笔记——数组篇【java实现】

*二分查找

题目链接

https://leetcode.cn/problems/binary-search/

左闭右闭区间实现

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)
/*** 左闭右闭写法** @param nums* @param target* @return*/
public static int search1(int[] nums, int target) {if (nums == null || nums.length == 0) {return -1;}int left = 0;int right = nums.length - 1;// 要是没有等号的话，在{5}里面找5就会出问题了while (left <= right) {int center = (left + right) / 2;if (target == nums[center]) {return center;} else if (target > nums[center]) {left = center + 1;} else {right = center - 1;}}return -1;
}

左闭右开区间实现

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)
/*** 左闭右开写法** @param nums* @param target* @return*/
public static int search2(int[] nums, int target) {if (nums == null || nums.length == 0) {return -1;}int left = 0;// 区别点int right = nums.length;// 区别点while (left < right) {int center = (left + right) / 2;if (target == nums[center]) {return center;} else if (target > nums[center]) {left = center + 1;} else {// 区别点// 虽然已经知道center位置的元素不是要找的元素，但是因为是左闭右开，因此right还是指向center// 后面无论怎么循环，都不会再使用到center这个为止，因为center = (left + right) / 2永远小于rightright = center;}}return -1;
}

*移除元素

题目链接

https://leetcode.cn/problems/remove-element/

暴力求解

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
public static int removeElement(int[] nums, int val) {int sameNum = 0;int i = 0;while (i < nums.length - sameNum) {if (val == nums[i]) {// 将后面的元素前移过来for (int j = i; j < nums.length - 1 - sameNum; j++) {nums[j] = nums[j + 1];}sameNum++;}if (val == nums[i]) {// 前移过来的数值和val一样，将i--i--;}i++;}return nums.length - sameNum;
}

双指针

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

【思想】

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作，将快指针的值赋给慢指针

slow：新数组存储值的索引，因为每次存储完新数组的值，都会将slow++，因此最后直接返回slow即可，需要返回slow+1

fast：用来去前面探索那些不是val的值，然后将这个值赋给slow对应的位置

在这里插入图片描述

/*** 双指针** @param nums* @param val* @return*/
public static int removeElement1(int[] nums, int val) {int slow = 0;for (int fast = 0; fast < nums.length; fast++) {if (nums[fast] != val) {// 如果快指针找的数值不是val，就需要将其存储到新数组中// 同时slow++，以便存储下一个新数组的值nums[slow++] = nums[fast];}}return slow;
}

相向双指针法

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

上面的实现方法并没有改变元素的相对位置，相向双指针方法改变了元素相对位置，但是确保移动最少元素

在这里插入图片描述

/*** 想向双指针** @param nums* @param val* @return*/
public static int removeElement(int[] nums, int val) {int slow = 0, fast = nums.length - 1;while (slow <= fast) {// slow赋值为第一个等于val的索引while (slow <= fast) {if (nums[slow] != val) {slow++;} else {break;}}// fast赋值为最后一个等于val的索引while (fast >= slow) {if (nums[fast] == val) {fast--;} else {break;}}if (slow < fast) {nums[slow++] = nums[fast--];}}// slow最后一定指向的是 新数组末尾元素的下一个元素return slow;
}

*有序数组的平方

题目链接

https://leetcode.cn/problems/squares-of-a-sorted-array/

暴力求解

  1. 先对数组的每个元素求平方
  2. 对数组升序排序

时间复杂度：O(n)+排序算法的时间复杂度

双指针

【思路】

数组本身就是非递减顺序的，只不过负数在平方之后可能会变大，因此只需要用两端来比较就能知道那个数字的平方更大

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

在这里插入图片描述

public static int[] sortedSquares(int[] nums) {int left = 0, right = nums.length - 1;// 用于存储排序之后的结果int[] result = new int[nums.length];for (int i = nums.length - 1; i >= 0; i--) {int leftValue = nums[left];int rightValue = nums[right];if (leftValue * leftValue >= rightValue * rightValue) {result[i] = leftValue * leftValue;left++;} else {result[i] = rightValue * rightValue;right--;}System.out.println(Arrays.toString(result));}return result;
}

*长度最小的子数组

题目链接

https://leetcode.cn/problems/minimum-size-subarray-sum/

暴力求解

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)

注意，子数组是原数组中连续的几个元素的集合

public int minSubArrayLen(int target, int[] nums) {// 最小子数组长度int minLen = nums.length + 1;for (int i = 0; i < nums.length; i++) {int sum = 0;for (int j = i; j < nums.length; j++) {sum += nums[j];if (sum >= target) {// 已经>=target，可以暂停了if ((j - i + 1) < minLen) {minLen = j - i + 1;break;}}}}return minLen == nums.length + 1 ? 0 : minLen;
}

部分案例已经超出时间限制

在这里插入图片描述

滑动窗口

  • 时间复杂度：O(n)：不能以为for里放一个while就是O(n^2)， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)
  • 空间复杂度：O(1)

在这里插入图片描述

/*** 滑动窗口** @param target* @param nums* @return*/
public int minSubArrayLen1(int target, int[] nums) {// 最小子数组长度int minLen = nums.length + 1;int i = 0;int sum = 0;for (int j = 0; j < nums.length; j++) {// j++，窗口终止位置后移一位，sum添加相应的元素sum += nums[j];while (sum >= target) {// 窗口内的元素总和已经超过target，尝试将窗口的起始位置后移，即i++if ((j - i + 1) < minLen) {minLen = j - i + 1;}// sum移除窗口起始位置的元素值sum -= nums[i++];}}return minLen == nums.length + 1 ? 0 : minLen;
}

螺旋矩阵

【思想】

这道题主要是考代码能力，注意每次循环都是左开右闭就行

【我写的程序】

public static int[][] generateMatrix1(int n) {int[][] result = new int[n][n];int curNum = 1;int target = n * n;int initN = n;// 圈数int cirCleNum = 0;while (curNum <= target) {if (curNum == target) {result[cirCleNum][cirCleNum] = curNum;System.out.println("---------------------填中心---------------------");for (int i = 0; i < result.length; i++) {System.out.println(Arrays.toString(result[i]));}break;}// 填上边for (int i = 0; i < n - 1; i++) {result[cirCleNum][i + cirCleNum] = curNum++;}System.out.println("---------------------填上边---------------------");for (int i = 0; i < result.length; i++) {System.out.println(Arrays.toString(result[i]));}// 填右边for (int i = 0; i < n - 1; i++) {result[i + cirCleNum][initN - 1 - cirCleNum] = curNum++;}System.out.println("---------------------填右边---------------------");for (int i = 0; i < result.length; i++) {System.out.println(Arrays.toString(result[i]));}// 填下边for (int i = n - 1; i > 0; i--) {result[initN - 1 - cirCleNum][i + cirCleNum] = curNum++;}System.out.println("---------------------填下边---------------------");for (int i = 0; i < result.length; i++) {System.out.println(Arrays.toString(result[i]));}// 填左边for (int i = n - 1; i > 0; i--) {result[i + cirCleNum][cirCleNum] = curNum++;}System.out.println("---------------------填左边---------------------");for (int i = 0; i < result.length; i++) {System.out.println(Arrays.toString(result[i]));}System.out.println("======================================================================");cirCleNum += 1;n -= 2;}return result;
}

【别人的代码】

public int[][] generateMatrix(int n) {int loop = 0;  // 控制循环次数int[][] res = new int[n][n];int start = 0;  // 每次循环的开始点(start, start)int count = 1;  // 定义填充数字int i, j;while (loop++ < n / 2) { // 判断边界后，loop从1开始// 模拟上侧从左到右for (j = start; j < n - loop; j++) {res[start][j] = count++;}// 模拟右侧从上到下for (i = start; i < n - loop; i++) {res[i][j] = count++;}// 模拟下侧从右到左for (; j >= loop; j--) {res[i][j] = count++;}// 模拟左侧从下到上for (; i >= loop; i--) {res[i][j] = count++;}start++;}if (n % 2 == 1) {res[start][start] = count;}return res;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/123447.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

攻防世界-WEB-php_rce

攻防世界-WEB-php_rce

打开靶机链接 搜村ThinkPhP V5存在远程命令执行的漏洞 构建payload /index.php?sindex/think\app/invokefunction&functioncall_user_func_array&vars[0]system&vars[1][]ls 查询当前目录文件&#xff0c;没有发现flag。调整payload 得到flag文件&#xff0c;修…
阅读更多...
springBoot-使用idea创建项目添加依赖并实现数据查询

springBoot-使用idea创建项目添加依赖并实现数据查询

一、使用idea创建springBoot项目 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://mave…
阅读更多...
【Java基础】深入理解反射、反射的应用（工厂模式、代理模式）

【Java基础】深入理解反射、反射的应用（工厂模式、代理模式）

文章目录 1. Java反射机制是什么&#xff1f;1.2 Java反射例子 2. Java反射机制中获取Class的三种方式及区别&#xff1f;3. Java反射机制的应用场景有哪些&#xff1f;3.1. 优化静态工厂模式&#xff08;解耦&#xff09;3.1.1 优化前&#xff08;工厂类和产品类耦合&#xff…
阅读更多...
剑指 Offer 04. 二维数组中的查找

剑指 Offer 04. 二维数组中的查找

题目描述 在一个 n * m 的二维数组中&#xff0c;每一行都按照从左到右 非递减 的顺序排序&#xff0c;每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数&#xff0c;输入这样的一个二维数组和一个整数&#xff0c;判断数组中是否含有该整数。 解题思路 注意每…
阅读更多...
Android 状态栏显示运营商名称

Android 状态栏显示运营商名称

Android 原生设计中在锁屏界面会显示运营商名称&#xff0c;用户界面中&#xff0c;大概是基于 icon 数量长度显示考虑&#xff0c;对运营商名称不作显示。但是国内基本都加上运营商名称。对图标显示长度优化基本都是&#xff1a;缩小运营商字体、限制字数长度、信号图标压缩上…
阅读更多...
案例聚焦：F5怎么样提升游戏玩家体验？

案例聚焦：F5怎么样提升游戏玩家体验？

对手机游戏市场有过了解的小伙伴&#xff0c;定然对Deltatech Gaming Limited这个公司不会陌生。作为印度在线游戏和娱乐行业的领跑者&#xff0c;两个最受欢迎的多人游戏应用分别为多人游戏的 “Addagames” 和扑克类游戏 “Adda52” &#xff0c;它们会定期举办在线联赛。而这…
阅读更多...
php 获取今日、昨日、上周、本月的起始时间戳和结束时间戳的方法非常简单

php 获取今日、昨日、上周、本月的起始时间戳和结束时间戳的方法非常简单

php 获取今日、昨日、上周、本月的起始时间戳和结束时间戳的方法&#xff0c;主要使用到了 php 的时间函数 mktime。下面首先还是以示例说明如何使用 mktime 获取今日、昨日、上周、本月的起始时间戳和结束时间戳&#xff0c;然后在介绍一下 mktime 函数作用和用法。非常简单哦…
阅读更多...
Windows云服务器 PHP搭建网站外网无法访问的问题

Windows云服务器 PHP搭建网站外网无法访问的问题

前言&#xff1a;本人在华为云上租了一台windows的云主机&#xff0c;可以远程访问桌面的那种&#xff0c;然后想搭个网站&#xff0c;最开始想到的是IIS&#xff0c;测试了下用html的文件&#xff0c;没有问题。但是&#xff0c;php文件却不能用&#xff0c;因为少了PHP环境。…
阅读更多...
Layer 2盛夏已至，StarkNet如何实现价值跃迁？

Layer 2盛夏已至，StarkNet如何实现价值跃迁？

作者&#xff5c;Jason Jiang Layer 2概念在2023年夏天迎来爆发。Coinbase、ConsenSys等加密巨头纷纷下场&#xff0c;其部署的原生L2解决方案Base、Linea在过去两个月内相继完成主网上线&#xff1b;被誉为L2 四大天王之一的StarkNet也在夏天顺利完成“量子跃迁”升级&#x…
阅读更多...
JavaSE，无框架实现贪吃蛇

JavaSE，无框架实现贪吃蛇

JavaSE&#xff0c;无框架实现贪吃蛇 文章目录 JavaSE&#xff0c;无框架实现贪吃蛇1.整体思考2.可能的难点思考2.1 如何表示游戏界面2.2 如何渲染游戏界面2.3 如何让游戏动起来2.4 蛇如何移动 3.流程图制作4.模块划分5.模块完善5.0常量优化5.1监听键盘服务i.输入存储ii.键盘监…
阅读更多...
Direct3D颜色

Direct3D颜色

在Direct3D中颜色用RGB三元组来表示&#xff0c;RGB数据可用俩种不同的结构来保存&#xff0c;第一种是D3DCOLOR&#xff0c;它实际上与DWORD类型完全相同&#xff0c;共有32位&#xff0c;D3DCOLOR类型种的各位被分成四个8位项&#xff0c;每项存储了一种颜色分量的亮度值。 由…
阅读更多...
JDK7多线程并发环境HashMap死循环infinite loop，CPU拉满100%，Java

JDK7多线程并发环境HashMap死循环infinite loop，CPU拉满100%，Java

JDK7多线程并发环境HashMap死循环infinite loop&#xff0c;CPU拉满100%&#xff0c;Java HashMap底层数据实现是数组链表&#xff0c;链表在哈希碰撞后装入新数据&#xff0c;像是一个桶。 HashMap在JDK7的实现中&#xff0c;并发环境存在死循环infinite loop问题。导致的结果…
阅读更多...
DAY-01--分布式微服务基础概念

DAY-01--分布式微服务基础概念

一、项目简介 了解整体项目包含后端、前端、周边维护。整个项目的框架知识。 二、分布式基础概念 1、微服务 将应用程序 基于业务 拆分为 多个小服务&#xff0c;各小服务单独部署运行&#xff0c;采用http通信。 2、集群&分布式&节点 集群是个物理形态&#xff0c;…
阅读更多...
Redis：StringRedisTemplate简介

Redis：StringRedisTemplate简介

&#xff08;笔记总结自b站黑马程序员课程&#xff09; 为了在反序列化时知道对象的类型&#xff0c;JSON序列化器会将类的class类型写入json结果中&#xff0c;存入Redis&#xff0c;会带来额外的内存开销。 为了减少内存的消耗&#xff0c;我们可以采用手动序列化的方式&am…
阅读更多...
【Python】【Fintech】用Python和蒙特卡洛法预测投资组合未来收益

【Python】【Fintech】用Python和蒙特卡洛法预测投资组合未来收益

【背景】 想利用蒙特卡洛方法和yahoo，stooq等财经网站上的数据快速预测特定portfolio的收益。 【分析】 整个程序的功能包括 读取json中的portfolio组合创建蒙特卡洛模拟预测收益的算法创建从财经网站获得特定投资组合数据，并根据2的算法获得该Index或Portfolio收益预测结…
阅读更多...
机器学习的第一节基本概念的相关学习

机器学习的第一节基本概念的相关学习

目录 1.1 决策树的概念 1.2 KNN的概念 1.2.1KNN的基本原理 1.2.2 流程&#xff1a; 1.2.3 优缺点 1.3 深度学习 1.4 梯度下降 损失函数 1.5 特征与特征选择 特征选择的目的 1.6 python中dot函数总结 一维数组的点积&#xff1a; 二维数组&#xff08;矩阵&#xff09;的乘法&am…
阅读更多...
Python代码雨

Python代码雨

系列文章 序号文章目录直达链接1浪漫520表白代码https://want595.blog.csdn.net/article/details/1306668812满屏表白代码https://want595.blog.csdn.net/article/details/1297945183跳动的爱心https://want595.blog.csdn.net/article/details/1295031234漂浮爱心https://want…
阅读更多...
python通过docker打包执行

python通过docker打包执行

背景 正常情况下，python脚本执行需要安装有python环境，那python环境虽然也可以通过移植的方法来安装，那总归是比较麻烦的，下面通过docker打包的方式来执行python脚本 1、安装python镜像 准备两个文件即可，dockerfile、requirements.txt两个文件的内容分别如下 同目录下…
阅读更多...
肖sir__设计测试用例方法之梳理测试点11（微信发红包）

肖sir__设计测试用例方法之梳理测试点11（微信发红包）

梳理测试点 讲解测试点&#xff1a; 1、定义&#xff1a;测试点就是测试的功能点&#xff0c;是指在软件测试过程中需要覆盖或关注的特定功能&#xff0c;特性或场景。 2、流程&#xff1a;拿到需求&#xff0c;梳理测试点(一般使用xmind图梳理)&#xff0c;在根据测试点使用测…
阅读更多...
Python爬虫-爬取文档内容，如何去掉文档中的表格，并保存正文内容

Python爬虫-爬取文档内容，如何去掉文档中的表格，并保存正文内容

前言 本文是该专栏的第58篇，后面会持续分享python爬虫干货知识，记得关注。 做过爬虫项目的同学，可能或多或少爬取过文档数据，比如说“政务网站，新闻网站，小说网站”等平台的文档数据。爬取文档数据，笔者这里就不过多详述，而本文，笔者将主要介绍在爬取文档数据的过程中…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023