当前位置: article > 正文

11.力扣刷题Java_力扣怎么刷java题

作者：weixin_40725706 | 2024-02-15 21:45:21

踩

力扣怎么刷java题

力扣刷题Java

爱学习的饲养员视频内容

https://blog.csdn.net/unspoken0714/article/details/110286517

基础部分：

复杂度
常见的时间复杂度
O(1):
执行常数次，和输入无关

def O1(num):
	i = num
	j = num*2
	return i+j
1
2
3
4

O(N):

def ON(num):
	total = 0
	for i in range(num):
		total+=i
	return total
1
2
3
4
5

O(logN):

def OlogN(num);
	 i = 1
	 while(i < num):
	 	i = i*2
	return i
1
2
3
4
5

O(M+N)

def OMN(num):
	total = 0
	for i in range(num):
		total += 1
	for j in range(num):
		total += j
	return total
1
2
3
4
5
6
7

O(NlogN)

def ONlogN(num1, num2):
	total = 0
	j = 0
	for i in range(num1):
		while(j < num2):
			total += i + j
			j = j*2
	return total
1
2
3
4
5
6
7
8

O(N^2)

def ON2(num):
	total = 0
	for i in range(num):
		for j in range(num):
			total += i + j
	return total
1
2
3
4
5
6

O(1) < O(logN) (二分查找) < O(N) < O(NlogN) < O(N^2) < O(2^n) < O(n!)

常见的空间复杂度
算法的存储空间与输入值之间的关系
O(1) < O(N) < O(N^2)
常量看其与输入值得关系
递归要考虑递归栈
O(1)

def ON(num):
	sum = 0;
	for i in range(num):
		sum = sum+i
	return sum
1
2
3
4
5

递归
O（1）

def ON(num):
	if(num<=0):
		return 0
	return ON(num-1) + ON(num-2)
1
2
3
4

数据结构

1、数组

定义：在连续的内存空间中，储存一组相同类型的元素
数组的访问: 通过索引访问元素。a[0]
数组的内存空间是连续的，增删需要移动后面的元素
二维数组的内存地址是连续的吗？
二维数组实际是一个线性数组存放着其他数组的首地址

数组的搜索：找到这个元素对应的索引

复杂度：
访问Access:O(1)
通过计算可以得到地址位置，从而进行访问
搜索search:O(N)
需要对数组进行遍历
插入insert: O(N)
需要将后面的元素往后移动
如果内存不够，需要开辟一块新空间，将数组移进去
删除delete: O(N)
需要将后面元素往前移
1
2
3
4
5
6
7
8
9
10

特点
适合读
不适合频繁做增删操作。
场景：读多写少

常用操作

（1）创建数组

1、
int[] a = {1,2,3}
System.out.println("a: "+Arrays.toString(a));
2、
int[] b = new int[]{1,2,3}
System.out.println("b: "+Arrays.toString(b));
3、
int[] c = new int[3];
for(int i=0; i < a.length; i++){
	c[i] = i+1;
}
System.out.println("c: "+Arrays.toString(c));
4、
ArrayList<Integer> arr = new ArrayList<>();
for(int i=0; i < 3; i++){
	arr.add(i+1)
}
System.out.println("arr: "+arr.toString());
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（2）添加元素

arr.add(99);
时间复杂度O(1),O(n)
arr.add(3,88);//指定3索引添加元素
1
2
3

（3）访问元素

int c1 = c[1];
int arr1 = arr.get(1);
1
2

（4）更新元素

c[1] = 11;
arr.set(1,11);
1
2

（5）删除元素

arr.remove(3);//删除元素3
1

（6）数组长度

int cSize = c.length;
int arrSize = arr.size();
1
2

（7）遍历数组

1/
for(int i=0; i < c.length; i++){
	int current = c[i];
	System.out.println("c at index"+i+":"+current);
}
2/
for(int i=0; i < arr.size(); i++){
	int current = arr.get(i);
	System.out.println("arr at index"+i+":"+current);
}
1
2
3
4
5
6
7
8
9
10

（8）查找元素

1/
for(int i=0; i < c.length; i++){
	if(c[i] == 99)
	System.out.println("we found 99 in c");
}
2/
boolen is99 = arr.contains(99);
System.out.println("Are we found 99 in arr" + is99);
1
2
3
4
5
6
7
8

（9）数组排序

c = new int[]{2,3,1};
arr = new ArrayList<>();
arr.add(2);
arr.add(3);
arr.add(1);

//排序：时间复杂度O（nlogn）
Arrays.sort(c);  //[1,2,3]
Collections.sort(arr);
//排序：从大到小
法1：将数组c从后往前读
法2：将int[]c 转换为Integer[]c;
	Arrays.sort(Integer[]c,Collections.reverseOrder());
Collections.sort(arr,Collections.reverseOrder());
1
2
3
4
5
6
7
8
9
10
11
12
13
14

练习题力扣：

485给定一个二进制数组，计算其中最大连续 1 的个数。

示例：

输入：[1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int count = 0;
        int result = 0;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == 1){
                count++;
            }else{
                result = Math.max(count,result);
                count = 0;
            }
        }
        return Math.max(count,result);//for循环结束后，最后一次比较result和count
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

283给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

