1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路一：暴力求解法
这种方式时间复杂度为，不可取。
//1. 两数之和，暴力求解算法
public static int[] twoSum(int[] nums, int target) {
for(int i=0;i<nums.length-1;i++){
for (int j = i+1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
return new int[]{i,j};
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
思路二：哈希求解
这种方式时间复杂度为，采用哈希表存储的方式，将数组中的数字以此存入哈希表中，同时进行试验。
//1. 两数之和，hash求解
public static int[] twoSum1(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for (int i=0;i<nums.length;i++){
int num2 = target - nums[i];
if(map.containsKey(num2)){
return new int[]{map.get(num2),i};
}
map.put(nums[i],i);
}
throw new IllegalArgumentException("No two sum solution");
}
2. 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
思路一：每种情况都分开讨论
这种方式冗长麻烦，容易漏掉一些情况，代码重复率高。
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result= new ListNode(0);
ListNode head = result,temp2;
int step = 0,flag=0;
if(l1!=null && l2!=null){
result.val = (l1.val+l2.val+step)%10;
step = (l1.val+l2.val+step)/10;
}
while(l1.next!=null&&l2.next!=null){
l1 = l1.next;
l2 = l2.next;
ListNode temp = new ListNode(0);
result.next = temp;
result = result.next;
result.val = (l1.val+l2.val+step)%10;
step = (l1.val+l2.val+step)/10;
}
while(l1.next!=null){
l1 = l1.next;
ListNode temp = new ListNode(0);
result.next = temp;
result = result.next;
result.val = (l1.val+step)%10;
step = (l1.val+step)/10;
}
while(l2.next!=null){
l2 = l2.next;
ListNode temp = new ListNode(0);
result.next = temp;
result = result.next;
result.val = (l2.val+step)%10;
step = (l2.val+step)/10;
}
if(step!=0){
ListNode temp = new ListNode(0);
result.next = temp;
result = result.next;
result.val = step;
}
result.next=null;
return head;
}
思路二：统一综合处理
整体处在只要不为空就进行循环，然后在循环内部分情况进行处理，在外部同时需要考虑最后发生进位的问题。
public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
ListNode result=new ListNode(0);
ListNode head=result;
int step=0;
while(l1!=null || l2!=null){
int x = (l1!=null)?l1.val:0;
int y = (l2!=null)?l2.val:0;
int sum = x+y+step;
head.next = new ListNode(sum%10);
step = sum/10;
head = head.next;
if(l1!=null)
l1=l1.next;
if(l2!=null)
l2=l2.next;
}
if(step>0){
head.next = new ListNode(step);
}
return result.next;
}
3.无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路一：暴力求解法
总体时间复杂度为，野蛮法会带来很大的时间消耗。
public static int lengthOfLongestSubstring(String s) {
int max_length = 0;
String temp;
for(int i=0;i<s.length()-max_length;i++){
temp = String.valueOf(s.charAt(i));
for (int j =i+1;j<s.length();j++){
if(temp.contains(String.valueOf(s.charAt(j))))
break;
else
temp = temp+s.charAt(j);
}
max_length = (temp.length()>max_length)?temp.length():max_length;
}
return max_length;
}
思路二：哈希求解法
这种方式将每个字符存入哈希表中，然后进行正常逻辑的处理。
public static int lengthOfLongestSubstring1(String s){
HashMap<Character,Integer> map = new HashMap<>();
int max_length=0;
for (int i=0,j=0;j<s.length();j++){
if(map.containsKey(s.charAt(j))){
i= Math.max(map.get(s.charAt(j)),i);
}
max_length = Math.max(max_length,j-i+1);
map.put(s.charAt(j),j+1);
}
return max_length;
}
网友评论