欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode刷题day001 (Jieky)

程序员文章站 2022-03-21 09:13:39
LeetCode第一题/*Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.Example:Given nums = [2...

LeetCode第一题

/*
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]
*/

import java.util.Arrays;
import java.util.HashMap; 
import java.util.Map; 

public class TwoSum{
	
	// 暴力破解法,寻找两个数的和等于目标数
	public static int[] towSum01(int[] nums,int target){
		int ans[] = new int[2];
		for (int i=0;i<nums.length;i++){
			for (int j=i+1;j<nums.length;j++){
				if (nums[i]+nums[j] == target){
					ans[0] = i;
					ans[1] = j;
					return ans;
				}
			}
		}
		return ans;
	}
	
	// 先将数组放入HashMap,只需判断sub在不在hash的key里就可以了,这种解法利用了hash数据结构的快速访问的特性
	public static int[] towSum02(int[] nums,int target){
		int ans[] = new int[2];
		Map<Integer,Integer> map = new HashMap<>();
		for (int i=0;i<nums.length;i++){
			map.put(nums[i],i);
		}
		
		for (int i=0;i<nums.length;i++){
			int sub = target - nums[i];
			if (map.containsKey(sub) && map.get(sub) != i){
				ans[0] = i;
				ans[1] = map.get(sub);
				return ans;
			}
		}
		return ans;
	}
	
	// 这种实现的优化在于,寻找的另一个数一定不包含在map里
	public static int[] towSum03(int[] nums,int target){
		int ans[] = new int[2];
		Map<Integer,Integer> map = new HashMap<>();
		for (int i=0;i<nums.length;i++){
			map.put(nums[i],i);
			int sub = target - nums[i];
			if (map.containsKey(sub)){
				ans[0] = i;
				ans[1] = map.get(sub);
			}
		}
		return ans;
	}
	
	public static void main(String[] args){
		int nums[] = {2,7,11,15};
		int target = 9;
		int result[] = towSum03(nums,target);
		Arrays.sort(result);
		System.out.println(Arrays.toString(result));
	}
}

LeetCode第二题

/*
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
*/

import java.util.ArrayList;
import java.util.Collections;

class ListNode{
	int val;
	ListNode next;
	ListNode(int x){val=x;}
}
	
public class AddTwoNumbers{
	
	public static void main(String[] args){
		// 生成第一个链表
		ListNode L1_head = new ListNode(4);
		ListNode temp01 = L1_head;
		temp01.next = new ListNode(4);
		temp01 = temp01.next;
		temp01.next = new ListNode(3);
		temp01 = temp01.next;
		temp01.next=null;
		
		// 生成第二个链表
		ListNode L2_head = new ListNode(5);
		ListNode temp = L2_head;
		temp.next = new ListNode(6);
		temp = temp.next;
		temp.next = new ListNode(4);
		temp = temp.next;
		temp.next=null;
		
		// new一个实例对象
		AddTwoNumbers addTwoNumbers = new AddTwoNumbers();
		
		// 对输入链表进行逆序
		L1_head = addTwoNumbers.reverseListRecursion(L1_head);
		L2_head = addTwoNumbers.reverseListRecursion(L2_head);
		
		// 对输入链表再次进行逆序
		L1_head = addTwoNumbers.reverseList(L1_head);
		L2_head = addTwoNumbers.reverseList(L2_head);
		
		ListNode result = addTwoNumbers.addTwoNumbers(L1_head,L2_head);
		
		ArrayList<Integer> ids = new ArrayList<Integer>();
		while(result != null){
			ids.add(result.val);
			result = result.next;
		}
		//Collections.reverse(ids);
		System.out.println(ids);
	}
	
	//递归思想,可以从最后还剩两个节点的链表为例进行理解
	public ListNode reverseListRecursion(ListNode head){
		ListNode newHead;
		if(head==null||head.next==null ){
			return head;
		}
		//head.next 指向当前需逆序子链表的头节点,指向逆序后的尾节点
		newHead=reverseListRecursion(head.next); 
		//head.next 代表指向新链表的尾,将它的 next 置为 head,就是将 head 加到最后作为真正的尾
		head.next.next=head; 
		//之前的head现在变成了逆序链表真正的尾,其next指向null
		head.next=null;
		
		return newHead;
	}

	//迭代思想
	public ListNode reverseList(ListNode head){
		if (head==null){return null;}
		ListNode pre = null;
		ListNode next = null;
		while(head!=null){
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		return pre;
	}
	
	//两个链表的相加
	public ListNode addTwoNumbers(ListNode L1,ListNode L2){
		// 保存结果链表的头,头不赋值,以免后期做判断
		ListNode dummyHead = new ListNode(0);
		ListNode p = L1, q = L2, curr = dummyHead;
		int carray = 0;
		while(p!=null || q!=null){
			int x = (p!=null) ? p.val:0;
			int y = (q!=null) ? q.val:0;
			// 逐次相加并加上相应的进位
			int sum = x + y + carray;
			// 进位最大为1 9+9=18
			carray = sum/10;
			curr.next = new ListNode(sum%10);
			curr = curr.next;
			if (p!=null){p = p.next;}
			if (q!=null){q = q.next;}
		}
		
		//判断最后一位数,是否发生进位
		if (carray > 0){
			curr.next = new ListNode(carray);
			// 始终保证curr指向最后一个节点
			curr = curr.next;
		}
		// 最后一个节点的next指向null
		curr.next = null;
		// 之所以next,是因为链表头不存数据
		return dummyHead.next;
	}
}

本文地址:https://blog.csdn.net/qq_24964575/article/details/110941756

相关标签: LeetCode Java