印象博客印象博客

leetcode刷题

两数之和

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

示例:

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

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

暴力破解法: 两个for循环,一前一后循环匹配相加的值是否等于target。O(N^2) 空间复杂度:O(1)

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

Goland代码

func twoSum(nums []int, target int) []int {
    res:=make([]int,2)
    for i:=0; i<len(nums); i++ {
        for j:=i+1; j<len(nums) ; j++ {
            if nums[i]+nums[j] == target {
                res[0]=i;
                res[1]=j;
                return res
            }
        }
    }
    return nil
}

func twoSum2(nums []int, target int) []int {
    rut:=make([]int,2)
    m := make(map[int]int)
    for i:=0; i<len(nums); i++ {
        res:=target-nums[i]
        value, ok := m[res]
        if ok {
            rut[0]=value
            rut[1]=i
            return rut
        }
        m[nums[i]]=i
    }
    return nil
}

HashMap解法:如果存在,我们需要找出它的索引,在进行迭代并将元素插入到表中的同时,回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在,那我们已经找到了对应解,并立即将其返回

public int[] twoSum(int[] nums, int target) {
        // {2, 7, 11, 15}
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
             //比如target=9,      1: 第一次遍历  9-2=7 , 2: 9-7=2
            int result=target-nums[i];
            if(map.containsKey(result)){
                return new int[]{map.get(result),i};
            }
             //第一次map中没有这个元素    1: put(2,0)
            map.put(nums[i], i);
        }
        return null;
    }

只出现一次的数字

  • 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素
  • 暴力破解法:使用set存储元素 并删除重复的元素 最后饭后迭代器做后的一个数
  • 最优解法: 使用抑或运算 相同取0
示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

解法:抑或运算

class Solution {
    public int singleNumber(int[] nums) {
     // 使用抑或运算 相同取0 不用取
        int a=0;
        for(int i=0;i<nums.length;i++){
            a=a ^ nums[i];
        }
        return a;
    }
}

合并两个有序数组

  • 给定两个有序整数数组 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]
  • 暴力破解法:把数组2合并到数组1的尾部,然后使用冒泡排序重新给num1排序
    /**
     * 暴力破解法:
     *  先把num2合并到num1中,在冒泡排序
     */
public static void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i <n ; i++) {
            nums1[m+i]=nums2[i];
        }
        int szie=m+n-1;
        for (int i = 0; i <szie ; i++) {
            boolean falg=true;
            for (int j = 0; j <szie-1 ; j++) {
                if(nums1[j]>nums1[j+1]){
                    int temp=nums1[j];
                    //  交换j和 j+1之间的位置
                    nums1[j]=nums1[j+1];
                    nums1[j+1]=temp;
                    falg=false;
                }
            }
            if(!falg){
                break;;
            }
        }
        System.out.println(Arrays.toString(nums1));
}


/**
 * 解题思路
 * 从两个数组中的最后一个位置开始进行合并,先找两个数中较大的移动到正的位置,将那个移
 * 动的位置值向前移动一个位置,再进行同样的操作,直到所有的元素处理完
 *
 */
public static void merge2(int[] nums1, int m, int[]
        int a=m-1;
        int b=n-1;
        int index=m+n-1;
        while (a>=0 && b>=0){
            // 比较
            if(nums1[a]>=nums2[b]){
                nums1[index--]=nums2[a--];
            }else{
                nums1[index--]=nums2[b--];
            }
        }
        while (b>=0){
            nums1[index--]=nums2[a];
        }
    System.out.println(Arrays.toString(nums1));
}

求众数(数组中出现次数大于n/2)

  • 给定一个大小为 n的数组,找到其中的众数。众数是指在数组中出现次数大于n/2 的元素
  • 你可以假设数组是非空的,并且给定的数组总是存在众数
示例 1:
输入: [3,2,3]
输出: 3

示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2

Java解法

public static int  majorityElement(int [] nums){
//        众数是指在数组中出现次数大于n/2 的元素。
        int n=nums[0];
        int  count=1;
        for (int i = 1; i <nums.length ; i++) {
             if(n==nums[i]){
                 count++;
             }else{
                 count--;
                 if(count==0){
                     n=nums[i+1];
                 }
             }
        }
        return n;
}

验证回文串

  • 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
示例 1
输入: "A man, a plan, a canal: Panama"
输出: true

 public boolean isPalindrome(String s) {
         if(s.length()==0){
            return  true;
        }
        int left=0,right=s.length()-1;
        //左指针小于右指针时 一直遍历
        while (left<right){

            //判断当前left指针指定的字符是否为字母或数字
            if(!Character.isLetterOrDigit(s.charAt(left))){
                left++; //不符合 ,跳过
            }else if(!Character.isLetterOrDigit(s.charAt(right))){
                //判断当前right指针指定的字符是否为字母或数字
                right--; //不符合 ,跳过
            }else{

                //都是字母数字的字符,可以进行比较的时候,比较这两个字符
                //大写都转换为小写 就行比较
                if(Character.toLowerCase(s.charAt(left))!= Character.toLowerCase(s.charAt(right))){
                    // 若不相等,直接返回 false。
                    return  false;
                }

                    //如果相等,则两个指针向它们的前进方向挪动,
                    left++;
                    right--;

            }
        }
        return  true;
    }

