牛客刷题——剑指offer(第五期)

2022-09-22 72

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 牛客刷题——剑指offer(第五期)

里面有非常多的题库跟面经知识真的非常良心了！！

JZ28 对称的二叉树🍨

JZ对称的二叉树

题目描述🍨

解题思路🍨

二叉树对称的要求满足：

两棵树的根节点相同

两颗子树的左右子树分别对称

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 字符串的排列🍨

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 第一个只出现一次的字符🍨

JZ50 第一个只出现一次的字符

解题思路🍨

1.根据字符串的api idexOf 跟lastindexOf 就是字符串第一次出现的索引跟最后一次出现的索引如果是同一个数证明出现了一次

2.还有一种办法是用一个哈希来存遍历完了次数++ 如果最后次数=1就是出现一次的字符！

这道题可以两种方法来做

代码详解🍨

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

方法2：

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