算法挑战第六天
3.无重复字符的最长子串
给定一个字符串s，请你给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
思路：利用双指针和Set集合维护一个滑动窗口，在遍历的过程中，比较滑动窗口值的大小。
class Solution {
public int lengthOfLongestSubstring(String s) {
int max = 0;
int rk = 0,len = s.length();
HashSet<Character> set = new HashSet<>();
for(int i = 0;i < len;i++){
if(i != 0){
set.remove(s.charAt(i - 1));
}
while(rk < len && !set.contains(s.charAt(rk))){
set.add(s.charAt(rk));
rk++;
}
max = Math.max(max, rk - i);
}
return max;
}
}
567.字符串的排列
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
思路：是某个的排列，说明字母在定义的数组中的位置和大小值相等，因此，利用s1维护一个滑动窗口，不断变化滑动窗口中的元素，在遍历中不断比较两个数组是否相等即可。
class Solution {
public boolean checkInclusion(String s1, String s2) {
int n = s1.length(), m = s2.length();
if(n > m) return false;
int[] cnt1 = new int[26];
int[] cnt2 = new int[26];
for(int i=0;i < n;i++){
++cnt1[s1.charAt(i) - 'a'];
++cnt2[s2.charAt(i) - 'a'];
}
if(Arrays.equals(cnt1,cnt2)){
return true;
}
for(int i = n;i < m;i++){
++cnt2[s2.charAt(i) - 'a'];
--cnt2[s2.charAt(i - n) - 'a'];
if(Arrays.equals(cnt1,cnt2)){
return true;
}
}
return false;
}
}
参考：
欢迎分享，点个在读
同名博客CodeJames
算法挑战第七天
733.图像渲染
有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0到 65535 之间。
给你一个坐标 (sr, sc)表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
最后返回经过上色渲染后的图像。
示例 1:
输入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析:
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。
思路：采用广度优先遍历的方式，建立队列，向四个方向进行遍历，和给定的初始位置值相等进行赋值。
class Solution {
int[] dx = {1,0,-1,0};
int[] dy = {0,1,0,-1};
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int currColor = image[sr][sc];
if(currColor == newColor){
return image;
}
int row = image.length, col = image[0].length;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{sr,sc});
image[sr][sc] = newColor;
while(!queue.isEmpty()){
int[] tmp = queue.poll();
int x = tmp[0], y = tmp[1];
for(int i = 0;i < 4;i++){
int mx = x + dx[i];
int my = y + dy[i];
if(mx >= 0 && my >= 0 && mx < row && my < col && image[mx][my] == currColor){
queue.offer(new int[]{mx,my});
image[mx][my] = newColor;
}
}
}
return image;
}
}
695. 岛屿的最大面积
给定一个包含了一些 0和 1 的非空二维数组grid。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个1必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
思路：采用深度优先遍历，从四个方向进行深度遍历，将遍历值是1的值进行替换成0，并进行计数，返回比较大小。
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int row = grid.length, col = grid[0].length;
int ans = 0;
for(int i=0;i < row;i++){
for(int j = 0;j < col;j++){
ans = Math.max(ans,dfs(grid,i,j));
}
}
return ans;
}
public int dfs(int[][] grid,int i, int j){
if(i < 0 || j < 0 || j >= grid[0].length || i >= grid.length || grid[i][j] != 1){
return 0;
}
grid[i][j] = 0;
int[] dx = {1,0,-1,0};
int[] dy = {0,1,0,-1};
int ans = 1;
for(int m = 0;m < 4;m++){
int x = i + dx[m];
int y = j + dy[m];
ans += dfs(grid,x,y);
}
return ans;
}
}
参考：
欢迎分享，点个在读
同名博客CodeJames
算法挑战第七天
617. 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
思路：从根节点开始向下进行深度遍历，遍历的过程中进行节点值处理
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1 == null){
return root2;
}
if(root2 == null){
return root1;
}
TreeNode merged = new TreeNode(root1.val + root2.val);
merged.left = mergeTrees(root1.left,root2.left);
merged.right = mergeTrees(root1.right,root2.right);
return merged;
}
}
116. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为NULL。
初始状态下，所有 next 指针都被设置为 NULL。
思路：进行树的层次遍历，利用next指针指向后续的结点。
class Solution {
public Node connect(Node root) {
if(root == null) return root;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i=0;i<size;i++){
Node node = queue.poll();
if(i < size - 1){
node.next = queue.peek();
}
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
}
}
return root;
}
}
参考：
欢迎分享，点个在读
同名博客CodeJames
算法挑战第九天
542. 01 矩阵
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]
思路：题目是找与零最近的距离，首先找到零点位置，从零点位置开始广度优先遍历，遍历过的进行记录，防止重复遍历。
class Solution {
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
public int[][] updateMatrix(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[][] dist = new int[m][n];
boolean[][] seen = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(mat[i][j] == 0){
queue.offer(new int[]{i,j});
seen[i][j] = true;
}
}
}
while(!queue.isEmpty()){
int[] cell = queue.poll();
int i = cell[0], j = cell[1];
for(int d = 0; d < 4;++d){
int ni = i + dirs[d][0];
int nj = j + dirs[d][1];
if(ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]){
dist[ni][nj] = dist[i][j] + 1;
queue.offer(new int[]{ni,nj});
seen[ni][nj] = true;
}
}
}
return dist;
}
}
同名微信公众号
