剑指offer刷题
JZ28 对称的二叉树
题目描述
解题思路:
二叉树对称的要求满足：
两棵树的根节点相同 两颗子树的左右子树分别对称 a的左子树与b的左子树的值对应相等 a的右子树的与b的右子树的值对应相等
我们可以定义一个check方法 来检查两颗子树是否满足对称条件~
代码详解
import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { boolean isSymmetrical(TreeNode pRoot) { return cheack(pRoot,pRoot); } boolean cheack(TreeNode a,TreeNode b) { if(a==null && b==null) return true; if(a==null||b==null) return false; if(a.val!=b.val) return false; return cheack(a.left,b.right)&cheack(a.right,b.left); } }
JZ38 字符串的排列
解题思路
一道比较经典的dfs
回溯完了记得剪枝~
代码详解
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param str string字符串 * @return string字符串ArrayList */ public ArrayList<String> Permutation (String str) { ArrayList<String> list=new ArrayList<>(); StringBuilder sub= new StringBuilder(); char strs[]=str.toCharArray(); Arrays.sort(strs); dfs(list,sub,strs,0,new boolean[strs.length]); return list; } void dfs(ArrayList<String> list,StringBuilder sub, char[]strs,int index,boolean[]vis){ if(index==strs.length){ list.add(sub.toString()); return ; } for(int i=0;i<strs.length;i++){ if(i>0 && strs[i-1]==strs[i]&&!vis[i-1]||vis[i])continue; sub.append(strs[i]); vis[i]=true; //用过的字符 标记为true dfs(list,sub,strs,index+1,vis); vis[i]=false; sub.deleteCharAt(index); } } }
JZ50 第一个只出现一次的字符
解题思路
.根据字符串的api idexOf 跟lastindexOf 就是字符串第一次出现的索引跟最后一次出现的索引如果是同一个数证明出现了一次
2.还有一种办法是用一个哈希来存 遍历完了次数++ 如果最后次数=1就是出现一次的字符！
这道题可以两种方法来做
代码详解
public class Solution { public int FirstNotRepeatingChar(String str) { int len=str.length(); for(int i=0;i<len;i++){ char ch=str.charAt(i); if(str.lastIndexOf(ch)==str.indexOf(ch)) { return i; } } return -1; } }
public class Solution { public int FirstNotRepeatingChar(String str) { int len=str.length(); int map[]=new int[256]; for(int i=0;i<len;i++){ map[str.charAt(i)]++; } for(int i=0;i<len;i++){ if( map[str.charAt(i)]==1){ return i; } } return -1; } }
