自己实现一个HashMap
- 代码：```java
import java.lang.reflect.Array; import java.util.*;
/**
- 实现一个简单的hashMap 用拉链法解决hash冲突
- @param
@param
*/ class MyHashMap return key==null?0:key.hashCode();
} //查询 public V get(Object key){
int hash = getHash(key); Node<K,V> e; return (e = getNode(hash,key))==null?null:e.value;}
public Node
int index = hash&(size-1); if(table[index]==null){ return null; } //若当前位置已经有元素了，就遍历链表 Node<K,V> first = table[index]; while(first!=null){ if(first.hash==hash&&first.key==key){ //先比较hash值是否相同，若相同再比较key是否相同 return first; }else{ first = first.next; } } return null;} //插入 没有考虑扩容等复杂逻辑 public void put(Object key,Object value){
putNode(getHash(key),key,value);}
private void putNode(int hash, Object key, Object value) {
int index = hash & (size-1); Node<K, V> first = table[index]; Node<K,V> node = new Node(key,value,hash); //若桶数组当前位置为空就直接插入 if(first==null){ table[index] = node; }else{ //遍历链表，寻找插入位置 while(first.next!=null){ //若找到key相同的节点就进行覆盖 if(first.hash==hash&&first.key==key){ first = node; }else{ first = first.next; } } //遍历到链表尾直接插入 first.next = node; } size++; //扩大容量}
//删除 public V remove(Object key){
Node<K, V> e; return (e=removeNode(getHash(key),key))==null?null:e.value;}
private Node
int index = hash & (size-1); Node<K, V> first = table[index]; Node<K,V> node= null; //返回值 Node<K,V> prev = null; if(first.hash==hash&&first.key==key){ node = first; }else { //寻找待删除的节点 while (first.next != null) { if (first.hash == hash && first.key == key) { node = first; break; } else { first = first.next; } prev = first; } } if(node==table[index]){ table[index] = node.next; }else{ prev.next = node.next; } return node;}
}
class Node
public static void main(String[] args) {
}
}
<a name="e43b1bcf"></a>
#### 实现三个线程交替打印ABC
- 思路：reentrantlock的condition实现选择性通知
- 代码：```java
public class TestLock {
ReentrantLock lock = null;
Condition condA,condB,condC;
private volatile int number; //共享变量控制线程顺序
public TestLock(){
lock = new ReentrantLock();
condA = lock.newCondition();
condB = lock.newCondition();
condC = lock.newCondition();
number = 1;
}
public void printA() throws InterruptedException {
try{
lock.lock();
while(number!=1){
condA.await();
}
System.out.println(Thread.currentThread().getName()+" A");
number = 2;
condB.signalAll(); //唤醒B
}catch (Exception e){
e.printStackTrace();
}finally {
lock.unlock();
}
}
public void printB() throws InterruptedException {
try{
lock.lock();
while(number!=2){
condB.await();
}
System.out.println(Thread.currentThread().getName()+" B");
condC.signalAll(); //唤醒B
number = 3;
}catch (Exception e){
e.printStackTrace();
}finally {
lock.unlock();
}
}
public void printC() throws InterruptedException {
try{
lock.lock();
while(number!=3){
condC.await();
}
System.out.println(Thread.currentThread().getName()+" C");
condA.signalAll(); //唤醒A
number = 1;
}catch (Exception e){
e.printStackTrace();
}finally {
lock.unlock();
}
}
public static void main(String[] args) {
TestLock t = new TestLock();
//每个线程都来了5轮，打印ABC
new Thread(()->{
for (int i = 0; i < 5; i++) {
try {
t.printA();
} catch (Exception e) {
e.printStackTrace();
}
}
},"线程1").start();
new Thread(()->{
for (int i = 0; i < 5; i++) {
try {
t.printB();
} catch (Exception e) {
e.printStackTrace();
}
}
},"线程2").start();
new Thread(()->{
for (int i = 0; i < 5; i++) {
try {
t.printC();
} catch (Exception e) {
e.printStackTrace();
}
}
},"线程3").start();
}
}
实现LRU缓存机制
- 思路：HashMap+双向链表
- HashMap存储结点在双向链表中的位置，方便查找。双向链表便于删除和插入。
- 双向链表的头部是最近使用的结点，尾部是最久未使用的结点。
- get操作分析
- 判断键值是否存在，若不存在则返回-1.
- 否则查询到该键值在双向链表中的位置，删除该结点，并插入到头部。
- put操作分析
- 判断键值是否存在，若不存在则新建一个结点，将其插入到双向链表头部，并在map中添加。
- 若链表长度大于规定长度，则删除尾部结点，并删除map中对应结点。
- 否则查询到该键值在双向链表中的位置，删除该结点，并插入到头部。
- 代码:```java import java.util.HashMap; import java.util.Map;
public class LRUCache {
class ListNode{
int key;
int value;
ListNode prev;
ListNode next;
public ListNode(){ }
public ListNode(int key,int value){
this.key = key;
this.value = value;
}
}
Map
public int get(int key){
ListNode node = cache.get(key);//从map中获取结点
if(node==null) return -1;
deleteNode(node);
insertToHead(node);
return node.value;
}
public void put(int key,int value){
ListNode node = cache.get(key);
if(node==null){
ListNode newNode = new ListNode(key,value);
insertToHead(newNode);
cache.put(key,newNode);
//判断是否超出容量
if(cache.size()>capacity){
//删除最后一个结点
ListNode tail = removeTail();
cache.remove(tail.key);
}
}else{
node.value = value;//更新value值
deleteNode(node);
insertToHead(node);
}
}
public ListNode removeTail(){
ListNode node = tail.prev;
deleteNode(node);
return node;
}
public void deleteNode(ListNode node){
node.prev.next = node.next;
node.next.prev = node.prev;
}
public void insertToHead(ListNode node){
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
public static void main(String[] args) {
LRUCache cache = new LRUCache(3);
cache.put(1,1);
cache.put(2, 2);
cache.put(3, 3);
cache.put(4, 4);
System.out.println(cache.get(4));
System.out.println(cache.get(3));
System.out.println(cache.get(2));
System.out.println(cache.get(1));
cache.put(5, 5);
System.out.println(cache.get(1));
System.out.println(cache.get(2));
System.out.println(cache.get(3));
System.out.println(cache.get(4));
System.out.println(cache.get(5));
}
}
- linkedHashMap实现
- ```java
public class LRUCache extends LinkedHashMap<Integer,Integer> {
private int capacity;
public LRUCache(int capacity){
super(capacity,0.75F,true);
this.capacity = capacity;
}
public int get(int key){
return super.getOrDefault(key,-1);
}
public void put(int key,int value){
super.put(key,value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size()>capacity;
}
public static void main(String[] args) {
LRUCache cache = new LRUCache(3);
cache.put(1,1);
cache.put(2, 2);
cache.put(3, 3);
cache.put(4, 4);
System.out.println(cache.get(4));
System.out.println(cache.get(3));
System.out.println(cache.get(2));
System.out.println(cache.get(1));
cache.put(5, 5);
System.out.println(cache.get(1));
System.out.println(cache.get(2));
System.out.println(cache.get(3));
System.out.println(cache.get(4));
System.out.println(cache.get(5));
}
}
日志登入和登出
- 然后一个动态规划题，给你一个日志文件，上面有每个用户登录登出时刻，求每一时刻同时在线的人数 (时间粒度为秒)
logs[] = [[1,0,1],[2,2,3],[3,0,5]] 日志格式 是 uid,login_time,logout_time ，要求算法时间复杂度为O(n)- 时间以秒为单位,则一共有 24*3600=86400秒 int delta[86400],存储人数变化
- 遍历每条记录,在delta数组中将登录时间对应的整数值+1,登出时间对应的整数值-1.
- dp[n] = dp[n-1]+delta[n];
- 代码:```java
public static int[] onlineNum(int[][] logs){
}int n = logs.length; //人数 //时间以秒为单位，定义一个大数组，存放每个时刻变化的人数 int[] matrix = new int[3600*24]; //遍历日志文件 for(int i=0;i<n;i++){ matrix[logs[i][1]]++; //登录，人数+1 matrix[logs[i][2]]--;//登出，人数-1 } //使用动态规划计算 int[] dp = new int[3600*24];//存放到当前时刻为止的在线人数 for(int i=0;i<matrix.length;i++){ if(i==0) dp[i] = matrix[i]; else { dp[i] = dp[i - 1] + matrix[i]; //上一时刻的人数+变化量 } } return dp;
public static void main(String[] arg){
int[][] logs = {{1,0,1},{2,2,3},{3,0,5}};
int[] dp = onlineNum(logs);
System.out.println(Arrays.toString(dp));
}
<a name="e99ccc3e"></a>
#### 手写单例模式 DCL懒汉
- 代码```java
public class SingleDemo {
private static volatile SingleDemo instance;
private SingleDemo(){
System.out.println(Thread.currentThread().getName()+"执行构造函数");
}
public static SingleDemo getInstance(){
if(instance==null){
//锁类对象
synchronized (SingleDemo.class){
if(instance==null){
instance = new SingleDemo();
}
}
}
return instance;
}
public static void main(String[] args){
for(int i=0;i<10;i++){
new Thread(()->{
System.out.println(SingleDemo.getInstance());
},String.valueOf(i+1)).start();
}
}
}
静态内部类实现单例模式
import java.util.*;
public class Main {
private Main(){
}
public static Main getInstance(){
return Singleton.instance;
}
static class Singleton{
private static Main instance = new Main();
}
}
生产者消费者模型
- 代码1：```java
/**
- 生产者消费者模型，阻塞队列实现 */
class Resource{
private volatile boolean FLAG = true;//标志位，开启或关闭 生产+消费
private AtomicInteger count = new AtomicInteger();
private BlockingQueue
public Resource(BlockingQueue<String> queue){
this.queue = queue;
System.out.println(queue.getClass().getName());//打印全类名
}
public void provider() throws Exception {
boolean result;
String data;
while(FLAG==true){
data = count.getAndIncrement()+"";
result = queue.offer(data, 2L, TimeUnit.SECONDS);
if(result){
System.out.println(Thread.currentThread().getName()+"生产"+data+"成功");
}else{
System.out.println(Thread.currentThread().getName()+"生产"+data+"失败");
}
Thread.sleep(1000);
}
System.out.println("生产线程停下");
}
public void consumer() throws Exception {
String result;
while(FLAG){
result = queue.poll(2L,TimeUnit.SECONDS);
if(result==null){
System.out.println("队列为空");
return;
}else{
System.out.println(Thread.currentThread().getName()+"消费"+result+"成功");
}
}
System.out.println("消费线程停下");
}
public void stop(){
FLAG = false;
}
}
public class MyCache {
public static void main(String[] args) throws InterruptedException {
Resource resource = new Resource(new ArrayBlockingQueue
//生产者
new Thread(()->{
try {
resource.provider();
} catch (Exception e) {
e.printStackTrace();
}
},"provider").start();
//消费者
new Thread(()->{
try {
resource.consumer();
} catch (Exception e) {
e.printStackTrace();
}
},"comsumer").start();
TimeUnit.SECONDS.sleep(5);
resource.stop();
}
}
- 代码2：```java
/**
* ReentrantLock实现生产者消费者队列
*/
class Resource1{
private volatile int number;
private int capacity;
private ReentrantLock lock;
//使用condition可以实现定向通知，一个线程一个condition
private Condition conditionProvider;
private Condition conditionConsumer;
public Resource1(int capacity){
this.capacity = capacity;
lock = new ReentrantLock();
conditionProvider = lock.newCondition();
conditionConsumer = lock.newCondition();
}
public void provider(){
try {
lock.lock();
//满了就阻塞
while (number >= capacity) {
conditionProvider.await();
}
number++;
System.out.println(Thread.currentThread().getName()+"进行生产，总共"+number);
//唤醒所有消费者线程
conditionConsumer.signalAll();
}catch (Exception e){
e.printStackTrace();
}finally {
lock.unlock();
}
}
public void consumer(){
try {
lock.lock();
//空了就阻塞
while (number<=0) {
conditionConsumer.await();
}
number--;
System.out.println(Thread.currentThread().getName()+"进行消费，总共"+number);
//唤醒所有生产者线程
conditionProvider.signalAll();
}catch (Exception e){
e.printStackTrace();
}finally {
lock.unlock();
}
}
}
public class MyCache1 {
public static void main(String[] args) {
Resource1 resource1 = new Resource1(1);
new Thread(()->{
for(int i=0;i<10;i++){
resource1.provider();
}
},"provider").start();
new Thread(()->{
for(int i=0;i<10;i++){
resource1.consumer();
}
},"consumer").start();
}
}
模拟死锁
- 代码：```java import java.sql.Time; import java.util.concurrent.TimeUnit;
class MyDeadLock implements Runnable{ //两个资源 public String lockA; public String lockB; public MyDeadLock(String lockA,String lockB){ this.lockA = lockA; this.lockB = lockB; } //持有一个资源要去申请另外一个资源 @Override public void run() { synchronized (lockA){ System.out.println(Thread.currentThread().getName()+”持有”+lockA+”要去申请”+lockB); try { TimeUnit.SECONDS.sleep(1); } catch (InterruptedException e) { e.printStackTrace(); } synchronized (lockB){ System.out.println(Thread.currentThread().getName()+”申请到了”+lockB); } } } } public class DeadLock { public static void main(String[] args) { MyDeadLock t1 = new MyDeadLock(“lockA”,”lockB”); MyDeadLock t2 = new MyDeadLock(“lockB”,”lockA”); new Thread(t1,”t1”).start(); new Thread(t2,”t2”).start(); } }
- ```java
class Resource {
//申请两个资源
public void getAB(Object A,Object B) throws InterruptedException {
synchronized (A){
Thread.sleep(1000);
System.out.println(Thread.currentThread().getName()+"getA");
synchronized (B){
System.out.println(Thread.currentThread().getName()+"getB");
}
}
}
}
public class DeadLock {
public static void main(String[] args) {
Resource resource = new Resource();
Object A = new Object();
Object B = new Object();
new Thread(()->{
try {
resource.getAB(A,B);
} catch (InterruptedException e) {
e.printStackTrace();
}
},"1").start();
new Thread(()->{
try {
resource.getAB(B,A);
} catch (InterruptedException e) {
e.printStackTrace();
}
},"2").start();
}
}
- 排查死锁：
- jps -l 查看当前运行的java线程
- jstack 进程号 （可以看出死锁）
吃汉堡
- 小红吃n天汉堡，要求每天吃的汉堡数目不一样，而且要尽可能多吃，且尽可能少吃牛肉汉堡。每天鸡肉汉堡供应数目a[i]，牛肉汉堡供应数目b[i]。求至少要吃多少牛肉汉堡？
BFS
用户到快递柜的最近距离(多源BFS)
- o表示住户，x表示快递柜地点。输出每个用户到快递柜的最近距离
输入:
o o o
o x o
o x o
输出
2 1 2
1 0 1
1 0 1 代码```java public class Main{ private Deque
queue = new ArrayDeque<>(); private int rows; private int cols; int[][] res;//记录距离 public int[][] minDistance(int [][] distance){ //将快递柜的坐标入队 rows = distance.length; cols = distance[0].length; for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ if(distance[i][j]==1){ int locate = i*cols+j; queue.offer(locate); } } } //出队 res = new int[rows][cols]; while(!queue.isEmpty()){ int locate = queue.poll(); int x = locate/cols; int y = locate%cols; bfs(x,y,distance); } return res;}
public void bfs(int x,int y,int[][] distance){
int[] dx = {1,-1,0,0}; int[] dy = {0,0,-1,1}; for(int i=0;i<4;i++){ int x1 = x+dx[i]; int y1 = y+dy[i]; //超出边界 if(x1<0||y1<0||x1>=rows||y1>=cols||distance[x1][y1]==1){ continue; } res[x1][y1] = res[x][y] + 1; distance[x1][y1] = 1; //已经访问过的点进行标记 queue.offer(x1 * cols + y1); //将坐标入队 }}
public static void main(String[] arg){
int[][] distance = {{0,0,0},{0,1,0},{0,1,0}};
Main main = new Main();
int[][] res = main.minDistance(distance);
for (int[] ans : res) {
System.out.println(Arrays.toString(ans));
}
}
}
<a name="8178ad6f"></a>
### 二叉树
<a name="7039572f"></a>
#### 二叉树的层序遍历
- 代码：```java
public List<List<Integer>> levelOrder(TreeNode root){
Deque<TreeNode> queue = new ArrayDeque<>();
List<List<Integer>> res = new ArrayList<>();
if(root==null) return res;
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> ans = new ArrayList<>();
for(int i=0;i<size;i++){
TreeNode node = queue.poll();
ans.add(node.val);
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
res.add(ans);
}
return res;
}
二叉树的右视图
- 思路:
- 广度优先遍历
- 只需要将每层的最后一个结点添加到链表中即可
代码：```java public List
rightSideView(TreeNode root){ List res = new ArrayList<>(); if(root==null) return res; Deque queue = new ArrayDeque<>(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); for(int i=0;i<size;i++){ TreeNode node = queue.poll(); if(i==size-1){ //每层最后一个节点 res.add(node.val); } if(node.left!=null){ queue.offer(node.left); } if(node.right!=null){ queue.offer(node.right); } }} return res; } ```
思路:
- 深度优先遍历
- 按照根->右->左的顺序进行遍历,记录当前层的深度.
代码:```java List
ans = new ArrayList(); public void rightSideView(TreeNode root,int depth){
if(root == null) return; //下一层的第一个结点 if(depth==ans.size()){ ans.add(root.val); } depth++; rightSideView(root.right,depth); rightSideView(root.left,depth);//入栈的时候depth=0} public List
rightSideView(TreeNode root){ rightSideView(root,0); return ans;} ```
二叉树的镜像
- 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
代码：```java public void mirror(TreeNode root){
if(root==null) return; //交换左右节点 TreeNode node = root.right; root.right = root.left; root.left = node; //递归交换 mirror(root.left); mirror(root.right);}
public TreeNode mirrorTree(TreeNode root){
mirror(root); return root;} ```
二叉树的路径总和
- 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
- 思路：深度优先+回溯
- 代码：```java import java.util.*;
class TreeNode{ int val; TreeNode left; TreeNode right; public TreeNode(int value){ this.val = value; } }
public class Main{
public void dfs(TreeNode root,int sum,Deque<Integer> path,List<List<Integer>> res){
if(root==null) return;//不满足条件
//遍历到叶子节点
if(root.right==null&&root.left==null&&sum==root.val) {
path.addLast(root.val);
res.add(new ArrayList<>(path));//保存的是拷贝
path.removeLast(); //一定要移除
return;
}
path.add(root.val); //将节点添加到路径中
dfs(root.left,sum-root.val,path,res);
dfs(root.right,sum-root.val,path,res);
path.removeLast();//回溯,移除最后一个元素
}
public List<List<Integer>> pathSum(TreeNode root,int sum){
List<List<Integer>> res = new ArrayList<>();
Deque<Integer> queue = new ArrayDeque<>();
if(root==null) return res;
dfs(root,sum,queue,res);
return res;
}
public static void main(String[] arg){
TreeNode root = new TreeNode(5);
root.left = new TreeNode(4);
root.right = new TreeNode(8);
root.left.left = new TreeNode(11);
root.left.left.left = new TreeNode(7);
root.left.left.right = new TreeNode(2);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(4);
root.right.right.left = new TreeNode(5);
root.right.right.right = new TreeNode(1);
Main main = new Main();
int sum = 22;
List<List<Integer>> res = main.pathSum(root, sum);
System.out.println(res.size());
for (List<Integer> ans : res) {
System.out.println(ans.toString());
}
}
}
<a name="28856633"></a>
#### 二叉树的最大路径和
- 给定一个**非空**二叉树，返回其最大路径和。<br />本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径**至少包含一个**节点，且不一定经过根节点。
- 代码```java
int maxSum =Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
getMaxSum(root);
return maxSum;
}
public int getMaxSum(TreeNode root){
//树为空直接返回
if(root==null) return 0;
//计算左子树的最大和
int leftSum = Math.max(0,getMaxSum(root.left)); //如果是负数，就设置为0
//计算右子树的最大和
int rightSum = Math.max(0,getMaxSum(root.right));
//计算最大和
maxSum = Math.max(maxSum,root.val+leftSum+rightSum);
return root.val+Math.max(leftSum,rightSum);//左子树和右子树的和的返回值是包含了根节点的
}
二叉树的最小路径和
- 给定一棵二叉树，求根节点到叶子节点的最小路径和。
- 代码:```java
public int minSum(TreeNode root){
} ```if(root==null) return 0; else if(root.left!=null&&root.right!=null){ //左右子树都在,选择其中一条路径 return root.val+Math.min(minSum(root.left),minSum(root.right)); }else if(root.left==null){ return root.val+minSum(root.right); //只有右子树 }else{ return root.val+minSum(root.left); //只有左子树 }
二叉树的完全性检验
- 给定一棵树，判断它是否是一个完全二叉树
- 思路：
- 完全二叉树的性质是某个节点下标为index,则它的左右子树的下标分别是
- 只需要判断树的节点数目是否等于最后一个节点的下标值即可。
- 完全二叉树的性质是某个节点下标为index,则它的左右子树的下标分别是
代码：```java int size; int maxIndex; //判断树的节点数是否等于最后一个节点的标号 public boolean isCompleteTree(TreeNode root) {
if(root==null) return true; recursive(root,1); return size==maxIndex;}
public void recursive(TreeNode root,int index){
if(root==null) return; size++;//树的节点数 maxIndex = Math.max(maxIndex,index);//最后一个节点的编号值 recursive(root.left,index*2); recursive(root.right,index*2+1);} ```
Z字形打印二叉树
- 第一行按照从左到右顺序，第二层从右到左，第三层再从左到右，以此类推。
- 代码```java
public List
} ```//利用双端队列的性质实现 Deque<TreeNode> queue = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); if(root==null) return res; queue.offer(root); while(!queue.isEmpty()) { int size = queue.size(); LinkedList<Integer> ans = new LinkedList<>();//每层结果 for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if(res.size()%2!=0){ ans.addFirst(node.val);//奇数层添加到头部 0,1,3 }else{ ans.addLast(node.val);//偶数层添加到尾部 2,4,6 } if(node.left!=null) queue.offer(node.left); if(node.right!=null) queue.offer(node.right); } res.add(ans); } return res;
迭代法写二叉树的前序遍历
- 代码:```java
public List
preorderTraversal(TreeNode root) {
} ```LinkedList<Integer> res = new LinkedList(); LinkedList<TreeNode> stack = new LinkedList(); while(root!=null||!stack.isEmpty()){ if(root!=null){ stack.offerLast(root); //根 res.add(root.val); root = root.left; //左 }else{ root = stack.pollLast(); root = root.right; //右 } } return res;
迭代法写二叉树的后序遍历
- 代码：```java
public List
postorderTraversal(TreeNode root) { LinkedList res = new LinkedList<>(); if(root==null) return res; //使用栈结构来模拟递归 Deque stack = new LinkedList<>(); while(root!=null || !stack.isEmpty()){
} return res; } ```//先遍历完所有的右节点 if(root!=null){ stack.offerLast(root); //根 res.addFirst(root.val); root = root.right; //右 //再遍历左结点 }else{ root = stack.pollLast(); root = root.left; //左 }
迭代法写二叉树的中序遍历
- 代码：```java
public List
inorderTraversal(TreeNode root) {
} ```LinkedList<Integer> res = new LinkedList<>(); LinkedList<TreeNode> stack = new LinkedList<>(); while(root!=null||!stack.isEmpty()){ //先将树的所有左结点入栈 while(root!=null){ stack.addLast(root); root = root.left; } //左节点依次出栈 root = stack.pollLast(); res.add(root.val); //如果有右子树就遍历右子树 root = root.right; } return res;
迭代法求二叉树的深度
- 代码：```java
//迭代法求深度
public int maxDepth(TreeNode root) {
} ```if(root==null) return 0; Stack<Pair<TreeNode,Integer>> stack = new Stack<>(); //保存每个结点及其深度 stack.push(new Pair<>(root,1));//压入根节点,深度设置为1 int depth = 0; //最大深度 while(!stack.isEmpty()){ Pair<TreeNode,Integer> pair = stack.pop();//弹出当前结点 root = pair.getKey(); int curDepth = pair.getValue(); depth = Math.max(depth,curDepth);//求最大深度 if(root.left!=null){ stack.push(new Pair<>(root.left,curDepth+1)); //压入左节点 } if(root.right!=null){ stack.push(new Pair<>(root.right,curDepth+1));//压入右节点 } } return depth;
重建二叉树
- 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字.
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]3 / \ 9 20 / \ 15 7private int[] preorder; //前序遍历数组 Map<Integer,Integer> map = new HashMap<>();//存放根结点和其对应的位置 public TreeNode buildTree(int pStart,int pEnd,int iStart,int iEnd){ //边界条件 if(pStart>pEnd||iStart>iEnd) return null; //前序序列的第一个结点一定是根节点 int pivot = preorder[pStart]; //寻找前序中的根节点在中序中的位置 int index = map.get(pivot); //创建根节点 TreeNode root = new TreeNode(pivot); //递归左右子树,需要计算一下左右子树在前序和中序序列中的范围 root.left = buildTree(pStart+1,pStart+(index-iStart),iStart,index-1); root.right = buildTree(pStart+(index-iStart)+1,pEnd,index+1,iEnd); return root; } public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; for(int i=0;i<inorder.length;i++){ map.put(inorder[i],i); } return buildTree(0,preorder.length-1,0,inorder.length-1); }
二叉树的最近公共祖先
- 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
- 代码:```java
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
} ```//边界条件 if(root==null||root==p||root==q) return root; //p,q是否在左子树中 TreeNode left = lowestCommonAncestor(root.left,p,q); //p,q是否在右子树中 TreeNode right = lowestCommonAncestor(root.right,p,q); if(left!=null&&right!=null){ return root; }else if(left!=null){ return left; }else{ return right; }
最小高度树（构造二叉搜索树）
- 给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树
- ```bash 给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
- 思路：
- 二分法，取中间位置作为根结点，左半部分作为左子树，右半部分作为右子树，递归。
- 代码：```java
public TreeNode sortedArrayToBST(int[] nums,int left,int right){
if(nums.length==0) return null;
if(left>right){
return null;
}
int mid = left+(right-left)/2;
TreeNode root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(nums,left,mid-1);
root.right = sortedArrayToBST(nums,mid+1,right);
return root;
}
public TreeNode sortedArrayToBST(int[] nums) {
return sortedArrayToBST(nums,0,nums.length-1);
}
验证二叉搜索树
- 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
输入: 2 / \ 1 3 输出: true思路：
- 使用last来保存中序遍历时的上一个结点值，注意数据类型是long,是为了防止根节点的值是Integer.MIN_VALUE的情况。
- 先遍历左子树，若左子树不是二叉搜索树则返回
- 遍历根节点，若根节点的值小于等于上一个节点的值则返回false;
- 最后遍历右子树，以右子树的结果返回。
代码：```java //利用中序遍历是一个递增序列来验证 private long last = Long.MIN_VALUE;//用来保存中序遍历的上一个结点值 public boolean isValidBST(TreeNode root) {
if(root==null) return true; //遍历左子树 if(!isValidBST(root.left)){ return false; } //比较当前结点与上一个结点的值 if(root.val<=last){ return false; } last = root.val; //更新上一个结点 return isValidBST(root.right); //遍历右子树} ```
代码：```java //二叉搜索树的中序遍历一定是升序序列 public boolean isValidBST(TreeNode root) {
if(root==null) return true; long prev = Long.MIN_VALUE; //上一个结点的值 //迭代法求中序遍历 Stack<TreeNode> stack = new Stack<>(); while(root!=null||!stack.isEmpty()){ while(root!=null) { stack.push(root); root = root.left; } if(!stack.isEmpty()) { root = stack.pop(); if(root.val>prev) prev =root.val; else return false; root = root.right; } } return true;} ```
二叉搜索树与双向链表
- 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
- 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
- 思路:
- 将整个二叉树的结点分为前驱结点和后继结点.可以发现如下规律:
- 前驱结点的右子树指向后继结点 pre.right = cur;
- 后继结点的左子树指向前驱结点 cur.left = pre;
- 头结点的左子树指向最后一个结点 head.left = tail;
- 最后一个结点的右子树指向头节点 tail.right = head;
- 我们只需要中序遍历整个二叉树,把上述结点关系描述出来即可.
- 将整个二叉树的结点分为前驱结点和后继结点.可以发现如下规律:
代码:```java //中序遍历 Node pre = null; Node head = null; public Node treeToDoublyList(Node root) {
if(root==null) return root; dfs(root); head.left = pre; pre.right = head; return head;}
public void dfs(Node cur){
if(cur==null) return; dfs(cur.left); if(pre!=null){ pre.right = cur; //前驱结点的右子树指向当前结点 }else{ head = cur; //双向链表的表头 } cur.left = pre; //当前结点的左子树指向前驱结点 pre = cur; //移动前驱结点 dfs(cur.right);} ```
将二叉树变成单链表
- 二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。
输入： [4,2,5,1,3,null,6,0] 输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]思路：
- 设置prev和head指针。prev表示前驱节点，head表示头指针。
- 模拟二叉树的中序遍历。先递归左子树，if prev==null, 那么 prev = root， head.right = root, 否则设置前驱节点的右子树为root,然后移动prev指针。然后设置root.left=null,最后递归右子树即可。
- 代码：```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Main {
//递归
TreeNode prev = null;
TreeNode head = new TreeNode(-1);//新的头结点
public TreeNode convertBiNode(TreeNode root){
} //模拟中序遍历 左->根->右 public void dfsTree(TreeNode root) {dfsTree(root); return head.right;
}if(root==null) return; dfsTree(root.left); if(prev==null){ //第一个节点 prev = root; head.right = root; }else{ prev.right = root;//将根节点作为前一个节点的右子树 prev = root;//前一个节点变为根节点 } root.left = null; dfsTree(root.right);
public static void main(String[] args) {
Main main = new Main();
TreeNode root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(5);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
root.left.left.left = new TreeNode(0);
root.right.right = new TreeNode(6);
main.convertBiNode(root);
}
}
<a name="c5f04685"></a>
#### 平衡二叉树
- 给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为: 一个二叉树_每个节点_ 的左右两个子树的高度差的绝对值不超过1。
- ```bash
3
/ \
9 20
/ \
15 7
#输出：true
- 思路:
- dfs,先判断根节点的左右子树高度差是否小于1，若不是，则返回false。是则递归根节点的左右子树，分别判断它们是否高度差小于1.
- 代码：```java
class Solution {
public int getHeight(TreeNode root){
} public boolean isBalanced(TreeNode root) {if(root==null) return 0; return 1+Math.max(getHeight(root.left),getHeight(root.right));
} } ```if(root==null) return true; int height = Math.abs(getHeight(root.left)-getHeight(root.right)); if(height>1){ return false; }else{ return isBalanced(root.left)&&isBalanced(root.right); }
后继者
- 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。如果指定节点没有对应的“下一个”节点，则返回
null。 ```bash 输入: root = [5,3,6,2,4,null,null,1], p = 6
5/ \ 3 6 / \ 2 4 /
1
输出: null
- 思路
- 递归：因为题目是二叉搜索树，故它的中序遍历一定是升序的。可以将p与root比较，若小于等于root则说明在右子树中。否则在左子树中查找，若找不到就返回当前根节点。
- 迭代: 先将所有左子树的节点入栈，再依次出栈，判断若与根节点相等就设置标志位，到时候返回栈顶元素即可。若当前节点存在右节点，则将右节点也入栈。
- 代码：```java
//中序遍历 左 根 右 是一个升序序列
public TreeNode inorderSuccessor(TreeNode root,TreeNode p){
if(root==null||p==null) return null;
//若当前节点的值小于等于根节点的值，那么答案一定在 右子树中
if(root.val<=p.val) return inorderSuccessor(root.right,p);
else{
//否则根节点就可能是答案，然后遍历其左子树，看看有没有更加接近的答案
TreeNode left = inorderSuccessor(root.left,p);
//如果左子树为空，那么当前根节点就是答案
return left!=null?left:root;
}
}
- 代码：```java
//迭代法求中序遍历
public TreeNode inorderSuccessor(TreeNode root,TreeNode p){
} ```Stack<TreeNode> stack = new Stack<>(); boolean flag = false; //是否找到 while(root!=null||!stack.isEmpty()){ while(root!=null){ stack.push(root); //左子树入队 root = root.left; } root = stack.pop(); if(flag) return root; if(root.val==p.val){ flag = true; } root = root.right; //遍历右子树 } return null;
二叉树着色游戏
- 有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。
输入：root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3 输出：True 解释：第二个玩家可以选择值为 2 的节点。思路:
- 第一个玩家选的x结点将会把整个二叉树拆成3个连通分量，分别是左子树、右子树和前驱。
- 我们需要计算这三个连通分量各自的结点数，由于第二个玩家只能选择1个连通分量，故要求选择的那个连通分量的结点数要大于总结点数的一半，第二个玩家才能获胜。
代码```java /**
- Definition for a binary tree node.
- public class TreeNode {
- int val;
- TreeNode left;
- TreeNode right;
- TreeNode(int x) { val = x; }
} */ class Solution { //x会将整棵树切割为三个连通分量，y可以选择三个中的任何一个 int left = 0;//左子树结点数目 int right = 0;//右子树结点数 public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
dfs(root,x); int prev = n-left-right-1; //前驱结点数 //只要存在一个连通分量的结点个数大于总节点数的一半就行 if(prev>n/2||left>n/2||right>n/2) return true; return false;}
//dfs求连通分量 public int dfs(TreeNode root,int x){
if(root==null) return 0; int l = dfs(root.left,x); int r = dfs(root.right,x); if(root.val==x){ left = l; right = r; } return l+r+1;// 左右连通分量的节点数+当前根节点} } ```
链表
链表倒数第K个节点
- 思路：快慢指针,快指针先走K步
- 代码```java
//快慢指针
public ListNode getKthFromEnd(ListNode head,int k){
} ```ListNode slow = head; ListNode fast = head; for(int i=0;i<k&&fast!=null;i++){ fast = fast.next; } if(fast==null) return head; while(fast!=null){ fast = fast.next; slow = slow.next; } return slow;
链表奇偶翻转
- 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性
输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL- 代码：```java
public ListNode oddEvenList(ListNode head) {
if(head==null) return null;
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even; //保存头节点
while(even!=null && even.next!=null){
} odd.next = evenHead; //奇链表和偶链表接起来 return head; } ```odd.next = even.next; odd = odd.next; //移动奇节点指针 even.next = odd.next; even = even.next; //移动偶节点指针
K个一组翻转链表
- 思路：
- 尾插法，新建头指针，pre和tail都从头指针开始。
- tail指向待翻转的链表最后一个节点。
- pre,cur,tail进行链表的翻转。
- tail=null时退出
- 翻转过程：
- 代码：```java
public ListNode reverseKGroup(ListNode head,int k){
} ```ListNode newHead = new ListNode(-1); newHead.next = head; ListNode pre = newHead; //待删除结点的前一个结点 ListNode tail = newHead; while(tail!=null){ ListNode head1 = pre.next; //下一个待删除结点 for(int i=0;i<k&&tail!=null;i++){ tail = tail.next; } //翻转链表 ListNode cur = null; while(tail!=null&&pre.next!=tail){ cur = pre.next; pre.next = cur.next; cur.next = tail.next; tail.next = cur; } pre = head1; tail = head1; } return newHead.next;
循环链表的第一个结点
- 思路：快慢指针
- 相遇点找到，然后一个指针回到起点重新出发，两个指针一起走，再次相遇即为循环链表的第一个结点。
- 代码：```java
public ListNode detectCycle(ListNode head) {
//快慢指针先找到相遇的点，然后其中一个指针再从起点出发，两个指针一起走，最后会在入环的节点处相遇
if(head==null||head.next==null) return null;
ListNode slow = head;
ListNode fast = head;
boolean haveCycle = false;
while(fast!=null&&fast.next!=null){
} if(!haveCycle) return null; //无环 slow = head; while(slow!=fast){slow = slow.next; fast = fast.next.next; //若相遇必有环 if(slow==fast){ haveCycle = true; break; }
} return slow; } ```slow = slow.next; fast = fast.next;
判断链表是否有环
- 思路：快慢指针
- 代码：```java
//快慢指针,快指针每次走两步，慢指针每次走一步
public boolean hasCycle(ListNode head) {
if(head==null||head.next==null) return false;//例外情况
ListNode slow = head;
ListNode fast = head;
while(fast!=null&&fast.next!=null){
} return false; } ```slow = slow.next; fast = fast.next.next; //两个指针相遇就有环 if(slow==fast){ return true; }
链表两两翻转
- 给定链表:
1->2->3->4->5->6->7返回结果：2->1->4->3->6->5->7 - 代码：
//链表两两翻转
public ListNode swapPairs(ListNode head){
ListNode newHead = new ListNode(-1);
newHead.next = head;
ListNode pre = newHead;
ListNode cur = null;
ListNode tail = null;
while(pre.next!=null&&pre.next.next!=null){
cur = pre.next; //待翻转结点
tail = cur.next;//尾节点
//翻转
pre.next = tail;
cur.next = tail.next;
tail.next = cur;
//移动到下一个待翻转结点的前驱节点
pre = cur;
}
return newHead.next;
}
链表反转II
- 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL思路：
- 找到待反转节点的前驱结点，然后找到带反转的右边界结点
- 使用尾插法反转链表即可
代码：```java /**
- Definition for singly-linked list.
- public class ListNode {
- int val;
- ListNode next;
- ListNode(int x) { val = x; }
} */ class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
//新建头指针 ListNode newHead = new ListNode(-1); newHead.next = head; ListNode prev = newHead; ListNode tail = newHead; ListNode p = newHead; //定位节点 for(int i=0;i<n&&p!=null;i++){ if(i==m-1){ prev = p;} p = p.next; } tail = p; //头插法反转 ListNode cur = null; while(prev.next!=tail){ cur = prev.next; prev.next = cur.next; cur.next = tail.next; tail.next = cur; //新的尾节点 } return newHead.next;} } ```
两链表相交的交点
- 思路：两个指针pA和pB分别指向两个链表的头节点，然后遍历链表，循环终止条件是两者相等。若某个指针遍历到链表尾仍然不相等，则该指针指向另外一个链表的头节点，继续遍历。原理：两者走过的路径是一样的，所以一定会都走到终点null或者相遇。
- 代码：```java
public ListNode getIntersectionNode(ListNode headA,ListNode headB){
} ```if(headA==null||headB==null) return null; ListNode pA = headA; ListNode pB = headB; while(pA!=pB){ pA = (pA==null)?headB:pA.next; pB = (pB==null)?headA:pB.next; } return pA;
判断回文链表
- 编写一个函数，检查输入的链表是否是回文的。
输入： 1->2->2->1 输出： true思路：
- 使用快慢指针定位中间节点，慢指针指向的节点
- 反转右半边链表
- 迭代比较两边的链表是否相等
- 代码：```java
// 快慢指针寻找中间节点=>反转右半边链表=>迭代比较两边的链表是否相等
public boolean isPalindrome(ListNode head) {
if(head==null) return true; //考虑空链表
//寻找链表的中间节点
ListNode mid = findMiddleNode(head);
//翻转右半边链表
ListNode rightStart = reverseList(mid.next);
//迭代比较两半边链表,右半边的链表长度比较小，以右半边结束为准
while(rightStart!=null){
} return true; }if(head.val==rightStart.val){ head = head.next; rightStart = rightStart.next; }else{ return false; }
//快慢指针寻找中间节点 public ListNode findMiddleNode(ListNode head){ ListNode slow = head; ListNode fast = head; while(fast.next!=null&&fast.next.next!=null){ fast = fast.next.next; slow = slow.next; //中间节点的位置 } return slow; } //反转链表 public ListNode reverseList(ListNode head){ ListNode prev = null; ListNode cur = head; while(cur!=null){ ListNode t = cur.next;//保存下一个待翻转的节点 cur.next = prev; prev = cur; cur = t; } return prev; //新的头节点 }
<a name="73437bc7"></a>
#### 复制带随机指针的链表
- 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的 深拷贝.
- 我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示： val：一个表示 Node.val 的整数。<br />random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
- 代码:```java
public Node copyRandomList(Node head) {
if(head==null) return null;
HashMap<Node,Node> map = new HashMap<>();
Node p = head;
//第一遍先复制所有结点
while(p!=null){
map.put(p,new Node(p.val)); //存储原节点和复制的结点
p = p.next;
}
//第二遍复制所有结点的next和random指针
p = head;//p是原链表的结点 map.get(p)是新链表的结点
while(p!=null){
map.get(p).next = map.get(p.next); //从哈希表中取p的next结点
map.get(p).random = map.get(p.random); //从哈希表中取p的random结点
p = p.next;
}
return map.get(head);
}
链表求和
- 给定两个用链表表示的整数，每个节点包含一个数位. 这些数位是反向存放的，也就是个位排在链表首部。
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 输出：2 -> 1 -> 9，即912代码:```java public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null; ListNode p = head; int carry = 0; while(l1!=null||l2!=null){ int num1 = l1==null?0:l1.val; int num2 = l2==null?0:l2.val; int sum = (num1+num2+carry)%10; carry = (num1+num2+carry)/10; if(head==null){ head = new ListNode(sum); p = head; }else{ p.next = new ListNode(sum); p = p.next; } //移动指针 l1 = l1==null?null:l1.next; l2 = l2==null?null:l2.next; } //溢出时 if(carry==1){ p.next = new ListNode(1); } return head;} ```
假设数据是正向存放的
输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295 输出：9 -> 1 -> 2，即912思路：
- 翻转两个链表，求和之后将求和得到的链表再次翻转
分割链表
- 编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。
输入: head = 3->5->8->5->10->2->1, x = 5 输出: 3->1->2->10->5->5->8思路：
- 此题的意思是让比x小的元素都放在左边，比x大的元素都放在右边即可。不需要跟示例完全保持一致
- 初始化两个指针p和q，其中p是用来记录比x小的节点，q是用来遍历链表的。只要q的值比x小，就交换p和q的值，并且移动p。q在每次循环中都要进行移动。
- 代码：```java
/**
- Definition for singly-linked list.
- public class ListNode {
- int val;
- ListNode next;
- ListNode(int x) { val = x; }
- }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
} } ```ListNode p = head; //记录小于x的节点 ListNode q = head; //遍历链表 while(q!=null){ if(q.val<x){ //交换p,q的值 int temp = q.val; q.val = p.val; p.val = temp; //移动p p = p.next; } //移动q q = q.next; } return head;
旋转链表
- 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL思路：
- 首先遍历链表获取链表长度 len,然后使用k%len，得到最后移动位置，若k为0，则不需要移动，直接返回。
- 否则先翻转整个链表，再翻转前k个元素，最后翻转后n-k个元素。
- 代码：```java
/**
- Definition for singly-linked list.
- public class ListNode {
- int val;
- ListNode next;
- ListNode(int x) { val = x; }
- }
*/
class Solution {
//将链表闭合成环，得到链表长度
public int getLength(ListNode head){
} public ListNode rotateRight(ListNode head, int k) {int n = 1; ListNode p = head; while(p.next!=null){ n++; p = p.next; } p.next = head; return n;
} } ```if(head==null) return head; int n = getLength(head); //新的头节点在n-k处 //新的尾节点在n-k-1处 k = k%n;//一定要取余 ListNode tail = head; ListNode newHead = head; for(int i=0;i<n-k;i++){ if(i<n-k-1) tail = tail.next; newHead = newHead.next; } tail.next = null;//将尾节点后面断开 return newHead;
反转单链表
- 代码：
思路1：迭代法```java public ListNode reverseList(ListNode head){
if(head==null) return null; ListNode prev = null; while(head!=null){ //保留下一个结点 ListNode t = head.next; //反转 head.next = prev; //移动指针 prev = head; head = t; } return prev;} ```
思路2：递归```java public ListNode reverseList(ListNode head) {
if(head==null||head.next==null) return head; ListNode cur = reverseList(head.next); head.next.next = head; //反转尾结点 head.next = null;//尾结点置空 return cur;//返回头结点} ```
单链表排序
- 思路1：归并排序
代码：```java //归并排序 public ListNode sortList(ListNode head) {
if(head==null||head.next==null) return head; ListNode mid = findMid(head); ListNode right = mid.next; mid.next = null; ListNode l = sortList(head); ListNode r = sortList(right); return mergeCross(l,r);} //寻找中间节点 public ListNode findMid(ListNode head){
ListNode slow = head; ListNode fast = head; while(fast.next!=null&&fast.next.next!=null){ fast = fast.next.next; slow = slow.next; } return slow;} //合并两个有序链表 public ListNode mergeCross(ListNode left,ListNode right){
ListNode head = new ListNode(-1); ListNode cur = head; while(left!=null&&right!=null){ if(left.val<right.val){ cur.next = left; left = left.next; }else{ cur.next = right; right = right.next; } cur = cur.next; } cur.next = left==null?right:left; return head.next;} ```
思路2：快速排序，交换值
代码：```java //快速排序 交换节点的值 public ListNode sortList(ListNode head) {
quickSort(head,null); return head;}
public void quickSort(ListNode head,ListNode tail){
if(head==tail||head.next==tail) return; int temp = head.val; ListNode left = head; //比较小的部分 ListNode cur = head.next;//大的部分 while(cur!=tail){ if(cur.val<temp){ left = left.next; //先移动，再交换 swap(left,cur); } cur = cur.next; } swap(head,left); //记得放回去 quickSort(head,left); quickSort(left.next,tail);} //交换两个节点的值 public void swap(ListNode a,ListNode b){
int temp = a.val; a.val = b.val; b.val = temp;} ```
思路3：快速排序，不交换值
代码:有问题待修改```java //快速排序 public ListNode sortList(ListNode head) {
quickSort(head); return head;}
public ListNode[] partition(ListNode head){
int temp = head.val; ListNode small = null; //比枢纽小的部分 ListNode equal = null;//相等部分 ListNode big = null; //比枢纽大的部分 ListNode cur = head; while(cur!=null){ ListNode t = cur.next; if(cur.val<temp){ cur.next = small; small = cur; }else if(cur.val>temp){ cur.next = big; big = cur; }else{ cur.next = equal; equal = cur; } cur = t; } return new ListNode[]{small,equal,big};}
// ListNode small,equal,big; public ListNode quickSort(ListNode head){
if(head==null||head.next==null) return head; //将链表按照枢纽的值划分为三个部分 ListNode[] nds = partition(head); ListNode small = nds[0]; ListNode equal = nds[1]; ListNode big = nds[2]; //分别对较大部分和较小部分进行快排 big = quickSort(big); small = quickSort(small); ListNode newHead = new ListNode(-1); //拼接三个部分 ListNode cur = newHead; ListNode[] nodes = new ListNode[]{small,equal,big}; ListNode p = null; for (ListNode node : nodes) { p = node; while(p!=null){ cur.next = p; p = p.next; cur = cur.next; // cur.next = null; } cur.next = null; } return newHead.next;} ```
相加
字符串相加
- 思路：
- 翻转字符串
- 注意加的时候带上进位
- 最后考虑溢出的情况
- 代码```java
public String addStrings(String num1, String num2) {
int len = Math.max(num1.length(),num2.length());
int index = 0;
StringBuilder res = new StringBuilder();
int carry = 0; //进位
//翻转字符串
num1 = new StringBuilder(num1).reverse().toString();
num2 = new StringBuilder(num2).reverse().toString();
while(index<len){
} if(carry==1) res.append(1); //溢出 return res.reverse().toString(); } ```//长度不够需要补0 int n1 = index<num1.length()?num1.charAt(index)-'0':0; int n2 = index<num2.length()?num2.charAt(index)-'0':0; int sum = (n1+n2+carry)%10; carry = sum/10; res.append(sum); index++;
两数相加
- 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807思路：
- 求两个链表对应位置的值及进位carry的和。注意如果链表长度不够，需要将当前值设置为0；
- 计算进位以及最终和，新建节点，尾插法插入结果链表。
- 考虑溢出情况，需要尾插入值为1的节点。
- 代码：```java
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);//头指针
ListNode cur = head;
int carry = 0;//进位
while(l1!=null||l2!=null){
} //溢出情况 if(carry==1) {//短的链表要补0 int x = (l1==null)?0:l1.val; int y = (l2==null)?0:l2.val; int sum = x+y+carry; carry = sum/10; sum = sum%10; cur.next = new ListNode(sum); cur = cur.next; //移动 if(l1!=null) l1 = l1.next; if(l2!=null) l2 = l2.next;
} return head.next; } ```cur.next = new ListNode(1);
滑动窗口
最长不含重复字符的子字符串
- 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。思路:
- 维护一个滑动窗口，使用map存放每个字符最新出现的位置
- 若新元素在滑动窗口中出现过，那么就更新左边界为 该元素位置+1或原来的左边界的最大值
- 计算不重复子串的长度
- 代码：```java
//滑动窗口
public int lengthOfLongestSubstring(String s) {
} ```int maxlen = 0; //存放每个字符最新出现的位置 Map<Character,Integer> map = new HashMap<>(); int left = 0;//左边界 for(int i=0;i<s.length();i++){//i是当前右边界 if(map.containsKey(s.charAt(i))){ //更新左边界 left = Math.max(left,map.get(s.charAt(i))+1); } map.put(s.charAt(i),i);//更新位置 maxlen = Math.max(maxlen,i-left+1);//求不重复子串的最大长度 } return maxlen;
连续正整数序列
- 输入一个正整数
target，输出所有和为target的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]代码：```java //滑动窗口,保证窗口内的和始终是target public int[][] findContinuousSequence(int target){ int leftBound = target/2+1;//至少含有两个数,所以左边界不能超过一半 int left = 1;//左边界 int right = 1;//右边界 int sum = 0; //滑动窗口内的和 List
//和小了，移动右边界 if(sum<target){ sum += right; right++; }else if(sum>target){//和大了，移动左边界 sum -= left; left++; }else{ //刚好合适，则保存，并移动左边界 int[] ans = new int[right-left]; int index = 0; for(int i=left;i<right;i++){ ans[index++] = i; } res.add(ans); //移动左边界 sum -= left; left++; }} return res.toArray(new int[res.size()][]); } ```
数组中连续三个数的最大值
- 思路：滑动窗口，每次右移一位即可。
- 代码：```java
public int maxSum(int[] num){
int res = 0;
if(num.length<2){
} int sum = num[0]+num[1]+num[2]; res = sum; for(int i=3;i<num.length;i++){for(int i=0;i<num.length;i++){ res += num[i]; }
} return res; } ```sum = num[i]-num[i-3]; res = Math.max(res,sum);
最长连续递增子序列
- 给定一个未经排序的整数数组，找到最长且连续的的递增序列，并返回该序列的长度。
输入: [1,3,5,4,7] 输出: 3 解释: 最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开代码：```java //滑动窗口 public int findLengthOfLCIS(int[] nums) {
int n = nums.length; if(n<=1) return n; int ans = 1; int count = 1; for (int i = 1; i < nums.length; i++) { if(nums[i]>nums[i-1]){ count++; }else{ count = 1; //不是连续递增的，则重新初始化 } ans = Math.max(ans,count); //更新最大长度 } return ans;} ```
最大或的最短子区间长度
- 最大子区间或的最短子区间长度
输入： [1:3] 输出： 1 # 满足最大或的子区间有三个，[1:2:3] [1:2] [3:3] 最小子区间长度为1思路：
- 滑动窗口。 只需要扫描一遍数组即可。
- 需要借助一个count数组来实现添加或回退的功能。count数组是一个32位的整型数组，存储每一位的1的个数。
- 每次出现新的最大或值时，判断能否往前滑动，缩小长度。
- 代码：```java package com.qmh;
import java.util.*;
public class Main { //记录每一位的1出现次数 int[] count = new int[32];
//添加元素，在count数组中添加对应1的个数
public void add(int x){
int i=0;
while(x>0){
count[i] += (x&1);
i+=1;
x = x>>1;
}
}
//判断能否删除x,若删除x会让对应位置的1的数量没有了，就不能删
public boolean can_del(int x){
int i=0;
while(x>0){
if(count[i]<=(x&1)){
return false;
}
i+=1;
x = x>>1;
}
return true;
}
//删除x,从count数组中扣除对应1的个数
public void del(int x){
int i=0;
while(x>0){
count[i] -= (x&1);
i+=1;
x = x>>1;
}
}
public int getMaxOr(int nums[],int n){
int v = 0;
int maxV = 0;
int j = 0; //左边界
int minL = n; //最短区间长度
for(int i=0;i<n;i++){ //右边界
v|=nums[i]; //计算[0:i]区间的或值
add(nums[i]); //加入到count数组中
if(v>=maxV){ //若当前值超过了最大值，判断能否扩大滑动窗口的左边界
while(j<=i && can_del(nums[j])){
del(nums[j]);
j+=1;
}
if(v==maxV){
minL = Math.min(minL,i-j+1); //更新最短区间长度
}else{
minL = i-j+1;
}
maxV = v;
}
}
return minL;
}
public static void main(String[] args) {
Main main = new Main();
int n = 7;
int[] nums = {1,2,3,4,5,6,7};
System.out.println(main.getMaxOr(nums, n));
}
}
<a name="620e2127"></a>
#### 计数二进制子串
- 给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。<br />重复出现的子串要计算它们出现的次数。
- ```bash
输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
请注意，一些重复出现的子串要计算它们出现的次数。
另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
- 思路：
- 此题关键在于将连续的0和1分段，统计它们连续出现的次数，记录在count数组中，比如”00110011”可以得到[2,2,2,2];
- 然后可以对count数组使用滑动窗口，统计当前元素与前一个元素能够组成的0和1个数相同的子串数目。
- 代码：```java
class Solution {
//滑动窗口
public int countBinarySubstrings(String s) {
} } ```//按照0和1的连续段分组 List<Integer> list = new ArrayList<>(); list.add(1); //设置第一个元素的个数为1 for (int i = 1; i < s.length(); i++) { char ch = s.charAt(i-1); if (s.charAt(i)==ch){ list.set(list.size()-1,list.get(list.size()-1)+1); //对最后一个元素+1 }else { list.add(1); //加入新元素，并设置个数为1 } } //计算相邻数字对答案的贡献 int ans = 0; for (int i = 1; i < list.size(); i++) { ans += Math.min(list.get(i),list.get(i-1)); } return ans;
最大连续1的个数III
- 给定一个由若干
0和1组成的数组A，我们最多可以将K个值从 0 变成 1 。返回仅包含 1 的最长（连续）子数组的长度。 输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释： [1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。思路：
- 滑动窗口，窗口维护小等于K的0的个数，若0的个数大于K，就需要扩大左边界。
- 每次选出以当前下标为右边界时的最大滑动窗口长度。
- 代码：```java
class Solution {
//滑动窗口，窗口内保持K个值为0，若0的个数大于K就移动左边界，直到不满足条件
public int longestOnes(int[] A, int K) {
} } ```int left = 0; int right = 0; int count = 0; int maxLen = 0; while(right<A.length){ if(A[right]==0) count+=1; if(count>K){ if(A[left]==0) count-=1; left+=1; } maxLen = Math.max(maxLen,right-left+1);//计算当前滑动窗口长度 right++;//移动有右边界 } return maxLen;
替换后的最长重复字符
- 给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
- ```java 输入: s = “AABABBA”, k = 1
输出: 4
解释: 将中间的一个’A’替换为’B’,字符串变为 “AABBBBA”。 子串 “BBBB” 有最长重复字母, 答案为 4。
- 思路：
- 滑动窗口,长度为26的数组，存放滑动窗口内每个字符的出现次数。
- 统计在当前右边界下的，滑动窗口长度是否大于maxlen+k(替换后的最大连续字符长度)，若大于，则需要扩大滑动窗口左边界。
- 代码：```java
//滑动窗口
public int characterReplacement(String s, int k) {
int[] map = new int[26]; //滑动窗口内各个字符出现的次数
if(s==null) return 0;
char[] chs = s.toCharArray();
int left = 0;
int maxLen = 0; //单个连续字符的最大长度
int ans = 0;
//当前滑动窗口的右边界
for(int right=0;right<s.length();right++){
int index = chs[right]-'A';
map[index]++;
maxLen = Math.max(maxLen,map[index]);
//若滑动窗口内替换的字符个数超过K就要扩大左边界
if(right-left+1>maxLen+k){
map[chs[left]-'A']--;
left++;
}else{
//更新答案
ans = Math.max(ans,right-left+1);
}
}
return ans;
}
求满足条件的最长字符串的长度
- 给定一个字符串，请返回满足以下条件的最长字符串的长度：a,b,c,x,y,z在字符串中都恰好出现了偶数次。0也是偶数。
# 输入 amabc 输出 ama思路：
- 使用一个mask来标志这6个字符的奇偶性情况。每一位代表1个字符的奇偶性。
- 然后将各种奇偶性出现的位置保存在map中。
- 代码：```java package com.qmh; import java.util.*;
public class Main {
public int getMaxLen(String str){
int mask = 0;//6位二进制，每一位代表对应字符是奇数还是偶数
Map<Character,Integer> map = new HashMap<>();
char[] chs = {'a','b','c','x','y','z'};
for (int i = 0; i < chs.length; i++) {
map.put(chs[i],i);
}
int ans = 0;
//某种奇偶性第一次出现的位置记录
Map<Integer,Integer> dict = new HashMap<>();
dict.put(0,-1); //全为偶数的情况
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if(map.containsKey(ch)){
mask = mask ^ (1<<map.get(ch));
}
//如果出现过这样的情况，就相减，抵消掉奇偶性，剩下的就是偶数了
if(dict.containsKey(mask)){
ans = Math.max(ans,i-dict.get(mask));
}else{
dict.put(mask,i);
}
}
return ans;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
String str = "aaabb";
Main main = new Main();
System.out.println(main.getMaxLen(str));
}
}
<a name="0e67d4b0"></a>
### 数组
<a name="f359d032"></a>
#### 返回前K个高频元素
- 给定一个非空的整数数组，返回其中出现频率前 **k**高的元素。
-
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
- 思路：
- 使用小根堆，小根堆可以保存topN的数据。注意在设置比较器时，需要比较的是map的value而不是key.
- 大根堆可以保存前N小的数据。
- 代码：```java
//堆，输出频次高的前k个元素
public int[] topKFrequent(int[] nums, int k) {
//先使用hashmap统计每个key出现的次数
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i],map.getOrDefault(nums[i],1)+1);
}
//小根堆保存key出现次数,堆的大小为K，即保存前K高的元素
PriorityQueue<Integer> heap = new PriorityQueue<>((n1,n2)->map.get(n1)-map.get(n2));
for (Integer n : map.keySet()) {
heap.add(n);
if(heap.size()>k){
heap.poll();
}
}
//输出结果
int[] topK = new int[k];
int index = 0;
while(!heap.isEmpty()){
topK[index++] = heap.poll();
}
return topK;
}
不用循环求数组最大值
- 思路：递归
- 代码：
java public int findMax(int[] array,int index,int maxValue){ if(index>=array.length) return maxValue; maxValue = Math.max(array[index],maxValue); return findMax(array,index+1,maxValue); }
输出数组中的连续子数组的最大和
- 思路：贪心法
- 设置两个变量maxSum和curSum,分别保存最大和和当前和。
- 若curSum<=0,则curSum=nums[i],即从下一个元素开始算。
- 否则继续累加当前值。
- 每遍历完一个元素就要更新最大值
- 代码：```java
/**
- 贪心法
*/
public class Solution {
public int maxSubArray(int[] nums){
int maxSum = Integer.MIN_VALUE;
int curSum = 0;
for(int i=0;i<nums.length;i++){
} return maxSum; } public static void main(String[] args) {//和小于等于0时，从下一个数重新开始 if(curSum<=0){ curSum = nums[i]; }else { curSum += nums[i];//和大于0时累加当前值 } maxSum = Math.max(maxSum,curSum);
} } ```Solution solution = new Solution(); int[] nums = {-1,-2}; System.out.println(solution.maxSubArray(nums));
- 贪心法
*/
public class Solution {
public int maxSubArray(int[] nums){
int maxSum = Integer.MIN_VALUE;
int curSum = 0;
for(int i=0;i<nums.length;i++){
旋转数组
- 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。要求空间复杂度为o(1)
输入: [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 3 4 5 6 7 反转所有数字后 : 7 6 5 4 3 2 1 反转前 k 个数字后 : 5 6 7 4 3 2 1 反转后 n-k 个数字后 : 5 6 7 1 2 3 4 --> 结果
```java //三次反转 //原始数组=》翻转所有数字=》翻转前k个数字=》翻转后n-k个数字 public void rotate(int[] nums,int k){ int n = nums.length; k = k%n; reverse(nums,0,n-1); //反转原始数组 reverse(nums,0,k-1);//反转前 k 个数字 reverse(nums,k,n-1);//反转后 n-k 个数字后 }
public void reverse(int[] nums,int start,int end){ while(start<end){ int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start++; end—; } }
<a name="b2513fb2"></a>
#### 两数之和
- 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
- ```bash
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
- 代码：```java
//使用哈希表保存数据
public int[] twoSum(int[] nums, int target){
int[] res = new int[2];
Map
} return res; } ```int remain = target-nums[i]; if(map.containsKey(remain)){ res[0] = i; res[1] = map.get(remain); break; } map.put(nums[i],i);
三数之和为0
- 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
- ```java 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
- 思路：
- 对数组进行排序，然后使用三个指针
- 当前元素位置是i,左边界left=i+1,右边界right=len-1;
- 注意去重
- 代码：```java
public List<List<Integer>> threeSum(int[] nums) {
//对输入数组进行排序
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList();
//设置左右边界，用双指针进行查找
for(int i=0;i<nums.length;i++){
if(nums[i]>0) break; //当前数大于0，则和一定不为0
if(i>0 && nums[i]==nums[i-1]) continue; //去重
int left = i+1;
int right = nums.length-1;
while(left<right){
int sum = nums[i]+nums[left]+nums[right];
if(sum>0){
right--;
}else if(sum<0){
left++;
}else{
res.add(Arrays.asList(nums[i],nums[left],nums[right]));
while(left<right&&nums[left]==nums[left+1]) left++; //去重
while(left<right&&nums[right]==nums[right-1]) right--; //去重
left++;
right--;
}
}
}
return res;
}
最长连续序列
- 给定一个未排序的整数数组，找出最长连续序列的长度。
- 要求算法时间复杂度为O(n)
输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4代码：```java //哈希表法 public int longestConsecutive(int[] nums) { List
list = new ArrayList<>(); List list1 = new ArrayList<>(); //利用set集合对数组去重 Set set = new HashSet<>(); for (int num : nums) { set.add(num);} int res = 0; int maxLen = 1; //遍历set,寻找最长连续序列,若e+1在set中，则序列长度+1，否则置为1 for (Integer e : set) {
while(set.contains(e+1)){ list.add(e); maxLen++; e = e+1; } res = Math.max(maxLen,res); maxLen = 1; //保存最长连续序列 if(list1.size()<list.size()){ list1 = new ArrayList<>(list); } list.clear();} System.out.println(list1.toString()); return res; } ```
寻找旋转排序数组中的最小值
- 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
- ( 例如，数组
[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。
请找出其中最小的元素。假定数组中不存在重复元素 输入: [4,5,6,7,0,1,2] 输出: 0思路：
- 折半查找，每次都和最右边的数据比较
- 考虑到重复元素的情况，若中间值和最右边相等，则移动右边界。
- 若中间值小于最右边，则说明最小值在左边。right = mid
- 若中间值大于最右边，说明最小值在右边，left = mid+1
- 代码：```java
public int minArray(int[] numbers) {
} ```int left = 0; int right = numbers.length-1; 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--; //如果相等，right就向前移动一位 } } return numbers[left];
搜索旋转排序数组
- 假设按照升序排序的数组在预先未知的某个点上进行了旋转。数组
[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2]搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回-1。 输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4思路：
- 先判断中间的元素是不是要查找的值，是就直接返回。
- 然后利用折半法，缩小区间范围。若右边元素有序，则判断一下目标值是否在右边元素中，是则扩大左边界。若不在右边，则缩小右边界。
- 代码：```java
public int search(int[] nums, int target) {
} ```int left = 0; int right = nums.length-1; while(left<=right){ int mid = left+(right-left)/2; if(target==nums[mid]) return mid; //缩小边界去判断 //[mid,right]有序 if(nums[mid]<nums[right]){ //在右半边 if(target>nums[mid]&&target<=nums[right]){ left = mid+1; }else{ right = mid;//不在右半边 } }else if(nums[mid]>nums[right]){//[left,mid]有序 if(target>=nums[left]&&target<nums[mid]){ right = mid; //在左半边 }else{ left = mid+1; //不在左半边 } }else{ right--; } } return -1;
缺失的第一个正数
- 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数
- 要求时间复杂度为O(n),空间复杂度为O(1)
输入: [3,4,-1,1] 输出: 2思路:
- 利用数组做原地哈希，nums[i]存放在i-1的位置上
- 遍历修改后的数组,如果发现num[i]!=i+1,那么i+1就是缺失的正数.
- 如果没有发现,那么缺失的正数为数组长度+1.
代码:```java //原地哈希 public int firstMissingPositive(int[] nums) {
int len = nums.length; for(int i=0;i<len;i++){ //调整数组,直到nums[i]存放的是num[i]-1或其他值 while(nums[i]>0&&nums[i]<=len&&nums[i]!=nums[nums[i]-1]){ int temp = nums[nums[i]-1]; nums[nums[i]-1] = nums[i]; nums[i] = temp; } } for(int i=0;i<len;i++){ if(nums[i]!=i+1){ return i+1; } } return len+1;} ```
消失的两个数字
- 给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
输入: [2,3] 输出: [1,4]思路：
- 数学方法或原地hash
- 代码：```java
public class Main{
//数学方法
public int[] missingTwo(int[] nums) {
} //原地hash public int[] missingTwo1(int[] nums) {int n = nums.length+2; //原本的长度 int sum = n*(n+1)/2; //原本的和 int curSum = 0; for (int num : nums) { curSum+= num; } int sumTwo = sum-curSum; //需要凑到的和 int threshold = sumTwo/2; //平均值 由于两个数不相等，要么一个小于，要么一个大于 sum = 0; //只对小于等于threshold的元素求和 for (int num : nums) { if(num<=threshold) sum+=num; } //sum(1...threshold)-sum(nums中小等于threshold的元素） int one = threshold *(threshold +1)/2-sum; //得到第一个缺失的数字 return new int[]{one,sumTwo-one};
} public static void main(String[] args) {//构建完整长度的数组 int n = nums.length+2; int[] newNums = Arrays.copyOf(nums,n); Arrays.fill(newNums,n-2,n,-1); //原地hash for (int i = 0; i < newNums.length; i++) { while(newNums[i]!=i+1&&newNums[i]!=-1){ int temp = newNums[newNums[i]-1]; newNums[newNums[i]-1] = newNums[i]; newNums[i] = temp; } } //寻找缺失的元素 List<Integer> list = new ArrayList<>(); for (int i = 0; i < newNums.length; i++) { if(newNums[i]==-1){ list.add(i+1); } } return list.stream().mapToInt(Integer::valueOf).toArray();
} } ```Main main = new Main(); int[] nums = {2,3}; System.out.println(Arrays.toString(main.missingTwo(nums)));
合并区间
- 给出一个区间的集合，请合并所有重叠的区间
输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]代码:```java public int[][] merge(int[][] intervals) {
int[][] res = new int[intervals.length][]; //先将各个区间按照左边界值进行排序 Arrays.sort(intervals,(o1,o2)->o1[0]-o2[0]); int index = -1; //合并区间 for (int i = 0; i < intervals.length; i++) { //若当前数组是空的,或当前区间的起始位置大于数组中最后区间的终止位置,则不合并 //将当前区间加入结果数组中 if(index==-1||intervals[i][0]>res[index][1]){ res[++index] = intervals[i]; }else{ res[index][1] = Math.max(res[index][1],intervals[i][1]); } } return Arrays.copyOf(res,index+1);} ```
在排序数组中查找元素的第一个和最后一个位置
- 给定一个按照升序排列的整数数组
nums，和一个目标值target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别.如果数组中不存在目标值，返回[-1, -1]。 输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4]代码:```java public int[] searchRange(int[] nums, int target) {
int left = 0; int right = nums.length-1; while(left<=right){ int mid = left+(right-left)/2; if(nums[mid]==target){ //找寻左边界 int leftBound = mid; for(int i=mid-1;i>=0;i--){ if(nums[i]==target){ leftBound = i; }else{ break; } } //找寻右边界 int rightBound = mid; for(int i=mid+1;i<nums.length;i++){ if(nums[i]==target){ rightBound = i; }else{ break; } } return new int[] {leftBound,rightBound}; }else if(nums[mid]<target){ left = mid+1; }else{ right = mid-1; } } return new int[] {-1,-1};} ```
另外一种排序
- 待排序数组为{25,84,21,47,15,27,68,35,20}
- 思路：、
- 划分数组：以第一个数字为枢纽，设置high和low指针，从high指针开始遍历，遇到大的就放过，遇到小的停止，然后从low开始遍历，遇到小的就放过，遇到大的停止，交换两个不符合条件的元素。
- 快速排序的函数是利用分治法+上述划分数组的函数。
- 代码：```java import java.util.*;
public class Main{
//划分数组
public int getPivot(int[] nums,int low,int high){
//基准数据
int temp = nums[low];
int oldLow = low; //记录low的位置
//int mid = (low+high)/2;
while(low
System.out.println(Arrays.toString(nums));
return low;
}
//另外一种快排
public void quickSort(int[] nums,int left,int right){
if(left>=right) return;
int index = getPivot(nums,left,right);
quickSort(nums,left,index-1);
quickSort(nums,index+1,right);
}
public static void main(String[] args) {
Main main = new Main();
Scanner sc = new Scanner(System.in);
int n = 9;
int[] nums = {25,84,21,47,15,27,68,35,20};
main.quickSort(nums,0,nums.length-1);
}
}
<a name="e289d966"></a>
#### 峰与谷
- 在一个整数数组中，“峰”是大于或等于相邻整数的元素，相应地，“谷”是小于或等于相邻整数的元素。例如，在数组{5, 8, 6, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。现在给定一个整数数组，将该数组按峰与谷的交替顺序排序
- ```bash
输入: [5, 3, 1, 2, 3]
输出: [5, 1, 3, 2, 3]
- 思路：
- 假设峰在偶数位，谷在奇数位，如果元素不满足峰或谷的条件就交换其与前面一个元素
- 代码：```java
class Solution {
} } ```public void wiggleSort(int[] nums) { for (int i = 1; i < nums.length; i++) { //假设峰在偶数位，谷在奇数位 if(((i&1) == 0 && nums[i] < nums[i-1])||((i&1) == 1 && nums[i] > nums[i-1])){ int temp = nums[i]; nums[i] = nums[i-1]; nums[i-1] = temp; } }
和为K的子数组
- 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。代码:```java //前缀和+哈希表优化 public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>(); map.put(0,1); //下标为0的元素,前缀和为0,个数为1次 [3,..,] k=3 int pre = 0; //前缀和 int count = 0; //结果 for(int i=0;i<nums.length;i++){ pre+=nums[i]; //计算以i为结尾的和为k的连续子数组的个数 if(map.containsKey(pre-k)){ count += map.get(pre-k); } //保存前缀和以及其出现次数 map.put(pre,map.getOrDefault(pre,0)+1); } return count;} ```
数组中的第K个最大元素
- 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4代码:```java public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>(k);//小根堆 for (int num : nums) { //堆容量小于K时压入 if(queue.size()<k){ queue.add(num); }else{ //堆顶元素小于当前元素，就弹出，压入当前元素 if(!queue.isEmpty()&&queue.peek()<num) { queue.poll(); queue.add(num); } } } return queue.isEmpty()?0:queue.peek();} ```
堆排序
- 思路：
- 写调整大根堆的函数，迭代法
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Main{
public void heapSort(int[] nums){
int len = nums.length;
//构建大顶堆
for(int i=len/2-1;i>=0;i--) {
adjustHeap(nums,i,len);
}
System.out.println(Arrays.toString(nums));
for (int j=len-1;j>0;j--) {
//交换堆顶和最后一个元素
int temp = nums[0];
nums[0] = nums[j];
nums[j] = temp;
//调整堆，注意不能取到最后一个元素
adjustHeap(nums,0,j);
}
}
//调整堆
public void adjustHeap(int[] nums,int i,int len){
int temp = nums[i];
//沿关键字较大的孩子节点向下筛选
for(int j=i*2+1;j<len;j=j*2+1){
//选出左右节点中较大的节点
if (j+1<len && nums[j] < nums[j+1]) {
j++;
}
//再将较大值与根节点相比较
if (nums[j] > temp) {
nums[i] = nums[j];
//更新i
i = j;
}else{
break;
}
}
nums[i] = temp;//将temp放到最终位置
}
public static void main(String[] args) {
int[] nums = {1,2,3,4,5,6,7};
Main main = new Main();
main.heapSort(nums);
System.out.println(Arrays.toString(nums));
}
}
快速排序
- 代码```java
class Solution {
//快速排序
public int partition(int[] nums,int left,int right){
} public void qucikSort(int[] nums,int left,int right){int temp = nums[left]; while(left<right){ while(left<right&&nums[right]>=temp){ right--; } nums[left] = nums[right]; while(left<right&&nums[left]<temp){ left++; } nums[right] = nums[left]; } nums[left] = temp; //还原 return left;
} public int[] sortArray(int[] nums) {if(left<right){ int mid = partition(nums,left,right); qucikSort(nums,left,mid-1); qucikSort(nums,mid+1,right); }
} } ```qucikSort(nums,0,nums.length-1); return nums;
图
课程表
- 你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1] 输入: 2, [[1,0],[0,1]] 输出: false 解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。思路：此题考点是图的拓扑排序。先构建图的结构，然后使用多源BFS遍历图。
- 代码：```java
/**
- 图的遍历，拓扑排序
- @param numCourses 节点数量
- @param prerequisites 边集数组 （终点，起点）
- @return
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
//构建邻接表和入度表
Map
} //队列，用来遍历节点 Queueadjacency.put(i,new ArrayList<>());queue = new LinkedList<>(); for (int[] p : prerequisites) {
} //图的多源BFS遍历 for (int i = 0; i < inDegree.length; i++) {inDegree[p[1]]++; adjacency.get(p[0]).add(p[1]);
} while(!queue.isEmpty()){if(inDegree[i]==0){ queue.offer(i); }
} return numCourses==0; } ```numCourses--; //课程数-1 int point = queue.poll(); for (Integer p : adjacency.get(point)) { inDegree[p]--; if(inDegree[p]==0){ queue.offer(p); } }
课程表输出先行课
- 修完课程需要至少几个学期，每个课程需要一个学期修完且必须在前面的学期修完它的先行课
{ 1 -> [] 2 ->[] 3 -> [1,2] 4 -> [1] 5- > [1,3,4] 6 -> [5] } 1~6的先行课如上，返回结果[[1,2][3,4][5][6]]代码：```java /**
- 拓扑排序
- @param courseMap 每门课的先修课程表
- @return
*/
public List
} for (Integer course : courseMap.keySet()) {adjacency.put(i+1,new ArrayList<>());
} //2.将入度为0的节点压入队列 Queue//构建入度表 inDegree[course-1] = courseMap.get(course).size(); //遍历先行课程,构建邻接表 for (Integer cours : courseMap.get(course)) { if(adjacency.containsKey(cours)) { adjacency.get(cours).add(course); } }queue = new LinkedList<>(); for (int i = 0; i < inDegree.length; i++) {
} //3.输出结果集 while(!queue.isEmpty()){if(inDegree[i]==0){ queue.offer(i); }
} return res; } public static void main(String[] arg){int size = queue.size(); List<Integer> list = new ArrayList<>(); for(int i=0;i<size;i++) { if(queue.isEmpty()) break; Integer course = queue.poll() + 1; //因为下标从0开始 list.add(course); //将课程添加到结果集 List<Integer> relevantCourses = adjacency.get(course); for (Integer cours : relevantCourses) { inDegree[cours - 1]--; if (inDegree[cours - 1] == 0) { queue.offer(cours - 1); } } } res.add(list);
} ```Main main = new Main(); Map<Integer,List<Integer>> map = new HashMap<>(); int[][] courses = {{},{},{1,2},{1},{1,3,4},{5}}; int numCourses = courses.length; for (int i = 0; i < numCourses; i++) { map.put(i+1,new ArrayList<>()); } for (int i = 0; i < courses.length; i++) { if(courses[i].length==0) continue; for (int j = 0; j < courses[i].length; j++) { map.get(i+1).add(courses[i][j]); } } System.out.println(map.toString()); List<List<Integer>> res = main.bfsGraph(map); for (List<Integer> re : res) { System.out.println(re.toString()); }
重新安排行程
- 给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] 输出: ["JFK","ATL","JFK","SFO","ATL","SFO"] 解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。思路：
- 此题相当于遍历图的所有边，且不重复。即求欧拉回路。由于欧拉回路只有两个或0个奇数度顶点，故只有一条或0条死胡同。因此在我们在遍历最可能的路径时，遇到这样的死胡同就先入队，然后继续遍历其他路径。最后逆序输出，死胡同一定是最后走的边。
代码:```java class Solution { //求欧拉回路 public List
findItinerary(List //ticket就是边集 //构造邻接表 Map<String,PriorityQueue<String>> map = new HashMap<>(); for (List<String> ticket : tickets) { if(!map.containsKey(ticket.get(0))){ map.put(ticket.get(0),new PriorityQueue<>()); } map.get(ticket.get(0)).add(ticket.get(1)); } List<String> ans = new LinkedList<>(); dfs(map,"JFK",ans); Collections.reverse(ans); return ans;}
private void dfs(Map
ans) { //dfs遍历最可能的路径,直到死胡同 //根据欧拉图的性质,只存在一条死胡同，否则无法完成一笔画 while(map.containsKey(from)&&map.get(from).size()>0){ String tmp = map.get(from).poll(); dfs(map,tmp,ans); } //插入死胡同,死胡同一定是最后走的，可以理解为删边过程，寻找所有的死胡同，找到就删除，最后将所有死胡同逆序输出即可。 ans.add(from);}
}
<a name="d39a003f"></a>
### 背包问题
<a name="107d0b9c"></a>
#### 石头分两堆，让两堆质量相差最小
- [给定一组石头，每个石头有一个正数的重量。每一轮开始的时候，选择两个石头一起碰撞，假定两个石头的重量为x，y，x<=y,碰撞结果为
1. 如果x==y，碰撞结果为两个石头消失
2. 如果x != y，碰撞结果两个石头消失，生成一个新的石头，新石头重量y-x
最终最多剩下一个石头为结束。求解最小的剩余石头质量的可能性是多少。
- ```bash
6 # 石头个数
2 7 4 1 8 1 #每个石头质量
- 思路：
- 01背包问题，先计算出总质量，然后较小堆的质量和一定小于等于总质量的一半。
- dp[i] 表示当前容量为i的最大质量。
- 动态规划，外层循环遍历石头个数，内存循环从最大容量（总质量的一半）到当前石头的质量，求能装满当前背包容量的最大重量。
- 代码：```java
//背包问题，将石头分成2堆，较小的那堆的质量一定小于等于总质量的一半
public int minRemainWeight(int[] stones){
//求石头总质量
int weight = 0;
for (int stone : stones) {
} //动态规划,较小堆的质量一定小于或等于总质量的一半 int maxCapacity = weight/2; int[] dp = new int[maxCapacity+1]; for(int i=0;i<stones.length;i++) {weight+= stone;
} return weight-2*dp[maxCapacity]; } ```for (int j = maxCapacity; j >= stones[i]; j--) { dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]); }
数组能否分为两半，使两半的总和相等
- 给定一个数组A，判断是否可以将数组A划分为两个数组B和C，满足每个元素属于且仅属于B或C中的一个，并且B和C的总和相等
- 思路：与上面一道题类似，只是需要修改输入与输出。
- 代码：```java
public boolean splitTwoParts(int[] nums){
//计算数组总和
int sum = 0;
for(int num:nums){
} int capacity = sum/2; int[] dp = new int[capacity+1]; for(int i=0;i<nums.length;i++){sum += num;
} return sum-2*dp[capacity]==0; } ```for(int j=capacity;j>=nums[i];j--){ dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);//装或不装的最大值 }
0/1背包问题
- 有为N件物品，它们的重量w分别是w1,w2,…,wn，它们的价值v分别是v1,v2,…,vn，每件物品数量有且仅有一个，现在给你个承重为M的背包，求背包里装入的物品具有的价值最大总和？
输入 物品数量N=5件 重量w分别是2 2 6 5 4 价值v分别是6 3 5 4 6 背包承重为M=10 输出 背包内物品最大总和为15代码：```java public int backPack(int[] w,int[] v,int n,int capacity) {
int[] dp = new int[capacity+1]; for(int i=0;i<n;i++){ for(int j=capacity;j>=w[i];j--){ dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]); } } return dp[capacity];} ```
零钱兑换
- 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1思路：
- 可以看作完全背包问题。每个物品的容量已知，可以选任意个。需要求恰好能把背包装满的最小数量。
- 采用自底向上的动态规划来做。
- 代码```java
class Solution {
//完全背包问题
public int coinChange(int[] coins, int amount) {
} } ```int[] dp = new int[amount+1]; Arrays.fill(dp,amount+1);//初始化为一个不可能的值 dp[0] = 0; //边界值 //自底向上 for(int i=0;i<coins.length;i++){ //物品个数 for(int j=coins[i];j<=amount;j++){ //容量 dp[j] = Math.min(dp[j],dp[j-coins[i]]+1); //计算最小硬币个数 } } return dp[amount]==amount+1?-1:dp[amount];
零钱兑换II
- 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个
输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1思路：
- 此题又可以看作完全背包问题，只不过求解目标不一样，该题是求组合数。
- dp[0] = 1,表示刚好消耗一张硬币就可以兑换成功。
- j需要从小到大进行遍历，因为硬币可以取多个相同面值。
- 代码：```java
//完全背包问题
public int change(int amount, int[] coins) {
} ```int[] dp = new int[amount+1]; dp[0] = 1; //刚好可以兑换，消耗1张硬币 for(int i=0;i<coins.length;i++){ for(int j=coins[i];j<=amount;j++){ dp[j] += dp[j-coins[i]]; } } return dp[amount];
多重背包问题
- 假设零食种类为n,每种零食有三个属性，分别是零食价格、满意度和零食数量。小明拥有价格为money的钱，想要在能承受的价格之内，吃到令自己满意度最高的食物。求最高满意度。如果不能买到零食，则返回-1；
- 思路：
- 此题容易有两种想法，其一是贪心算法，每次都选自己满意度最高的，选完再选下一种。但这种方式不能保证最后买到的零食是总满意度最高的。故此种想法不可取。
- 第二种是多重背包问题，因为每种物品的数量是有限的，所以介于01背包和完全背包之间。多重背包问题的转移方程如下：
%7C0%3C%3Dk%3C%3Dn%5Bi%5D#card=math&code=dp%5Bi%5D%5Bj%5D%20%3D%20Math.max%28dp%5Bi%5D%5Bj%5D%2Cdp%5Bi-1%5D%5Bj-k%2Ac%5Bi%5D%5D%2Bk%2Aw%5Bi%5D%29%7C0%3C%3Dk%3C%3Dn%5Bi%5D)
- 此题中
表示用j元钱买了i种零食所获得的最高满意度。零食价格对应容量数组c,零食满意度对应价值数组w,用现有钱能买的最大零食数量对应数量数组n
- 代码：```java import java.util.*;
public class Main {
//动态规划
//多重背包问题
public int getMaxCount(int[][] matrix,int n,int money){
int[][] dp = new int[n+1][money+1]; //用价钱j 购买了i种零食所获得的满意度
for (int i = 1; i <= n; i++) {
int num = matrix[i-1][2]; //零食数量
int price = matrix[i-1][0];//零食价格
int like = matrix[i-1][1]; //满意度
int count = Math.min(num,money/price);//能选择的最大数量
for(int j=price;j<=money;j++){
for(int k=0;k<=count;k++){
if(j>=k*price)
dp[i][j] = Math.max(dp[i][j],dp[i-1][j-k*price]+k*like);
}
}
}
return dp[n][money];
}
public static void main(String[] args) {
Main main = new Main();
Scanner sc = new Scanner(System.in);
int n = 3;
int money = 104;
int[][] matrix = {{26,100,4},{5,1,4},{5,2,2}};
System.out.println(main.getMaxCount(matrix, n, money));
}
}
- 由于代码中含有三重循环，运行时可能会超时，所以可以对上述代码进行优化：
-
<a name="ce60a163"></a>
### 折半
<a name="84f68586"></a>
#### 判断一个整数是否为回文数
- 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
-
输入: 121 输出: true
- 思路：
- 负数和末尾为0但非0的数一定不是回文数
- 只需要反转一半的数字即可
- 代码：```java
public boolean isPalindrome(int x) {
//负数一定不是回文数，若数的末尾是0，则首位也是0才是回文数，只有0满足条件
if(x<0||(x%10==0&&x!=0)){
return false;
}
//只需要一半数字就可以
int reverseNumber = 0;
while(x>reverseNumber){
reverseNumber = reverseNumber*10 + x % 10;
x = x/10;
}
//偶数时相等 1221 奇数时多一个数，需要除去 12321
return reverseNumber==x || reverseNumber/10==x;
}
0~n-1中缺失的数字
- 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
输入: [0,1,2,3,4,5,6,7,9] 输出: 8代码：```java //折半查找 public int missingNumber(int[] nums) { int left = 0; int right = nums.length; while(left<right){
int mid = left + (right-left)/2; //没有缺失 if(nums[mid]==mid){ left = mid + 1; } //缺失 else{ right = mid; }} return left; } ```
设计sqrt函数
- 计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。思路：二分法
- 求中间数字的平方，若小于等于x,则更新答案，并移动left.
- 若大于x,则移动right
代码：```java public int mySqrt(int x) { int left = 0; int right = x; int ans = -1; //注意终止条件 while(left<=right){
int mid = left+(right-left)/2; if((long)mid*mid<=x){ ans = mid; //更新结果 left = mid+1; }else{ right = mid-1; }} return ans; } ```
带精度的平方根
- 代码:```java
public float mySqrt(int n,float e) {
} ```float left = 0; float right = n; float ans = -1; //注意终止条件 while(left<right){ float mid = left+(right-left)/2; //结果比n大，且大的程度超过了精度，就需要缩小右边界 if(mid*mid>n+e){ right = mid; //结果比n小，且小的程度也超过了精度，就需要扩大左边界 }else if(n-mid*mid>e){ left = mid; }else{ ans = mid; break; } } return ans;
小张刷题计划
- 小张选中了n道题目，编号从0-n-1。在m天内按照题目编号顺序刷完所有的题目。在小张刷题计划中，小张需要用 time[i] 的时间完成编号 i 的题目。此外，小张还可以使用场外求助功能，通过询问他的好朋友小杨题目的解法，可以省去该题的做题时间。为了防止“小张刷题计划”变成“小杨刷题计划”，小张每天最多使用一次求助。
- ```bash 输入：time = [1,2,3,3], m = 2
输出：3
解释：第一天小张完成前三题，其中第三题找小杨帮忙；第二天完成第四题，并且找小杨帮忙。这样做题时间最多的一天花费了 3 的时间，并且这个值是最小的
- 思路：
- 第一时间需要想到贪心算法和二分查找（关键词：顺序或连续）。二分查找用来缩小范围的。
- 首先确定left=0,right=总时间，然后使用二分查找，判断当前中间值能否在day组内分完。若可以，那么就缩小右边界，否则扩大左边界。最后返回左边界的值。
- 代码：```java
class Solution {
//判断每组累加和在limit范围内，能否在day组内分完
public boolean check(int limit,int[] time,int day){
int useDay; //已经使用的天数
int totalTime;//当前天数内的总时间
int maxTime;//当前范围的最大值
useDay = 1; totalTime = maxTime = 0;
for(int i=0;i<time.length;i++){
//下一个待加入的时间，取当前最大值和当前时间中较小的值
//根据题目，较大的会被减去
int nextTime = Math.min(maxTime,time[i]);
//若当前时间+待加入时间在limit范围内
if(nextTime+totalTime<=limit){
totalTime += nextTime;
maxTime = Math.max(maxTime,time[i]);
}else{
++useDay;
totalTime = 0;
maxTime = time[i];//把没有加入成功的时间计入maxTime
}
}
return (useDay<=day);
}
//二分查找+贪心
public int minTime(int[] time, int m) {
int left,right,middle;
left = right = 0;
for(int i=0;i<time.length;i++){
right+= time[i];
}
//平均值
while(left<=right){
middle = (left+ right)/2;
//如果可以切分，就缩小右边界
if(check(middle,time,m)) right = middle-1;
else left = middle+1;
}
return left;
}
}
分割数组的最大值
- 给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
- ```bash 输入: nums = [7,2,5,10,8] m = 2
输出: 18
解释: 一共有四种方法将nums分割为2个子数组。 其中最好的方式是将其分为[7,2,5] 和 [10,8]， 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
- 思路：
- 二分查找（关键词连续）。在判断每组和<=limit且能否分为m组时需要注意，如果新的组的元素值超过了limit，那么就不能被分进去。这是与上一题的区别点。上一题可以去掉最大值的。
- 代码：```java
import java.util.*;
public class Main {
//判断每组总和<=limit，能否分为m组
public boolean canSplit(int limit,int[] nums,int m){
int group = 1;//组数
int curSum = 0;//当前和
for(int i=0;i<nums.length;i++){
if(curSum+nums[i]<=limit){
curSum += nums[i];
}else{
curSum = nums[i];//重新初始化当前和
if(curSum>limit) return false; //不能被分组
group++;
}
}
return group<=m;
}
public int splitArray(int[] nums, int m) {
int left = 0;
int right = 0;
for(int i=0;i<nums.length;i++){
if(nums[i]==Integer.MAX_VALUE) return nums[i];
right += nums[i];
}
while(left<=right){
int mid = left+(right-left)/2;
if(canSplit(mid,nums,m)) {
right = mid-1;
}
else left = mid+1;
}
return left;
}
public static void main(String[] args) {
Main main = new Main();
int[] nums ={1,Integer.MAX_VALUE};
int m = 2;
System.out.println(main.splitArray(nums, m));
}
}
爱吃香蕉的珂珂
- 珂珂喜欢吃香蕉。这里有
N堆香蕉，第i堆中有piles[i]根香蕉。警卫已经离开了，将在H小时后回来。珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在H小时内吃掉所有香蕉的最小速度K（K为整数）。 - 思路：
- 二分法，这里的左右边界是速度，左边界的下界是1，因为速度不可能为0.右边界是这堆香蕉中的最大数目。
- 每次折半的时候，需要判断以当前速度limit能否吃完这堆香蕉，如果吃掉消耗时间大于h，则返回false.否则返回true.
- 代码：```java
//贪心+二分
public int minEatingSpeed(int[] piles, int H) {
} //判断能否在h小时内，以速度limit吃完这堆香蕉 private boolean canEat(int limit, int[] piles, int h) {int left = 1;//速度最小，左边界 int right = 0;//右边界,速度最大 for(int i=0;i<piles.length;i++){ right = Math.max(piles[i],right); } //寻找吃掉每堆香蕉最合适的速度 while(left<right){ int mid = left+(right-left)/2; if(canEat(mid,piles,H)) right = mid; //速度太快了 else left = mid+1; //速度慢 } return left;
} ```int group = 0; //只能把一堆吃完了才行，且不能连续吃两堆 for(int i=0;i<piles.length;i++){ if(piles[i]<=limit){ group++; }else{ group += piles[i]/limit; if(piles[i]%limit>0) group++; } if(group>h) return false; } return group<=h;
稀疏数组搜索
- 稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta" 输出：-1 说明: 不存在返回-1。思路：
- 使用二分查找，跳过空字符串，若mid所在的位置刚好对应空字符串，就往右遍历，直到遇到非空字符串。然后将s与mid所指向字符串比较，并缩小边界。
- 代码：```java
class Solution {
//折半查找
public int findString(String[] words, String s) {
} } ```int left = 0; int right = words.length-1; while(left<=right){ //跳过空串 while(words[left].equals("")) left++; while(words[right].equals("")) right--; int mid = left+(right-left)/2; //如果中间是空字符，则向右边移动，直到遇到非空字符 while(words[mid].equals("")){ mid++; } //进行比较，缩小范围 if(words[mid].compareTo(s)>0){ right = mid-1; }else if(words[mid].compareTo(s)<0){ left = mid+1; }else{ return mid; } } return -1;
栈
判断括号是否有效
- 给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效 输入: "()[]{}" 输出: true思路:用栈来解决
- 遇到左括号就入栈
- 遇到右括号,如果栈不为空并且栈顶与右括号配对,就出栈.否则返回false
- 返回栈是否为空
- 代码:```java
public boolean isValid(String s) {
} ```if(s.length()==0) return true; Stack<Character> stack = new Stack(); stack.push(s.charAt(0)); for(int i=1;i<s.length();i++){ if(s.charAt(i)=='('||s.charAt(i)=='{'||s.charAt(i)=='['){ stack.push(s.charAt(i)); } if(s.charAt(i)==')'){ if(stack.isEmpty() || stack.peek()!='(') return false; stack.pop(); //弹出即可 }else if(s.charAt(i)=='}'){ if(stack.isEmpty() || stack.peek()!='{') return false; stack.pop(); //弹出即可 }else if(s.charAt(i)==']'){ if(stack.isEmpty() || stack.peek()!='[') return false; stack.pop(); //弹出即可 } } return stack.isEmpty();
栈排序
- 栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
输入： ["SortedStack", "push", "push", "peek", "pop", "peek"] [[], [1], [2], [], [], []] 输出： [null,null,null,1,null,2]代码：```java //维护两个栈，原栈为降序，辅助栈为升序 class SortedStack {
Deque
s1; Deque s2; public SortedStack() {
s1 = new ArrayDeque<>();//原栈为降序 s2 = new ArrayDeque<>();//辅助栈为升序}
public void push(int val) {
//如果当前元素大于原栈栈顶元素，需要将栈中小于当前元素的数组弹出栈， while(!s1.isEmpty()&&s1.peekLast()<val){ s2.offerLast(s1.pollLast()); } //如果当前元素小于辅助栈栈顶元素，需要将辅助栈元素弹出 while(!s2.isEmpty()&&s2.peekLast()>val){ s1.offerLast(s2.pollLast()); } s1.offerLast(val);}
public void pop() {
//将辅助栈数据全部弹出 while(!s2.isEmpty()) { s1.offerLast(s2.pollLast()); } s1.pollLast();}
public int peek() {
//将辅助栈数据全部弹出 while(!s2.isEmpty()){ s1.offerLast(s2.pollLast()); } return s1.isEmpty()?-1:s1.peekLast();}
public boolean isEmpty() {
return s1.isEmpty()&&s2.isEmpty();} } ```
接雨水
- 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
- 思路:单调栈
- 栈用来存储柱子的下标
- 若栈顶的柱子高度大于当前柱子的高度,说明不会有凹陷,接不了雨水.并将当前柱子的下标入栈
- 若栈顶柱子的高度小于当前柱子的高度,说明有凹陷.需要弹出栈顶柱子,若弹出的过程中遇到与栈顶高度相同的柱子也一起弹出.然后每弹出一种高度较小的柱子就需要计算它与当前柱子能接的雨水面积.直到栈顶高度大于当前柱子的高度.
代码:```java public int trap(int[] height) {
Stack<Integer> stack = new Stack<>(); //单调栈保存柱子的位置 if(height.length==0) return 0; stack.push(0); int res = 0; for(int i=1;i<height.length;i++){ //如果栈顶元素大于当前柱子的高度,说明接不了雨水 if(height[stack.peek()]>height[i]){ stack.push(i); }else{ //否则说明有凹陷的地方，可以接雨水 while(!stack.isEmpty() && height[stack.peek()]<height[i]){ int curIndex = stack.pop(); //栈顶元素一直相等，就继续pop while(!stack.isEmpty() && height[curIndex]==height[stack.peek()]){ stack.pop(); //弹出 } //计算能接到雨水的面积 if(!stack.isEmpty()){ int top = stack.peek();//左边界位置 //当前块能接的雨水高度被左右边界限定，取左右边界的最小值-当前块的高度 int h = Math.min(height[top],height[i])-height[curIndex]; int w = i-top-1; res += h*w; } } stack.push(i); } } return res;} ```
简易计算器
- 表达式仅包含非负整数，
+，-，*，/四种运算符和空格 。 整数除法仅保留整数部分。 输入: " 3+5 / 2 " 输出: 5思路：
- 设op是操作数num的前一个操作符。初始为+。
- op为+可以把num入栈。为-表示把-num入栈
- op=*或/ 时可以弹出栈顶元素与num进行运算，然后再入栈
- 代码：```java
//不带括号，可以顺序扫描表达式求值
public int calculate(String s) {
} ```s = s.trim();//去除前后空格 char[] chs = s.toCharArray(); Stack<Integer> digit = new Stack<>(); //操作数栈 int num = 0; char op = '+'; //表示num的前一个操作符 for (int i = 0; i < chs.length; i++) { if(chs[i]==' ') continue; if(Character.isDigit(chs[i])){ num = num*10+chs[i]-'0'; } //如果不是数字或已经走到最后一个字符了 if(!Character.isDigit(chs[i])||i==chs.length-1){ switch (op){ case '+': digit.push(num); break; case '-': digit.push(-num); break; case '*': int num1 = digit.pop(); digit.push(num1*num); break; case '/': num1 = digit.pop(); digit.push(num1/num); break; } op = chs[i]; //更新操作符 num = 0; //重新初始化num } } //最后只需要计算加法 int res = 0; while (!digit.isEmpty()){ res += digit.pop(); } return res;
基本计算器
- 实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式可以包含左括号(，右括号)，加号+，减号-，非负整数和空格 。 - 思路：
- 利用栈来存储括号中的结果，先压入符号sign,(+1代表正数，-1代表负数) 再压入结果result。
- 先把运算符左边的结果计算出来，然后遇到左括号，就先把result压入栈中，重新设置result=0，sign=1。遇到右括号就先计算操作符右边的值，再弹出栈中的元素，添加到当前结果result中。并初始化操作数。
- 代码```java
class Solution {
//栈
public int calculate(String s){
}Stack<Integer> stack = new Stack<>();//存放左括号里面的值 int operand = 0; //操作符左边的操作数 int result = 0; //当前结果 int sign = 1; //正负号，+1表示正数 -1表示负数 for(int i=0;i<s.length();i++){ char ch = s.charAt(i); if(Character.isDigit(ch)){ operand = 10 * operand+ch-'0'; }else if(ch=='+'){ result += sign*operand;//先计算运算符左边的值 sign = 1; operand = 0; //初始化操作数 }else if(ch=='-'){ result += sign*operand; sign = -1; operand = 0; }else if(ch=='('){ //将之前计算的结果和符号入栈 stack.push(result); stack.push(sign); //重新设置结果 sign = 1; result = 0; }else if(ch==')'){ result += sign*operand; //先恢复符号 result *= stack.pop(); result += stack.pop(); operand = 0; //初始化操作数 } } return result + (sign*operand);
}
<a name="bd6899f2"></a>
#### 逆波兰表达式求值
- 根据[ 逆波兰表示法](https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437)，求表达式的值。有效的运算符包括 `+`, `-`, `*`, `/` 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
- ```bash
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
- 思路：
- 逆波兰表达式又称后缀表达式，运算规则是先将所有的数字入栈，然后遇到运算符就弹出栈顶的两个元素，进行运算。完成后压入栈中。继续遍历，直到遍历完后缀表达式。
- 前缀表达式的计算与后缀表达式一致，只不过扫描顺序是从右到左。
- 代码：```java
class Solution {
public int evalRPN(String[] tokens) {
} //进行两个操作数的运算 public int compute(char op,int num1,int num2){Stack<Integer> stack = new Stack<>(); for (int i = 0; i < tokens.length; i++) { if(isDigitForString(tokens[i])){ stack.push(Integer.valueOf(tokens[i])); }else{ //遇到运算符就出栈 int num2 = stack.pop(); int num1 = stack.pop(); stack.push(compute(tokens[i].charAt(0),num1,num2)); } } return stack.peek();
} //判断字符串是否是数字 public boolean isDigitForString(String str){int res = 0; switch (op){ case '+': res = num1+num2; break; case '-': res = num1-num2; break; case '*': res = num1 * num2; break; case '/': res = num1 / num2; break; } return res;
} } ```for (int i = 0; i < str.length(); i++) { if(Character.isDigit(str.charAt(i))){ return true; } } return false;
贪心算法
跳跃游戏
- 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。思路:
- 若当前位置在当前能跳的最远位置内,则计算新的最远位置.
- 若新的最远位置超过了终点,就一定可以跳到.
- 代码:```java
public boolean canJump(int[] nums) {
} ```int right = 0;//当前能达到的最远位置 for(int i=0;i<nums.length;i++){ //若当前位置在最远位置内 if(i<=right) { //计算新的能跳到的最远位置 right = Math.max(right, i + nums[i]); //若新的最远位置超过了终点，就返回true if(right>=nums.length-1) return true; } } return false;
跳跃游戏II
- 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置.
输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。思路:
- 从第一个位置遍历到倒数第二个位置,因为最后一个位置不需要起跳.
- 设置旧边界和新的边界,每次跳的时候计算新边界的值,若当前位置达到了旧边界,那么需要更新旧边界,并且跳数+1.
- 代码:```java
//贪心
public int jump(int[] nums) {
} ```int right = 0; //最远位置 int steps = 0; //跳跃次数 int oldRight = 0; //旧的最远位置 //不需要算最后一个位置，因为不需要起跳了 for(int i=0;i<nums.length-1;i++){ right = Math.max(right,i+nums[i]); if(i==oldRight){ steps ++; oldRight = right; } } return steps;
怪物攻击
- 怪物分布在x轴上，主角可以在某个位置发起攻击，攻击范围为[x-y,x+y],在此范围内的所有怪物血量都减少1.问主角最少发动多少次攻击才能消灭所有怪物？
3 5 # 怪物数量为3，攻击范围为5 1 10 # 第一个怪物位置为1，血量为10 10 5 22 3思路：将所有怪物距离排序，然后利用贪心算法解答。
- 注意每次遍历的是左边界，而不是中间那个位置 ```java import java.util.*;
public class Main {
public int minOperator(int[][] monsters,int n,int x){
//计算最大距离
int maxLen = 0;
for (int i = 0; i < monsters.length; i++) {
maxLen = Math.max(maxLen,monsters[i][0]);
}
//使用排序的哈希表来存放怪物位置和血量
//key=距离 value= 血量
Map
for(int i=0;i<n;i++){
map.put(monsters[i][0],monsters[i][1]);
}
int res = 0;//攻击次数
//怪物位置
Integer[] distances = map.keySet().toArray(new Integer[] {});
for(int i=0;i<distances.length;i++){
if(map.get(distances[i])==0) continue; //如果当前位置怪物血量为0，则跳过
//否则进行攻击，当前怪物的位置是左边界，而不是中心
int j = i+1;
while(j<distances.length && distances[j]<=distances[i]+2*x){
//后面在攻击范围内的怪物所受攻击等于当前怪物或后面怪物的较小的血量
int hp = Math.min(map.get(distances[j]),map.get(distances[i]));
map.put(distances[j],map.get(distances[j])-hp);
j++;
}
//攻击次数
res += map.get(distances[i]);
//当前怪物血量为0
map.put(distances[i],0);
}
return res;
}
public static void main(String[] args) {
Main main = new Main();
int[][] monsters = {{1,10},{10,5},{22,3}};
int n = 3;
int x = 5;
System.out.println(main.minOperator(monsters, n, x));
} }
<a name="473b5e5d"></a>
#### 剪绳子
- 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]_k[1]_...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18
-
输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36 注意m>1,意思是至少切一下
- 思路:
- 代码:```java
public int cuttingRope(int n) {
//长度为2分为两个1
if(n==2) return 1;
//长度为3可以分为1和2
if(n==3) return 2;
int res = 1;//最大乘积
//其他长度就进行三等分,保留的最后一段可能为2,3,4三种情况
while(n>4){
n = n-3;
res *= 3;
}
//n是最后剩下的长度
return res*n;
}
柠檬水找零
- 在柠檬水摊上，每一杯柠檬水的售价为
5美元.顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。如果你能给每位顾客正确找零，返回true，否则返回false。 输入：[5,5,5,10,20] 输出：true 解释： 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零，所以我们输出 true。代码:```java public boolean lemonadeChange(int[] bills) {
int m_5 = 0; //5元数量 int m_10 = 0; //10元数量 for(int bill:bills){ if(bill==5){ m_5++; } if(bill==10){ m_10++; if(m_5<0) return false; m_5--; } if(bill==20){ m_20++; //有5元和10元的情况 if(m_5>0&&m_10>0){ m_10--; m_5--; //只有5元且数量>=3的情况 }else if(m_5>=3){ m_5-=3; }else{ //其他情况 return false; } } } return true;} ```
回合制攻击
- 你在玩一个回合制角色扮演的游戏。现在你在准备一个策略，以便在最短的回合内击败敌方角色。在战斗开始时，敌人拥有HP格血量。当血量小于等于0时，敌人死去。一个缺乏经验的玩家可能简单地尝试每个回合都攻击。但是你知道辅助技能的重要性。
在你的每个回合开始时你可以选择以下两个动作之一：聚力或者攻击。
聚力会提高你下个回合攻击的伤害。
攻击会对敌人造成一定量的伤害。如果你上个回合使用了聚力，那这次攻击会对敌人造成buffedAttack点伤害。否则，会造成normalAttack点伤害。
给出血量HP和不同攻击的伤害，buffedAttack和normalAttack，返回你能杀死敌人的最小回合数。 输入 13 血量 3 normalAttack 5 buffedAttack 输出 5 最小回合数代码：```java import java.util.*; public class Main{ //贪心算法 public int minRound(int hp,int normalAtk,int bufferAtk){
int res = 0; //蓄力攻击伤害更高，使用蓄力攻击 if(bufferAtk>=2*normalAtk){ res = hp/bufferAtk*2; hp = hp%bufferAtk;//剩余血量 if(hp==0) return res; if(hp<=normalAtk){ res++; }else{ res += 2; //使用蓄力攻击 } }else{ //普通攻击伤害更高 res = hp/normalAtk; hp = hp%normalAtk; //剩余血量 if(hp>0) res++; //剩余血量大于0，再使用一次普攻 } return res;} public static void main(String[] args){
Main main = new Main(); Scanner sc = new Scanner(System.in); int hp = sc.nextInt(); int normalAtk = sc.nextInt(); int bufferAtk = sc.nextInt(); System.out.println(main.minRound(hp,normalAtk,bufferAtk));} } ```
寻找子串
- 给出m个字符串S1，S2，…，Sm和一个单独的字符串T。请在T中选出尽可能多的子串同时满足： 1）这些子串在T中互不相交。 2）这些子串都是S1，S2，…，Sm中的某个串。 问最多能选出多少个子串。
3 # 子串个数 aa b ac bbaac # 主串思路：
- 先使用KMP算法找出子串在主串中所有可能的出现位置区间。
- 然后利用贪心算法，找出尽可能多的不相交的区间。类似活动安排问题。
代码：```java import java.util.*; public class Main{ //求模式串在主串中出现的所有位置区间 private static int[][] intervals = new int[500000][2]; private static int k = 0;//下标 //求模式串的next数组 public static void getNext(int[] next,String t){
int j = 0; int k = -1; next[0] = -1; while(j<t.length()-1){ if(k==-1||t.charAt(j)==t.charAt(k)){ next[++j]=++k; }else{ k = next[k]; //回溯 } }}
public static void KMP(String s,String t){
int[] next = new int[t.length()]; int i=0,j=0; getNext(next,t);//求next数组 while(i<s.length()){ if(j==-1||s.charAt(i)==t.charAt(j)){ i++; j++; }else j = next[j]; //j回退 //返回子串在主串中的出现位置 if(j==t.length()){ intervals[k++] = new int[]{i-j,i-1}; j = 0; //重新置为0 } }}
//只保留不相交的区间 活动时间表 public static int merge(int[][] intervals){
int count = 0; int tail = -1; //将所有区间按照右边界进行排序 Arrays.sort(intervals,(o2, o1) -> o2[1]-o1[1]); for (int i = 0; i < intervals.length; i++) { //若数组为空或当前区间的左边界大于结果集中最后一个区间的右边界则是不相交的 if(intervals[i][0]>tail){ count++; tail = intervals[i][1]; } } return count;}
public static void main(String[] args){
Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String[] t = new String[n]; for(int i=0;i<n;i++){ t[i] = sc.next(); } String s = sc.next(); //寻找各个子串在主串中的区间 for(int i=0;i<n;i++){ // findSubString(s,t[i]); KMP(s,t[i]); } intervals = Arrays.copyOf(intervals,k); //合并所有相交的区间 System.out.println(merge(intervals));} } ```
有效括号的嵌套深度
- 有效括号字符串 定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。详情参见题末「有效括号字符串」部分。
输入：seq = "()(())()" 输出：[0,0,0,1,1,0,1,1] 解释：本示例答案不唯一。 按此输出 A = "()()", B = "()()", max(depth(A), depth(B)) = 1，它们的深度最小。 像 [1,1,1,0,0,1,1,1]，也是正确结果，其中 A = "()()()", B = "()", max(depth(A), depth(B)) = 1 。思路：要使两个栈的深度差最小，就需要把连续的左括号分到不同的栈中。如果不连续，说明可以弹出栈中的左括号了，嵌套深度减少，直到遇到下一个左括号。
- 代码：
//保证连续的左括号不分配在同一组
public int[] maxDepthAfterSplit(String seq) {
char[] chars = seq.toCharArray();
int[] res = new int[seq.length()];
int depth = 0; //嵌套深度
for (int i = 0; i < chars.length; i++) {
//保证连续的左括号不分在同一组
if(chars[i]=='('){
depth++;
res[i] = depth%2;
}else{
res[i] = depth%2;
depth--;//如果不是连续的左括号，嵌套深度一直减下去，直到遇到左括号
}
}
return res;
}
加油站
- 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。 输入: gas = [1,2,3,4,5] cost = [3,4,5,1,2] 输出: 3 解释: 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油 开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。 因此，3 可为起始索引。思路:贪心算法,统计每个加油站剩余的油量，累加剩余油量，找到最小的剩余油量，那么它的下一个一定是起点。
- 代码:```java
public int canCompleteCircuit(int[] gas, int[] cost) {
} ```//贪心算法 //找到累计剩余油量最少的加油站，那么它的下一个一定是起点 int len = gas.length; int minSpare = Integer.MAX_VALUE; int minIndex = 0; int spare = 0; //当前剩余油量 for(int i=0;i<len;i++){ spare += gas[i]-cost[i]; if(spare<minSpare){ minSpare = spare; minIndex = i; } } return spare>=0?(minIndex+1)%len:-1;
电梯问题
- 搭电梯人数为n,容量为k,每个人的目的地不同，怎样乘坐电梯才能达到他们对应的楼层，且花费时间最少。电梯需要从1层上去，然后回到1层。
输入 3 2 # 人数 容量 2 3 4 # 目的地 输出 8 # 先坐到4楼，再下3楼，然后回到1层。去载最后一个人，不用返回。思路：
- 先对每个人的目的地由大到小排序，然后每次选K个人搭载，需要往返。最后不足K个人一趟就搭载完毕。
- 代码：```java import java.util.*;
public class Main { public int getMinPrice(int[] nums,int k){ //降序 int[] nums1 = new int[nums.length]; Arrays.sort(nums); for (int i = 0; i < nums1.length; i++) { nums1[i] = nums[nums.length-1-i]; } //人数凑个整 int ans = 0; int len = nums1.length%k==0?nums1.length:(nums1.length/k+1) *k; //统计做电梯的代价 for (int i = 0; i < len; i+=k) { ans += getSum(nums1,i,i+k); } return ans; } //单次乘坐电梯所需要的最小花费 public int getSum(int[] nums,int start,int end){ end = Math.min(nums.length-1,end); //取最小值，最后1趟载不满的情况 int sum = nums[start]-1;//坐到最高层需要的代价 for(int i=start+1;i<=end;i++){ sum+= Math.abs(nums[i-1]-nums[i]);//下行时，停在指定楼层需要的代价 } //送完最后一个人回到第一层 sum+=nums[end]-1; return sum; }
public static void main(String[] args) {
Main main = new Main();
int[] nums = {2,3,4};
int k = 3;
System.out.println(main.getMinPrice(nums, k));
}
}
<a name="246ce79f"></a>
#### 坏了的计算器
- 在显示着数字的坏计算器上，我们可以执行以下两种操作：<br />双倍（Double）：将显示屏上的数字乘 2；<br />递减（Decrement）：将显示屏上的数字减 1 。<br />最初，计算器显示数字 X。<br />返回显示数字 Y 所需的最小操作数。
- ```bash
输入：X = 5, Y = 8
输出：2
解释：先递减，再双倍 {5 -> 4 -> 8}.
- 思路：
- 采用贪心算法，逆向思维，
, $ x—==Y++$,
- Y如果是偶数就除2，如果是奇数就+1变成偶数.这样做操作次数更小。
- 采用贪心算法，逆向思维，
- 代码：```java
class Solution {
//贪心算法
public int brokenCalc(int X, int Y) {
} } ```int count = 0; //X*2 可以替换为Y/2 X-- 可以替换为Y++ while(Y>X){ //如果Y是奇数，先执行加法 if((Y&1)==1){ Y++; }else{ //Y是偶数时，需要先执行除法 Y/=2; } count++; } return count+X-Y;
双指针
合并排序的数组
- 给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。初始化 A 和 B 的元素数量分别为 m 和 n。
- ```java 输入: A = [1,2,3,0,0,0], m = 3 B = [2,5,6], n = 3
输出: [1,2,2,3,5,6] A.length == n + m
- 代码:```java
//逆向双指针
public void merge(int[] A, int m, int[] B, int n) {
if(n==0) return;
int pa = m-1;
int pb = n-1;
int tail = m+n-1;
while(pa>=0||pb>=0){
//A数组没有元素了，就拷贝B
if(pa==-1){
A[tail] = B[pb--];
}
//B数组没有元素了，就拷贝A
else if(pb==-1){
A[tail] = A[pa--];
}
//都有元素时，选择较大的元素放入A的尾部
else if(A[pa]>B[pb]){
A[tail] = A[pa--];
}else{
A[tail] = B[pb--];
}
tail--;
}
}
颜色分类
- 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]代码：```java //三个指针 public void sortColors(int[] nums) {
int left = 0; //0的最右边界 int right = nums.length-1; //2的最左边界 //只需要交换0和2的位置即可 for(int i=0;i<nums.length&&i<=right;){ //遇到0交换 if(nums[i]==0){ swap(nums,i,left); left++; } //遇到2也交换 if(nums[i]==2){ swap(nums,i,right); right--; }else{ i++; //遇到1才移动 } }}
public void swap(int[] nums,int index1,int index2){
int temp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = temp;} ```
最短无序连续子数组
- 给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。思路：
- 双指针，只需要遍历一遍数组即可。从左往右找升序数组，max是升序数组的最大值，若当前元素小于max,就记录下它的位置，以它的位置为右边界。从右往左找降序数组，min是降序数组的最小值，若当前元素大于min,就记录它的位置，以它为左边界。
- ans = 右边界-左边界+1；
- 代码：```java
class Solution {
//双指针
public int findUnsortedSubarray(int[] nums) {
} } ```int len = nums.length; int max = nums[0]; //上界 int min = nums[len-1]; //下界 int l = 0,r=-1;//初始化保证值可以为0 for(int i=0;i<len;i++){ //从左往右遍历，找不符合升序的元素的下标 // 若不是升序，记录当前元素的下标，以它为右边界 if(max>nums[i]){ r = i; }else{ max = nums[i]; //如果是升序的就更新上界 } //从右往左遍历，找不符合降序的元素的下标 //若不是降序，就记录当前元素的下标，以它为左边界 if(min<nums[len-i-1]){ l = len-i-1; }else{ min = nums[len-i-1];//如果是降序的就更新下界 } } return r-l+1;
动态规划
买卖股票的最佳时机
- 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。注意：你不能在买入股票前卖出股票。
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。思路：动态规划
- 股票有两种状态，分别是持有股票1和不持有股票0，状态转移图如下：
- 状态转移方程：```bash
设 dp[i][k][j] i代表当前天数 k代表交易次数，买入和卖出算一次交易 j是股票状态 取值为0或1
dp[i][k][0] # 第i天，剩余交易次数为k,不持有股票的利润 dp[i][k][1] # 第i天，剩余交易次数为k,持有股票的利润状态转移方程
dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]) # 前一天不持有股票的利润和前一天持有股票但今天卖出的利润的最大值 dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]) # 前一天持有股票的利润和前一天不持有股票但今天买入的利润的最大值，注意这里买入算一次交易次数边界条件
dp[-1][k][0] = 0 # 未开始交易不持有股票利润为0 dp[-1][k][1] = Integer.MIN_VALUE # 未开始交易持有股票，不可能 dp[i][0][0] = 0 # k=0表示禁止交易，利润为0 dp[i][0][1] = Integer.MIN_VALUE # 禁止交易但持有股票，不可能 ```
- 股票有两种状态，分别是持有股票1和不持有股票0，状态转移图如下：
代码：```java public int maxProfit(int[] prices) {
int dp_0 = 0; //不持有股票 int dp_1 = Integer.MIN_VALUE; //持有股票 for(int i=0;i<prices.length;i++){ dp_0 = Math.max(dp_0,dp_1+prices[i]); dp_1 = Math.max(dp_1,-prices[i]); } return dp_0;} ```
买卖股票含冷冻期
- 允许多次交易，你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
思路：
bash dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])# 第i-1天卖出了，需要隔一天才能进行买入 dp[i][1] = max(dp[i-1][1],dp[i-2][0]-prices[i])# 第i天选择buy时要从第i-2天状态转移代码：```java public int maxProfit(int[] prices) {
int dp_0 = 0; int dp_1 = Integer.MIN_VALUE; int dp_pre = 0; //保存前一天的利润 for(int i=0;i<prices.length;i++){ int t = dp_0; //保存当天利润 dp_0 = Math.max(dp_0,dp_1+prices[i]); dp_1 = Math.max(dp_1,dp_pre-prices[i]); dp_pre = t; //更新前一天的利润 } return dp_0;} ```
买卖股票的最佳时机II
- 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 思路：
bash dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])# 第i-1天卖出了，需要隔一天才能进行买入 dp[i][1] = max(dp[i-1][1],dp[i-2][0]-prices[i])# 第i天选择buy时要从第i-2天状态转移代码：```java public int maxProfit(int[] prices) {
int dp_0 = 0; int dp_1 = Integer.MIN_VALUE; for(int i=0;i<prices.length;i++){ dp_0 = Math.max(dp_0,dp_1+prices[i]); dp_1 = Math.max(dp_1,dp_0-prices[i]); } return dp_0;} ```
买卖股票的最佳时机III
思路
bas dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]) dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])代码：```java public int maxProfit(int[] prices) {
int n = prices.length; int k = 2;//交易次数 int[][][] dp = new int[n+1][k+1][2]; //天数 for(int i=1;i<=n;i++){ //边界条件 交易次数为0时不允许交易 dp[i][0][0] = 0; dp[i][0][1] = Integer.MIN_VALUE; //交易次数 for(int j=k;j>0;j--){ //边界条件 天数为0时 dp[0][j][0] = 0; dp[0][j][1] = Integer.MIN_VALUE; //状态方程 dp[i][j][0] = Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]); dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]); } } return dp[n][k][0]; //第n天交易了k次不持有股票的利润} ```
买卖股票的最佳时机IV
- 思路：
- 注意k分情况讨论：若k>n/2，那么可以看作是k有无限次。(买入和卖出至少需要两天)
- 否则按k次进行计算
代码```java //不限制交易次数时的最大利润 public int maxProfit(int[] prices){
int dp_0 = 0; int dp_1 = Integer.MIN_VALUE; for(int i=0;i<prices.length;i++){ dp_0 = Math.max(dp_0,dp_1+prices[i]); dp_1 = Math.max(dp_1,dp_0-prices[i]); } return dp_0;}
public int maxProfit(int k, int[] prices) {
int n = prices.length; //若交易次数超过n/2可以看作无限次交易 if(k>n/2){ return maxProfit(prices); } int[][][] dp = new int[n+1][k+1][2]; //天数 for(int i=1;i<=n;i++){ //边界条件 交易次数为0时不允许交易 dp[i][0][0] = 0; dp[i][0][1] = Integer.MIN_VALUE; //交易次数 for(int j=k;j>0;j--){ //边界条件 天数为0时 dp[0][j][0] = 0; dp[0][j][1] = Integer.MIN_VALUE; //状态方程 dp[i][j][0] = Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]); dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]); } } return dp[n][k][0]; //第n天交易了k次不持有股票的利润} ```
最小路径和
- 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。思路：
- 因为该题存在重复子问题，故使用动态规划解题。
代码：```java //动态规划，保存之前所有步到当前步的最小路径数字 public int minPathSum(int[][] grid) {
if(grid.length==0||grid[0].length==0) return -1; int rows = grid.length; int cols = grid[0].length; int[][] dp = new int[rows][cols]; dp[0][0] = grid[0][0]; //左上角 for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ if(i==0&&j==0) continue; else if(i==0) dp[i][j] = dp[i][j-1]+grid[i][j]; //上边界，只能从左边来 else if(j==0) dp[i][j] = dp[i-1][j]+grid[i][j];//左边界，只能从上面来 else{ //其他情况，等于往下走或往上走的最短路径+当前路径 dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j]; } } } return dp[rows-1][cols-1];} ```
打靶问题
- 一个射击运动员打靶，靶一共有10环，打10枪打中90环的可能性有多少种?
- 代码：```java
/**
- 动态规划
- @param n 开枪次数
- @param target 目标环数
- @return
/
public int gunsPossibility(int n,int target){
//dp[i][j]保存射击i次能得j分的情况
int[][] dp = new int[n+1][10n+1];
//第一把，0-10环可能性
for(int j=0;j<=10;j++){
} //计算达到目标环数的可能性 for(int i=2;i<=n;i++){//轮次dp[1][j] = 1;
} return dp[n][target]; } ```for(int j=0;j<=i*10;j++){//当前轮次所有可能的分数 for(int k=0;k<=10;k++) { //0到10环 if(j-k<0) break; dp[i][j] += dp[i-1][j-k]; } }
打家劫舍II
- 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
输入: [2,3,2] 输出: 3 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。思路:
- 把环状排列的房子转化为两个单排列的房子，因为最后一家和第一家是相连的。所以一种排列是第一家到倒数第二家。另外一种排列是第二家到最后一家。
- 使用滚动数组来对dp数组进行优化，节约空间
- 代码：```java
//动态规划
//把环状排列的房子转化为两个单排列的房子
public int rob(int[] nums){
} //动态规划求解 public int getRob(int[] nums) {int len = nums.length; if(len==0) return 0; if(len==1) return nums[0]; return Math.max(getRob(Arrays.copyOfRange(nums,0,len-1)), getRob(Arrays.copyOfRange(nums,1,len)));
} ```int pre = 0; //dp[n-2] int cur = 0;//dp[n-1] int temp; for (int num : nums) { temp = cur; cur = Math.max(pre+num,cur); //dp[n] = max(dp[n-2]+nums[i],dp[n-1]) pre = temp; } return cur;
打家劫舍III
- 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
```bash 输入: [3,2,3,null,3,null,1]
3 / \ 2 3 \ \ 3 1
输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
- 思路：
- 考点是树形结构的动态规划。如果是用自顶向上，那么需要有额外空间来存储已经访问过的结点值，避免重复访问。
- 此题可以采用自底向上的动态规划。假设每个结点就两个状态值，选或不选。
- 假设当前结点是根节点，那么选了根节点就不能选它的两个子树。不选根节点，最大价值就等于左子树和右子树能提供的最大价值。不一定是要选择左子树或右子树的根节点。
- 代码：```java
public int rob(TreeNode root){
int[] rootStatus = dfs(root);
return Math.max(rootStatus[0],rootStatus[1]);
}
private int[] dfs(TreeNode root) {
if(root==null) return new int[]{0,0};
//注意这里是自底向上的，利用了动态规划的思想
int[] l = dfs(root.left);
int[] r = dfs(root.right);
//选了根节点就不能选左子树和右子树
int selected = root.val + l[1] + r[1];
//不选根节点就可以选左子树和右子树的最大价值。注意最大价值不一定要选中左子树或右子树的根节点
int notSelected =Math.max(l[0],l[1]) + Math.max(r[0],r[1]);
return new int[] {selected,notSelected};
}
最长公共子序列(不要求连续)
- 给定两个字符串
text1和text2，返回这两个字符串的最长公共子序列的长度。 输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，它的长度为 3。思路：动态规划
- 代码:```java
class Solution {
//最长公共子序列 动态规划
public int longestCommonSubsequence(String text1, String text2) {
} } ```int m = text1.length(); int n = text2.length(); int[][] dp = new int[m+1][n+1]; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(text1.charAt(i-1)==text2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]+1; }else{ dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); } } } return dp[m][n];
最长公共子串（要求连续）
- 给定两个字符串s和t,返回两个字符串的最长公共子串。
输入： s="acbcf" t="abcbced" 输出： "cbc"思路：动态规划
- 代码：```java
public class Main { public String getLCS(String s,String t){ //dp[i][j]表示s的前i个字符和t的前j个字符的公共子序列的长度 int[][] dp = new int[s.length()+1][t.length()+1]; int maxLen = 0,maxEnd = 0;//记录公共串的长度和结束位置 for (int i = 1; i <= s.length(); i++) { for (int j = 1; j <= t.length(); j++) { if(s.charAt(i-1)==t.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]+1; }else{ dp[i][j] = 0; //对应位置不相等时，公共子序列长度=0 } if(dp[i][j]>maxLen){ maxLen = dp[i][j]; maxEnd = i; } } } return s.substring(maxEnd-maxLen,maxEnd);//前闭后开 }
public static void main(String[] args) {
Main main = new Main();
String s = "abcdef";
String t = "defg";
System.out.println(main.getLCS(s, t));
}
}
<a name="ba91031a"></a>
#### 三步问题
- 三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
- ```bash
输入：n = 3
输出：4
说明: 有四种走法
- 思路：
- 这种题乍一看与硬币兑换的方案数比较相似，但实际上两者是不同的问题。走楼梯问题跟顺序很有关系，顺序不同，方案数就不同。但硬币兑换就与顺序无关了。比如示例的3，其中 2,1 和 1,2算两种方案，而对硬币兑换来说只有一种。
- 代码：```java
class Solution {
public int waysToStep(int n) {
} } ```int[] steps = {1,2,3}; int[] dp = new int[n+1]; dp[0] = 1; //刚好可以下去，消耗一种方案 for(int j=1;j<=n;j++){ for(int i=0;i<steps.length;i++){ if(j>=steps[i]) { dp[j] += dp[j - steps[i]]; dp[j] = dp[j] % 1000000007; } } } return dp[n];
最大子序和
- 给定一个整数数组
nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。代码:```java class Solution { public int maxSubArray(int[] nums) {
if(nums.length==0) return 0; int maxValue = Integer.MIN_VALUE; int curSum = Integer.MIN_VALUE;//保存当前和 for(int i=0;i<nums.length;i++){ if(curSum>0){ curSum+=nums[i]; }else{ curSum =nums[i];//若当前和小于0,则重新从nums[i]开始 } maxValue = Math.max(maxValue,curSum); } return maxValue;} } ```
求矩阵的最大子矩阵和
输入： 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 输出： 15 # 代表的是子矩阵3x2 {{9,2},{-4,1},{-1,8}}的最大和思路：
- 将二维的矩阵转化为一维子序列，然后求最大和。
- 转化方式三重for循环，第一重循环表示子矩阵的最大高度（底）。第二重循环表示子矩阵当前高度，第三重循环表示子矩阵的列。
- 第一重循环中初始化一个nums[]数组，用来存储得到的子矩阵。通过对应列的数据相加将k维的子矩阵折叠程一维nums[]数组。
- 然后对nums[]数组求最大子序和。
- 代码：```java package com.qmh;
import java.util.ArrayDeque; import java.util.Arrays; import java.util.Queue;
public class Main {
//通过三重循环来列举所有可能的子矩阵，这些子矩阵都变成一维的，它们代表的是k维度子矩阵，只不过对应和被加起来了。
//通过寻找这些一维矩阵的最大和，就可以得到子矩阵的最大和
public int subMaxMatrix(int[][] matrix){
int maxValue = Integer.MIN_VALUE;
//i是最大高度
for(int i=0;i
public static void main(String[] args) {
Main main = new Main();
int[][] matrix = {{9,2,-6,2},{-4,1,-4,1},{-1,8,0,-2}};
System.out.println(main.subMaxMatrix(matrix));
for (int i = 0; i < matrix.length; i++) {
System.out.println(Arrays.toString(matrix[i]));
}
}
}
<a name="06c21ddc"></a>
#### 最大子矩阵
- 给定一个正整数和负整数组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
- ```java
输入:
[
[-1,0],
[0,-1]
]
输出: [0,1,0,1]
解释: 输入中标粗的元素即为输出所表示的矩阵
- 思路：
- 此题在上面一道题的基础上进行了小小的修改，变成求最大子矩阵的左上角坐标和右下角坐标。
- 左边的行号是i-j 即起始行，左边的列号是最大子序和的起点，右边的行号是子矩阵的底即i,右边的列号是最大自序和的终点，即k.
- 代码：```java
class Solution {
public int[] getMaxMatrix(int[][] matrix) {
} } ```//记录最大和的子矩阵的左上角和左下角坐标 int[] ans = null; int maxSum = Integer.MIN_VALUE; //将其转化为一维的子序列，求最大子序和 //最大高度 for (int i = 0; i < matrix.length; i++) { int[] nums = new int[matrix[i].length]; //存放子序列 //所能达到的高度 for (int j = 0; j <= i; j++) { //所在的列 int curSum = 0; int leftCol = 0; for (int k = 0; k < matrix[j].length; k++) { nums[k] += matrix[i-j][k];//i-j是起始行,k是当前列 //求最大子序和 curSum += nums[k]; if(curSum<=nums[k]){ curSum = nums[k]; leftCol = k; } if(curSum>maxSum){ maxSum = curSum; ans = new int[] {i-j,leftCol,i,k}; } } } } return ans;
生存人数
- 给定N个人的出生年份和死亡年份，第i个人的出生年份为birth[i]，死亡年份为death[i]，实现一个方法以计算生存人数最多的年份。
你可以假设所有人都出生于1900年至2000年（含1900和2000）之间。如果一个人在某一年的任意时期都处于生存状态，那么他们应该被纳入那一年的统计中。例如，生于1908年、死于1909年的人应当被列入1908年和1909年的计数。 输入： birth = {1900, 1901, 1950} death = {1948, 1951, 2000} 输出： 1901思路：
- 先用一个数组记录每个年份变动的人数，如果某年有人出生，那就自增1，若某年有人死亡，则对下一年减一。
- 然后使用动态规划，记录到当前年份为止的存活人数。并用两个变量保存最大存活人数和存活年份。
- 代码：```java
class Solution {
public int maxAliveYear(int[] birth, int[] death) {
} } ```int[] nums = new int[102]; //存放各个年份变动的人数 int n = birth.length; for(int i=0;i<n;i++){ nums[birth[i]-1900]++; nums[death[i]+1-1900]--; //下一年才去世 } //动态规划 int maxLive = 0; //最大生存人数 int year = 0; int curLive = 0;//当前生存人数 for(int i=0;i<nums.length;i++){ curLive += nums[i]; if(curLive>maxLive){ maxLive = curLive; year = i+1900; } } return year;
编辑距离
- 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
- 你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')思路：
- 二维动态规划
- 需要初始化，分别考虑word1为空和word2为空的情况。
- 转移方程如下
- 二维动态规划
代码：```java class Solution { public int minDistance(String first, String second) {
int n = first.length(); int m = second.length(); int[][] dp = new int[n+1][m+1]; //初始化 second为空串时 for(int i=0;i<=n;i++){ dp[i][0] = i; } //初始化 first为空串时 for(int j=0;j<=m;j++){ dp[0][j] = j; } //dp[i][j]表示将first的前i个字符转换为second的前j个字符所需的最小交换次数 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(first.charAt(i-1)==second.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1; } } } return dp[n][m];}
public int min(int a,int b,int c){
return Math.min(Math.min(a,b),c);} } ```
恢复空格
- 哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子”I reset the computer. It still didn’t boot!”已经变成了”iresetthecomputeritstilldidntboot”。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。
输入： dictionary = ["looked","just","like","her","brother"] sentence = "jesslookedjustliketimherbrother" 输出： 7 解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。思路：
- 动态规划,不适合用贪心，因为 abcdef，{“abcd”,”ab”,”def”}, 其中”ab” 和”def”能匹配的字符个数要比“abcd”更多一些。
- dp[i]表示前i个字符中未匹配的最少字符个数。dp[i] = dp[i-1]+1
- 遍历前i个字符，以idx为开头，判断以idx开始，并以i结尾的字符串是否出现在字典中，若是，则更新dp[i]的值。dp[i] = min(dp[i], dp[idx]);
- 由于第二步耗时比较大，可以使用字典树进行优化。字典树存储具有相同后缀的字符串，只需要统计每个字符串的起始位置返回即可。
- 动态规划,不适合用贪心，因为 abcdef，{“abcd”,”ab”,”def”}, 其中”ab” 和”def”能匹配的字符个数要比“abcd”更多一些。
代码：```java class Solution { //动态规划 public int respace(String[] dictionary, String sentence) {
Set<String> dict = new HashSet<>(Arrays.asList(dictionary)); int len = sentence.length(); int[] dp = new int[len+1];//记录前i个字符中不能匹配的最少字符个数 for (int i = 1; i <= len; i++) { dp[i] = dp[i-1]+1; //假设第i个字符不能匹配 //遍历前i个字符，若以其中某一个下标idx为开头，以i结尾的字符串正好在字典里面，就更新dp[i]; for(int idx = 0;idx<i;idx++){ if(dict.contains(sentence.substring(idx,i))){ dp[i] = Math.min(dp[i],dp[idx]); } } } return dp[len];} } ```
代码：```java import javafx.util.Pair;
import java.util.ArrayList; import java.util.Arrays; import java.util.List;
class TrieNode{ TrieNode[] childs; boolean isWord; public TrieNode(){ childs = new TrieNode[26]; } } public class Main{
public int replace(String[] dictionary,String sentence){
TrieNode root = new TrieNode();
for (String word : dictionary) {
insert(root,word);
}
int n = sentence.length();
int[] dp = new int[n+1];
for(int i=1;i<=n;i++){
dp[i] = dp[i-1]+1;
//通过字典树来寻找单词的前缀，比依次遍历要节约时间
List<Integer> indices = search(root, sentence, i-1);
for (Integer index : indices) {
dp[i] = Math.min(dp[i],dp[index]);
}
}
return dp[n];
}
//构建后缀树
public void insert(TrieNode root,String word){
TrieNode node = root;
for(int i=word.length()-1;i>=0;i--){
int idx = word.charAt(i)-'a';
if(node.childs[idx]==null){
node.childs[idx] = new TrieNode();
}
node = node.childs[idx];
}
node.isWord = true;
}
//查询sentence中以endPos为结尾的单词，返回这些单词的开头下标
public List<Integer> search(TrieNode root,String sentence, int endPos){
TrieNode node = root;
List<Integer> indices = new ArrayList<>();
for(int i=endPos;i>=0;i--){
int idx = sentence.charAt(i)-'a';
if(node.childs[idx]==null) {
break;
}
node = node.childs[idx];
if(node.isWord) {
indices.add(i);
}
}
return indices;
}
public static void main(String[] args) {
Main main = new Main();
String[] dictionary = {"looked","just","like","her","brother"};
String sentence = "jesslookedjustliketimherbrother";
System.out.println(main.replace(dictionary, sentence));
}
}
<a name="6dba4a3a"></a>
#### 回文子串
- 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
- ```bash
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
思路：
- 动态规划，使用dp数组来保存区间i到j是否是回文串，若
- 转移方程：
- 动态规划，使用dp数组来保存区间i到j是否是回文串，若
代码```java class Solution { //动态规划 public int countSubstrings(String s) {
int len = s.length(); boolean[][] dp = new boolean[len][len]; //表示区间j到i的字符串是否是回文串 //主对角线上的字符都是回文串 for(int i=0;i<len;i++){ dp[i][i] = true; } int count = s.length(); //至少单个字符都是回文串 for(int j=1;j<len;j++){ for(int i=0;i<j;i++){ if(s.charAt(i)!=s.charAt(j)){ dp[i][j] = false; }else{ //区间长度为3 if(i+1==j){ dp[i][j] = true; }else{//区间长度>3 dp[i][j] = dp[i+1][j-1]; } if(dp[i][j]) count++; } } } return count;} } ```
最长上升子序列
- 给定一个无序的整数数组，找到其中最长上升子序列的长度
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。思路：
- dp[i]表示以nums[i]结尾的上升子序列的长度,全部初始化为1，1个字符显然是长度为1的上升子序列。
- 遍历到nums[i]时，需要把下标i之前的所有数重新遍历一遍，选择可以形成上升序列的最大长度。
代码：```java class Solution { public int lengthOfLIS(int[] nums) {
int len = nums.length; int[] dp = new int[len]; //初始化 Arrays.fill(dp,1); int ans = 0; for(int i=0;i<len;i++){ for(int j=0;j<i;j++){ //nums[i]之前的所有数据都需要遍历一遍 if(nums[i]>nums[j]){ dp[i] = Math.max(dp[i],dp[j]+1); //选择所能形成的上升序列的最大长度 } } ans = Math.max(ans,dp[i]); //最大长度 } return ans;} } ```
思路2：贪心算法+二分查找
- 代码：```java
class Solution {
//贪心+二分
public int lengthOfLIS(int[] nums) {
} } ```int len = nums.length; if(len==0) return 0; //tail 长度为i+1的上升子序列的末尾元素最小是几 int[] tail = new int[len]; int end = 0; //tail的最后一个元素的索引 tail[0] = nums[0]; for(int i=1;i<len;i++){ //若当前元素大于最末尾元素则直接追加上去 if(nums[i]>tail[end]){ end++; tail[end] = nums[i]; }else{ //使用二分查找，在有序数组tail中找到nums[i]的插入位置，并插入 int mid = Arrays.binarySearch(tail,0,end,nums[i]); if(mid<0){ tail[-mid-1] = nums[i]; } } } return end+1;
最长递增子序列的个数
- 给定一个未排序的整数数组，找到最长递增子序列的个数。
- ```java 输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
- 思路：
- 有两个动态规划数组，dp[n]和count[n]分别保存最大递增子序列的长度和个数。
- 最后统计count数组中最大递增子序列长度=maxlen的所有个数之和。
- 代码：```java
//动态规划
public int findNumberOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n]; //存放第i个元素及之前的最大递增子序列长度
int[] count = new int[n]; //存放最大递增子序列个数
int maxLen = 0;
//初始化
Arrays.fill(dp,1);
Arrays.fill(count,1);
//遍历数组
for(int i=0;i<n;i++){
//遍历i前面的子数组
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
if(dp[j]+1>dp[i]){
dp[i] = Math.max(dp[i],dp[j]+1);
count[i] = count[j]; //最大递增子序列个数不变
}else if(dp[j]+1==dp[i]){
count[i] += count[j];//长度相同则个数需要增加
}
}
}
maxLen = Math.max(maxLen,dp[i]);
}
//统计最大递增子序列的个数
int res = 0;
for(int i=0;i<n;i++){
if(dp[i]==maxLen) res+=count[i];
}
return res;
}
马戏团人塔
- 有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110] 输出：6 解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)思路：
- 逆向思维，此题相当于求最长上升子序列的长度，不过这个序列有两个维度的变量：身高和体重，需要固定一个，然后变化另外一个，将其减少为只关注体重的最长上升子序列。具体做法是按照身高升序排列，注意如果身高一样的是不能选的，所以我们把身高一样的，对体重进行降序排序。这样保证不会有两个身高一样的人出现在最长上升子序列中。
- 由于使用动态规划求最长上升子序列长度超时了，故本地使用贪心+二分来求最长上升子序列长度。
- 代码：```java
//动态规划
public int bestSeqAtIndex(int[] height, int[] weight) {
} ```int n = height.length; int[][] persons = new int[n][2]; for(int i=0;i<n;i++){ persons[i][0] = height[i]; persons[i][1] = weight[i]; } //按照身高升序，若身高相同就按体重降序 Arrays.sort(persons,(a,b)->(a[0]==b[0]?b[1]-a[1]:a[0]-b[0])); //求最长递增子序列的个数 （只需要关注体重即可，因为身高已经符合条件了） //贪心+二分 int[] tail = new int[n]; tail[0] = persons[0][1]; //只有1个人时，它就是最末尾的位置 int end = 0; //最后一个元素的索引位置 for(int i=0;i<n;i++){ //遇到体重更大的，直接添加进上升子序列中 if(persons[i][1]>tail[end]){ end++; tail[end] = persons[i][1]; }else{ //使用折半查找，将当前人的体重插入到tail的升序数组中，使其保持有序。 //若当前人的体重已经存在于tail中就不用管 int mid = Arrays.binarySearch(tail,0,end,persons[i][1]); //mid = -(插入点+1) 那么插入点就是 -mid-1 if(mid<0) { tail[-mid-1] = persons[i][1]; } } } return end+1;
堆箱子
- 堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。
输入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]] 输出：10思路：
- 此题是求最大上升子序列的和，而不是长度，适合用动态规划解决。
- 先对箱子数组按照宽度升序，宽度相同则按照深度降序。这样可以提高求解效率。
- dp[i]表示堆到第i个箱子时的最大高度。
- 代码：```java
class Solution {
public int pileBox(int[][] box) {
} } ```//按照宽度升序 Arrays.sort(box,(a,b)->(a[0]==b[0]?b[1]-a[1]:a[0]-b[0])); int len = box.length; int[] dp = new int[len];//存储第i个箱子时的最大高度 int maxHeight = 0; for(int i=0;i<len;i++){ dp[i] = box[i][2]; //初始化 i为顶，所以高度至少为box[i][2] for(int j=i-1;j>=0;j--){ //宽度、深度和高度必须严格小于第i个箱子 if(box[j][0]<box[i][0]&&box[j][1]<box[i][1]&&box[j][2]<box[i][2]){ dp[i] = Math.max(dp[i],dp[j]+box[i][2]);//之前箱子的高度+当前箱子的高度的最大值 } } maxHeight = Math.max(dp[i],maxHeight); } System.out.println(Arrays.toString(dp)); return maxHeight;
最大黑方阵
- 给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。 输入: [ [1,0,1], [0,0,1], [0,0,1] ] 输出: [1,0,2] 解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵思路：
- 三维的动态规划，
最后两维表示以(i,j)作为右下角的矩阵的左边和上边连续0的个数
- 在构建dp数组的时候，需要判断能构成的最大子方阵的合法性，若不合法，则减少边长，直到合法。
- 三维的动态规划，
- 代码：```java
class Solution {
//动态规划
public int[] findSquare(int[][] matrix) {
}int rows = matrix.length; int cols = matrix[0].length; int maxSize = -1; //dp[i][j][0] i,j左边连续0的个数（包括自身） //dp[i][j][1] i,j上边连续0的个数（包括自身） //统计以当前坐标为右下角的左侧连续1的个数和上侧连续1的个数 int[][][] dp = new int[rows+1][cols+1][2]; int[] ans = new int[3]; for (int i = 1; i<=rows; i++) { for (int j = 1; j<=cols;j++) { if(matrix[i-1][j-1]==0){ dp[i][j][0] = 1+dp[i][j-1][0];//左边 dp[i][j][1] = 1+dp[i-1][j][1];//上边 int side = Math.min(dp[i][j][0],dp[i][j][1]);//最大可能的边长 //若不能构成方阵，则减少边长 //缩小i看上边的0的个数是否大于等于边长 缩小j看左边的0的个数是否大于等于边长 while(dp[i][j-side+1][1]<side||dp[i-side+1][j][0]<side){ side--; } if(maxSize<side){ //从前往后算，故不需要更新最大值 maxSize = side; ans = new int[]{i-side,j-side,side}; } } } } if(maxSize==-1) return new int[0]; return ans;
}
<a name="a4ffa4a7"></a>
#### 第k个数
- 有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
- ```bash
输入: k = 5
输出: 9
- 思路：
- 此题和求丑数的题目本质是一样的，我们使用dp数组来保存所有已经排好序的数，以空间换时间找出答案。
- 创建三个索引记录某三个素数的位置，在它们之前的元素乘以3，5，7得到的结果都比现有结果小，在它之后的元素乘以3，5，7的结果比它要大。我们只考虑最接近的解。
- 注意可能有不同素数乘以3，5，7的结果是一样的，为了避免记录重复结果，我们使用if条件进行判断。只要符合目前的解，就让对应的下标进行移动。
代码：```java class Solution { //动态规划 //每次从3个候选数中选出1个，然后让其对应下标+1 public int getKthMagicNumber(int k) {
int[] dp = new int[k+1]; dp[0] = 1; int s3=0, s5=0, s7=0; //记录某个素数的下标 for(int i=1;i<k;i++){ dp[i] = getMin(dp[s3]*3,dp[s5]*5,dp[s7]*7); //使用if而不使用else if是为了跳过相同结果 比如 15=3*5=5*3 此时 3和5对应下标都要+1 if(dp[i]==dp[s3]*3){ s3++; } if(dp[i]==dp[s5]*5){ s5++; } if(dp[i]==dp[s7]*7){ s7++; } } return dp[k-1];}
public int getMin(int a,int b,int c){
return Math.min(a,Math.min(b,c));} } ```
预测赢家
- 给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
输入：[1, 5, 2] 输出：False 解释：一开始，玩家1可以从1和2中进行选择。 如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。 所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。 因此，玩家 1 永远不会成为赢家，返回 False 。思路：
- 该题是二维的动态规划。
- 当只剩下一个元素时，那么dp一定是当前元素的值。若i<j,那么当前玩家可以选最左边的元素i也可以选最右边的元素j,选了之后要去减去前一盘的结果，因为前一盘当前玩家不是先手。最后取两种方案的最大值即可。
- 该题是二维的动态规划。
- 代码：```java
class Solution {
public boolean PredictTheWinner(int[] nums) {
} } ```int n = nums.length; int[][] dp = new int[n][n]; //dp[i][j]表示当前剩下的数为i..j时，先手-后手的差值 for(int i=0;i<n;i++){ dp[i][i] = nums[i]; } for(int i=n-1;i>=0;i--){ for(int j=i+1;j<n;j++){ //当前选手可以选最左边的元素 并留下 i+1..j int a = nums[i]-dp[i+1][j]; //当前选手可以选最左边的元素 并留下 i..j-1 int b = nums[j]-dp[i][j-1]; dp[i][j] = Math.max(a,b); } } for (int i = 0; i < dp.length; i++) { System.out.println(Arrays.toString(dp[i])); } return dp[0][n-1]>=0;
目标和
- 给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
- ```bash 输入：nums: [1, 1, 1, 1, 1], S: 3 输出：5 解释：
-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
- 思路1： 暴力求解，列举出所有可能性
- 代码：```java
class Solution {
//暴力求解
int count = 0;
public int findTargetSumWays(int[] nums, int S) {
dfs(nums,0,S);
return count;
}
public void dfs(int[] nums,int index,int S){
//满足条件，所有数字都用上了
if(S==0&&index==nums.length) count++;
if(index<nums.length) {
dfs(nums, index + 1, S + nums[index]);
dfs(nums, index + 1, S - nums[index]);
}
}
}
- 思路2：动态规划 转化为01背包问题
- 将正数分为1组，总和为x, 负数分为一组总和为y（绝对值）
- 可以得到如下关系式 x+y=sum x-y=S
- 解出 x=(sum+S)/2 将x作为背包的容量，根据容量是整数的特征，表明sum+S不能是奇数
- 从数组中选出能塞满x的方案数即可
- 代码：```java
class Solution {
//转化为01背包问题
//设所有符号为负的数总和设置为一个背包的容量 y
//所有符号为正的数总和设置为一个背包的容量 x
//x+y = sum x-y = S x = (sum+S)/2
//找到能填满x的方法数即可
public int findTargetSumWays(int[] nums, int S) {
} } ```int n = nums.length; //求数组总和 int sum = 0; for (int num : nums) { sum += num; } //目标和不能超过总和 if(S>Math.abs(sum)){ return 0; } //背包容量应该是偶数，奇数不满足要求 if((sum+S)%2==1) return 0; int capacity = (sum+S)/2; int[] dp = new int[capacity+1]; dp[0] = 1; //01背包问题 for (int i = 0; i < nums.length; i++) { for(int j=capacity;j>=nums[i];j--){ dp[j] += dp[j-nums[i]]; } } return dp[capacity];
并查集
地铁打卡活动
- 地铁迷在某个城市组织了地铁打卡活动。活动要求前往该城市中的所有地铁站进行打卡。打卡可以在站外或者站内进行。地铁的计价规则如下：只要不出站，就不计费；出站时，只计算进站和出站站点的距离。如在同一个站点进出站，按照最低票价 a 元计算。假设地铁票不会超时。大部分站点都是通过地铁线连通的，而且地铁站的连通是双向的（若 A，B 连通，则 B，A连通），且具有传递性的（若 A，B 连通，且 B，C 连通，则 A，C连通）。但并不是所有的地铁站都相互连通，在不能通过坐地铁达到的两个地点间，交通的花费则提高到 b 元。地铁迷从酒店起点出发，再回到酒店。假设从酒店到达任意地铁站的交通花费为 b 元。请计算地铁迷完成打卡最小交通花费。
输入 8 7 3 6 #n，m，a，b其中n表示地铁站点数，m表示连通的地铁站点对数，a代表地铁最低票价，b代表非地铁方式票价 0 1 # hi，ti 表示hi和ti站点是连通的 1 2 2 3 0 3 4 5 5 6 4 7 输出 24代码：```java class Union{ //并查集 public int[] parent;
//初始化,每个节点的父节点都是自身 public Union(int[] nums){
parent = new int[nums.length]; for(int i=0;i<nums.length;i++){ parent[i] = nums[i]; }}
//找到某个节点的父节点 public int findParent(int x){
if(parent[x]==x) return x; return findParent(parent[x]); //找其父节点的父节点}
//节点合并 public void merge(int x,int y){
//先分别找到两个节点的父节点 int x1 = findParent(x); int y1 = findParent(y); parent[y1] = x1;} }
public class Main {
public int minPrice(int[][] matrix,int n,int a,int b){
int[] stations = new int[n];
for(int i=0;i<n;i++){
stations[i] = i;
}
Union union = new Union(stations);
for (int i = 0; i < matrix.length; i++) {
union.merge(matrix[i][0],matrix[i][1]);
}
//统计并查集的根节点数目，即不连通的站点数
int stationNum = 0;
for(int i=0;i<n;i++){
if(i==union.parent[i]){
stationNum++;
}
}
return a*stationNum+(stationNum-1)*b+2*b;
}
public static void main(String[] args) {
Main main = new Main();
int n = 8;//站点数
int m = 7; //连通站点数
int a = 3;//最低票价
int b = 6;//非地铁票价
int[][] matrix = {{0,1},{1,2},{2,3},{0,3},{4,5},{5,6},{4,7}};
System.out.println(main.minPrice(matrix, n,a,b));
}
}
<a name="d8b9fdd7"></a>
#### 紧急疏散
- 体育场突然着火了，现场需要紧急疏散，但是过道真的是太窄了，同时只能容许一个人通过。现在知道了体育场的所有座位分布，座位分布图是一棵树，已知每个座位上都坐了一个人，安全出口在树的根部，也就是1号结点的位置上。其他节点上的人每秒都能向树根部前进一个结点，但是除了安全出口以外，没有任何一个结点可以同时容纳两个及以上的人，这就需要一种策略，来使得人群尽快疏散，问在采取最优策略的情况下，体育场最快可以在多长时间内疏散完成。
- ```java
6 //结点数
2 1 //表示两个结点连通
3 2
4 3
5 2
6 1
//输出：
4
代码：```java import java.util.*; public class Main{ //并查集 private static int[] parent; // private static int[] depth; //每个结点到根节点的深度 private static int maxDepth=Integer.MIN_VALUE; //寻找根节点 public static int findParent(int x){
//使用了路径压缩，让根节点直接作为当前结点的父节点 return x==parent[x]?x:(parent[x]=findParent(parent[x]));} //合并 public static void merge(int x,int y){
//找到两个结点的父节点 int px = findParent(x); int py = findParent(y); //以y为根 parent[px] = py;} public static void main(String[] args){
Scanner sc = new Scanner(System.in); int n = sc.nextInt(); //已经在出口的情况 if(n==1){ System.out.println(0); return; } parent = new int[n+1]; for(int i=1;i<=n;i++){ parent[i] = i; //初始化 } for(int i=0;i<n-1;i++){ int x = sc.nextInt(); int y = sc.nextInt(); if(x==1||y==1) continue; merge(x,y); } //重新走一遍，让px的子节点指向py for (int i = 0; i <= n; i++) { findParent(i); } int[] ans = new int[n+1]; for (int i = 0; i < parent.length; i++) { ans[parent[i]]++; maxDepth = Math.max(maxDepth, ans[parent[i]]); } System.out.println(maxDepth);} } ```
水域大小
- 你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
输入： [ [0,2,1,0], [0,1,0,1], [1,1,0,1], [0,1,0,1] ] 输出： [1,2,4]思路：
- 通过并查集找到根节点的大小，排序后输出即可。
- 注意这里size数组不是秩，而是根节点数量。
- 代码：```java
class Union{
int[] parent = null;
int[] size = null; //节点数量
int count = 0; //根节点的数量
public Union(int n){
} //找到x的父节点 public int find(int x){this.parent = new int[n]; this.size = new int[n]; this.count = n; for (int i = 0; i < n; i++) { parent[i] = i; } Arrays.fill(size,1);
} //合并 以x为根 public void merge(int x,int y){if(parent[x]==x) return x; return find(parent[x]);
} }int px = find(x); int py = find(y); if(px==py) return; if(size[px]>=size[py]) { parent[py] = px; //以px作为新的根节点 size[px] += size[py]; }else if(size[px]<size[py]){ parent[px] = py; size[py] += size[px]; } this.count-=1;
class Solution {
//并查集
public int[] pondSizes(int[][] land) {
int rows = land.length;
int cols = land[0].length;
Union union = new Union(rowscols+1);
int dummyNode = rowscols; //使用一个虚拟节点
int[] dx = {1,0,1,1};
int[] dy = {0,1,-1,1};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
//从单点水域向四周扩展
if(land[i][j]==0){
for(int k=0;k<4;k++){
int x = i+dx[k];
int y = j+dy[k];
if(x<0||y<0||x>=rows||y>=cols||land[x][y]!=0) continue;
//将相邻水域合并
union.merge(icols+j,xcols+y); //合并
}
}else{
//将所有陆地都连接到虚拟节点上
union.merge(dummyNode,i*cols+j);
}
}
}
//最后统计水域面积
List
}
- 思路2： 使用dfs深度优先遍历，已经遍历过的节点直接进行标记，因为不会再走了。
- 代码：```java
class Solution {
//dfs
int count = 0;
public int[] pondSizes(int[][] land) {
int rows = land.length;
int cols = land[0].length;
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if(land[i][j]==0){
count = 0; //计数重新置为0
dfs(land,i,j,rows,cols);
if(count>0) {
ans.add(count);
}
}
}
}
Collections.sort(ans);
return ans.stream().mapToInt(Integer::valueOf).toArray();
}
int[] dx = {0,0,1,-1,1,-1,1,-1};
int[] dy = {1,-1,0,0,-1,1,1,-1};
public void dfs(int[][] land,int x,int y,int rows,int cols){
if(x<0||y<0||x>=rows||y>=cols||land[x][y]!=0) return;
land[x][y] = -1; //直接染色
count++;
//从8个方向搜索
for(int i=0;i<8;i++){
int xx = x+dx[i]; //这里注意一定不能改值，否则要回溯
int yy = y+dy[i];
dfs(land,xx,yy,rows,cols);
}
}
}
- 思路3：
- bfs广度有限遍历，先入队一个节点，在将它相邻的水域节点入队，并且将已访问的节点进行标记。
- 代码
//bfs public int[] pondSizes(int[][] land) { int[] dx = {0,0,1,-1,1,-1,1,-1}; int[] dy = {1,-1,0,0,-1,1,1,-1}; int rows = land.length; int cols = land[0].length; List<Integer> ans = new ArrayList<>(); for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if(land[i][j]==0){ //先将值为0的水域入队 Queue<Integer> queue = new ArrayDeque<>(); queue.offer(i*cols+j); land[i][j] = -1; //将已经访问过的节点进行标记 int count = 1; //计数 while(!queue.isEmpty()){ int locate = queue.poll(); int x = locate/cols; int y = locate%cols; //寻找与该水域相邻的水域 for(int k=0;k<8;k++){ int xx = x+dx[k]; int yy = y+dy[k]; if(xx<0||yy<0||xx>=rows||yy>=cols||land[xx][yy]!=0) continue; land[xx][yy] = -1; //已经访问过的进行标记 count++; //将新的节点入队 queue.offer(xx*cols+yy); } } ans.add(count); } } } Collections.sort(ans); return ans.stream().mapToInt(Integer::valueOf).toArray(); }
回溯
生成匹配的括号
- 括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合. 说明：解集不能包含重复的子集
输入：n = 3 输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ]代码:```java List
ans = new ArrayList(); //回溯 public void generateParenthesis(StringBuilder str, int left,int right){ //左括号数必须严格小于等于右括号 if(left>right){ return; } //满足条件，添加到结果中 if(left==0&&right==0) { ans.add(str.toString()); return; } if(left>0){ str.append("("); generateParenthesis(str,left-1,right); str.deleteCharAt(str.length()-1);//回溯 } if(right>0){ str.append(")"); generateParenthesis(str,left,right-1); str.deleteCharAt(str.length()-1);//回溯 }
}
public List<String> generateParenthesis(int n) {
StringBuilder str = new StringBuilder();
generateParenthesis(str, n,n);
return ans;
}
<a name="1eb42436"></a>
#### 全排列
- 给定一个 **没有重复** 数字的序列，返回其所有可能的全排列。
- ```java
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
- 代码:```java
List
ans,boolean[] visited){
} public Listif(ans.size()==nums.length){ res.add(new LinkedList<>(ans)); } for(int i=0;i<nums.length;i++){ if(visited[i]) continue; //已经被访问过的结点跳过 //添加结点 ans.add(nums[i]); visited[i] = true; //递归 permute(nums,ans,visited); //回溯 ans.removeLast(); visited[i] = false; }
} ```LinkedList<Integer> ans = new LinkedList<>(); boolean[] visited = new boolean[nums.length]; permute(nums,ans,visited); return res;
全排列II
- 给定一个可包含重复数字的序列，返回所有不重复的全排列。
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]思路:
- 首先要对数组进行升序排序,这一点特别重要.
- 然后定义一个boolean数组来记录结点是否被访问过.
- 剪枝的要点是如果当前元素值等于前一个元素值,且前一个结点已经被访问过了,就跳出当前循环.
- 回溯的时候要注意把boolean数组的值设置为false.
- 代码:```java
List
ans,boolean[] used){
} public Listif(ans.size()==nums.length){ res.add(new LinkedList<>(ans)); return; } for(int i=0;i<nums.length;i++){ if(used[i]) continue; //已经选过的数字就跳过 //剪枝 如果当前节点与前一个结点一样，并且它的前一个结点已经被遍历过了 if(i>0 && nums[i]==nums[i-1] && used[i-1]) break; ans.add(nums[i]); used[i] = true; permuteUnique(nums,ans,used); ans.removeLast(); //回溯 used[i] = false; }
} ```LinkedList<Integer> ans = new LinkedList<>(); //对待排序的列表进行升序排列 Arrays.sort(nums); boolean[] used = new boolean[nums.length]; permuteUnique(nums,ans,used); return res;
下一个排列
- 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 1,2,3,4,6,5,4,3 -> 1,2,3,4,3,4,5,6-> 1,2,3,5,3,4,4,6代码:```java //从低位向高位查找，发现连续两个数是升序排列 //将大数后面的所有数进行升序排列，然后将升序序列中大于小数的数和小数进行交换，返回 //若整个序列是降序的，则将所有数进行升序排列 public void nextPermutation(int[] nums) {
int len = nums.length; for(int i=len-1;i>0;i--){ //若发现连续两个数是升序排列 if(nums[i]>nums[i-1]){ Arrays.sort(nums,i,len); //将大数后面的数升序 //若升序序列的元素（大数）大于当前元素（小数）就交换，然后返回 for(int j=i;j<len;j++){ if(nums[j]>nums[i-1]){ int temp = nums[j]; nums[j] = nums[i-1]; nums[i-1] = temp; return; } } } } //降序排列变为升序排列 Arrays.sort(nums); return;} ```
幂集
- 幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。说明：解集不能包含重复的子集
输入： nums = [1,2,3] 输出： [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]思路：回溯+剪枝
代码：```java List
ans,int start){ //每次遍历都把新结果加入到结果集中 res.add(new ArrayList<>(ans)); for(int i=start;i<nums.length;i++){ ans.add(nums[i]); subsets(nums,ans,i+1); //每次从下一个元素开始，防止重复遍历已经走过的元素 ans.removeLast(); }} public List
boolean[] visited = new boolean[nums.length]; LinkedList<Integer> ans = new LinkedList(); subsets(nums,ans,0); return res;} ```
按键的排列组合
- 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合，按照字典序升序排序,如果有重复的结果需要去重。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
- 思路：回溯法，用start表示字符串数组中字符串的下标，只需要遍历每个字符串即可，若start==len(字符串数组)则将结果添加到结果集中，并返回，然后回溯。
代码：```java import java.util.*; public class Main { Map
list = new ArrayList<>(); //建立字典映射 public void buildDict(){ map.put(2,"abc"); map.put(3,"def"); map.put(4,"ghi"); map.put(5,"jkl"); map.put(6,"mno"); map.put(7,"pqrs"); map.put(8,"tuv"); map.put(9,"wxyz");}
public List
letterCombinations(String digits) { buildDict();//建立字典映射 String[] words = new String[digits.length()]; for(int i=0;i<digits.length();i++){ words[i] = map.get(digits.charAt(i)-'0'); } //回溯求排列组合 StringBuilder builder = new StringBuilder(); backTrack(words,0,builder); return list;}
public void backTrack(String[] words,int start, StringBuilder ans){
if(start==words.length){ list.add(ans.toString()); return; } for (int j = 0; j < words[start].length(); j++) { ans.append(words[start].charAt(j)); backTrack(words,start+1,ans); //回溯 ans.deleteCharAt(ans.length()-1); }}
public static void main(String[] args) {
Main main = new Main(); String str = "458"; List<String> list = main.letterCombinations(str); System.out.println(list.toString());} } ```
种树
- 小多想在美化一下自己的庄园。他的庄园毗邻一条小河，他希望在河边种一排树，共 M 棵。小多采购了 N 个品种的树，每个品种的数量是 Ai (树的总数量恰好为 M)。但是他希望任意两棵相邻的树不是同一品种的。小多请你帮忙设计一种满足要求的种树方案。
3 品种数量 4 2 1 每个品种的树的数量 输出： 1 2 1 2 1 3 1思路：
- 暴力递归+回溯+剪枝
- 从编号小的树种开始遍历，若某个树种的数量大于剩余数量的一半则返回，进行剪枝
- 若当前树种数量不为0，且没有被访问过，那么当前树种数量-1，并加入到结果集中。若当前树种被访问过，则遍历下一个树种
- 若这样的排列找不到最优序列则进行回溯。尝试下一个结点。
代码：```java import java.util.*; public class Main{ //暴力递归+回溯+剪枝 public boolean getTreePlan(int[] trees,int count,LinkedList
ans){ //树种全部被用完了 if(count==0){ return true; } //从小到大遍历每个品种 for(int i=0;i<trees.length;i++){ if(trees[i]*2>count+1){ //剪枝，当前树种的数量超过剩余数量的一半 return false; } //若当前树种的数量不为0，且最近没有被访问过 if(ans.size()==0||trees[i]>0&&ans.getLast()!=i+1) { trees[i]--; ans.add(i + 1); //递归 if (getTreePlan(trees, count - 1, ans)) { return true; //如果成立，提前返回 } //回溯 ans.removeLast(); trees[i]++; } } return false;}
public static void main(String[] args){
Main main = new Main(); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] trees = new int[n]; for(int i=0;i<n;i++){ trees[i] = sc.nextInt(); } int sum =0; for(int tree:trees){ sum += tree; } LinkedList<Integer> ans = new LinkedList<>(); if(main.getTreePlan(trees,sum,ans)){ for (int i = 0; i < ans.size(); i++) { System.out.print(ans.get(i)); if(i!=ans.size()) System.out.print(" "); } System.out.println(); }else{ System.out.println("-"); }}
}
<a name="3c3c08ca"></a>
#### 递增子序列
- 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2.
- ```bash
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
- ```java import java.util.*;
public class Main {
//回溯+剪枝
public List
public static void main(String[] args) {
int[] nums = {4,6,7,7};
Main main = new Main();
List<List<Integer>> lists = main.findSubsequences(nums);
for (List<Integer> list : lists) {
System.out.println(list.toString());
}
}
}
<a name="f235f8e1"></a>
#### 复原IP地址
- 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。<br />有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。
- ```bash
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
- 思路：
- 回溯+剪枝。
- 剪枝条件主要有两个，一个是判断剩余字符串长度能否构成合法的ip地址，第二个看ip段的值是否在255之内，且长度大于1时不能以0开头。
- 每个节点可以选择截取的方法只有三种，截1位、截2位、截3位，因此从每个节点生长出的分支最多有3个。
- ```java import java.util.*;
public class Main {
public List<String> restoreIpAddresses(String s) {
int len = s.length();
List<String> res = new ArrayList<>();
//长度不合法就不搜索
if(len<4||len>12) return res;
//存放ip地址
Deque<String> path = new ArrayDeque<>(4);
int splitTimes = 0;
//回溯+剪枝
dfs(s,len,splitTimes,0,path,res);
return res;
}
/**
* 回溯+剪枝
* @param s 字符串s
* @param len s的长度
* @param split 切割次数 不能超过3次
* @param i 当前遍历到的位置
* @param path 存储合法的ip地址
* @param res 最后的结果
*/
private void dfs(String s, int len, int split, int i, Deque<String> path, List<String> res) {
if(i==len){
//将ip地址添加到结果集中
if(split==4){
res.add(String.join(".",path));
}
return;
}
//剪枝 当前剩余字符串的长度不能再次切分成合法的ip地址就剪枝
if(len-i<(4-split)||len-i>3*(4-split)){
return;
}
//可能的ip某段的取值
for(int j=0;j<3;j++){
//最后一段ip可能的长度超过数组长度就终止
if(i+j>=len){
break;
}
//判断是否是一个合法的ip段
int ipSegment = judgeIpSegment(s,i,i+j);
if(ipSegment!=-1){
path.addLast(String.valueOf(ipSegment));
dfs(s,len,split+1,i+j+1,path,res);
path.removeLast();
}else{
continue; //不合法就剪枝
}
}
}
//判断是否是一个合法的ip段
private int judgeIpSegment(String s, int left, int right) {
int len = right-left+1;
//段的长度大于0时，不能以0开头
if(len>1&&s.charAt(left)=='0') return -1;
String subStr = s.substring(left, right + 1);
int ipSegment = Integer.parseInt(subStr);
if(ipSegment>255){
return -1;
}
return ipSegment;
}
public static void main(String[] args) {
Main main = new Main();
String s = "25525511135";
List<String> strings = main.restoreIpAddresses(s);
System.out.println(strings.toString());
}
}
<a name="304fe557"></a>
#### 迷路的机器人
- 设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。
- ```bash
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]
解释:
输入中标粗的位置即为输出表示的路径，即
0行0列（左上角） -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列（右下角）
class Solution { //dfs+回溯 List<List<Integer>> ans = new ArrayList<>(); public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) { //0表示空位置，1表示障碍物 List<List<Integer>> path = new ArrayList<>(); int rows = obstacleGrid.length; int cols = obstacleGrid[0].length; if(obstacleGrid[rows-1][cols-1]==1) return ans; //如果目的地走不通，就直接返回 backTrack(obstacleGrid,0,0,rows,cols,path); return ans; } public boolean backTrack(int[][] obstacleGrid,int i,int j,int rows,int cols,List<List<Integer>> path){ //边界 if(i<0||i>=rows||j<0||j>=cols) return false; //走到了目的地,且目的地是空位置 if(i==rows-1&&j==cols-1){ path.add(new ArrayList<>(Arrays.asList(i,j))); for (List<Integer> list : path) { ans.add(new ArrayList<>(list)); } path.remove(path.size()-1); return true; } //该位置可以走 if(obstacleGrid[i][j]==0){ //将当前位置加入结果集中 path.add(new ArrayList<>(Arrays.asList(i,j))); obstacleGrid[i][j] = 1; //已经访问过的节点设置为不再被访问 //尝试向右或向下移动 boolean res1 = backTrack(obstacleGrid,i+1,j,rows,cols,path); if(res1) return true; //如果向下走可以成功的话就返回该方案 boolean res2 = backTrack(obstacleGrid, i, j + 1, rows, cols, path); //走不通就回溯 path.remove(path.size()-1); return res2; }else{ return false; } } }
八皇后
- 设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
输入：4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释: 4 皇后问题存在如下两个不同的解法。 [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]代码：```java class Solution { //回溯法 public List
char[][] chs = new char[n][n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ chs[i][j] = '.'; } } List<List<String>> res = new ArrayList<>(); solveNQueens(chs,n,res,0); return res;}
public void solveNQueens(char[][] chs,int n,List
//终止条件 每行都有皇后 if(row==n){ res.add(chsToList(chs)); //保存当前结果 return; } for(int col=0;col<n;col++){ if(isValid(chs,row,col)){ chs[row][col] = 'Q'; solveNQueens(chs,n,res,row+1);//递归 chs[row][col] = '.'; //回溯 } }
}
//将字符数组变成list保存
public List<String> chsToList(char[][] chs){
List<String> ans = new ArrayList<>();
for (int i = 0; i < chs.length; i++) {
ans.add(new String(chs[i]));
}
return ans;
}
//判断放置的位置是否合法
private boolean isValid(char[][] chs, int x, int y) {
for (int i = 0; i <= x; i++) {
for (int j = 0; j < chs[0].length; j++) {
if(chs[i][j]=='Q'){
//若在同一行、同一列或对角线上就不合法
if(j==y||Math.abs(i-x)==Math.abs(j-y)){
return false;
}
}
}
}
return true;
}
}
<a name="ad278f03"></a>
#### 24点游戏
- 你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 `*`，`/`，`+`，`-`，`(`，`)` 的运算得到 24。注意除法不是整数除法。
- ```bash
输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24
- 思路：
- 挑出两个数，计算出1个数，取代原来的两个数，现在有三个数，
- 再挑出两个数，计算出1个数，取代它们，现在有两个数
- 最后计算两个数的结果
- 使用回溯+剪枝
- 计算两个数的时候加法和乘法不需要考虑顺序性，但除法和乘法需要考虑，所以有6种方案。
- 使用set集合保存。遍历结果，并与第三个数进行组合，形成两个数。
代码：```java class Solution { public boolean judgePoint24(int[] nums){
List<Double> numbers = new ArrayList<>(); for (int num : nums) { numbers.add((double)num); } return solve(numbers);}
private boolean solve(List
numbers) { //指剩下一个数的时候判断结果 if(numbers.size()==1){ return Math.abs(numbers.get(0)-24)<1e-6;//看看是否与24相等 } for (int i = 0; i < numbers.size(); i++) { for (int j = 0; j < numbers.size(); j++) { if(i!=j){//取两个不同的数 List<Double> nums = new ArrayList<>(); for(int k=0;k<numbers.size();k++){ if(k!=i&&k!=j){//将剩下的数添加到nums中 nums.add(numbers.get(k)); } } Set<Double> doubles = calculate(numbers.get(i),numbers.get(j)); //取两个数进行运算获取结果 for (Double aDouble : doubles) { nums.add(aDouble); //变成了三个数 //递归，从三个数中选两个数 if(solve(nums)){ return true; //找到一个结果立即返回 } nums.remove(nums.size()-1);//回溯 去掉不合适的结果 } } } } return false;} //两个数有六种运算顺序 private Set
calculate(double a, double b) { Set<Double> res = new HashSet<>(); res.add(a-b); res.add(b-a); res.add(a+b); res.add(a*b); if(a!=0){ res.add(b/a); } if(b!=0){ res.add(a/b); } return res;} } ```
扫雷游戏
- 给定一个代表游戏板的二维字符矩阵。 ‘M’ 代表一个未挖出的地雷，’E’ 代表一个未挖出的空方块，’B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（’1’ 到 ‘8’）表示有多少地雷与这块已挖出的方块相邻，’X’ 则表示一个已挖出的地雷。
现在给出在所有未挖出的方块中（’M’或者’E’）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：
如果一个地雷（’M’）被挖出，游戏就结束了- 把它改为 ‘X’。
如果一个没有相邻地雷的空方块（’E’）被挖出，修改它为（’B’），并且所有和其相邻的未挖出方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（’E’）被挖出，修改它为数字（’1’到’8’），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板 - ```bash 输入:
[[‘E’, ‘E’, ‘E’, ‘E’, ‘E’], [‘E’, ‘E’, ‘M’, ‘E’, ‘E’], [‘E’, ‘E’, ‘E’, ‘E’, ‘E’], [‘E’, ‘E’, ‘E’, ‘E’, ‘E’]]
Click : [3,0]
输出:
[[‘B’, ‘1’, ‘E’, ‘1’, ‘B’], [‘B’, ‘1’, ‘M’, ‘1’, ‘B’], [‘B’, ‘1’, ‘1’, ‘1’, ‘B’], [‘B’, ‘B’, ‘B’, ‘B’, ‘B’]]
- 思路：
- DFS/BFS，如果是‘E’才继续搜索，否则停止搜索。并且若该方块附近有雷也停止搜索。BFS需要设置标记，防止已访问的结点重新入队。
- 代码：```java
class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
int rows = board.length;
int cols = board[0].length;
int row = click[0];
int col = click[1];
if(board[row][col]=='M'){
board[row][col] = 'X';
}else{
//递归
board[row][col] = 'B';
dfs(board,row,col,rows,cols);
}
return board;
}
int[][] directs = {{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{1,1},{-1,1},{1,-1}};
public void dfs(char[][] board,int x,int y,int rows,int cols){
int count = getCount(board,x,y,rows,cols);
//相邻有雷就放弃搜索
if(count>0){
board[x][y] = (char)(count+'0');
return;
}
for (int[] direct : directs) {
int xx = x+direct[0];
int yy = y+direct[1];
if(xx<0||xx>=rows||yy<0||yy>=cols||board[xx][yy]!='E') continue;
board[xx][yy] = 'B'; //修改标记
dfs(board,xx,yy,rows,cols);
}
}
//统计当前坐标的相邻地雷数
public int getCount(char[][] board,int x,int y,int rows,int cols){
int count = 0;
for (int[] direct : directs) {
int xx = x+direct[0];
int yy = y+direct[1];
if(xx<0||xx>=rows||yy<0||yy>=cols) continue;
if(board[xx][yy]=='M'){
count++;
}
}
return count;
}
}
bfs```java class Solution { //bfs public char[][] updateBoard(char[][] board, int[] click) {
int rows = board.length; int cols = board[0].length; int row = click[0]; int col = click[1]; if(board[row][col]=='M'){ board[row][col] = 'X'; }else{ board[row][col] = 'B'; bfs(board,row,col,rows,cols); } return board;}
int[][] directs = {{-1,0},{1,0},{0,-1},{0,1},{1,1},{-1,-1},{1,-1},{-1,1}}; public void bfs(char[][] board, int row, int col, int rows, int cols) {
Queue<Integer> queue = new ArrayDeque<>(); queue.offer(row*cols+col); //将坐标入队 while(!queue.isEmpty()) { int locate = queue.poll(); row = locate/cols; col = locate%cols; //获取相邻地雷数量 int count = getCount(board, row, col, rows, cols); if(count>0) { board[row][col] = (char) (count +'0'); continue; } for (int[] direct : directs) { int x = row + direct[0]; int y = col + direct[1]; if (x < 0 || y < 0 || x >= rows || y >= cols || board[x][y] != 'E') continue; board[x][y] = 'B'; //修改标记，防止重复入队 queue.offer(x*cols+y); } }}
public int getCount(char[][] board,int row, int col, int rows, int cols){
int count = 0; //相邻地雷数量 for (int[] direct : directs) { int x = row+direct[0]; int y = col+direct[1]; if(x<0||y<0||x>=rows||y>=cols||board[x][y]!='M') continue; count++; } return count;}
}
<a name="3c101060"></a>
#### 选择课程（同时上的最小课程数量）
- ```bash
4 #课程数量
# 每个课程的开始时间和结束时间
1 4
1 2
2 3
3 4
#输出：
2
- 思路：
- 刚开始选择贪心算法，解决活动安排问题，但遇到了结束时间一样的活动有很多的问题，这种情况不适合用贪心，因为不太好决定这些课程的次序。
- 看了网上的代码后发现可以使用优先队列来存储每个活动的结束时间，判断当前活动开始时间是不是晚于堆顶的活动结束时间，是则弹出，直到堆顶活动结束时间大于当前活动开始时间，表示他们有冲突，不能连续上。最后返回堆的大小即可
- 优先队列中存放的是所有冲突的活动数量。
- 代码：
```java
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main{
//优先队列
public int getMaxCourses(int[][] nums){
PriorityQueue<Integer> queue = new PriorityQueue<>();
//将课程的结束时间保存到优先队列中
queue.add(nums[0][1]);
for (int i = 1; i < nums.length; i++) {
//遍历优先队列，找出结束时间小于当前课程开始时间的课程弹出，这些课程是不冲突的
while(!queue.isEmpty()&&queue.peek()<=nums[i][0]){
queue.poll();
}
//将当前课程加入队列
queue.add(nums[i][1]);
}
return queue.size();
}
public static void main(String[] args){
Main main = new Main();
Scanner sc = new Scanner(System.in);
int[][] nums = {{1,4},{1,2},{2,3},{3,4}};
// System.out.println(Arrays.toString(nums));
System.out.println(main.getMaxCourses(nums));
}
}
10万个数据，按照数字出现的频次取出次数最高的10个数
- 思路：
- 利用随机数生成10万个数字，然后存入list中。
- 利用map统计每个数字出现的频次。
- 利用最小堆统计topK
- 代码：```java import javafx.util.Pair;
import java.util.*;
public class Main{
//生成10万数据
public List
public void getTopK(List<Integer> list, int k){
//利用map统计每个数字的频次
Map<Integer,Integer> map = new HashMap<>();
for (Integer x : list) {
map.put(x,map.getOrDefault(x,0)+1);
}
//利用优先队列统计topk 小根堆
PriorityQueue<Pair<Integer,Integer>> queue = new PriorityQueue<>((o1, o2) -> o1.getValue()-o2.getValue());
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
Pair<Integer,Integer> pair= new Pair<>(entry.getKey(),entry.getValue());
queue.offer(pair);
if(queue.size()>k){
queue.poll();
}
}
System.out.println(queue.toString());
}
public static void main(String[] args) {
Main main = new Main();
int k = 10;
List<Integer> list = main.buildList(100000);
main.getTopK(list,k);
main.getTopK(list,k/2);
}
}
<a name="5f89a491"></a>
#### 连续中值
- 随机产生数字并传递给一个方法。你能否完成这个方法，在每次产生新值时，寻找当前所有值的中间值（中位数）并保存。中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
- 思路：
- 小根堆存放数组较大的数据，大根堆存放数组中较小的数据。当总元素个数为偶数或0时，就把数据放入小根堆，否则放入大根堆。为了保证大根堆中的数据全部小于小根堆，可以先把数据放入最大堆，然后poll到小根堆，或先把数据放入小根堆，然后poll到大根堆。
- 代码```java
import javafx.util.Pair;
import java.util.*;
class MedianFinder {
double median;
Queue<Integer> big; //大根堆 左边
Queue<Integer> small; //小根堆 右边
int size;
/** initialize your data structure here. */
public MedianFinder() {
big = new PriorityQueue<>((o1, o2) -> o2-o1);
small = new PriorityQueue<>();
}
public void addNum(int num) {
//在总数目是偶数时，插入最小堆
//保证最大堆的所有值都要比最小堆小
if((size&1)==0) {
big.offer(num);
small.offer(big.poll());
}else{
//总数目是奇数时，插入最大堆
small.offer(num);
big.offer(small.poll());
}
size++;
}
public double findMedian() {
//偶数
if((size&1)==0){
int num1 = small.peek();
int num2 = big.peek();
median = (num1+num2)/2.0;
}else{
median = small.peek();
}
return median;
}
}
public class Main{
public static void main(String[] args) {
Main main = new Main();
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(-1);
medianFinder.addNum(-2);
medianFinder.addNum(-3);
medianFinder.addNum(-4);
medianFinder.addNum(-5);
System.out.println(medianFinder.findMedian());
}
}
路径总和 III
- 给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。 ```bash root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10/ \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1
返回 3。和等于 8 的路径有:
- 5 -> 3
- 5 -> 2 -> 1
- -3 -> 11 ```
- 思路：
- 类似两数之和，使用hash表来登记当前和出现的次数，避免两次DFS
代码：```java class Solution { //dfs int count = 0; public int pathSum(TreeNode root, int sum) {
Map<Integer,Integer> map = new HashMap<>(); map.put(0,1); //根节点就是sum的情况 dfs(root,sum,0,map); return count;}
//用hash保存当前和出现的次数。以当前节点为根节点，求路径上的和 public void dfs(TreeNode root,int sum,int curSum,Map
if(root==null) return; //将当前节点加入 curSum+=root.val; //判断一下curSum-sum是否在hash表中出现过,若是就直接累加当前次数 count += map.getOrDefault(curSum-sum,0); map.put(curSum,map.getOrDefault(curSum,0)+1);//更新当前和出现的次数 dfs(root.left,sum,curSum,map); dfs(root.right, sum, curSum,map); map.put(curSum,map.get(curSum)-1); //避免兄弟节点的影响}
}
<a name="42e48ae4"></a>
#### 单词搜索
- 给定一个二维网格和一个单词，找出该单词是否存在于网格中。<br />单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
- ```bash
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
- 思路：
- 二维数组的dfs,若当前字符不是单词的首字符就直接返回false,否则就进行递归，直到单词的最后一个字符被找到。若中途路径错误，需要回溯，复原标记
代码：```java class Solution { public boolean exist(char[][] board, String word) {
//bfs 将起始的字符的位置放入队列中 int rows = board.length; int cols = board[0].length; boolean[][] isVisited = new boolean[rows][cols]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if(dfs(board,i,j,word,rows,cols,isVisited,0)){ return true; } } } return false;}
int[][] directs = {{0,-1},{0,1},{1,0},{-1,0}}; public boolean dfs(char[][] board,int x,int y,String word,int rows,int cols,boolean[][] isVisited,int start){
//判断最后一个字符是否相等，若相等则返回 if(start==word.length()-1) return board[x][y]==word.charAt(start); if(board[x][y]==word.charAt(start)) { isVisited[x][y] = true;//设置已经访问过的标记 for (int[] direct : directs) { int xx = x + direct[0]; int yy = y + direct[1]; if (xx < 0 || xx >= rows || yy < 0 || yy >= cols || isVisited[xx][yy]) { continue; } if (dfs(board, xx,yy, word, rows, cols, isVisited, start + 1)) { return true; } } //回溯 isVisited[x][y] = false; } return false;} } ```
组合总和II
- 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。 输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]思路：
- 回溯+剪枝
- 大剪枝：情况1和不满足的情况直接剪枝 情况2 同一层相同数值的节点需要跳过
代码：```java class Solution { List
Arrays.sort(candidates); LinkedList<Integer> path = new LinkedList<>(); dfs(candidates,target,0,0,path); return ans;}
public void dfs(int[] candidates,int target,int index,int curSum,LinkedList
path){ if(curSum==target){ ans.add(new ArrayList<>(path)); } for(int i=index;i<candidates.length;i++){ if(curSum+candidates[i]>target) continue;//剪枝 if(i>index && candidates[i]==candidates[i-1]) continue;//同一层相同数值的节点，剪枝 curSum += candidates[i]; path.add(candidates[i]); dfs(candidates,target,i+1,curSum,path); curSum -= candidates[i]; //回溯 path.removeLast(); }} } ```
字典序
查找字典序第k小的数字
- 给定整数
n和k，找到1到n中字典序第k小的数字。 - ```bash 输入: n: 13 k: 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
- 思路：
- 确定当前前缀下的所有结点数
- 寻找前缀。若第k个数在当前前缀下，cur++,前缀*=10， 若不在，则prefix++,指针指向下一个前缀起点。
- 
- 代码：```java
/**
* 确定指定前缀下的所有子节点数
* @param prefix 前缀i
* @param n 上界
* @return
*/
public int getCount(int prefix,int n){
long cur = prefix;
long next = prefix+1; //下一个前缀
int count = 0;
while(cur<=n){
count += Math.min(n+1,next)-cur;//下一个前缀的起点-当前前缀的起点
cur*=10;
next*=10;
}
return count;
}
/**
* 寻找前缀
* @param n
* @param k
* @return
*/
public int findKthNumber(int n,int k){
int cur = 1;//字典序元素的当前指针
int prefix = 1;//前缀
while(cur<k){
int count = getCount(prefix,n);//当前前缀下的所有结点的数量
//若第k个数在当前前缀下
if(cur+count>k){
prefix *= 10;//前缀移动一层11-> 110
cur++;
//第k个数不在当前前缀下
}else if(cur+count<=k){
prefix++;
cur += count; //指针指向下一个前缀的起点
}
}
return prefix;
}
字典序排数
- 给定一个整数 n, 返回从 1 到 n 的字典顺序。
- 给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
- 代码：```java
//dfs 统计以prefix开头的数字
public void getNumbers(int prefix,int n,List
list){
} public List//若不符合条件就返回 if(prefix>n) return; list.add(prefix); for(int i=0;i<10;i++){ prefix= prefix*10+i; if(prefix>n) break;//若下一个值大于n就中断 getNumbers(prefix,n,list); prefix = (prefix-i)/10;//回溯 }lexicalOrder(int n) {
} ```List<Integer> res = new ArrayList<>(); //遍历所有可能的前缀prefix for(int prefix=1;prefix<10;prefix++){ getNumbers(prefix,n,res); } return res;
单词的压缩编码
- 给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
例如，如果这个列表是 [“time”, “me”, “bell”]，我们就可以将其表示为 S = “time#bell#” 和 indexes = [0, 2, 5]。
对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 “#” 结束，来恢复我们之前的单词列表。
那么成功对给定单词列表进行编码的最小字符串长度是多少呢？ 输入: words = ["time", "me", "bell"] 输出: 10 说明: S = "time#bell#" ， indexes = [0, 2, 5] 。思路：
- 该题就是找到所有单词列表中，哪些单词被别的单词后缀包含了就可以。使用字典树来做，存储相同的后缀。注意待插入的单词需要先按照长度进行降序排列。统计时只需要统计新单词的长度即可。
- 代码：```java import java.util.Arrays;
class TrieNode{ TrieNode[] childs; char val; public TrieNode(){ childs = new TrieNode[26]; //所有小写字母 } } class Solution { public int minimumLengthEncoding(String[] words) { //按照单词的长度进行降序 Arrays.sort(words,(o1, o2) -> o2.length()-o1.length()); TrieNode root = new TrieNode(); int ans = 0; for (String word : words) { ans += insert(root,word); } return ans; } public int insert(TrieNode root,String word){ TrieNode node = root; boolean isNew = false; //是否是新单词 for (int i = word.length()-1; i >=0; i—) { int idx = word.charAt(i)-‘a’; if(node.childs[idx]==null){ isNew = true; node.childs[idx] = new TrieNode(); } node = node.childs[idx]; } return isNew?word.length()+1:0; } }
<a name="3a5aa100"></a>
#### 多次搜索
- 给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。
- ```bash
输入：
big = "mississippi"
smalls = ["is","ppi","hi","sis","i","ssippi"]
输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]
- 思路：
- 对smalls数组构建后缀树
- 遍历big字符串，寻找以i结尾的各个单词的起始位置，并存放于map集合中
代码：```java class TrieNode{ TrieNode[] childs; boolean isWord; public TrieNode(){
childs = new TrieNode[26];} } class Solution { public int[][] multiSearch(String big, String[] smalls) {
TrieNode root = new TrieNode(); Map<String,List<Integer>> map = new HashMap<>(); //构建字典树 for (String small : smalls) { map.put(small,new ArrayList<>()); insert(root,small); } //寻找所有单词在big中的起始位置，并存放在map中 for(int i=0;i<big.length();i++){ search(root, i, big,map); } //输出结果 int[][] ans = new int[smalls.length][]; for (int i = 0; i < smalls.length; i++) { ans[i] = map.get(smalls[i]).stream().mapToInt(Integer::valueOf).toArray(); } return ans;}
//构建后缀树 public void insert(TrieNode root,String word){
TrieNode node = root; for (int i = word.length()-1; i >=0; i--) { int idx = word.charAt(i)-'a'; if(node.childs[idx]==null){ node.childs[idx] = new TrieNode(); } node = node.childs[idx]; } node.isWord = true; //表示单词的结尾}
//寻找以endPos结尾的所有单词的起始位置 public void search(TrieNode root,int endPos,String sentence,Map
TrieNode node = root; StringBuilder builder = new StringBuilder(); //单词作为key for(int i=endPos;i>=0;i--){ int idx = sentence.charAt(i)-'a'; if(node.childs[idx]==null){ break; } //由于字典树存的是后缀，故要倒着插入 builder.insert(0,sentence.charAt(i)); node = node.childs[idx];//递归寻找 //找到某个单词，就把起始位置添加到map中 if(node.isWord){ map.get(builder.toString()).add(i); } }}
}
<a name="68942c77"></a>
### 模式匹配
<a name="5f559369"></a>
#### KMP算法
- 高效的字符串模式匹配算法。用来在主串中查找模式串出现的位置。与普通模式匹配算法的差别在于它减少了无效的比较过程。
- 时间复杂度为O（mn),其中n是主串的长度，m是模式串的长度。
- 步骤：
- 假设主串为s,模式串为t,遍历主串，假设模式串的下标为i，模式串下标j=0.
- 若j==-1或s[i]==p[j], 让i++,j++. 继续匹配下一个字符。
- 否则匹配失败，模式串按照next数组中的值进行回退，继续匹配模式串的下一个字符。
- 如果模式串下标和模式串长度相等，说明匹配到了一个子串，记录模式串的位置，然后将模式串下标置为0，重新开始匹配下一个出现位置。
- 核心是求出next数组，next数组实际上存储的是模式串中前后缀公共元素的最大长度。
- 
- 
- 代码：```java
//求模式串在主串中出现的所有位置区间
private static int[][] intervals = new int[500000][2];
private static int k = 0;//下标
//求模式串的next数组
public static void getNext(int[] next,String t){
int j = 0;
int k = -1;
next[0] = -1;
while(j<t.length()-1){
if(k==-1||t.charAt(j)==t.charAt(k)){
next[++j]=++k;
}else{
k = next[k]; //回溯
}
}
}
public static void KMP(String s,String t){
int[] next = new int[t.length()];
int i=0,j=0;
getNext(next,t);//求next数组
while(i<s.length()){
if(j==-1||s.charAt(i)==t.charAt(j)){
i++;
j++;
}else
j = next[j]; //j回退
//返回子串在主串中的出现位置
if(j==t.length()){
intervals[k++] = new int[]{i-j,i-1};
j = 0; //重新置为0
}
}
}
朴素模式匹配
- 思路:
- 主串和子串同时走,若匹配失败,则主串需要回退到i-j+1的位置
- 最后看一下j是否走到底了,若是则说明匹配成功了
- 代码:```java
public int match(String s,String p){
} ```int sLen = s.length(); int pLen = p.length(); int i = 0; int j =0; //当主串和模式串都没遍历完时继续遍历 while(i<sLen&&j<pLen){ //相等则继续匹配 if(s.charAt(i)==p.charAt(j)){ i++; j++; }else{ i = i-j+1;//i回退 j = 0;//j回退 } } //模式串已经遍历完了 if(j>=pLen){ return i-j; }else{ return -1; }
数学
矩形重叠
- 矩形以列表
[x1, y1, x2, y2]的形式表示，其中(x1, y1)为左下角的坐标，(x2, y2)是右上角的坐标。如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。 输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3] 输出：true思路：
- 有四种不相交的情况，如果都不属于这四种，那么一定相交。
代码：```java class Solution { public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
int x1 = rec1[0]; int x2 = rec1[2]; int y1 = rec1[1]; int y2 = rec1[3]; int x3 = rec2[0]; int x4 = rec2[2]; int y3 = rec2[1]; int y4 = rec2[3]; //不相交条件 if(x3>=x2||x1>=x4||y3>=y2||y1>=y4){ return false; } return true;} } ```
骰子期望
- 扔n个骰子，第i个骰子有可能投掷出Xi种等概率的不同的结果，数字从1到Xi。所有骰子的结果的最大值将作为最终结果。求最终结果的期望
- ``` 第一行一个整数n，表示有n个骰子。（1 <= n <= 50） 第二行n个整数，表示每个骰子的结果数Xi。(2 <= Xi <= 50)
输出最终结果的期望，保留两位小数。
- 思路：
- 利用 %3Dp(x%3C%3Dk)-p(x%3C%3Dk-1)#card=math&code=p%28x%3Dk%29%3Dp%28x%3C%3Dk%29-p%28x%3C%3Dk-1%29)
- 期望是*k#card=math&code=p%28x%3Dk%29%2Ak)求和
- #card=math&code=p%28x%3C%3Dk%29)的概率是min(当前点数k,当前骰子的最大结果）/当前骰子的最大结果
- 代码：```java
import java.util.*;
import java.text.DecimalFormat;
public class Main{
public float expectResult(int maxNum,int n,int[] nums){
float pre = 0;//上一次的概率
float ans = 0; //期望
for(int i=1;i<=maxNum;i++){
float cur = 1; //当前结果的概率
for(int j=0;j<n;j++){//骰子个数
cur *= (float) Math.min(i,nums[j])/nums[j];
}
ans += (cur-pre)*i;
pre = cur;
}
return ans;
}
public static void main(String[] args){
Main main = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
int maxNum = Integer.MIN_VALUE;
for(int i=0;i<n;i++){
nums[i] = sc.nextInt();
maxNum = Math.max(maxNum,nums[i]);
}
float ans = main.expectResult(maxNum,n,nums);
DecimalFormat decimalFormat=new DecimalFormat(".00");//构造方法的字符格式这里如果小数不足2位,会以0补足.
System.out.println(decimalFormat.format(ans));
}
}
1~n整数中1出现的次数
- 输入一个整数
n，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。 输入：n = 12 输出：5思路：此题需要找数学规律。
- 假设factor是因子，当前位值是cur,低位是low,高位是high.那么对于cur的不同取值，有以下几种情况：
- cur==0.则1出现的次数完全由高位决定，high*factor.
- cur==1，则1出现的次数不止由高位决定，还由低位决定， high*factor+low+1
- cur==2~9 则1出现的次数由高位+1决定，(high+1)*factor
- 代码：```java
class Solution {
public int countDigitOne(int n) {
} } ```long factor = 1;//因子 long higerNum = 0;//高位 int curNum =0;//当前位 long lowerNum = 0;//低位 long res = 0; while(n/factor!=0){ lowerNum = n-n/factor*factor; curNum = (int)(n/factor)%10; higerNum = n/(factor*10); //当前位的数字 switch (curNum){ case 0: //1的个数取决于高位 res += higerNum*factor; break; case 1: //1的个数取决于高位以及低位 res += higerNum*factor+lowerNum+1; break; default: //1的个数取决于高位+1 res += (higerNum+1)*factor; break; } factor *=10; } return (int) res;
数字范围按位与
- 给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
输入: [5,7] 输出: 4思路:
- 一段连续的数字按位与之后只剩下起点和终点的公共前缀,其余数字都变成了0.
- 故需要对两个数字进行右移操作,直到两数相等,求出它们的公共前缀,期间移动次数相当于0的个数
- 最后将公共前缀左移0的个数个位置即得到最终结果
- 代码:```java
//一段连续的数进行与操作结束之后只剩下了公共前缀，其余位都是0
public int rangeBitwiseAnd(int m, int n) {
} ```int count = 0; //将两个数向右移动，直到数字相等，则数字被缩减为它们的公共前缀 while(m!=n){ m>>=1; n>>=1; count++; //移动次数就是0的个数 } return m<<count; //公共前缀前移，即将零附加到公共前缀后面
计算质数
- 统计所有小于非负整数 n 的质数的数量
输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。思路:
- n以内的质数是有规律的，2,3,5,7是质数，那么它们的倍数一定不是质数，最后留下的就是质数。
- 为了加快算法速度，我们只需要枚举到sqrt(n)即可。
- 代码：```java
class Solution {
//因子具有对称性，只需要计算到sqrt(n)即可
public int countPrimes(int n) {
} } ```boolean[] isPrime = new boolean[n]; Arrays.fill(isPrime,true); for(int i=2;i*i<n;i++){ if(isPrime[i]){ //找到所有i的倍数，设置为false for(int j=i*i;j<n;j+=i){//j=i*i是为了规避偶数，提高效率 isPrime[j] = false; } } } //统计质数的个数 int ans = 0; for(int i=2;i<n;i++){ if(isPrime[i]) ans++; } return ans;
用rand7()实现rand10()
- 已有方法
rand7可生成 1 到 7 范围内的均匀随机整数，试写一个方法rand10生成 1 到 10 范围内的均匀随机整数。 - 思路：
- 首先要生成等概率的范围的数，$rand7()+(rand7()-1)*7 $, 可以生成[1-49]的数，而且每个数都是等概率的。
- 然后去掉41-49这个范围的数，最后得到的数对10取余并加1
- 代码：```java
/**
- The rand7() API is already defined in the parent class SolBase.
- public int rand7();
- @return a random integer in the range 1 to 7
*/
class Solution extends SolBase {
public int rand10() {
} } ```//生成1到49的等概率的数 int num = (rand7()-1)*7+rand7(); while(num>40){ //舍弃41-49之间的数 num = (rand7()-1)*7+rand7(); } return 1+num%10;
递归
汉诺塔问题
- 在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。 输入：A = [2, 1, 0], B = [], C = [] 输出：C = [2, 1, 0]思路：
- 其实这道题和之前书上看的汉诺塔的递归步骤是一样的，只不过把move函数的打印换成了真实的移动。
- A上面有3个盘子，需要借助B的帮助全部移动到C上，并保持自上而下升序。
- 移动过程中，判断若剩余盘子数n=1,就可以直接通过move函数将A的盘子移动到C。否则将n-1个盘子从A移动到B，辅助为C。再将最后一个盘子从A移动到C，最后将n-1个盘子从B移动到C，辅助为A。
- 此题只需要修改move函数即可。
- 代码：```java
class Solution {
public void hanota(List
A,List B,List C){
} //将n个盘子从A移动到C 辅助为B public void hanota(int n,Listint n = A.size(); hanota(n,A,B,C);A,List B,List C){
} //移动函数 源地点，目的地点 public void move(Listif(n==1) move(A,C); if(n>1){ hanota(n-1,A,C,B); //把前n-1个盘子从A移动到B，辅助为C move(A,C); //把编号为n的从A移动到C hanota(n-1,B,A,C); //再把前n-1个盘子从B移动到C，辅助为A }src,List dst){
} } ```Integer x = src.remove(src.size() - 1); //移动最顶部 dst.add(x);
矩阵
搜索二维矩阵
- 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]代码:```java public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length==0||matrix[0].length==0) return false; int row = 0; int col = matrix[0].length-1; //从第一列的最后一个元素开始找 while(row<matrix.length && col>=0){ //相等直接返回 if(target==matrix[row][col]){ return true; //大了就往下搜索 }else if(target>matrix[row][col]){ row++; //小了就往左搜索 }else{ col--; } } return false;}https://leetcode-cn.com/problems/search-a-2d-matrix-ii/) ```
旋转矩阵
- 给你一幅由
N × N矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。 - ```bash 给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ],
原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3] ]
- 思路：
- 先对矩阵进行对角线翻转
- 然后进行水平翻转
- 代码：```java
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length-1;
if(n<=0) return;
//先沿着对角线进行翻转
for(int i=0;i<=n;i++){
for(int j=i+1;j<=n;j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
//然后水平翻转
for(int i=0;i<=n;i++){
for(int j=0;j<=n/2;j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n-j];
matrix[i][n-j] = temp;
}
}
}
}
顺时针打印矩阵
- 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]思路:
- 确定遍历的起点坐标(x,y),终点坐标(xx,yy)
- 每层遍历完之后,需要将起点坐标+1,终点坐标-1.
- 代码:```java
public int[] spiralOrder(int[][] matrix,int x,int y,int xx,int yy){
} public int[] spiralOrder(int[][] matrix) {List<Integer> ans = new ArrayList<>(); while(x<=xx && y<=yy){ //左到右 for(int i=y;i<=yy;i++){ ans.add(matrix[x][i]); } //上到下 for(int i=x+1;i<=xx;i++){ ans.add(matrix[i][yy]); } //右到左 if(x<xx && y<yy){ for(int i=yy-1;i>=y;i--){ ans.add(matrix[xx][i]); } } //下到上 if(x<xx && y<yy) { for(int i=xx-1;i>=x+1;i--){ ans.add(matrix[i][y]); } } //终点减少 xx--; yy--; //起点增加 x++; y++; } return ans.stream().mapToInt(Integer::valueOf).toArray();
} ```if(matrix.length==0||matrix[0].length==0) return new int[0]; return spiralOrder(matrix,0,0,matrix.length-1,matrix[0].length-1);
位运算
数组中数字出现的次数II
- 在一个数组
nums中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。 输入：nums = [3,4,3,3] 输出：4思路：
- 本题不能使用异或等位运算符来做，因为并没有什么规律可言。
- 而是由题意可知，既然其他数字都出现了3次，那么在它们对应位的和一定是3的整数倍。如果不是说明该位含有那个只出现1次的数字。
- 所以使用count做一个大小为32的整型数组，存放每一位的和。
- 代码：```java
class Solution {
public int singleNumber(int[] nums) {
} //求数组中各个数字每一位上的和 public void add(int num,int[] count){int[] count = new int[32]; //存储每一位的和 for(int num:nums){ add(num,count); } //当前位的和不是3的整数倍就说明该位为1，否则为0 int ans = 0; for(int i=0;i<32;i++){ if(count[i]%3!=0){ ans = ans + (int) Math.pow(2,i); } } return ans;
} } ```int i = 0; while(num>0){ count[i] += num & 1; i++; num >>>= 1; }
数组中数字出现的次数
- 一个整型数组
nums里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]思路：
- 利用异或运算的特性，出现了两次的数字异或结果一定是0. 故可以把数组里面的数字分为两组，每组各包含一个只出现一次的数字。
- 分组依据是根据所有数字异或的结果的第一个为1的位置。
- 代码：```java
class Solution {
public int[] singleNumbers(int[] nums) {
} } ```int res = 0; //两个只出现一次数字的异或 for(int num:nums){ res ^= num; } //找到第一个为1的位的位置 int x = 1; while((res&x)!=x){ x<<=1; } //将数字分成两组 int n1 = 0; int n2 = 0; for(int num:nums){ if((num&x)==x){ n1 ^= num; }else{ n2^=num; } } return new int[] {n1,n2};
绘制直线
- 绘制直线。有个单色屏幕存储在一个一维数组中，使得32个连续像素可以存放在一个 int 里。屏幕宽度为w，且w可被32整除（即一个 int 不会分布在两行上），屏幕高度可由数组长度及屏幕宽度推算得出。请实现一个函数，绘制从点(x1, y)到点(x2, y)的水平线。
给出数组的长度 length，宽度 w（以比特为单位）、直线开始位置 x1（比特为单位）、直线结束位置 x2（比特为单位）、直线所在行数 y。返回绘制过后的数组。 输入：length = 1, w = 32, x1 = 30, x2 = 31, y = 0 输出：[3] 说明：在第0行的第30位到第31为画一条直线，屏幕表示为[0b000000000000000000000000000000011]思路：
- 由于1个init代表32位，直接使用int[]数组存放这些位不仅浪费空间而且不能完全装下。故需要考虑位运算。只需要把这条直线的x1到x2之间全部置一，其他位置零就行。
- 使用（y*w+x）/32 定位低位和高位的坐标，然后对低位进行调整，让其无符号右移，使低位前面的位都保持为0。最后对高位进行调整，让高位前面的位都为1，并和低位结果相与，得到低位和高位之间全为1的结果。
- 代码：```java
class Solution {
public int[] drawLine(int length, int w, int x1, int x2, int y) {
}int[] ans = new int[length]; int low = (y*w+x1)/32;//首位数字下标 int high = (y*w+x2)/32;//末尾数字下标 //将涉及到的数全部置一 for(int i=low;i<=high;i++){ ans[i] = -1; } //调整首位数字 ans[low] = ans[low]>>>x1%32;//无符号右移，确定低位的位置,低位前面全是0 //调整末尾数字 ans[high] = ans[high] & Integer.MIN_VALUE>>x2%32;//带符号右移，确定高位的位置，高位前面全是1，再与上低位，就成了低位到高位之间全是1 return ans;
}
<a name="95566613"></a>
### 归并排序
<a name="db483a01"></a>
#### 数组中的逆序对
- 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
- ```bash
输入: [7,5,6,4]
输出: 5
- 思路：
- 归并排序，分治法，合并的时候统计逆序对的个数即可。以右边的数据为准，进行对比，统计出逆序对的个数。
- 注意辅助数组不要在递归中进行创建，容易造成超时，可以将其定义为形参。
- ```java import javafx.util.Pair;
import java.util.*;
public class Main{ int count = 0; //逆序对的个数 public int reversePairs(int[] nums) { int[] p = new int[nums.length]; //辅助数组 mergeSort(nums,0,nums.length-1,p); return count; }
public void mergeSort(int[] nums,int left,int right,int[] p){
if(left==right) return; //只有一个元素时，一定是有序的
int mid = left+(right-left)/2;
mergeSort(nums,left,mid,p);//对左半段排序
mergeSort(nums,mid+1,right,p);//对右半段进行排序
if(nums[mid]<=nums[mid+1]) return; //若左右两边都有序则返回
mergeCross(nums,left,mid,right,p);//跨越两个区间排序
}
private void mergeCross(int[] nums, int left, int mid, int right, int[] p) {
//拷贝原数组到辅助数组中
for (int i = left; i <= right; i++) {
p[i] = nums[i];
}
//开始合并
int l = left; //左边第一个
int r = mid+1; //右边第一个
for(int k=left;k<=right;k++){
//如果左边的数用完了，就拷贝右边
if(l==mid+1){
nums[k] = p[r++];
}else if(r==right+1){//如果右边的数用完了，就拷贝左边
nums[k] = p[l++];
}else{
//否则比较两边的大小,注意此时两边均有序
if(p[l]>p[r]){
count+= mid+1-l;//计算逆序对的个数
nums[k] = p[r++];
}else{
nums[k] = p[l++];
}
}
}
}
//归并排序
public List<Integer> countSmaller(int[] nums) {
int len = nums.length;
int[] count = new int[len];
List<Integer> ans = new ArrayList<>();
for(int i=len-1;i>=0;i--){
for(int j=i+1;j<len;j++){
if(nums[j]<nums[i]){
count[i]++;
}
}
ans.add(0,count[i]);
}
return ans;
}
public static void main(String[] args) {
Main main = new Main();
int[] nums = {7,5,6,4};
System.out.println(main.reversePairs(nums));
}
}
<a name="44986bec"></a>
#### 计算右侧小于当前元素的个数
- 给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
- ```java
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
- 思路：
- 此题用暴力法会超时，时间复杂度是O(n^2)
- 归并排序
- 代码：
其他
字符串转16进制
- 给定一个包含大写英文字母和数字的句子，找出这个句子所包含的最大的十六进制整数，返回这个整数的值。数据保证该整数在int表示范围内。
public int findMaxSum(String str){ int sum = 0; for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); if(Character.isDigit(ch)){ int x = ch-'0'; sum = sum*16+x; //这里是16进制的转换 }else if(ch>='A'&&ch<='F'){ int x = ch-'A'+10; sum = sum*16+x; }else{ break; } } return sum; }
将n拆成3个数乘积最大
求加法的方案数目
- 代码```java import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Scanner;
public class Main { //动态规划 public int findPlans(int n,int k,int d){
int[][] dp = new int[n+1][k+1];
dp[0][0] = 1;
for(int i=1;i<=n;i++){
for (int j = 1; j <= k; j++) {
for(int a=1;a<j&&i>=a;a++){
dp[i][j] += dp[i-a][j];
}
for(int b=0;b<=j&&i>=j;b++){
dp[i][j] += dp[i-j][b];
}
}
}
int s = 0;
for(int j=d;j<=k;j++){
s+=dp[n][j];
}
return s;
}
public static void main(String[] args) {
Main main = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //和为n
int k = sc.nextInt();// 必须小于等于k
int d = sc.nextInt(); //最大值必须大于等于d
System.out.println(main.findPlans(n, k, d));
}
} ```
场景题
- 两根香，一根烧完1小时，如何测量15分钟
- 先将一根香的一端点燃，另一根香的两端全部点燃。当第二根香全部烧完时，此时已经过了半个小时。再将第一根香的另一端也点燃，那么此时第一根香剩下部分烧完的时间就是 15 min。
- 互相关注表设计 需求：谁关注了我，我关注了谁，谁与我互相关注。表该如何设计，索引怎么建。查询语句怎么写
- 表: 个人id,被关注者id,粉丝id. 索引建在粉丝id和被追随者id.
- 10亿个数,取最小的100个数
- 先通过hash去重后再使用堆排序.
- 1亿个正整数,范围是0-42亿。求出现次数是2的数字，空间复杂度
- 用byte[]数组来存放,每一位代表一个数字,普通的一个int占4个字节，32位，用了位图之后可以将空间节省32倍。
- 开一个42亿大小的位图，将这一亿个数字存进数字大小对应的位置，一个bit每存进去一个数字，就将value+1,比如第一次存8，就将索引为8的位置的value置为1，第二次就置为2，存完之后搜索value为2的key是多少。
- 空间是
#card=math&code=42%20%E4%BA%BF%20%2F%288%2A1024%2A1024%29)
- 一硬币，一面向上概率0.7，一面0.3，如何公平？
- 抛两次，正反A胜，反正B胜。
- 每一轮抛硬币，A先抛赢得概率是1/2，B后抛赢得概率是（1/2）*（1/2）= 1/4。那么每一轮A赢得概率都是B赢得概率的2倍，总概率为1,所以A赢的概率是2/3。
- 有一个IP地址库，假设有几十万条ip，如何判断某个ip地址是否在这个库中？
- 位图,每个位存储一个ip
- 布隆过滤器,对每个ip进行多次hash,将指定位置的标志设置为1,若某个ip的hash值有一个不为1,那么它一定不在地址库中.
- 100个0～1000的正整数，怎么找到第一个缺失的数?
- 用一个大小为1001的布尔数组，扫描这100个数，将下标为数字的位置设置为true，再扫描一遍这个bool数组，遇到第一个false就返回。
fork()函数的问题
若有收获，就点个赞吧
0 人点赞
