LeetCode-Java(04)

这篇具有很好参考价值的文章主要介绍了LeetCode-Java(04)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

15. 三数之和

LeetCode-Java(04),LeetCode刷题,java,开发语言,算法

 固定第一个数,从后面找第二个和的三个数的和等于第一个数,转化为两数之和问题。比target大,则l--,否则r++,直到找到三个数

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            int low = i + 1;
            int high = nums.length - 1;
            int target = -nums[i];
            
            // two pointer to solve two sum
            while (low < high) {
                int l = nums[low];
                int h = nums[high];
                
                if (l + h < target) low++;
                else if (l + h > target) high--;
                else {
                    res.add(Arrays.asList(nums[i], l, h));
                    
                    // attention: low < high
                    while (low < high && nums[low + 1] == nums[low]) low++;
                    // new nums[low] val
                    low++;
                }
            }
        }
        
        return res;
    }
}

16. 最接近的三数之和

LeetCode-Java(04),LeetCode刷题,java,开发语言,算法

 和上一题一样,之多加了一个判断语句 if(Math.abs(target - sum) < Math.abs(target - ans))

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for(int i=0;i<nums.length;i++) {
            int start = i+1, end = nums.length - 1;
            while(start < end) {
                int sum = nums[start] + nums[end] + nums[i];
                if(Math.abs(target - sum) < Math.abs(target - ans))
                    ans = sum;
                if(sum > target)
                    end--;
                else if(sum < target)
                    start++;
                else
                    return ans;
            }
        }
        return ans;
    }
}

17. 电话号码的字母组合

LeetCode-Java(04),LeetCode刷题,java,开发语言,算法回溯法

class Solution {
	String[] letter_map = {" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
	public List<String> letterCombinations(String digits) {
		if(digits==null || digits.length()==0) {
			return new ArrayList<>();
		}
		iterStr(digits, new StringBuilder(), 0);
		return res;
	}

	List<String> res = new ArrayList<>();
	
	//递归函数
	public void iterStr(String digits,StringBuilder sb, int index){
		//"ad" index==digits.length()==2 满足条件 存入res
		if(index==digits.length()){ 
			res.add(sb.toString());
			return;
		}
		char c=digits.charAt(index);
		int pos=c-'0'; // 23 对应成字符串数组中的下标
		String letterstr=letter_map[pos]; // 得到字符串
		for(int i=0;i<letterstr.length();i++){
			// 拼接
			sb.append(letterstr.charAt(i));
			// 下一层递归
			iterStr(digits, sb, index+1);
			// 例如"ad"结果产生到res中后,删除最后一个字符 
			sb.deleteCharAt(sb.length()-1);
		}
	}
	
}

队列

class Solution {

	public List<String> letterCombinations(String digits) {
		if(digits==null || digits.length()==0) {
			return new ArrayList<String>();
		}
		//一个映射表,第二个位置是"abc“,第三个位置是"def"。。。
		//这里也可以用map,用数组可以更节省点内存
		String[] letter_map = {
			" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
		};
		List<String> res = new ArrayList<>();
		//先往队列中加入一个空字符
		res.add("");
		for(int i=0;i<digits.length();i++) {
			//由当前遍历到的字符,取字典表中查找对应的字符串
			String letters = letter_map[digits.charAt(i)-'0'];
			int size = res.size();
			//计算出队列长度后,将队列中的每个元素挨个拿出来
			for(int j=0;j<size;j++) {
				//每次都从队列中拿出第一个元素
				String tmp = res.remove(0);
				//然后跟"def"这样的字符串拼接,并再次放到队列中
				for(int k=0;k<letters.length();k++) {
					res.add(tmp+letters.charAt(k));
				}
			}
		}
            // 队列结构变化:""-a,b,c-a,b,c,ad,-a,b,c,ad,ae,af-b,c,ad,ae,af,bd ……
		return res;

	}

}

18. 四数之和

LeetCode-Java(04),LeetCode刷题,java,开发语言,算法

第一步肯定还是先排序,和三数之和一样的思想,就是剪枝操作多一点。

