LeetCode的算法前三题

第一题与第二题只有自己的暴力求解要看官方代码请自己去leetcode查看也有中文版的

1.two_sum

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

自己的暴力求解：

/** * @author Satsuki * @time 2019/7/17 16:10 * @description: */ class Solution { public int[] twoSum(int[] nums, int target) { int firstNum,secNum; for (int i = 0; i < nums.length; i++) { firstNum=nums[i]; for (int j = 0; j < nums.length; j++) { secNum=nums[j]; if((firstNum+secNum==target)&&i!=j){ return new int[]{i,j}; } } } return null; } public static void main(String[] args) { int a[] = {3,2,4}; int target=6; Solution solution = new Solution(); int s[]=solution.twoSum(a,target); for (int i = 0; i < s.length; i++) { System.out.println(s[i]); } } }

2.add_two_numbers

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/add-two-numbers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/** * @author Satsuki * @time 2019/7/17 16:20 * @description: */ import java.util.List; /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public static class ListNode{ int val; ListNode next; ListNode(int x){ val=x; } } public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int n1,n2; n1=n2=0; n1=myLen(l1); n2=myLen(l2); System.out.println("n1:" + n1 + "-" + "n2:" + n2); int n; if(n1>n2){ n=n1; }else if(n1<n2){ n=n2; }else{ n=n1; } ListNode res = new ListNode(0); ListNode res1 = res; ListNode res2 = res1; //将进位 carry 初始化为 0。 boolean carry=false; int nval=0; //遍历列表 l1 和 l2 直至到达它们的尾端。 for (int i = 0; i < n; i++) { //设定 sum = x + y + carrysum=x+y+carry。 nval = l1.val+l2.val; if(carry){ nval++; } carry=false; if(nval>=10){ //更新进位的值，carry = sum / 10 //进位标志置为true carry=true; //取个位数字 nval = nval%10; } //创建一个数值为 (summod 10) 的新结点，并将其设置为当前结点的下一个结点，然后将当前结点前进到下一个结点。 res.val=nval; res.next = new ListNode(0); res = res.next; //将 x 设为结点 p 的值。如果 p 已经到达 l1 的末尾，则将其值设置为 0。 //将 y 设为结点 q 的值。如果 q 已经到达 l2 的末尾，则将其值设置为 0。 //同时，将 p 和 q 前进到下一个结点。 //如果下一个元素存在则取下一个 //如果不存在则取0 if(l1.next!=null){ l1=l1.next; }else { l1.val=0; } if(l2.next!=null){ l2=l2.next; }else { l2.val=0; } System.out.println(nval); } //检查 carry = 1 是否成立，如果成立，则向返回列表追加一个含有数字 1 的新结点。 if(carry==true){ res.val=1; res.next=null; } if(carry==false){ while (res1.next.next!=null){ res1 = res1.next; } res1.next=null; }else { while (res1.next!=null){ res1 = res1.next; } res1.next=null; } return res2; } public static int myLen(ListNode len){ int n=0; while (len!=null){ n++; len=len.next; } return n; } public static void main(String[] args) { ListNode l1 = new ListNode(2); l1.next = new ListNode(4); l1.next.next = new ListNode(3); l1.next.next.next=null; ListNode l2 = new ListNode(5); l2.next = new ListNode(6); l2.next.next = new ListNode(4); l2.next.next.next=null; // ListNode l1 = new ListNode(5); // l1.next = null; // // ListNode l2 = new ListNode(5); // l2.next=null; // while (l1.next!=null){ // System.out.println(l1.val); // l1= l1.next; // } ListNode res = new Solution().addTwoNumbers(l1,l2); while (res.next!=null){ System.out.println(res.val); res = res.next; } } }

官方解答：

