力扣HOT100 (1-5)

目录

1.两数之和

2.两数相加

拓展到牛客的TOP101的BM11( 链表相加（二）)

3.无重复的最长子串（牛客BM92）

 解法1：

解法2：

4.寻找两个正序数组的中位数

 5.最长回文子串

---

1.两数之和

思路：用HashMap的containKey，key是具体数值，value是对应下标。如果包含了目标数字-当前数字的值，则返回key对应的value以及当前下标，否则将其加入到HashMap中，

代码： 

public int[] twoSum(int[] nums, int target) {        //创建hashmapHashMap<Integer,Integer> hashMap = new HashMap<>();for (int i = 0; i < nums.length; i++) {//是否包含if (hashMap.containsKey(target-nums[i])){return new int[] {hashMap.get(target-nums[i]),i};}//将其加入到HashMap中hashMap.put(nums[i], i);}return new int[0];}

2.两数相加

 思路：链表第一个节点是个位，然后依次向后是百位，千位.....。因此，直接用链表从一个节点进行相加，获得新的值，存入新的链表中（尾插法），最终输出。

代码：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//新链表，有虚拟头节点ListNode newHead = new ListNode(-1);ListNode cur = newHead;//进位int temp = 0;while (l1!=null || l2!=null){int val = temp;if (l1!=null){val+=l1.val;l1=l1.next;}if (l2!=null){val+=l2.val;l2=l2.next;}temp = val/10;ListNode node = new ListNode(val%10);//尾插法建立链表cur.next=node;cur = cur.next;}//判断最后一位if (temp > 0){ListNode node = new ListNode(temp);cur.next= node;}//输出跳过虚拟头节点return newHead.next;}

拓展到牛客的TOP101的BM11( 链表相加（二）)

思路：可知，链表最后一个节点是个位，然后依次向前是百位，千位.....，我们相加都是先从个位加起，然后百位.....（中间要考虑进位），因此，采用栈的方式，利用栈的先进后出，获取链表尾部（个位），然后依次出栈相加，获得新的值，存入新的链表中(头插法)，最终输出。

 代码：

import java.util.*;
//链表类 
public class ListNode {int val;ListNode next = null;}public class Solution {/*** * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类*/public ListNode addInList (ListNode head1, ListNode head2) {// write code here//特殊情况if (head1 == null){return head2;}if (head2 == null){return head1;}//两个辅助栈Stack<ListNode> s1 = new Stack<>();Stack<ListNode> s2 = new Stack<>();ListNode h1 = head1;ListNode h2 = head2;//两个链表依次入栈while (h1!= null){s1.push(h1);h1 = h1.next;}while (h2 != null){s2.push(h2);h2 = h2.next;}//进位int temp = 0;//创建新链表，ListNode newHead = null;//当s1或s2不为空的时候while (!s1.isEmpty() || !s2.isEmpty()){int val = temp;if (!s1.isEmpty()){val += s1.pop().val;}if (!s2.isEmpty()){val+=s2.pop().val;}//判断进位temp = val/10;//头插法，val%10是，如果存在进位的话，应该只取个位，比如说//s1的值是7，s2的值是8，两者相加后，得15，因此，进位是1，而新节点的值是5ListNode node = new ListNode(val%10);node.next = newHead;newHead = node;}//判断第一位if (temp > 0){ListNode node = new ListNode(temp);node.next = newHead;newHead = node;}return newHead;}
}

3.无重复的最长子串（牛客BM92）

 解法1：

思路：我们使用两个指针，一个i一个j，最开始的时候i和j指向第一个元素，然后i往后移，把扫描过的元素都放到HashMap中，如果i扫描过的元素没有重复的就一直往后移，顺便记录一下最大值max，如果i扫描过的元素有重复的，就改变j的位置。我们就以p w w k e w，（图源自牛客大佬）

代码：

public int lengthOfLongestSubstring(String s) {
// write code hereif (s==null)return 0;int length = s.length();int max = 0;//hashmapHashMap<Character,Integer> hp = new HashMap<>();for (int i = 0,j = 0; i < length; i++) {if (hp.containsKey(s.charAt(i))){j = Math.max(j,hp.get(s.charAt(i))+1);}hp.put(s.charAt(i),i);max = Math.max(max,i-j+1);}return max;}

解法2：

用一个队列（Queue），把元素不停的加入到队列中，如果有相同的元素，就把队首的元素移除，这样我们就可以保证队列中永远都没有重复的元素，记录队列的最大长度。

代码：

public int lengthOfLongestSubstring(String s) {
// write code hereif (s==null)return 0;int length = s.length();int max = 0;//创建队列Queue<Character> queue = new LinkedList<>();for (int i = 0; i < length; i++) {while (queue.contains(s.charAt(i)))//移除队首元素queue.poll();queue.add(s.charAt(i));max = Math.max(max,queue.size());}return max;}

4.寻找两个正序数组的中位数

思路：由于是困难题，故先放弃最优解法，先给出一个笨方法，即将两个数组合并，然后输出合并数组的中位数。（后续如果有多余的时间刷困难题，会进行完善）

代码：

public double findMedianSortedArrays(int[] nums1, int[] nums2) {//第一种方法：先将两个数组合并，然后排序，找到中位数。//创建arraylist，存储数组数据ArrayList<Integer> list = new ArrayList<>();//添加第一个数组for (int i = 0; i < nums1.length; i++) {list.add(nums1[i]);}//添加第二个数组for (int i = 0; i < nums2.length; i++) {list.add(nums2[i]);}//排序Collections.sort(list);//转化为数组Integer[] num = list.toArray(new Integer[(list.size())]);//寻找中位数if (num.length %2 == 0){return (num[num.length/2]+num[num.length/2-1])/2.0;}else {return num[num.length/2];}}

 5.最长回文子串

 思路：动态规划（参考官方）

动态规划的步骤：

 代码：

public static String longestPalindrome(String s) {int len = s.length();//如果字符串长度小于2，直接返回if (len < 2)return s;int max = 1;//起始位置int begin = 0;// dp[i][j] 表示 s[i..j] 是否是回文串boolean[][] dp = new boolean[len][len];//所有长度为1的子串一定是回文串for (int i = 0; i < len; i++) {dp[i][i] = true;}//将字符串转化为char数组char[] chars = s.toCharArray();//开始递推//L为子串的长度，从2开始枚举，因为子串长为1的已经为truefor (int L = 2; L <= len; L++) {//枚举左边界for (int i = 0; i < len; i++) {//右边界j = L+i-1；int j = L+i-1;//右边界越界则退出当前循环if (j >= len)break;//判断字符是否相等if (chars[i]!=chars[j]){dp[i][j] = false;}else {//如果子串长度<=2,即j-i<1if (j-i<=1)dp[i][j]=true;elsedp[i][j]=dp[i+1][j-1];}//只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置if (dp[i][j] && j-i+1 > max){max = j-i+1;begin = i;}}}return s.substring(begin,begin+max);}