75. 颜色分类【中等】
75.颜色分类
中等
1.6K
相关企业
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1： 输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2] 示例 2： 输入：nums = [2,0,1] 输出：[0,1,2]
提示：
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2
进阶：
你能想出一个仅使用常数空间的一趟扫描算法吗？
排序
class Solution { public void sortColors(int[] nums) { for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length-1-i; j++) { if (nums[j]>nums[j+1]){ swap(nums,j,j+1); } } } } public static void swap(int[] nums,int i,int j){ int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } }
76. 最小覆盖子串【困难】
76.最小覆盖子串
困难
2.6K
相关企业
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1： 输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。 示例 2： 输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。 示例 3: 输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
提示：
m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成
进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
参考
滑动窗口
class Solution { Map<Character,Integer> ori=new HashMap<>();//t的字母统计 Map<Character,Integer> cnt=new HashMap<>();//窗口中的字母统计 public String minWindow(String s, String t) { //统计t的字母 int tLen=t.length(); for(int i=0;i<tLen;i++){ char c=t.charAt(i); ori.put(c,ori.getOrDefault(c,0)+1); } //窗口 int l=0,r=-1; int len=Integer.MAX_VALUE,ansL=-1,ansR=-1; int sLen=s.length(); //滑动 while(r<sLen){ ++r; if(r<sLen&&ori.containsKey(s.charAt(r))){ cnt.put(s.charAt(r),cnt.getOrDefault(s.charAt(r),0)+1); } //左移缩小窗口 while(check()&&l<=r){ if(r-l+1<len){ len=r-l+1; ansL=l; ansR=l+len; } if(ori.containsKey(s.charAt(l))){ cnt.put(s.charAt(l),cnt.getOrDefault(s.charAt(l),0)-1); } ++l; } } return ansL==-1?"":s.substring(ansL,ansR); } //检查是否符合覆盖条件 public boolean check(){ Iterator iter=ori.entrySet().iterator(); while(iter.hasNext()){ Map.Entry entry=(Map.Entry) iter.next(); Character key=(Character) entry.getKey(); Integer val=(Integer) entry.getValue(); if(cnt.getOrDefault(key,0)<val){ return false; } } return true; } }
78. 子集【中等】
78.子集
中等
2.1K
相关企业
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1： 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2： 输入：nums = [0] 输出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
参考
回溯
class Solution { List<Integer> t=new ArrayList<>(); List<List<Integer>> ans=new ArrayList<List<Integer>>(); //回溯 public List<List<Integer>> subsets(int[] nums) { dfs(0,nums); return ans; } public void dfs(int cur, int[] nums) { if(cur==nums.length){ ans.add(new ArrayList<Integer>(t)); return; } t.add(nums[cur]); dfs(cur+1,nums); t.remove(t.size()-1); dfs(cur+1,nums); } }
79. 单词搜索【中等】
79.单词搜索
中等
1.6K
相关企业
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1： 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true 示例 2： 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" 输出：true 示例 3： 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出：false
提示：
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
官方
回溯
class Solution { public boolean exist(char[][] board, String word) { int h = board.length, w = board[0].length; boolean[][] visited = new boolean[h][w]; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { boolean flag = check(board, visited, i, j, word, 0); if (flag) { return true; } } } return false; } public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) { if (board[i][j] != s.charAt(k)) { return false; } else if (k == s.length() - 1) { return true; } visited[i][j] = true; int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; boolean result = false; for (int[] dir : directions) { int newi = i + dir[0], newj = j + dir[1]; if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) { if (!visited[newi][newj]) { boolean flag = check(board, visited, newi, newj, s, k + 1); if (flag) { result = true; break; } } } } visited[i][j] = false; return result; } }
84. 柱状图中最大的矩形【困难】
84.柱状图中最大的矩形
困难
2.5K
相关企业
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1: 输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10 示例 2： 输入： heights = [2,4] 输出： 4
提示：
1 <= heights.length <=105
0 <= heights[i] <= 104
参考
栈
class Solution { public int largestRectangleArea(int[] heights) { int len=heights.length; if(len==0){ return 0; }else if(len==1){ return heights[0]; } int area = 0; Deque<Integer> stack=new ArrayDeque<>(); for(int i=0;i<len;i++){ //如果当前栈顶高度大于遍历到的高度，右边较低了到右边界，从左扫弾栈 while(!stack.isEmpty()&&heights[stack.peekLast()]>heights[i]){ //栈顶的高度 int height=heights[stack.removeLast()]; //栈顶与新栈顶高度一样弹出即可 while(!stack.isEmpty()&&heights[stack.peekLast()]==height){ stack.removeLast(); } int width; //如果刚好为空 即左边界在当前遍历 if(stack.isEmpty()){ width=i; }else{//否则，左边界在新栈顶 width=i-stack.peekLast()-1; } area=Math.max(area,width*height); } //当前栈顶高度小于遍历到的高度，压栈 stack.addLast(i); } //如果栈中还有元素，就是右边界在最右边 while(!stack.isEmpty()){ //栈顶的高度 int height=heights[stack.removeLast()]; //栈顶与新栈顶高度一样弹出即可 while(!stack.isEmpty()&&heights[stack.peekLast()]==height){ stack.removeLast(); } int width; //如果刚好为空 即左边界在最左边 if(stack.isEmpty()){ width=len; }else{//否则，左边界在新栈顶 width=len-stack.peekLast()-1; } area=Math.max(area,width*height); } return area; } }
参考
栈
class Solution { public int largestRectangleArea(int[] heights) { int len=heights.length; if(len==0){ return 0; }else if(len==1){ return heights[0]; } int area = 0; //增加哨兵减少判断 //左哨兵 0 heights 右哨兵 0 int[] newHeights=new int[len+2]; for(int i=0;i<len;i++){ newHeights[i+1]=heights[i]; } len+=2; heights=newHeights; Deque<Integer> stack=new ArrayDeque<>(); stack.addLast(0); for(int i=1;i<len;i++){ //如果当前栈顶高度大于遍历到的高度，右边较低了到右边界，从左扫弾栈 while(heights[stack.peekLast()]>heights[i]){ //栈顶的高度 int height=heights[stack.removeLast()]; //栈顶与新栈顶高度一样弹出即可 //不保留 int width=i-stack.peekLast()-1; area=Math.max(area,width*height); } //当前栈顶高度小于遍历到的高度，压栈 stack.addLast(i); } return area; } }
85. 最大矩形【困难】
85.最大矩形
困难
1.5K
相关企业
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1： 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：6 解释：最大矩形如上图所示。 示例 2： 输入：matrix = [] 输出：0 示例 3： 输入：matrix = [["0"]] 输出：0 示例 4： 输入：matrix = [["1"]] 输出：1 示例 5： 输入：matrix = [["0","0"]] 输出：0
提示：
rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j] 为 ‘0’ 或 ‘1’
参考
class Solution { public int maximalRectangle(char[][] matrix) { int m=matrix.length; if(m==0){ return 0; } int n=matrix[0].length; //存储左边连续的1的数量 int [][] left=new int[m][n]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(matrix[i][j]=='1'){ left[i][j]=(j==0?0:left[i][j-1])+1; } } } int ret=0; //遍历作为矩形右下角 for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(matrix[i][j]=='0'){ continue; } int width=left[i][j]; int area=width; //往上查找 for(int k=i-1;k>=0;k--){ //取得最小宽度 width=Math.min(width,left[k][j]); //计算面积 area=Math.max(area,(i-k+1)*width); } ret=Math.max(ret,area); } } return ret; } }
参考
栈
class Solution { public int maximalRectangle(char[][] matrix) { int m = matrix.length; if (m == 0) { return 0; } int n = matrix[0].length; //存储左边连续的1的数量 int[][] left = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == '1') { left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1; } } } int ret = 0; //对于每一列，使用基于柱状图的方法 for (int j = 0; j < n; j++) { int[] up = new int[m];//上 int[] down = new int[m];//下 Deque<Integer> stack = new LinkedList<Integer>(); //赋值up for (int i = 0; i < m; i++) { //如果栈顶宽度大于遍历的 弾栈 while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) { stack.pop(); } //赋值 up[i] = stack.isEmpty() ? -1 : stack.peek(); //否则压栈 stack.push(i); } stack.clear(); //复制down for (int i = m - 1; i >= 0; i--) { while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) { stack.pop(); } down[i] = stack.isEmpty() ? m : stack.peek(); stack.push(i); } //计算面积 for (int i = 0; i < m; i++) { int height = down[i] - up[i] - 1; int area = height * left[i][j]; ret = Math.max(ret, area); } } return ret; } }