class Solution {
//不需要返回，力扣在当前nums上判断
    public void moveZeroes(int[] nums) {
        int index = 0;
        for(int i = 0; i < nums.length; i++){
            if (nums[i] != 0){
                nums[index] = nums[i];
                index++;
            }
        }
        for(int i = index; i < nums.length; i++){
            nums[i]=0;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

27.给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

//双指针进行移动
class Solution {
    public int removeElement(int[] nums, int val) { 
        if(nums == null || nums.length ==0) return 0;
        int l = 0;
        int r = nums.length-1;
        while(l < r) {

            while(l < r && nums[l] != val){
                l++;
            }
            while(l < r && nums[r] == val){
                r--;
            }
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
        }
        return nums[l] == val? l:l+1;

    }        
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2、链表

非连续空间，包含当前数据和下一节点的地址
复杂度
访问access O（N）
搜索search O（N）
插入insert O (1)
删除 delete O（1）
场景
读少写多

常用操作

（1）创建链表

LinkedList<Integer> list = new LinkedList<>();
1

（2）添加元素 O(1)

list.add(1); //O(1)
list.add(2);
list.add(3);
System.out.println(list.toString());

list.add(2,99);  //2表示索引  O(n)
1
2
3
4
5
6

（3）访问元素

int element = list.get(2);  //O(n)
1

（4）查找元素

int index = list.indexOf(99); //O(n)
//  2
1
2

（5）更新元素

list.set(2,88);  //O(n)
//[1,2,88,3]
1
2

（6）删除元素

list.remove(2);//删除索引为2的元素  O(n)
1

（7）链表长度

int length = list.size();
1

力扣练习：

203

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

/**
 * 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) {
        ListNode result = new ListNode(0);  //result节点是指向开始，为了返回整个链表
        result.next = head;
        ListNode pre = result;             //pre指针记录head前一个指针，方便删除元素
        while(head != null){
            if(head.val == val){
                pre.next = head.next;
            }else{
                pre = head;
            }
            head = head.next;
            
        }
        return result.next;
    }
}
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

206

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

/**
 * 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 reverseList(ListNode head) {
        ListNode result = new ListNode(0);
        result.next = head;
        while(head != null && head.next != null){
            ListNode rnext = result.next;
            ListNode Next = head.next;
            result.next = Next;
            head.next = Next.next;
            Next.next = rnext;
        }
        return result.next;

    }
}
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

3、队列

先进先出
基于链表创建的
单端队列：一个口进一个口出

双端队列：两个口都可以进，两个口都可以出

复杂度
访问: O(N)
搜索：O(N)
插入: O(1)
删除：O(1)

常用操作

（1）创建队列

Queue<Integer> queue = new LinkedList<>();
1

（2）添加元素 O(1)

queue.add(1); //O(1)
queue.add(2);
queue.add(3);
System.out.println(queue.toString());
1
2
3
4

（3）获取即将出队的元素 O(1)

int temp1 = queue.peek();
1

（4）删除即将出队的元素O(1)

int temp2 = queue.poll(); 
1

（5）判断队列是否为空O(1)

queue.isEmpty();
//true,false
1
2

（6）队列长度O(1)

queue.size();
1

（7）遍历队列O(n)

while(!queue.isEmpty()){
	int temp = queue.poll();
	System.out.println(temp);
}
1
2
3
4

力扣练习：练习题

933

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证每次对 ping 的调用都使用比之前更大的 t 值。

class RecentCounter {
    Queue<Integer> queue;   //声明队列
    
    public RecentCounter() { //构造器中初始化队列
        //初始化队列
        queue = new LinkedList<>();
    }
    
    public int ping(int t) {
        queue.add(t);     // 添加元素
        while(!queue.isEmpty() &&  t - queue.peek() > 3000){
            queue.poll();  //出队
        }
        return queue.size();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Leetcode 239
经典单调队列题目

思路：
将滑动窗可以看成一个双端队列。双端队列的最大值放在头部，当头部与滑动窗口出窗的元素相同时，则弹出队头。滑动窗要新进入的元素与队列的尾部元素进行比较，如果比尾部元素大，这弹出尾部元素，因为尾部元素肯定不可能为最大元素。直到尾部元素比要进队元素大或者队列为空时，将进队元素压入队尾。

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
queue = deque()
res = []
for i in range(k):
while (len(queue)!=0 and nums[i] > queue[len(queue)-1]):
queue.pop()

        queue.append(nums[i])
    res.append(queue[0])


    for i in range(k,len(nums)):
        if(queue[0]==nums[i-k]):
            queue.popleft()
        
        while (len(queue)!=0 and nums[i] > queue[len(queue)-1]):
            queue.pop()
        queue.append(nums[i])
        res.append(queue[0])

    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4、Stack

先进后出
浏览器后退功能

复杂度
访问: O(1)
搜索：O(N)
插入: O(1)
删除： O(1)

常用操作

（1）创建栈

Stack<Integer> stack = new stack<>();
1

（2）添加元素 O(1)

stack.push(1); 
stack.push(2);
stack.push(3);
System.out.println(stack.toString());
1
2
3
4

（3）查看栈顶元素 O(1)

stack.peek();
1

（4）删除栈顶元素O(1)

int temp2 = stack.pop(); 
1

（5）判断栈是否为空O(1)

stack.isEmpty();
//true,false
1
2

（6）栈长度O(1)

stack.size();
1

（7）遍历栈O(n)

while(!stack.isEmpty()){
	int temp = stack.pop();
	System.out.println(temp);
}
1
2
3
4

力扣练习：练习题

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

class Solution {
    public boolean isValid(String s) {
        if(s.length() == 0)  return true;
        Stack<Character> stack = new Stack<>();         //字符类型为Character
        for(char ch : s.toCharArray()){
            if( ch == '(' || ch == '[' || ch == '{'){   //字符用单引号
                stack.push(ch);
            }else{
                if(stack.size() == 0){
                    return false;
                }else{
                    char temp = stack.pop();            //pop要返回给出值
                    if(ch == ')'){						//pop后要进行括号配对
                        if(temp != '('){
                        return false;}
                    }else if(ch == ']'){
                        if(temp != '['){
                        return false;}
                    }else if(ch == '}'){
                        if(temp != '{'){
                        return false;}
                        }
                    }
                }
            }
        return stack.isEmpty();                         //最后根据是否栈空判断匹配是否成功
    }
}
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

496.给你两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

两个栈，一个存数组，一个存pop出的数：时间复杂度O(MN),空间复杂度O（N）

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack();       
        int[] result = new int[nums1.length];
        for (int num: nums2){						//nums2全部进栈
            stack.push(num);
        }
        for (int i = 0; i < nums1.length; i++){		//遍历nums1的所有数
            Stack<Integer> temp = new Stack();
            int max = -1;
            boolean isfound = false;
            int cur = nums1[i];
            while(!stack.isEmpty() && !isfound ){   //nums2的数找完或者找到相等的数退出循环
                int top = stack.pop();
                if(top > cur){						//找到更大的值进行保存
                    max = top;
                }else if(top == cur){				//找到相等标志改为true
                    isfound = true;
                }
                temp.push(top);                     //将pop的数临时存进temp栈
            }
            result[i] = max;                        //一次for循环结束，找到max，并还原nums2的栈
            while( !temp.isEmpty()){
                stack.push(temp.pop());
            }
        }
    return result;
    }
}
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

5、Hash

Hash Table哈希表，散列表
Key - Value
哈希碰撞：两个不同的key通过同一个hash函数得到相同的内存地址

4通过哈希函数解析出的地址也是1，冲突了。
解决方法：链表法，在后面通过链表加入4.bish
复杂度
访问: 没有这个方法
搜索：O(1)，如果有hash碰撞的情况下，就不是O(1)了，为O(K), K为碰撞元素的个数
插入: O(1)
删除： O(1)

常用操作

（1）创建哈希表

//数组
String[] hashTable = new String[4];
//HashMap
HashMap<Integer,String> map = new HashMap<>();
1
2
3
4

（2）添加元素O(1)

//数组
hashTable[1] = "hanmeimei";
hashTable[2] = "lihua";
hashTable[3] = "siyangyuan";
//HashMap
map.put(1,"hanmeimei");
map.put(2,"lihua");
map.put(3,"siyangyuan");
1
2
3
4
5
6
7
8

（3）删除元素O(1)

hashTable[1] = "";
map.remove(1);
1
2

（4）更新元素O(1)

hashTable[1] = "bishi";
map.put(1,"bishi");
1
2

（5）获取key的值O(1)

String temp = hashTable[3];
map.get(3);
1
2

（6）检查key是否存在

map.containsKey(3);
1

（7）哈希表长度

map.size();
1

（7）哈希表是否还有元素

map.isEmpty();
1

练习题
Leetcode 217

思路：
将数组中的数看做key，出现相同的key，则在key对应的value上+1
然后判断，如果有value>1的情况，则说明有重复元素，返回true

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if(nums == null || nums.length == 0)  return false;       //数组为空的情况
        HashMap<Integer,Integer> map = new HashMap<>();        //map定义的时候key和value类型
        for(int num: nums){                                //map.containsKey()判断碰撞
            if(map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else{
                map.put(num,1);
            }
        }       
        for(int k: map.keySet()){                        //map.keySet()
            if(map.get(k) > 1){
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Leetcode 389给定两个字符串 s 和 t，它们只包含小写字母。

字符串 *t* 由字符串 *s* 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

key -》 ASCII码 value:次数

思路：
将字符串中的元素看做key，出现相同的key，则在key对应的value上+1
然后对t字符串的元素进行遍历，如果该元素没有出现在mapping中，或者该元素对应的value为0，则返回该元素

class Solution {
    public char findTheDifference(String s, String t) {
        int Ssize = s.length();
        int Tsize = t.length();
        if(Ssize == 0 )    return t.charAt(0);			//t.charAt(0)取字符串索引的字符
        int[] Table = new int[26];						//数组建立的hash表
        for(int i = 0; i < Tsize; i++){		//s存在的字符加1，t存在的字符-1，不为0则多余字符
            if(i < Ssize){
                Table[s.charAt(i)-'a']++;
            }
            Table[t.charAt(i)-'a']--;    
        }
        for(int i = 0; i < 26; i++){
            if (Table[i] != 0){
                return (char)('a'+i);      //数字转字符，加‘a’转char类型
            }
        }
        return 'a';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Leetcode 496

思路：
场景：寻找下一更大元素（单调递减栈），或更小元素（单调递增栈）；
使栈里的元素呈现单调递增或者递减
以此题为例，如果想要让栈里元素递减，则当要入栈元素>栈顶元素，则弹出栈顶元素，并用哈希表保存栈顶和入栈元素。直至出现比入栈元素大的栈顶元素，或者栈空。
遍历完元素后，栈中剩余元素，规定其对应的值为-1，存入hash表中

 class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        Stack<Integer> stack = new Stack<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int num: nums2){
            while(!stack.isEmpty() && num > stack.peek()){    //peek取栈顶元素，不会删除
                int temp = stack.pop();						  //pop取栈顶元素并删除
                map.put(temp,num);
            }
            stack.push(num);
        }
        while(!stack.isEmpty()){
            map.put(stack.pop(),-1);
        }
        for(int i = 0; i < nums1.length;i++){
            result[i] = map.get(nums1[i]);
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

6、Set

无序
不重合
主要作用：检查某一个元素是否存在
有没有重复元素

Hash Set: Hash冲突用链表

复杂度
访问: 没有这个方法
搜索：O(1)，如果有hash碰撞的情况下，就不是O(1)了，为O(K), K为碰撞元素的个数
插入: O(1)；有hash冲突O（k）
删除：O(1)；有hash冲突O（k）

常用操作

（1）创建集合

HashSet<Integer> set = new HashSet<>();
1

（2）添加元素O(1)；无序不重复

set.add(1);
set.add(2);
1
2

（3）搜索元素O(1)

set.contains(2)
1

（4）删除元素O(1)

set.remove(2);
1

（5）长度O(1)

set.size();
1

力扣：

217.给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        HashSet<Integer> set = new HashSet<>();
        for(int num: nums){
            set.add(num);
        }
        if(set.size() != nums.length){
            return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

class MyHashSet {
    boolean[] hashSet = null;
    /** Initialize your data structure here. */
    public MyHashSet() {
        hashSet = new boolean[1000001];
    }    
    public void add(int key) {
        hashSet[key] = true;
    }    
    public void remove(int key) {
        hashSet[key] = false;
    }    
    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        return hashSet[key];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

7、树

节点：除了根节点和叶子节点外的节点
根节点：第一个开始的节点
叶子节点：最底层的节点，没有孩子

深度：从上往下计算
高度：从下往上计算
层：从上往下计算。1开始
二叉树（普通二叉树、满二叉树（所有叶子节点在同一层)、完全二叉树）

遍历

前序遍历:先访问根节点，然后访问左节点，最后右节点
中序遍历:先访问左节点，然后访问根节点，最后右节点
后续遍历:先访问左节点，然后访问右节点，最后根节点

力扣

144

145

8、堆（heap）

完全二叉树
每个节点>=(最大堆） or <=（最小堆）孩子节点

复杂度
访问（acess）：无
搜索：O(1) (只查看堆顶元素)
添加：O(logN) 上下层对比
删除：O(logN）一般是堆顶

堆化操作（构建完成二叉树，调整为堆）时间复杂度O(n)

常用操作

（1）创建堆

//创建最小堆
PriorityQueue<Integer> minheap = new PriorityQueue<>();
//创建最大堆
PriorityQueue<Integer> maxheap = new PriorityQueue<>(Collections.reverseOrder());
1
2
3
4

（2）添加元素

minheap.add(1);
maxheap.add(2);
1
2

（3）打印堆

System.out.println(minheap.toString());
1

（4）获取堆顶元素

minheap.peek();
maxheap.peek();
1
2

（5）删除堆顶元素

minheap.poll();
maxheap.poll();
1
2

（6）堆大小

minheap.size();
maxheap.size();
1
2

（7）遍历堆（边删除）

while(!minheap.isEmpty()){
	System.out.println(minheap.poll());
}
1
2
3

Leetcode

215

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length < k || k==0)  return Integer.MIN_VALUE;
        PriorityQueue <Integer> maxheap = new PriorityQueue<>(Collections.reverseOrder());
        for(int num: nums){
            maxheap.add(num);
        }
        while(k > 1){
            maxheap.poll();
            k--;
        }
        return maxheap.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

692

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

思路：

堆：统计前K个

哈希表：统计出现次数

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map  = new HashMap<>();
        //计算单词出现次数保存在哈希表
        for(String word:words){
            if(!map.containsKey(word)){
                map.put(word,0);
            }
            int count = map.get(word)+1;
            map.put(word,count);
        }
        //构建最小堆，重写比较方法，先比较出现次数，次数一样比较字母大小
        //valuez值小的在堆顶，字母大的先出
        PriorityQueue<String> pq = new PriorityQueue<>(
            (w1,w2) -> map.get(w1).equals(map.get(w2)) ?w2.compareTo(w1):map.get(w1)-map.get(w2) 
        );
        //将单词存于最小堆，当单词数大于给定值K时删除堆顶元素
        for(String word: map.keySet()){
            pq.add(word);
            if(pq.size() > k){
                pq.poll();
            }
        }
        //建立数组存放最终结果，将堆中元素全部取出，进行反转即为最终结果
        List<String> res = new ArrayList<>();
        while(!pq.isEmpty()){
            res.add(pq.poll());
        }
        Collections.reverse(res);
        return res;
    }
}
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
32

8、图

无向图

有向图

权重图（最短路径）

入度：多少边指向该顶点

出度：多少边从这个点指向别的顶点

9、Trie 字典树/前缀树

自动匹配

插入：O（n） n表示字符串长度

搜索：O（n）

存在：O（n）

Trie: root结点；孩子结点；结束flag；对应的值

应用：

前缀匹配，词频统计

力扣： 208 实现Trie

力扣： 720 词典中最长的单词

给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。

class Solution {
    public String longestWord(String[] words) {
        if(words == null || words.length ==0)   return "";
        Trie root = new Trie(); //字典树开头
        //在Trie中插入word
        for( String word : words){
            Trie cur = root;
            for(char c: word.toCharArray()){
                if(cur.children.containsKey(c)){
                    cur = cur.children.get(c);
                }else{
                    Trie newNode = new Trie();
                    cur.children.put(c,newNode);
                    cur = newNode;
                }
            }
            cur.val = word;
            cur.isEnd = true;
        }
       
        String result = "";
        for(String word: words){
            Trie cur = root;
            if(word.length() > result.length()||(word.length() == result.length()&& word.compareTo(result) < 0)){
                boolean isWord = true;
                for(char c : word.toCharArray()){
                    cur = cur.children.get(c);
                    if(! cur.isEnd){
                        isWord = false;
                        break;
                    }
                }
                result = isWord? word : result;
            }
        }
        return result;
    }
}
class Trie{
    public HashMap<Character, Trie> children = new HashMap<>();  //孩子结点
    public boolean isEnd = false;    //结束标志
    public String val = null;
}
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
32
33
34
35
36
37
38
39
40
41
42
43

力扣： 692 前k个高频单词

**数据结构知识点回顾

各种数据结构：数组，链表，队列，栈，堆，哈希表，哈希集合，树/图，

访问，搜索，插入，删除
各种数据结构相对应的时间复杂度

算法部分

1、双指针（Two Pointers）

（1）普通双指针：两个指针往同一个方向移动

（2）对撞双指针：两个指针面对面移动（有序）

（3）快慢指针：，慢指针+快指针（判断环形链表）

力扣：141

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null)  return false;				//边界判断
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;						//慢指针一次走一步
            fast = fast.next.next;					//快指针一次走两步
            if( slow == fast){						//快慢指针相遇说明有环
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

力扣：881

第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        if(people == null || people.length == 0) return 0;
        Arrays.sort(people);				//数组排序
        int res = 0;
        int i = 0;
        int j = people.length-1;
        while(i <= j){						//每一次people[j]都载，people[i]需要判断能否同时载
            if(people[i] + people[j] <= limit){ 
                i++;  
            }
            res++;
            j--;    
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

力扣345

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 ‘a’、‘e’、‘i’、‘o’、‘u’，且可能以大小写两种形式出现。

示例 1：

输入：s = “hello”
输出：“holle”

class Solution {
    public String reverseVowels(String s) {
        char[] sca = s.toCharArray();
        for(int i=0,j=sca.length-1;i<j;){
            if(sca[i]=='a'|sca[i]=='e'|sca[i]=='i'|sca[i]=='o'|sca[i]=='u'){
                if(sca[j]=='a'|sca[j]=='e'|sca[j]=='i'|sca[j]=='o'|sca[j]=='u'){
                    char temp = sca[i];
                    sca[i] = sca[j];
                    sca[j] = temp;
                    i++;
                    j--;
                }else{
                    j--;
                }
            }else{
                i++;
            }
        }
        return (new String(sca));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

力扣680 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

class Solution {
    public boolean validPalindrome(String s) {
        for(int i =0,j = s.length()-1;i<j;i++,j--){
            if(s.charAt(i) != s.charAt(j)){
                return isPalindrome(s,i+1,j) | isPalindrome(s,i,j-1);
            }
        }
        return true;
    }
    public boolean isPalindrome(String s,int i ,int  j){
        while(i<j){
            if(s.charAt(i++) != s.charAt(j--)){
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2、二分查找（Binary Search）

适用场景
有序数组中查找指定元素。O（logn）

力扣：704 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution {
    public int search(int[] nums, int target) {
        if( nums == null || nums.length == 0) return -1;
        int left = 0;
        int right = nums.length-1;
        while(left <= right){
            int mid = left + (right-left)/2;            //l+r可能会超过int类型的边界值
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

力扣：35 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

class Solution {
    public int searchInsert(int[] nums, int target) {
        if(nums == null || nums.length == 0)  return 0;
        int left = 0;
        int right = nums.length-1;
        while(left < right){              //插入位置在left位置,right位置，left和right之间
            int mid = left + (right - left)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){  // 移动到mid-1，可能比target小，就需要插入到right之后
                right = mid;
            }else{
                left = mid+1; // 移动到mid+1可能比target大，是第一个比target大的数，就插入到left上
            }
        }
        return nums[left] > target? left:left+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

力扣：162 寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

思路：M>M+1 峰值在M左边

	  M<M+1  峰值在M右边
1

class Solution {
    public int findPeakElement(int[] nums) {
        if(nums == null || nums.length == 0) return -1;
        int left = 0;
        int right = nums.length-1;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] > nums[mid+1]){
                right = mid;		//峰值可能在mid或其左边
            }else {
                left = mid +1;      //峰值在mid+1或其右边
            }
        }
        return left;                //left==right时，找到峰值
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

力扣：74 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

思路：二维索引转换为一维（x,y）—> x * col +y col表示列数

一维索引转换为二维 [i] —> x= i /col y=i%4

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0)  return false;
        int row = matrix.length;
        int col = matrix[0].length;
        int left = 0;
        int right = row * col -1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            int element = matrix[mid / col][mid % col];
            if(element == target){
                return true;
            }else if(element < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3、滑动窗口技巧（Sliding Window）

目的：减少while循环

场景：数组中定长问题

力扣：209 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        if (nums == null || nums.length ==0) return 0;
        int res = nums.length +1;    //定义为第一个取不到的值
        int total = 0;              //数相加的和
        int i = 0;                  //滑动窗口的开头为i，结尾为j
        int j = 0;
        while(j < nums.length){
            total += nums[j];
            j++;
            while(total >= target){
                res = Math.min(res,j-i);
                total -= nums[i];
                i++;
            } 
        }
        return res == nums.length+1? 0:res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

力扣：1456

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的元音字母为（a, e, i, o, u）。

class Solution {
    public int maxVowels(String s, int k) {
        if (s == null || s.length() == 0 || s.length() < k)  return 0;
        HashSet<Character> set = new HashSet<>();   //利用set查找是否是元音字母
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        int res = 0;
        int count = 0;
        //前K个字符窗口判断最大元音数
        for(int i = 0; i < k; i++){    
            char temp = s.charAt(i);
            if(set.contains(temp)){
                count++;
            }
        }
        res = Math.max(res,count);
        //从第k+1个开始进行滑动，每次检查进来的字符和出去的字符是否是元音字母
        for( int i = k; i < s.length(); i++){
            char out = s.charAt(i-k);
            if(set.contains(out)){
                count--;
            }
            char in = s.charAt(i);
            if(set.contains(in)){
                count++;
            }
            res = Math.max(res,count);
        }
        return res;
    }
}
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
32
33
34

4、递归

定义：函数直接或者间接调用自己

经常与回溯、深度优先搜索、分治相结合

4要素：

接受的参数：

返回值：

终止条件：

递归拆解（如何递归下一层）：

时间复杂度：O（2^n）

空间复杂度：O（n）使用了递归栈

力扣：509 斐波那契数列

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。

class Solution {
    public int fib(int n) {  			//接受的参数
        if( n < 2){					    //终止条件
            return n ==1? 1: 0;
        } 
         int sum = fib(n-1)+fib(n-2);	//递归拆解
         return sum;					//返回值
    }
}
1
2
3
4
5
6
7
8
9

力扣：206 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

1—>2—>3—>4—>5—>null

head=5时终止条件成立，返回上一层head=4

head.next.next = head;

1—>2—>3—>4<—5

head.next = null;

1—>2—>3—>4—>null

return res;

再次返回上一层head=3

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode res = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11

力扣：344 反转字符串

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

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

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

思路：双指针，头尾交换

递归：头尾为一层，第二个和倒数第二个为一层

class Solution {
    public void reverseString(char[] s) {
        if (s == null || s.length == 0){
            return ;
        }
        recursion(s, 0, s.length-1);
    }
    private void recursion (char[] s, int left, int right){
        if(left >= right){
            return;
        }
        recursion(s, left+1, right-1);
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

5、分治法

大问题切割成一个个小问题

用到了递归

力扣：169

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

class Solution {
    public int majorityElement(int[] nums) {
        return getMajoriy(nums, 0, nums.length-1);
    }
    private int getMajoriy(int[] nums, int left, int right){
        if(left == right){          //分解到最后单个数字时结束
            return nums[left];
        }
        int mid = left + (right - left)/2;
        int leftMajority = getMajoriy(nums, left, mid);     // 获取左边的多数元素
        int rightMajority = getMajoriy(nums, mid+1, right); // 获取右边的多数元素
		 //左边多数元素和右边多数元素一样，返回
        if(leftMajority == rightMajority){               
            return leftMajority;
        }
        //左边多数元素和右边多数元素不一样，比较出现次数
        int leftCount = 0;
        int rightCount = 0;
        for(int i = left; i <= right; i++){
            if (nums[i] == leftMajority){
                leftCount++;
            }else if(nums[i] == rightMajority){
                rightCount++;
            }
        }
        return leftCount > rightCount? leftMajority: rightMajority;
    }
}
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

力扣：53（暴力法，分治法，动态规划）

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

一分为二：最大子序列在左边，中间，右边

class Solution {
    public int maxSubArray(int[] nums) {
        return getMax(nums, 0, nums.length-1);
    }
    private int getMax(int[] nums, int left, int right){
        if(left == right){
            return nums[left];
        }
        int mid = left + (right - left)/2;
        int leftMax = getMax(nums, left ,mid);
        int rightMax = getMax(nums, mid+1, right);
        int crossMax = getCrossMax(nums, left, right);
        return Math.max(Math.max(leftMax,rightMax),crossMax);
    }
    //最大子序列在中间时
    private int getCrossMax(int[] nums, int left, int right){
        int mid = left + (right - left)/2;
        //从中间往左边走
        int leftSum = nums[mid];
        int leftMax = leftSum;
        for (int i = mid-1; i >= left; i--){
            leftSum += nums[i];
            leftMax = Math.max(leftMax,leftSum);
        }
        //从中间往右边走
        int rightSum = nums[mid+1];
        int rightMax = rightSum;
        for (int i = mid+2; i <= right; i++){
            rightSum += nums[i];
            rightMax = Math.max(rightMax,rightSum);
        }
        return leftMax + rightMax;
    }
}
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
32
33
34

6、回溯法

一层一层向下递归，尝试搜索答案

（1）找到答案，返回答案，再尝试别的可能

（2）返回上一层递归，尝试别的路径

力扣：78

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

扩展法：一步一步去扩展，加入到前面的集合里

class Solution {
    // Time Complexity: O(N*2^N)
    // Space Complexity: O(N*2^N)
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>()); //[]一定是子集，先加进去
        //nums中的每一个元素加到结果集的每一个子集里
        for (int i: nums) {
            List<List<Integer>> subset = new ArrayList<>();  //存放当前nums扩展成的新的子集
            //将num加入到result集合的每一个数组里
            for (List<Integer> list: result) {
                List<Integer> temp = new ArrayList<>(list);  //新建变量temp，复制result中的每个list，防止引用传递
                temp.add(i);
                subset.add(temp);
            }
            //将添加num后的存放在subset里的元素放回到result
            for (List<Integer> l: subset) {
                result.add(l);
            }
        }
        return result;
    }
}        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

回溯法：

递归，剪枝（去掉不满足条件的）

class Solution {
    // Time Complexity: O(N*2^N)
    // Space Complexity: O(N*2^N)
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());//[]一定是子集，先加进去
        //子集长度范围：0~nums.length,[]已经加入了，从1 开始
        for (int i = 1; i <= nums.length; i++) {
            backtracking(nums, result, i, 0, new ArrayList<>());
        }
        return result;
    }
    //回溯：
    private void backtracking(int[] nums, List<List<Integer>> result, int length, int index, List<Integer> subset) {
        //递归终止条件：剪枝
        if (subset.size() == length) {
            result.add(new ArrayList<>(subset)); //子集复制，避免引用传递
            return;
        }
        //不满足条件是继续向下找，从索引开始往后遍历，避免重复子集
        for(int i = index; i < nums.length; i++) {
            subset.add(nums[i]);
            backtracking(nums, result, length, i+1, subset);
            //删除新加入的值，返回上一层
            subset.remove(subset.size()-1);
        }

    }
}
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

力扣：22

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

右边括号数大于左边括号数，就不是有效的括号组合

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtracking(n, result, 0, 0, "");
        return result;
    }

    private void backtracking(int n, List<String> result, int left, int right, String str){
        //右括号数大于左括号数，不是有效组合直接退出
        if(right > left){
            return;
        }
        //终止条件，生成n对括号
        if(left == n && right == n){
            result.add(str);
            return;
        }
        if( left < n){
            backtracking(n, result, left+1, right, str+"(");
        }
        if(right < left){			//保证右括号数小于左括号数，是有效组合
            backtracking(n, result, left, right+1, str+")");
        }
    }
}
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

7、深度优先搜索

从root节点开始，尽可能深的搜索每一个分支（把一个分支搜索完再去看下一个分支）

应用：二叉树搜索、图搜索、走迷宫

DFS: 递归，一条路走到底，不撞南墙不回头

力扣：78

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

class Solution {
    // Time Complexity: O(N*2^N)
    // Space Complexity: O(N)
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();//定义数组，里面的元素是数组
        dfs(nums, result, 0, new ArrayList<>());
        return result;
    }
    //DFS:
    private void dfs(int[] nums, List<List<Integer>> result, int index, ArrayList<Integer> subset) {
        result.add(new ArrayList<>(subset)); //每一步都形成子集，复制一份加入结果集
        //递归终止条件
        if (nums.length == index) {
            return;
        }
        //未终止继续向下走
        for (int i = index; i < nums.length; i++) {
            subset.add(nums[i]);          //加入nums里的数形成新的子集
            dfs(nums, result, i+1, subset); //下一层DFS从索引之后开始，从当前开始会重复，出现[1,1]或者[2,1]
            subset.remove(subset.size()-1); //删除加入的元素再返回上层递归
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

补充：DFS和回溯的区别

回溯=DFS+剪枝

力扣78中，回溯法的剪枝条件：子集为空，子集为一个元素（满足条件就剪枝，回溯到上一层，不再向下走），子集为两个元素，子集为三个元素；

力扣：938

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

法1：递归

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if(root == null )  return 0; //节点不存在
        int leftSum = rangeSumBST(root.left, low, high); //左子树符合条件的节点和
        int rightSum = rangeSumBST(root.right, low, high);//右子树符合条件的结点和
        int result = leftSum + rightSum;
        if( root.val >= low && root.val <= high){         //判断根节点是否满足条件
            result += root.val;
        }
        return result;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

法2：BFS

利用栈，删除结点后加入左右孩子结点

class Solution {
    // Time Complexity: O(N)
    // Space Complexity: O(N)
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }
        int result = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (queue.size() > 0) { //栈为空，二叉树全部遍历
            int size = queue.size(); //二叉树一层的元素个数
            while (size > 0) {  //一层遍历完下一次whlie循环进入二叉树下一层
                TreeNode cur = queue.poll();
                if (cur.val >= low && cur.val <= high) {
                    result = result + cur.val;
                }
                if (cur.left != null) {  //左孩子存在则入栈
                    queue.add(cur.left);
                }
                if (cur.right != null) {  //右孩子存在则入栈
                    queue.add(cur.right);
                }
                size--;
            }
        }
        return result;
    }
}
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

力扣：200

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

法1：DFS

找到1，将其上下左右的1同化为0，没有可以同化的；再次移动指针找到下一个1为止

class Solution {
    // DFS
    // R is the row of grid
    // C is the column of grid
    // Time Complexity: O(RC)
    // Space Complexity: O(RC)
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int result = 0;  //岛屿数量
        int row = grid.length;
        int col = grid[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    dfs(grid, i, j, row, col);
                }
            }
        }
        return result;
    }
    private void dfs(char[][] grid, int x, int y, int row, int col) {
        //递归终止条件
        if (x < 0 || y < 0 || x >= row || y >= col || grid[x][y] == '0') {
            return;
        }
        //同化为0，再继续上下左右扫荡
        grid[x][y] = '0';
        dfs(grid, x-1, y, row, col);
        dfs(grid, x+1, y, row, col);
        dfs(grid, x, y-1, row, col);
        dfs(grid, x, y+1, row, col);
    }
}
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
32
33
34
35
36

法2：BFS

思路：找到1，放入队列，将1变为0，再将坐标出队，上下左右扫荡，将1的坐标入队

class Solution {
    // BFS
    // R is the row of grid
    // C is the column of grid
    // Time Complexity: O(RC)
    // Space Complexity: O(RC)
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int result = 0;
        int row = grid.length;
        int col = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    queue.add(new int[]{i,j});
                    grid[i][j] = '0';
                    while (queue.size() > 0) {
                        int[]  cur = queue.poll();
                        int x = cur[0];
                        int y = cur[1];
                        if (x-1 >= 0 && grid[x-1][y] == '1' ) {  //上方元素
                            queue.add(new int[]{x-1, y});
                            grid[x-1][y] = '0';
                        }
                        if (y-1 >= 0 && grid[x][y-1] == '1') {   //左方元素
                            queue.add(new int[]{x, y-1});
                            grid[x][y-1] = '0';
                        }
                        if (x+1 < row && grid[x+1][y] == '1') {   //下方元素
                            queue.add(new int[]{x+1, y});
                            grid[x+1][y] = '0';
                        }
                        if (y+1 < col && grid[x][y+1] == '1') {   //右方元素
                            queue.add(new int[]{x, y+1});
                            grid[x][y+1] = '0';
                        }
                    }
                }
            }
        }
        return result;
    }
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

法3：并查集

并查集：找到共同祖先

Union(x,y)合并x,y为同一个祖先

Find(x):找到x的祖先 x= root[x]

思路：二维数组转换为一维

找到1，将上下左右为1的同化为同一祖先

result= 所有格子数—水域数—同化次数

class Solution {
    // Union Find
    // R is the row of grid
    // C is the column of grid
    // Time Complexity: O(RC)
    // Space Complexity: O(RC)
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        int waters = 0;
        UnionFind uf = new UnionFind(grid);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '0') {
                    waters++;
                } else {
                    int[][] directions = new int[][]{{0,1}, {0, -1}, {1, 0}, {-1, 0}};
                    for (int[] dir : directions) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x >= 0 && y >= 0 && x < row && y < col && grid[x][y] == '1') {
                            uf.union(x*col+y, i*col+j);
                        }
                    }
                }
            }
        }
        return uf.getCount() - waters;
    }
}

