目录
关键词
二叉树递归、动态规划法、双指针法、滑动窗口、哈希集合、Brian Kernighan 算法
1.相同的树
难度：★ 链接：力扣
解题思路：
碰到关于二叉树的问题，一般考虑使用递归来解决。本题不难，只需要先进行特殊情况地处理，即首先考虑树是否同时为空，或者其中一个为空的情况，其次再判断当前节点的value值是否相同，最后递归地去判断第一棵二叉树的左、右子树是否等于第二棵二叉树的左、右子树。
解题代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
//先判断树是否同时为空
if(p==null&&q==null)return true;
//判断其中一个树是否为空
else if(p==null||q==null)return false;
else if(p.val!=q.val)return false;
//递归判断p,q的各自的子树是否相等
else return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}
2.可以被一步捕获的棋子数
难度：★ 链接：力扣
示例1：
输入：[[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”R”,”.”,”.”,”.”,”p”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”]]
输出：3
解释：在本例中，车能够捕获所有的卒。
示例2：
输入：[[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”p”,”p”,”p”,”p”,”p”,”.”,”.”],[“.”,”p”,”p”,”B”,”p”,”p”,”.”,”.”],[“.”,”p”,”B”,”R”,”B”,”p”,”.”,”.”],[“.”,”p”,”p”,”B”,”p”,”p”,”.”,”.”],[“.”,”p”,”p”,”p”,”p”,”p”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”]]
输出：0
解释：象阻止了车捕获任何卒。
示例3：
输入：[[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“p”,”p”,”.”,”R”,”.”,”p”,”B”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”B”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”]]
输出：3
解释：车可以捕获位置 b5，d6 和 f5 的卒。
提示：
board.length == board[i].length == 8
board[i][j] 可以是 ‘R’，’.’，’B’ 或 ‘p’
只有一个格子上存在 board[i][j] == ‘R’
解题思路：
本题乍一看似乎有点复杂，其实理解了题意非常简单。因为棋盘是8×8固定不变的，数据规模不算大，所以此时蛮力法非常适用且效果不错，大致的思路分为下面两步：
第一步，二重循环确定白车棋子的具体位置，即坐标（x,y）
第二步，在白车所在行与所在列遍历敌方棋子的数目，若先遍历到己方棋子则该方向上无法一次捕获敌方棋子，因为敌方棋子被己方棋子给挡住了
解题代码：
class Solution {
public int numRookCaptures(char[][] board) {
//第一步，二重循环确定白车棋子的具体位置，即坐标
int x=0,y=0,count=0;//x,y分别为白车的横纵坐标，count存放能一次捕获的敌方棋子数目
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
if(board[i][j]=='R'){
x=i;
y=j;
break;
}
}
}
//第二步，在白车所在行与所在列遍历敌方棋子的数目，若先遍历到己方棋子则该方向上无法一次捕获敌方棋子，因为敌方棋子被己方棋子给挡住了
//向下遍历所在列
for(int row=x;row<8;row++){
if(board[row][y]=='B')break;
if(board[row][y]=='p'){
count++;
break;
}
}
//向上遍历所在列
for(int row=x;row>=0;row--){
if(board[row][y]=='B')break;
if(board[row][y]=='p'){
count++;
break;
}
}
//向左遍历所在行
for(int col=y;col>=0;col--){
if(board[x][col]=='B')break;
if(board[x][col]=='p'){
count++;
break;
}
}
//向右遍历所在行
for(int col=y;col<8;col++){
if(board[x][col]=='B')break;
if(board[x][col]=='p'){
count++;
break;
}
}
return count;
}
}
3.最长回文子串
难度：★★ 链接：力扣
思路一：蛮力法
设置两个指针 i 和 j, i从字符串的首个字符出发，j从i当前位置的下一个字符出发，每一次判断i到j之间的所构成的字符串是否是回文串，然后将其长度与maxlength进行比较，更新最大回文子串的长度与最大回文子串首个字符的下标begin ，一轮循环结束后则以第0个字符为首字符的回文子串遍历结束，下面开始遍历以第1个字符为首个字符的回文子串，如此反复，不断更新最大长度与其首字符的下标。最后使用字符串截取的方法从主串中截取出最大的回文子串
代码：
class Solution {
public String longestPalindrome(String s) {
//暴力解法
int len=s.length();
int maxlength=1;
int begin=0;//最长回文串的首个字符的下标
char arr[]=s.toCharArray();
if(len<2)return s;
for(int i=0;i<len-1;i++){
for(int j=i+1;j<=len-1;j++){
if(j-i+1>maxlength&&isPalindrome(arr,i,j)){
maxlength=j-i+1;//j-i+1为当前遍历的子串的区间长度
begin=i;
}
}
}
return s.substring(begin,begin+maxlength);
}
//判断某个区间内的子串是否是回文串
public boolean isPalindrome(char arr[],int start,int end){
int left=start,right=end;
//采取左右居中的扩散方法将字符逐一进行比对
while(left<right){
if(arr[left]!=arr[right]){
return false;
}
left++;
right--;
}
return true;
}
}思路二：动态规划法，来自官方解法
其中，最重要的是理解动态规划的边界条件与状态转移方程
本题中，转态转移的基础是以首尾两个字符相同且去掉首尾后的子串为回文串来完成的，满足这两点说明P(i,j)是一个回文串。边界条件是长度为1和2的情况，前者显然必定是一个回文串，后者当两个字符相等时则为回文串。理清楚了这两点后，就可以完成动态规划了，其过程就是一个不断填写状态表的过程，如下图：
代码：
class Solution {
public String longestPalindrome(String s) {
//动态规划法
int len=s.length();
int maxlength=1;
int begin=0;
if(len<2)return s;
char arr[]=s.toCharArray();
boolean dp[][]=new boolean[len][len];//记录状态，dp[i][j]为true表面s[i,j]子串是一个回文串
//长度为1的子串必定是回文串，将其状态设置成true
for(int i=0;i<len;i++){
dp[i][i]=true;
}
//正常填状态表
for(int j=1;j<len;j++){
for(int i=0;i<j;i++){
if(arr[i]!=arr[j])dp[i][j]=false;
else{
if(j-i+1<4)dp[i][j]=true;
else{
//去掉边界后，当前状态取决于其子串是否是回文串
dp[i][j]=dp[i+1][j-1];
}
}
if(dp[i][j]&&j-i+1>maxlength){
maxlength=j-i+1;
begin=i;
}
}
}
return s.substring(begin,begin+maxlength);
}
}
4.比特位计数
难度： ★ 链接：力扣
解题思路：Brian Kernighan 算法
即：x &= (x-1) 表示将x表示的二进制数的最后一个1变成0，所以只需统计执行该操作的次数即可知道二进制中1的个数，这个算法还是蛮巧妙的。
解题代码：
class Solution {
public int[] countBits(int n) {
//Brian Kernighan 算法:x&=(x-1) =>将x表示的二进制数的最后一个1变成0
// 只需统计该操作的次数即可知道其中1的个数
int res[]=new int[n+1];
for(int i=0;i<=n;i++){
res[i]=countOne(i);
}
return res;
}
public int countOne(int x){
int count=0;
while(x>0){
x&=(x-1);
count++;
}
return count;
}
}
5.无重复字符的最长子串
难度：★★ 链接：力扣
解题思路：滑动窗口＋哈希集合法
设置两个指针left和right作为滑动窗口的左右端点，利用Set不允许存储重复元素的特点，每次判断right当前表示的字符在集合Set中是否出现过，没有出现过则说明无重复，将该字符加入到集合Set中，否则进行从字符串的下一个字符开始即left+1位置开始下一次的循环判断。期间不断更新最大无重复子串的长度，取manlength与right-left+1的较大者，right-left+1就是每次遍历的最大子串的区间长度。
解题代码：
class Solution {
public int lengthOfLongestSubstring(String s) {
//滑动窗口
Set<Character> res=new HashSet<Character>();
int n=s.length();
int maxLength=0,right=-1;
for(int left=0;left<n;left++){
//每一次外循环结束后总是从下一个字符开始遍历 则从集合中删去其前一个字符
if(left!=0){
res.remove(s.charAt(left-1));
}
while(right+1<n && !res.contains(s.charAt(right+1))){
res.add(s.charAt(right+1));
right++;
}
maxLength=Math.max(maxLength,right-left+1);
}
return maxLength;
}
}
6.重新格式化电话号码
难度： ★★ 链接：力扣
解题思路：蛮力法
不难，慢慢分析，细心一点注意边界条件的处理，我第一次并没有完全通过测试样例，因为漏考虑了一些边界情况
解题代码：
class Solution {
public String reformatNumber(String number) {
StringBuffer arr=new StringBuffer();
StringBuffer res=new StringBuffer();
int n=number.length();
//去除空格与破折号，将结果存放在arr中
for(int i=0;i<n;i++){
char ch=number.charAt(i);
if(ch!=' '&&ch!='-')
arr.append(ch);
}
String s=arr.toString();//将去除空格与破折号的新的字符串存储在s中
//重新格式化字符串
int left=0,right=2,len=s.length();
//边界处理
if(len<=3){
res.append(s);
}else if(len==4){
//长度为4 直接两两分
res.append(s.substring(0,2)+"-");
res.append(s.substring(2,4));
}
else{
//先对3进行整除，得到可以分3个数字为1组的个数，也即循环的次数
int num=len/3;
for(int i=1;i<=num;i++){
//如果右指针right到达字符串末尾，则只需加上分组数组，结尾不用加 - 符号
if(right==len-1)res.append(s.substring(left,right+1));
else res.append(s.substring(left,right+1)+"-");
//特殊处理：若最后三个三个分组时最后正好还剩下四个，则直接按照题意两两分
if(len-1-right==4){
res.append(s.substring(right+1,right+3)+"-");
res.append(s.substring(right+3,len));
break;
}
//三三为一组，指针步长为3
left+=3;
right+=3;
}
//循环结束时right多移动了3位，故减三
right-=3;
//将剩余的数字作为一组
if(len-1-right<4){
res.append(s.substring(right+1,len));
}
}
return res.toString();
}
}
7.在LR字符串中交换相邻字符
难度：★ ★ 链接：力扣
解题思路：
观察发现，本题替换的规则很简单：LX–>XL , XR–>RX，其实本质上就是字符L和R的移动，替换前后相比，L在替换后相当于在原来字符串中进行右移，R在替换后相当于在原来字符串中进行左移，所以不难看出其相对位置的变化。由于每次移动操作只是交换两个相邻字符，不会增加或删除字符，因此如果可以经过一系列移动操作将start转换成end后，二者的每一种字符串的数目肯定是相同的，并且L和R的相对顺序也是一致的，且L在start中的下标应该小于在end中的下标，因为LX–>XL, L进行了右移，同理，R在start中的下标应该大于在end中的下标，因XR–>RX, R进行了左移。因此可以通过转换后L,R的相对位置是否符合这一替换规则来判断最终start是否能够转换成end。
解题代码：
class Solution {
public boolean canTransform(String start, String end) {
//双指针法，根据L、R的相对位置，移动前后的位置关系判断
int n=start.length();
char s[]=start.toCharArray();
char e[]=end.toCharArray();
int i=0,j=0;
while(i<n&&j<n){
while(i<n&&s[i]=='X')i++;
while(j<n&&e[j]=='X')j++;
if(i<n&&j<n){
if(s[i]!=e[j])
return false;
if((s[i]=='L'&&i<j)||(s[i]=='R'&&i>j))
return false;
i++;
j++;
}
}
while(i<n){
if(s[i]!='X')
return false;
i++;
}
while(j<n){
if(e[j]!='X')
return false;
j++;
}
return true;
}
}让刷题成为一种习惯！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/93452.html
