首页 文章 精选 留言 我的

精选列表

搜索[国密算法],共10000篇文章
优秀的个人博客,低调大师

leetcode算法题学习Java版(1)

队列和广度优先搜索 岛屿的个数 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。 https://leetcode-cn.com/explore/learn/card/queue-stack/217/queue-and-bfs/872/ 解题思路:广度优先,从某个为1的点开始,广度优先搜索他附近所有为1的点,将这些点的值改为2防止重复。计算有多少次将相邻的1改为2的次数,即为岛屿的次数。 class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) return 0 ; int row = grid.length;//行数 int column = grid[0].length;//列数 int count = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < column; j++) { if (grid[i][j] == '1'){ count ++; combine(grid,i,j); } } } return count; } public static void combine(char[][] grid, int x, int y){ grid[x][y] = '2'; if (x > grid.length-1 && y > grid[0].length-1 ) { return; } if (x < grid.length-1 && grid[x+1][y] == '1') { //向下 combine(grid,x+1,y); } if (y < grid[0].length-1 && grid[x][y+1] == '1'){ //向右 combine(grid,x,y+1); } if (x > 0 && grid[x-1][y] == '1' ){ //向上 combine(grid,x-1,y); } if (y > 0 && grid[x][y-1] == '1') { //向左 combine(grid,x,y-1); } } } 打开转盘锁 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转:例如把 '9' 变为 '0','0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。 锁的初始数字为 '0000' ,一个代表四个拨轮的数字的字符串。 列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。 字符串 target 代表可以解锁的数字,你需要给出最小的旋转次数,如果无论如何不能解锁,返回 -1。 https://leetcode-cn.com/explore/learn/card/queue-stack/217/queue-and-bfs/873/ 解题思路:将这道题看作是一道迷宫题,每次找一个数字当前能一步到的其他所有邻居数字,次数加1,所有邻居数字再找邻居数字的邻居数字,直到找到一个正确路径。 package com.ice.leetcode; import java.util.*; public class Solution { public static void main(String[] args) { String[] deadends = {"8887","8889","8878","8898","8788","8988","7888","9888"}; String target = "8888"; int count = openLock(deadends, target); System.out.println(count); } public static int openLock(String[] deadends, String target) { String start = "0000"; List<String> visited = new ArrayList<String>(); visited.add(start); Queue<String> queue = new LinkedList<String>(); int count = 0; queue.offer(start); while (!queue.isEmpty()) { int len = queue.size(); for (int i = 0; i < len; i++) { String top = queue.peek(); queue.poll(); List<String> neibors = findNeibors(top); for (String neibor:neibors) { if (target.equals(neibor)) { count++; return count; } if (findString(visited, neibor)) { continue; } if (!findString(Arrays.asList(deadends), neibor)) { visited.add(neibor); queue.offer(neibor); } } } count++; } return -1; } public static List<String> findNeibors(String s) { String temp = s; List<String> result = new ArrayList<>(); for (int i = 0; i < s.length(); i++) { char[] charTemp = temp.toCharArray(); charTemp[i] = String.valueOf((Integer.parseInt(String.valueOf(charTemp[i])) + 1) % 10).toCharArray()[0]; // charTemp[i] = (char) ((Integer.parseInt(String.valueOf(charTemp[i])) + 1) % 10); result.add(String.valueOf(charTemp)); charTemp[i] = String.valueOf((Integer.parseInt(String.valueOf(charTemp[i])) + 8) % 10).toCharArray()[0]; result.add(String.valueOf(charTemp)); } return result; } public static boolean findString(List<String> tofind, String s) { for (String temp : tofind) { if (s.equals(temp)) { return true; } } return false; } } 完全平方数 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4. 示例 2: 输入: n = 13 输出: 2 解释: 13 = 4 + 9. https://leetcode-cn.com/explore/learn/card/queue-stack/217/queue-and-bfs/874/ 解题思路:这道题和上一道打开转盘锁思路基本一样,同样是使用广度优先,每遍历一层将count++。不同点在于,本题每层将一个数拆成一个完全平方数和另一个数之和,每次将另一个数加入队列,判断另一个数是否为完全平方数,否则,广度搜索他的下一层。 import static java.lang.Math.sqrt; class Solution { public int numSquares(int n) { int count = 0; Queue<Integer> queue = new LinkedList<>(); if(isSquare(n)){ return 1; } queue.offer(n); while(!queue.isEmpty()){ int len = queue.size(); for (int z=0;z<len;z++){ int top = queue.peek(); queue.poll(); for(int i=0;i<=sqrt(top);i++){ int m = top-i*i; if(isSquare(m)){ count +=2; return count; } if(m==top){ continue; } queue.offer(m); } } count++; } return count; } public static boolean isSquare(int n){ double temp = sqrt(n); int m = (int) temp; return m*m==n; } } 栈和深度优先搜索 有效的括号 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 解题思路:本题较简单,利用堆栈,遇到右括号即一直出栈,判断括号是否匹配 class Solution { public boolean isValid(String s){ Stack<String> stack = new Stack<String>(); for(int i =0;i<s.length();i++){ String temp = s.substring(i,i+1); if(temp.equals("}")||temp.equals("]")||temp.equals(")")){ if(stack.empty()){ return false; } while (!stack.empty()){ String top = stack.peek(); stack.pop(); if((top.equals("{")||top.equals("[")||top.equals("("))){ if(!matchBrackets(top,temp)){ return false; }else { break; } } } }else { stack.push(temp); } } if(stack.isEmpty()){ return true; } return false; } public static boolean matchBrackets(String a,String b){ if( (a.equals("{")&&b.equals("}")) || (a.equals("[")&&b.equals("]")) || (a.equals("(")&&b.equals(")")) ){ return true; } return false; } } 每日温度 根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高的天数。如果之后都不会升高,请输入 0 来代替。 例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的都是 [30, 100] 范围内的整数。 https://leetcode-cn.com/explore/learn/card/queue-stack/218/stack-last-in-first-out-data-structure/879/ 解题思路:本题利用栈,将气温不断入栈,判断下一个气温是否比栈顶的气温高,如果高,则不断出栈直到不比栈顶的温度高,如果,并逐个计算每个出栈元素与这个比他们高的气温的差值天数,最后将这个气温入栈,寻找下一个比他高的气温。直到栈空。 class Solution { public int[] dailyTemperatures(int[] temperatures) { Stack<Entry> stack = new Stack<Entry>(); int[] res = new int[temperatures.length]; for (int i = 0; i < temperatures.length; i ++) { if (stack.isEmpty()) { stack.push(new Entry(temperatures[i], i)); continue; } if (temperatures[i] <= stack.peek().val) stack.push(new Entry(temperatures[i], i)); else { int j = 1; while (!stack.isEmpty() && temperatures[i] > stack.peek().val) { Entry tmp = stack.pop(); res[tmp.index] = i - tmp.index; } stack.push(new Entry(temperatures[i], i)); } } return res; } private class Entry { public int val; public int index; public Entry(int val, int index) { this.val = val; this.index = index; } } } 逆波兰表达式求值 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 说明: 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。 https://leetcode-cn.com/explore/learn/card/queue-stack/218/stack-last-in-first-out-data-structure/880/ 解题思路:本题很简单,不断入栈,遇到运算符就出栈前两位进行运算即可 class Solution { public int evalRPN(String[] tokens){ Stack<String> stack = new Stack<>(); for(int i =0;i<tokens.length;i++){ if(isSimbol(tokens[i])){ int temp1 = Integer.parseInt(stack.pop()); int temp2 = Integer.parseInt(stack.pop()); if(tokens[i].equals("+")){ stack.push(String.valueOf(temp1+temp2)); } if(tokens[i].equals("-")){ stack.push(String.valueOf(temp2-temp1)); } if(tokens[i].equals("*")){ stack.push(String.valueOf(temp1*temp2)); } if(tokens[i].equals("/")){ stack.push(String.valueOf(temp2/temp1)); } }else { stack.push(tokens[i]); } } return Integer.parseInt(stack.pop()); } public static boolean isSimbol(String s){ if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){ return true; } return false; } }

