leetcode算法题学习Java版（2）
283.Move Zeros(移动零)
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
class Solution {
public void moveZeroes(int[] nums) {
int k = 0;
for(int i = 0;i<nums.length;i++){
if(nums[i]!=0){
if(i!=k){
int temp = nums[k];
nums[k] = nums[i];
nums[i] = temp;
}
k++;
}
}
}
}
75.Sort Colors（颜色分类）
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
- 一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 - 你能想出一个仅使用常数空间的一趟扫描算法吗？
解题思路，本题共三个元素，非常适合三路快排的方法，并且仅需扫描数组一遍即可完成排序
class Solution {
public void sortColors(int[] nums) {
int zero = -1; // nums[0...zero]==0
int two = nums.length; //nums[two...n-1]==2
for (int i = 0; i < two;) {
if(nums[i]==0){
int temp = nums[++zero];
nums[zero] = nums[i];
nums[i++] = temp;
}else if(nums[i]==1){
i++;
}else{
assert nums[i]==2;
int temp = nums[--two];
nums[two] = nums[i];
nums[i] = temp;
}
}
}
}
88.Merged sorted Array（合并有序数组）
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
解题思路：这道题解决很简单，但是最大效率的算法却也比较难想，很巧妙，暴力解法就是把两个数组合并，然后快排。但是参照了leetcode上别人的代码，效率更高，思路就是不断比较二者的最大值，把最大值放在nums1数组的最后，知道排序成功。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int count = m + n - 1;
m--;
n--;
while (m != -1 && n != -1) {
nums1[count--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
}
while (n != -1) {
nums1[count--] = nums2[n--];
}
}
}
215.Kth Largest Element in an Array（数组中第K个最大的元素）
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
这道题很有趣，他的解法非常多，我也是在这道题感受到了自己与大佬之间的差距，就算用同一种解法，别人的代码也比我写的优雅的多。令人哭笑不得的是，自己写了半天的算法，其实运行下来比别人两行代码（Array.sort，调用jdk内置的函数）就搞定了还慢了很多倍。
解题思路：这道题用简单暴力的解法是非常容易的，同样是先对数组进行排序，最简单的办法是用jdk内置的Array.sort进行排序，然后从后往前取第k个元素，这种解法既简单，又由于jdk内置的快排效率非常高，在leetcode上这种解法只用了4ms，排名第二。当然更聪明的解法很多，例如，使用快排（分治算法），在快排的每一趟排完后，如果要找的k较大，则只对对应的一半继续进行快排，直到找到结果。还有使用堆的办法。
class Solution {
public int findKthLargest(int[] nums, int k) {
Queue<Integer> queue = new PriorityQueue<Integer>();
for (int i = 0; i < nums.length; i++) {
if (i < k) {
queue.add(nums[i]);
} else if (queue.peek() < nums[i]) {
queue.remove();
queue.add(nums[i]);
}
}
return queue.peek();
}
}
class Solution {
public int findKthLargest(int[] nums, int k) {
int left = 0, right = nums.length - 1;
while (true){
int pos = partition(nums, left, right);
if(k - 1 == pos) return nums[pos];
else if(pos > k - 1) right = pos - 1;
else left = pos + 1;
}
}
public int partition(int[] nums, int left, int right){
int pivot = nums[left], l = left +1, r = right;
while (l <= r){
if(nums[l] < pivot && nums[r] > pivot)
swap(nums, l, r);
if (nums[r] <= pivot) r--;
if (nums[l] >= pivot) l++;
}
swap(nums, left, r);
return r;
}
public void swap(int nums[], int left, int right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
Two Sum II（两数之和）
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
解题思路：这道题同样有多种思路，暴力解法是两次遍历该数组，找到相加等于target的索引，这种解法的时间复杂度是O(n^2)。利用二分法的思想来解这道题，时间复杂度是O(nlogn)。而利用对撞指针来解这道题，时间复杂度只有O（n），以下是对撞指针的解法。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int i = 0,j = numbers.length-1;
while(i<j){
if(numbers[i]+numbers[j]==target){
break;
}
if(numbers[i]+numbers[j]>target){
j--;
}
if(numbers[i]+numbers[j]<target){
i++;
}
}
return new int[]{++i,++j};
}
}
209.Minimum Size Subarray Sum（最小子数组）
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
解题思路：该题使用滑动窗口法解决只需要O（n）的时间复杂度
public class MSSubarraySum {
public int minSubArrayLen(int s, int[] nums) {
int i = 0, j = -1;
int sum = 0;
int result = nums.length+1;
while(i<nums.length){
if(j<nums.length-1&&sum<s){
sum+=nums[++j];
}else{
sum-=nums[i++];
}
if(sum>=s)
result = Math.min(result,j-i+1);
}
if(result == nums.length+1){
result = 0;
}
return result;
}
}
3.Longest Substring Without Repeating Characters（无重复字符的最小子串）
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc"，其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b"，其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke"，其长度为 3。
请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。
解题思路：这道题同样是使用滑动窗口的思想去解是最佳的。该题需要记录每个字符出现的频率，因此初始化一个长度为256的freq数组，根据字符的ASCII码来每个字符出现的频率。根据频率来进行窗口的滑动。
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] freq = new int[256];
for (int f = 0; f < freq.length; f++) {
freq[f] = 0;
}
int i = 0, j = -1;
int result = 0;
while (i < s.length()) {
if (j < s.length() - 1 && freq[s.charAt(j + 1)] == 0) {
freq[s.charAt(++j)]++;
}else{
freq[s.charAt(i++)]--;
}
result = Math.max(result, j - i + 1);
}
return result;
}
}
Minimum Window Substring（最小覆盖子串）
给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
解题思路：这道题我依然是使用滑动窗口的思想去解的，时间复杂度为O（2st），解题耗时较长，主要原因是每次都要遍历一遍结果集去判断结果是否正确，可以去参考leetcode 该题更好的解法。
class Solution {
public String minWindow(String s, String t) {
HashMap<Integer,Integer> target = new HashMap<>();
for(int i =0;i<t.length();i++){
if(target.get((int)t.charAt(i))==null){
target.put((int) t.charAt(i),1);
}else{
int temp = target.get((int)t.charAt(i));
target.put((int) t.charAt(i),temp+1);
}
}
int freq[] = new int[256];
for (int i = 0; i < freq.length; i++) freq[i] = 0;
int i = 0, j = -1;
int length = Integer.MAX_VALUE;
String result = "";
while(i<s.length()){
if(j<s.length()-1&&!hasFound(freq,target)){
freq[s.charAt(++j)]++;
}else{
freq[s.charAt(i++)]--;
}
if(hasFound(freq,target)){
if(length>j-i+1){
length = j-i+1;
result = s.substring(i,j+1);
}
}
}
return result;
}
public static boolean hasFound(int[] arr1,HashMap<Integer,Integer> arr2){
// for(int i =0;i<arr2.length;i++){
// if(arr1[arr2[i]]<1)
// return false;
// }
Iterator iter = arr2.entrySet().iterator();
while(iter.hasNext()){
Map.Entry<Integer,Integer> entry = (Map.Entry) iter.next();
if(arr1[entry.getKey()]<entry.getValue()){
return false;
}
}
return true;
}
}
451.Sort Characters By Frequency(根据字符出现频率排序)
示例 1:
输入:
"tree"
输出:
"eert"
解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
解题思路：这里我是用HashMap来解的，不过最后用了比较笨的办法来按顺序拼凑字符串。是通过类似选择排序的办法，每次比较map里的所有value值，将最大的值拿出来放在最前面。Leetcode上有更好的方法可以借鉴。
class Solution {
public String frequencySort(String s) {
Map<Character,Integer> map = new HashMap<>();
for(int i =0;i<s.length();i++){
map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
}
StringBuffer result = new StringBuffer();
int temp = -1;
char tempKey=' ';
int i = 0;
while(i<s.length()){
for (Map.Entry<Character,Integer> entry:map.entrySet()) {
if(temp<entry.getValue()){
tempKey = entry.getKey();
temp = entry.getValue();
}
}
map.remove(tempKey);
while(temp>0){
result.append(tempKey);
i++;
temp--;
}
}
return result.toString();
}
}
15.3Sum（三数之和）
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解题思路：我用的是对撞指针的方式，遍历数组的过程中，对当前遍历的索引之后的数，采用对撞指针的方式，找到和等于0-nums【i】的两个数。我的代码略有瑕疵导致速度较慢，以下为leetcode上解题思路与我相同，但是做了细节优化的代码
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int len=nums.length;
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for(int i=0;i<len;i++){
if(nums[i]>0)break; //简化，如果>0则说明该三数之和不可能为0
if(i>0&&nums[i]==nums[i-1])continue; //去重
int target=0-nums[i];
int l=i+1,r=len-1; //此处必须对i后面的数字进行筛选，不能重复
while(l<r){
List<Integer> list=new ArrayList();
if(nums[l]+nums[r]==target){
list.add(nums[i]); list.add(nums[l]); list.add(nums[r]);
res.add(list);
while(r>l&&nums[l+1]==nums[l])l++; //这个地方改成l-1只会出现一个结果了
while(r>l&&nums[r]==nums[r-1])r--;
l++;r--;
}else if(nums[l]+nums[r]>target)r--;
else l++;
}
}
return res;
}
}
454.4SumII（四数相加II）
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
例如:
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
解释:
两个元组如下:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
解题思路：暴力解法为遍历四个数组所有情况，时间复杂度为O(n^4 )。本题我使用了查找表的方法，将数组A和B的所有和的情况置入查找表中，遍历C和数组D即可得到结果，时间复杂度为O(n^2)
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
int result = 0;
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i<A.length;i++){
for(int j = 0;j<B.length;j++){
map.put(A[i]+B[j],map.getOrDefault(A[i]+B[j],0)+1);
}
}
for(int i = 0;i<C.length;i++){
for(int j = 0;j<D.length;j++){
if(map.containsKey(0-C[i]-D[j])){
result+=map.get(0-C[i]-D[j]);
}
}
}
return result;
}
206. Reverse Linked List 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
解题思路：对于链表题来说，一般不能直接操作链表节点的值，而是通过操作指针来改变链表。例如，扫描一遍链表，将值压入栈中，再第二次扫描链表，将值从栈中弹出，这种方式一般在面试的算法题中是不被允许的。因此，这道题我用了三个临时指针，只改变listNode的next指针的方向来改变链表。
public class ReverseLinkedList {
public ListNode reverseList(ListNode head) {
if(head == null) return head;
ListNode pre = null, cur = head, next = head.next;
while (cur != null){
cur.next = pre;
pre = cur;
cur = next;
if(next!=null){
next = next.next;
}
}
return pre;
}
}
92. Reverse Linked List II 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
这道题个人感觉还是挺难的，因为要处理的特殊情况较多，又不能直接更改节点的值，而是要通过指针来实现反转链表。这里还是以leetcode上大神写的更优美的代码为例吧
public ListNode reverseBetween_1(ListNode head, int m, int n) {
if (head == null || m < 1 || m > n) return null;
ListNode head1 = head;
ListNode preTail = null;//需要逆置节点的前驱节点
//第一步：前进至第m节点，即行走m-1步;注意考虑m为1的情况，此时preTail=null
int i = 1;
while(head1 != null && i++ < m){
preTail = head1;
head1 = head1.next;
}
//第二步：反转m->n节点
if(head1 == null) return head;//head1为null，不需要后翻转了
ListNode preNode = null;
ListNode reverseListPreHead = head1;
ListNode nextNode;
while (head1 != null && m++ <= n) {
nextNode = head1.next;
head1.next = preNode;
preNode = head1;
head1 = nextNode;
}
//第三步：反转链表的头尾处理
reverseListPreHead.next = head1;//处理尾巴
if (preTail != null) {//处理头部
preTail.next = preNode;
return head;
}else{
return preNode;//若preTail为null,返回翻转链表段的最后一个节点
}
}
Remove Duplicates from Sorted List 删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
解题思路：这道题题意我理解错了，不知道是不是题目表达的问题，让我误以为要删除所有的不管是否相邻的具有重复值的节点。但看了leetcode上其他人的代码，都只是删除相邻的重复的节点。
if(head ==null) return null;
if(head.next == null) return head;
Set<Integer> set = new HashSet<>();
ListNode temp = new ListNode(-1);
temp.next = head;
while (temp!=null&&temp.next!=null){
ListNode next = temp.next;
if(set.contains(next.val))
temp.next = temp.next.next;
else{
set.add(next.val);
temp = temp.next;
}
}
return head;
86.Partition List 分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
解题思路：感觉链表的题都好难啊……但是看了别人的解法有感觉很简单，这道题的思路就是把小的和大的分别依次链起来，最后整合。
public ListNode partition(ListNode head, int x){
ListNode head1 = new ListNode(0);
ListNode head2 = new ListNode(0);
ListNode phead1 = head1;
ListNode phead2 = head2;
ListNode temp = head;
while (temp!=null){
if(temp.val<x){
phead1.next = temp;
temp = temp.next;
phead1 = phead1.next;
phead1.next = null;
}else{
phead2.next = temp;
temp = temp.next;
phead2 = phead2.next;
phead2.next = null;
}
}
phead1.next = head2.next;
head = head1.next;
return head;
}
328. Odd Even Linked List 奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:
应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
解题思路：这道题和上一道题的解题思路基本一致。将奇偶数节点分别链起来，最后再整合即可。需要注意的是需要记录奇偶节点的首节点的位置，方便整合。
public ListNode oddEvenList(ListNode head) {
ListNode temp = head;
ListNode evenNode = new ListNode(-1);
ListNode oddNode = new ListNode(-1);
ListNode pEvenNode = evenNode;
ListNode pfirOddNode = oddNode;
int i = 1;
while (temp != null){
if(i%2==0){
evenNode.next = temp;
evenNode = evenNode.next;
temp = temp.next;
evenNode.next = null;
}else {
oddNode.next = temp;
oddNode = oddNode.next;
temp = temp.next;
oddNode.next = null;
}
i++;
}
oddNode.next = pEvenNode.next;
head = pfirOddNode.next;
return head;
}
2.Add Two Numbers 两数相加
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解题思路：不得不说看别人的代码都赏心悦目，相比之下自己的代码不知道是哪个弱智写的。这道题同样不难，两两相加，遇到某个数字位数不够了补0就可以了。这里还是以leetcode上大佬写的代码为例
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode next = new ListNode(0);
ListNode result = next;
int add = 0;
while (l1 != null || l2 != null) {
int l1val = (l1 != null) ? l1.val : 0;
int l2val = (l2 != null) ? l2.val : 0;
int value = l1val + l2val + add;
add = value / 10;
next.next = new ListNode(value % 10);
next = next.next;
l1 = (l1 != null) ? l1.next : null;
l2 = (l2 != null) ? l2.next : null;
}
if (add > 0) {
next.next = new ListNode(add);
}
return result.next;
}
203. Remove Linked List Elements 移除链表元素
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
解题思路： 利用虚拟头结点，删除所有重复元素即可。我的代码有些小瑕疵，应该释放删除掉节点的内存空间。
public ListNode removeElements(ListNode head, int val) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode cur = dummyNode;
while (cur.next!=null){
if(cur.next.val==val)
cur.next = cur.next.next;
else
cur = cur.next;
}
return dummyNode.next;
}
82. Remove Duplicates from Sorted List II 删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
解题思路：总感觉链表题都挺有难度的，可能是平常用的少的原因吧。这道题其实思路也很简单，就是遇到相同节点，就循环往下找下一个不同的节点，并链接。
public ListNode deleteDuplicates(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode prev = dummyHead;
while (prev.next != null) {
ListNode cur = prev.next;
if (cur.next == null || cur.val != cur.next.val) {
prev = prev.next;
continue;
}
while (cur.next != null && cur.next.val == cur.val) {
cur.next = cur.next.next;
}
prev.next = cur.next;
}
return dummyHead.next;
}
