- 1. 数组中重复的数字
- 2. 二维数组中的查找
- 3. 替换空格
- 4. 从尾到头打印链表
- 5. 双栈实现队列
- 6. 斐波那契数列
- 7. 青蛙跳台问题
- 8. 旋转数组的最小数字
- 9. 矩阵中的路径
- 10.机器人的运动范围
- 11.剪绳子I
- 12.剪绳子II
- 13.二进制数中1的个数
- 14. 数值的整数次方
- 15. 打印从1到最大的n位数
- 16. 删除链表的节点
- 17.调整数组顺序使奇数位于偶数前面
- 18. 链表的倒数第k个节点
- 19.反转链表
- 20.合并两个排序链表
- 21.二叉树的镜像
- 22.对称的二叉树
- 23.顺时针打印矩阵
- 24.包含min函数的栈
- 25.栈的压入、弹出序列
- 26.从上到下打印二叉树
- 27.从上到下打印二叉树2
- 28.数组中出现次数超过一半的数字
- 29.复杂链表的复制
- 30.连续子数组的最大和
- 31.数字数列中某一位数字
- 32.把数字翻译成字符串
- 33.礼物的最大价值
1. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：输入：[2, 3, 1, 0, 2, 5, 3]输出：2 或 3
// class Solution {
// public int findRepeatNumber(int[] nums) {
// // 使用set装配数字，判断下一个数字是否已经存在
// // 1. 存在，则返回该数字；
// // 2. 不存在，则放入set；
// Set<Integer> set = new HashSet<Integer>();
// for(int i : nums){
// if(!set.contains(i)){
// set.add(i);
// }else{
// return i;
// }
// }
// return -1;
// }
// }
class Solution {
public int findRepeatNumber(int[] nums) {
// 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内
// 表示索引与数字值为一对多关系
// 遍历数组，判断值大小的索引处是否有相同的数存在，将每个数值与数值对应的索引位置的数进行交换
// 保证数值与索引都一一对应，当发现有值对应的索引处已经存在该数，那么直接返回
for(int i=0;i<nums.length;){
if(nums[i]==i){
i++;
continue;
}
if(nums[i]==nums[nums[i]]){
return nums[i];
}
int temp = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = temp;
}
return -1;
}
}
2. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[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]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
/**
思路：
1. 从右上方或者左下方为起始位置；
2. 不停的判断目标值与对应位置的值的关系，然后进行索引位置移动；
3. 最终在对角位置停止；
*/
// 从左下方开始
int i = matrix.length-1;
int j = 0;
while(i>=0 && j<matrix[0].length){
if(target<matrix[i][j]){
i--;
}else if(target>matrix[i][j]){
j++;
}else{
return true;
}
}
return false;
}
}
3. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
限制：
0 <= s 的长度 <= 10000
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder("");
char[] chs = s.toCharArray();
for(char c : chs){
if(c==' '){
sb.append("%20");
}else{
sb.append(c);
}
}
return sb.toString();
}
}
4. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1： 输入：head = [1,3,2] 输出：[2,3,1] 限制： 0 <= 链表长度 <= 10000
class Solution {
public int[] reversePrint(ListNode head) {
/**
头插法：
*/
ListNode newHead = new ListNode();
ListNode cur = head;
int total = 0;
while(cur!=null){
ListNode newNode = new ListNode(cur.val);
newNode.next = newHead.next;
newHead.next = newNode;
cur = cur.next;
total++;
}
int[] res = new int[total];
int index = 0;
ListNode temp = newHead.next;
while(temp!=null){
res[index++] = temp.val;
temp = temp.next;
}
return res;
}
}
5. 双栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1： 输入： ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] 输出：[null,null,3,-1] 示例 2： 输入： ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"] [[],[],[5],[2],[],[]] 输出：[null,-1,null,null,5,2] 提示： 1 <= values <= 10000 最多会对 appendTail、deleteHead 进行 10000 次调用
class CQueue {
Stack<Integer> A;
Stack<Integer> B;
public CQueue() {
A = new Stack<>();
B = new Stack<>();
}
public void appendTail(int value) {
A.push(value);
}
public int deleteHead() {
if(B.isEmpty()){
while(!A.isEmpty()){
B.push(A.pop());
}
}
if(B.isEmpty()){
return -1;
}
return B.pop();
}
}
6. 斐波那契数列
写一个函数，输入 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。
示例 1： 输入：n = 2 输出：1 示例 2： 输入：n = 5 输出：5 提示： 0 <= n <= 100
class Solution {
public int fib(int n) {
int a=0,b=1,sum;
for(int i=0;i<n;i++){
sum = (a+b)%1000000007;
a = b;
b = sum;
}
return a;
}
}
7. 青蛙跳台问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1： 输入：n = 2 输出：2 示例 2： 输入：n = 7 输出：21 示例 3： 输入：n = 0 输出：1 提示： 0 <= n <= 100
class Solution {
public int numWays(int n) {
int a = 0,b = 1,sum = 1;
for(int i=0;i<n;i++){
sum = (a+b)%1000000007;
a = b;
b = sum;
}
return sum;
}
}
8. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。
示例 1： 输入：[3,4,5,1,2] 输出：1 示例 2： 输入：[2,2,2,0,1] 输出：0
class Solution {
public int minArray(int[] numbers) {
/**
遍历数组，比较相邻两个值大小关系，
如果大于等于，则继续遍历；
如果小于，则直接返回当前值；
*/
int min = numbers[0];
for(int i=1;i<numbers.length;i++){
if(numbers[i]>=numbers[i-1]){
continue;
}else{
min = numbers[i];
break;
}
}
return min;
}
}
9. 矩阵中的路径
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。
示例 1： 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true 示例 2： 输入：board = [["a","b"],["c","d"]], word = "abcd" 输出：false 提示： 1 <= board.length <= 200 1 <= board[i].length <= 200 board 和 word 仅由大小写英文字母组成
class Solution {
public boolean exist(char[][] board, String word) {
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
if(board[i][j] ==word.charAt(0)){
if(func(i,j,board,word,0)==true){
return true;
}
}
}
}
return false;
}
public boolean func(int i,int j,char[][] board, String word,int index){
if(index==word.length()){
return true;
}else if(i>=0 && i<board.length && j>=0 && j<board[0].length && board[i][j]==word.charAt(index) && board[i][j]!='0'){
char temp = board[i][j];
board[i][j] = '0';
boolean res = func(i,j+1,board,word,index+1)||func(i+1,j,board,word,index+1)||func(i-1,j,board,word,index+1)||func(i,j-1,board,word,index+1);
board[i][j] = temp;
return res;
}else{
return false;
}
}
}
- 回溯
- 该题比较特殊，需要找到每一个可能的作为第一个单词的第一个字母，然后进行搜索；
10.机器人的运动范围
地上有一个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。请问该机器人能够到达多少个格子？ ```java 示例 1：
输入：m = 2, n = 3, k = 1 输出：3 示例 2：
输入：m = 3, n = 1, k = 0 输出：1
提示：
1 <= n,m <= 100 0 <= k <= 20
```java
class Solution {
int count = 0;
int m=0,n=0;
byte[][] isOk;
public int movingCount(int m, int n, int k) {
isOk = new byte[m][n];
this.m = m;
this.n = n;
fun2(0,0,k);
/** 如果需要查看所有矩阵中所有解
for(int i=10;i<m;i+=10){
fun2(i,0,k);
}
for(int j=10;j<n;j+=10){
fun2(0,j,k);
}
for(int i=10,j=10;i<m && j<n;i+=10,j+=10){
fun2(i,j,k);
}
*/
return count;
}
// 递归搜索
public void fun2(int i,int j,int k){
if(!(i>=0 && i<m && j>=0 && j<n && fun1(i)+fun1(j)<=k && isOk[i][j]==0)){
return;
}
count++;
isOk[i][j] = 1;
fun2(i+1,j,k);
fun2(i,j+1,k);
}
// 计算多位数的数字和
public int fun1(int n){
return n%10+n/10;
}
}
- 机器人每次只能走一步，因此部分位置是满足条件的解，但是机器人不可达；
11.剪绳子I
给你一根长度为 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。 ```latex 示例 1：
输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1 示例 2:
输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36 提示：
2 <= n <= 58
```java
class Solution {
public int cuttingRope(int n) {
/**
根据客观规律，尽量剪成长度为3的段，得到的结果最优；
当最后一段是3+1时，那么就剪成两端2；
*/
int a = n%3;
int b = n/3;
if(n==2){
return 1;
}else if(n==3){
return 2;
}
if(b>0){
if(a==1){
return 4*power(3,(b-1));
}else if(a==2){
return 2*power(3,b);
}
}
return power(3,b);
}
public int power(int i,int j){
int res = 1;
for(int k=0;k<j;k++){
res*=i;
}
return res;
}
}
// 对于2^n这样的数进行取模，可以使用位运算提高效率
// m%(2^n) == m&(2^n-1)
12.剪绳子II
给你一根长度为 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。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1： 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1 示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
class Solution {
public int cuttingRope(int n) {
if(n==2){
return 1;
}else if(n==3){
return 2;
}
int a = n/3;
int b = n%3;
long res = 0;
if(b==0){
res =power(3,a);
}else if(b==1){
res = power(3,a-1)*4;
}else if(b==2){
res = power(3,a)*2;
}
return (int)(res%1000000007);
}
public long power(int m,int n){
long res = 1;
for(int i=0;i<n;i++){
res*=m;
res = res%1000000007;
}
return res;
}
}
13.二进制数中1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数。
示例 1： 输入：n = 11 (控制台输入 00000000000000000000000000001011) 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。 示例 2： 输入：n = 128 (控制台输入 00000000000000000000000010000000) 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。 示例 3： 输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3） 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while(n!=0){
if((n&1)==1){
count++;
}
n = n>>>1;
}
return count;
}
}
14. 数值的整数次方
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
示例 1： 输入：x = 2.00000, n = 10 输出：1024.00000 示例 2： 输入：x = 2.10000, n = 3 输出：9.26100 示例 3： 输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
class Solution {
public double myPow(double x, int n) {
if(x==0){
return 0;
}else if(x==1){
return 1;
}
long b = n;
if(b<0){
b = -b;
x = 1.0/x;
}
double res = 1;
while(b>0){
if((b&1)==1){
res *= x;
}
x*=x;
b>>=1;
}
return res;
}
}
输入: n = 1 输出: [1,2,3,4,5,6,7,8,9]
说明：
用返回一个整数列表来代替打印 n 为正整数
```java
class Solution {
public int[] printNumbers(int n) {
int m = fun(n);
int[] res = new int[m];
for(int i=0;i<m;i++){
res[i] = i+1;
}
return res;
}
public int fun(int n){
return (int)Math.pow(10,n)-1;
}
}
16. 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 示例 2: 输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode res = head;
ListNode temp = head;
if(temp.val==val){
return head.next;
}
while(temp!=null){
if(temp.next.val==val){
temp.next = temp.next.next;
return res;
}
temp = temp.next;
}
return res;
}
}
17.调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
前后指针：
class Solution {
public int[] exchange(int[] nums) {
int i = 0;
int j = nums.length-1;
while(i<j){
while(i<j && (nums[i]&1)==1){
i++;
}
while(i<j && (nums[j]&1)==0){
j--;
}
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
return nums;
}
}
顺序双指针：
class Solution {
public int[] exchange(int[] nums) {
// 双指针
for(int i=0;i<nums.length;i++){
if((nums[i]&1)==0){// 找到了第一个偶数
for(int j=i;j<nums.length;j++){
if((nums[j]&1)==1){// 找一个基数与之交换位置
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
break;
}
if(j==nums.length-1){
return nums;
}
}
}
}
return nums;
}
}
18. 链表的倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例： 给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
// 双指针
ListNode poninter1 = head;
ListNode poninter2 = head;
for(int i=0;i<k;i++){
poninter1 = poninter1.next;
}
while(poninter1!=null){
poninter1 = poninter1.next;
poninter2 = poninter2.next;
}
return poninter2;
}
}
19.反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
class Solution {
public ListNode reverseList(ListNode head) {
// 头插法
ListNode res = new ListNode();
ListNode temp = head;
while(temp!=null){
ListNode newNode = new ListNode(temp.val);
newNode.next = res.next;
res.next = newNode;
temp = temp.next;
}
return res.next;
}
}
20.合并两个排序链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 限制： 0 <= 链表长度 <= 1000
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode res = new ListNode();
ListNode temp = res;
while(l1!=null && l2!=null){
if(l1.val <= l2.val){
temp.next = new ListNode(l1.val);
l1 = l1.next;
}else{
temp.next = new ListNode(l2.val);
l2 = l2.next;
}
temp = temp.next;
}
if(l1==null){
while(l2!=null){
temp.next = new ListNode(l2.val);
temp = temp.next;
l2 = l2.next;
}
}
if(l2==null){
while(l1!=null){
temp.next = new ListNode(l1.val);
temp = temp.next;
l1 = l1.next;
}
}
return res.next;
}
}
21.二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入： 4 / \ 2 7 / \ / \ 1 3 6 9 镜像输出： 4 / \ 7 2 / \ / \ 9 6 3 1 示例 1： 输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
class Solution {
public TreeNode mirrorTree(TreeNode root) {
fun(root);
return root;
}
public void fun(TreeNode root){
if(root==null) return;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
fun(root.left);
fun(root.right);
}
}
22.对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3 示例 1： 输入：root = [1,2,2,3,4,4,3] 输出：true 示例 2： 输入：root = [1,2,2,null,3,null,3] 输出：false
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}else{
return fun(root.left,root.right);
}
}
public boolean fun(TreeNode left,TreeNode right){
if(left==null && right==null){
return true;
}else if(left==null || right==null){
return false;
}else{
if(left.val == right.val){
return fun(left.left,right.right)&&fun(left.right,right.left);
}
}
return false;
}
}
23.顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1： 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5] 示例 2： 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
class Solution {
int[] res;
int index = 0;
public int[] spiralOrder(int[][] matrix) {
if(matrix.length==0){
return new int[]{};
}
res = new int[matrix.length*matrix[0].length];
fun(matrix,0,0,1);
return res;
}
public void fun(int[][] matrix,int i,int j,int k){
if(i>=0 && i<matrix.length && j>=0 && j<matrix[0].length && matrix[i][j]!=-8){
res[index++] = matrix[i][j];
matrix[i][j] = -8;
if(k==1){
fun(matrix,i,j+1,1);
fun(matrix,i+1,j,2);
}else if(k==2){
fun(matrix,i+1,j,2);
fun(matrix,i,j-1,3);
}else if(k==3){
fun(matrix,i,j-1,3);
fun(matrix,i-1,j,4);
}else{
fun(matrix,i-1,j,4);
fun(matrix,i,j+1,1);
}
}
}
}
24.包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.
class MinStack {
int[] stack1 = new int[10000];
int[] stack2 = new int[10000];
int index1 = -1;
int index2 = -1;
int min = 0;
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
stack1[++index1] = x;
if(index2==-1||x<=min){
min = x;
stack2[++index2] = x;
}
}
public void pop() {
if(index1==-1){
return;
}
if(stack1[index1]==stack2[index2]){
index2--;
if(index2!=-1){
min = stack2[index2];
}
}
index1--;
}
public int top() {
return stack1[index1];
}
public int min() {
return stack2[index2];
}
}
25.栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
// 设置一个栈来模拟
Stack<Integer> stack = new Stack<>();
int i = 0;
int j = 0;
for(;i<pushed.length;i++){
stack.push(pushed[i]);
while(j<popped.length && !stack.isEmpty() && stack.peek()==popped[j]){
stack.pop();
j++;
}
}
if(j>=popped.length){
return true;
}else{
return false;
}
}
}
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
// 设置一个栈来模拟
Stack<Integer> stack = new Stack<>();
int i = 0;
for(int n : pushed){
stack.push(n);
while(!stack.isEmpty() && stack.peek()==popped[i]){
stack.pop();
i++;
}
}
return stack.isEmpty();
}
}
26.从上到下打印二叉树
层序遍历
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果： [ [3], [9,20], [15,7] ]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if(root!=null){
queue.add(root);
queue.add(new TreeNode(Integer.MAX_VALUE));
}
List<Integer> list = new ArrayList<>();
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
if(temp.val==Integer.MAX_VALUE){
res.add(list);
list = new ArrayList<>();
if(queue.isEmpty()){
break;
}
queue.add(new TreeNode(Integer.MAX_VALUE));
continue;
}
list.add(temp.val);
if(temp.left!=null){
queue.add(temp.left);
}
if(temp.right!=null){
queue.add(temp.right);
}
}
return res;
}
}
关于队列中每一层标记的优秀解法：获取队列的大小size；
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()){
int size = queue.size();
List<Integer> list = new ArrayList<>();
for(int i=0;i<size;i++){
TreeNode temp = queue.poll();
list.add(temp.val);
if(temp.left!=null){
queue.add(temp.left);
}
if(temp.right!=null){
queue.add(temp.right);
}
}
res.add(list);
}
return res;
}
}
27.从上到下打印二叉树2
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果： [ [3], [20,9], [15,7] ]
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root!=null){
queue.add(root);
}
while(!queue.isEmpty()){
int size = queue.size();
LinkedList<Integer> list = new LinkedList<>();
for(int i=0;i<size;i++){
TreeNode temp = queue.poll();
if(res.size()%2==0){
list.addLast(temp.val);
}else{
list.addFirst(temp.val);
}
if(temp.left!=null){
queue.add(temp.left);
}
if(temp.right!=null){
queue.add(temp.right);
}
}
res.add(list);
}
return res;
}
}
28.数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2
class Solution {
public int majorityElement(int[] nums) {
/**
1. 使用Hash来计数统计重复值的个数，然后遍历哈希表，比较值是否大于数组长度的一半；
2. 排序，由于该众数超过了数组长度的一半，所以排序后数组中最中间位置必然是该众数；
3. 摩尔投票法，众数超过数组元素个数的一半，所以可以让不同的数相互抵消，最终留下的必然是众数；
*/
// 摩尔投票法
int x = 0,vote = 0;
for(int num : nums){
if(vote==0){
x = num;
}
vote += num==x?1:-1;
}
return x;
}
}
29.复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1： 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例 2： 输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
// 添加到hash中
Node cur = head;
Map<Node,Node> map = new HashMap<>();
while(cur!=null){
map.put(cur,new Node(cur.val));
cur = cur.next;
}
cur = head;
Node res = map.get(cur);
Node temp = res;
while(cur!=null){
temp.next = map.get(cur.next);
temp.random = map.get(cur.random);
cur = cur.next;
temp = temp.next;
}
return res;
}
}
30.连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
for(int i=1;i<nums.length;i++){
nums[i] += Math.max(nums[i-1],0);
res = Math.max(res,nums[i]);
}
return res;
}
}
31.数字数列中某一位数字
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
示例 1： 输入：n = 3 输出：3 示例 2： 输入：n = 11 输出：0
class Solution {
public int findNthDigit(int n) {
if(n<10){
return n;
}
long x = 10;
long y = 2;
long sum = n-9;
while(true){
long temp = (x*10-x)*y;
if(sum<temp){
long a = (sum-1)%y;
long b = (sum-1)/y;
String s = ""+(x+b);
char c = s.charAt((int)a);
return c-'0';
}
x*=10;
y++;
sum -= temp;
}
}
}
/**
9 90 900 9000
9 180 2700 36000
*/
32.把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1: 输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi" 提示： 0 <= num < 231
class Solution {
public int translateNum(int num) {
String s = num+"";
int a = 1, b = 1;
int length = s.length();
for(int i = 0;i<length-1;i++){
String temp = s.substring(i,i+2);
int c = temp.compareTo("10")>=0 && temp.compareTo("25")<=0 ? a+b : b;
a = b;
b = c;
}
return b;
}
}
33.礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
class Solution {
public int maxValue(int[][] grid) {
// 动态规划
int a = 0,b = 0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(i-1<0){
a = 0;
}else{
a = grid[i-1][j];
}
if(j-1<0){
b = 0;
}else{
b = grid[i][j-1];
}
grid[i][j]+=Math.max(a,b);
}
}
return grid[grid.length-1][grid[0].length-1];
}
}
若有收获，就点个赞吧
0 人点赞
