当前位置 博文首页 > SOARING：LeetCode刷题笔记—简单题（Java版）
?
?
记录LeetCode算法学习路程。
描述：找到数组中两个数相加和为target的数组下标。
解法1：简单粗暴的方法，嵌套循环数组，返回相加为target的两个数的下标。
class Solution {
? ? public int[] twoSum(int[] nums, int target) {
? ? ? ? for(int i =0;i<nums.length;i++){ //嵌套循环找到相加为target
? ? ? ? ? ? for(int j=i+1;j<nums.length;j++){
? ? ? ? ? ? ? ? if(nums[j]+nums[i]==target){
? ? ? ? ? ? ? ? ? ? return new int[]{i,j};//返回一个int数组，其中值为i j
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? throw new IllegalArgumentException("No two sum solution");//不存在的话抛出异常
? ? }
}描述：给出两个?非空?的链表用来表示两个非负的整数。其中，它们各自的位数是按照?逆序?的方式存储的，并且它们的每个节点只能存储?一位?数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
解法1：先创建一个ListNode s用来存放每一位相加的值，用add存放进位值。注意数字的长度可能不同的情况。当相同时将两个链表第一个值相加对10取余，写入到s中。并记录进位值。依次往后移动指针，直到为空。当长度不一致时，即移动到两个链表其中一个 指向null的时候，s仅需要记录另外一个链表所指向的值即可（注意前一个是否有进位，以及此节点是否进位，即为9的情况下）。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode s = new ListNode(0),p = s;//创建个链表存放相加的值 并将p作为头指针
int add = 0;//进位值
while(l1 != null || l2 != null){//直到指针走到最后停止循环，注意左边为数字的低位
//当两数长度不一样时，
if(l1 == null){
s.next = new ListNode((l2.val + add)%10);
s = s.next;
add = (l2.val + add)/10;
l2 = l2.next;
continue;
}
if(l2 == null){
s.next = new ListNode((l1.val + add)%10);
s = s.next;
add = (l1.val + add)/10;
l1 = l1.next;
continue;
}
s.next = new ListNode((l1.val + l2.val+add)%10);//
s = s.next;
add = ((l1.val + l2.val +add)/10);//更新进位值
l1 = l1.next;//往后移动
l2 = l2.next;
}
if(add == 1){ // 当指针走到末尾时还有进位，则新建值为1的节点
s.next=new ListNode(1);
s=s.next;
}
return p.next;
}
}描述：将一个32位整数进行反转，321——>123? -3123—>-3213
解法1：简单思路，将int x转换成stringBuffer 进行反转，同时去掉 ‘-’ 以便能够将str转换到double类型，double是为了检测是否超过了int的最大值，超过了则返回0。判断x小于零的话返回相应负的值。
class Solution {
public int reverse(int x) {
String str = String.valueOf(x);
StringBuffer s = new StringBuffer(str);
s = s.reverse();
if(s.charAt(s.length()-1)=='-'){
s.deleteCharAt(s.length()-1);
}
str=s.toString();
Double d = Double.parseDouble(str);
if(d>Integer.MAX_VALUE || d<Integer.MIN_VALUE){
return 0;
}
Integer i =d.intValue();
if(x<0){
return -i;
}
return i;
}
}描述:
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000例如， 罗马数字 2 写做?II?，即为两个并列的 1。12 写做?XII?，即为?X?+?II?。 27 写做??XXVII, 即为?XX?+?V?+?II?。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做?IIII，而是?IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为?IX。这个特殊的规则只适用于以下六种情况：
I?可以放在?V?(5) 和?X?(10) 的左边，来表示 4 和 9。X?可以放在?L?(50) 和?C?(100) 的左边，来表示 40 和?90。?C?可以放在?D?(500) 和?M?(1000) 的左边，来表示?400 和?900。给定一个罗马数字，将其转换成整数。输入确保在 1?到 3999 的范围内。
解法1：首先想到用switch，遍历字符的时候遇到相应的罗马数字转换成相应的整数。根据题意，小罗马字符在大罗马字符前面的时候需要大罗马字符减去小罗马字符的值。由此可想到，把所有的罗马字符先加起来，然后在判断在当前的这个字符下是否需要减去（即前一个罗马字符小于当前这个）。遍历完即可得到答案。
?
//执行用时: 106 ms, 在Roman to Integer的Java提交中击败了51.59% 的用户
//内存消耗: 58.1 MB, 在Roman to Integer的Java提交中击败了3.07% 的用户
class Solution {
public int romanToInt(String s) {
int result=0 ;
int len = s.length();
for(int i = 0;i<len;i++){
switch(s.charAt(i))
{
case 'I' :result = result + 1;break;
case 'V' :result = result + 5;break;
case 'L' :result = result + 50;break;
case 'X' :result = result + 10;break;
case 'C' :result = result + 100;break;
case 'D' :result = result + 500;break;
case 'M' :result = result + 1000;break;
default: System.out.println("default");break;
}
if(i!=0)
{
if(((s.charAt(i)=='V') || (s.charAt(i)=='X')) && (s.charAt(i-1)=='I')){
result = result - 2*1;
}
if(((s.charAt(i)=='L') || (s.charAt(i)=='C')) && (s.charAt(i-1)=='X')){
result = result - 2*10;
}
if(((s.charAt(i)=='D') || (s.charAt(i)=='M')) && (s.charAt(i-1)=='C')){
result = result - 2*100;
}
}
}
return result;
}
}
?描述：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串?""。
解法1：用StringBuilder来存放公共前缀。?先记录第一个字符串的第一个字符，遍历字符串数组，和数组中的每一个字符串进行比对。如果有一个不同或者达到了数组中最小字符串的length时就返回当前的sb。
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length==0){
return "";
}
StringBuilder sb = new StringBuilder();
/**不需要找到串中的最小长度
int minlen = strs[0].length();
for(String str : strs){
if(str.length()<minlen)
minlen = str.length();
}
**/
int i=0;
while(true){
if(i == strs[0].length)
return sb.toString();
char c = strs[0].charAt(i);//数组第一个字符串中，从第一个往后比，
for(String str : strs){
//此处可保证当达到穿中最小字符串的长度是返回
if(c != str.charAt(i) || i == str.length()){
return sb.toString();
}
}
sb.append(c);
i++;
}
}
}描述：给定一个只包括?'('，')'，'{'，'}'，'['，']'?的字符串，判断字符串是否有效。有效字符串需满足：
注意空字符串可被认为是有效字符串。
解法1：首先想到遍历给定的括号字符串，遇到左括号尾加到StringBuilder中，遇到右括号就比对StringBuilder中最后一个括号是否和当前的右括号匹配，是的话就删除SB中的最后的字符。
解法2：利用Stack的思想。new一个<Character>的Stack ，遍历括号字符串，遍历到左括号是将对应的右括号入栈，遍历到右括号是就判断出栈的字符和当前的字符是否一样，不一样返回false；
class Solution {
public boolean isValid(String s) {
/** 解法1
StringBuilder sb = new StringBuilder();
int i =0;
while(i<s.length()-1){
if(s.charAt(i)=='(' || s.charAt(i)=='[' || s.charAt(i)=='{')
sb.append(s.charAt(i));
if(s.charAt(i)==')' || s.charAt(i)==']' || s.charAt(i)=='}'){
if(sb.charAt(sb.length()-1) == s.charAt(i)){
sb.deleteCharAt(sb.length()-1);
}else{
return false;
}
}
i++;
}
return true;
**/
if(s.isEmpty()){
return true;
}
Stack<Character> st = new Stack<Character>();
for(int i = 0;i<s.length();i++){
char push_char = s.charAt(i);
switch(push_char){
case '(':
st.push(')');
break;
case '[':
st.push(']');
break;
case '{':
st.push('}');
break;
default:
try{
if(push_char!=st.pop()){
return false;
}
}catch(Exception e){
return false;
}
}
}
return st.empty();
}
}描述：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。?
解法1：创建一个新的链表，遍历比较l1和l2的节点的值，小的头插到新的链表中。当其中一个链表为空的时候，直接将另一个剩余的部分插进去。
执行用时:?9 ms, 在Merge Two Sorted Lists的Java提交中击败了92.36%?的用户
内存消耗:?28.5 MB, 在Merge Two Sorted Lists的Java提交中击败了15.06%?的用户
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode p = result;
while(l1!=null && l2!=null){
if(l1.val<l2.val){
p.next = l1;
l1=l1.next;
p=p.next;
}else{
p.next=l2;
l2=l2.next;
p=p.next;
}
}
if(l1==null){
p.next=l2;
}else{
p.next=l1;
}
return result.next;
}
}描述：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
解法1：遍历数组，i作为慢下标，j作为快下标，当j查找到与i不相同的时候就将i+1置为这个不同的数，然后i往前移动。直到遍历结束。
执行用时:?14 ms, 在Remove Duplicates from Sorted Array的Java提交中击败了73.40%?的用户
内存消耗:?40.6 MB, 在Remove Duplicates from Sorted Array的Java提交中击败了46.10%?的用户
class Solution {
public int removeDuplicates(int[] nums) {
int i=0;
int j=1;
while(j<nums.length){
if(nums[i]!=nums[j]){
nums[i+1]=nums[j];
i++;
}
j++;
}
return i+1;
}
}27. 移除元素
描述：给定一个数组?nums?和一个值?val，你需要原地移除所有数值等于?val?的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
解法1：与删除排序数组中的重复项思想一致，慢指针和快指针，遍历数组，快指针遇到非val的时候就把值赋给慢指针，次数正好是去掉val数组的长度。
执行用时:?9 ms, 在Remove Element的Java提交中击败了69.33%?的用户
内存消耗:?29.5 MB, 在Remove Element的Java提交中击败了26.89%?的用户
class Solution { public int removeElement(int[] nums, int val) { int i=0; for(int j=0;j<nums.length;j++){ if(nums[j]!=val){ nums[i]=nums[j]; i++; } } return i; } }?
28. 实现strStr()
描述：实现?strStr()?函数。给定一个?haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回??-1。
解法1：遍历找到haystack
class Solution { public int strStr(String haystack, String needle) { if(needle=="" || haystack.equals(needle)) return 0; for(int i = 0;i<haystack.length()-needle.length()+1;i++){ if((haystack.substring(i,i+needle.length())).equals(needle)) return i; } return -1; } }?
描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
解法1：暴力搜索
class Solution { public int searchInsert(int[] nums, int target) { for(int i =0;i<nums.length;i++){ if(nums[i]>=target) return i; } return nums.length; } }?
53、最大子序列和
描述：给定一个整数数组?nums?，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
解法1：?暴力法，嵌套for循环，求出每个字串的和，最后找出最大的。效率很低。
class Solution { public int maxSubArray(int[] nums) { int max = nums[0]; for(int i=0;i<nums.length;i++){ int temp=0; for(int j=i;j<nums.length;j++){ temp = temp+nums[j]; if(temp>max) max=temp; } } return max; } }?
58、最后一个单词的长度
描述：给定一个仅包含大小写字母和空格?' '?的字符串，返回其最后一个单词的长度。
如果不存在最后一个单词，请返回 0?。
说明：一个单词是指由字母组成，但不包含任何空格的字符串。
解法1：用字符串的split方法将单词分割成字符串数组，在求最后一个字符串的长度。
class Solution { public int lengthOfLastWord(String s) { if(s==" ") return 0; String[] strs = s.split(" "); if(strs.length==0) return 0; return strs[strs.length-1].length(); } }?
66、加一
描述：
解法1：从数组中的末尾开始遍历，加1后判断是否大于10，大于则取余数，进位设为1；小于则进位设为0；遍历完如果进位为1的话需要在原始的数组的头部进位，解决办法是创建一个length+1的新数组，将第一个元素设置为1后，后面的元素整体copy进行加1处理后的原始数组。
执行用时:?1 ms, 在Plus One的Java提交中击败了61.85%?的用户
内存消耗:?20.5 MB, 在Plus One的Java提交中击败了72.64%?的用户
class Solution { public int[] plusOne(int[] digits) { int add = 1; for(int i=digits.length-1;i>=0;i--){ digits[i] += add; if(digits[i]>=10){ digits[i] -= 10; add=1; }else{ add = 0; break; } } if(add==1){ int[] result = new int[digits.length+1]; result[0] = 1; System.arraycopy(digits,0,result,1,digits.length); return result; }else{ return digits; } } }?
67、二进制求和
描述：给定两个二进制字符串，返回他们的和（用二进制表示）。输入为非空字符串且只包含数字?1?和?0。
解法1：比较粗暴的方法，先找到较短的字符串，从右网左扫描。对应依次相加（**注意字符转整形 -‘0’！）后插入到StringBuilder的头中，分三种情况：《=1就直接存到StringBuilder ，不进位。等于2时，replace头为0，同时进位。等于3时，replace头为1，同时进位。循环次数为短的字符串长度，循环结束则只剩较长的字符串，依次加入。最后要判断是否有进位，有则头补充1.
执行用时:?8 ms, 在Add Binary的Java提交中击败了33.00%?的用户
内存消耗:?26.6 MB, 在Add Binary的Java提交中击败了14.91%?的用户
class Solution { public String addBinary(String a, String b) { StringBuilder sb = new StringBuilder(); int i ; int a1=a.length()-1; int a2=b.length()-1; if(a.length()>=b.length()){ i = b.length(); }else{ i=a.length(); } int add = 0; while(i>0){ sb.insert(0,a.charAt(a1)-'0'+b.charAt(a2)-'0'+add); if(sb.charAt(0)-'0'>1){ if(sb.charAt(0)-'0'==2){ sb.replace(0,1,"0"); add = 1; }else{ sb.replace(0,1,"1"); add = 1; } }else{ add = 0; } a1--; a2--; i--; } while(a1>a2 && a1>=0){ sb.insert(0,a.charAt(a1)-'0'+add); if(sb.charAt(0)-'0'>1){ sb.replace(0,1,"0"); add = 1; }else{ add = 0; } a1--; } while(a2>a1 && a2>=0){ sb.insert(0,b.charAt(a2)-'0'+add); if(sb.charAt(0)-'0'>1){ sb.replace(0,1,"0"); add = 1; }else{ add = 0; } a2--; } if(add==1){ sb.insert(0,1); } return sb.toString(); } }?
70、爬楼梯?
描述：假设你正在爬楼梯。需要?n?阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定?n?是一个正整数。
解法1:数学表达式为f(a) = f(a-1)+f(a-2).当前要求的数是前面两个数的和。
执行用时:?3 ms, 在Climbing Stairs的Java提交中击败了82.31%?的用户
class Solution { public int climbStairs(int n) { int a =0; int b =1; int result=0; for(int i=1;i<=n;i++){ result=a+b; a=b; b=result; } return result; } }?
?83、删除链表中重复的元素
描述：
解法1：设置两个指针p q，两个指针指向的值不相等时同步往后移，相等时删除操作。当q为空的时候结束。
?
? /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode deleteDuplicates(ListNode head) { if(head==null) return head; ListNode p=head; ListNode q=p.next; while(q!=null){ if(p.val!=q.val){ p=p.next; q=q.next; }else{ q=q.next; p.next=q; if(q==null) return head; } } return head; } } ??
88、合并两个有序的数组
描述：给定两个有序整数数组?nums1?和?nums2，将?nums2?合并到?nums1?中，使得?num1?成为一个有序数组。
说明:初始化?nums1?和?nums2?的元素数量分别为?m?和?n。你可以假设?nums1?有足够的空间（空间大小大于或等于?m + n）来保存?nums2中的元素。
解法1：
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int p = m+n-1;//指向nums1最后一位 m--; n--; while(m>=0 && n>=0){ if(nums1[m]<=nums2[n]){ nums1[p]=nums2[n]; p--; n--; }else{ nums1[p]=nums1[m]; p--; m--; } } while(n>=0){ nums1[p]=nums2[n]; p--; n--; } //LeetCode自动返回nums1 } }?
100、判断是否是相同的树
描述：
解法1：先判断p q节点的值是否相等，在递归判断if（左节点，右节点） 为真时返回true
执行用时:?5 ms, 在Same Tree的Java提交中击败了56.87%?的用户?
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ 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){ if(isSameTree(p.left,q.left) && isSameTree(p.right,q.right)){ return true; }else{ return false; } }else{ return false; } } }?
101、对称二叉树
描述：
解法1：?
执行用时:?10 ms, 在Symmetric Tree的Java提交中击败了81.17%?的用户
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { if(root==null) return true; return isSym(root.left,root.right); } private boolean isSym(TreeNode p,TreeNode q){ if(p==null && q==null){ return true; }else if((p!=null && q!=null) && p.val == q.val){ if(isSym(p.left,q.right) && isSym(q.left,p.right)){ return true; }else{ return false; } }else{ return false; } } }?
104、二叉树的深度
解法 1：递归法
执行用时:?0 ms, 在Maximum Depth of Binary Tree的Java提交中击败了100.00%的用户
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int maxDepth(TreeNode root) { int HL,HR,depth; if(root!=null){ HL = maxDepth(root.left); HR = maxDepth(root.right); depth = HL>HR?HL+1:HR+1; }else{ return 0; } return depth; } }解法二：三元表达式,递归（自底向上）
class Solution { public int maxDepth(TreeNode root) { return root==null?0:Math.max(maxDepth(root.left),maxDepth(root.right))+1; }?
118，杨辉三角
?
public List<List<Integer>> generate(int numRows) { List<List<Integer>> res = new ArrayList<>(); if (numRows==0) { return res; } res.add(new ArrayList<>()); res.get(0).add(1); for(int i=1;i<numRows;i++) { List<Integer> ll = new ArrayList<>(); ll.add(1); //遍历往里面放相应的数 res.get()第一次表示上边的list,第二次get()表示当前需要插入数 //的左上方和右上方数字 for (int j = 1; j < i-1; j++) { ll.add(res.get(i-1).get(j-1)+res.get(i-1).get(j)); } //最后一个数字为1 ll.add(1); res.add(ll); } return res; }?
121 股票股买最佳时期?
?
public int maxProfit(int[] prices) { int max = 0; for (int i = 0; i < prices.length; i++) { int tempmax=0; for (int j = i+1; j < prices.length; j++) { if (prices[j]>prices[i]&&(prices[j]-prices[i])>tempmax) { tempmax=prices[j]-prices[i]; } } if (tempmax>max) { max = tempmax; } } return max; }?
122 股票最佳购买2?
?
package day20190318; public class BuyStocks2 { public static void main(String[] args) { int[] prices = new int[]{1,2,3,4,5}; System.out.println(new Stocks().maxProfit(prices)); } public static class Stocks{ public int maxProfit(int[] prices) { int sum = 0; for (int i = 1; i < prices.length; i++) { if (prices[i]>prices[i-1]) { sum+=prices[i]-prices[i-1]; } } return sum; } } }?
判断是否是回文串?
解法一：只看字母和数字，忽略其他字符和大小写。提交异常。
package day20190318; public class PalindromeString { public static void main(String[] args) { String s ="!@#!a...@$@$#"; PalindromeStringClass palindromeStringClass = new PalindromeStringClass(); System.out.println(palindromeStringClass.isPalindrome(s)); } public static class PalindromeStringClass{ public boolean isPalindrome(String s) { String str = s.replaceAll("[^a-zA-Z0-9]", ""); String lowerCase = str.toLowerCase(); String reverseString = reverseString(lowerCase); return lowerCase.equals(reverseString); } public String reverseString(String string) { if (string==null || string.length()<2) { return string; } return reverseString(string.substring(1))+string.charAt(0); } } }