class UnionFind {
    private int[] root = null;
    private int count = 0;   //   
    //构造函数，传入网格，转换为一维数组
    public UnionFind(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        count = row * col;
        root = new int[row*col];
        for(int i = 0; i < row*col; i++) {
            root[i] = i;          //用索引表示祖先
        }
    }

    // Find the root of X
    public int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }

    // Union two element into one root
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            root[rootX] = rootY;  //将x的祖先的祖先改为y的祖先
            count--;
        }
    }

    public int getCount() {
        return count;
    }
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

8、宽度优先搜索

应用：二叉树搜索、图搜索

主要思想：层层递进，一层一层遍历

力扣：102二叉树层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。（即逐层地，从左到右访问所有节点）。

class Solution {
    // BFS
    // N is the size of tree
    // Time Complexity: O(N)
    // Space Complexity: O(N)
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        while (q.size() > 0) {
            int size = q.size();
            ArrayList<Integer> list = new ArrayList<>();
            while (size > 0) { //遍历当层所有元素
                TreeNode cur = q.poll();
                list.add(cur.val);
                if (cur.left != null) {
                    q.add(cur.left);
                }
                if (cur.right != null) {
                    q.add(cur.right);
                }
                size--;
            }
            result.add(new ArrayList<>(list));   //复制list进行赋值，避免引用传递
        }
        return result;
    }
}
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
32

