1、回文数
判断输入的整数是否是回文
我的一般思路:
将输入的整数转成字符串,再将这个字符串转成字符数组c,对字符数组进行遍历,如果第i个元素与第 c.length - i - 1 元素不相等,也就是通过比较首尾元素是否相同来判断是否是回文,只要有一个不相等就不是。
public boolean isPalindrome(int x) {
String s = String.valueOf(x);
char[] c = s.toCharArray();for(int i=0;i<c.length;i++){//比较前后元素是否相同if(c[i]!=c[c.length-i-1]){return false;}
}
return true;
}
进阶思路
先排除掉一定不为回文的数,比如最后一位是0且不为0,或者小于0的整数,再讨论可能为回文的情况,通过对整数除以十取余,对余数乘10,将原整数顺序颠倒,具体思路如下图
public boolean isPalindrome(int x) {//先排除不为回文的数if(x < 0 || (x % 10 == 0&&x!=0)){return false;} //处理的余数 初值为0int reverNum = 0;while(x>reverNum){reverNum = reverNum * 10 + x % 10;x /= 10;}//第二种情况是当存在131这种以中间对称的数时会变成 1 和 13,所以需要做除以十取整操作return(x == reverNum || x == reverNum / 10);}
2、最长公共前缀
求一个字符串数组的最长公共前缀
解题思路
既然是比较一个字符串数组中所有字符串的公共前缀,那么可以额外封装一个方法,用来返回两个字符串之间的公共前缀,让他们进行两两比较,最终得出所有字符串的公共前缀
public String longestCommonPrefix(String[] strs) {//先排除非0和为空的情况if(strs == null || strs.length == 0){return "";}//取第一个数作为初始值比较String prefix = strs[0];//取字符串数组的总长度作为循环执行次数int num = strs.length;//执行循环for(int i=1;i<num;i++){//调用比较两个字符串公共前缀的方法prefix = SelectMaxPro(prefix,strs[i]);if(prefix.length() == 0){//如果两个字符串的公共前缀为0说明没有公共前缀//一旦有两个字符串没有公共前缀则字符串数组也没有,就跳出for循环break;}if(prefix.length() == 0){return "";}}return prefix;}//创建查找两个字符最大公共前缀的方法public String SelectMaxPro(String str1,String str2){//创建一个变量作为索引,用来截取相同的前缀int index = 0;//找出两字符串之间最短的一个作为循环条件,防止数组越界int minLength = Math.min(str1.length(),str2.length());//index<minLength时 作为循环条件,并且当str1和str2对应index位置上的字符相同时index++再继续比较下一个while(index < minLength && str1.charAt(index) == str2.charAt(index)){index++;}return str1.substring(0,index);}
3、有效的括号
这里先引入栈的创建方式
栈
栈是一种先入后出的数据结构(Last In First Out, LIFO)
栈的基本实现
public class StackDemo {public static void main(String[] args) {//使用链表创建栈LinkedList<Character> stack = new LinkedList<>();//向栈中添加元素//1、添加元素到栈顶stack.addFirst('d');//2、添加元素到栈底stack.addLast('v');//封装好的添加元素的方法stack.push('p'); //底层直接调用addFirst()//从栈中取数据//当栈中元素为空时使用这种方式进行取数据会抛出NoSuchElementException异常//1、取出栈顶元素并返回stack.removeFirst();//2、取出栈底元素并返回stack.removeLast();//3、封装好的方法返回栈顶元素stack.pop(); //它的底层就是调用了removeFirst()//查看栈中元素//1、查看第一个元素stack.getFirst();//2、查看最后一个元素stack.getLast();//封装好的方法返回栈顶元素stack.peek();}
}
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
public class Solution{//创建哈希表存储键值对
Map<Character,Character> map = new HashMap<Character,Character>{{//使用此方式在创建哈希表示就对元素进行初始化put('(',')');put('{','}');put('[',']');put('?','?');
}};public static boolean isValid(string s){if(s.length() % 2 == 1){return false;}//创建栈//此处对栈初始化一个元素,防止在栈空情况下出栈抛异常LinkedList<Character> stack = new LinkedList<Character>{{push('?')}}char[] chars = s.toCharArray;for(char c : chars){if(map.containsKey(c)) stack.push(c);//在此处进行了一个出栈的操作 满足条件就会出栈else if(c != map.get(stack.pop())) return false;}return stack.size() == 1;}
}
此方法稍微有点难以理解的点在于他是何时进行的出栈,虽然他是进行一个判断栈顶元素是否等于当前元素,但当他执行完这个判断条件时就会将栈顶元素弹出,这里也可以这么理解:
//弹出的字符
char c = stack.pop()
//如果c等于弹出字符对应的值就继续向后判断否则false
if( c == map.get(c)){continue;
}else{return false;
}
只能用于理解实际这么写会报错
4、删除有序数组中的重复项并返回处理后的数组长度
解决本题采用双指针运算,定义一个快慢指针,将快指针小于数组长度作为循环条件,如果快指针与快指针后一个位置的值相同,就说明两个元素值不相同,就将快指针的值赋给慢指针,使得不重复数据提到数组靠前的位置。但要注意双指针的初始位置都在第二位元素上,因为如果快指针在第一个位置会造成数组越界,慢指针在第一位如果前两个元素不相同,就会覆盖第一个元素。
class Solution {public int removeDuplicates(int[] nums) {int length = nums.length;if(length == 0){return 0;}//定义快慢指针int fast = 1;int low = 1;while(fast < length){if(nums[fast] != nums[fast - 1]){nums[low] = nums[fast];low++;}fast++;}return low;}
}