首页
关于
Search
1
python初学示例
547 阅读
2
欢迎使用 Typecho
510 阅读
3
晒谷子
486 阅读
4
痛
466 阅读
5
蓝桥杯2022年第十三届省赛真题-X进制减法
460 阅读
默认分类
登录
Search
Typecho
累计撰写
35
篇文章
累计收到
10
条评论
首页
栏目
默认分类
页面
关于
搜索到
35
篇与
默认分类
的结果
2024-03-03
128. 最长连续序列
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。示例 1:输入:nums = [100,4,200,1,3,2]输出:4解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2:输入:nums = [0,3,7,2,5,8,4,6,0,1]输出:9提示:0 <= nums.length <= 105-109 <= nums[i] <= 109拿HashSet存储数组,达到去重,和快速判断是否有这个元素设置一个 longLength = 0,保存最大长度开始遍历数组当当前元素i不存在n-1时,就代表它是这个序列长度中最小的一个,设置int count = 1,这个要算长度的,再设置current = i;开始while(set.contains(current+1)) //判断有无这个数有count++,current +=1;再比较count和longLength,赋值给longLengthreturnclass Solution { public int longestConsecutive(int[] nums) { HashSet<Integer> integers = new HashSet<>(); for (Integer i:nums ) { integers.add(i); } int longLenght = 0; int count = 0; int current = 0; for (Integer i:nums ) { if (!integers.contains(i-1)){ current = i; count = 1; while (integers.contains(current+1)){ current+=1; count++; } longLenght = Math.max(count,longLenght); } } return longLenght; } }
2024年03月03日
45 阅读
0 评论
0 点赞
2024-02-15
2024-02-15打卡BFS
层序遍历层序遍历给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。示例 1:输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]]示例 2:输入:root = [1] 输出:[[1]]示例 3:输入:root = [] 输出:[]提示:树中节点数目在范围 [0, 2000] 内-1000 <= Node.val <= 1000 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { //采用队列形式,父节点进了之后让子节点进 Queue<TreeNode> treeNodes = new LinkedList<>(); List<List<Integer>> arrayLists = new ArrayList<>(); ArrayList<Integer> list = new ArrayList<>(); if (root!=null){ treeNodes.add(root); } while (!treeNodes.isEmpty()){ //只能每一次获取队列的大小,不然会wA int n = treeNodes.size(); for (int i = 0; i < n; i++) { TreeNode poll = treeNodes.poll(); if (poll.left!=null){ treeNodes.add(poll.left); } if (poll.right!=null){ treeNodes.add(poll.right); } list.add(poll.val); } arrayLists.add(list); list = new ArrayList<>(); } return arrayLists; } } //leetcode submit region end(Prohibit modification and deletion)层序遍历 Ⅱ给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)示例 1:输入:root = [3,9,20,null,null,15,7] 输出:[[15,7],[9,20],[3]]示例 2:输入:root = [1] 输出:[[1]]示例 3:输入:root = [] 输出:[]提示:树中节点数目在范围 [0, 2000] 内-1000 <= Node.val <= 1000与上题不同的就只是插入大列表的时候是从头插class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { LinkedList<TreeNode> treeNodes = new LinkedList<>(); List<List<Integer>> lists = new ArrayList<>(); ArrayList<Integer> integers = new ArrayList<>(); if (root!=null){ treeNodes.add(root); } while(!treeNodes.isEmpty()){ int n = treeNodes.size(); for (int i = 0;i<n;i++){ TreeNode poll = treeNodes.poll(); integers.add(poll.val); if (poll.left!=null){ treeNodes.add(poll.left); } if(poll.right!=null){ treeNodes.add(poll.right); } } lists.add(0,integers); integers = new ArrayList<Integer>(); } return lists; } }给定一个二叉树 root ,返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。示例 1:输入:root = [3,9,20,null,null,15,7] 输出:3示例 2:输入:root = [1,null,2] 输出:2提示:树中节点的数量在 [0, 104] 区间内。-100 <= Node.val <= 100class Solution { public int maxDepth(TreeNode root) { Queue<TreeNode> treeNodes = new LinkedList<TreeNode>(); int i = 0; if (root!=null){ treeNodes.add(root); } while(!treeNodes.isEmpty()){ int n = treeNodes.size(); for (int j = 0; j < n; j++) { TreeNode poll = treeNodes.poll(); if (poll.left!=null){ treeNodes.add(poll.left); } if (poll.right!=null){ treeNodes.add(poll.right); } } i++; } return i; } }给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。示例 1:输入:root = [3,9,20,null,null,15,7] 输出:[[3],[20,9],[15,7]]示例 2:输入:root = [1] 输出:[[1]]示例 3:输入:root = [] 输出:[]提示:树中节点数目在范围 [0, 2000] 内-100 <= Node.val <= 100class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); List<List<Integer>> arrayLists = new ArrayList<>(); ArrayList<Integer> list = new ArrayList<>(); boolean q = false; if (root!=null){ queue.add(root); } while(!queue.isEmpty()){ int n = queue.size(); for (int i = 0; i < n; i++) { TreeNode poll = queue.poll(); list.add(poll.val); if (poll.left!=null){ queue.add(poll.left); } if(poll.right!=null){ queue.add(poll.right); } } if (q){ Collections.reverse(list); } arrayLists.add(list); list = new ArrayList<Integer>(); q=!q; } return arrayLists; } }给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明:叶子节点是指没有子节点的节点。示例 1:输入:root = [3,9,20,null,null,15,7] 输出:2示例 2:输入:root = [2,null,3,null,4,null,5,null,6] 输出:5提示:树中节点数的范围在 [0, 105] 内-1000 <= Node.val <= 1000考虑左右都没子节点class Solution { public int minDepth(TreeNode root) { LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); int deep = 0; if (root!=null){ queue.add(root); }else{ return deep; } while(!queue.isEmpty()){ int n = queue.size(); for (int i = 0; i < n; i++) { TreeNode poll = queue.poll(); if (poll.left!=null){ queue.add(poll.left); } if (poll.right!=null){ queue.add(poll.right); } if (poll.left==null&&poll.right==null){ return ++deep; } } deep++; } return deep; } }给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。叶子节点 是指没有子节点的节点。示例 1:输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出:true 解释:等于目标和的根节点到叶节点路径如上图所示。示例 2:输入:root = [1,2,3], targetSum = 5 输出:false 解释:树中存在两条根节点到叶子节点的路径: (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。示例 3:输入:root = [], targetSum = 0 输出:false 解释:由于树是空的,所以不存在根节点到叶子节点的路径。提示:树中节点的数目在范围 [0, 5000] 内-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { LinkedList<TreeNode> queue = new LinkedList<>(); ArrayList<Integer> integers = new ArrayList<>(); if(root!=null){ queue.add(root); TreeNode poll = queue.poll(); if (poll.left!=null){ poll.left.val += poll.val; queue.add(poll.left); } if (poll.right!=null){ poll.right.val +=poll.val; queue.add(poll.right); } if (poll.left==null&&poll.right==null){ integers.add(poll.val); } } while(!queue.isEmpty()){ int n = queue.size(); for (int i = 0; i < n; i++) { TreeNode poll = queue.poll(); if (poll.left!=null){ poll.left.val += poll.val; queue.add(poll.left); } if (poll.right!=null){ poll.right.val +=poll.val; queue.add(poll.right); } if (poll.left==null&&poll.right==null){ integers.add(poll.val); } } } int i = integers.indexOf(targetSum); if (i!=-1){ return true; }else{ return false; } } }给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:struct Node { int val; Node *left; Node *right; Node *next; }填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。初始状态下,所有 next 指针都被设置为 NULL。示例 1:输入:root = [1,2,3,4,5,6,7] 输出:[1,#,2,3,#,4,5,6,7,#] 解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,'#' 标志着每一层的结束。示例 2:输入:root = [] 输出:[]提示:树中节点的数量在 [0, 212 - 1] 范围内-1000 <= node.val <= 1000class Solution { public Node connect(Node root) { LinkedList<Node> nodes = new LinkedList<Node>(); ArrayList<Node> list = new ArrayList<Node>(); if(root!=null){ nodes.add(root); } while(!nodes.isEmpty()){ int n = nodes.size(); for (int i = 0; i < n; i++) { Node poll = nodes.poll(); list.add(poll); if (poll.left!=null){ nodes.add(poll.left); } if (poll.right!=null){ nodes.add(poll.right); } } for (int i = 0; i < list.size()-1; i++) { list.get(i).next = list.get(i+1); } list.get(list.size()-1).next=null; list.clear(); } return root; } }
2024年02月15日
47 阅读
0 评论
0 点赞
2023-09-08
修车的最少时间
给你一个整数数组 ranks ,表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。同时给你一个整数 cars ,表示总共需要修理的汽车数目。请你返回修理所有汽车 最少 需要多少时间。注意:所有机械工可以同时修理汽车。示例 1:输入:ranks = [4,2,3,1], cars = 10输出:16解释:第一位机械工修 2 辆车,需要 4 2 2 = 16 分钟。第二位机械工修 2 辆车,需要 2 2 2 = 8 分钟。第三位机械工修 2 辆车,需要 3 2 2 = 12 分钟。第四位机械工修 4 辆车,需要 1 4 4 = 16 分钟。分钟是修理完所有车需要的最少时间。示例 2:输入:ranks = [5,1,8], cars = 6输出:16解释:第一位机械工修 1 辆车,需要 5 1 1 = 5 分钟。第二位机械工修 4 辆车,需要 1 4 4 = 16 分钟。第三位机械工修 1 辆车,需要 8 1 1 = 8 分钟。分钟时修理完所有车需要的最少时间。提示:1 <= ranks.length <= 1051 <= ranks[i] <= 1001 <= cars <= 106根据题解的思路由于无法判断每一个修车师傅修的具体数量,但是可以假设时间为t则每个师傅修车的数量为sqrt(t/r),这个函数的自变量为t,故函数为单调递增的将每一个修车师傅的数量加上大于等于cars,那么这个时间就是ok的采用二分法先写一个check()函数 private boolean check(int[] ranks,long m,long cars){ long x=0;//用来求和 for(int i=0;i<ranks.length;i++) { x+=Math.sqrt(m/ranks[i]);//求在当前t下,每一个师傅的修车数,并叠加 } return x>=cars;//是否总数大于cars }再采用二分public long repairCars(int[] ranks, int cars) { long l=0; long r=1l*ranks[0]*cars*cars;//这是假设的最大时间,可以换成rank[rank.length-1]*cars*cars; while(l<r){ long m=l+r>>1;//取中间的时间 if(check(ranks,m,cars)){ r=m;//如果满足check函数,则说明右侧所有时间都可以满足,那我们就需要把中间点向左侧移动 }else{ l=m+1;//同理 } } return l; }完整代码class Solution { public long repairCars(int[] ranks, int cars) { long l=0; long r=1l*ranks[0]*cars*cars;//这是假设的最大时间,可以换成rank[rank.length-1]*cars*cars; while(l<r){ long m=l+r>>1;//取中间的时间 if(check(ranks,m,cars)){ r=m;//如果满足check函数,则说明右侧所有时间都可以满足,那我们就需要把中间点向左侧移动 }else{ l=m+1;//同理 } } return l; } private boolean check(int[] ranks,long m,long cars){ long x=0;//用来求和 for(int i=0;i<ranks.length;i++) { x+=Math.sqrt(m/ranks[i]);//求在当前t下,每一个师傅的修车数,并叠加 } return x>=cars;//是否总数大于cars } }
2023年09月08日
146 阅读
0 评论
0 点赞
2023-03-05
基于点灯科技的esp8266控制舵机
材料:esp8266 nodeMcu SG90;接线 3v D5 GND;引脚图 代码#define BLINKER_PRINT Serial #define BLINKER_WIFI #include<Servo.h> #include <Blinker.h> Servo myservo; //定义一个舵机对象 int _servo = 14; char auth[] = "your key"; char ssid[] = "mywifi";//wifi ssid char pswd[] = "12345678";// wifi password // 新建组件对象 BlinkerButton Button1("btn-abc"); BlinkerNumber Number1("num-abc"); BlinkerButton btn2("round_max"); BlinkerButton btn3("round_min"); int counter = 0; // 按下按键即会执行该函数 void button1_callback(const String & state) { BLINKER_LOG("get button state: ", state); digitalWrite(LED_BUILTIN, !digitalRead(LED_BUILTIN)); } //按下按钮round_max旋转舵机到最大值 void button2_callback(const String & state){ Serial.println(state); BLINKER_LOG("get button state: ", 180); myservo.write(180); Blinker.vibrate(); // delay(10); // myservo.write(0); // Blinker.vibrate(); } //按下按钮round_min旋转舵机到最小值 void button3_callback(const String & state){ Serial.println(state); BLINKER_LOG("get button state: ", 0); myservo.write(0); Blinker.vibrate(); // delay(10); // myservo.write(0); // Blinker.vibrate(); } // 如果未绑定的组件被触发,则会执行其中内容 void dataRead(const String & data) { BLINKER_LOG("Blinker readString: ", data); counter++; Number1.print(counter); } void setup() { // 初始化串口 Serial.begin(9600); #if defined(BLINKER_PRINT) BLINKER_DEBUG.stream(BLINKER_PRINT); #endif myservo.attach(_servo); //设置指定的IO为舵机 myservo.write(0); // 初始化有LED的IO pinMode(LED_BUILTIN, OUTPUT); digitalWrite(LED_BUILTIN, HIGH); // 初始化blinker Blinker.begin(auth, ssid, pswd); Blinker.attachData(dataRead); Button1.attach(button1_callback); btn2.attach(button2_callback); btn3.attach(button3_callback); } void loop() { Blinker.run(); }
2023年03月05日
330 阅读
1 评论
0 点赞
2023-02-13
截断数组
题目给定一个长度为 n 的数组 a1,a2,…,an。现在,要将该数组从中间截断,得到三个非空子数组。要求,三个子数组内各元素之和都相等。请问,共有多少种不同的截断方法?输入格式第一行包含整数 n。第二行包含 n 个整数 a1,a2,…,an。输出格式输出一个整数,表示截断方法数量。数据范围前六个测试点满足 1≤n≤10。所有测试点满足 1≤n≤105,−10000≤ai≤10000。输入样例1:41 2 3 3输出样例1:1输入样例2:51 2 3 4 5输出样例2:0输入样例3:20 0输出样例3:0分析我们数组开辟100010个输入从i=1开始先对数组进行求一个前缀和,取前缀和最后一位得到总和,如果sum%3!=0那么这个数组是不能进行截断的total%3==0,满足该条件下的数组是绝对可以进行截断 我们对前缀和数组进行一个遍历遍历sum[i]==total/3时 cns++;sum[i]==total/3*2时 count++;我们最后的结果其实就是res = count*cns边界问题for(int i=2;i<=n-1;i++)i=2的原因:因为说的是三份,非空,所以第一份数组必须至少包含i=1i<=n-1的原因:最后一个i=n;第三个数组必须至少包含i=n#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; int a[N]; long long sum[N]; int main() { int n; long long cns=0,count=0,total=0,ave=0; cin >> n; for (int i = 1; i <= n; i ++ ) { scanf("%d",&a[i]); sum[i]=a[i]; sum[i]+=sum[i-1]; total+=a[i]; } if(total%3!=0) { cout << "0"<<endl; }else{ ave=total/3; for(int i=2;i<=n-1;i++) { if(ave==sum[i-1]) cns++; if(2*ave==sum[i]) count+=cns; } cout << count<<endl; } }
2023年02月13日
284 阅读
0 评论
0 点赞
1
2
...
7