前言
2023-7-1 10:52:39
推荐
HOT 100（1~20）
1. 两数之和【简单】
简单
15.7K
相关企业
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1： 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 示例 2： 输入：nums = [3,2,4], target = 6 输出：[1,2] 示例 3： 输入：nums = [3,3], target = 6 输出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
class Solution { public int[] twoSum(int[] nums, int target) { HashMap<Integer,Integer> map=new HashMap<>(); for(int i=0;i<nums.length;i++){ if(map.containsKey(target-nums[i])){ return new int[]{map.get(target-nums[i]),i}; } map.put(nums[i],i); } return new int[0]; } }
三数之和
四数之和
两数之和 II - 输入有序数组
2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1： 输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807. 示例 2： 输入：l1 = [0], l2 = [0] 输出：[0] 示例 3： 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
我的解法：一位加法器
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode res=new ListNode(-1); ListNode cur=res; ListNode cur1=l1; ListNode cur2=l2; int[] r={0,0}; while(cur1!=null&&cur2!=null){ r=add(cur1.val, cur2.val, r[0]); cur.next=new ListNode(r[1]); cur1=cur1.next; cur2=cur2.next; cur=cur.next; } while (cur1!=null){ r= add(cur1.val, 0, r[0]); cur.next=new ListNode(r[1]); cur1=cur1.next; cur=cur.next; } while (cur2!=null){ r= add(0, cur2.val, r[0]); cur.next=new ListNode(r[1]); cur2=cur2.next; cur=cur.next; } if(r[0]!=0){ cur.next=new ListNode(r[0]); } return res.next; } public int[] add(int a,int b,int jin){ int c=(a+b+jin)%10; jin=(a+b+jin)/10; return new int[]{jin,c}; } }
我之前的解法
递归
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if (l1==null){ return l2; } if (l2==null){ return l1; } l2.val= l1.val+ l2.val; if(l2.val>=10){ l2.val= l2.val%10; if (l2.next!=null){ l2.next.val+=1; if (l2.next.val==10){ l2.next = addTwoNumbers(new ListNode(0, null), l2.next); } } else { l2.next = new ListNode(1, null); } } l2.next = addTwoNumbers(l1.next, l2.next); return l2; } }
官方的解法
模拟
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode head = null, tail = null; int carry = 0; while (l1 != null || l2 != null) { int n1 = l1 != null ? l1.val : 0; int n2 = l2 != null ? l2.val : 0; int sum = n1 + n2 + carry; if (head == null) { head = tail = new ListNode(sum % 10); } else { tail.next = new ListNode(sum % 10); tail = tail.next; } carry = sum / 10; if (l1 != null) { l1 = l1.next; } if (l2 != null) { l2 = l2.next; } } if (carry > 0) { tail.next = new ListNode(carry); } return head; } }
3. 无重复字符的最长子串【中等】
中等
8.4K
相关企业
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1: 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
class Solution { public int lengthOfLongestSubstring(String s) { // 哈希集合，记录每个字符是否出现过 Set<Character> occ = new HashSet<Character>(); int n = s.length(); // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动 int rk = -1, ans = 0; for (int i = 0; i < n; ++i) { if (i != 0) { // 左指针向右移动一格，移除一个字符 occ.remove(s.charAt(i - 1)); } while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) { // 不断地移动右指针 occ.add(s.charAt(rk + 1)); ++rk; } // 第 i 到 rk 个字符是一个极长的无重复字符子串 ans = Math.max(ans, rk - i + 1); } return ans; } }
4. 寻找两个正序数组的中位数 【困难】
4.寻找两个正序数组的中位数
困难
6.6K
相关企业
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1： 输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2 示例 2： 输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
我的解法
总共奇数个元素，和偶数个元素是不一样的
还有就是数组是从0开始计数的，中间的下标计算不一样
偶树计算的是中-左，中-右
奇数计算的是中左，中
用res存放
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { double res; int len1 = nums1.length; int len2 = nums2.length; int len = nums1.length + nums2.length; int even = len % 2; int mid = len / 2-1; int c1 = 0, c2 = 0; int []res0 =new int[2]; for (int i = 0; i <= mid + 1; i++) { if (c2 >= len2 || (c1<len1&&nums1[c1] <= nums2[c2])) { res0[i%2] = nums1[c1]; c1++; }else if (c1 >= len1 || (c2<len2&&nums1[c1] > nums2[c2])) { res0[i%2] = nums2[c2]; c2++; } } if (even == 0) { res = ((double) res0[0] + res0[1]) / 2; } else { res = Math.max(res0[0], res0[1]); } return res; } }
5. 最长回文子串【中等】
中等
5.9K
相关企业
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1： 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2： 输入：s = "cbbd" 输出："bb"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
方法一：动态规划
对于一个子串而言，如果它是回文串，并且长度大于 222，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是“a”。
P(i,j)=P(i+1,j−1)∧(S i ==S j )
class Solution { public String longestPalindrome(String s) { //长度为1，本身就是回文的 int len=s.length(); if(len<2){ return s; } //记录最长回文子串长度 int maxLen=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[] charArray = s.toCharArray(); // 递推开始 //枚举子串长度 for(int L=2;L<=len;L++){ //枚举左边界 for(int l=0;l<len;l++){ int r=L+l-1; if(r>=len){ break; } //s[i,j] 本身不是一个回文串； if(charArray[l]!=charArray[r]){ dp[l][r]=false; }else{ if(r-l<3){ dp[l][r]=true; }else{ dp[l][r]=dp[l+1][r-1]; } } // 只要 dp[l][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置 if (dp[l][r] && r - l + 1 > maxLen) { maxLen = r - l + 1; begin = l; } } } return s.substring(begin, begin + maxLen); } }