法2：DFS

按照层级添加元素

class Solution {
    // DFS
    // N is the size of tree
    // H is the height of tree
    // Time Complexity: O(N)
    // Space Complexity: O(H)
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        dfs(root, result, 0);
        return result;
    }

    private void dfs(TreeNode node, List<List<Integer>> result, int level) {
        if (node == null) {  //终止条件
            return;
        }

        if (level > result.size()-1) {
            result.add(new ArrayList<>());   //添加空数组存放当前层的元素
        }
        result.get(level).add(node.val);
        //左孩子进入下一层
        if (node.left != null) {
            dfs(node.left, result, level+1);
        }
        右孩子进入下一层
        if (node.right != null) {
            dfs(node.right, result, level+1);
        }
    }
}
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
32
33
34

力扣：107

给定一个二叉树，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

法一：BFS

使用链表将每一层的元素数组插入到前面，时间复杂度O(1)

class Solution {
    // BFS
    // N is the size of tree
    // H is the height of tree
    // Time Complexity: O(N)
    // Space Complexity: O(N)
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        LinkedList<ArrayList<Integer>> temp = new LinkedList<>();  //链表

        while (q.size() > 0) {  //进入新的一层
            int size = q.size();
            ArrayList<Integer> list = new ArrayList<>();  //存放当前层的元素
            while (size > 0) {   //同一层
                TreeNode cur = q.poll();
                list.add(cur.val);
                if (cur.left != null) {
                    q.add(cur.left);
                }
                if (cur.right != null) {
                    q.add(cur.right);
                }
                size--;
            }
            temp.addFirst(new ArrayList<>(list));
        }
        result = new ArrayList<>(temp);
        
