java基础(10)---leetcode的String、数组以及集合的一些使用
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java基础(10)---leetcode的String、数组以及集合的一些使用，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含15276字，纯文字阅读大概需要22分钟。
内容图文
整数
一、整数反转_7
/*
12345 变成 54321
*/
public class 整数反转_7 {
public static void main(String[] args){
int x = 12345;
System.out.println(reverseInt(x));
}
public static int reverseInt(int x){
int res = 0;
while (x != 0){
int pop = x % 10;
if (res > Integer.MAX_VALUE / 10 || res == Integer.MAX_VALUE && pop > 7) return 0;
if (res < Integer.MIN_VALUE / 10 || res == Integer.MIN_VALUE && pop < -8) return 0;
res = res * 10 + pop;
x /= 10;
}
return res;
}
}
View Code
数组
一、两数之和_1(数组）
/*
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
*/
import java.util.HashMap;
import java.util.Map;
public class 两数之和_1 {
public static void main(String[] args){
int[] nums = {1,2};
int target = 3;
//法一：
int[] result = method1(nums,target);
System.out.println( result[0] + "" + result[1] );
//法二：
int[] result2 = method2(nums,target);
System.out.println(result2[0] + "" + result2[1]);
}
//法一：两次遍历，时间O(n2)，空间O(n)
public static int[] method1(int[] nums, int target){
for (int i = 0; i < nums.length; i++){
for (int j = i+1; j < nums.length; j++){
if (nums[i] + nums[j] == target){
return new int[] {i,j};
}
}
}
throw new IllegalArgumentException("No such target");
}
//法二：采用字典存储,时间O（n),空间O(n）
public static int[] method2 (int[] nums, int target){
//遍历一遍，存储到map中，key为nums值，value为索引
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++){
map.put(nums[i] , i);
}
// 遍历第二遍，查看target-nums[i] 是否在字典中
for (int i = 0; i < nums.length; i++){
int tmp = target - nums[i];
if (map.containsKey(tmp) && map.get(tmp) != i) {
return new int[]{i, map.get(tmp)};
}
}
throw new IllegalArgumentException("No such target!");
}
}
View Code
二、三数之和_15（数组）
/*
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
*/
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
public class 三数之和_15 {
public static void main(String[] args){
int[] nums = {-1,0,1,2,-2,4};
threeSum(nums);
}
public static List<List<Integer>> threeSum(int[] nums){
List<List<Integer>> ans = new ArrayList<List<Integer>>();
int len = nums.length;
if (nums == null && len < 3) return ans;
Arrays.sort(nums); // 排序
for (int i = 0; i < len; i++){
if (nums[0] > 0) break; //如果第一个数大于0，直接退出
while (i > 0 && nums[i] == nums[i-1]) continue; //去重
int L = i+1, R = len - 1;
while (L < R){ //两数之和
int sum = nums[i] + nums[L] + nums[R];
if (sum == 0){
ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
while (L < R && nums[L] == nums[L+1]) L++; //去重
while (L < R && nums[R] == nums[R-1]) R--; //去重
L++;
R--;
}
else if(sum < 0) {
L++;
}
else if (sum > 0){
R--;
}
}
}
return ans;
}
}
View Code
三、删除排序数组中的重复项_26 (数组）
/*
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
*/
public class 删除排序数组中的重复项_26 {
public static void main(String[] args){
int[] nums = {1,1,1,2,2,3,4,4,5};
System.out.println(removeDulplicates(nums));
}
public static int removeDulplicates(int[] nums){
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++){
if (nums[i] != nums[j]){
i++;
nums[i] = nums[j];
}
}
return i+1;
}
}
View Code
四、寻找两个有序数组的中位数_4（数组）
/*
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
*/
public class 寻找两个有序数组的中位数_4 {
public static void main(String[] arg){
int[] nums1 = {};
int[] nums2 = {2,3};
System.out.println(findMedianSortedArrays(nums1,nums2));
}
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] numsAll = new int[ m+n ];
int i = 0;
int j = 0;
while (i < m && j < n){
if (nums1[i] < nums2[j]){
numsAll[i+j] = nums1[i];
i++;
} else{
numsAll[i+j] = nums2[j];
j++;
}
}
for (int a=i+j; a < m+n; a++ ){
if (i < m){
numsAll[a] = nums1[i];
i++;
}
else{
numsAll[a] = nums2[j];
j++;
}
}
int mid = (m+n)/2;
if ((m+n)%2 == 0){
return (numsAll[mid-1] + numsAll[mid]) / 2.0;
}
else{
return numsAll[mid];
}
}
}
View Code
五、搜索插入位置_35（数组）
/*
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
*/
public class 搜索插入位置_35 {
public static void main(String[] args){
int[] nums = {1,2,5,7};
int target = 2;
searchInsert(nums,target);
}
public static int searchInsert(int[] nums, int target) {
int len = nums.length;
if (len <= 0) return 0;
if (nums[len-1] < target) return len;
int left = 0 , right = len - 1;
while (left <= right){
int mid = (left + right) / 2;
if (nums[mid] > target){
right = mid - 1;
}
else if (nums[mid] < target){
left = mid + 1;
}
else{
return mid;
}
}
return left;
}
}
View Code
六、杨辉三角_118 （二维数组）
import java.util.ArrayList;
import java.util.List;
public class 杨辉三角_118 {
public static void main(String[] args){
int numRows = 5;
generate(numRows);
}
public static List<List<Integer>> generate(int numRows){
List<List<Integer>> triangle = new ArrayList<List<Integer>> ();
if (numRows == 0) return triangle;
triangle.add(new ArrayList<Integer>());
triangle.get(0).add(1);
for (int i= 1; i < numRows; i++){
List<Integer> row = new ArrayList<>();
List<Integer> preRow = triangle.get(i - 1);
row.add(1);
for (int j = 1; j < i; j++){
row.add(preRow.get(j) + preRow.get(j-1));
}
row.add(1);
triangle.add(row);
}
return triangle;
}
}
View Code
七、盛最多水的容器_11（数组）
/*
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
链接：https://leetcode-cn.com/problems/container-with-most-water。
思路：
两个首尾指针L,R，面积等于 高( tmp = min(nums[L],nums[R]) * 底 （R-L)；
然后，如果高等于nums[L]，则L++;
如果高等于nums[R], 则R--;
*/
public class 盛最多水的容器_11 {
public static void main(String[] args){
int[] height = {1,8,6,2,5,4,8,3,7};
System.out.println(maxArea(height));
}
public static int maxArea(int[] height){
int L = 0 , R = height.length - 1;
int area = Integer.MIN_VALUE;
while (L < R){
int temp = Math.min(height[L] , height[R]);
area = Math.max(area, temp * (R - L));
if (temp == height[L]) L++;
else if (temp == height[R]) R--;
}
return area;
}
}
View Code
八、买卖股票的最佳时机_121 (数组)
/*
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
思路：两个变量，一个记录谷底数值，一个记录结果（即最大利润）；
*/
public class 买卖股票的最佳时机_121 {
public static void main(String[] args){
int[] prices = {7,1,5,6,4,3};
System.out.println(maxProfit(prices));
}
public static int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = 0; i < prices.length; i++){
if (prices[i] < minPrice){
minPrice = prices[i];
}
else if (prices[i] - minPrice > maxProfit){
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}
}
View Code
字符串
一、Z型变换_6
import java.util.ArrayList;
import java.util.List;
public class Z字型变换_6 {
public static void main(String[] args){
String s = "leetcodeishiring";
int numsRow = 3;
System.out.println(convert(s,numsRow));
}
public static String convert(String s,int numsRow){
if (s.length() < numsRow) return s;
//初始化
List<StringBuilder> rows = new ArrayList<>();
for (int i = 0; i < Math.min(s.length(),numsRow); i++){
rows.add(new StringBuilder());
}
int curRow = 0;
boolean goingDown = false;
for (char c:s.toCharArray()){
rows.get(curRow).append(c);
if (curRow == 0 || curRow == numsRow - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}
StringBuilder res = new StringBuilder();
for (StringBuilder row: rows){
res.append(row);
}
return res.toString();
}
}
View Code
二、二进制求和_67
/*
1011 + 1101 = 11000
*/
public class 二进制求和_67 {
public static void main(String[] args){
String a = "1011", b = "1101";
System.out.println(addBinary(a,b));
}
public static String addBinary(String a,String b){
StringBuilder ans = new StringBuilder();
int ca = 0;
for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--){
int sum = ca;
sum += (i >= 0) ? a.charAt(i) - '0' : 0;
sum += (j >= 0) ? b.charAt(j) - '0' : 0;
ca = sum / 2;
ans.append(sum % 2);
}
ans.append(ca == 1 ? ca : "");
return ans.reverse().toString();
}
}
View Code
三、唯一摩尔斯密码词_804
import java.util.HashMap;
import java.util.Map;
public class 唯一摩尔斯密码词_804 {
public static void main(String[] args) {
String[] pwd = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."};
String keys = "abcdefghijklmnopqrstuvwxyz";
char[] key = keys.toCharArray();
Map<String, Integer> map = new HashMap<>();
String[] words = {"gin", "zen", "gig", "msg"};
for (String word : words) {
String password = "";
for (char ch : word.toCharArray()) {
password += pwd[ch - 97];
}
map.put(password, 1);
}
System.out.println(map.keySet().size());
}
}
View Code
四、报数_38
/*
1 1
2 11 "一个1"
3 21 "一个2一个1"
4 1211 "一个2一个1"
5 111221 "一个1一个2两个1"
6 312211
*/
public class 报数_38 {
public static void main(String[] args){
int n = 4;
System.out.println(
countAndSay(n)
);
}
public static String countAndSay(int n) {
String s = "11";
if (n==1){
return "1";
} else if(n==2){
return s;
}
for (int i = 2; i < n; i++ ){
int j = 0;
StringBuilder num = new StringBuilder();
while (j < s.length()-1){
int count = 1;
while (j < s.length()-1 && s.charAt(j) == s.charAt(j+1)){
count += 1;
j++;
}
num.append(""+count).append(s.charAt(j));
j++;
}
if (s.charAt(s.length()-1) != s.charAt(s.length()-2) ){
num.append("1").append(s.charAt(s.length()-1));
}
s = num.toString();
}
return s;
}
}
View Code
五、无重复的最长子串_3
/*
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
*/
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class 无重复元素的最长子串_3 {
public static void main(String[] args){
String s = "dvdf";
int res = lengthOfLongestSubstring(s);
System.out.println(res);
}
public static int lengthOfLongestSubstring(String s) {
Map<Character,Integer> map = new HashMap<> ();
int start = -1;
int res = 0;
for (int i = 0; i < s.length(); i++){
if (map.containsKey(s.charAt(i))){
start = Math.max(start,map.get(s.charAt(i)));
}
res = Math.max(i - start,res);
map.put(s.charAt(i),i);
}
return res;
}
}
View Code
六、转换成小写字母_709
/*
所有字符串都转成小写
*/
public class 转换成小写字母_709 {
public static void main(String[] args){
String s = "HeLLo";
System.out.println(toLowerCase(s));
}
public static String toLowerCase(String str){
char[] cArray = str.toCharArray();
for(int i= 0; i<cArray.length; i++){
if (cArray[i] <= 'Z' && cArray[i]>='A') {
cArray[i] = (char) (cArray[i] + 32);
}
}
return String.valueOf(cArray);
}
}
View Code
七、验证回文串_125
/*
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
*/
public class 验证回文串_125 {
public static void main(String[] args){
String s = "A man, a plan, a canal:Panama";
System.out.println(isPal1(s));
}
public static boolean isPal1(String s){
int len = s.length();
s = s.toLowerCase();
int i = 0, j = len - 1;
while (i < j){
while (!isAlpha(s.charAt(i))){
i++;
if (i == len){
return true;
}
}
while (!isAlpha(s.charAt(j))){
j--;
}
if (s.charAt(i)!= s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}
public static boolean isAlpha(char c){
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' &&c <= '9')){
return true;
}
return false;
}
}
View Code
集合
一、有效的括号_20
/*
判断括号是否有效
*/
import javax.swing.text.html.ListView;
import java.util.HashMap;
import java.util.Stack;
public class 有效的括号_20 {
private HashMap<Character,Character> mapping;
public 有效的括号_20(){
this.mapping = new HashMap<Character, Character>();
this.mapping.put(')','(');
this.mapping.put(']','[');
this.mapping.put('}','{');
}
public static void main(String[] args){
String s = "(()[])";
有效的括号_20 res = new 有效的括号_20();
System.out.println(res.isValid(s));
}
public boolean isValid(String s){
Stack<Character> stack = new Stack<>();
for (char ch : s.toCharArray()){
if (this.mapping.containsKey(ch)) {
char popChar = stack.isEmpty() ? '#' : stack.pop();
if (popChar != this.mapping.get(ch)) {
return false;
}
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}
View Code
链表
一、两数相加_2
/*
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
*/
import java.util.ArrayList;
class ListNode{
int val;
ListNode next;
ListNode(int x){ val = x; }
}
public class 两数相加_2 {
public static void main(String[] args) {
ListNode l1 = new ListNode(1);
ListNode head1 = l1;
for (int i = 2; i < 5; i++){
l1.next = new ListNode(i);
l1 = l1.next;
}
ListNode l2 = new ListNode(3);
ListNode head2 = l2;
for (int i = 4; i < 6; i++){
l2.next = new ListNode(i);
l2 = l2.next;
}
ArrayList<Integer> list = new ArrayList<Integer> ();
ListNode res = addNum(head1,head2);
while (res != null){
list.add(res.val);
res = res.next;
}
list.stream().forEach(System.out::println);
}
public static ListNode addNum (ListNode l1 , ListNode l2){
ListNode res = new ListNode(0);
ListNode head = res;
int flag = 0;
while (l1 != null || l2 != null){
int x = (l1 != null) ? l1.val : 0;
int y = (l2 != null) ? l2.val : 0;
int sum = x + y + flag;
flag = sum / 10;
res.next = new ListNode(sum % 10);
res = res.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (flag > 0){
res.next = new ListNode(flag);
}
return head.next;
}
}
View Code
内容总结
以上是互联网集市为您收集整理的java基础(10)---leetcode的String、数组以及集合的一些使用全部内容，希望文章能够帮你解决java基础(10)---leetcode的String、数组以及集合的一些使用所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】