Leetcode 01: t1. sum of two numbers; T1108. IP address invalidation; T344. Reverse string

T1: 1. Sum of two numbers （ Simple ）

Given an array of integers nums  And an integer target value target, Please find... In the array And is the target value the   Two   Integers , And return their array subscripts .

You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .

You can return the answers in any order .

Example 1：

 Input ：nums = [2,7,11,15], target = 9
 Output ：[0,1]
 explain ： because  nums[0] + nums[1] == 9 , return  [0, 1] 

Example 2：

 Input ：nums = [3,2,4], target = 6
 Output ：[1,2]

Example 3：

 Input ：nums = [3,3], target = 6
 Output ：[0,1]

Tips ：

2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
There will only be one valid answer

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/two-sum
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas

Finding sum directly can achieve target The number of , I can think of two pointers , Notice the right pointer in the second loop = Left pointer +1 Instead of being equal to 0

Or use Hash The table finds the corresponding value faster

solution 1: violence

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

Execution time ：0 ms, In all  Java  Defeated in submission **100.00%** Users of

Memory consumption ：38.6 MB, In all  Java  Defeated in submission **68.15%** Users of

Time complexity ：O(N^2), among  N Is the number of elements in the array . In the worst case, any two numbers in the array must be matched once .

Spatial complexity ：O(1).

class Solution {
    
    public int[] twoSum(int[] nums, int target) {
    
        int left =0;
        while(left<nums.length-1){
    
            for(int i = left+1; i < nums.length; ++i){
    
                if(nums[left]+nums[i]==target){
    
                    return new int[]{
    left, i};
                }
            }
            ++left;
        }
        return new int[0];
    }
}

solution 2: Hashtable

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer,Integer>();
        for(int i = 0;i<nums.length;++i){
            if(hashtable.containsKey(target-nums[i])){
                return new int[]{hashtable.get(target-nums[i]),i};
            }
            hashtable.put(nums[i],i);
        }
        return new int[0];
    }
}

Execution time ：0 ms, In all  Java  Defeated in submission **100.00%** Users of

Memory consumption ：38.5 MB, In all  Java  Defeated in submission **80.48%** Users of

Time complexity ：O(N), among N Is the number of elements in the array . For each element x, We can O(1) Looking for target - x.

Spatial complexity ：O(N)), among N Is the number of elements in the array . Mainly for the cost of hash table .

T2: 1108. IP Address invalidation （ Simple ）

Give you an effective IPv4 Address  address, Go back to this IP Invalid version of address .

The so-called invalidation  IP Address , In fact, it is to use  “[.]”  Instead of every “.”.

Example 1：

 Input ：address = "1.1.1.1"
 Output ："1[.]1[.]1[.]1"

Example 2：

 Input ：address = "255.100.50.0"
 Output ："255[.]100[.]50[.]0"

Tips ：

Given  address  Is an effective IPv4 Address

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/defanging-an-ip-address
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas

Direct replacement …

Or use StringBuilder

solution 1: replace

class Solution {
    public String defangIPaddr(String address) {
        return address.replace(".","[.]");
    }
}

Execution time ：0 ms, In all  Java  Defeated in submission **100.00%** Users of

Memory consumption ：36 MB, In all  Java  Defeated in submission **99.78%** Users of

solution 2: StringBuider

class Solution {
    
    public String defangIPaddr(String address) {
    
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < address.length(); ++i){
    
            if(address.charAt(i)=='.'){
    
                sb.append("[.]");
            }else{
    
                sb.append(address.charAt(i));
            }
        }
        return sb.toString();
    }
}

Execution time ：0 ms, In all  Java  Defeated in submission **100.00%** Users of

Memory consumption ：36.3 MB, In all  Java  Defeated in submission **87.23%** Users of

T3: 344. Reverse string （ Simple ）

Write a function , Its function is to invert the input string . Input string as character array  char[]  Given in the form of .

Do not allocate extra space to another array , You must ** In situ Modify input array **、 Use O(1) To solve this problem .

You can assume that all characters in an array are  ASCII  Printable characters in code table .

Example 1：

 Input ：["h","e","l","l","o"]
 Output ：["o","l","l","e","h"]

Example 2：

 Input ：["H","a","n","n","a","h"]
 Output ：["h","a","n","n","a","H"]

https://leetcode-cn.com/problems/reverse-string/

Ideas

It can be used temp In exchange for , It can also be exchanged with XOR , You can also use a = a+b, b = a-b, a = a-b

solution 1: Double pointer

class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length-1;
        while(left<=right){
            char temp = s[left];
            s[left] = s[right];
            s[right]= temp;
            left++;
            right--;
        }
    }
}

Execution time ：1 ms, In all  Java  Defeated in submission **100.00%** Users of

Memory consumption ：44.9 MB, In all  Java  Defeated in submission **83.80%** Users of

Time complexity ：O(N), among N Is the length of the character array . All executed N/2 Exchange of times .

Spatial complexity ：O(1). Only constant space is used to store several variables .

solution 2: Exclusive or

class Solution {
    
    public void reverseString(char[] s) {
    
        int left = 0, right = s.length-1;
        while(left<right){
    
            s[left] ^= s[right];
            s[right] ^= s[left];
            s[left] ^= s[right];
            left++;
            right--;
        }
    }
}

Execution time ：1 ms, In all  Java  Defeated in submission **100.00%** Users of

Memory consumption ：45.2 MB, In all  Java  Defeated in submission **34.69%** Users of