前言

记录一下leetcode字符串部分题目的刷题笔记，顺序参考代码随想录中，但不仅限于这些，可以扩展记录。

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

1 2	输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]

思路：双指针

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public void reverseString(char[] s) {
        int left = 0  ,len = s.length;
        int right = len - left - 1;
        while(left <= right){
            char temp = s[left];
            s[left++] = s[right];
            s[right--] = temp;
        }
    }
}

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：48.2 MB, 在所有 Java 提交中击败了35.53%的用户
• 通过测试用例：477 / 477

前言

记录一下leetcode哈希表部分题目的刷题笔记，顺序参考代码随想录中，但不仅限于这些，可以扩展记录。

代码随想录 ——哈希表理论基础

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

1 2	输入: s = "anagram", t = "nagaram" 输出: true

思路：哈希表

思路很简单，维护一个26位数组，每次遍历s的时候，对应位置的值+1，遍历t的时候，对应字母位置值-1，当有一个小于0的时候，即数量不同，直接返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
        int[] table = new int[26];
        for(int i = 0 ; i<s.length() ; i++){
            table[s.charAt(i)-'a']++;
        }
        for(int i = 0; i < t.length(); i++){
            table[t.charAt(i)-'a']--;
            if(table[t.charAt(i)-'a']<0){
                return false;
            }
        }
        return true;
    }
}

前言

记录一下leetcode树部分题目的刷题笔记

一、二叉树的深度优先遍历

• 前序遍历
• 中序遍历
• 后序遍历

这三种遍历方式，我个人比较倾向于递归法来实现，因为递归法的代码简洁，三种遍历的写法很类似。

其实还可以使用统一迭代法来实现这三种遍历方式，但个人觉得还是有点难记~可以当作扩展来了解

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

1 2	输入：root = [1,null,2,3] 输出：[1,3,2]

思路：递归

首先我们需要了解什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

定义 inorder(root) 表示当前遍历到 root 节点的答案，那么按照定义，我们只要递归调用 inorder(root.left) 来遍历 root 节点的左子树，然后将 root 节点的值加入答案，再递归调用inorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。

前言

5月份每日一题记录~

1305. 两棵二叉搜索树中的所有元素

给你 root1 和 root2 这两棵二叉搜索树。请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.

1
2

输入：root1 = [2,1,4], root2 = [1,0,3]
输出：[0,1,1,2,3,4]

思路：中序遍历+归并

回顾二叉搜索树的定义：

• 当前节点的左子树中的数均小于当前节点的数；

• 当前节点的右子树中的数均大于当前节点的数；

• 所有左子树和右子树自身也是二叉搜索树。

根据上述定义，我们可以用中序遍历访问二叉搜索树，即按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候也按照同样的方式遍历，直到遍历完整棵树。遍历结束后，就得到了一个有序数组。

由于整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。具体描述见 94. 二叉树的中序遍历 的 官方题解。

中序遍历这两棵二叉搜索树，可以得到两个有序数组。然后可以使用双指针方法来合并这两个有序数组，这一方法将两个数组看作两个队列，每次从队列头部取出比较小的数字放到结果中（头部相同时可任取一个）。如下面的动画所示：

前言

该部分为面向对象编程（中级部分）

包

基本介绍

本质：创建不同的文件夹来保存类文件

三大作用

• 1、区分相同名字的类
• 2、当类很多时，可以很好的管理类
• 3、控制访问范围

基本语法

1

package com.hspedu;

• 1、package 关键字，表示打包
• 2、com.hspedu 表示包名

包的命名

规则：只能包含数字、字母、下划线、小圆点。但不能用数字开头，不能是关键字或保留字

规范：

• 一般是小写字母+小圆点
• com.公司名.项目名.业务模块名

常用的包

1
2
3
4

java.lang.*		//lang是基本包，默认引入，不需要再引入
java.util.*		//util包，系统提供的工具包，工具类，使用Scanner
java.net.*		//网络包，网络开发
java.awt.*		//java界面开发，GUI

前言

记录一下3月底、4月份每日一题记录，顺便督促自己打卡，仅记录每日一题~

（困难题型是否可以摸鱼呢？）

172. 阶乘后的零

题目描述：给定一个整数 n ，返回 n! 结果中尾随零的数量。提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

自己的解法

最开始想的是阶乘求解之后，再去求末尾0的数量， 例如阶乘后的结果遍历对(10*j)求余，但发现执行到30就走不通了= =，就算给result赋值long类型也不够，因为会溢出。

思路学习

首先末尾有多少个 0 ，只需要给当前数乘以一个 10 就可以加一个 0。

再具体对于 5!，也就是 5 * 4 * 3 * 2 * 1 = 120，我们发现结果会有一个 0，原因就是 2 和 5 相乘构成了一个 10。而对于 10 的话，其实也只有 2 * 5 可以构成，所以我们只需要找有多少对 2/5。