/** * @author Satsuki * @time 2019/7/17 18:26 * @description: */ public class Official { public static class ListNode{ int val; ListNode next; ListNode(int x){ val=x; } } public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode p = l1, q = l2, curr = dummyHead; int carry = 0; while (p != null || q != null) { int x = (p != null) ? p.val : 0; int y = (q != null) ? q.val : 0; int sum = carry + x + y; carry = sum / 10; curr.next = new ListNode(sum % 10); curr = curr.next; if (p != null) p = p.next; if (q != null) q = q.next; } if (carry > 0) { curr.next = new ListNode(carry); } return dummyHead.next; } public static void main(String[] args) { ListNode l1 = new ListNode(2); l1.next = new ListNode(4); l1.next.next = new ListNode(3); l1.next.next.next=null; ListNode l2 = new ListNode(5); l2.next = new ListNode(6); l2.next.next = new ListNode(4); l2.next.next.next=null; // ListNode l1 = new ListNode(5); // l1.next = null; // // ListNode l2 = new ListNode(5); // l2.next=null; // while (l1.next!=null){ // System.out.println(l1.val); // l1= l1.next; // } ListNode res = new Official().addTwoNumbers(l1,l2); while (res.next!=null){ System.out.println(res.val); res = res.next; } } }

3.longest_substring_without_repeating_characters

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 示例 2:

输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 示例 3:

输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

自己的解法（无尽的暴力求解，把边界的情况列出）：

/** * @author Satsuki * @time 2019/7/18 15:18 * @description: */ public class Solution { /** * 返回最长无重复子字符串长度 * * @param s * @return */ public int lengthOfLongestSubstring(String s) { //长度初始化 //最大长度 int maxLength=0; //所有出现的非重复子字符串的长度 int myMax=0; //可能出现的边界情况比如""与" " if (s.equalsIgnoreCase("")){ maxLength=0; }else if(s.indexOf(" ")>=0){ maxLength=1; } //通过StringBuilder不断的连接求解非重复子字符串 StringBuilder subString = new StringBuilder(""); for (int i = 0; i < s.length(); i++) { //每次循环将可能得到的非重复子字符串长度置零 myMax=0; //初始化子字符串 subString = new StringBuilder(String.valueOf(s.charAt(i))); //子字符串中有第一个字符了 myMax++; //第二层循环从i+1开始向后找直到找到出现相同字符的情况 for (int j = i+1; j < s.length(); j++) { //判断有没有相同字符的出现 if (subString.indexOf(String.valueOf(s.charAt(j)))>=0){ //找到重复字符串了 if(myMax>maxLength){ maxLength = myMax; subString = null; } //跳出第二层循环 break; }else{ //将该字符添加到字串中 subString.append(s.charAt(j)); myMax = subString.length(); } } if(myMax>maxLength){ //更新最长值 maxLength = myMax; } } System.out.println(subString.toString()); return maxLength; } public static void main(String[] args) { // String s = "abcabcbb"; // String s = "bbbbb"; // String s = "pwwkew"; // String s = ""; // String s = " "; // String s = "c"; // String s = "au"; String s = "jbpnbwwd"; System.out.println(new Solution().lengthOfLongestSubstring(s)); } }

以下是官方给出的解答以及一点点小注释

滑动窗口解答

import java.util.HashSet; import java.util.Set; /** * @author Satsuki * @time 2019/7/18 16:24 * @description: */ public class Official { public int lengthOfLongestSubstring(String s) { int n = s.length(); int ans = 0; for (int i = 0; i < n; i++) { for (int j = i+1; j <=n ; j++) { if(allUnique(s,i,j)) ans = Math.max(ans,j-i); } } return ans; } public boolean allUnique(String s,int start,int end){ Set<Character> set = new HashSet<>(); for (int i = start; i < end; i++) { Character ch = s.charAt(i); if(set.contains(ch)) return false; set.add(ch); } return true; } public static void main(String[] args) { // String s = "abcabcbb"; // String s = "bbbbb"; // String s = "pwwkew"; // String s = ""; // String s = " "; // String s = "c"; // String s = "au"; String s = "jbpnbwwd"; System.out.println(new Solution().lengthOfLongestSubstring(s)); } }

滑动窗口的优化以及通过hashmap的记录求解

import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; /** * @author Satsuki * @time 2019/7/18 16:33 * @description: */ public class Optimization { // public int lengthOfLongestSubstring(String s) { // int n = s.length(); // Set<Character> set = new HashSet<>(); // int ans = 0,i=0,j=0; // while (i<n&&j<n){ // if(!set.contains(s.charAt(j))){ // set.add(s.charAt(j++)); // ans = Math.max(ans,j-i); // }else { // set.remove(s.charAt(i++)); // } // } // return ans; // } /** * 此算法记录字符串中出现字符的位置 * 该字符后面没有重复相同与自己的字符 * 根据j-i+i来记录没有重复子字符的长度 * 一旦出现重复字符i就会向后移动 * @param s * @return */ public int lengthOfLongestSubstring(String s) { //初始化 int n=s.length(),ans=0; //用HashMap来存储字符串的各个字符以及字符在字符串中出现的位置 Map<Character,Integer> map = new HashMap<>();// current index of character //j代表位置会不断的向后移，i代表会重复出现的字符串 for (int j=0,i = 0; j < n; j++) { //如果map中包含相同的字符串 if (map.containsKey(s.charAt(j))){ //更新i的值 i会保持上一个重复字符出现的位置 i = Math.max(map.get(s.charAt(j)),i); } //更新非重复子字符串的长度 ans = Math.max(ans,j-i+1); //更新字符串中各个字符出现的位置 map.put(s.charAt(j),j+1); } return ans; } public static void main(String[] args) { // String s = "abcabcbb"; // String s = "bbbbb"; // String s = "pwwkew"; // String s = ""; // String s = " "; // String s = "c"; // String s = "au"; String s = "jbpnbwzwd"; System.out.println(new Optimization().lengthOfLongestSubstring(s)); } }