一.两数之和
二.回文数
三.罗马数字转整数
四.最长公共字串
五.有效的括号
六.合并两个有序链表七.删除有序数组中的重复项八.移除元素
一.两数之和1.两数之和
题目描述
解答思路:
运用hashMap来解决此题目
1.key:放数组中的值;value:放数组下标
2.将数组第一个元素放入hashMap当中
3.然后遍历数组,如果hashMap当中已经存在target-nums[i]的值,就找到了对应的两个下标
4.否则就是没找到,将这个值继续放入hashMap当中
class Solution { public static int[] twoSum(int[] nums, int target) { int length=nums.length; HashMaphashMap=new HashMap<>(length-1); hashMap.put(nums[0],0); for(int i=1;i 二.回文数 2.回文数
题目描述:
解题思路:回文的特点是,正着读和反着读是一样的,因此,可以利用StringBuilder中的reverse()方法
1.先将int类型转为StringBuilder类型;
2.再利用reverse(),即,字符串反转,比如:10–>reverse()–>01 abcd–>reverse()–>dcba
3.利用 .equals()方法来比较是否相同,即证明这个数字是否是回文数字class Solution { public static boolean isPalindrome(int x) { StringBuilder stringBuilder=new StringBuilder(x+""); if(stringBuilder.toString().equals(stringBuilder.reverse().toString())){ return true; } return false; } }三.罗马数字转整数3.罗马数字转整数
题目描述:
题解:
1.利用HashMap(key,value),key:放 罗马数字,vlaue:放 数字;
2.将字符串转化成字符数组;
3.遍历整个字符数组,
4.遍历,当下这个字符对应的数字 VS 下一个字符的数字
5.如果 i 下标对应的数字 < i+1对应的数字:则,就属于特殊情况,比如:IV->(-1+5=4)再例如:IX(-1+10=9):对于这种情况,结果值减去当下这个 i下标对应的数字;
6.如果i下标对应的数字 >=i+1下标对应的数字:则结果值进行累加即可。class Solution { public static int romanToInt(String s) { HashMap四.最长公共字串hashMap = new HashMap<>(); hashMap.put('I', 1); hashMap.put('V', 5); hashMap.put('X', 10); hashMap.put('L', 50); hashMap.put('C', 100); hashMap.put('D', 500); hashMap.put('M', 1000); char[] ret = s.toCharArray(); int result = 0; for (int i = 0; i < ret.length; i++) { if ((i < ret.length - 1) && hashMap.get(ret[i]) < hashMap.get(ret[i+1])) { //hashMap.get(ret[i]): //ret[i]:对应的字符 //hashMap.get(key):根据key,去找对应的value值 result-=hashMap.get(ret[i]); } else { result += hashMap.get(ret[i]); } } return result; } } 4.最长公共字串
题目描述:
解题思路:
利用双层for循环来解决此问题;
外层循环:遍历整个数组元素;
内层循环:遍历公共字符串和当前下标的数组元素,一个字符一个字符的进行比较,待两个字符不一样的时候,则退出循环,更新公共字符串。class Solution { public static String longestCommonPrefix(String[] strs) { if(strs.length==0){ return ""; } //result:代表意思:代表公共字符串,首先,设初值的时候,可以将数组0号下标设置 String result=strs[0]; //外层循环:控制的是 数组的个数,目的是取到数组中的每一个数与公共字符串进行比较 for(int i=1;i五.有效的括号 5.有效的括号
题目描述
解题思路:
这个题目利用 栈来解决
1.遍历这个字符串
2.当取到的字符属于左边括号时,进栈;
3.当取到的字符属于右边括号时,此时,出栈 栈顶元素,当栈顶元素是相对应的 左边括号时,就继续循环,继续取下一个字符元素,否则返回false;
4.小细节,当取到元素为右边括号的时候,此刻,需要先判断,栈是否为空,如果栈为空,说明,之前没有左边括号,则,直接返回false;
5.最后,需要对栈进行检验,看是否为空,为空:true;不为空:falseclass Solution { public static boolean isValid(String s) { Stackstack=new Stack<>(); for(int i=0;i 六.合并两个有序链表 6.合并两个有序链表
题目描述:
解题思路:
1.创建两个新的节点;
2.进入while循环,然后将两个链表的值分别进行比较;
3.选择较小的值加入到新的节点中;
4.判断,两个链表是否为空,如果其中一个链表已经为空,则,直接把另一个链表加到新的节点之后class Solution { public static ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode result=new ListNode(0); ListNode temp=result; while(list1!=null && list2!=null){ if(list1.val<= list2.val){ temp.next=list1; list1=list1.next; temp=temp.next; }else{ temp.next=list2; list2=list2.next; temp=temp.next; } } if(list1==null){ temp.next=list2; }else if(list2==null){ temp.next=list1; } return result.next; } }七.删除有序数组中的重复项7.删除有序数组中的重复项
题目描述:
解题思路:
本题目要求,在原地 删除出现重复的数字,并且要求空间复杂度为O(1),
所以,只能在原来的数组中改,不能使用hash
1.记录下标,默认0下标是:nums[0];
2.遍历数组,当前一个数组元素和当前数组元素不一样的时候,此时,将
nums[index++]=nums[i];class Solution { public static int removeDuplicates(int[] nums) { int index=1; for(int i=1;i八.移除元素 8.移除元素
题目描述:
解题思路:与上一题思路一致class Solution { public int removeElement(int[] nums, int val) { int index=0; for(int i=0;i