Problem:

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.

Intuition:

这个题目总体思路非常直观。就是模拟小学的笔算来做加法。其中解题时要注意两个list长度不一样的情况（比如两位数+3位数），这种情况下直接在位数较短的那一方（先访问到null的那一方）填0就行了。

还有一个要注意的只是对list中的null如何处理。因为处理的表达式较容易，用？：表达式比if else要更方便。

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode dummyHead = new ListNode(0);
	ListNode p = l1, q = l2, curr = dummyHead;
	int carry = 0;
	//这里对于两个list长度不一致的处理方式值得学习
	while (p != null || q != null) {
		int x = (p != null) ? p.val : 0;
		int y = (q != null) ? q.val : 0;


		int sum = carry + x + y;
		carry = sum / 10;
		curr.next = new ListNode(sum % 10);
		curr = curr.next;
		if (p != null) p = p.next;
		if (q != null) q = q.next;
	}
	if (carry > 0) {
		curr.next = new ListNode(carry);
	}
	return dummyHead.next;

}

Problem:

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].

Intuition:

首先明确题目需要我们做的是返回一个和所对应的两个加数在数组中的下标。直接两层遍历当然很容易，但是时间复杂度会达到O(n2),那么接下来我们就开始用空间换时间。

我们肯定要把整个数组进行一次遍历，那么在遍历的过程中我们只要能够找到和减去当前数组下标元素的差所对应在数组中的下标整个题目就完成了。

接下来的任务就是进行高效率的查找。自然而然就会想到查找时间复杂度为O(1)的hashmap.然后我们把数组中的所有元素放到Hashmap里面，key表示为数组中元素的值，这样遍历的时候一旦得到和与当前元素的差，直接用差作为hashmap的key进行查找即可直接返回数组下标。

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static int[] twoSumSolution(int[] nums, int target) {
  	/*
       * We reduce the look up time from O(n)O(n) to O(1) by
       * trading space for speed. A hash table is built exactly
       * for this purpose, it supports fast look up in near constant time.
       * look up in hash table should be amortized O(1).
       */

      //节省时间的技巧是利用hashmap搜索复杂度为(1)的特点，用hashmap来搜素，而不是
      //手动遍历（O(n)）
      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 complement = target - nums[i];
          //&&map.get(complement)!=i也很关键，这样确保数组中的同一个元素不会被重复使用
          if (map.containsKey(complement) && map.get(complement) != i) {
              return new int[] { i, map.get(complement) };
          }
      }
      throw new IllegalArgumentException("No two sum solution");
  }

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment