chenxin's blog
0%

算法题-数组

发表于 更新于 分类于

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

1
2
3
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

**思路：首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集

  1. 如果 nums[i] 大于 0，则三数之和必然无法等于 0，结束循环
  2. 如果 nums[i] == nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过
  3. 当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
  4. 当 sum == 0 时，nums[R] == nums[R-1] 则会导致结果重复，应该跳过，R−−

**

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
35
36
37
38
39
40
41
42
43
44
public List<List<Integer>> threeSum(int[] nums) {
       Arrays.sort(nums);
       List<List<Integer>> result =  new ArrayList();
       for(int i = 0;i< nums.length -2;i++){
           int left = i+1;
           int right = nums.length -1;
           if(nums[i] > 0) {
               break;  
           }
           if(i > 0 && nums[i-1] == nums[i]){
               continue;
           }else {
               while(left < right){
                   int val = nums[left] + nums[right] + nums[i];
                   if(val > 0){
                       right--;
                   }else if(val < 0){
                       left++;
                   }else{
                       List<Integer> r = new ArrayList();
                       r.add(nums[i]);
                       r.add(nums[left]);
                       r.add(nums[right]);
                       result.add(r);

                       while(left < right){
                           left++;
                           if(nums[left] != nums[left-1]){
                               break;
                           }
                       }
                       while(left < right){
                           right--;
                           if(nums[right] != nums[right+1]){
                               break;
                           }
                       }

                   }
               }
           }
       }
       return result;
   }

16. 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。

1
2
3
4
5
示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

思路1：和3sum类似，固定一个值然后去选其他两个值，与target差值和abs与target的差值进行比较,不用去重还比3sum省事。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int threeSumClosest(int[] num, int target) {
       Arrays.sort(num);
       int ans = num[0] + num[1] + num[2];
       for (int i = 0; i < num.length - 1; i++) {
           int left = i + 1;
           int right = num.length - 1;
           while (left < right) {
               int sum = num[i] + num[left] + num[right];
               if (Math.abs(sum - target) < Math.abs(target - ans)) {
                   ans = sum;
               }
               if (sum > target) {
                   right--;
               } else if (sum < target) {
                   left++;
               } else {
                   return ans;
               }
           }

       }
       return ans;
   }

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

1
2
3
4
5
6
7
示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

思路：动态规划的思想，用一个数组记录第i天时前i-1天中最小买入值

1
2
3
4
5
6
7
8
9
10
11
12
public int maxProfit(int[] prices) {
      if(prices == null || prices.length <= 1) return 0;
      int max = 0;
      int[] min = new int[prices.length];
      min[0] = prices[0];
      for(int i =1;i<prices.length;i++){
          min[i] = Math.min(prices[i-1],min[i-1]);//前i-1中最小的那个
          int m = prices[i] - min[i];
          if(m > max) max = m;
      }
      return max;
  }

122. 买卖股票的最佳时机 II

给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

1
2
3
4
5
6
示例 1:

输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

思路：如果今天与前一天的差值是正数那么就交易一次（累计起来与在最低值买入最高值卖出是一样的，反正不限制交易次数）

1
2
3
4
5
6
7
8
9
public int maxProfit(int[] prices) {
    if(prices == null || prices.length <= 1) return 0;
    int max = 0;
    for(int i=1;i<prices.length;i++){
        int m = prices[i] - prices[i-1];
        if(m > 0) max += m;
    }
    return max;
}

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。

思路：由于只有三种值，那可以使用类似快排的切分方法，一个指针p1指向排好序的0，另一个指针p2指向排好序的2，再用一个指针cur遍历数组，遍历的条件是cur小于p2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void sortColors(int[] nums) {
     int p1 = -1;
     int p2 = nums.length;
     int cur = 0;
     while(cur < p2){
         if(nums[cur] == 0){
             swap(nums,++p1,cur);//交换到cur一定是1
         }else if(nums[cur] == 2){
             swap(nums,--p2,cur);
             cur--;//由于交换到cur的数字不确定，有可能是0、1、2，那么就需要再次比较
         }
         cur++;
     }
 }

231. 2 的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

思路：位运算，如果是2的幂，那么存在它&上某个2的幂的结果是它自己

1
2
3
4
5
6
7
public boolean isPowerOfTwo(int n) {
    if(n == 0) return false;
    for(int i =0;i<=30;i++){
      if((n & (1 << i)) == n) return true;
    }
    return false;
}

43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

1
2
输入: num1 = "123", num2 = "456"
输出: "56088"

思路：模拟两个数相乘的逻辑，
1）两数相乘位数不会两个数的长度相加
2）模拟运算的低位在数组的开头，要将数字翻转再模拟
3）这样就可以从末尾用排除0的方式找到高位的边界
4）特殊情况，乘以0，endP==0

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
35
36
37
public String multiply(String num1, String num2) {
        if (num1 == null || num1.length() == 0) return "";
        if (num2 == null || num2.length() == 0) return "";
        int[] r = new int[num1.length() + num2.length()];
        num1 = new StringBuilder(num1).reverse().toString();
        num2 = new StringBuilder(num2).reverse().toString();
        for (int i = 0; i < num1.length(); i++) {
            for (int j = 0; j < num2.length(); j++) {
                int x = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                r[i + j] += x;
            }
        }
        for (int i = 0; i < r.length; i++) {
            int t = r[i];
            r[i] = r[i] % 10;
            if (i + 1 < r.length) {
                r[i + 1] += (t / 10);
            }
        }

        int endP = r.length - 1;
        while (endP > 0) {
            if (r[endP] != 0) {
                break;
            }
            endP--;
        }
        if (endP == 0 && r[endP] == 0) {
            return "0";
        }
        StringBuilder builder = new StringBuilder();
        for (int i = endP; i >= 0; i--) {
            builder.append(r[i]);
        }
        return builder.toString();
    }
}

