[数据结构与算法]LeetCode 46~50

前言

本文隶属于专栏《LeetCode 刷题汇总》，该专栏为笔者原创，引用请注明来源，不足和错误之处请在评论区帮忙指出，谢谢！

本专栏目录结构请见LeetCode 刷题汇总

正文

幕布

幕布链接

46. 全排列

题解

A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partioning)

回溯 + 11

import scala.collection.mutable.ListBuffer
object Solution {
    def permute(nums: Array[Int]): List[List[Int]] = {
        val list = ListBuffer[List[Int]]()
        backtracking(list, ListBuffer[Int](), nums)
        list.toList
    }

    private def backtracking(list: ListBuffer[List[Int]], buf: ListBuffer[Int], nums: Array[Int]){
        if(buf.size == nums.length){
            list += buf.toList
            return
        }
        for((num, i) <- nums.zipWithIndex){
            if(num != 11){
                buf += num
                nums(i) = 11
                backtracking(list, buf, nums)
                buf.remove(buf.size - 1)
                nums(i) = num
            }
        }
    }
}

回溯，list.contains

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        helper(list, new ArrayList<>(), nums);
        return list;
    }

    private void helper(List<List<Integer>> list, List<Integer> tmp, int[] nums){
        if(tmp.size() == nums.length){
            list.add(new ArrayList<>(tmp));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(!tmp.contains(nums[i])){
                tmp.add(nums[i]);
                helper(list, tmp, nums);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}

47. 全排列 II

题解

Really easy Java solution, much easier than the solutions with very high vote

回溯+boolean数组

import scala.collection.mutable.ListBuffer

object Solution {
  def permuteUnique(nums: Array[Int]): List[List[Int]] = {
    val res: ListBuffer[List[Int]] = ListBuffer()
    rec(res, ListBuffer(), nums.sorted, new Array(nums.length))
    res.toList
  }

  def rec(list: ListBuffer[List[Int]], temp: ListBuffer[Int], nums: Array[Int], used: Array[Boolean]): Unit = {
    if (nums.length == temp.size) {
      list += temp.toList
      return
    }
    for (i <- nums.indices if !(used(i) || i > 0 && nums(i) == nums(i - 1) && !used(i - 1))) {
      used(i) = true
      temp += nums(i)
      rec(list, temp, nums, used)
      used(i) = false
      temp.remove(temp.size - 1)
    }
  }
}

48. 旋转图像

题解

官方题解

先上下颠倒，再反斜杆翻转（i，j 交换）

class Solution {
    public void rotate(int[][] matrix) {
        int s = 0, e = matrix.length - 1;
        while(s < e){
            int[] temp = matrix[s];
            matrix[s] = matrix[e];
            matrix[e] = temp;
            s++; e--;
        }

        for(int i = 0; i < matrix.length; i++){
            for(int j = i+1; j < matrix[i].length; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

49. 字母异位词分组

题解

官方题解

质数数组+map

class Solution {
    private int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<Long, List<String>> map = new HashMap<>();
        for(String str : strs){
            long tmp = 1L;
            for(char c : str.toCharArray()){
                tmp *= primes[c - 'a'];
            }
            if(map.containsKey(tmp)){
                map.get(tmp).add(str);
            }else{
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(tmp, list);
            }
        }
        return new ArrayList<>(map.values());
    }
}

50. Pow(x, n)

题解

官方题解

递归+n/2

public class Solution {
    public double myPow(double x, int n) {
        if(n == 0) return 1;
        if(n == Integer.MIN_VALUE){
            x = x * x;
            n = n/2;
        }
        if(n < 0) {
            n = -n;
            x = 1/x;
        }
        
        return (n%2 == 0) ? myPow(x * x, n/2) : x *  myPow(x * x, n/2);
    }
}