目的

扎实基本功

一周最少三道题

把思路和代码记录下来

Start

1. Two Sum

Q：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

**思路一：**遍历每个数据，查找是否有和这个target-nums[i]相等的数据。

code：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[j]==target-nums[i]){
                    return new int[] {i,j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");

    }
}

时间复杂度:O(n^2)

空间复杂度：O(1)

**思路二：**哈希表，牺牲空间换取速度，先将key与值绑定，然后进行检查。

code：

class Solution{
public int[] twoSum(int[] nums, int target) {
    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];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
	}
}

时间复杂度：O(n)

空间复杂度：O(n)

905.Sort Array By Parity

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

1 <= A.length <= 5000
0 <= A[i] <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-array-by-parity
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

code：

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int a[]=new int[A.length];
        int j=0;
        for(int i=0;i<A.length;i++){
            if(A[i]%2==0){
                a[j++]=A[i];
            }
        }
        for(int k=0;k<A.length;k++){
            if(A[k]%2==1){
                a[j++]=A[k];
            }
        }
        
        return a;
    }
}

814. Binary Tree Pruning

We are given the head node root of a binary tree, where additionally every node’s value is either a 0 or a 1.

Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)

Example 1:
Input: [1,null,0,0,1]
Output: [1,null,0,null,1]

Explanation:
Only the red nodes satisfy the property “every subtree not containing a 1”.
The diagram on the right represents the answer.

Example 2:
Input: [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

Example 3:
Input: [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]

Note:

The binary tree will have at most 100 nodes.
The value of each node will only be 0 or 1.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-pruning
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

code：

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if(root==null)
            return null;
        root.right=pruneTree(root.right);
        root.left=pruneTree(root.left);
        if(root.val==0&&root.left==null&&root.right==null)
            return null;
        return root;      
    }
}

48. Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:

Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-image
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

code:

class Solution {
    public void rotate(int[][] matrix) {
        int l=matrix.length;
        for(int i=0;i<l;i++)
            for(int j=i;j<l;j++){
                int a=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=a;
            }
        for (int i = 0; i < l; i++){
      for (int j = 0; j < l / 2; j++) {
        int b = matrix[i][j];
        matrix[i][j] = matrix[i][l - j - 1];
        matrix[i][l - j - 1] = b;
      }
        } 
    }
}

Minimum Number of Refueling Stops

A car travels from a starting position to a destination which is target miles east of the starting position.

Along the way, there are gas stations. Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.

When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

What is the least number of refueling stops the car must make in order to reach its destination? If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Example 1:

Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.
Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can’t reach the target (or even the first gas station).
Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation:
We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas. We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.

Note:

1 <= target, startFuel, stations[i][1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < … < stations[stations.length-1][0] < target

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-number-of-refueling-stops
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

现在只有个思路，代码等过段时间尝试实现一下。

首先，题目规定了跑1英里消耗1升油，那就代表初始有多少油就能最大跑多少英里，可以完全把第二个数据（油量）当作现在汽车可以最大跑的距离，然后找小于等于这个数的加油站，先从油量开始找，然后先加上加油站的油试试能不能到达目的地，不能的话递归往后找。后来我感觉这样可能不太好，万一有在前面的加油站加一次直接可以到目的地呢，所以我想先找出油足够多到达目的地的加油站，然后比较距离.

停更刷题。