Skip to content

Commit cccceaf

Browse files
committed
update algorithm
1 parent 5e4c25f commit cccceaf

3 files changed

Lines changed: 146 additions & 0 deletions

File tree

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package easy.array;
2+
3+
import java.util.Arrays;
4+
import java.util.LinkedList;
5+
import java.util.List;
6+
7+
8+
/**
9+
* 题目: 给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
10+
* 注意:答案中不可以包含重复的三元组。
11+
*
12+
* 实例: 给定数组 nums = [-1, 0, 1, 2, -1, -4],
13+
* 满足要求的三元组集合为:
14+
* [
15+
* [-1, 0, 1],
16+
* [-1, -1, 2]
17+
* ]
18+
*
19+
*
20+
* 思路:1、将数字从大到小排好序
21+
* 2、然后设置两个游标(left,right),只要满足 0-第三个数 == nums[left]-nums[right],
22+
* 所以设置 sum=0-第三个数,只要找满足 nums[left]-nums[right] ==sum 即可。
23+
* 3、一个从左往右找,一个从右往左找
24+
* 4、如果两数之和大于sun,那么说明要找的数字更小,就把右边的游标往左移
25+
* 反之,左边的往右移
26+
*/
27+
class _15_3nums {
28+
29+
public List<List<Integer>> threeSum(int[] nums) {
30+
if(nums.length <3 || nums == null)
31+
return new LinkedList();
32+
Arrays.sort(nums);
33+
List<List<Integer>> list = new LinkedList<>();
34+
for(int i=0;i<nums.length-1;i++){
35+
// 避免添加相同的list
36+
if(i==0 || (i>0 &&nums[i]!=nums[i-1])){
37+
int left = i+1,right=nums.length-1,sum = 0-nums[i];
38+
while(left<right){
39+
if(nums[left]+nums[right] == sum){
40+
// 添加进列表
41+
list.add(Arrays.asList(nums[left],nums[right],nums[i]));
42+
// 避免添加相同的list
43+
while(left<right && nums[left]==nums[left+1]) left++;
44+
while(left<right && nums[right]==nums[right-1]) right--;
45+
left++;
46+
right--;
47+
48+
//说明要找的数更大
49+
}else if(nums[left]+nums[right]<sum)
50+
left++;
51+
else
52+
//说明要找的数更小
53+
right--;
54+
}
55+
56+
}
57+
}
58+
return list;
59+
60+
}
61+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package easy.array;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* description:Given an array of integers, return indices of the two numbers such that they add up to a specific target.
8+
* You may assume that each input would have exactly one solution, and you may not use the same element twice.
9+
* 给你一个数组,返回数组两个元素相加等于目标值的元素的下标,返回其中一组解即可。同一个元素不能用两次;
10+
*
11+
* 如{1,2,5,6,7,2} 目标值 11
12+
* 返回{2,3}
13+
* solution: 利用HashMap存储元素以及下标,遍历元素,利用hash表,直接锁定另外一个符合条件的下标
14+
*/
15+
class _1_twoSum {
16+
public static int[] twoSum(int[] nums, int target) {
17+
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
18+
for(int i=0; i<nums.length; i++){
19+
map.put(nums[i],i);
20+
}
21+
for(int i=0; i<nums.length; i++){
22+
if(map.containsKey(target - nums[i])
23+
&& map.get(target -nums[i]) != i){
24+
return new int[]{i, map.get((target-nums[i]))};
25+
}
26+
27+
}
28+
return null;
29+
}
30+
31+
public static void main(String[] args) {
32+
int[] a = {1,2,5,6};
33+
34+
twoSum(a,7);
35+
}
36+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package easy.linkedList;
2+
3+
/**
4+
* 描述:Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
5+
*
6+
* Given linked list -- head = [4,5,1,9], which looks like following:
7+
*
8+
* 请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。
9+
*
10+
* 现有一个链表 -- head = [4,5,1,9],它可以表示为:
11+
*
12+
* Input: head = [4,5,1,9], node = 5
13+
* Output: [4,1,9]
14+
* Explanation: You are given the second node with value 5,
15+
* the linked list should become 4 -> 1 -> 9 after calling your function.
16+
*
17+
*
18+
*
19+
* 提示:你已经进入了那个节点,并不是从头开始。
20+
* 链表至少包含两个节点。
21+
* 链表中所有节点的值都是唯一的。
22+
* 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
23+
* 不要从你的函数中返回任何结果。
24+
*
25+
* 请一定要注意描述和提示!!!!
26+
*
27+
*
28+
* 解法: 直接用后面的覆盖前面的,然后将指针修改下就行
29+
*/
30+
31+
public class _237_deleteNodeInLinkedList {
32+
static class ListNode{
33+
int val;
34+
ListNode next;
35+
36+
public ListNode() {
37+
}
38+
}
39+
40+
public static void main(String[] args) {
41+
42+
}
43+
public static void deleteNode(ListNode node){
44+
// 覆盖
45+
node.val = node.next.val;
46+
// 修改指针
47+
node.next = node.next.next;
48+
}
49+
}

0 commit comments

Comments
 (0)