东单网站建设,可以做网站的公司,网络培训是什么意思,无极招聘网无极在线目录
1.两数之和
2.两数相加
拓展到牛客的TOP101的BM11( 链表相加#xff08;二#xff09;)
3.无重复的最长子串#xff08;牛客BM92#xff09; 解法1#xff1a;
解法2#xff1a;
4.寻找两个正序数组的中位数 5.最长回文子串 1.两数之和 思路#xff1a;用Has…目录
1.两数之和
2.两数相加
拓展到牛客的TOP101的BM11( 链表相加二)
3.无重复的最长子串牛客BM92 解法1
解法2
4.寻找两个正序数组的中位数 5.最长回文子串 1.两数之和 思路用HashMap的containKeykey是具体数值value是对应下标。如果包含了目标数字-当前数字的值则返回key对应的value以及当前下标否则将其加入到HashMap中
代码
public int[] twoSum(int[] nums, int target) { //创建hashmapHashMapInteger,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){vall1.val;l1l1.next;}if (l2!null){vall2.val;l2l2.next;}temp val/10;ListNode node new ListNode(val%10);//尾插法建立链表cur.nextnode;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;}//两个辅助栈StackListNode s1 new Stack();StackListNode 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()){vals2.pop().val;}//判断进位temp val/10;//头插法val%10是如果存在进位的话应该只取个位比如说//s1的值是7s2的值是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 (snull)return 0;int length s.length();int max 0;//hashmapHashMapCharacter,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-j1);}return max;}
解法2
用一个队列Queue把元素不停的加入到队列中如果有相同的元素就把队首的元素移除这样我们就可以保证队列中永远都没有重复的元素记录队列的最大长度。 代码
public int lengthOfLongestSubstring(String s) {
// write code hereif (snull)return 0;int length s.length();int max 0;//创建队列QueueCharacter 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存储数组数据ArrayListInteger 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 Li-1int j Li-1;//右边界越界则退出当前循环if (j len)break;//判断字符是否相等if (chars[i]!chars[j]){dp[i][j] false;}else {//如果子串长度2,即j-i1if (j-i1)dp[i][j]true;elsedp[i][j]dp[i1][j-1];}//只要 dp[i][L] true 成立就表示子串 s[i..L] 是回文此时记录回文长度和起始位置if (dp[i][j] j-i1 max){max j-i1;begin i;}}}return s.substring(begin,beginmax);}