        return result;
    }
}
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
32
33
34
35
36
37

法二：DFS

结果集反转

class Solution {
    // DFS
    // N is the size of tree
    // H is the height of tree
    // Time Complexity: O(N)
    // Space Complexity: O(H)
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        dfs(root, result, 0);
        Collections.reverse(result);   //结果集反转
        return result;
    }
    private void dfs(TreeNode node, List<List<Integer>> result, int level) {
        if (node == null) {
            return;
        }

        if (level > result.size()-1) {
            result.add(new ArrayList<>());
        }

        result.get(level).add(node.val);
        if (node.left != null) {
            dfs(node.left, result, level+1);
        }
        if (node.right != null) {
            dfs(node.right, result, level+1);
        }
    }
}
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
32
33

9、并查集Union Find及其优化

root根节点

两个方法：

union（x,y）：合并两个元素为同一个根节点

find(x)：找到某个元素的根节点并返回

（1）初始化：

root[] 0 1 2 3 4 5

索引 0 1 2 3 4 5

（2）2的根节点是1，4的根节点是3

root[] 0 1 1 3 3 5

索引 0 1 2 3 4 5

（3）4的根节点为1，此时修改3的根节点

root[] 0 1 1 1 3 5

索引 0 1 2 3 4 5

注：索引与root相同才是根节点

