2019.7.15～2019.7.19 leetcode刷题总结

<>2019.7.15～2019.7.19 leetcode刷题总结

1 两数之和(#2)

题目描述：
给定一个整数数组 nums 和一个目标值
target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

解题思路：
常规的暴力遍历的思路就不考虑了，时间复杂度为O(n^2),这个题比较优的解题思路是使用哈希表，时间复杂度为O(n),
首先建立一个哈希表，然后遍历数组，设当前值为temp, 当哈希表中不存在target-temp的key值时，将当前值存入哈希表，如果存在，则返回结果。

代码：
public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new
HashMap<>(); for (int i = 0; i < nums.length; i++) { int temp = target -
nums[i]; if (map.containsKey(temp)) { return new int[]{map.get(temp), i}; }
else { map.put(nums[i], i); } } return new int[2]; }
2 无重复字符的最长子串（#3）

题目描述：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

解题思路：
还没有理解透，后续补充

代码：
public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); for (int j = 0, i = 0; j < n;
j++) { if (map.containsKey(s.charAt(j))) { i = Math.max(map.get(s.charAt(j)),
i); } ans = Math.max(ans, j - i + 1); map.put(s.charAt(j), j + 1); } return
ans; }
3 寻找两个有序数组的中位数（#4）

题目描述：
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

解题思路：
常规的方法就是将两个数组合并，然后求中位数即可，但是这种解法时间复杂度为O(m+n),空间复杂度也为O(m+n),不满足题目的要求，因而考虑二分的思想，

代码：
public double findMedianSortedArrays(int[] A, int[] B) { int m = A.length; int
n = B.length; if (m > n) { // to ensure m<=n int[] temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp; } int iMin = 0, iMax = m, halfLen = (m + n + 1) /
2; while (iMin <= iMax) { int i = (iMin + iMax) / 2; int j = halfLen - i; if (i
< iMax && B[j-1] > A[i]){ iMin = i + 1; // i is too small } else if (i > iMin
&& A[i-1] > B[j]) { iMax = i - 1; // i is too big } else { // i is perfect int
maxLeft = 0; if (i == 0) { maxLeft = B[j-1]; } else if (j == 0) { maxLeft =
A[i-1]; } else { maxLeft = Math.max(A[i-1], B[j-1]); } if ( (m + n) % 2 == 1 )
{ return maxLeft; } int minRight = 0; if (i == m) { minRight = B[j]; } else if
(j == n) { minRight = A[i]; } else { minRight = Math.min(B[j], A[i]); } return
(maxLeft + minRight) / 2.0; } } return 0.0; }
4 回文数（#9）

题目描述：
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

解题思路：

常规思路是申请两个指针，一个指向数字的头部，一个指向尾部，依次比较头尾，相同则头尾指针一起向中间移动一位，但是这种算法需要将数字转成字符串或者数组，需要额外的空间。另外一种解法是将数字的后半部分逆序，如果与前半部分相等，则改数字是回文数。

代码：
public boolean isPalindrome(int x) { // x为负数或者最后一位为0，则肯定不是回文数 if (x < 0 || (x
!= 0 && x % 10 == 0)) { return false; } int reverse = 0; while (x > reverse) {
reverse = reverse * 10 + x % 10; x /= 10; } // 区分x的长度为奇偶的情况 return x == reverse
|| x == reverse / 10; }
5 合并两个有序链表（#21）

题目描述：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路：
经典题目，比较简单

代码：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode head = new
ListNode(0); ListNode temp = head; while (l1 != null && l2 != null) { if
(l1.val < l2.val) { head.next = l1; l1 = l1.next; head = head.next; } else {
head.next = l2; l2 = l2.next; head = head.next; } } if (l1 != null) { head.next
= l1; } if (l2 != null) { head.next = l2; } return temp.next; }
6 删除排序数组中的重复项（#26）

题目描述：
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用
O(1) 额外空间的条件下完成。

解题思路：

由于不能有额外空间，因此利用两个指针，一个j指向当前元素，一个i指向前一个元素，如果当前元素等于前一个元素，则j+1,如果当前元素不等于前一个元素，则i+1,并把当前元素赋值给i+1位置的元素。

代码：
public int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int
i = 0; for (int j = 1; j < nums.length; j++) { if (nums[j] != nums[i]) { i++;
nums[i] = nums[j]; } } return i + 1; }
7 移除元素（#27）

题目描述：
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解题思路：
与上一题的解法基本相同

代码：
public int removeElement(int[] nums, int val) { int i = 0; for (int j = 0; j <
nums.length; j++) { if (nums[j] != val) { nums[i] = nums[j]; i++; } } return i;
}
8 删除链表的倒数第N个节点（#19）

题目描述：
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

解题思路：
经典思路，设定两个指针p1，p2，当p2从头开始走了n步后，p1开始跟p2一起走，当p2走到终点时，p1则处于倒数第n个位置。