33. 搜索旋转排序数组

给出一个转动过的有序数组，你事先不知道该数组转动了多少
(例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2).
在数组中搜索给出的目标值，如果能在数组中找到，返回它的索引，否则返回-1。
假设数组中不存在重复项。

思路：
二分查找，二分查找命中的mid将数组分成两个部分，那么必然有一边是升序的，判断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
public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0) return -1;
        int l = 0;
        int h = nums.length-1;
        while(l <= h){
            int mid = (l+h)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[l] < nums[mid]){//左边是升序的
               if(target == nums[l]) {
                   return l;
               }
               if(target > nums[l] && target < nums[mid]){//target在这个升序中
                   h = mid-1;
               }else {//没在，那么排除这段
                   l = mid+1;
               }  
            }else {//走到这个，右边必然是升序
                if(target == nums[h]) {
                   return h;
                }
                if(target > nums[mid] && target < nums[h]){//target在这个升序中
                   l = mid+1;
                }else {
                    h = mid-1;
                }        
            }
        }
        return -1;
    }

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

思路：所有字符串的最长相同前缀一定是小于两个字符串的相同前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String longestCommonPrefix(String[] strs) {
           if(strs == null) return "";
           if(strs.length == 1) return strs[0];
           String prefix = "";
           for(int i=1;i<strs.length;i++){
              prefix =  longestCommonPrefix(strs[0],strs[i]);
              strs[0] = prefix;
           }
           return prefix;
    }

   private String longestCommonPrefix(String a,String b){
       int c = Math.min(a.length(),b.length());
       int i =0;
        while(i < c && a.charAt(i) == b.charAt(i)){
            i++;
        }
        return a.substring(0,i);
   }

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路：使用栈，栈内保存的是柱子的下标，并且柱高度是从栈低开始升序排列的，遍历到一个柱子，如果它的高度大于栈顶的柱子那么就说明可以和栈顶后面的那个柱子形成积水，这时把它们pop出来，利用下标计算即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int trap(int[] height) {
        int ans = 0;
        Stack<Integer> stack = new Stack<Integer>();
        int n = height.length;
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量

思路：左右双指针，每次都移动矮的柱子指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int maxArea(int[] height) {
            if(height == null || height.length <= 1) return 0;
            int p1 = 0;
            int  p2 = height.length -1;
            int max = 0;
            while(p1 < p2){
                int h1 = height[p1];
                int h2 = height[p2];
                int w = p2 - p1;
                int h =0;
                if(h1 > h2){
                    h = h2;
                    p2--;
                }else {
                    h = h1;
                    p1++;
                }
                int area = w * h;
                if(area > max) max = area;
            }    
            return max;
    }

9. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

思路：对数字直接进行截取高位和低位进行比较，那就需要先得到数字的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean isPalindrome(int x) {
       if(x < 0) return false;
       if(x == 0) return true;
       int length = 1;
       int topBase = 1;
       int x1 = x;
       while(x1 / 10 != 0){
           length++;
           x1 /= 10;
           topBase *= 10;
       }
       int count = length / 2;
       while(count-- > 0){
           int right = x % 10;
           int left = x / topBase;
           if(left != right) return false;
           x = (x % topBase) / 10;
           topBase /= 100;
       }

       return true;
   }

7. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−2^31,  2^31 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。

思路：类似与出栈，挨个弹出最后一位，然后累加结果，但是需要判断边界：
1）如果Int.MAX/10会小于r,那么r*10大于最大值，就可以判断是否越界，最小值同理
2）还有一种个位的导致越界的情况，那么需要单独判断个位越界的情况，如果弹出的数字大于7并且Int.MAX - r 小于7，那么也会越界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int reverse(int x) {
         /*
          2147483647
          -2147483648
         */
       int r = 0;
       while (x != 0) {
           int pop = x % 10;
           if (x > 0 &&
                   (Integer.MAX_VALUE / 10 < r
                           || (pop > 7 && Integer.MAX_VALUE - r < 7))) {
               return 0;
           }
           if (x < 0 &&
                   (Integer.MIN_VALUE / 10 > r
                           || (pop < -8 && Integer.MIN_VALUE - r > -8))) {
               return 0;
           }
           r = r * 10 + pop;
           x /= 10;
       }
       return r;
   }

36. 有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）  

注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。

思路：利用hash表的思想，保存每个单列、每个单行、每个单块上数字出现的次数，如果哪个次数大于1那就不成立了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean isValidSudoku(char[][] board) {
            int[][] rows = new int[9][9];
            int[][] colunms = new int[9][9];
            int[][][] boxs = new int[3][3][9];

            for(int i=0;i< 9;i++){
                for(int j=0;j<9;j++){
                    if(board[i][j] == '.'){
                        continue;
                    }

                    int val = board[i][j] - '0'-1;
                    rows[i][val]++;
                    colunms[j][val]++;
                    boxs[i/3][j/3][val]++;
                    if(rows[i][val] > 1 || colunms[j][val]>1 || boxs[i/3][j/3][val] > 1){
                        return false;
                    }
                }
            }
            return true;
    }

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

1
2
3
4
5
下面给出几个样例：
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

思路：二分法，找到返回.因为是向下取整的,没找到就直接返回指针相遇的那个位置

1
2
3
4
5
6
7
8
9
10
11
12
public int searchInsert(int[] A, int target) {
    if (A == null || A.length == 0) return 0;

    int lo = 0, hi = A.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (A[mid] == target) return mid;
        else if (target > A[mid]) lo = mid + 1;
        else hi = mid - 1;
    }
    return lo;
}