无重复字符的最长子串

  • 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

暴力法:通过两个for循坏嵌套 遍历所有字符串

 public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
         for (int i = 0; i < n; i++){
            for (int j = i + 1; j <= n; j++){
                  if (allUnique(s, i, j)) { 
                            //如果返回true   说明 i 到j下标的字符串是 无重复字符的最长子串
                            if(ans==0){
                                ans++;
                            }
                            if(ans<( j - i)){
                                ans=j - i;
                            }
                             System.err.println("ans:"+ans);
                        }
                   }
            }

       return ans;
 }

public  static boolean allUnique(String s, int start, int end) {
           Set<Character> set = new HashSet<>();
            for (int i = start; i < end; i++) {
                // 循坏遍历指定的起-终下标  取出对应下标的字符串
                Character ch = s.charAt(i);
                if (set.contains(ch)) {
                    //如果存在直接返回
                    return false;
                }
                //不存在放入set
                set.add(ch);
            }
            return true;
 }

斐波那契数列

  • 斐波纳挈数列是以兔子的繁殖引入的,因此也叫“兔子数列
  • 该数列已经有这样一个规律:F(n) = F(n-1) + F(n-2)
// 递归实现 时间复杂度 O(2^N)
public class Solution {
    public int Fibonacci(int n) {
        if(n==0 || n==1){
            return n;
        } 
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

// 非递归算法来实现

 public int Fibonacci(int n) {
      int one = 0;
        int two = 1;
        if(n <= 0) return one;
        if(n == 1) return two;
        int result = 0;
        for(int i = 2; i <= n; i++){
            result = one + two;
            one = two;
            two = result;
        }
        return result;
    }

移动零

  • 给定一个数组 nums,编写一个函数将所有0移动到数组的末尾,同时保持非零元素的相对顺序。
示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

必须在原数组上操作,不能拷贝额外的数组。
尽量减少操作次数
  • 可以先把所有非0的元素移到前面,然后将后面的位置补0
  • 使用指针i,指向需要插入的下标,使用指针j指向遍历的下标。遍历一如果j指向的位置为0,则i不变,j++后移;
  • 如果j指向的位置不为0,则将j位置的元素值赋值到i位置,然后i++。
 public static void moveZeroes(int[] nums) {
     int  i=0;
     for (int j = 0; j <nums.length; j++) {
             if(nums[j] !=0){
                 nums[i]=nums[j];
                 i++;
             }
     }
     for (int p = i; p <nums.length ; p++) {
         nums[p]=0;
     }
 }

Golang解法

func moveZeroes(nums []int)  {
     i:=0
    for j:=0;j< len(nums);j++  {
        if nums[j] !=0 {
            nums[i]=nums[j]
            i++
        }
    }
    for p:=i;p< len(nums);p++ {
        nums[p]=0
    }
}

移除元素

  • 给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。
  • 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

java 解法:双指针

public  int removeElement(int[] nums, int val) {
    if(nums.length==0){
        return 0;
    }
     int i = 0;
     for (int j = 0; j < nums.length; j++) {
             if (nums[j] != val) {
                 nums[i] = nums[j];
                 i++;
             }
      }
    return i;
}

Golang解法

func removeElement(nums []int, val int) int {
    i:=0
    for j:=0;j< len(nums);j++ {
        if nums[j] != val {
            nums[i]=nums[j]
            i++;
        }
    }
    fmt.Println(nums)
    return  i
}

两数之和 II - 输入有序数组

  • 给定一个已按照升序排列的有序数组,找到两个数使得它们相加之和等于目标数。
说明:

返回的下标值(index1 和 index2)不是从零开始的。
你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

java解法:暴力破解法双重循环一前一后遍历。指针碰撞法

public static int[] twoSum(int[] numbers, int target) {
        int left=0;
        int right=numbers.length-1;
        while(left < right){
            if(numbers[left]+ numbers[right]== target){
                return new int[]{left+1,right+1};
            }else if(numbers[left]+numbers[right] < target){
                left++;
            }else {
                right--;
            }

        }
        return null;
    }

Golang解法

func twoSum22(numbers []int, target int) []int {
    l:=0
    r:= len(numbers)-1
    for l<r {
        if numbers[l]+numbers[r] == target {
            return []int{l+1,r+1}
        }else if numbers[l]+numbers[r] < target {
            l++
        }else {
            r--
        }
    }
    return  nil
}
如未加特殊说明,转载必须注明出处:印象博客 » leetcode刷题

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. 你好

    简简单单才是真 (2019-08-05) 回复