刷题学算法

数据结构

一、数组

1. 数组创建：

// 方式1：先创建，再逐个存储元素
String[] cityArray1 = new String[5];
cityArray1[0] = "北京";
cityArray1[1] = "上海";
cityArray1[2] = "广州";
cityArray1[3] = "深圳";
cityArray1[4] = "杭州";
System.out.println(Arrays.toString(cityArray1));// 方式2：创建数组，并直接初始化数组中的元素(不使用new关键字)
String[] cityArray2 = { "成都", "重庆", "西安", "苏州", "南京", "大连", "沈阳" };
System.out.println(Arrays.toString(cityArray2));
System.out.println(cityArray2.length);// 错误
// cityArray2 = {"","",""}; 使用该方式初始化元素值，初始化必须与定义数组在同一行代码中// 方式3：创建数组，并直接初始化数组中的元素(使用new关键字)
String[] cityArray3 = new String[] { "宝鸡", "安康", "汉中", "渭南" };
System.out.println(Arrays.toString(cityArray3));// 该方式可以让数组重新分配内存空间，并初始化
cityArray3 = new String[] {"南洋","信阳","沁阳","濮阳"};

Java的数组有几个语法特点：
●数组所有元素初始化为默认值，整型都是0，浮点型是0.0，布尔型是false；
●数组一旦创建后，大小就不可改变，所以说数组长度固定；
●访问数组中的某一个元素，需要使用索引。数组索引从0开始。例如，5个元素的数组，索引范围是0~4。
●可以修改数组中的某一个元素，使用赋值语句，例如，ns[1] = 79;
●可以用数组变量.length获取数组大小

2.Leetcode题目

hot100 : easy1

二、栈 stack

栈详解参考
在Java中，我们用Deque可以实现Stack的功能

这里注意，pop()返回的是被弹出的站定对象，但与此同时会对栈做顶部元素移除

三、链表（ListNode）

链表是一种数据结构：由数据和指针构成，链表的指针指向下一个节点。 链表 是用Java自定义实现的链表结构，在Java中用需要自己定义一个ListNode类来生成链表对象。

对链表的操作

class ListNode {        //类名 ：Java类就是一种自定义的数据结构int val;            //数据 ：节点数据 ListNode next;      //对象 ：引用下一个节点对象。在Java中没有指针的概念，Java中的引用和C语言的指针类似ListNode(int val){  //构造方法 ：构造方法和类名相同   this.val=val;   //把接收的参数赋值给当前类的val变量}
}class Test{public static void main(String[] args){ListNode nodeSta = new ListNode(0);          //创建首节点ListNode nextNode;                           //声明一个变量用来在移动过程中指向当前节点nextNode=nodeSta;                            //指向首节点//创建链表for(int i=1;i<10;i++){ListNode node = new ListNode(i);         //生成新的节点nextNode.next=node;                      //把心节点连起来nextNode=nextNode.next;                  //当前节点往后移动} //当for循环完成之后 nextNode指向最后一个节点，nextNode=nodeSta;                            //重新赋值让它指向首节点print(nextNode);                             //打印输出//插入节点while(nextNode!=null){if(nextNode.val==5){ListNode newnode = new ListNode(99);  //生成新的节点ListNode node=nextNode.next;          //先保存下一个节点nextNode.next=newnode;                //插入新节点newnode.next=node;                    //新节点的下一个节点指向 之前保存的节点}nextNode=nextNode.next;}//循环完成之后 nextNode指向最后一个节点nextNode=nodeSta;                            //重新赋值让它指向首节点print(nextNode);                             //打印输出}static void print(ListNode listNoed){//创建链表节点while(listNoed!=null){System.out.println("节点:"+listNoed.val);listNoed=listNoed.next;}System.out.println();}
}

注意：对链表进行操作时，经常要新建一个链表变量去存放后边要用到的节点，一遍后期指向；

算法

一、递归算法

eg: hot100.3

什么是递归呢？函数在运行时调用自己，这个函数就叫递归函数，调用的过程叫做递归。 比如定义函数 f(x)=x+f(x−1)f(x)=x+f(x-1)f(x)=x+f(x−1)：
递归的两个规律：
（1）递归函数必须要有终止条件，否则会出错；
（2）递归函数先不断调用自身，直到遇到终止条件后进行回溯，最终返回答案。

二、斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下递推的方法定义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

    public int climbStairs(int n) {int p=1; int q=1; int sum;for(int i=0; i<n-1; i++){sum = p+q;p=q;q=sum;}return q;}

零散知识点

一、String

substring(i) – 字符串从0开始，截取包括i所在位及后边所有位数字符串
indexOf(“h”) – 返回字符串中首次出现h的位置

二、常用方法

判断偶数：i%2==0
判断奇数：i%2==1

三、Collection

排序：Collections.sort()