数组

发布： 分类： 评论： 阅读：

数组的全排列

leetcode 31. 给出全排列的下一个排列

  • 输入1: 1,2,3,4,3,8,7,6,5 → 1,2,3,4,5,3,6,7,8
  • 输入2: 3,2,1 → 1,2,3
  • 条件：在nums数组上就地转换，并且要使用常数级辅助空间
  • 从后向前，找到递减的位置，然后从后面找到比他大的第一个元素，交换，然后对后面从小到大排序即可
  • 如果当前已经是最大，那么就输出他的最小值 从小到大排序即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}
    
public void reverse(int[] nums, int begin) {
    int end = nums.length-1;
    for(int i=0;i<(end-begin+1)/2;i++)
        swap(nums, begin+i, end-i);
}

public void nextPermutation(int[] nums) {
    boolean flag = true;
    for(int i=nums.length-1;i>0;i--) {
        if(nums[i]<=nums[i-1])
            continue;
        else {
            //nums[i-1]是递减的那个值
            for(int j=nums.length-1;j>=0;j--) {
                if(nums[j]>nums[i-1]) {
                    swap(nums, i-1, j);
                    flag = false;
                    break;
                }
            }
            //对后面逆序
            reverse(nums, i);
            break;
       }
    }
    if(flag)
        Arrays.sort(nums);
}