  1. 在确定第一个数之后,如果 nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target,说明此时剩下的三个数无论取什么值,四数之和一定大于 target,因此退出第一重循环;
  2. 在确定第一个数之后,如果 nums[i]+nums[n−3]+nums[n−2]+nums[n−1]<target,说明此时剩下的三个数无论取什么值,四数之和一定小于 target,因此第一重循环直接进入下一轮,枚举 nums[i+1];
  3. 在确定前两个数之后,如果 nums[i]+nums[j]+nums[j+1]+nums[j+2]>target,说明此时剩下的两个数无论取什么值,四数之和一定大于target,因此退出第二重循环;
  4. 在确定前两个数之后,如果 nums[i]+nums[j]+nums[n−2]+nums[n−1]<target,说明此时剩下的两个数无论取什么值,四数之和一定小于target,因此第二重循环直接进入下一轮,枚举 nums[j+1]。

这里i是第一重取值从0到length-3,j是第二重,取值从i+1到length-2,固定两个以后,取right和left为剩下的左右端点,接下来的分析情况就和三数之和一样了。文章来源地址https://www.toymoban.com/news/detail-628583.html

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 4) {
            return quadruplets;
        }
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = 0; i < length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
                continue;
            }
            for (int j = i + 1; j < length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                    continue;
                }
                int left = j + 1, right = length - 1;
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        left++;
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return quadruplets;
    }
}

到了这里,关于LeetCode-Java(04)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode-Java:26.删除有序数组的重复项

    给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过

    2024年02月05日
    浏览(45)
  • Java算法 leetcode简单刷题记录6

    环和杆: https://leetcode.cn/problems/rings-and-rods/ 统计范围内的元音字符串数: https://leetcode.cn/problems/count-the-number-of-vowel-strings-in-range/ 最长平衡子字符串: https://leetcode.cn/problems/find-the-longest-balanced-substring-of-a-binary-string/ K 个元素的最大和: https://leetcode.cn/problems/maximum-sum-with-exa

    2024年01月24日
    浏览(46)
  • Java算法 leetcode简单刷题记录4

    买卖股票的最佳时机: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 笨办法: 记录当天的值及之后的最大值,相减得到利润; 所有的天都计算下,比较得到利润最大值; 会超时 记录过程中遇到的最低值,每当有利润大于0及大于上一个利润值的情况,赋值; 最小和分割:

    2024年01月23日
    浏览(45)
  • java数据结构与算法刷题-----LeetCode283. 移动零

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 双指针,用right和left两个指针,将非0元素,全部按顺序换到数组前面。left指向左边非0元素应该插入的位置,right找到非

    2024年01月21日
    浏览(49)
  • java数据结构与算法刷题-----LeetCode566. 重塑矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 代码:时间复杂度O(r*c).除题目要求外,算法本身没有需要额外空间,空间复杂度O(1) 从0开始算,一个3列n行矩阵中,每行就有3个元

    2024年01月21日
    浏览(46)
  • java数据结构与算法刷题-----LeetCode287. 寻找重复数

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 弗洛伊德判圈法,也就是快慢指针判圈法(龟兔赛跑算法),此算法分为两个步骤 判断是否有环,并得到快慢指针相遇

    2024年01月24日
    浏览(43)
  • java数据结构与算法刷题-----LeetCode766. 托普利茨矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 这道题只要换一种理解方式,瞬间就会变的很简单。 题目描述是每个元素左上和右下对角线元素都相同。但是,我们发

    2024年01月25日
    浏览(48)
  • java数据结构与算法刷题-----LeetCode667. 优美的排列 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 题目要求我们返回一个数组长度为n的数组,必须含有1~n的所有数,并且从左到右,相邻的元素依次相减,它们的差,必

    2024年01月25日
    浏览(52)
  • java数据结构与算法刷题-----LeetCode240. 搜索二维矩阵 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 法一:把整个数组遍历一遍,时间复杂度O(m*n) 法二:每一行用二分搜索,那么时间复杂度就是O(m * l o g 2 n log_2{n} l o g

    2024年01月22日
    浏览(62)
  • java数据结构与算法刷题-----LeetCode209. 长度最小的子数组

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 代码:时间复杂度O(n).空间复杂度O(1)

    2024年01月21日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包