代码模板：

class UnionFind {
    private int[] root = null;
   
    public UnionFind() {    //初始化
        root = new int[row*col];
        for(int i = 0; i < row*col; i++) {
            root[i] = i;          //用索引表示祖先
        }
    }
  // Find the root of X
    public int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return find(root[x]);
    }

    // Union two element into one root
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            root[rootX] = rootY;  //将x的祖先的祖先改为y的祖先
        }
    }
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

力扣：200 岛屿数量

力扣：547 朋友圈

***并查集优化：

Quick Find:

初始：

root[] 0 0 0 3 3

索引 0 1 2 3 4

4与2相连后：

优化前：

root[] 0 0 0 0 3

索引 0 1 2 3 4

优化后：（递归到3那层，顺手将4的根节点改为0）

root[] 0 0 0 0 0

索引 0 1 2 3 4

class UnionFind {
    private int[] root = null;
   
    public UnionFind() {    //初始化
        root = new int[row*col];
        for(int i = 0; i < row*col; i++) {
            root[i] = i;          //用索引表示祖先
        }
    }
  // Find the root of X
    public int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] == find(root[x]);       //优化位置
    }

    // Union two element into one root
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            root[rootX] = rootY;  //将x的祖先的祖先改为y的祖先
        }
    }
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

Quick Union:权重，防止树太高

原理：比较两个树的高，把矮的树连接到高的树上，使树的高度最低

初始：

root[] 0 0 0 3 3 4

索引 0 1 2 3 4 5

3与2相连后：

优化前：树高5层

root[] 0 0 0 2 3 4

索引 0 1 2 3 4 5

优化后：树高三层

root[] 3 0 0 3 3 4

索引 0 1 2 3 4 5

class UnionFind {
    int[] root;
    int[] rank;
   
    public UnionFind() {    //初始化
        root = new int[n];
        rank = new int[n];
        for(int i = 0; i < n; i++) {
            root[i] = i;          //用索引表示祖先
            rank[i] = 0;
        }
    }
  // Find the root of X
    public int find(int x) {
        if (x == root[x]) {
            return root[x];
        }
        return root[x] == find(root[x]);       //优化位置
    }

    // Union two element into one root
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if(rank[rootX] > rank[rootY]){
            	root[rootY] = rootX;
            }else if(rank[rootX] < rank[rootY]){
            	root[rootX] = rootY;
            }else{
            	root[rootY] = rootX;
            	rank[rootX] += 1;
            }
        }
    }
}
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
32
33
34
35
36

10、贪心算法

核心：每一步做出的选择都是当前看起来最好的选择

	  只是局部最优解，而不是整体最优解
1

大问题分解为小问题，找到每个小问题的最优解，进行合并，找到最后的答案

例题：零钱兑换

力扣： 322 零钱兑换

力扣： 1217 玩筹码

力扣： 55 跳跃游戏

11、算法记忆化（备忘录）技巧

目的：减少重复计算

用数组记录递归过程中的中间值

力扣：509 斐波那契数列

力扣： 322 零钱兑换

12、动态规划

初始状态：

方程式：状态转移

终止状态：

应用：

（1）计数：有多少种方法/方式

机器人从左上角到右下角有多少路径

（2）求最值：最大值/最小值

机器人从左到右的路径的最大数字和

（3）求存在性：是否存在某个可能

是否存在机器人从左到右的路径

力扣：509 斐波那契数列

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
1
2

