面试刷题——剑指offer

CSDN话题挑战赛第2期 参赛话题：面试宝典

剑指offer刷题

JZ28 对称的二叉树

JZ对称的二叉树

题目描述

解题思路:

二叉树对称的要求满足： 两棵树的根节点相同 两颗子树的左右子树分别对称 a的左子树与b的左子树的值对应相等 a的右子树的与b的右子树的值对应相等 我们可以定义一个check方法 来检查两颗子树是否满足对称条件~

代码详解

代码语言：javascript复制

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 回溯完了记得剪枝~

代码详解

代码语言：javascript复制

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就是出现一次的字符！ 这道题可以两种方法来做

代码详解

代码语言：javascript复制

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;
        
        
    }
}

方法2：

代码语言：javascript复制

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;
        
    }
}

二叉树 编程算法

0 人点赞