leetcode 46. 无重复数字数组的全排列

  • 输入：[1,2,3]
  • 输出：[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void get_permute(int[] nums, int[] visit, List<List<Integer>> result, List<Integer> tmp_res) {
    if(tmp_res.size()==nums.length) {
        List<Integer> tmp = new ArrayList();
        tmp.addAll(tmp_res);
        result.add(tmp);
        return;
    }
    for(int i=0;i<nums.length;i++) {
        if(visit[i]==0) {
            tmp_res.add(nums[i]);
            visit[i] = 1;
            get_permute(nums, visit, result, tmp_res);
            tmp_res.remove(tmp_res.size()-1);
            visit[i] = 0;
        }
    }
}

public List<List<Integer>> permute(int[] nums) {
    int[] visit = new int[nums.length];
    List<List<Integer>> result = new ArrayList();
    List<Integer> tmp_res = new ArrayList();
    get_permute(nums, visit, result, tmp_res);
    return result;
}

leetcode 47. 有重复数字的全排列

  • 输入：[1,2,1]
  • 输出：[1,1,2] [1,2,1] [2,1,1]
  • 有重复数字时，可以使用set代替之前的list,因为set本身就有过滤重复的用途。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public void get_permute(int[] nums, int[] visit, Set<List<Integer>> result, List<Integer> tmp_res) {
    if(tmp_res.size()==nums.length) {
     List<Integer> tmp = new ArrayList();
        tmp.addAll(tmp_res);
        result.add(tmp);
        return;
    }
    for(int i=0;i<nums.length;i++) {
        if(visit[i]==0) {
            tmp_res.add(nums[i]);
            visit[i] = 1;
            get_permute(nums, visit, result, tmp_res);
            tmp_res.remove(tmp_res.size()-1);
            visit[i] = 0;
        }
    }
}
public List<List<Integer>> permuteUnique(int[] nums) {
    List<Integer> list = new ArrayList();
    Set<List<Integer>> res = new HashSet();
trueint[] visit = new int[nums.length];
    
    Arrays.sort(nums);
    get_permute(nums, visit, res, list);

    List<List<Integer>> result = new ArrayList();
    for(List<Integer> list1:res)
        result.add(list1);
    return result;
}
  • 但是这种做法会比较复杂，不管相同不相同的数字，都会进行一次全排列，会比较耗时，所以可以先将数组排序，将相同的放在一起，如果取出下一个元素和上一个相同，那么这一轮就可以不再进行全排列了。

leetcode 60. 取特定位置的全排列字符串

  • n=3, 则全排列为："123" "132" "213" "231" "312" "321"，若k=3, 则输出为："213"
  • n=4, k=9, 则输出为："2314"
  • 第一个位置有n中情况，第二个位置n-1中情况，…对于给定的n，其全排列中n!中情况。
  • 求第一个位置的值时：k/(n-1)! = shang…yu, 若yu>0, 则拿到shang位置的值。其他同理
  • 4 13 13/6 = 2…1 3
  • 7/2! = 7/2 = 3…1 
1

给定第k个全排列，求倒数第k个全排列

  • n=3, 则全排列为："123" "132" "213" "231" "312" "321"
  • 给定k=3, 第3个全排列为 "213" ，则输出为："231"
  • 这道题比较有规律，倒数第k个全排列，就是n+1减去正数第k个全排列每个位置上面的值。
  • 例：k=2, n=3：正数："132"；倒数：(n+1-1)(n+1-3)(n+1-2)="312"

输出所有和为target的数组

先来一个类似的简单题：leetcode 633. 判断一个值可否由两个数的平方和组成

1
2
whether there're two integers a and b such that a^2 + b^2 = c.
例如：输入5，返回true， 因为 1 * 1 + 2 * 2 = 5。
  • 解法：设置两个变量，i=0, j= $\sqrt5$ 的向下取整， 若$ii+jj<c$, 则增大i，否则减小j，直到i>j或找到满足条件的值为止。
1
2
3
4
5
6
7
8
9
10
11
public boolean judgeSquareSum(int c) {
    int i = 0;
    int j = (int)Math.sqrt(c);
    while(i<=j) {
        int value = i*i+j*j;
        if(value==c) return true;
        if(value>c) j -= 1;
        if(value<c) i += 1;
    }
    return false;
}

leetcode 15. threesum, 输出所有和为0的数组

  • 先将数组进行排序。

  • 设置两个指针，一个指向数组头，一个指向数组尾，向中间移动。

  • 如果指针指向的两数之和小于target，则我们将左边那个指针i右移一位，使得指向的数字增大一些。

  • 同理，如果两数之和大于target，则我们将右边那个指针j左移一位，使得指向的数字减小一些。

  • 直到找到满足条件的两个值。

  • 因为该道题是三个数的和为target，所以需要先确定一个数，然后让new_target = target-当前值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static List<List<Integer>> threeSum(int[] nums) {
    Set<List<Integer>> res = new HashSet<>();
    Arrays.sort(nums);
    for(int i=1;i<nums.length;i++) {
        int left = 0;
        int right = nums.length-1;
        int target = 0-nums[i];
        while(left<right && left!=i && right!=i) {
            if(nums[left]+nums[right]>target)
                right -= 1;
            else if(nums[left]+nums[right]<target)
                left += 1;
            else {
                List<Integer> tmp_res = new ArrayList<>();
                tmp_res.add(nums[left]);
                tmp_res.add(nums[i]);
                tmp_res.add(nums[right]);
                res.add(tmp_res);
                right -= 1;
                left += 1;
            }

     }
    }
    List<List<Integer>> result = new ArrayList<>();
    Iterator<List<Integer>> iterator = res.iterator();
    while(iterator.hasNext())
        result.add(iterator.next());

   return result;
}

leetcode 16. 三个数的和最接近target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int threeSumClosest(int[] nums, int target) {
    int res = Integer.MAX_VALUE;
    Arrays.sort(nums);
    for(int i=1;i<nums.length-1;i++) {
        int left = 0;
        int right = nums.length-1;
        int new_tar = target - nums[i];
        while(left<right && left!=i && right!=i) {
            if(nums[left]+nums[right]>new_tar)
                right -= 1;
            else if(nums[left]+nums[right]<new_tar)
                left += 1;
            else {
                return target;
            }
        }
        left = left==i? left-1: left;
        right = right==i ? right+1:right;
        int tmp = nums[i] + nums[left] + nums[right];
        res = Math.abs(target-tmp)<Math.abs(target-res)?tmp:res;
    }
    return res;
}

其他题目

leetcode 56. Merge Intervals

  • 将数组有重叠的部分进行合并。
  • 先将数组按照第一个元素的位置排序，然后比较前一个的第二个值与后一个的第一个值
  • 如果前一个的第二个值大于后一个的第一个值，就进行合并，右边界取第一个和第二个右边界的大值
1
2
3
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int[][] merge(int[][] intervals) {
    List<int[]> list = new ArrayList();
    Arrays.sort(intervals, new Comparator<int[]>(){
        @Override
        public int compare(int[] x, int[] y) {
            return Integer.compare(x[0], y[0]);
        }
    });
    int start = 0;
    while(start<intervals.length) {
        int[] tmp = new int[2];
        tmp[0] = intervals[start][0];
        int cur_end = intervals[start][1];
        while(start<intervals.length-1 && cur_end>=intervals[start+1][0]) {
            cur_end = Math.max(cur_end, intervals[start+1][1]);
            start += 1;
        }
        start += 1;
        tmp[1] = cur_end;
        list.add(tmp);
    }

    return list.toArray(new int[list.size()][2]);
}