class Solution {
    public int fib(int n) {  
        if( n < 2){
            return n ==1? 1: 0;
        } 
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i < n+1; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];    
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

力扣：62 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for(int i = 0; i < m; i++){
            for(int j = 0;j < n; j++){
                if(i-1 >= 0 && i-1 < m){        //左边各自有效
                    dp[i][j] =  dp[i][j] +  dp[i-1][j];
                }
                if(j-1 >= 0 && j-1 < n){        //右边格子有效
                    dp[i][j] =  dp[i][j] +  dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

力扣：121 买卖股票的最佳时机

力扣：70 爬楼梯

力扣：279 完全平方数

位运算
符号描述运算规则
& 与两个位都为1时，结果才为1
| 或两个位都为0时，结果才为0
^ 异或两个位相同为0，相异为1
~ 取反 0变1，1变0
<< 左移各二进位全部左移若干位，高位丢弃，低位补0

右移各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

char类型的运算对象首先提升成int型，提升时原来位保持不变，高位补零。

1.栈

（1）声明

Stack <Integer> stack1;
1

（2）初始化

stack1 = new Stack();
1

（3）插入

stack1.push(value);
1

（4）删除

stack1.pop();
1

（5）判空

stack1.isEmpty();
!stack1.isEmpty();
1
2

注：声明要在外面，初始化和插入删除操作才能进行

2.链表

1）声明

ListNode pre = head, cur = head.next;
1

（2）初始化

ListNode pre = head, cur = head.next;
1

（3）插入

（4）删除

pre.next = cur.next;
1

（5）判空

cur != null 空节点
cur.val   取值
1
2

（6）返回

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

public ListNode deleteNode(ListNode head, int val) {
        if(head.val == val) return head.next;
        ListNode pre = head, cur = head.next;
        while(cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }
        if(cur != null) pre.next = cur.next;
        return head;
    }
1
2
3
4
5
6
7
8
9
10

//返回从倒数k个节点开始的链表
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode former = head, latter = head;
        for(int i = 0; i < k; i++)
            former = former.next;
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

//链表翻转
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, pre = null;
        while(cur != null) {
            ListNode tmp = cur.next; // 暂存后继节点 cur.next
            cur.next = pre;          // 修改 next 引用指向
            pre = cur;               // pre 暂存 cur
            cur = tmp;               // cur 访问下一节点
        }
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.字符串

//取字符串中的i索引的字符
char temp = s.charAt(i);
//初始化：
String[] a = {"abc123","abc+1234","ababab--1"}
//字符串长度
a[i].length()
//字符串字母个数，数字个数
for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < a[i].length(); j++) {
        if (a[i].charAt(j)<='z' && a[i].charAt(j)>='a'){
             zimu++;
        }
        if (a[i].charAt(j)>='0' && a[i].charAt(j)<='9'){
             shuzi++;
        }
}
//按照字母个数降序排列
for (int i = 0; i < b.length - 1; i++) {
     if (a[i].compareTo(a[i+1])<0){
          String temp = a[i];
          a[i] = a[i+1];
          a[i+1] = temp;
      }
}
//打印数组的全部值
System.out.println(Arrays.toString(a));
[ababab--1, abc123, abc+1234]
//
使用String.toCharArray()方法将字符串转为字符数组
Scanner input = new Scanner(System.in);
String str = input.next();
char ss[] = str.toCharArray(); //利用toCharArray方法转换
for (int i = 0; i < ss.length; i++) {
    System.out.println(ss[i]);
}
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
32
33
34
35

4.数组

数组声明初始化

int[] result = new int[n];
1

数组长度

result.length
result[i].length()
1
2

5.斐波那契数列

斐波那契数列输出第n个

class Solution {
    public int fib(int n) {
        if(n < 2) return n;
        long[] result = new long[n+1];
        result[0] = 0;
        result[1] = 1;
        for(int i =2;i <= n;i++){
            result[i]=result[i-1]+result[i-2];
            result[i] %= (Math.pow(10,9) +7);
        }
        return (int)result[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

注：答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

result[i] %= (Math.pow(10,9) +7);
1

青蛙跳台阶

class Solution {
    public int numWays(int n) {
       if (n <= 1)
            return 1;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            dp[i] %= 1000000007;
        }
        return dp[n];  
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

6.（二分查找）数组旋转

排序数组的查找问题首先考虑使用 二分法 解决，其可将 遍历法 的 线性级别 时间复杂度降低至 对数级别

class Solution {
    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;
        if(right == 0){
            return number[0];
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (numbers[mid] < numbers[right]) {
                right = mid;
            } else if (numbers[mid] > numbers[right]) {
                left = mid + 1;
            } else {
                right -= 1;
            }
        }
        return numbers[left];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

7.矩阵搜索问题

可使用深度优先搜索（DFS）+ 剪枝解决。

深度优先搜索：可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝：在搜索中，遇到这条路不可能和目标字符串匹配成功的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为可行性剪枝。

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if(k == word.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        board[i][j] = word[k];//回溯返回时还原原始矩阵
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

机器人行走问题

方法一：深度优先遍历 DFS
深度优先搜索：可以理解为暴力法模拟机器人在矩阵中的所有路径。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝：在搜索中，遇到数位和超出目标值、此元素已访问，则应立即返回，称之为可行性剪枝。
算法解析：
递归参数：当前元素在矩阵中的行列索引 i 和 j ，两者的数位和 si, sj 。
终止条件：当 ① 行列索引越界或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过时，返回 00 ，代表不计入可达解。
递推工作：
标记当前单元格：将索引 (i, j) 存入 Set visited 中，代表此单元格已被访问过。
搜索下一单元格：计算当前元素的下、右两个方向元素的数位和，并开启下层递归。
回溯返回值：返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数。

class Solution {
    int m, n, k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        this.m = m; this.n = n; this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }
    public int dfs(int i, int j, int si, int sj) {
        if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二：广度优先遍历 BFS
BFS/DFS ：两者目标都是遍历整个矩阵，不同点在于搜索顺序不同。DFS 是朝一个方向走到底，再回退，以此类推；BFS 则是按照“平推”的方式向前搜索。
BFS 实现：通常利用队列实现广度优先遍历。
算法解析：
初始化：将机器人初始点 (0, 0)(0,0) 加入队列 queue ；
迭代终止条件： queue 为空。代表已遍历完所有可达解。
迭代工作：
单元格出队：将队首单元格的索引、数位和弹出，作为当前搜索单元格。
判断是否跳过：若 ① 行列索引越界或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过时，执行 continue 。
标记当前单元格：将单元格索引 (i, j) 存入 Set visited 中，代表此单元格已被访问过。
单元格入队：将当前元素的下方、右方单元格的索引、数位和加入 queue 。
返回值： Set visited 的长度 len(visited) ，即可达解的数量。

class Solution {
    int m, n, k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        this.m = m; this.n = n; this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }
    public int dfs(int i, int j, int si, int sj) {
        if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

7.数位之和

数位之和计算：

int sums(int x)
    int s = 0;
    while(x != 0) {
        s += x % 10;
        x = x / 10;
    }
    return s;
1
2
3
4
5
6
7

8.剪绳子

思路一：动态规划
这题用动态规划是比较好理解的

我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而来
用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积，也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积，初始化dp[2] = 1
我们先把绳子剪掉第一段（长度为j），如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪
剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话长度乘积即为j * (i - j)；如果剪的话长度乘积即为j * dp[i - j]。取两者最大值max(j * (i - j), j * dp[i - j])
第一段长度j可以取的区间为[2,i)，对所有j不同的情况取最大值，因此最终dp[i]的转移方程为
dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
最后返回dp[n]即可

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i < n + 1; i++){
            for(int j = 2; j < i; j++){
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

8.二进制中1的个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0){
            res += n & 1; //末尾是否为1
            n >>>= 1;//无符号右移
            
            //res++;
            //n &= n - 1;//消除末尾再付给n
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

笔试真题

1. 计算题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cqG1IJ9T-1637024154157)(力扣刷题Java.assets/image-20210906194405760.png)]

public class test01 {
    public static void main(String[] args) {
        double[] raw_data = {22.1, 22.3, 22.4, 22.7, 22.0, 24.0, 25.0, 27.0, 28.0, 27.0, 29.0, 27.0, 26.0, 25.0, 24.0, 24.0, 23.0, 21.0, 20.0, 22.0};
        int k=5;
        int n = raw_data.length;
        float[] result = new float[n-k+1];
        for (int i = 0; i < n-k+1; i++) {
            for (int j = i; j-i < k; j++) {
                result[i] += raw_data[j];
            }
            result[i] = result[i] / k;
        }
        System.out.println(Arrays.toString(result));
    }
}

[22.3, 22.68, 23.22, 24.14, 25.2, 26.2, 27.2, 27.6, 27.4, 26.8, 26.2, 25.2, 24.4, 23.4, 22.4, 22.0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.别人的答案：

public class demo1 {
    static public Float[] getKAverage(Float[] raw_data,int K){
        int len = raw_data.length;
        Float[] result = new Float[len-K+1];
        for (int i = 0; i < (len - K + 1); i++) {
            float sum = 0;
            float temp = 0;
            for (int j = i; j < i + K; j++) {
                sum += raw_data[j];
            }
            temp = sum/K;
            result[i] = temp;
        }
        return result;
    }

    public static void main(String[] args) {
        Float[] raw_data = {22.1f,22.3f,22.4f,22.7f,22.0f,24.0f,25.0f,27.0f,28.0f,27.0f,29.0f,27.0f,26.0f,25.0f,24.0f,24.0f,23.0f,21.0f,20.0f,22.0f};
        int K = 5;
        System.out.println(raw_data.length);
        Float[] result = getKAverage(raw_data,K);
        System.out.println(Arrays.toString(result));
    }
}


20
[22.3, 22.679998, 23.22, 24.14, 25.2, 26.2, 27.2, 27.6, 27.4, 26.8, 26.2, 25.2, 24.4, 23.4, 22.4, 22.0]
    
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

2.二维字符串数组[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KkszViIt-1637024154162)(力扣刷题Java.assets/image-20210906193504418.png)]

public class test02 {
    public static void main(String[] args) {
        String[] Rel_Matrix = {"5,3,4,2,3","1,5,2,2,3","3,2,5,2,1","1,4,2,5,2","1,2,3,1,5"};
        int result = findBestMan(Rel_Matrix);
        System.out.println(result);
    }

    public static int findBestMan(String[] Rel_Matrix){

        int m = Rel_Matrix.length;
        int n =Rel_Matrix[0].split(",").length;
        int[] total = new int [m];
        int max = Integer.MIN_VALUE;
        //统计每个人的支持度
        for(int i =0; i< m;i++){
            int sum = 0;
            for(int j = 0;j < n;j++){
                int k = i;
                sum += Integer.parseInt(Rel_Matrix[j].split(",")[k]);
            }
            total[i]=sum;
        }
        //遍历获取最大的支持度
        int result =0;
        for(int i =0; i < m;i++){
            if(total[i]>max){
                max = total[i];
                result = i;
            }

        }
        return result;

    }
}
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
32
33
34
35

输出：
1
1
2

2.别人的答案

public class demo02 {
    static public int findBestMan(String[] Rel_Matrix){
        int rows = Rel_Matrix.length;
        int cols = Rel_Matrix[0].split(",").length;
        int[] count = new int[rows];
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < rows; i++) {
            int sum = 0;
            for (int j = 0; j < cols; j++) {
                sum += Integer.parseInt(Rel_Matrix[i].split(",")[j]);
            }
            count[i] = sum;
        }
        System.out.println(Arrays.toString(count));
        // 找出最大的值
        for (int coun : count) {
            max = Math.max(coun,max);
        }
        // 数组下标为用户，对应的元素为她的支持度，返回第一个等于max即可
        for (int i = 0; i < rows; i++) {
            if (count[i] == max){
                return i+1;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        String[] Rel_Matrix = {"5,3,4,2,3","1,5,2,2,3","3,2,5,2,1","1,4,2,5,2","1,2,3,1,5"};
        int result = findBestMan(Rel_Matrix);
        System.out.println(result);
    }
}
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
32
33
34

3.排序并输出

public class test03 {
    public static String[] scoresort(String[] names,String[] scores) {
        String[] result = new String[names.length];
        int[] count = new int[scores.length];
        int index = 0;
        //统计总分
        int m = scores.length;
        int n = scores[0].split(",").length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++)
                count[i] += Integer.parseInt(scores[i].split(",")[j]);
        }
        System.out.println(Arrays.toString(count));
        //进行排序
        for (int i = 0; i < count.length; i++) {
            for (int j = i+1; j < count.length; j++) {
                if (count[i] < count[j]){
                    int temp1 = count[i];
                    count[i] = count[j];
                    count[j] = temp1;

                    String temp2 = names[i];
                    names[i] = names[j];
                    names[j] = temp2;

                }
            }

        }
        System.out.println(Arrays.toString(count));
        return names;
    }
    public static void main(String[] args) {
        String[] names = {"王飞","刘洋","李丽"};
        String[] scores = {"89,92,90,88,91","92,96,81,90,92","89,91,91,78,97"};
        String[] result = scoresort(names,scores);
        System.out.println(Arrays.toString(result));
    }
}

输出：
    [450, 451, 446]
	[451, 450, 446]
	[刘洋, 王飞, 李丽]
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
32
33
34
35
36
37
38
39
40
41
42
43
44

4.数字加密

大意如下：控制台输入num为四位数，对其按照如下的规则进行加密：

1、每一位分别加5，然后分别将其替换为该数除以10取余后的结果

2、将该数的第1位和第4为互换，第二位和第三位互换

3、最后合起来作为加密后的整数输出

例如：输入：1000，输出：5556

时间限制：1s 内存限制：16MB

package com.ting;

import java.util.Scanner;

public class main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String numStr = in.next();
        char[] c = numStr.toCharArray();
        int[] temp = new int[c.length];
        for(int i =0;i<temp.length;i++){
            temp[i] = c[i]-'0';
            System.out.println(temp[i]);
            temp[i] = (temp[i]+5)%10;
        }
        int t = 0;
        t = temp[0];
        temp[0]=temp[3];
        temp[3] = t;
        
        t = temp[1];
        temp[1]=temp[2];
        temp[2] = t;
        String s1 = "";
        StringBuffer sb = new StringBuffer(s1);
        for(int i= 0;i<temp.length;i++){
            sb.append(temp[i]);
        }
        String sb2 = sb.toString();
        System.out.println(sb2);

    }
}
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
32
33

int a = 100000;
String str = String.valueOf(a);
String[] strArray = str.split("");
Integer[] intArray = new Integer[strArray.length];
for(int i = 0; i < strArray.length ; i++){
    intArray[i] = (Integer.valueOf(strArray[i]) + 5) % 10;
}
StringBuilder newStr = new StringBuilder();
for (int i = 0; i < intArray.length / 2; i++) {
    if(intArray.length - 1 - i == i){
        break;
    }
    intArray[i] = intArray[i] + intArray[intArray.length - 1 - i];
    intArray[intArray.length - 1 - i] = intArray[i] - intArray[intArray.length - 1 - i];
    intArray[i] = intArray[i] - intArray[intArray.length - 1 - i];
}
for(int i : intArray){
    newStr.append(i);
}
System.out.println(newStr.toString());
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

5.句子按单词排序输出

题目描述：

对输入的单词进行字典序排序输出：字典序定义：1. 单词中字母比较不区分大小写，两个单词先以第一个字母作为排序的基准，如果第一个字母相同，就用第二个字母为基准，如果第二个字母相同就以第三个字母为基准。依此类推，如果到某个字母不相同，字母顺序在前的那个单词顺序在前。 2. 当一个短单词和一个长单词的开头部分都相同（即短单词是长单词从首字母开始的一部分），短单词顺序在前。 3. 字母大小写不同的相同单词，只输出一次。

输入描述：

不超过255个字符中,单词间用空格进行分隔，为简单起见，单词不包含连字符，无其它标点符号。

输出描述：

输出排序后的单词，单词之间用空格隔开（最后不带空格），重复的单词只输出一次。

package com.java1;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

//字典排序，采用插入排序的方法
     public static List<String> sort(String strword){//strword输入的句子
         int length = strword.length();
         int k =0;
         List sortedList = new ArrayList();

         for(int i = 0;i<length;i++){
             if((strword.charAt(i)-' ') ==0){
                 String word = strword.substring(k, i);
                 addAword(sortedList,word);
                 k=i+1;
             }
         }
         return sortedList;
     }

//插入排序实现:每次插入的单词与列表的单词进行比较
     public static void addAword(List<String> sortedList,String word){//word切割后每次添加的单词
         if(word == null || word.length()==0){
             return;
         }
         String temp = word;
         boolean bigger = false;
         for(int i=0;i<sortedList.size();i++){
             String slword = sortedList.get(i);
             if(bigger || compare(word,slword)<0){
                 sortedList.set(i, temp);
                 temp = slword;
                 bigger = true;
             }else if(!bigger && compare(word,slword) == 0){
                 return;
             }//else if 去除重复单词
         }
         sortedList.add(temp);
     }

//单词比较
     public static int compare(String str1,String str2){
         int length1 = str1.length();
         int length2 = str2.length();

         int limit = Math.min(length1, length2);

         char a[] = str1.toCharArray();
         char b[] = str2.toCharArray();

         for(int i = 0;i<limit;i++){
             char c1 = (char) (a[i]>='a'?a[i]:(a[i]+32));
             char c2 = (char) (b[i]>='a'?b[i]:(b[i]+32));
             if(c1 != c2){
                 return c1-c2;
             }
         }
         return length1-length2;
     }
//主函数
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         String s = sc.nextLine();
         List<String> resultList = sort(s);
         for(int i = 0;i<resultList.size();i++){
             if(i == resultList.size()-1){
                 System.out.print(resultList.get(i));
                 break;
             }
             System.out.print(resultList.get(i) + " ");
         }
     }
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

6、6 = {1,2,4} 10 = {1,2,4,8}

package com.java1;

/**
 * @auther xiaoting
 * @create 2021-09-24  21:17
 */
public class test0924 {
    private int fun(int n){
        int sum=0;//开始到当前位置所有数字的和。
        int num=0;//添加的数字个数。
        int i=1;
        while(sum<n){
            if(i>=n)
                break;
            if(sum<i){
                System.out.println("sum="+sum+" add:\t"+i);
                sum+=i++;
                num++;
            }else{
                int tmp=sum+1;
                System.out.println("sum="+sum+" add:\t"+tmp);
                sum+=tmp;
                num++;
                i++;
            }
        }
        return num;
    }
    public static void main(String[] args) {
        System.out.println("n=10 => min="+new test0924 ().fun(10));
    }

}

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
32
33
34

7、s中查找k个字符串中有重复字符的个数（set,list都可以）

package com.java1;

import java.util.*;

/**
 * @auther xiaoting
 * @create 2021-09-24  18:20
 */
public class test02 {
    public static void main(String[] args) {
        String s = "createfunonyoka";
        int k =4;
        int result = numKLenSubstrNoRepeats(s,k);
        System.out.println(result);
    }

    public static int numKLenSubstrNoRepeats(String s, int k) {
        int n = s.length(); // 字符串的长度
        List<Character> list = new ArrayList<>();
        int ane = 0;  // 返回符合要求的子串数目
        boolean flag = false;
        for(int i =0; i < n; i++){
            for(int j =i;(j-i) < k&&j < n; j++){ //遍历k次，判断长度为k的子串是否包含重复字符
                if(!list.contains(s.charAt(j))){
                    list.add(s.charAt(j));
                }else{
                    flag = true;
                }
            }
            if(flag){//包含重复字符，标志flag为true
                ane++;
            }
            list.clear();//清空set集合
            flag = false;//重置标志
        }
        return ane;
    }
}
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
32
33
34
35
36
37
38

null || word.length()==0){
return;
}
String temp = word;
boolean bigger = false;
for(int i=0;i<sortedList.size();i++){
String slword = sortedList.get(i);
if(bigger || compare(word,slword)<0){
sortedList.set(i, temp);
temp = slword;
bigger = true;
}else if(!bigger && compare(word,slword) == 0){
return;
}//else if 去除重复单词
}
sortedList.add(temp);
}

//单词比较
public static int compare(String str1,String str2){
int length1 = str1.length();
int length2 = str2.length();

     int limit = Math.min(length1, length2);

     char a[] = str1.toCharArray();
     char b[] = str2.toCharArray();

     for(int i = 0;i<limit;i++){
         char c1 = (char) (a[i]>='a'?a[i]:(a[i]+32));
         char c2 = (char) (b[i]>='a'?b[i]:(b[i]+32));
         if(c1 != c2){
             return c1-c2;
         }
     }
     return length1-length2;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

//主函数
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
List resultList = sort(s);
for(int i = 0;i<resultList.size();i++){
if(i == resultList.size()-1){
System.out.print(resultList.get(i));
break;
}
System.out.print(resultList.get(i) + " ");
}
}
}


## 6、6 = {1,2,4} 10 = {1,2,4,8}

1
2
3

package com.java1;

/**

@auther xiaoting
@create 2021-09-24 21:17
*/
public class test0924 {
private int fun(int n){
int sum=0;//开始到当前位置所有数字的和。
int num=0;//添加的数字个数。
int i=1;
while(sum<n){
if(i>=n)
break;
if(sum<i){
System.out.println(“sum=”+sum+" add:\t"+i);
sum+=i++;
num++;
}else{
int tmp=sum+1;
System.out.println(“sum=”+sum+" add:\t"+tmp);
sum+=tmp;
num++;
i++;
}
}
return num;
}
public static void main(String[] args) {
System.out.println(“n=10 => min=”+new test0924 ().fun(10));
}

}


7、s中查找k个字符串中有重复字符的个数（set,list都可以）

1
2
3

package com.java1;

import java.util.*;

/**

@auther xiaoting
@create 2021-09-24 18:20
*/
public class test02 {
public static void main(String[] args) {
String s = “createfunonyoka”;
int k =4;
int result = numKLenSubstrNoRepeats(s,k);
System.out.println(result);
}

public static int numKLenSubstrNoRepeats(String s, int k) {
int n = s.length(); // 字符串的长度
List list = new ArrayList<>();
int ane = 0; // 返回符合要求的子串数目
boolean flag = false;
for(int i =0; i < n; i++){
for(int j =i;(j-i) < k&&j < n; j++){ //遍历k次，判断长度为k的子串是否包含重复字符
if(!list.contains(s.charAt(j))){
list.add(s.charAt(j));
}else{
flag = true;
}
}
if(flag){//包含重复字符，标志flag为true
ane++;
}
list.clear();//清空set集合
flag = false;//重置标志
}
return ane;
}
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/87279