优秀的个人博客,低调大师

Java 最常用的10大算法

String/Array/Matrix 在Java中,String是一个包含char数组和其它字段、方法的类。 toCharArray() //get char array of a String Arrays.sort() //sort an array Arrays.toString(char[] a) //convert to string charAt(int x) //get a char at the specific index length() //string length length //array size substring(int beginIndex) substring(int beginIndex, int endIndex) Integer.valueOf()//string to integer String.valueOf()/integer to string 逆波兰表示法最长回文字符串单词分割字梯两个排序数组的中值正则表达式匹配合并间隔

优秀的个人博客,低调大师

spark ML算法之线性回归使用

版权声明:本文由董可伦首发于https://dongkelun.com,非商业转载请注明作者及原创出处。商业转载请联系作者本人。 https://blog.csdn.net/dkl12/article/details/80259410 我的原创地址:https://dongkelun.com/2018/04/09/sparkMlLinearRegressionUsing/ 前言 本文是讲如何使用spark ml进行线性回归,不涉及线性回归的原理。 1、数据格式 1.1 普通标签格式 1.1.1 格式为: 标签,特征值1 特征值2 特征值3... 1,1.9 2,3.1 3,4 3.5,4.45 4,5.02 9,9.97 -2,-0.98 1.1.2 spark 读取 1、Rdd 旧版(mllib)的线性回归要求传入的参数类型为RDD[LabeledPoint] import org.apache.spark.SparkConf import org.apache.spark.SparkContext import org.apache.spark.mllib.linalg.Vectors import org.apache.spark.mllib.regression.LabeledPoint val data_path = "files/ml/linear_regression_data1.txt" val data = sc.textFile(data_path) val training = data.map { line => val arr = line.split(',') LabeledPoint(arr(0).toDouble, Vectors.dense(arr(1).split(' ').map(_.toDouble))) }.cache() training.foreach(println) 结果: (1.0,[1.9]) (2.0,[3.1]) (3.0,[4.0]) (3.5,[4.45]) (4.0,[5.02]) (9.0,[9.97]) (-2.0,[-0.98]) 一共有两列,第一列可以通过.label获得(类型为Double),第二列可以通过.features获得(类型为Vector[Double]) 2、 DataFrame 新版(ml)的线性回归要求传入的参数类型为Dataset[_] import org.apache.spark.ml.linalg.Vectors import org.apache.spark.sql.Row import spark.implicits._ val data_path = "files/ml/linear_regression_data1.txt" val data = spark.read.text(data_path) val training = data.map { case Row(line: String) => var arr = line.split(',') (arr(0).toDouble, Vectors.dense(arr(1).split(' ').map(_.toDouble))) }.toDF("label", "features") training.show() 结果: +-----+--------+ |label|features| +-----+--------+ | 1.0| [1.9]| | 2.0| [3.1]| | 3.0| [4.0]| | 3.5| [4.45]| | 4.0| [5.02]| | 9.0| [9.97]| | -2.0| [-0.98]| +-----+--------+ 其中列名”label”, “features”固定,不能改为其他列名。 1.2 LIBSVM格式 1.2.1 格式为: label index1:value1 index2:value2 ... 其中每一行的index必须为升序 为了便于理解,造几条多维数据: 1 1:1.9 2:2 4:2 100:3 101:6 2 1:3.1 2:2 4:2 100:3 101:6 3 1:4 2:2 4:2 100:3 101:6 3.5 1:4.45 2:2 4:2 100:3 101:6 4 1:5.02 2:2 4:2 100:3 101:6 9 1:9.97 4:2 100:3 101:6 -2 1:-0.98 2:2 4:2 100:3 201:6 1.2.2 spark 读取 1、Rdd import org.apache.spark.SparkConf import org.apache.spark.SparkContext import org.apache.spark.mllib.util.MLUtils val data_path = "files/ml/linear_regression_data2.txt" val training = MLUtils.loadLibSVMFile(sc, data_path) training.foreach(println) 结果: (1.0,(201,[0,1,3,99,100],[1.9,2.0,2.0,3.0,6.0])) (2.0,(201,[0,1,3,99,100],[3.1,2.0,2.0,3.0,6.0])) (3.0,(201,[0,1,3,99,100],[4.0,2.0,2.0,3.0,6.0])) (3.5,(201,[0,1,3,99,100],[4.45,2.0,2.0,3.0,6.0])) (4.0,(201,[0,1,3,99,100],[5.02,2.0,2.0,3.0,6.0])) (9.0,(201,[0,3,99,100],[9.97,2.0,3.0,6.0])) (-2.0,(201,[0,1,3,99,200],[-0.98,2.0,2.0,3.0,6.0])) 返回类型为RDD[LabeledPoint],其中第一列为label,第二列vector的第一个值为max(index),第二个index-1组成的数组,第三个为value组成的数组。 2、DataFrame val data_path = "files/ml/linear_regression_data2.txt" val data = spark.read.text(data_path) val training = spark.read.format("libsvm").load(data_path) training.show(false) 结果: +-----+--------------------------------------------+ |label|features | +-----+--------------------------------------------+ |1.0 |(201,[0,1,3,99,100],[1.9,2.0,2.0,3.0,6.0]) | |2.0 |(201,[0,1,3,99,100],[3.1,2.0,2.0,3.0,6.0]) | |3.0 |(201,[0,1,3,99,100],[4.0,2.0,2.0,3.0,6.0]) | |3.5 |(201,[0,1,3,99,100],[4.45,2.0,2.0,3.0,6.0]) | |4.0 |(201,[0,1,3,99,100],[5.02,2.0,2.0,3.0,6.0]) | |9.0 |(201,[0,3,99,100],[9.97,2.0,3.0,6.0]) | |-2.0 |(201,[0,1,3,99,200],[-0.98,2.0,2.0,3.0,6.0])| +-----+--------------------------------------------+ 2、线性回归代码 2.1 数据 用libsvm格式的数据: 1 1:1.9 2 1:3.1 3 1:4 3.5 1:4.45 4 1:5.02 9 1:9.97 -2 1:-0.98 2.2 旧版代码 package com.dkl.leanring.spark.ml import org.apache.log4j.{ Level, Logger } import org.apache.spark.{ SparkConf, SparkContext } import org.apache.spark.mllib.regression.LinearRegressionWithSGD import org.apache.spark.mllib.util.MLUtils import org.apache.spark.mllib.regression.LabeledPoint import org.apache.spark.mllib.linalg.Vectors import org.apache.spark.mllib.regression.LinearRegressionModel object OldLinearRegression { def main(args: Array[String]) { // 构建Spark对象 val conf = new SparkConf().setAppName("OldLinearRegression").setMaster("local") val sc = new SparkContext(conf) Logger.getRootLogger.setLevel(Level.WARN) //读取样本数据 val data_path = "files/ml/linear_regression_data3.txt" val training = MLUtils.loadLibSVMFile(sc, data_path) val numTraing = training.count() // 新建线性回归模型,并设置训练参数 val numIterations = 10000 val stepSize = 0.5 val miniBatchFraction = 1.0 //书上的代码 intercept 永远为0 //val model = LinearRegressionWithSGD.train(examples, numIterations, stepSize, miniBatchFraction) var lr = new LinearRegressionWithSGD().setIntercept(true) lr.optimizer.setNumIterations(numIterations).setStepSize(stepSize).setMiniBatchFraction(miniBatchFraction) val model = lr.run(training) println(model.weights) println(model.intercept) // 对样本进行测试 val prediction = model.predict(training.map(_.features)) val predictionAndLabel = prediction.zip(training.map(_.label)) val print_predict = predictionAndLabel.take(20) println("prediction" + "\t" + "label") for (i <- 0 to print_predict.length - 1) { println(print_predict(i)._1 + "\t" + print_predict(i)._2) } // 计算测试误差 val loss = predictionAndLabel.map { case (p, l) => val err = p - l err * err }.reduce(_ + _) val rmse = math.sqrt(loss / numTraing) println(s"Test RMSE = $rmse.") } } 其中注释的第30行代码为书上的写法,但这样写intercept一直为0,也就是只适用于y=a*x的形式,不适用于y=ax+b,改为31、32替代即可。 结果: [0.992894785953067] -0.9446037936869749 prediction label 0.9418962996238525 1.0 2.133370042767533 2.0 3.0269753501252934 3.0 3.473778003804174 3.5 4.039728031797421 4.0 8.954557222265104 9.0 -1.9176406839209805 -2.0 Test RMSE = 0.06866615969192089. 即a=0.992894785953067,b=-0.9446037936869749,y=0.992894785953067*x-0.9446037936869749 2.2 新版代码 package com.dkl.leanring.spark.ml import org.apache.spark.ml.regression.LinearRegression import org.apache.spark.sql.SparkSession object NewLinearRegression { def main(args: Array[String]): Unit = { val spark = SparkSession .builder .appName("NewLinearRegression") .master("local") .getOrCreate() val data_path = "files/ml/linear_regression_data3.txt" import spark.implicits._ import org.apache.spark.ml.linalg.Vectors import org.apache.spark.sql.Row val training = spark.read.format("libsvm").load(data_path) val lr = new LinearRegression() .setMaxIter(10000) .setRegParam(0.3) .setElasticNetParam(0.8) val lrModel = lr.fit(training) println(s"Coefficients: ${lrModel.coefficients} Intercept: ${lrModel.intercept}") val trainingSummary = lrModel.summary println(s"numIterations: ${trainingSummary.totalIterations}") println(s"objectiveHistory: [${trainingSummary.objectiveHistory.mkString(",")}]") trainingSummary.residuals.show() println(s"RMSE: ${trainingSummary.rootMeanSquaredError}") println(s"r2: ${trainingSummary.r2}") trainingSummary.predictions.show() spark.stop() } } 结果: Coefficients: [0.9072296333951224] Intercept: -0.630360819004294 numIterations: 3 objectiveHistory: [0.5,0.41543560544030766,0.08269406021049913] +--------------------+ | residuals| +--------------------+ | -0.0933754844464385| |-0.18205104452058585| |0.001442285423804...| | 0.09318895039599973| | 0.07606805936077965| | 0.5852813740549223| | -0.4805541402684861| +--------------------+ RMSE: 0.2999573166705823 r2: 0.9906296595124621 +-----+---------------+------------------+ |label| features| prediction| +-----+---------------+------------------+ | 1.0| (1,[0],[1.9])|1.0933754844464385| | 2.0| (1,[0],[3.1])| 2.182051044520586| | 3.0| (1,[0],[4.0])|2.9985577145761955| | 3.5| (1,[0],[4.45])|3.4068110496040003| | 4.0| (1,[0],[5.02])|3.9239319406392204| | 9.0| (1,[0],[9.97])| 8.414718625945078| | -2.0|(1,[0],[-0.98])|-1.519445859731514| +-----+---------------+------------------+

资源下载

更多资源
Mario

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长,特征是大鼻子、头戴帽子、身穿背带裤,还留着胡子。与他的双胞胎兄弟路易基一起,长年担任任天堂的招牌角色。

Nacos

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称,一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集,帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Spring

Spring

Spring框架(Spring Framework)是由Rod Johnson于2002年提出的开源Java企业级应用框架,旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念,提供核心容器、应用上下文、数据访问集成等模块,支持整合Hibernate、Struts等第三方框架,其适用范围不仅限于服务器端开发,绝大多数Java应用均可从中受益。

Rocky Linux

Rocky Linux

Rocky Linux(中文名:洛基)是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版,作为CentOS稳定版停止维护后与RHEL(Red Hat Enterprise Linux)完全兼容的开源替代方案,由社区拥有并管理,支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性,采用模块化包装和SELinux安全架构,默认包含GNOME桌面环境及XFS文件系统,支持十年生命周期更新。

用户登录
用户注册