每日刷题记录 (四)

文章目录

第一题: 零矩阵

LeetCode: 面试题 01.08. 零矩阵
描述:
编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

解题思路:

题目意思是只要第 i 行 第 j 列某个元素为0, 则该行该列所有元素都为0
这里使用标记法,

1. 首先遍历一次, 如果当前元素为0, 记录当前 i 和 j 的坐标.
2. 再次遍历, 如果当前 i 和 j 的坐标被标记, 就让当前元素等于0

代码实现:

classSolution{publicvoidsetZeroes(int[][] matrix){// 使用两个boolean数组来进行标记boolean[] row =newboolean[matrix.length];boolean[] col =newboolean[matrix[0].length];// 第一次遍历用来标记for(int i =0; i < matrix.length ; i++){for(int j =0; j < matrix[0].length; j++){if(matrix[i][j]==0){
                    row[i]=true;
                    col[j]=true;}}}// 第二次遍历, 用来置零for(int i =0; i < matrix.length ; i++){for(int j =0; j < matrix[0].length; j++){if(row[i]|| col[j]){
                    matrix[i][j]=0;}}}}}

第二题: 合法二叉搜索树

LeetCode: 面试题 04.05. 合法二叉搜索树
描述:
实现一个函数，检查一棵二叉树是否为二叉搜索树。

解题思路:

判断是否是二叉搜索树, 就相当于判断中序遍历是不是有序的
这里使用 中序遍历递归的方式进行.

1. 判断左子树是否小于根节点
2. 判断右子树是否大于根节点
3. 防止右子树出现的值小于最开始的根节点
4. 防止左子树出现的值大于最开始的根节点

代码实现:

classSolution{publicbooleanisValidBST(TreeNode root){returnisBST(root,Long.MIN_VALUE,Long.MAX_VALUE);}publicbooleanisBST(TreeNode root,long min,long max){// 为空返回trueif(root ==null)returntrue;// 不满足这个范围就返回false [min,max]if(root.val <= min || root.val >= max)returnfalse;// 遍历左子树右子树returnisBST(root.left,min,root.val)&&isBST(root.right,root.val,max);}}

第三题: 特定深度节点链表

LeetCode: 面试题 04.03. 特定深度节点链表
描述:
给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。

解题思路:

这里就相当于是层序遍历, 把每一层的节点用链表连起来
注意这里的转链表的过程

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 *//**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */classSolution{publicListNode[]listOfDepth(TreeNode tree){if(tree ==null)returnnull;// 首先使用list来存放节点List<ListNode> list =newArrayList<>();Queue<TreeNode> queue =newLinkedList<>();
        queue.offer(tree);while(!queue.isEmpty()){// 用tmp来链接这一层的节点ListNode tmp =newListNode(-1);// 用ret标记初始tmp节点位置ListNode ret = tmp;int size = queue.size();while(size !=0){TreeNode top = queue.poll();// 链接节点
                tmp.next =newListNode(top.val);
                tmp = tmp.next;if(top.left !=null) queue.offer(top.left);if(top.right !=null) queue.offer(top.right);
                size--;}// 因为最初的节点是-1, 他的下一节点之后的内容才是需要的.
            list.add(ret.next);}// 将list的内容转化成数组ListNode[] ans =newListNode[list.size()];for(int i =0; i < list.size(); i++){
            ans[i]= list.get(i);}return ans;}}

第四题: 检查平衡性

LeetCode: 面试题 04.04. 检查平衡性
描述:
实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。

解题思路:

1. 对于当前遍历到的节点, 先判断他的左右子树是否平衡, 再判断以当前节点为根的树是否平衡
2. 如果子树平衡, 返回子树的高度
3. 如果子树不平衡, 那么整个树都不会平衡, 返回-1

代码实现:

classSolution{publicbooleanisBalanced(TreeNode root){returnmaxDepth(root)>=0;}publicintmaxDepth(TreeNode root){if(root ==null)return0;int leftHigh =maxDepth(root.left);int rightHight =maxDepth(root.right);// 首先判断子树是否平衡, 平衡返回高度.if(leftHigh >=0&& rightHight >=0&&Math.abs(leftHigh-rightHight)<=1){returnMath.max(leftHigh,rightHight)+1;}else{return-1;}}}

第五题: 回文排列

LeetCode: 面试题 01.04. 回文排列
描述:
给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。

解题思路:

1. 使用一个数组来记录当前字符出现的次数
2. 如果字符为出现次数为奇数, 那么出现奇数的次数的字符不能超过1个
3. 超过就是false

代码实现:

classSolution{publicbooleancanPermutePalindrome(String s){int count =0;int[] arr =newint[128];for(char c : s.toCharArray()){
            arr[c]++;}for(int val : arr){// 记录奇数次数字符的个数if(val %2==1){
                count++;}// 超过一个就是false;if(count >1){returnfalse;}}returntrue;}}

第六题: 判定字符是否唯一

LeetCode: 面试题 01.01. 判定字符是否唯一
描述:
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

解题思路:

这里不使用额外的数据结构, 那么可以使用数组的方式进行判定
用数组的方式记录下当前的字符个数
如果超过1个就返回false;

代码实现:

classSolution{publicbooleanisUnique(String astr){int[] arr =newint[26];for(int i =0;i < astr.length();i++){
            arr[astr.charAt(i)-'a']++;if(arr[astr.charAt(i)-'a']>1){returnfalse;}}returntrue;}}