LeetCode 130被围绕的区域

题目

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。找到所有被 ‘X’
围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充

思路

1.所有与四条边相连的O都保留，其他O都变为X
2.遍历四条边上的O，并深度遍历与其相连的O，将这些O都转为-
3. 将剩余的O变为X
4. 将剩余的*变为O

代码

    int rowNum = 0;
    int colNum = 0;
    public void solve(char[][] board) {
     if(board==null||board.length<=0||board[0].length<0)
        return;    
        
     rowNum = board.length;
     colNum = board[0].length;
     for(int i=0;i<colNum;++i) {//对第一排和最后一排的O进行深度遍历
        dfs(board,0,i);
        dfs(board,rowNum-1,i);
     }

     for(int i = 0; i<rowNum ;++i) {
        dfs(board,i,0);
        dfs(board,i,colNum-1);
     }

     //将除了四个边以及他们关联的o全部替换 
     for(int i=0;i<rowNum;++i) {
        for(int j=0;j<colNum;++j) {
            if(board[i][j]=='O')
                board[i][j]='X';
      }
    }

     for(int i=0;i<rowNum;++i) {
        for(int j=0;j<colNum;++j) {
            if(board[i][j]=='-')
                board[i][j]='O';
       }
     }
    }

    

    //深度遍历，搜索与四周关联的o并全部置为-
    private void dfs(char[][] board,int row,int col) {
     if(board[row][col]=='O') {
        board[row][col]='-'; //如果这个位置是O，置为-
        if(row>1)          
            dfs(board,row-1,col); //向上（i>1时候才需要向上，因为i=0肯定会被执行，不需要考虑。）
        if(col>1)                  
            dfs(board,row,col-1); //向左（理由同上，但是写col>=1;row>=1也成立，但是不需要，因为i=1向上深度搜索没必要）
        if(row<rowNum-1)           
            dfs(board,row+1,col); //向下      
        if(col<colNum-1)           
            dfs(board,row,col+1);//向右
     }
    }

LeetCode 129 求跟到叶子节点数字的和

题目

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和.
说明: 叶子节点是指没有子节点的节点。

思路

参考的别人的代码
深度优先遍历，层次遍历。上一层结果×10，分别加上其两个子节点，最后整体相加即可。

代码

    	public int sumNumbers(TreeNode root) {
		return dfs(root,0);
 	  }

    	private int dfs(TreeNode root , int sum) {
		if(root == null)  return 0;
     		sum = sum*10+root.val;//上层结果×10+子节点的值
     		if(root.left==null&&root.right==null) 
	          	return sum;
	       	return dfs(root.left,sum)+dfs(root.right,sum);
   }

LeetCode674 最长连续递增序列

题目

给定一个未经排序的整数数组，找到最长且连续的的递增序列。

思路

暴力

代码

public static int findLengthOfLCIS(int[] nums) {  
     if(nums.length<2)
        return nums.length;
     int max = 1;
     int count = 1;
     for(int i=1;i<nums.length;++i) {  //注意i的范围，下面用到了i-1.索引i应该在[0,LENGTH-1]
        if(nums[i-1]<nums[i]) {
            count++;
            max = Math.max(max, count);
        }else
            count = 1;             
     }
     return max;
}

LeetCode128 最长连续序列(674进阶)

题目

给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。

思路

使用HashMap进行查找，因为HashMap的查找复杂度为O（1）
Map的key值为数组中的数值，value为最长连续元素的个数

1. 如果map中已经包含了数字n，则跳过
2. 若没有包含，则先查看map中是否存在n-1和n+1
   1. 如果存在n-1，那么包含n-1的最长连续子序列有 left= map.get(n-1)个连续元素
   2. 如果存在n+1，……（这是因为n一开始并不存在与map中，所以n-1和n+1并没有连续性）
   3. Key为n的值的value = left+right+1;
3. 将n和value存入map
4. 更新left和right的值（只需要更新两个端点的值的原因是每次添加n在测试的时候，不需要测试这个连续序列是从什么时候开始，只需要查看她前一位和后一位分别处在多长的连续序列中即可，连续序列则[left,right]中所有数值都已经存在于map中，则不会执行map。Put，所以根本不可能出现需要判断l,r之间的情况）
   
   

代码

    public int longestConsecutive(int[] nums) {      
        int res = 0;
        HashMap<Integer,Integer> map = new HashMap<>();       
        for(int n:nums) {
         if(map.containsKey(n))
            continue; 
         int left = map.containsKey(n-1)?map.get(n-1):0;
         int right = map.containsKey(n+1)?map.get(n+1):0;
         int count = left+right+1;    

         res = res>count?res:count;       

         map.put(n, count);
         
         if(left>0)
            map.put(n-left, count);
         if(right>0)
            map.put(n+right, count);
        }
        return res;
    }