21.给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组
[0,1,0,2,1,0,1,3,2,1,2,1]表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
栈解法
说到栈，我们肯定会想到括号匹配了。我们仔细观察蓝色的部分，可以和括号匹配类比下。每次匹配出一对括号（找到对应的一堵墙），就计算这两堵墙中的水。
我们用栈保存每堵墙。
当遍历墙的高度的时候，如果当前高度小于栈顶的墙高度，说明这里会有积水，我们将墙的高度的下标入栈。
如果当前高度大于栈顶的墙的高度，说明之前的积水到这里停下，我们可以计算下有多少积水了。计算完之后继续判断 当前的墙和新的栈顶的关系。如果栈空，就把当前的墙继续入栈，作为新的积水的墙。
而对于计算current 指向墙和新的栈顶之间的水，根据图的关系
current指向的高度大于栈顶高度，栈顶height [ 2 ]出栈。计算 height [ 3 ]和新的栈顶之间(这里指height[1])的水请看代码注释
package wg;
import java.util.Stack;
public class Solution {
public static int trap(int[] height){
int sum=0;
Stack<Integer> stack = new Stack<>();
int i = 0;
int len = height.length;
while(i<len){
////如果栈不空并且当前指向的高度大于栈顶高度就一直循环
while(!stack.isEmpty()&&height[i]>height[stack.peek()]){
int h = height[stack.peek()];//取出要出栈的元素 用于最小高度减去该高度来求得积水的高度
stack.pop();//出栈
if(stack.isEmpty()){// 栈空就出去 表示是1 2 这样 1 和2 之间没有间隔 积不了水
break;
}
int distance = i-stack.peek()-1;//两堵墙之前的距离。
int minh = Math.min(height[i],height[stack.peek()]);//注意这里的stack.peek()是新的栈顶，他俩的大小是不知道的，进来的条件是height[i]>原来的栈顶
sum+=(minh-h)*distance;
}
stack.push(i);////当前指向的墙入栈
i++;
}
return sum;
}
public static void main(String[] args) {
int[] nums={0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println(trap(nums));
}
}
另一种方法
翻山越岭填坑大法
遍历一次找到最大值，左右两边分别遍历依次补全，即可得雨水收集
翻山越岭填坑大法
最高为A，将整个模型对半切，一半为从左到右爬,一半为从右到左爬。
public static int trap(int[] height) {
int max = 0;//最大值多少
int maxIndex = 0;//最大值的位置
//寻找A点
for (int i = 0; i < height.length; i++) {
if(height[i]>max){
max = height[i];
maxIndex =i;
}
}
int maxLeft = 0;//左边的最大值
int result = 0;
//计算从左到右爬的雨水收集
for (int i = 0; i < maxIndex; i++) {
if(height[i]>maxLeft){
maxLeft = height[i];
}else {
result += maxLeft-height[i];
}
}
int maxRight = 0;
//计算从右到左爬的雨水收集
for (int i = height.length-1; i > maxIndex ; i--) {
if(height[i]>maxRight){
maxRight = height[i];
}else {
result += maxRight - height[i];
}
}
return result;
}
22.给定一个没有重复数字的序列，返回其所有可能的全排列。
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
经典的回溯法
package wg;
import java.util.*;
public class Solution {
public static void backtrack(int n,
ArrayList<Integer> nums,
List<List<Integer>> output,
int first) {
if (first == n)
output.add(new ArrayList<Integer>(nums));
for (int i = first; i < n; i++) {
Collections.swap(nums, first, i);
backtrack(n, nums, output, first + 1);
Collections.swap(nums, first, i);
}
}
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> output = new LinkedList();
ArrayList<Integer> nums_lst = new ArrayList<Integer>();
for (int num : nums)
nums_lst.add(num);
int n = nums.length;
backtrack(n, nums_lst, output, 0);
return output;
}
public static void main(String[] args) {
int[] nums={1,2,3};
List<List<Integer>> res = new LinkedList<>();
res = permute(nums);
System.out.println(res);
//[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
}
}
23.给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
将给定的矩阵分成四个矩形并且将原问题划归为旋转这些矩形的问题。
自外向内一共有不超过n/2层（单个中心元素不算一层）矩形框。对于第i层矩形框，其框边长len=nums-(i*2)，将其顺时针分为4份len-1的边，对四条边进行元素的循环交换即可。注意这里说层对于第 i 层矩形框，其框边长len=nums-(i*2)然后分成4份的边又为len-1
public void rotate(int[][] matrix) {
if(matrix.length == 0 || matrix.length != matrix[0].length) {
return;
}
int nums = matrix.length;
int times = 0;
while(times < (nums >> 1)){
int len = nums - (times << 1);
for(int i = 0; i < len - 1; ++i){//i这里表示行
int temp = matrix[times][times + i];//第times列第times + i行
matrix[times][times + i] = matrix[times + len - i - 1][times];
matrix[times + len - i - 1][times] = matrix[times + len - 1][times + len - i - 1];
matrix[times + len - 1][times + len - i - 1] = matrix[times + i][times + len - 1];
matrix[times + i][times + len - 1] = temp;
}
++times;//列加加
}
}
24.给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
解法1
算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。
利用这个，我们把每个字符串都映射到一个正数上。
用一个数组存储质数 prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103}。
然后每个字符串的字符减去 ' a ' ，然后取到 prime中对应的质数。把它们累乘。
例如 abc ，就对应'a' - 'a'， 'b' - 'a'， 'c' - 'a'，即 0, 1, 2，也就是对应素数2 3 5，然后相乘 2 * 3 * 5 = 30，就把abc 映射到了 30。
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<Integer, List<String>> hash = new HashMap<>();
//每个字母对应一个质数
int[] prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103 };
for (int i = 0; i < strs.length; i++) {
int key = 1;
//累乘得到 key
for (int j = 0; j < strs[i].length(); j++) {
key *= prime[strs[i].charAt(j) - 'a'];
}
if (hash.containsKey(key)) {
hash.get(key).add(strs[i]);
} else {
List<String> temp = new ArrayList<String>();
temp.add(strs[i]);
hash.put(key, temp);
}
}
return new ArrayList<List<String>>(hash.values());
}
一定的局限性，因为求 key 的时候用的是累乘，可能会造成溢出，超出 int 所能表示的数字。
解法2
首先初始化 key = "0#0#0#0#0#"，数字分别代表 abcde 出现的次数，# 用来分割。
这样的话，"abb" 就映射到了 "1#2#0#0#0"。
"cdc" 就映射到了 "0#0#2#1#0"。
"dcc" 就映射到了 "0#0#2#1#0"。
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> hash = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
int[] num = new int[26];
//记录每个字符的次数
for (int j = 0; j < strs[i].length(); j++) {
num[strs[i].charAt(j) - 'a']++;
}
//转成 0#2#2# 类似的形式
String key = "";
for (int j = 0; j < num.length; j++) {
key = key + num[j] + '#';
}
if (hash.containsKey(key)) {
hash.get(key).add(strs[i]);
} else {
List<String> temp = new ArrayList<String>();
temp.add(strs[i]);
hash.put(key, temp);
}
}
return new ArrayList<List<String>>(hash.values());
}
25.给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
动态规划
首先对数组进行遍历，设当前最大连续子序列和为sum，结果为ans
如果sum > 0，则说明sum对结果有增益效果，则 sum 保留并加上当前遍历数字
如果sum <= 0，则说明sum对结果无增益效果，需要舍弃，则sum直接更新为当前遍历数字
每次比较sum和ans的大小，将最大值置为ans，遍历结束返回结果
时间复杂度：O(n)
package wg;
import java.util.*;
public class Solution {
public static int maxSubArray(int[] nums){
int ans = nums[0];
int sum=0;
for(int i =0,j=nums.length;i<j;i++){
if(sum<=0){
sum=nums[i];
}else{
sum+=nums[i];
}
ans=Math.max(sum,ans);
}
return ans;
}
public static void main(String[] args) {
int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
System.out.println(maxSubArray(nums));
//6
}
}
26.给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
如果我们可以从数组中的某个位置跳到最后的位置，就称这个位置是“好坐标”，否则称为“坏坐标”。问题可以简化为第 0 个位置是不是“好坐标”。
首先判断倒数第二个元素能否到达最后一个元素，如果可以，我们将不再考虑最后一个元素，
因为根据刚才的分析如果可以到达倒数第二个，那么也可以到达最后一个元素。
然后依次往前递推，如果都能跳到的话，我们最后应该分析的就是第一个元素能否跳到第二个元素上。
这个比较符合动态规划的思想
动态规划解决
public boolean canJump(int[] nums){
int len = nums.length;
if(len==0)
return false;
boolean[] dp = new boolean[len];
dp[0]=true;
for(int i=1;i<len;i++){
for(int j=0;j<i;j++){
//// 如果之前的j节点可达，并且从此节点可以到跳到i
if(dp[j]&&nums[j]+j>=i){
dp[i]=true;
break;
}
}
}
return dp[len-1];
}
贪心解决
使用贪心的思路看下这个问题，我们记录一个的坐标代表当前可达的最后节点，这个坐标初始等于
nums.length-1，
然后我们每判断完是否可达，都向前移动这个坐标，直到遍历结束。
如果这个坐标等于0，那么认为可达，否则不可达。
public boolean canJump(int[] nums){
int len = nums.length;
if(len==0)
return false;
int lastp = len-1;
for(int i=lastp;i>=0;i--){
//// 逐步向前递推
if(nums[i]+i>=lastp){
lastp=i;
}
}
if(lastp==0)
return true;
else
return false;
}
27.给出一个区间的集合，请合并所有重叠的区间。
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
先把所有区间按照第一个值进行排序，通过后一个区间的左坐标值与前一个区间的右坐标值进行比较，便可以确定是否有重合
用Arrays.deepToString()打印二维数组
package wg;
import java.util.*;
public class Solution {
public static int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList<>();
if (intervals.length == 0 || intervals == null) return res.toArray(new int[0][]);
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int i = 0;
while (i < intervals.length) {
int left = intervals[i][0];
int right = intervals[i][1];
//满足区间合并条件 直到下一个区间的首数字大于right
while (i < intervals.length - 1 && intervals[i + 1][0] <= right) {
i++;
right = Math.max(right, intervals[i][1]);
}
res.add(new int[]{left, right});
i++;
}
return res.toArray(new int[0][]);
}
public static void main(String[] args) {
int[][] nums ={{1,3},{2,6},{8,10},{15,18}};
System.out.println(Arrays.deepToString(merge(nums)));
//[[1, 6], [8, 10], [15, 18]]
}
}
28.一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。m 和 n 的值均不超过 100
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
动态规划
我们令dp[i][j]是到达 i, j 最多路径
动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
注意，对于第一行dp[0][j]，或者第一列dp[i][0]，由于都是在边界，所以只能为1。路径只有一条横着走或者竖着走
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < n; i++) dp[0][i] = 1;
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
可以优化空间
public int uniquePaths(int m, int n) {
int[] cur = new int[n];
Arrays.fill(cur,1);
for (int i = 1; i < m;i++){
for (int j = 1; j < n; j++){
cur[j] += cur[j-1] ;
}
}
return cur[n-1];
}
29.给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小
动态规划：自顶向下计算方法：每次只能向右或者向下走，分析其中一个点，
1.在经过第一列的每个点D(i,0)时：必然经过点D(i-1,0),那么第一列的状态转移方程为：f(i,0)=f(i-1,0)+D(i,0)
2.在经过第一行的每个点D(0,j)时：必然经过点D(0,j-1),那么第一行的状态转移方程为：f(0,j)=f(0,j-1)+D(0,j)
3.在经过非边界点D(i,j)时，必然经过具有min(f(i,j-1),f(i-1,j))的点，那么非边界点的状态转移方程为：
f(i,j)=min(f(i,j-1),f(i-1,j))+D(i,j)
package wg;
import java.util.*;
public class Solution {
public static int minPathSum(int[][] grid){
int m=grid.length;
int n=grid[0].length;
int[][] res = new int[m][n];
res[0][0]=grid[0][0];//起点的步数等于自身
//第一行
for(int i=1;i<n;i++){
res[0][i]=res[0][i-1]+grid[0][i];
}
//第一列
for(int i=1;i<m;i++){
res[i][0]=res[i-1][0]+grid[i][0];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
res[i][j]=Math.min(res[i-1][j],res[i][j-1])+grid[i][j];
}
}
return res[m-1][n-1];
}
public static void main(String[] args) {
int[][] nums={{1,3,1},{1,5,1},{4,2,1}};
System.out.println(minPathSum(nums));
//7
}
}
30.假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
斐波那契数列
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
网友评论