1.用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
import java.util.Stack;
class CQueue {
Stack<Integer> inStack; // 保存输入的栈
Stack<Integer> outStack; // 保存输出的栈
// 构造方法
public CQueue() {
inStack = new Stack<>();
outStack = new Stack<>();
}
public void appendTail(int value) {
inStack.push(value);
}
// 检查顺序为：①输出栈②输入栈
public int deleteHead() {
if(!outStack.isEmpty()){
return outStack.pop();
}
if (!inStack.isEmpty()){
in2out();
return outStack.pop();
}
return -1;
}
public void in2out(){
while(!inStack.isEmpty()){
outStack.push(inStack.pop());
}
}
}
2.包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
import java.util.Stack;
class MinStack {
Stack<Integer> xStack;// 主栈
Stack<Integer> minStack;// 每次主站操作元素，同步确定此操作后，主栈中的最小值
public MinStack() {
xStack = new Stack<Integer>();
minStack = new Stack<Integer>();
minStack.push(Integer.MAX_VALUE); // 用最大值初始化最小栈
}
public void push(int x) {
xStack.push(x);
// Stack.peek()方法获取Stack顶部的元素，获取到的元素不会被删除
minStack.push(Math.min(minStack.peek(), x));
}
public void pop() {
xStack.pop();
minStack.pop();
}
public int top() {
return xStack.peek();
}
public int min() {
return minStack.peek();
}
}
3.从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
import java.util.Stack;
/**
* 下面这个注释的类需要定义
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
// “从尾到头”提示我们可以考虑用“栈”来解决这个问题
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> listNodes = new Stack<>();
ListNode temp = head;
while (temp != null){
listNodes.push(temp);
temp = temp.next;
}
int size = listNodes.size();
int[] ints = new int[size];
for (int i = 0; i < ints.length; i++) {
ints[i] = listNodes.pop().val;
}
return ints;
}
}
4.反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
/**
* 下面这个注释的类需要定义
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
// 链表没办法找到之前那个节点，所以定义了一个prev节点
class Solution {
public ListNode reverseList(ListNode head) {
ListNode curr = head;
ListNode prev = null;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
5.复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
import java.util.HashMap;
import java.util.Map;
// 核心思想，从头开始，如果random指针指向了还没建立的node则递归建立node
class Solution {
Map<Node,Node> cachedNode = new HashMap<Node,Node>();
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
if (!cachedNode.containsKey(head)){ // 避免重复建立已有的node
Node newHead = new Node(head.val);
cachedNode.put(head,newHead);
newHead.next = copyRandomList(head.next);
newHead.random = copyRandomList(head.random);
}
return cachedNode.get(head);
}
}
6.替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
class Solution {
public String replaceSpace(String s) {
int length = s.length();
char[] array = new char[length*3]; // 考虑极端情况，s串全是空格
int size = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if(c == ' '){
array[size++] = '%';
array[size++] = '2';
array[size++] = '0';
}else{
array[size++] = c;
}
}
String newStr = new String(array, 0, size); // 截取array数组中的0-size部分为string
return newStr;
}
}
7.左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
class Solution {
public String reverseLeftWords(String s, int n) {
// String.substring(x,y)截取x-y部分的字串
return s.substring(n,s.length())+s.substring(0,n);
}
}
8.数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
**输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 **
import java.util.HashSet;
import java.util.Set;
// “重复”可以利用集合不能重复的特性
class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> sets = new HashSet<>();
int repeat = -1;// 数字范围为0~n-1，返回-1则说明无重复
for (int num:nums){
if(!sets.add(num)){// 集合添加失败，说明该数字重复了
repeat = num;
break;
}
}
return repeat;
}
}
9.在排序数组中查找数字
统计一个数字在排序数组中出现的次数。
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
class Solution {
public int search(int[] nums, int target) {
int count = 0;
for(int num:nums){
if(target == num){
count++;
}
if (target < num){
break;
}
}
return count;
}
}
10.0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
输入: [0,1,3]
输出: 2
class Solution {
public int missingNumber(int[] nums) {
int x = 0;// 判断是哪个数字缺失的
int i = 0;
for (; i < nums.length; i++) {
// 特别注意要越界检查
if (i == nums.length){
return i;
}
if(x == nums[i]){ // 有相等的说明没缺失
x++;
}else{
break;
}
}
return x;
}
}
11.二维数组中的查找
在一个 m * n 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
Z 字形查找
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
// 数组判空（题解漏了）
if(matrix.length == 0){
return false;
}
int m = matrix.length, n = matrix[0].length;
int x = 0, y = n - 1;
while (x < m && y >= 0) {
if (matrix[x][y] == target) {
return true;
}
if (matrix[x][y] > target) {
--y;
} else {
++x;
}
}
return false;
}
}
12.旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
举例：
输入：numbers = [3,4,5,1,2]
输出：1
// 算法核心：二分查找（left，middle，right指针）
class Solution {
public int minArray(int[] numbers) {
int left = 0; // 左指针
int right = numbers.length - 1; // 右指针
while (left < right) {
int middle = left + (right - left) / 2; // 中间的指针
if (numbers[middle] < numbers[right]) {
right = middle;
} else if (numbers[middle] > numbers[right]) {
left = middle + 1; // +1的关键在于，该值是否有可能是最小值
} else {
right -= 1;
}
}
return numbers[left];
}
}
13.第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
举例：
输入：s = “abaccdeff”
输出：‘b’
输入：s = “”
输出：’ ’
import java.util.HashMap;
import java.util.Map;
// 用哈希表存 （字符，出现次数）
class Solution {
public char firstUniqChar(String s) {
Map <Character,Integer> maps = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
// Map.getOrDefault(key,defaultValue),获取map中key对应的value，如果不存在此key则返回defaultValue
maps.put(ch,maps.getOrDefault(ch,0)+1);
}
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (maps.get(ch) == 1){
return ch;
}
}
return ' ';
}
}
14.从上到下打印二叉树（1）
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
import java.util.*;
// 广度优先遍历算法（BFS），先进先出，使用“队列”
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] levelOrder(TreeNode root) {
if (root == null) return new int[0];
// LinkedList实现了queue接口，因为要频繁增删，所以用链表好点
Queue<TreeNode> queue = new LinkedList<>() ;
// 添加元素：queue.add()，在超出容量时，add()方法会对抛出异常
queue.add(root);
// ArrayList 动态数组，存放值
ArrayList<Integer> ans = new ArrayList<>();
while (!queue.isEmpty()) {
// 删除并弹出元素：queue.remove()，在容量为0的时候，remove()会抛出异常
TreeNode node = queue.remove();
ans.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
int[] res = new int[ans.size()];
for (int i = 0; i < ans.size(); i++)
res[i] = ans.get(i);
return res;
}
}
15.从上到下打印二叉树（2）
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
import java.util.*;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>(); // 二维数组
if(root != null) queue.add(root);
while(!queue.isEmpty()) {
List<Integer> tmp = new ArrayList<>(); // 一维数组
for(int i = queue.size(); i > 0; i--) { // 循环条件是精髓
TreeNode node = queue.remove();
tmp.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}
16.从上到下打印二叉树（3）
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
import java.util.*;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()) {
LinkedList<Integer> tmp = new LinkedList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.remove();
if(res.size() % 2 == 0) tmp.addLast(node.val); // 偶数层 -> 队列头部
else tmp.addFirst(node.val); // 奇数层 -> 队列尾部
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}
17.树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
//这个函数对这棵树进行前序遍历：即处理根节点，再递归左子节点，再递归处理右子节点
//特殊情况是：当A或B是空树的时候 返回false
//用||关系可以达到 不同顺序遍历的作用
if(A==null||B==null){
return false;
}
return recur(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
}
//此函数的作用是从上个函数得到的根节点开始递归比较 是否是子树
boolean recur(TreeNode A, TreeNode B){
//结束条件
//当最后一层B已经为空的，证明则B中节点全是A中节点
if(B==null){
return true;
}
//这里因为有上一个条件，则说明 A已经为空了，B却不为空，则一定不是子树
if(A==null){
return false;
}
//处理本次递归，即处理当前节点
if(A.val!=B.val){
return false;
}
//递归，同时递归左右两个子节点
return recur(A.left,B.left)&&recur(A.right,B.right);
}
}
18.二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
// 从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转得到镜像。
// 如果当前遍历到的节点 root 的左右两棵子树都已经翻转得到镜像，
// 那么我们只需要交换两棵子树的位置，即可得到以 root为根节点的整棵子树的镜像。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null){
return null;
}
TreeNode left = mirrorTree(root.left);
TreeNode right = mirrorTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
19.对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
提示：
如果同时满足下面的条件，两个树互为镜像：
- 它们的两个根结点具有相同的值
- 每个树的右子树都与另一个树的左子树镜像对称
/**
我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，
p 指针和 q 指针一开始都指向这棵树的根，
随后 p 右移时，q 左移，p 左移时，q 右移。
每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
public boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}
}
20.斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
// 动态规划 p q r
class Solution {
public int fib(int n) {
final int MOD = 1000000007;
if (n < 2) {
return n;
}
int p = 0, q = 0, r = 1;
for (int i = 2; i <= n; ++i) {
p = q;
q = r;
r = (p + q) % MOD;
}
return r;
}
}
21.青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
// 动态规划
class Solution {
public int numWays(int n) {
int a = 1,b = 1,c = 2;
if(n == 0){
return 1;
}else if(n == 1){
return 1;
}
for(int i = 2; i < n; i++){
a = b;
b = c;
c = (a + b) % 1000000007;
}
return c;
}
}
22.股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
// 前i日最大利润=max[前(i−1)日最大利润,第i日价格−前i日最低价格]
class Solution {
public int maxProfit(int[] prices) {
// cost是最低价格，profit是利润
int cost = Integer.MAX_VALUE,profit = 0;
for(int price : prices){
cost = Math.min(price,cost);
profit = Math.max(profit,price-cost);
}
return profit;
}
}
23.连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
// 动态规划
class Solution {
public int maxSubArray(int[] nums) {
// pre为以nums[i]结尾的子数组的和
int pre = 0, maxAns = nums[0];
for (int x : nums) {
// 如果x之前的子数组和小于0，则可以直接抛弃转而从x开始
pre = Math.max(pre + x, x);
maxAns = Math.max(maxAns, pre);
}
return maxAns;
}
}
24.礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
// 动态规划
/**给定数组 当前单元格的最大礼物价值
1 3 1 1 4 5
1 5 1 2 9 10
4 2 1 6 11 12
*/
class Solution {
public int maxValue(int[][] grid) {
// grid为到当前单元格的最大礼物价值
int m = grid.length, n = grid[0].length;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0 && j == 0) continue;
// 第一行只能靠左边算出来
if(i == 0) grid[i][j] += grid[i][j - 1] ;
// 第一列只能靠上边算出来
else if(j == 0) grid[i][j] += grid[i - 1][j];
else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
}
}
return grid[m - 1][n - 1];
}
}
25.把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
// 动态规划
class Solution {
// 排列顺序是这样的： b a c
public int translateNum(int num) {
// String.valueOf()数字转字符串
String s = String.valueOf(num);
// 初始化dp[0],dp[i]都是1
int a = 1, b = 1;
for(int i = 2; i <= s.length(); i++) {
String tmp = s.substring(i - 2, i);
int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
b = a;
a = c;
}
return a;
}
}
26.最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
import java.util.HashMap;
import java.util.Map;
// 动态规划+哈希表
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> dic = new HashMap<>();
// 顺序：i j
int res = 0, tmp = 0;
for(int j = 0; j < s.length(); j++) {
int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i
dic.put(s.charAt(j), j); // 更新哈希表
/**
* 当dp[j-1] < j-i ，
* 说明字符s[i]在子字符串dp[j-1]区间之外，则dp[j]=dp[j-1]+1
*
* 当dp[j-1] >= j-i ，
* 说明字符s[i]在子字符串dp[j-1]区间之中，则dp[j]的左边界由s[i]决定，dp[j]=j-i
*/
tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
}
return res;
}
}
27.删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
// 删除的是头结点
if(head.val == val) return head.next;
ListNode pre = head, cur = head.next;
while(cur != null && cur.val != val) {
pre = cur;
cur = cur.next;
}
if(cur != null) pre.next = cur.next;
return head;
}
}
28.链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
if(head == null){
return null;
}
int len = 1; // 计算链表长度
ListNode p = head;
while (p!=null){
p = p.next;
len++;
}
int index = len - k - 1;
for ( ; index > 0 ; index--) {
head = head.next;
}
return head;
}
}
29.合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// temp为伪头节点(固定不动的)
ListNode temp = new ListNode(0), cur = temp;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
}
else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2;
return temp.next;
}
}
30.两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
// 双指针
/**
* 如果指针 pA 为空，则将指针 pA 移到链表 headB的头节点；
* 如果指针 pB为空，则将指针 pB 移到链表 headA的头节点。
* （这个意思:a+b = b+a）
* 当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。
*/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = (pA == null) ? headB : pA.next;
pB = (pB == null) ? headA : pB.next;
}
return pA;
}
}
31.调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
class Solution {
// 双指针 一个从前往后，一个从后往前
public int[] exchange(int[] nums) {
int n = nums.length;
int[] res = new int[n];
int left = 0, right = n - 1;
for (int num : nums) {
if (num % 2 == 1) {
res[left++] = num;
} else {
res[right--] = num;
}
}
return res;
}
}
32.和为s的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
class Solution {
// 双指针
public int[] twoSum(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while(i < j) {
int s = nums[i] + nums[j];
if(s < target) i++;
else if(s > target) j--;
else return new int[] { nums[i], nums[j] };
}
return new int[0];
}
}
33.翻转单词顺序
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。
// 双指针从后往前遍历
class Solution {
public String reverseWords(String s) {
s = s.trim(); // 删除首尾空格
int j = s.length() - 1, i = j;
StringBuilder res = new StringBuilder();
while(i >= 0) {
while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
j = i; // j 指向下个单词的尾字符
}
return res.toString().trim(); // 转化为字符串并返回（因为“添加单词”那边添加了空格）
}
}
34.矩阵中的路径
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
class Solution {
// 深度优先+减枝
// k表示单词里面字母的索引
public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(dfs(board, words, i, j, 0)) return true;
}
}
return false;
}
boolean dfs(char[][] board, char[] word, int i, int j, int k) {
if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
if(k == word.length - 1) return true;
board[i][j] = '\0';
boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
board[i][j] = word[k]; // 递归把之前设置为\0的还原回去
return res;
}
}
35.机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
class Solution {
int m, n, k;
boolean[][] visited;
public int movingCount(int m, int n, int k) {
this.m = m; this.n = n; this.k = k;
this.visited = new boolean[m][n];
// i j 为索引，si sj为数位和
return dfs(0, 0, 0, 0);
}
public int dfs(int i, int j, int si, int sj) {
if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
visited[i][j] = true;
// 下面为数量和增量判定
return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
}
}
36.二叉树中和为某一值的路径
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
LinkedList<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
recur(root, sum);
return res;
}
void recur(TreeNode root, int tar) {
if(root == null) return;
path.add(root.val);
tar -= root.val;
if(tar == 0 && root.left == null && root.right == null)
res.add(new LinkedList(path));
recur(root.left, tar);
recur(root.right, tar);
path.removeLast();
}
}
37.二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
Node head, pre;
public Node treeToDoublyList(Node root) {
if(root==null) return null;
dfs(root);
pre.right = head;
head.left =pre;//进行头节点和尾节点的相互指向，这两句的顺序也是可以颠倒的
return head;
}
public void dfs(Node cur){
if(cur==null) return;
dfs(cur.left);
//pre用于记录双向链表中位于cur左侧的节点，即上一次迭代中的cur,当pre==null时，cur左侧没有节点,即此时cur为双向链表中的头节点
if(pre==null) head = cur;
//反之，pre!=null时，cur左侧存在节点pre，需要进行pre.right=cur的操作。
else pre.right = cur;
cur.left = pre;//pre是否为null对这句没有影响,且这句放在上面两句if else之前也是可以的。
pre = cur;//pre指向当前的cur
dfs(cur.right);//全部迭代完成后，pre指向双向链表中的尾节点
}
}
38.二叉搜索树的第k大节点
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int count,res;
public int kthLargest(TreeNode root, int k) {
count = k;
dfs(root); //倒着中序遍历 右子数->中间结点->左子数
return res;
}
void dfs(TreeNode node){
if(node==null||count<=0) return; //设置终止条件
dfs(node.right); //先遍历右子树
count--;
if(count==0) res = node.val; //如果count==0，说明这就是第倒数k个数
dfs(node.left); //再遍历左子树
}
}
39.把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++)
strs[i] = String.valueOf(nums[i]);
Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
StringBuilder res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
}
40.扑克牌中的顺子
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
class Solution {
public boolean isStraight(int[] nums) {
Set<Integer> repeat = new HashSet<>();
int max = 0, min = 14;
for(int num : nums) {
if(num == 0) continue; // 跳过大小王
max = Math.max(max, num); // 最大牌
min = Math.min(min, num); // 最小牌
if(repeat.contains(num)) return false; // 若有重复，提前返回 false
repeat.add(num); // 添加此牌至 Set
}
return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
}
41.最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
quickSort(arr, 0, arr.length - 1);
return Arrays.copyOf(arr, k);
}
private void quickSort(int[] arr, int l, int r) {
// 子数组长度为 1 时终止递归
if (l >= r) return;
// 哨兵划分操作（以 arr[l] 作为基准数）
int i = l, j = r;
while (i < j) {
while (i < j && arr[j] >= arr[l]) j--;
while (i < j && arr[i] <= arr[l]) i++;
swap(arr, i, j);
}
swap(arr, i, l);
// 递归左（右）子数组执行哨兵划分
quickSort(arr, l, i - 1);
quickSort(arr, i + 1, r);
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
42.数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。
class MedianFinder {
Queue<Integer> A, B;
public MedianFinder() {
A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
}
public void addNum(int num) {
if(A.size() != B.size()) {
A.add(num);
B.add(A.poll());
} else {
B.add(num);
A.add(B.poll());
}
}
public double findMedian() {
return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
}
}
Q.E.D.