我们把每个乘数再稍微分解下，看一个例子。

11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 11 * (2 * 5) * 9 * (4 * 2) * 7 * (3 * 2) * (1 * 5) * (2 * 2) * 3 * (1 * 2) * 1

对于含有 2 的因子的话是 1 * 2, 2 * 2, 3 * 2, 4 * 2 …

对于含有 5 的因子的话是 1 * 5, 2 * 5…

含有 2 的因子每两个出现一次，含有 5 的因子每 5 个出现一次，所有 2 出现的个数远远多于 5，换言之找到一个 5，一定能找到一个 2 与之配对。所以我们只需要找有多少个 5。

直接的，我们只需要判断每个累乘的数有多少个 5 的因子即可。

对于一个数的阶乘，就如之前分析的，5 的因子一定是每隔 5 个数出现一次，也就是下边的样子。

n! = 1 * 2 * 3 * 4 * (1 * 5) * … * (2 * 5) * … * (3 * 5) *… * n

因为每隔 5 个数出现一个 5，所以计算出现了多少个 5，我们只需要用 n/5 就可以算出来。

但还没有结束，继续分析。

… * (1 * 5) * … * (1 * 5 * 5) * … * (2 * 5 * 5) * … * (3 * 5 * 5) * … * n

每隔 25 个数字，出现的是两个 5，所以除了每隔 5 个数算作一个 5，每隔 25 个数，还需要多算一个 5。

也就是我们需要再加上 n / 25 个 5。

同理我们还会发现每隔 5 * 5 * 5 = 125 个数字，会出现 3 个 5，所以我们还需要再加上 n / 125 。

综上，规律就是每隔 5 个数，出现一个 5，每隔 25 个数，出现 2 个 5，每隔 125 个数，出现 3 个 5… 以此类推。

最终 5 的个数就是 n / 5 + n / 25 + n / 125 …

写程序的话，如果直接按照上边的式子计算，分母可能会造成溢出。所以算 n / 25 的时候，我们先把 n 更新，n = n / 5，然后再计算 n / 5 即可。后边的同理。

前言

记录一下leetcode链表部分题目的刷题笔记

203. 移除链表元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null){
            return head;
        }
        // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作
        ListNode dummy = new ListNode(-1 , head);
        ListNode pre = dummy;
        ListNode cur = head;//cur指向当前头节点
        while(cur != null){
            if(cur.val == val){//如果当前头节点值等于val
                //则直接修改前一个结点的指针指向下一个节点（删除当前节点）
                pre.next = cur.next;
            }else{//不相等则继续看下一个节点
                pre = cur ;
            }
            cur = cur.next;//当前节点
        }
        return dummy.next;
    }
}

前言

本部分记录，leetcode上面关于数组、二分查找等部分题目的思路，动态更新。

704. 二分查找

本题是典型的二分查找题目，题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int search(int[] nums, int target) {
        int left = 0 , right = nums.length-1;
        while(left <= right){
            int mid = left + (right - left)/2;
            int num = nums[mid];
            if(num == target){
                return mid;
            }else if(num < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：O*(log*n)，其中 n 是数组的长度。
• 空间复杂度：O(1)。

一、for循环细节

• （1）for(;循环条件;)中的初始化和变量迭代可以写到其他地方，但是两边的分号不能省略
• （2）循环初始值可以有多条初始化语句，但要求类型一样，并且中间用逗号隔开，循环变量迭代也可以有多条变量迭代语句，中间用逗号隔开，例如：

1
2
3

for(inti=0,j=0;i<count;i++,j+=2){
    System.out.println("i=" + i + "j=" + j);
}

二、do while循环

• （1）do while是关键字
• （2）与while的区别：while是先判断再执行，do while先执行，再判断，也就是说一定会执行一次。

（一）Java数据类型

这里需要注意：String在Java里面是属于一个类而不是数据类型。

1、整数类型细节

• Java的整型常量默认为int型，声明long型常量必须在后面加’l’或者‘L’。

1

long a=1L

2、浮点数细节

• Java的浮点型常量默认为double类型，声明float型常量，通常在后面加’f’或‘F’
• 通常情况下，应该使用double型，因为比float型更精确。
• 浮点数使用陷阱：2.7和8.1/3比较，结果不同。（具体可在计算机组成原理里面了解）
• 如果涉及浮点数计算，例如除法得到的变量：a = 8.1 / 3。一般用其进行条件判断时，不使用”=”来作条件（2.7和8.1/3比较例子），而是让条件判断为一个范围，例如：

1
2
3
4
5
6
7
8
9

a = 2.7;
b = 8.1 / 3;
if( a =	b){
	//错误
}
//应该使用以下条件判断：
if(Math.abs(a - b) < 0.00001){
	//0.00001这个数字可以自设定，属于精度
}