LeetCode的算法前三题(java实现)

算法前三题(java实现)"/>

LeetCode的算法前三题(java实现)

LeetCode的算法前三题

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

1.two_sum

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

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

示例:

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

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

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

自己的暴力求解：

/*** @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）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/*** @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//进位标志置为truecarry=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 前进到下一个结点。//如果下一个元素存在则取下一个//如果不存在则取0if(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）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

/*** @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));}}