力扣hot100刷题记录
脑壳疼___
帮助1人
二刷hot100，坚持每天打卡3道题！！！Today：2023-8-14
1. 两数之和
// 先求差，再查哈希表
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i<nums.length;i ){
int key = target - nums[i];
if(map.containsKey(key)){
return new int[]{map.get(key),i};
}
map.put(nums[i],i);
}
return new int[0];
}
2. 两数相加
// 对应位置相加，记录进位，然后链表尾插法即可
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int flag = 0,lv1,lv2;
ListNode answer = null,target = null;
while (l1 != null || l2 != null){
lv1 = l1 == null ? 0:l1.val;
lv2 = l2 == null ? 0:l2.val;
l1 = l1 == null ? null:l1.next;
l2 = l2 == null ? null:l2.next;
int sum = lv1 lv2 flag;
flag = sum / 10;
ListNode listNode = new ListNode(sum % 10);
if (target == null){
target = listNode;
answer = target;
}else {
target.next = listNode;
target = target.next;
}
}
if (flag >0){
target.next = new ListNode(flag);
}
return answer;
}
3. 无重复字符的最长字串
// 滑动窗口
public int lengthOfLongestSubstring(String s){
Set<Character> set = new HashSet<>();
int start = 0,end = 0,answer=0;
while (end < s.length()){
if (set.contains(s.charAt(end))){
set.remove(s.charAt(start ));
}else {
set.add(s.charAt(end ));
answer = Math.max(answer,end - start);
}
}
return answer;
}
4. 最长回文子串
// 动态规划
public String longestPalindrome(String s) {
if (s == null || s.length() < 2) {
return s;
}
int strLen = s.length();
int maxStart = 0; //最长回文串的起点
int maxEnd = 0; //最长回文串的终点
int maxLen = 1; //最长回文串的长度
boolean[][] dp = new boolean[strLen][strLen];
for (int r = 1; r < strLen; r ) {
for (int l = 0; l < r; l ) {
if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l 1][r - 1])) {
dp[l][r] = true;
if (r - l 1 > maxLen) {
maxLen = r - l 1;
maxStart = l;
maxEnd = r;
}
}
}
}
return s.substring(maxStart, maxEnd 1);
}
5. 寻找两个正序数组的中位数
/*
总体思路：模拟合并数组，合并到中位数停止
时间：1ms， 击败 100.00%使用 Java 的用户
内存：42.03mb 击败 63.77%使用 Java 的用户
*/
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int num = 0; // 偶数中位数数字，奇数中位数右侧数字
int len = nums1.length nums2.length;
boolean b = len % 2 == 0; // 是否为偶数
len /= 2; // 偶数中位数位置，奇数中位数右侧位置
if (nums1.length nums2.length == 0) return 0; // 空数组返回0
if (nums1.length == 0) return b ? (nums2[len - 1] nums2[len]) / 2.0 : nums2[len]; // 数组1为空返回数组2中位数
if (nums2.length == 0) return b ? (nums1[len - 1] nums1[len]) / 2.0 : nums1[len]; // 数组2为空返回数组1中位数
int i = 0,j = 0;
int oldNum = num; // 奇数中位数左侧数字
while (i j != len 1) { // 判断是否循环至中位数
oldNum = num;
if (i >= nums1.length || (j < nums2.length && nums1[i] > nums2[j])) num = nums2[j ];
else num = nums1[i ];
}
return b ? (num oldNum) / 2.0 : num; // 返回中位数
}
6. 正则表达式匹配
// 动态规划
public boolean isMatch(String s, String p) {
//此处为length 1的目的是放入一个额外的为空的字符情况，以便于判断当*时，添加的字符情况
boolean table[][]=new boolean[s.length() 1][p.length() 1];
table[0][0]=true;
for(int i =1;i<table[0].length;i ){
char ch=p.charAt(i-1);
if(i>1){
//若ch=='*'，则看同一行内回退两格的boolean值：
//（因为相当于若回退两格为true，即在选择添加该字符时可以选择数量为0（因为是'*'））
if(ch=='*'){
table[0][i]=table[0][i-2];
}
//因为第0行的s字符为空，所以和除了*以外的都不匹配，直接false
else table[0][i]=false;
}
else {
//如果填第一个空格，且字符为*，则赋值为true（因为*的匹配可以选择0个字符）
if(ch=='*') table[0][i]=true;
}
}
//接下来按照行优先的顺序填充表格
for(int j =1;j<table.length;j ){
char ch01=s.charAt(j-1);
for(int h =1;h<table[j].length;h ){
char ch02=p.charAt(h-1);
//如果行和列对应的字符相等 || 列的字符为'.'，则当前位置的值由左斜上方的值确定
if(ch02==ch01||ch02=='.'){
table[j][h]=table[j-1][h-1];
}
//如果列的字符为'*'
else if(ch02=='*'){
if(h>1){
//按照规则，先在同一行回退两格，若该值为true则直接赋值true
if(table[j][h-2]==true) table[j][h]=true;
else {
//若不为true，则比较当前行的字符（s里的）与当前列-1的字符（p里的）是否相等
char prev=p.charAt(h-2);
//若相等 || 当前列-1的字符（p里的）为'.'，将当前位置上方的值赋给当前位置
if(ch01==prev||prev=='.') table[j][h]=table[j-1][h];
}
}
}
}
}
//返回table表的最右下方元素，即为整个字符串的匹配结果
return table[s.length()][p.length()];
}
7. 盛水最多的容器
/**
* 高往低走，长度变小、高度变小、面积一定变小
* 低往高走，长度变小、高度可能变大、面积可能变大
*/
public int maxArea(int[] height) {
int i = 0, j = height.length - 1, res = 0;
while(i < j) {
res = height[i] < height[j]
? Math.max(res, (j - i) * height[i ])
: Math.max(res,(j - i) * height[j--]);
}
return res;
}
8. 三数之和
/*
思路：排序 双指针
-4,1,2,3
当前元素(target)的下一个元素(left)为起点、最后一个元素(right)为终点进行计算
情况1：target left right == 0 》 正确
情况2：target left right > 0 》 说明 right 数值太大，right--
情况3：target left right < 0 》 说明 left 数值太小，left
*/
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < nums.length ; i ) {
// 当前元素>0 后面的所有元素肯定都>0，所以提前结束
if(nums[i] > 0) break;
// 当前元素和前一个元素相同，说明发现重复数字，无需再次计算
if(i > 0 && nums[i] == nums[i-1]) continue;
int left = i 1;
int right = nums.length-1;
while(left < right){
int sum = nums[i] nums[left] nums[right];
if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[left],nums[right]));
// [-2,0,0,2,2] 跳过相同数字，去重
while (left<right && nums[left] == nums[left 1]) left ;
// [-2,0,0,2,2] 跳过相同数字，去重
while (left<right && nums[right] == nums[right-1]) right--;
left ;
right--;
}
else if (sum < 0) left ;
else right--;
}
}
return ans;
}
9. 电话号码的字母组合
private StringBuilder sb = new StringBuilder();
private List<String> answer = new ArrayList<>();
/*
思路：获取对应字母的字符串，递归组合
*/
public List<String> letterCombinations(String digits) {
if(digits.equals("")) return new ArrayList<>();
String[] nums = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> list = new ArrayList<>(4);
for (int i = 0; i < digits.length(); i ) list.add(nums[Integer.parseInt(digits.charAt(i) "")]);
assemble(list,0);
return answer;
}
private void assemble(List<String> list, int index) {
if (index == list.size()){
answer.add(sb.toString());
return;
}
String numChars = list.get(index);
for (int i = 0; i < numChars.length(); i ) {
// 组装
sb.append(numChars.charAt(i));
assemble(list,index 1);
// 回溯
sb.deleteCharAt(index);
}
}
10. 删除列表倒数第n个结点
/*
思路：双指针，start，end
start定位正数第n个结点，然后end和start循环后移，当start指向最后一个元素时，end就指向了要删除元素的前一个结点
注意：删除头结点或尾结点时会存在问题，所以新建一个空的前驱结点做为头结点
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre = new ListNode(0);
pre.next = head;
ListNode start = pre, end = pre;
while(n != 0) {
start = start.next;
n--;
}
while(start.next != null) {
start = start.next;
end = end.next;
}
end.next = end.next.next;
return pre.next;
}
11. 有效的括号
/*
配对问题，优先考虑栈
*/
public boolean isValid(String s) {
final Map<Character,Character> map = new HashMap<Character,Character>(){{
put('{','}'); put('[',']'); put('(',')');
}};
Stack<Character> stack = new Stack<Character>();
// 保证栈不为空，如果第一个字符为 }]) 中的一种会出现 空栈pop
stack.push('1');
for(Character c : s.toCharArray()){
if(map.containsKey(c)) stack.push(c);
else if(map.get(stack.pop()) != c) return false;
}
return stack.size() == 1;
}
12. 合并两个有序链表
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode node = new ListNode(),head = node;
while (true){
if (list1 == null && list2 == null){
return head.next;
}else if (list1 == null){
node.next = new ListNode(list2.val);
list2 = list2.next;
}else if (list2 == null){
node.next = new ListNode(list1.val);
list1 = list1.next;
}else {
if (list1.val > list2.val){
node.next = new ListNode(list2.val);
list2 = list2.next;
}else {
node.next = new ListNode(list1.val);
list1 = list1.next;
}
}
node = node.next;
}
}
13. 括号生成
/*
回溯： 左括号的数量 < n那，加'('
右括号的数量 < 左括号的数量,加')'
StringBuilder的元素长度== n 结束
*/
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
dfs(n, 0, 0,res,sb);
return res;
}
public void dfs(int n, int left, int right,List<String> res,StringBuilder sb) {
if (sb.length() == n*2){
res.add(sb.toString());
return;
}
if(left < n){
sb.append("(");
dfs(n,left 1,right,res,sb);
sb.deleteCharAt(sb.length()-1);
}
if (right < left){
sb.append(")");
dfs(n,left,right 1,res,sb);
sb.deleteCharAt(sb.length()-1);
}
}
14. 合并 k 个升序链表
//-----------------------------解法1----------------------------------------
// （不推荐）：暴力求解，获取所有元素排序后生成
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> list = new ArrayList<>();
for (ListNode node : lists) {
while (node != null){
list.add(node.val);
node = node.next;
}
}
list.sort(Comparator.comparingInt(o -> o));
ListNode listNode = new ListNode(0),p = listNode;
for (Integer val : list) {
p.next = new ListNode(val);
p = p.next;
}
return listNode.next;
}
//-----------------------------解法2----------------------------------------
// 解法2：获取每个链表中的最小值
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
ListNode head = new ListNode(0),p = head;
while (true) {
int minIndex = -1,minVal = Integer.MAX_VALUE;
for (int i = 0; i < k; i ) {
if (lists[i] == null) {
continue;
}
if (lists[i].val < minVal) {
minVal = lists[i].val;
minIndex = i;
}
}
if (minVal == Integer.MAX_VALUE) {
break;
}
lists[minIndex] = lists[minIndex].next;
p.next = new ListNode(minVal);
p = p.next;
}
return head.next;
}
这篇好文章是转载于：学新通技术网
- 版权申明： 本站部分内容来自互联网，仅供学习及演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，请提供相关证据及您的身份证明，我们将在收到邮件后48小时内删除。
- 本站站名： 学新通技术网
- 本文地址： /boutique/detail/tanhgghjaf
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储，并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13