代码
public ListNode removeNthFromEnd(ListNode head, int n) { if (head.next ==
null) { return null; } ListNode temp = head; ListNode lastN = head; ListNode
res = lastN; int i = 1; while (temp != null) { temp = temp.next; if (i <= n +
1) { i++; } else { lastN = lastN.next; } } if (i == n + 1) { return head.next;
} if (lastN.next != null) { lastN.next = lastN.next.next; } else { lastN.next =
null; } return res; }
9 爬楼梯（#70）

题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

解题思路：

经典动态规划问题，要到达第n阶楼梯只有两种可能，从n-1阶跳1步到n阶，或者从n-2阶跳2步到n阶，则爬到第n阶楼梯的方法数等于爬到第n-1阶的方法数加上爬到第n-2阶的方法数，即f(n)=f(n-1)+f(n-2)，同时考虑初始值，即n=1时，f(1)
= 1, n=2时，f(2) = 2。是不是很像高中时候做的数学题目， 哈哈，编程就是数学。

代码：
public int climbStairs(int n) { if (n == 1) { return 1; } if (n == 2) { return
2; } int a = 1; int b = 2; int c = 0; for (int i = 3; i <= n; i++) { c = a + b;
a = b; b = c; } return c; }
10 合并两个有序数组（#88）

题目描述：
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

解题思路：
与上面的合并有序数组的思路类似

代码：
public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1; int
j = n - 1; int q = m + n - 1; while (i >= 0 && j >= 0) { nums1[q--] = nums1[i]
> nums2[j] ? nums1[i--] : nums2[j--]; } while (i >= 0) { nums1[q--] =
nums1[i--]; } while (j >= 0) { nums1[q--] = nums2[j--]; } }
11 从中序与后序遍历序列构造二叉树（#106）

题目描述：
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。

解题思路：

由于后序遍历序列的最后一个数是二叉树的根结点的值，同时，中序遍历中根结点处于中间位置，且其左部分为根结点的左子树，右部分为根结点的右子树，而后序序列中除了最后一个根结点外，其左部分为左子树，右部分为右子树，然后每部分递归，便可以构造出二叉树。

代码：
public TreeNode buildTree(int[] inorder, int[] postorder) { return
build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1); }
public TreeNode build(int[] in, int inBegin, int inEnd, int[] post, int
postBegin, int postEnd) { if (inBegin > inEnd || postBegin > postEnd) { return
null; } int headVal = post[postEnd]; TreeNode head = new TreeNode(headVal); for
(int i = inBegin; i <= inEnd; i++) { if (in[i] == headVal) { head.left =
build(in, inBegin, i - 1, post, postBegin, i - inBegin + postBegin - 1);
head.right = build(in, i + 1, inEnd, post, i - inBegin + postBegin, postEnd -
1); } } return head; }
12 有效的字母异位词（#242）

题目描述：
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
说明:
你可以假设字符串只包含小写字母。

解题思路：

由题意可知，可以用哈希表来解决，由于假设都是小写字母，因此只需要一个长度为26的字符数组，同时，由于两个字符串的长度相等（不相等则不可能是异位词），则在遍历时，字符串s中的字符在数组的对应位置+1，字符串t中的字符在数组的对应位置-1。
遍历完后，如果两个t是s的字母异位词，那么数组的每一个位置的值都为0，否则就不是异位词。

代码：
public boolean isAnagram(String s, String t) { if (s.length() != t.length()) {
return false; } int[] counter = new int[26]; for (int i = 0; i < s.length();
i++) { counter[s.charAt(i) - 'a']++; counter[t.charAt(i) - 'a']--; } for (int a
: counter) { if (a != 0) { return false; } } return true; }
13 3的幂(326#)

题目描述：
给定一个整数，写一个函数来判断它是否是 3 的幂次方。

解题思路：
比较简单，循环对3求余即可。

代码：
public boolean isPowerOfThree(int n) { if (n < 1) { return false; } while (n %
3 == 0) { n /= 3; } return n == 1; }
14 奇偶链表（#328）

题目描述：
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

解题思路：
新建两个链表，一个存奇数节点，一个存偶数节点，最后将偶数节点连在奇数节点后面即可。

代码：
public ListNode oddEvenList(ListNode head) { ListNode even = new ListNode(0);
ListNode evenTemp = even; ListNode odd = new ListNode(0); ListNode oddTemp =
odd; int i = 1; while (head != null) { if (i % 2 == 0) { even.next = head; even
= even.next; } else { odd.next = head; odd = odd.next; } head = head.next; i++;
} odd.next = evenTemp.next; even.next = null; return oddTemp.next; }
15 两数相加（#2）

题目描述：
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

解题思路：
注意进位的控制

代码：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead =
new ListNode(0); ListNode p = l1, q = l2, curr = dummyHead; int carry = 0;
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; } }

• « 上一篇：86 怎样编写一个程序，把一个有序整数数组放到二叉树中
• » 下一篇：怎样编写一个程序，把一个有序整数数组放到二叉树中？