• [技术干货] Java新手小白,Java基础知识-转载
    一、 关键字和保留字关键字(keyword)的定义和特点定义:被Java语言赋予了特殊含义,用做专门用途的字符串(单词)特点:关键字中所有字母都为小写根据分类:数据类型:Boolean、int、long、short、byte、float、double、char、class、interface流程控制:if、else、do、while、for、Switch、case、default、break、continue、return、try、catch、finally修饰符:  public、protected、private、final、void、static、abstract、transient、synchronized、volatile、native动作:package、import、throw 、throws、extends、implements、this、supper、instanceof、new保留字:Java保留字:现有Java版本尚未使用,以后可能会作为关键字使用。命名【标识符】时要避免使用这些保留字goto、const二、标识符什么是标识符Java对各种变量,方法和类等要素命名时使用的字符串序列称为标识符技巧:凡是自己可以 起名字的地方都叫标识符定义合法标识符规则由26个英文字母大小写,0-9,_或$组成数字不能包含空格不可以使用关键字和保留字,但能包含关键字个保留字Java中严格区分大小写,长度无限制Java 中名称命名规范包名:多单词组成时所有字母都小写:xxxxyyyy类名:接口名:多单词组成时,所有单词首字母读大写 : XxxYyy变量名:方法名:多单词组成时,第一个单词首字母小写,第二个单词开始每个单词首字母大写:xxxYyyZzz常量名:所有字母都大写,多单词时每个单词用下划线连接:XXX_YYY_AAA注意点:注意1:在起名字时,为了提高阅读性,要尽量有意义注意2:Java采用Unicode字符集,因此标识符也可以使用汉字声明,但是不建议使用三、变量变量的声明与使用变量的概念: 内存中的一个存储区域该区域的数据可以在同一类型范围内不断变化变量是程序中最基本的存储的单位。包含变量类型  变量名和存储的值变量的作用:用于在内存中保存的数使用变量的注意:Java中每个变量必须先声明,后使用使用变量名来访问这块区域的数据变量的作用域:其定义所在的一对{}内变量只有在其作用域才有效同一个作用域内,不能定义重名的变量声明变量:语法:数据类型  变量名称 int   var;变量的赋值:var =10;声明和赋值变量语法:数据类型  变量名 =初始值int var =10;补充:变量的分类  按声明的位置的不同在方法体外,类体内声明的变量称为成员变量在方法体内,声明的变量称为局部变量所有变量:成员变量、局部变量成员变量和局部变量的区别:成员变量:实例变量(不以static修饰);类变量(以static修饰)局部变量:形参(方法、构造器中定义的变量);方法局部变量(在方法内定*义);代码块局部变量(在代码块内定义)注意:二者在初始值方面的异同异:局部变量除形参外,都需要显式初始化同: 都有生命周期基本数据类型变量的分类  按数据类型对于每一种数据都定义了明确的具体数据类型(强类型语言),在内存中分配了不同大小的内存空间。数据类型包括:基本数据类型和引用数据类型基本数据类型:数值型(整数类型:byte、short、int、long;浮点类型:float、double)、字符型char、布尔型boolean引用数据类型:类class、接口interface、数组 【】整数类型:byte、short、int、longJava各整数类型有固定的表数范围和字段长度,不受OS的影响,以保证Java程序的可移植性。Java的整型常量默认为int型,声明long型常量须后加“l”或‘L’Java程序中变量通常声明为int 型,除非不足以表示较大的数,才使用longbit 计算机中的最小存储单位,byte计算机中基本存储单位下面一个小练习:class VariableTest1 {    public static void main(String[] args) {        //整型:byte(1字节=8bit)  short(2字节)  int(4字节)  long(8字节)        //byte 范围: -128~127         byte b1 = 12;        byte b2 = -128;        //b2=128 编译不通过        System.out.println(b1);        System.out.println(b2);// ② 声明long型变量,必须以“1”或“L”结尾        short s1 = 128;        int i1 = 12345;        long l1 = 345678586;        System.out.println(l1);    }}浮点类型:float 、double 与整数类型类似,Java浮点类型也有固定的表数范围和字段长度,不受具体的操作系统影响。浮点型常量有两种表示形式:十进制数形式:如:5.12 512.0f 0.512 (必须有小数点)科学计数法形式:如:5.12e2 512E2 100E-2float :单精度,尾数可以精确到7有效数字。很多情况下,精度很难满足需求。double :双精度,精度是float 的两倍。通常采用此类型。Java的浮点型常量默认为double 型,声明float 型常量,须后加“ f ”或“ F ” 字符类型:charchar 型数据用来表示通常意义上的“字符”(2字节)Java中所有字符都使用Unicode编码,故一个字符可以存储一个字母,一个汉字,或其他书面语的一个字符。字符型变量的三种形式:字符常量是用单引号(‘’)括起来的单个字符、例如:char c1 = ‘a’; char c2 = ‘中’; char c3 = ‘9’;Java中还可以使用转义字符‘ / ’ 来将其后字符转变为特殊字符型常量 。例如:char c3 = ‘\n’;‘\n’ 表示换行符直接使用Unicode 值来表示字符型常量:‘\uXXXX’。其中,XXXX代表一个十六进制整数。如: \u000a 表示\n。char类型是可以进行运算的。因为它都对应有Unicode码。小练习:编程就需要多动手,看会了理解了还需要多多动手class VariableTest1 {    public static void main(String[] args) {         double d1 = 12.3;        System.out.println(d1 + 1);         //定义float类型变量时,变量要以"f" 或"F"结尾        float f1 = 12.3f;        System.out.println(f1);         //② 通常,定义浮点型变量时,使用double变量        //3. 字符型:char(1字符=2字节)        //① 定义char型变量,通常使用一对''        char c1='a';        System.out.println(c1);         char c2 = '1';        char c3 = '中';        char c4 = '&';        System.out.println(c2);        System.out.println(c3);        System.out.println(c4);         //② 表示方式:1.声明一个字符;2.转义字符;3.直接使用Unicode值来表示字符型常量        char c5='\n';//换行符        c5='\t';//制表符        System.out.println("hello"+c5);        System.out.println("world");         char c6= '\u0123';        System.out.println(c6);        char c7 = '\u0043';        System.out.println(c7);    }}布尔类型: Boolean Boolean 类型用来判断逻辑条件,一般用于程序流程控制:if 条件控制语句while 循环控制语句do-while 循环控制语句for 循环控制语句boolean类型数据只允许取值true 和 false ,这点和C语言 不同。Java虚拟机中没有任何供Boolean值专用的字节码指令,Java语言表达所操作的Boolean 值,在编译之后都使用Java虚拟机中的int 类型数据类型代替:true 用1 表示,false 用0表示。代码示例:class VariableTest2 {    public static void main(String[] args) {//4. 布尔型:boolean//① 只能取两个值之一:true . false//② 常常在条件判断. 循环结构中使用        boolean bb1 = true;        System.out.println(bb1);         boolean isMarried=false;        if(isMarried){            System.out.println("禁止入内!");        }else {            System.out.println("可以参观!");        }    }}基本数据类型转换自动类型转换:容量小的类型自动转换为容量大的数据类型,数据类型按容量大小排序为:有多种类型的数据混合运算时,系统首先自动将所有数据转换成容量最大的那种数据类型,然后再 进行计算。byte、short、char之间不会相互转换,他们三者在计算时首先转换为int类型。boolean类型不能与其它数据类型运算。当把任何基本数据类型的值和字符串(String)进行连接运算时(+),基本数据类型的值将自动转化为 字符串(String)类型。  代码示例:class VariableTest3{    public static void main(String[] args) {        byte b1=2;        int i1=129;         int i2=b1+i1;        long l3=b1+i1;        System.out.println(i2);        System.out.println(l3);         float f = b1 + i1;        System.out.println(f);//***************特别的**************************        char c1 = 'a'; //字符’a‘对应的数字是97        int i3=10;        int i4 = c1 + i3;        System.out.println(i4);    }}字符串类型:StringString不是基本数据类型,属于引用数据类型使用方式与基本数据类型一致。例如:String str= “abcd”;一个字符串可以串接另一个字符串,也可以直接串接其它类型的数据。代码示例:String类型变量的使用1. String属于引用数据类型2. 声明String类型变量时,使用一对""3. String可以和8种基本数据类型变量做运算,且运算只能是连接运算;+4. 运算的结果依然是String类型class  StringTest{    public static void main(String[] args) {        String s1="hello";        System.out.println(s1);        String s2 = "a";        String s3 = "";// char c = ''; //编译不通过//*******************************        int number = 1001;        String numberStr = "学号:";        String info = numberStr + number; //连接运算        boolean b1 = true;        String info1 = info + true;        System.out.println(info1);    }}练习:String str1 = 4; //判断对错:noString str2 = 3.5f + “”; //判断str2对错:yesSystem.out.println(str2); //输出:”3.5”System.out.println(3+4+“Hello!”); //输出:7Hello!System.out.println(“Hello!”+3+4); //输出:Hello!34System.out.println(‘a’+1+“Hello!”); //输出:98Hello!System.out.println(“Hello”+‘a’+1); //输出:Helloa1强制类型转换自动类型转换的逆过程,将容量大的数据类型转换为容量小的数据类型。使用时要加上强制转换 符:(),但可能造成精度降低或溢出,格外要注意。通常,字符串不能直接转换为基本类型,但通过基本类型对应的包装类则可以实现把字符串转换成 基本类型。如:String a = “43”; inti= Integer.parseInt(a);boolean 类型不可以转换为其它的数据类型。练习:判断是否能通过编译short s = 5;s = s-2; //判断:nobyte b = 3;b = b + 4;//判断:nob = (byte)(b+4);//判断:yeschar c = ‘a’;int i = 5;float d = .314F;double result = c+i+d; //判断:yesbyte b = 5;short s = 3;short t = s + b;//判断:no————————————————版权声明:本文为CSDN博主「Serendipity的人」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/m0_57448314/article/details/126239827
  • [技术干货] 【数据结构】栈和队列面试题总结(持续更新中...)-转载
    一、栈相关基础概念① 先进先入。不是所有进完才可以出,入的同时也可以出。②用数组实现栈:入栈和出栈的时间复杂度是O(1)③用单链表实现栈:头插法: 入栈和出栈 O(1)尾插法:入栈和出栈 O(n)所以用单链表实现栈时一定要头入头出。④方法  push、peek、pop、size、empty二、队列相关基础概念① 队尾进,队头出。底层是个双向链表。②Queue是个接口,在实例化时必须实例化LinkedList的对象。        Queue<Integer> q = new LinkedList<>();③用单链表实现队列  ok④ 用数组实现队列 。必须使用循环数组。后面3.6有代码实现逻辑。④方法  offer、poll、peek、size、isEmpty三、OJ题3.1 不可能的出栈顺序核心:入的时候同时可以出3.2 中缀表达式中缀转后缀:按照自己的理解,从左往右加括号,先乘除后加减。再逐步将运算符移到括号后,移                        掉所有的(),就是rug计算中缀表达式的值:遇见数字入栈,遇到运算符就从栈出两个元素。先出的放在运算符的后面,后出栈的放在运算符前面。将计算结果再入栈。3.3 括号匹配 OJ链接:20. 有效的括号 - 力扣(LeetCode)实现代码:class Solution {    public boolean isValid(String s) {        Stack<Character> stack = new Stack<>();        for(int i = 0 ;i<s.length();i++){            char ch = s.charAt(i);            // 遇见左括号就入栈,注意是单引号            if(ch == '[' || ch == '{' || ch == '('){                stack.push(ch);            }else{                // 否则,就与栈顶元素进行比较                // 如果栈是空的,并且遇见的是右括号,直接返回false                // 判断栈空 不能使用stack==null                if(stack.isEmpty()){                    return false;                }else{                    char peek = stack.pop();                    if( (peek == '[' && ch == ']') || (peek == '{' && ch == '}') || (peek == '(' && ch ==')')){                        continue;                    }else{                        return false;                    }                }            }        }        if(stack.isEmpty()){            return true;        }else{            return false;        }    }}3.4 逆波兰表达式求值 OJ链接:150. 逆波兰表达式求值 - 力扣(LeetCode)实现代码:class Solution {     public int evalRPN(String[] tokens) {        Stack<Integer> stack = new Stack<>();        HashSet<String> set = new HashSet<>();        set.add("+");        set.add("-");        set.add("*");        set.add("/");        for(String str:tokens){            // 如果遇见的是不是运算符,是数字,就入栈            if(!set.contains(str)){                stack.push(Integer.parseInt(str));            }else{                // 遇见运算符,就弹出两个数字                int back = stack.pop();                int front = stack.pop();                HashMap<String,Integer> hashMap = new HashMap<>();                hashMap.put("+",front+back);                hashMap.put("-",front-back);                hashMap.put("*",front*back);                //  注意:back有可能为 0                 if(back != 0){                    hashMap.put("/",front/back);                }//计算结果,将结果入栈                int result = hashMap.get(str);                stack.push(result);            }        }        return stack.peek();    }}3.5 出栈入栈次序匹配 OJ链接:栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com) 解题思路:要点1:定义一个pos,记录popA数组中元素的位置。要点2:遍历pushA,依次将pushA中的元素入栈,判断栈顶元素和popA中的元素是否相同,相同就出栈,并观察popA中的下一个元素是否和新栈顶元素相等。如果不相等,入栈pushA的下一个元素实现代码:import java.util.*;import java.util.ArrayList; public class Solution {    public boolean IsPopOrder(int [] pushA,int [] popA) {        Stack<Integer> stack1 = new Stack();        int pos = 0;        for(int i=0;i<pushA.length;i++){            stack1.push(pushA[i]);            while(!stack1.isEmpty() && stack1.peek() == popA[pos]){                stack1.pop();                pos++;            }        }        if(stack1.empty()){            return true;        }        return false;    }}3.6 循环队列 OJ链接:622. 设计循环队列 - 力扣(LeetCode)​ 解题思路:要点1:为了区分队列空和满,约定:        rear指向数组最后一个元素的下一个位置,下一次添加数据,可以直接往rear位置上放        front == rear 队列空        rear的下一个元素是front,队列满了。(rear+1)%elem.length要点2:返回队列顶部元素,返回front所在位置元素,front向前移。为了保证front可以从3移到1,front=(front+1)%elem.length要点3:返回队列最后一个元素。如果rear=0,返回elem[elem.length-1].如果rear不为0,就返回elem[rear-1]实现代码:class MyCircularQueue {     private int[] elem;    private int front;    private int rear;     public MyCircularQueue(int k) {        elem = new int[k+1];    }        public boolean enQueue(int value) {        if(isFull()){            return false;        }        if(isEmpty()){            elem[0] = value;            front = 0;            rear = 1;            return true;        }        elem[rear] = value;        rear = (rear+1) % elem.length;        return true;    }        public boolean deQueue() {        if(isEmpty()){            return false;        }        front = (front+1) % elem.length;        return true;    }        public int Front() {        if(isEmpty()){            return -1;        }        return elem[front];     }        public int Rear() {        if(isEmpty()){            return -1;        }        if(rear == 0){            return elem[elem.length-1];        }        return elem[rear-1];     }        public boolean isEmpty() {        return rear == front;     }        public boolean isFull() {        if((rear+1)%elem.length == front){            return true;        }        return false;     }}3.7 用队列实现栈 OJ链接:225. 用队列实现栈 - 力扣(LeetCode)解题思路:要点1:有两个队列要点2:第一次放push数据时,默认放到队列1中要点3:添加元素时,添加到不为空的队列中,这样才能保证顺序要点4:出栈—》获得栈顶元素—》栈后入先出—》弹出最后一个入栈的元素因此,需要找出最后一个入队列的元素。将队列的前n-1个元素,放到另外一个队列中,剩下的就是最后一个入队列的元素实现代码:class MyStack {     private Queue<Integer> qu1;    private Queue<Integer> qu2;     public MyStack() {        qu1 = new LinkedList<>();        qu2 = new LinkedList<>();    }        public void push(int x) {        // 如果队列2是空的,就往队列1里面放。原因:只有放在不为空的队列中顺序才不会乱        if(qu2.isEmpty()){            qu1.offer(x);        }else{            qu2.offer(x);        }            }        public int pop() {        if(empty()){            return -1;        }        if(qu1.isEmpty()){            // 队列2不为空,队列先进先出,将队列前size-1个元素放到队列1中,剩下的最后一个元素就是最后入队列的,也就是栈的第一个元素,将其返回            int size = qu2.size();            while(size > 1){                qu1.offer(qu2.poll());                size--;            }            int result = qu2.poll();            return result;        }        if(qu2.isEmpty()){            int size = qu1.size();            while(size > 1){                qu2.offer(qu1.poll());                size--;            }            int result = qu1.poll();            return result;        }        return -1;    }    public int top() {        if(empty()){            return -1;        }        if(qu1.isEmpty()){            int size = qu2.size();            while(size > 1){                qu1.offer(qu2.poll());                size--;            }            int result = qu2.poll();            qu1.offer(result);            return result;        }        if(qu2.isEmpty()){            int size = qu1.size();            while(size > 1){                qu2.offer(qu1.poll());                size--;            }            int result = qu1.poll();            qu2.offer(result);            return result;        }        return -1;     }        public boolean empty() {        return qu1.isEmpty()&&qu2.isEmpty();    }}3.8 用栈实现队列 OJ链接:232. 用栈实现队列 - 力扣(LeetCode)​ 解题思路:要点1:有两个栈。存数据都存到栈1中,取数据都从栈2中取。要点2:取数据时,如果栈2是空的,就把栈1中的元素全放到栈2中。再从栈2中取。实现代码:class MyQueue {    private Stack<Integer> stack1;    private Stack<Integer> stack2;    public MyQueue() {        stack1 = new Stack();        stack2 = new Stack();    }        public void push(int x) {        stack1.push(x);    }        public int pop() {        if(empty()){            return -1;        }        if(stack2.empty()){            while(!stack1.empty()){                stack2.push(stack1.pop());            }        }        return stack2.pop();    }        public int peek() {        if(empty()){            return -1;        }        if(stack2.empty()){            while(!stack1.empty()){                stack2.push(stack1.pop());            }        }        return stack2.peek();     }        public boolean empty() {        return stack1.empty()&&stack2.empty();     }}3.9 最小栈 OJ链接:155. 最小栈 - 力扣(LeetCode) 解题思路:要点1:创建两个栈。一个栈存放所有的元素,另外一个栈存放栈中最小的元素要点2:第一次push数据,数据存放在两个栈中要点3:之后存放数据,该数据小于等于最小栈的栈顶元素,才能存放到最小栈和stack中。否则,就只能存放到stack中实现代码:class MinStack {    public Stack<Integer> stack;    public Stack<Integer> minStack;     public MinStack() {        stack = new Stack();        minStack = new Stack();    }        public void push(int val) {        // 如果第一次放元素,往stack和minStack里都放        if(stack.empty() && minStack.empty()){            stack.push(val);            minStack.push(val);            return;        }        // 如果存放的数据比minStack元素小,该元素同时放到两个栈中        if(val <= minStack.peek()){            stack.push(val);            minStack.push(val);            return;        }else{            // 否则,就只往stack中放            stack.push(val);            return;        }    }        public void pop() {        int peek = stack.pop();        if(peek == minStack.peek()){            minStack.pop();        }    }        public int top() {        if(stack.empty()){            return -1;        }        return stack.peek();     }        public int getMin() {        if(minStack.empty()){            return -1;        }        return minStack.peek();     }}————————————————版权声明:本文为CSDN博主「刘减减」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/weixin_44258092/article/details/126240946
  • [技术干货] TopK问题求解方法-转载
    opK问题输入数组arr,找出其中最大的k个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最大的4个数字是5、6、7、8。示例一: 输入:arr = [3,2,1], k = 2 输出:[3,2]或者[2,3]示例二: 输入:arr = [0,1,2,1], k = 1 输出:[2]解决方法1:先将这个数组排成降序,输出前K个数字即可!注意1.如果排升序,就建立大根堆2.如果排降序,接建立小根堆//交换函数void Swap(int* x, int* y){    int tmp = *x;    *x = *y;    *y = tmp;}//堆的向下调整(小堆)void AdjustDown(int* a, int n, int parent){    //child记录左右孩子中值较小的孩子的下标    int child = 2 * parent + 1;//先默认其左孩子的值较小    while (child < n)    {        if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小        {            child++;//较小的孩子改为右孩子        }        if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小        {            //将父结点与较小的子结点交换            Swap(&a[child], &a[parent]);            //继续向下进行调整            parent = child;            child = 2 * parent + 1;        }        else//已成堆        {            break;        }    }}int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){    *returnSize = k;    int i = 0;    //建小堆    for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)    {        AdjustDown(arr, arrSize, i);    }    //排降序    int end = arrSize - 1;    while (end > 0)    {        Swap(&arr[0], &arr[end]);        AdjustDown(arr, end, 0);        end--;    }    //将最大的k个数存入数组    int* retArr = (int*)malloc(sizeof(int)*k);    for (i = 0; i < k; i++)    {        retArr[i] = arr[i];    }    return retArr;//返回最大的k个数}时间复杂度: O(N+NlogN) 空间复杂度:O(N)解决方法2:将数组建成一个大堆,取K次堆顶的数据就可以了。细节:每次拿走堆顶的数据后,需要将堆顶的数据和最后一个数据进行交换,然后重新建堆!//交换函数void Swap(int* x, int* y){    int tmp = *x;    *x = *y;    *y = tmp;}//堆的向下调整(大堆)void AdjustDown(int* a, int n, int parent){    //child记录左右孩子中值较大的孩子的下标    int child = 2 * parent + 1;//先默认其左孩子的值较大    while (child < n)    {        if (child + 1 < n&&a[child + 1] > a[child])//右孩子存在并且右孩子比左孩子还大        {            child++;//较大的孩子改为右孩子        }        if (a[child] > a[parent])//左右孩子中较大孩子的值比父结点还大        {            //将父结点与较大的子结点交换            Swap(&a[child], &a[parent]);            //继续向下进行调整            parent = child;            child = 2 * parent + 1;        }        else//已成堆        {            break;        }    }}int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){    *returnSize = k;    int i = 0;    //建大堆    for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)    {        AdjustDown(arr, arrSize, i);    }    //将最大的k个数存入数组    int* retArr = (int*)malloc(sizeof(int)*k);    int end = arrSize - 1;    for (i = 0; i < k; i++)    {        retArr[i] = arr[0];//取堆顶数据        Swap(&arr[0], &arr[end]);//交换堆顶数据与最后一个数据        //进行一次向下调整,不把最后一个数据看作待调整的数据,所以待调整数据为end=arrSize-1        AdjustDown(arr, end, 0);        end--;//最后一个数据的下标改变    }    return retArr;//返回最大的k个数}时间复杂度: O(N+klogN) 空间复杂度:O(N)弊端:如果待待续的数字有100亿个,那么存储100亿个整数究竟需要多大的内存空间?让咱们来大概估算一下: 我们知道1KB=1024byte,1MB=1024KB,1GB=1024MB,于是可以得出1GB大概有230个字节,也就是说1GB大概等于10亿个字节。 存储100亿个整型需要400亿个字节,所以存储100亿个整型数据需要40G左右的内存空间。前面两种算法的空间复杂度均为O(N),并不适合用于这种海量数据处理。基于上述问题,我们重新建立一种新的解决方法!解决方法3:1.先将前K个数据建立小堆 2.将数组剩下的N-K个数字依次和堆顶的数据比较,如果大于堆顶的数据,进行替换,然后向下调整,使其仍为小堆。//交换函数void Swap(int* x, int* y){    int tmp = *x;    *x = *y;    *y = tmp;}//堆的向下调整(小堆)void AdjustDown(int* a, int n, int parent){    //child记录左右孩子中值较小的孩子的下标    int child = 2 * parent + 1;//先默认其左孩子的值较小    while (child < n)    {        if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小        {            child++;//较小的孩子改为右孩子        }        if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小        {            //将父结点与较小的子结点交换            Swap(&a[child], &a[parent]);            //继续向下进行调整            parent = child;            child = 2 * parent + 1;        }        else//已成堆        {            break;        }    }}int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){    *returnSize = k;    if (k == 0)        return NULL;    //用数组的前K个数建小堆    int i = 0;    int* retArr = (int*)malloc(sizeof(int)*k);    for (i = 0; i < k; i++)    {        retArr[i] = arr[i];    }    for (i = (k - 1 - 1) / 2; i >= 0; i--)    {        AdjustDown(retArr, k, i);    }    //剩下的N-k个数依次与堆顶数据比较    for (i = k; i < arrSize; i++)    {        if (arr[i]>retArr[0])        {            retArr[0] = arr[i];//堆顶数据替换        }        AdjustDown(retArr, k, 0);//进行一次向下调整    }    return retArr;//返回最大的k个数}————————————————版权声明:本文为CSDN博主「XG_JieJie」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/jiejiezuishuai/article/details/126245957
  • [技术干货] Arrays类-转载
    Arrays类Arrays类是Java中用来操作数组的模块他的使用方法是在Java类中使用import java.util.Arrays进行导入,并使用Arrays.方法()进行调用方法!Arrays类的fill方法fill方法有两种用途!第一种就是填充数组,将数组中的全部元素转换为所输入的元素第二种就是替换数组元素,将数组中某个元素进行单个替换用fill方法填充数组在初始化一个数组之后,如果没有给数组的元素赋值,那么这个数组中的元素默认是为0的,那么我们一个个进行赋值又会略显麻烦,会堆积代码!所以我们就需要用到fill方法进行填充,但是这么做会让全部元素变成同一个数值!import java.util.Arrays; //这里导入Arrays类public class Fill{public static void main(String[] args){int[] mylist = new int[5]; //这里创建一个名称为mylist的数组,数组的元素个个数为5Arrays.fill(mylist,3); //为数组填充3,格式为fill(列表,数值)for(int x:mylist){System.out.println(x);} //通过for each来遍历数组元素}}上面的for each在以前的文章中介绍过!用fill方法替换数组元素在给元素赋值完或者是填充完元素之后,如果想对某个元素进行修改,那么我们就要重新赋值或者是替换元素,但是重新赋值会增加代码,让代码显得更繁琐,所以Arrays类中提供了替换元素的方法fill!import java.util.Arrays;public class Fill{public static void main(String[] args){int[] mylist = {1,2,3,4};Arrays.fill(mylist, 1,2,4);for(int x:mylist){System.out.println(x);}} //这是一个特殊的格式Arrays.fill(列表名称,空格正向索引,反向索引,改变的数值)1}这里的正反向索引指向的一定要是同一个元素!Arrays类的复制数组方法在Java程序的使用过程中,有时候会需要一个含有相同或者是部分相同元素的数组,但是重新创建数组的话就会增加代码长度,减少代码可读性,那么我们就可以使用到复制数组或者是部分数组的方法!用copyOf复制数组☄️copyOf方法提供了多种重载的方法,用以复制数组,增加代码可读性。该方法不受数组长度的限制,若超出,则多处部分为0!import java.util.Arrays;public class Fill{public static void main(String[] args){int[] mylist = {1,2,3,4};int[] justlist = Arrays.copyOf(mylist,4); //将复制后的数组赋值给justlist//格式Arrays.copyOf(列表,复制后的长度)for(int x:justlist){System.out.println(x);}System.out.println(mylist);System.out.println(justlist); //这里输出两个数组的内存空间进行检查} //这是一个特殊的格式Arrays.fill(列表名称,空格正向索引,反向索引,改变的数值)1}解:从以上结果可以看出赋值成功了,并且内存空间不同(下面我会解释为什么要输出内存空间)用copyOfRange方法复制部分数组有时候在编辑代码的时候只需要中间一部分代码,但是copyOf方法只能复制以前面部分为开头的元素,而不能直接复制中间的代码,为了解决这一个问题,这个类提供了另一个方法copyOfRange方法(中文意思:选择复制)利用这个方法就可以解决这一个问题!import java.util.Arrays;public class Fill{public static void main(String[] args){int[] mylist = {1,2,3,4};int[] justlist = Arrays.copyOfRange(mylist,1,3);//Arrays类的方法使用形式Arrays.copyOfRange(列表,第一个索引位置,第二个索引位置)for(int x:justlist){System.out.println(x);}}}注:在末尾有问题解答!Arrays类对数组进行排序在代码编译过程中,有时候会需要用到有序的一组数组才能进行更好的操作,但是我们重新进行编译会增加代码数量,所以我们要对代码进行排序,Java中提供了sort方法对数组的元素进行升序排序!用sort方法进行升序排序在Java编译过程中,有顺序的数组会让你的编译更加方便,使得你自己以及其他参与编译的人更加清楚,尤其是适合那些大基数的数组更为适用和实用!import java.util.Arrays;public class Fill{public static void main(String[] args){    int[] mylist = {1,7,33,4};    Arrays.sort(mylist);    //方式为Arrays.sort(列表)    for(int x:mylist){        System.out.println(x);    }}}问题解答为什么要在fill方法中加空格:因为不加空格就会使他执行不正确,无法达到效果为什么要输出内存空间吗:如果在同一个内存空间,一个数组改变之后另一个也会随之改变,会影响后续程序执行copyOfRange方法如果超出索引最大限度会怎么样:如果超出,则超出部分默认为0!为什么有些要方法要创建新数组有些不用:因为有些方法是对一个数组进行改变,有些是要重新创建数组!————————————————版权声明:本文为CSDN博主「Code Writers」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/m0_71905144/article/details/126250825
  • [技术干货] 数据结构 桶排序 基数排序-转载
    首先来了解桶排序将数组分成若干类  分这个类的条件  我们自己决定这里我们用的是 每隔5个数分为一类如20~24  25~29 30~34...数组中的元素满足这样的条件就会被放在相应的桶中如: 23会被放在20~24的桶中假设我们有这样一个数组int arr[15] = { 34,36,31,78,65,32,33,34,89,90,91,67,52,71,77};我们决定桶的数量 为确保数组中的元素都能如桶   一般设定为  :原数组中的最大值-最小值+1 想判断当前数组元素应该入哪个桶  我们这里的条件是:当前元素的值-最小值/5   为他要入的桶的下标如  最小元素20 当前元素40  那么他要进去的桶的下标为 (40-20)/5=4我们这里所谓的桶  其实就是一个哈希数组 这里用的是链式存储法 (每一个元素都是一个链表的头)如相应的桶  就是 把元素添加到哈希数组的相应下标上的链表上去  在这里我们添加用的是链表插入的方式  直接根据节点的值将节点插入到相应的位置   完成排序 之后我们只需要 遍历哈希数组并遍历哈希数组元素  吧 哈希数组中的元素都放回到原数组中去这样就实现了桶排序桶排序完整代码如下#include<iostream>using namespace std;#define  jiange 5struct List{    int id;    List* pNext;}; void Insert(List*&pHead,int value){    List* pTemp=new List;    pTemp->id = value;    pTemp->pNext = NULL;    //链表中没有节点    if (pHead == NULL)    {        pHead = pTemp;        return;    }    //链表中的头节点比当前节点的值大      //头插入    if (pTemp->id < pHead->id)    {        pTemp->pNext=pHead;        pHead = pTemp;        return;    }    //链表的头的值比当前要插入的节点的值小    //遍历链表  找到要插在谁的后面            List* pMark = pHead;        while (pMark->pNext != NULL)        {            if (pMark->pNext->id > pTemp->id)            {                pTemp->pNext = pMark->pNext;                pMark->pNext = pTemp;                return;            }            pMark = pMark->pNext;        }        //遍历到最后一个节点  都没找到比当前节点大的节点  插在最后        pMark->pNext = pTemp;         }void BuckeSort(int arr[],int nLen){    int begin = arr[0];    int end =arr[0];    //参数校验    if (arr == NULL || nLen <= 10)    {        return;    }    //找到最大值和最小值确定桶的数量    for (int i = 0; i < nLen; i++)    {        if (arr[i] < begin)            begin = arr[i];        if (arr[i] > end)            end = arr[i];    }    int nBucketCount =  end -begin + 1;    //开辟空间    List** Hash = new List*[nBucketCount];    ::memset(Hash, 0, sizeof(List*)* nBucketCount);    //遍历数组入桶    for (int i = 0; i < nLen; i++)    {        //入桶函数        Insert(Hash[(arr[i]-begin)/jiange], arr[i]);    }    //出桶     int j = 0;    for (int i = 0; i < nBucketCount; i++)    {                while (Hash[i])        {            List* pDel = Hash[i];            Hash[i] = Hash[i]->pNext;             arr[j++] =pDel->id;            delete pDel;            pDel = NULL;                                }    }    delete Hash;    Hash = NULL;       } int main(){    int arr[15] = { 34,36,31,78,65,32,33,34,89,90,91,67,52,71,77};    BuckeSort(arr, 15);    for (int val : arr)    {        cout << val << " ";    }    return 0;}基数排序:可以看做是桶排序的另一种优化  只不过 他的如桶条件变了 而且需要额外创建一个记录链表的尾的哈希数组;  用于添加节点尾入  头出思想:先把数组中的元素根据个位入桶出桶放入原数组在把数组中的元素根据十位入桶出桶放入原数组...直到把数组中的元素根据  数组中的最大的元素的最高位  入桶出桶放入原数组   结束这样一来  数组自己就排序好了基数排序:代码如下#include<iostream>using namespace std;#define  jiange 5struct List{    int id;    List* pNext;}; void AddNode(List*& pHead, List*& pEnd ,int value){    List* pTemp = new List;    pTemp->id = value;    pTemp->pNext = NULL;    //链表中没有节点    if (pHead == NULL)    {        pHead = pTemp;            }    //链表有节点      //尾插入    else     {        pEnd->pNext = pTemp;     }                  pEnd = pTemp;      }void RadixSort(int arr[], int nLen){        //参数校验    if (arr == NULL || nLen <= 10)    {        return;    }    //找到最大值    int max = arr[0];    for (int i = 0; i < nLen; i++)    {        if (arr[i] > max)        {            max = arr[i];        }    }    int base = 1;        //创建桶中链表的头节点数组    List** pHeadarr = new List * [10];    //创建桶中链表的尾节点数组    List** pEndarr = new List * [10];    ::memset(pHeadarr, 0, sizeof(List*) * 10);    ::memset(pEndarr, 0, sizeof(List*) * 10);    while (max / base != 0)    {        //arr的元素放入桶中        for (int i = 0; i < nLen; i++)        {                        //链表尾部添加            AddNode(pHeadarr[arr[i] / base % 10], pEndarr[arr[i] / base % 10], arr[i]);        }        //出桶        int j = 0;        for (int i = 0; i < 10; i++)        {            while (pHeadarr[i])            {                List* pDel = pHeadarr[i];                                pHeadarr[i] = pHeadarr[i]->pNext;                                    arr[j++] = pDel->id;                delete pDel;                pDel = NULL;            }        }        base *= 10;     }       } int main(){    int arr[15] = { 34,36,31,78,65,32,33,34,89,90,91,67,52,71,77 };    RadixSort(arr, 15);    for (int val : arr)    {        cout << val << " ";    }    return 0;————————————————版权声明:本文为CSDN博主「van9527」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/van9527/article/details/126232966
  • [技术干货] 数据结构基础==数据结构与算法2-转载
    1、数据处理的基本操作:增、删、查其中,增和删又可细分为在数据结构中间的增和删,以及在数据结构最后进行增和删,区别在于原始数据的位置是否发生改变。查找又可分为按照位置条件的查找和按照数值特征的查找。2、线性表结构的增删查(1)线性表是 n 个数据的有限序列,最常用的是线性链表,即链表。(2)链表有单向链表、循环链表、双向链表、双向循环链表。(3)链表新增、删除操作都比较容易,可以在 O(1)的时间复杂度内完成。但查找操作需要 O(n)的时间复杂度,不管是按照位置条件还是数值条件的查找。然而,链表的新增、 删除操作通常都伴随着查找操作。(4)当数据的元素个数不确定,且需要经常进行数据的新增和删除时,那么链表会比较合 适。(5)线性表案例:①单向链表的翻转:双指针。②给定一个奇数个元素的链表,查找出这个链表中间位置的结点的数值:暴力方法、快慢指 针方法。③判断链表是否有环:快慢指针方法。3、栈(先进后出的线性表)如何实现增、删、查?(1)栈是个限制版的线性表,限制的功能是,只允许数据从栈顶进出。不管是顺序栈(依赖数组)还是链式栈(依赖链表),对于数据的新增操作和删除操作的时间复杂度都是 O(1),而对于查找操作则需要 O(n)的时间复杂度。(2)栈具有后进先出的特性,当面对的问题需要高频使用新增、删除操作,且新增和删除 操作的数据执行顺序具备后来居上的相反顺序时,栈就是个不错的选择。例如:浏览器页面的前进和后退、括号匹配等问题。4、队列(先进先出的线性表)如何实现增删查?(1)队列也是一种加了限制的线性表,它值允许从队尾插入数据,从队头删除数据,通常 有顺序队列(数组方式)和链式队列(链表方式)。队列通常用 front 指针指向队头, 用 rear 指针指向队尾。(2)顺序队列有普通队列和循环队列,循环队列可以防止出现“假溢出”问题。(3)链式队列的头结点不存放数据,是为了避免当队列为空时 front 和 rear 成为野指针。4)在时间复杂度上,循环队列和链式队列的新增、删除操作都为 O(1),查找操作为 O(n)。 在空间性能方面,循环队列必须有一个固定的长度,因此存储的元素数量有限制且有时会造成空间浪费,而链式队列则更为灵活一些。(5)约瑟夫环可以用循环队列来解决。5.数组:如何实现基于索引的查找?(1)链表、栈、队列都是线性表,而数组可以看成线性表的一种推广,属于另外一种数据 结构。(2)数组增删查操作的特点:①增加:若插入数据在最后,则时间复杂度为 O(1);若不是, 则时间复杂度为 O(n)。②删除:对应位置的删除,时间复杂度为 O(n)。③查找:如果 只根据索引值进行查找,则时间复杂度为 O(1);若根据数值条件进行查找,则时间复 杂度为 O(n)。 (3)数组需要在定义时(3)数组需要在定义时就确定长度,且在内存中是按顺序存储的;而链表的长度灵活可变, 且在内存中随机存储。(4)数组更适合在数据量确定,且较少需要进行数据的增加、删除操作的场景下使用。同 时也更适合在数据对位置敏感的场景下使用。链表对数据的增加、删除操作的时间复 杂度更低。6.字符串匹配(1)字符串是由 n 个字符组成的有序整体,字符串的存储结构与线性表相同,也有顺序存储和链式存储两种。(2)字符串增删查的特点:①增加:和数组非常相似,正常情况下时间复杂度为 O(n),若在最后插入(也叫连接),则为 O(1)。②删除:同样是 O(n)和 O(1)。③查找(字符串匹配),若主串的长度为 n,模式串的长度为 m,则时间复杂度为 O(nm)。(3)案例:字符串翻转,给定一个字符串,逐个翻转字符串中每个单词,例如,输入“the sky is blue”,输出“blue is sky the”。#include <stdio.h>#include <string.h>#include <stdlib.h>void str_reverse(char *str,char* rev){    int len=strlen(str),i,j,left=0,index;    for(i=0;i<=len;i++){        if(str[i]==''||str[i]=='\0'){            index=len-i;            for(j=left;j<i;j++){                rev[index]=str[j];                index++;//直接越位            }            if(left==0)                rev[index]='\0';            else                rev[insex]='';            left=i+1;//左端设置        }    }}void main(){    char str[]="the sky si blue";    char* rev=(char*)malloc(strlen(str)+1);    str_reverse(str,rev);    printf("The outis:%s\n", rev);}12345678910111213141516171819202122232425262728297.树和二叉树:分支关系与层次结构下,如何有效实现增删查?(1)树是由结点和边组成的,不存在环的一种数据结构。(2)相关概念:根结点、父结点、子结点、兄弟结点、叶子结点、深度、层。(3)二叉树:每个结点最多有两个分支,其中有两个特殊类型:①满二叉树。②完全二叉树:除了最后一层外,其他层的结点个数都达到最大,并且最后一层的叶 子结点都靠左排列。(4)二叉树有两种存储方法:链式存储法顺序存储法(下标为 i 的左子结点为 2i,右子 结点为 2i+1)(5)二叉树的基本操作:①遍历:前序遍历、中序遍历、后序遍历。时间复杂地为 O(n)。②增加和删除:时间复杂度位 O(1)==类似链表(6)二叉查找(搜索)树(BST)①任意一个结点的的左子树的每个结点的值都小于该结点的值,右子树的每个结点的 值都大于该结点的值。对二叉查找树进行中序遍历,即可输出一个从小到大的有序数据队列。②二叉查找树的查找操作、插入操作(包含查找位置)的时间复杂度为 O(logn)。③删除操作比较复杂:a.要删除某个叶子结点,则直接删除,将其父结点指针指向 NULL。b.要删除的结点只有一个子结点,则将其父结点指针指向其子结点的指针。c.要删除的结点有两个子结点,第一种方法是找到这个结点的左子树中的最大结点来替换该结点;第二种方法是找到这个结点的右子树中的最小 结点来替换该结点。(7)Trie 树/字典树:根结点不包含字符、其他结点都只包含一个字符;从根结点到某一叶子结点,路径上经过的字符连接起来,即为集合中的某个字符串。8.哈希表:高效率查找的利器(1)哈希表也叫散列表,是一种特殊的数据结构,其核心思想是:如果有一种方法,可以实现”地址” = f(关键字)的映射关系,那么就可以快速完成基于数据的数值查找了。但 哈希表不可避免地会产生哈希冲突,即不同的关键字得到相同的地址。(2)常用的设计哈希函数的方法:①直接定制法:哈希函数为关键字到地址的线性函数,如 H(key) = a * key + b。②数字分析法:假设关键字集合中的每个关键字 key 都是由 s 位数字组成的,从中提 取分布均匀的若干为组成哈希地址。③平方取中法:如果关键字的每一位都有重复的数字出现,并且频率很高,就可以先求关键字的平方值,扩大差异,然后取中间几位作为存储地址。④折叠法:如果关键字的位数很多,可以将关键字分割为几个等长的部分,取它们的 叠加和的值(舍去进位)作为哈希地址。⑤除留余数法:预先设置一个数 p,然后对关键字进行取余运算,即地址 为 key mod p。(3)常用解决哈希冲突的方法:①开放定址法:当一个关键字和另一个关键字产生冲突时,使用某种探测技术在哈希表中形成一个探测序列,然后沿着这个探测序列一次查找下去,当碰到空的单元时则插入其中。常用的探测方法是线性探测法。②链地址法:将哈希地址相同的记录存储在一张线性链表中。(拉链法)(4)哈希表可以提供非常快速的插入、删除、查找,无论多少数据,插入和删除只需要接 近常量的时间,查找的速度比树还快。但哈希表中的数据没有顺序的概念,同时 key 是不允许重复的。(5)在很多高级语言中,哈希函数、哈希冲突都已完成了黑盒化处理,是不需要开发者自 己设计的。————————————————版权声明:本文为CSDN博主「栋哥修炼日记」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/weixin_47397155/article/details/126233587
  • [技术干货] 多线程进阶:常见数据结构的安全性分析-转载
    一、常见数据结构非线程安全的数据结构:ArrayList,LinkedList,ArrayQueue,HashMap,HashSet线程安全的数据结构:Vector,Stack,Hashtable,CopyOnWriteArrayList,ConcurrentHashMap二、ArrayList2-1 线程不安全的原因看源码public boolean add(E e) {    ensureCapacityInternal(size + 1);  // Increments modCount!!    // 该方法是容量保障,当容纳不下新增的元素时会进行扩容    elementData[size++] = e;    return true;}分析:当数组长度为10,而size = 9时,此时A线程判断可以容纳,B线程也来判断发现可以容纳(这是因为add非原子操作)。当A添加完之后,B线程再添加的话,就会报错(数组越界异常)而且这一步elementData[size++] = e也非原子性的.可以拆分为elementData[size] = e 和 size ++;在多线程的情况下很容易出现elementData[size] = e1; elementData[size] = e2; size++; size++; 的情况2-2 Vector实现安全Vector的add()源码:    public synchronized void addElement(E obj) {        modCount++;        ensureCapacityHelper(elementCount + 1);        elementData[elementCount++] = obj;    }分析: Vector的add方法加了synchronized ,而ArrayList没有,所以ArrayList线程不安全,但是,由于Vector加了synchronized ,变成了串行,所以效率低。回到目录…三、CopyOnWriteArrayListCopyOnWrite容器即写时复制的容器。// java.util.concurrent包下List<String> list = new CopyOnWriteArrayList<String>();123-1 如何实现线程安全? 通俗的理解是当我们往一个容器添加元素的时候,不直接往当前容器添加,而是先将当前容器进行Copy,复制出一个新的容器,然后新的容器里添加元素,添加完元素之后,再将原容器的引用指向新的容器。 这样做的好处是我们可以对CopyOnWrite容器进行并发的读,而不需要加锁,因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想,读和写不同的容器。3-2 特征CopyOnWriteArrayList(写数组的拷贝)是ArrayList的一个线程安全的变体,CopyOnWriteArrayList和CopyOnWriteSet都是线程安全的集合,其中所有可变操作(add、set等等)都是通过对底层数组进行一次新的复制来实现的。它绝对不会抛出ConcurrentModificationException的异常。因为该列表(CopyOnWriteArrayList)在遍历时将不会被做任何的修改。CopyOnWriteArrayList适合用在“读多,写少”的并发场景中,比如缓存、白名单、黑名单。它不存在“扩容”的概念,每次写操作(add or remove)都要copy一个副本,在副本的基础上修改后改变array引用,所以称为“CopyOnWrite”,因此在写操作要加锁,并且对整个list的copy操作时相当耗时的,过多的写操作不推荐使用该存储结构。读的时候不需要加锁,如果读的时候有多个线程正在向CopyOnWriteArrayList添加数据,读还是会读到旧的数据,因为开始读的那一刻已经确定了读的对象是旧对象。3-3 缺点在写操作时,因为复制机制,会导致内存占用过大。不能保证实时性的数据一致,“脏读”。回到目录…四、HashMap4-1 底层原理不清楚的小白看看之前两篇文章,就可以很容易搞懂HashMap的底层实现原理了。 Java数据结构之哈希表 JDK中的Set和Map解析4-2 线程不安全的原因单看 HashMap 中的 put 操作:JDK1.7头插法 –> 将链表变成环 –> 死循环JDK1.8尾插法 –> 数据覆盖回到目录…五、ConcurrentHashMap// java.util.concurrent包下Map<Integer, String> map = new ConcurrentHashMap<>();125-1 实现原理JDK1.7时,采用分段锁JDK1.8时,只针对同一链表内互斥,不是同一链表内的操作就不需要互斥。但是一旦遇到需要扩容的时候,涉及到所有链表,此时就不是简单的互斥了。扩容的过程:当A线程put 操作时发现需要扩容,则它自己创建一个扩容后的新数组。A线程只把当前桶中的节点重新计算哈希值放入新数组中,并且标记该桶元素已经迁移完成。由于其它桶中的元素还没有迁移,所以暂时还不删除旧数组。等其它线程抢到锁并在桶内做完操作时,需要义务的将该桶节点全部搬移并标记桶。直到最后一个线程将最后一桶节点搬移完毕,则它需要把旧数组删除。5-2 与Hashtable的区别HashTable和HashMap的实现原理几乎一样,差别在于:HashTable不允许key和value为null;HashTable是线程安全的。 但是HashTable线程安全的策略实现代价却比较大,get/put所有相关操作都是synchronized的,这相当于给整个哈希表加了一把全表锁。当一个线程访问或操作该对象,那其他线程只能阻塞。 所以说,Hashtable 的效率低的离谱,几近废弃。————————————————版权声明:本文为CSDN博主「一只咸鱼。。」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/qq15035899256/article/details/125961682
  • [技术干货] 算法之从会用到理解 - 数组反转-转载
    前言OK,今天是一个简单的应用题材分析,算法的学习需要我们不断的去思考,今天的题目依然来自leecode。1.数组反转1.1 leecode题目-旋转数组给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。示例:输入: nums = [1,2,3,4,5,6,7], k = 3输出: [5,6,7,1,2,3,4]解释:向右轮转 1 步: [7,1,2,3,4,5,6]向右轮转 2 步: [6,7,1,2,3,4,5]向右轮转 3 步: [5,6,7,1,2,3,4]1.2 分析题目数组元素有序轮转,即轮转位置k,意味着,每个元素向后移k位,且长度n-k~n-1位置的元素会被挪移至最前方;k为非负整数,所以,不存在向左轮转;1.3解题思路在不使用额外数组的前提下,我们可以有如下思考,设数组长度为length,则需要轮转k位,即数组的最后k位会进行挪移至数组前方,即,当我们反转数组后,可以得知[0,k-1],[k,lenth-1]这两个数组,即为轮转之后的对应数组,但是,两个数组中的元素排序是反的;接下来,依次反转[0,k-1],[k,lenth-1],这两个数组,得到的数组就是答案了1.4 代码const reverseArray = (nums, start, end) => {  while (start < end) {    const temp = nums[start];    nums[start] = nums[end];    nums[end] = temp;    start += 1;    end -= 1;  }  return nums;};var reverseFunction = function(nums, k) {  let length  = nums.length;  nums = reverseArray(nums, 0, length - 1);  nums = reverseArray(nums, 0, k - 1);  nums = reverseArray(nums, k, length - 1);};reverseFunction([1,2,3,4,5,6,7],3);输出:[5,6,7,1,2,3,4]1.5 复杂度分析时间复杂度:时间复杂度:O(n),其中 nn 为数组的长度。每个元素被翻转两次,一共 n 个元素,因此总时间复杂度为 O(2n)=O(n)。空间复杂度:O(1)。只需要常数空间存放若干变量。1.6 其他解法思路:既然轮转k位,即[length-1-k,length-1]位置的元素变为[0,k-1][0,length-1-k]位置的元素变为[length-1-k,length-1]所以我们只需要将原数组拆分为[0,k-1],[length-1-k,length-1],然后将其按照[length-1-k,length-1]+[0,k-1]组装成一个数组即可代码var reverseFunction2 = function(nums, k) {  let length  = nums.length;  let arrayLeft = nums.slice(0,length-k);  let arrayRight = nums.slice(length-k);  // return [...new Set([...arrayRight,...arrayLeft])];  return arrayRight.concat(arrayLeft);};reverseFunction2([1,2,3,4,5,6,7],3);大家会发现上述代码中,我注释了一行,因为,绝对诱人会想使用new Set方法去合并两个数组,那么,请注意,千万不能使用,因为,new Set方法,会讲两个数组进行合并后去重,如果原数组中出现相同元素,则,new Set将会给使用者狠狠上一课!总结算法的逻辑不同的人有不同的想法,但是殊途同归,答案是一致的,前提是,一定要靠清楚问题,仔细分析,验证的时候也要考虑各种情况。寄语算法的验证,必要且一定,好的算法,少不了单元测试————————————————版权声明:本文为CSDN博主「乾复道」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/Long861774/article/details/126214914
  • [技术干货] 55跳跃游戏-转载
    题目给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。示例 1:输入:nums = [2,3,1,1,4]输出:true解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2:输入:nums = [3,2,1,0,4]输出:false解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。方法一:正向遍历,计算每个位置开始能到达的最高处class Solution {public:    bool canJump(vector& nums) {        int reach=0;//记录当前能到达的最远处        //i遍历数组,i要始终处于能到达的位置,如果reach已经大于nums边界已经可以退出循环        for(int i=0;i<=reach&&reach<nums.size();i++)        {            reach=max(reach,i+nums[i]);//当前位置的最远边界为当前位置能加最大步数和最远边界,二者取较大        }        return reach+1>=nums.size();//边界是数组下标,从0开始,所以要加1    }};时间复杂度O(n)空间复杂度O(1)思路对于数组中的任意一个位置y,只要当前位置x加上x处可走的最大步数,二者之和大于y,则可以到达y一次遍历数组,维护当前的最远边界最后比较最远边界是否可以到达数组大小,如果是则返回true法二:逆向遍历数组,从末尾看能不能下降到0class Solution {public:    bool canJump(vector& nums) {        int left=nums.size()-1;//左边界        //从后往前遍历数组,如果i所指的位置加上当前数组值大于lef,则当前的左边界为i        for(int i=nums.size()-2;i>=0;i--)        {            if(nums[i]+i>=left) left=i;        }        //最后判断左边界能否小于0,即从终点能否回到起点        return left<=0;    }};法三:动态规划class Solution {public:    bool canJump(vector& nums) {        vector f(nums.size(),0);        f[0]=nums[0]-1;//初始位置可以到达的最远距离就是0加上当前可以走的步数        //依次确定经过每一个位置的最远距离        for(int i=1;i<nums.size();i++)        {            f[i]=max(f[i-1],i+nums[i-1]);            if(f[i]==i) return false;//表示不能往后走了,返回false        }        return true;    }};时间复杂度O(n)空间复杂度O(n)思路f[i]表示当前位置可以到达的最远位置状态转移方程:f[i]=max(f[i-1],i+nums[i-1])当前位置可以到达的最远位置有两种情况,如果不到达当前位置则是前一个位置可以到达的最远位置即f[i-1],如果从当前位置出发则是i+nums[i],二者取最大值每次比较当前位置可以到达的最远位置是否与当前位置相同,如果相同则表示无法继续向后走,返回false如果for循环正常退出则表示可以走到末尾,返回true————————————————版权声明:本文为CSDN博主「Mirevas」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/weixin_45781228/article/details/126202831
  • [技术干货] 1105 链表合并 – PAT乙级真题-转载
    给定两个单链表 L1​=a1​→a2​→⋯→an−1​→an​ 和 L2​=b1​→b2​→⋯→bm−1​→bm​。如果 n≥2m,你的任务是将比较短的那个链表逆序,然后将之并入比较长的那个链表,得到一个形如 a1​→a2​→bm​→a3​→a4​→bm−1​⋯ 的结果。例如给定两个链表分别为 6→7 和 1→2→3→4→5,你应该输出 1→2→7→3→4→6→5。输入格式:输入首先在第一行中给出两个链表 L1​ 和 L2​ 的头结点的地址,以及正整数N (≤105),即给定的结点总数。一个结点的地址是一个 5 位数的非负整数,空地址 NULL 用 -1 表示。随后 N 行,每行按以下格式给出一个结点的信息:Address Data Next其中 Address 是结点的地址,Data 是不超过 105 的正整数,Next 是下一个结点的地址。题目保证没有空链表,并且较长的链表至少是较短链表的两倍长。输出格式:按顺序输出结果链表,每个结点占一行,格式与输入相同。输入样例:00100 01000 702233 2 3489100100 6 0000134891 3 1008601000 1 0223300033 5 -110086 4 0003300001 7 -1输出样例:01000 1 0223302233 2 0000100001 7 3489134891 3 1008610086 4 0010000100 6 0003300033 5 -1分析:用vector<int> L1、L2存储题目中给定的两个链表,vector<int> ans保存合并后的链表。将较长的一个链表存储在L1中,如果原本L1较短,则将L1与L2用swap函数互相置换~在链表合并的过程中,i从0开始,将L1中每个结点添加到ans中,如果当前i是奇数(i & 1不等于0)就把L2的一个结点添加到ans中,直到L2中没有剩余元素~如此反复,就大功告成啦。#include <iostream>#include <vector>using namespace std;struct node {    int data, next;}A[100000];vector<int> L1, L2, ans;int sa, sb, n, a, ta, tb, c;int main() {    cin >> sa >> sb >> n;    for (int i = 0; i < n; i++) {        cin >> a >> A[a].data >> A[a].next;    }    ta = sa;    while (ta != -1) {        L1.push_back(ta);        ta = A[ta].next;    }    tb = sb;    while (tb != -1) {        L2.push_back(tb);        tb = A[tb].next;    }    if (L1.size() < L2.size()) swap(L1, L2);    for (int i = 0, c = L2.size() - 1; i < L1.size(); i++) {        ans.push_back(L1[i]);        if (i & 1 && c >= 0) ans.push_back(L2[c--]);    }    for (int i = 1; i < ans.size(); i++) {        printf("%05d %d %05d\n", ans[i-1], A[ans[i-1]].data, ans[i]);    }    printf("%05d %d -1", ans.back(), A[ans.back()].data);    return 0;}————————————————版权声明:本文为CSDN博主「柳婼」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/liuchuo/article/details/126209963
  • [技术干货] C/C++后端实习经验大礼包-转载
    C/C++后端实习经验大礼包文章目录C/C++后端实习经验大礼包一、前言二、实习面试宝典1.自我介绍2.深挖个人项目(多个问题不同角度)3.有用过STL吗?常用哪些STL?4.介绍一下你对STL的理解5.深挖STL底层6.Qt有接触过吗?Qt下Tcp通信的整个流程是怎么样的?7.设计模式的问题8.编译原理的简单问题9.讲一下dijkstra算法10.谈一下你对STL的理解11.STL的使用场景12.C++11语法熟悉吗13.工程里面的回溯是什么?14.Widget::Widget(QWidget *parent) :QWidget(parent)什么意思15.算法题:跳台阶(找规律可以发现是个斐波那契数列)16.算法题: 餐厅(区间贪心)17.反问面试官环节三、实习工作分享1.实习专有名词及分析篇1.1SDK:软件开发工具包(Software Development Kit)1.2API:应用程序接口(Application Programming Interface)举例:windows串口通信函数API1.3上位机1.4下位机1.5上位机与下位机区别四、总结一、前言这篇文章是C/C++后端实习经验大礼包的第一弹,后面会持续更新,谢谢大家支持~~撒花,前面说过博主目前在一家互联网公司实习,今天给大家带来第一弹C/C++后端实习经验大礼包,希望大家喜欢。123二、实习面试宝典流程:投简历->简历筛选->笔试->技术电话面->技术视频面->hr面(有些公司可能在中间环节比较多,比如两次技术电话面,两次技术视频面等,视频面多为主管之类的,ps:主管面会参考之前的部门对你面试的评价)1.自我介绍2.深挖个人项目(多个问题不同角度)3.有用过STL吗?常用哪些STL?回答:用过,平时用的比较多,常用vector,map,unordered_map,stack,queue,deque,set,multiset,unordered_set,priority_queue,bitset,list之类的4.介绍一下你对STL的理解回答:STL就是标准模板库,可以提高程序的开发效率和复用性。5.深挖STL底层vector:底层存储是一个可变大小的数组,支持O(1)的随机访问,在尾部之外的位置插入和删除操作时间复杂度是 O(n);deque:双端队列,支持O(1)随机访问在头部和尾部之外的位置插入和删除的时间复杂度是O(n);list: 双向链表,不支持随机访问,只支持顺序访问,在任意位置的插入和删除速度很快;forward_list:单向链表;array是固定大小的数组(vector是可变大小的数组);string:与vector类似,可以理解为特殊的vector,专门用来存储字符,支持随机访问,在尾部之外的位置插入的时间复杂度是O(n);6.Qt有接触过吗?Qt下Tcp通信的整个流程是怎么样的?有的,主要从服务器端和客户端两方面介绍:1.服务器端创建用于监听的套接字(Socket)Socket可以看成在两个程序进行通讯连接中的一个端点,一个程序将一段信息写入Socket中,该Socket将这段信息发送给另外一个Socket中,使这段信息能传送到其他程序中。给套接字设置监听如果有连接到来, 监听的套接字会发出信号newConnected接收连接, 通过nextPendingConnection()函数, 返回一个QTcpSocket类型的套接字对象(用于通信)使用用于通信的套接字对象通信1 发送数据: write2. 接收数据: readAll/read客户端方面:创建用于通信的套接字连接服务器: connectToHost连接成功与服务器通信1 发送数据: write2.接收数据: readAll/read7.设计模式的问题后面我会专门写文章来讲8.编译原理的简单问题后面我会专门写文章来讲9.讲一下dijkstra算法回答:。dijkstra算法是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。时间复杂度:朴素版写法O(V方) 进阶写法:基于优先队列的写法(适用于稀疏图)总复杂度为 O(V log E)Edge:边 Vertex:顶点10.谈一下你对STL的理解C++ STL 做为C++的一个标准类库,包含了复用性最高的数据结构(容器)与算法(模板函数)。STL的容器可以分为以下几个大类:一:序列容器,有vector, list, deque,string.二:关联容器可以分为 set(集合)和 map(映射表)两大类,及其衍生体 multiset 和 multimap。这些容器的底层机制均以 RB-tree(红黑树)实现。RB-tree 也是一个独立容器,但并不开放使用。SGI STL 还提供一个不在标准规格的关联式容器 hash_table(散列表),以及以 hash_table 为底层机制而完成的 hash_set散列集合、hash_map散列映射表、hash_multiset散列多键集合、hash_multimap散列多键映射表。关联容器,类似关联式数据库,每个元素都有一个键值key和一个实值value。关联式容器的内部结构是一个平衡二叉树,包括 AVL-tree、RB-tree、AA-tree,STl 中运用的是 RB-tree红黑树。11.STL的使用场景vector(可变长的动态数组)适用场景:需要快速查找,不需要频繁插入/删除的场景string:string 类型支持长度可变的字符串,实际上就是vector,便于程序员操作字符串的类库。也可以认为string是一个类:string封装了char* ,管理这个字符串,是一个char* 型的容器;array:数组 使用场景:类似vector,比数组更安全(不担心越界),但是内容在栈上,且属于定长容器。deque:(double-ended queue,双端队列)是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。使用场景:头尾增删元素很快,随机访问比vector慢一点,因为内部处理堆跳转。中间插入和删除效率交较高。但因为他是list和vector的结合体,出场次数不多。forward_list:使用场景:需要list的优势,但只要向前迭代list:需要频繁插入/删除,不需要快速查找queue:FIFO(先进先出)~( First Input First Output)。底层容器可以是list或deque。set/multiset:需要元素有序,查找/删除/插入性能一样。红黑树效率都是O(logN)。即使是几个亿的内容,最多也查几十次。map/multimap 映射/多重映射:需要key有序将值关联到key,O(logN)查找/删除/插入性能一样12.C++11语法熟悉吗回答:还行,之后问了std::function,我回答是std::function是一个函数包装模板,可以包装下列这几种可调用元素类型:函数、函数指针、类成员函数指针或任意类型的函数对象(例如定义了operator()操作并拥有函数闭包)。std::function对象可被拷贝和转移,并且可以使用指定的调用特征来直接调用目标元素。当std::function对象未包裹任何实际的可调用元素,调用该std::function对象将抛出std::bad_function_call异常。13.工程里面的回溯是什么?回答:用git一直备份版本有需要就回退一下14.Widget::Widget(QWidget *parent) :QWidget(parent)什么意思由于构造函数是指在创建一个新对象的时候,自动执行,因此通常用来实现一些默认操作。此处“Widget::Widget(QWidget *parent) ”定义派生类的构造函数;:QWidget(parent)基类的有参构造函数最终达到:调用基类的有参构造函数,实现对象树上基类的功能15.算法题:跳台阶(找规律可以发现是个斐波那契数列)一个楼梯共有 n 级台阶,每次可以走一级或者两级,问从第 0 级台阶走到第 n 级台阶一共有多少种方案。输入格式共一行,包含一个整数 n。输出格式共一行,包含一个整数,表示方案数。数据范围1≤n≤15输入样例:5输出样例:8#include<bits/stdc++.h>using namespace std;int a=1,b=2,c;int main(){    int n;    cin>>n;    int w=n-2;    if(n==1) cout<<1;    else if(n==2) cout<<2;    else    {        while(w--)        {            c=a+b;            a=b,b=c;        }        cout<<b;    }}123456789101112131415161718192016.算法题: 餐厅(区间贪心)一家餐厅收到了 n 个客人的预约订单。每个订单都有开始时间和结束时间。对于每个订单,餐厅有权利接单,也有权利拒单。接受的订单,两两之间不得有任何时间交集,甚至不得有时刻交集,即如果一个订单的开始时间和另一个订单的结束时间相同,则两订单也不得同时接受。为了赚更多钱,餐厅需要尽可能多的接单。请问,餐厅最多可以接多少单?输入格式第一行包含一个整数 n。接下来 n 行,每行包含两个整数 l,r,表示一个订单的开始时间和结束时间。输出格式输出可以接受的最大订单数量。数据范围1≤n≤5×105,1≤l≤r≤109输入样例1:27 114 7输出样例1:1输入样例2:51 22 33 44 55 6输出样例2:3输入样例3:64 81 54 72 51 36 8输出样例3:2#include<bits/stdc++.h>using namespace std;struct node{    int l,r;};int n;bool cmp(node x,node y){    return x.r<y.r;}int main(){    cin>>n;    node a[n+1];    int i;    for(i=0;i<n;i++)    {        cin>>a[i].l>>a[i].r;    }    sort(a,a+n,cmp);    int temp=a[0].r;    int tot=1;    for(i=1;i<n;i++)    {        if(a[i].l>temp)        {            temp=a[i].r;            tot++;        }    }    cout<<tot;}123456789101112131415161718192021222324252627282930313217.反问面试官环节自由发挥即可,可以提前准备一些大众问题和自己关心的问题。三、实习工作分享1.实习专有名词及分析篇实习中你肯定会接触到很多自己没不熟悉的名词,在这里算法小学徒给大家分享一些cpp后端专有名词的解释:1.1SDK:软件开发工具包(Software Development Kit)软件开发工具包一般都是一些软件工程师为特定的软件包、软件框架、硬件平台、操作系统等建立应用软件时的开发工具的集合。SDK相当于是一个开发者集成的环境,作为APP供应链中重要的一环,在提升App兼容性和灵活性、节约开发成本方面表现卓著。一个产品想实现某些特定功能如消息推送,便可以找到相关的第三方SDK,工程师直接接入SDK,不用再重新开发。这样,工程师可以将更多的时间和精力投入到其他产品业务相关功能的开发上。1.2API:应用程序接口(Application Programming Interface)API又称为应用编程接口,就是软件系统不同组成部分衔接的约定。由于近年来软件的规模日益庞大,常常需要把复杂的系统划分成小的组成部分,编程接口的设计十分重要。程序设计的实践中,编程接口的设计首先要使软件系统的职责得到合理划分。良好的接口设计可以降低系统各部分的相互依赖,提高组成单元的内聚性,降低组成单元间的耦合程度,从而提高系统的维护性和扩展性。简单地说:API就是接口,就是通道,负责一个程序和其他软件的沟通,本质是预先定义的函数。举例:windows串口通信函数API1.CreateFile - 打开串口;2.SetupComm-初始化一个指定的通信设备的通信参数3.ReadFile - 读数据;4.WriteFile - 写数据;5.CloseHandle - 关闭串口;6.GetCommState - 取得串口当前状态;7.SetCommState - 设置串口状态;8.PurgeComm - 清除串口缓冲区 ;9.ClearCommError - 清除串口错误或者读取串口现在的状态;10.SetCommMask - 设置串口通信事件;1.3上位机上位机是指可以直接发出操控命令的计算机。1.4下位机下位机是直接控制设备获取设备状况的计算机。1.5上位机与下位机区别1.上位机一般是集中管理监控机,下位机是指现场直接控制器或控制机。上位机面向管理级用户,下位机面向底层设备控制。2.上位机:上位监视系统,一般为计算机系统(监控软件;下位机:控制系统的现场执行系统,一般为PLC等设备。3上位机是指工业控制中位于较高层次的计算机,一般是指电脑;而下位机是直接控制设备获取设备状况的的计算机,一般是指PLC/单片机之类的。4.经验:通常工控机,工作站,触摸屏作为上位机;而通信控制PLC,单片机等作为下位机,从而控制相关设备元件和驱动装置。四、总结后面博主会继续为大家带来 C/C++后端实习经验大礼包的其他内容,希望大家喜欢,撒花~~,另外根据博主的亲身实习经验,自学能力不管是面试还是实习过程中都非常受青睐, 程序员行业是一个需要终身学习的行业,大部分时间别人教你的东西只能作为一个参考,而且自学这种能力可以让人感觉到了无限的可能和创造性,跨越认识边界,不受限制的感觉真的很奇妙每日一句:不是因为有希望才去努力,而是努力了,才能看到希望。成功重在努力与坚持,抓住时机,就趁现在!与大家共勉!!!————————————————版权声明:本文为CSDN博主「算法小学徒」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/wyhplus/article/details/125771094
  • [技术干货] 算法系列二:插值查找、斐波那契查找-转载
    文章目录四. 插值查找4.1 简介4.2 代码实现五. 斐波那契查找5.1 简介5.2 算法实现四. 插值查找4.1 简介上一篇的二分查找中,每次查找都是从待查序列的中间开始,那么就很容易想到一个问题或者场景:假设我有一个数组0~999,我要查找的数为900,如果按照二分查找,那我每次取中间值要查找好一会,我们从上帝视角看明显可以从靠后的位置去查。于是针对这种情况,出现了插值查找。基本思路  插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的 查找方法,其核心就在于插值的计算公式 (key-array[low])/(array[high]-array[low])*(high-low)。简而言之,基于二分查找算法,将查找点的选择改进为自适应选择。复杂度分析时间复杂性:如果元素均匀分布,则O(log(logn)),在最坏的情况下可能需要O(n)。空间复杂度:O(1)。优缺点分析  对于长度比较长、关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。区别对比:① 插值查找类似于二分法,但插值查找每次从自适应 mid 处开始查找;② 二分查找种mid为(left+right) / 2, 插值查找则是通过公式计算得来;③ 插值查找公式:int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;low表示左边索引left,high表示右边索引right. key 就是需要查找的值。插值查找特点:① 查找序列有序;② 数据量大、关键字分布均匀的有序序列,插值查找快;③ 对于分布不均匀的有序序列来说,不一定比二分查找好。4.2 代码实现① 迭代法查找:private static int insertSearch1(int arr[],int target){    /*初始化左右搜索边界*/       int left=0,right=arr.length-1;       int mid;       while(left<=right){           mid=left+(target-arr[left])/(arr[right]-arr[left])*(right-left);           /*arr[mid]大于target,即要寻找的元素在左半边,所以需要设定右边界为mid-1,搜索左半边*/           if(target<arr[mid]){               right=mid-1;           /*arr[mid]小于target,即要寻找的元素在右半边,所以需要设定左边界为mid+1,搜索右半边*/              }else if(target>arr[mid]){               left=mid+1;           /*搜索到对应元素*/           }else if(target==arr[mid]){               return mid;           }       }       /*搜索不到返回-1*/       return -1;    }② 递归法实现:private static int insertSearch2(int array[],int left,int right,int target){    if(left<=right){        int mid=left+(target-array[left])/(array[right]-array[left])*(right-left);        /*搜索到对应元素*/        if(array[mid]==target){            return mid;        }else if(array[mid]<target){            /*array[mid]小于target,即要寻找的元素在右半边,所以需要设定左边界为mid+1,搜索右半边*/            return insertSearch2(array,mid+1,right,target);        }else{            /*array[mid]大于target,即要寻找的元素在左半边,所以需要设定右边界为mid-1,搜索左半边*/            return insertSearch2(array,left,mid-1,target);        }    }else{        return -1;    }}uniapp uView u-picker组件三级联动Demozip0星超过10%的资源555KB下载五. 斐波那契查找5.1 简介斐波那契查找又名黄金分割查找算法。什么是黄金分割?黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618.由于按此比例设计的造型十分美丽,因此称为黄金分割,也称中外比。什么是斐波那契数列?斐波那契数列{1, 1, 2, 3, 5, 8, 13, 21, 34, 55…}发现斐波那契数列的两个相邻数的比例,无限接近黄金分割值0.618算法原理:斐波那契查找原理与二分查找算法和插值查找算法非常相似,仅仅改变了中间节点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近,即mid=low+F(k-1)-1(F代表斐波那契数列)。???怎么理解这里的mid由斐波那契数列F[k] = F[k-1] + F[k-2]的性质,可以得到(F[k]-1) = (F[k-1]-1) + (F[k-2]-1) + 1. 该式说明:只要顺序表的长度为F[k]-1,则可以将该表分成长度为F[k-1]-1 和F[k-2]-1的两段,如上图所示。从而中间位置为mid=low+F(k-1)-1.类似的,每一字段也可以用相同的方式分割但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1.这里的k值只要能使F[k]-1恰好大于或等于n即可,由以下代码得到,顺序表长度增加后,新增的位置(从n+1 到 F[k]-1位置),都赋为n位置的值即可while(n>fib(k)-1){  k++;}123复杂度分析最坏情况下,时间复杂度为O(logn),且其期望复杂度也为O(logn)。5.2 算法实现public class FibonacciSearch {        public static int FLENGTH = 20;    public static void main(String[] args) {        int [] arr = {1,8,10,89,100,134};        int target = 89;        System.out.println("目标元素在数组中位置是:" + fibSearch(arr, target));            }    public static int[] fib() {        int[] f = new int[FLENGTH];        f[0] = 1;        f[1] = 1;        for (int i = 2; i < FLENGTH; i++) {            f[i] = f[i-1] + f[i-2];        }        return f;    }        public static int fibSearch(int[] arr, int target) {        int low = 0;        int high = arr.length - 1;        int k = 0;         int mid = 0;         int f[] = fib();        /*获取最相邻的斐波那契数组中元素的值,该值略大于数组的长度*/        while(high > f[k] - 1) {            k++;        }        /*因为 f[k]值可能大于arr的长度。如果大于时,需要构造一个新的数组temp[],将arr数组中的元素拷贝过去,不足的部分会使用0填充*/        int[] temp=Arrays.copyOf(arr, f[k]);        /*然后将temp后面填充的0,替换为最后一位数字         *如将temp数组由{1,8,10,89,100,134,0,0}变换为{1,8,10,89,100,134,134,134}*/        for(int i = high + 1; i < temp.length; i++) {            temp[i] = arr[high];        }                while (low <= high) {             mid = low + f[k - 1] - 1;            if(target < temp[mid]) {                 high = mid - 1;                /*因为f[k]=f[k-1]+f[k-2],所以k--就相当于取temp数组的左边部分*/                k--;            } else if ( target > temp[mid]) {                 low = mid + 1;                /*同理,f[k]=f[k-1]+f[k-2],k -= 2就相当于取temp数组的右边部分*/                k -= 2;            } else {                /*原arr数组中的值*/                if(mid <= high){                    return mid;                /*在temp中,扩展出来的高位的值*/                }else{                    return high;                }            }        }        return -1;    }}这里的算法实现可以理解可以看这位博主————————————————版权声明:本文为CSDN博主「Pisces_224」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/qq_36256590/article/details/126176644
  • [技术干货] 选择排序、冒泡排序、插入排序【十大经典排序算法】-转载
    选择排序、冒泡排序、插入排序【十大经典排序算法】利用对数器验证结果【选用Arrays.sort()系统提供的来】1 选择排序【选最小】//选择排序【每次选出一个最小的】public static void selectSort(int[] arr){    if(arr == null || arr.length < 2){        return;    }    for (int i = 0; i < arr.length - 1; i++){        int min = i;//假设i位置为最小值        for (int j = i+1; j < arr.length; j++) {            if(arr[j] < arr[min]){                min = j;            }        }        swap(arr, i, min);    }}1234567891011121314152 冒泡排序【选最大】//冒泡排序[每次选出最大的]public static void bubbleSort(int[] arr){    if(arr == null || arr.length < 2){        return;    }    for (int i = 0; i < arr.length - 1; ++i){        for(int j = 0; j < arr.length - i - 1; ++j){            if(arr[j] > arr[j+1]){                swap(arr, j, j+1);            }        }    }}123456789101112133 插入排序【前面有序】//插入排序[保证前面部分全部有序]public static void insertSort(int[] arr){    if(arr == null || arr.length < 2){        return;    }    for(int i = 1; i < arr.length; ++i){ //保证[0, i]位置上有序        for(int j = i - 1; j >= 0; j--){            if(arr[j] > arr[j+1]){                swap(arr, j, j+1);            }        }    }}123456789101112134 对数器4.1 gernateRandomArr(int maxSize, int maxValue)Math.random() -> [0,1) 所有的小数,等概率返回一个Math.random() * N -> [0,N) 所有小数,等概率返回一个(int)(Math.random() * N) -> [0,N-1] 所有的整数,等概率返回一个arr[i] = (int)((Math.random()+1) * maxValue - Math.random() * maxValue);【保证有正有负】//构建随机数组public static int[] generateRandomArr(int maxSize, int maxValue){    // Math.random() -> [0,1) 所有的小数,等概率返回一个    // Math.random() * N -> [0,N) 所有小数,等概率返回一个    // (int)(Math.random() * N) -> [0,N-1] 所有的整数,等概率返回一个    int[] arr = new int[(int)(Math.random() * (maxSize + 1))];    for (int i = 0; i < arr.length; i++) {        arr[i] = (int)((Math.random()+1) * maxValue - Math.random() * maxValue);    }    return arr;}12345678910114.2 copy(int[] arr)//复制数组public static int[] copy(int[] arr){    if(arr == null){        return null;    }    int[] res = new int[arr.length];    int i = 0;    for (int num : arr) {        res[i++] = num;    }    return res;}1234567891011124.3 isEq//判断数组是否相等public static boolean isEq(int[] arr1, int[] arr2){     if((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)){         return false;     }     if(arr1 == null && arr2 == null){         return true;     }     if(arr1.length != arr2.length){         return false;     }     for(int i = 0; i < arr1.length; ++i){         if(arr1[i] != arr2[i]){             return false;         }     }     return true;}————————————————版权声明:本文为CSDN博主「NPE~」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/weixin_45565886/article/details/126185609
  • [技术干货] 【简答题】月薪4k和月薪8k的区别就在这里-转载
    什么是数据?1.所有能被输入到计算机中,且能被计算机处理的符号的总称。如:实数、整数、字符(串)、图形和声音等。2.是计算机操作对象的集合。3.是计算机处理的信息的某种特定的符号表示形式。算法的五种性质1.有穷性2.确定性3.有效性4.输入5.输出算法设计的目标1.正确性2.可读性3.健壮性4.高效率(时间与空间)算法的描述方式:1.自然语言2.程序设计语言3.伪代码4.流程图多项式时间算法的时间复杂度有哪些形式?1.常量阶:O(1)2.线性阶:O(n)3.平方阶:O(n2)4.立方阶5.对数阶6.线性对数阶按照数据元素之间逻辑关系的特性可分为哪几类(作简要说明)?1.集合集合中数据元素之间除了“同属于一个集合”的特性外,数据元素之间无其他关系,它们之间的关系称为是松散性的2.线性结构线性结构中数据元素之间存在“一对一”的关系3.树形结构树形结构中数据元素之间存在“一对多”的关系4.图形结构图形结构中数据元素之间存在“多对多”的关系列举几个常见的链表(至少三个)?1.单链表1.循环链表2.双向链表3.双向循环链表顺序表与链表的比较1.链表比较灵活,插入和删除操作效率较高,但空间利用率低,适用于实现动态的线性表;2.顺序表实现比较简单,并且空间利用率也较高,可高效的进行随机存取,但顺序表不易扩充,插入和删除操作效率较低,适合于实现相对“稳定”的静态线性表。静态查找与动态查找分别是什么?静态查找表:查找表的操作不包含对表的修改操作。也就是仅对查找表进行查找或读表元操作。动态查找表:若在查找的同时插入了表中不存在的记录,或从查找表中删除了已存在的记录。动态表查找有什么特点?表结构本身是在查找过程中动态生成的,即对于给定值key,若表中存在关键字值等于key的记录,则查找成功返回;否则插入关键字值等于key的记录。什么是二叉排序树?二叉排序树或者是一棵空树,或者是一颗具有下列性质的二叉树:① .若左子树不空,则左子树上所有结点的值均小于根结点的值;② .若右子树不空,则右子树上所有结点的值均大于根结点的值;③ .它的左右子树也都是二叉排序树简述什么是结点的平衡因子。结点的平衡因子:该结点的左子树深度与右子树深度之差,又称为平衡度。① .平衡二叉树也就是树中任意结点的平衡因子的绝对值小于等于1的二叉树。② .在AVL树中的结点平衡因子可能有3种取值:-1、0、1在哈希表查找中,对数字的关键字常用的哈希函数有哪些(不少于5个)1. 除留余数法2. 平方取中法3. 直接定址法4. 折叠法5. 数字分析法6. 随机数法在哈希表查找中,常用的处理哈希冲突的方法有哪些(不少于3个)1. 开放定址法2. 链地址法3. 公共溢出区法4. 再哈希法computed 和 watch 的区别computed: 是计算属性,依赖其它属性值,并且 computed 的值有缓存,只有它依赖的属性值发生改变,下一次获取 computed 的值时才会重新计算 computed 的值;watch: 更多的是“观察”的作用,类似于某些数据的监听回调,每当监听的数据变化时都会执行回调进行后续操作;vue-router 路由模式有几种?vue-router 有 3 种路由模式:hash、history、abstract各模式的说明如下:hash: 使用 URL hash 值来作路由。支持所有浏览器,包括不支持 HTML5 History Api 的浏览器;history : 依赖 HTML5 History API 和服务器配置。具体可以查看 HTML5 History 模式;abstract : 支持所有 JavaScript 运行环境,如 Node.js 服务器端。如果发现没有浏览器的 API,路由会自动强制进入这个模式.vue中为什么data是一个函数组件的data写成一个函数,数据以函数返回值形式定义,这样每复用一次组件,就会返回一份新的data,类似于给每个组件实例创建一个私有的数据空间,让各个组件实例维护各自的数据。如果单纯的写成对象形式,就使得所有组件实例共用了一份data,这样一个实例中更新数据会导致其他实例数据改变。v-if 和 v-show 的区别v-if 在编译过程中会被转化成三元表达式,条件不满足时不渲染此节点。v-show 会被编译成指令,条件不满足时控制样式将此节点隐藏请列举几个vue内部指令,并说明其作用(至少五个)1. v-bind:绑定属性,动态更新HTML元素上的属性。例如 v-bind:class;2. v-on:用于监听DOM事件。例如 v-on:click v-on:keyup;3. v-text:更新元素的textContent;4. v-model:用来在 input、select、textarea、checkbox、radio 等表单控件元素上创建双向数据绑定,根据表单上的值,自动更新绑定的元素的值;5. v-for:循环指令编译出来的结果是 -L 代表渲染列表。优先级比v-if高最好不要一起使用,尽量使用计算属性去解决;6. v-show:使用指令来实现 -- 最终会通过display来进行显示隐藏;你建不建议v-if和v-for一起使用?为什么?v-for和v-if不要在同一标签中使用,因为解析时先解析v-for在解析v-if。如果遇到需要同时使用时可以考虑写成计算属性的方式。v-for为什么要加keyv-for遍历时,key是Vue中vnode的唯一标记,通过这个 key,我们的 diff 操作可以更准确、更快速。更准确是因为带 key时,在sameNode函数进行key值对比中可以避免就地复用的情况。所以会更加准确。更快速是利用 key 的唯一性生成 map 对象来获取对应节点,比遍历方式更快什么是微服务框架?微服务架构就是将单体的应程序分成多个应程序,这多个应程序就成为微服务,每个微服务运行在自己的进程中,并使用轻量级的通信机制。这些服务围绕业务能力来划分,并通过自动化机制来独立部署。汶些服务可以使用不同的编程语言,不同数据库,以保证最低限度的集中式管理Spring Cloud是什么Spring Cloud是一系列框架的有序集合,它利用Spring Boot的开发便利性巧妙的简化了分布式系统基础设施的开发,如服务发现、配置中心、智能路由、消息总线、负载均衡等,都可以用Spring Boot的开发风格来做到一键部署和启动。Spring Cloud将各家公司开发的比较成熟的服务框架组合起来,通过Spring Boot风格进行再封装,屏蔽掉了复杂的配置和实现原理,最终给开发者一套易懂、易部署和易维护的分布式系统开发工具包。Spring Cloud和Spring Boot的区别Spring Boot专注于快速方便的开发单个个体微服务。Spring Cloud关注全局,它将Spring Boot开发的单体微服务整合并管理起来Spring Cloud为各个微服务之间提供配置管理、服务发现、路由、熔断、降级等等集成服务。Spring Boot可以离开Spring Cloud独立使用开发项目,Spring Cloud离不开Spring Boot,属于依赖关系Spring Boot专注于微服务个体,Spring Cloud关注全局的微服务治理SpringCloud Alibaba有哪些主要功能?分布式配置:分布式系统的外部配置管理,配置中心可视化、分环境配置控制。配置动态更新能力。服务注册与发现:适配SpringCloud标准的服务注册与服务发现管理。服务限流与降级:可通过控制台进行实时的修改限流降级的规则,实时的Metrics监控。支持多种协议消息驱动:基于RocketMQ实现消息驱动的业务场景开发。分布式事务:开源Seata使用@GlobalTransactional注解,零侵入的实现分布式事务的支持。SpringCloud Alibaba核心组件有哪些?Nacos (配置中心与服务注册与发现)Sentinel (分布式流控)RocketMQ (消息队列)Seata (分布式事务)Dubbo (RPC)Nacos是什么,他有哪些关键特性?Nacos用于服务的注册发现与服务的配置管理,它提供了简单易用的Web Console。可以帮助开发者快速的实现服务发现、服务配置管理、服务元数据等需求它的关键特性主要有:服务发现和服务健康监测动态配置服务动态 DNS 服务服务及其元数据管理Sentinel是什么,它有什么作用?Sentinel是一个高可用的流量控制与防护组件,保障微服务的稳定性。Sentinel分为两个部分,sentinel-core与sentinel-dashboard。sentinel-core 部分能够支持在本地引入sentinel-core进行限流规则的整合与配置。sentinel-dashboard 则在core之上能够支持在线的流控规则与熔断规则的维护与调整等。熔断和降级的区别?服务降级有很多种降级方式!如开关降级、限流降级、熔断降级!服务熔断属于降级方式的一种!当发生下游服务不可用的情况,熔断和降级必定是一起出现。服务降级大多是属于一种业务级别的处理,熔断属于框架层级的实现什么是Feign?Feign是一个声明web服务客户端,这使得编写web服务客户端更容易Feign将我们需要调用的服务方法定义成抽象方法保存在本地就可以了,不需要自己构建Http请求,直接调用接口即可,不过要注意的是,调用的方法要和本地抽象方法的签名完全一致。Spring Cloud Gateway是什么,它有什么作用?Spring Cloud Gateway是Spring Cloud官方推出的第二代网关框架,取代Zuul网关。网关作为流量控制组件,在微服务系统中有着非常重要的作用,网关常见的功能有转发、权限校验、限流控制等作用什么是Redis,它有哪些基本数据类型?Redis是用C语言开发的一个开源的高性能键值对(key-value)数据库。它通过提供多种键值数据类型来适应不同场景下的存储需求,Redis支持的基本数据类型如下:字符串类型 string散列类型 hash列表类型 list集合类型 set有序集合类型 sortedset有哪些场景可以使用 RabbitMQ?服务间异步通信顺序消费定时任务请求削峰RabbitMQ有哪几种常见的工作模式?Work queuesPublish/Subscribe:发布订阅模式Routing:路由模式TopicsHeaderRPCMQ的优点有哪些?异步处理 - 相比于传统的串行、并行方式,提高了系统吞吐量。应用解耦 - 系统间通过消息通信,不用关心其他系统的处理。流量削锋 - 可以通过消息队列长度控制请求量;可以缓解短时间内的高并发请求。日志处理 - 解决大量日志传输。消息通讯 - 消息队列一般都内置了高效的通信机制,因此也可以用在纯的消息通讯。————————————————版权声明:本文为CSDN博主「陶然同学」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/weixin_45481821/article/details/126163199
  • [技术干货] 寻找OpenConfig Yang和IETF Yang的前世今生:2.Yang的语法结构
    上一期为大家区分了 NETCONF 和 YANG  ,分别阐述了他们出现的缘由。因为YANG还是很重要的,所以本期多说些,给大家介绍下YANG的树形语法结构。.  Yang的语法结构YANG模型是一种树形结构,是由无数的叶子、列表、叶列表、容器组成的描述整个设备的一棵树。具体来说,YANG模型有四种主要类型的数据节点,包括叶节点(leaf)、列表节点(list)、叶列表节点(leaf-list)和容器节点(container):    叶子                      列表                           叶列表                      容器                  除了以上四种主要类型的数据节点外,组(grouping)、分支(choice)、基础数据类型和派生类型(typedef)也是YANG模型其中一部分的相关功能定义语句。    组                      分支                      基础数据类型                      派生类型                  .本期大家知道了Yang的树形结构,树形结构比于数组、链表、队列和栈等线性结构要复杂些,通过设定条件和限制就可以定义出一种新类型的树。但是树形结构其实很形象,并且不同的树也有很多有趣的特点,如果大家感兴趣,可以自行了解一下。下一期重点来了,大家可以提前思考:OpenConfig Yang和IETF Yang 到底是什么?为什么有两种模型?是哪些人创造了它们?在使用上会有什么要求呢?让我们后面逐步解答...*注:部分文档来源于网络.上一篇:《Yang的缘起》下一遍:待更新.iMaster NCE AOC社区入口:    中文版社区      /    英文版社区 
总条数:771 到第
上滑加载中