数组

数组

单调栈

参考: LeetCode

单调栈 = 单调 + 栈,因此其同时满足两个特性: 单调性的特点。

  • 单调性: 单调栈里面所存放的数据是有序的(单调递增或递减)。
  • 栈: 后进先出。

因其满足单调性和每个数字只会入栈一次,所以可以在时间复杂度 O(n) 的情况下解决一些问题。

LeetCode 739. 每日温度

题意

给定每天的温度,求对于每一天需要等几天才可以等到更暖和的一天。如果该天之后不存在 更暖和的天气,则记为 0。 输出一个一维数组,表示每天需要等待的天数。

示例

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

代码

class Solution {
    
    public int[] dailyTemperatures(int[] T) {
        int[] ans = new int[T.length];
        Deque<Integer> s = new LinkedList<Integer>();
        for (int i = 0; i < T.length; i++) {
            while (!s.isEmpty() && T[i] > T[s.peek()]) {
                ans[s.peek()] = i - s.pop();
            }
            s.push(i);
        }
        return ans;
    }

}

LeetCode 316. 去除重复字母

题意

给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

示例

输入:s = "bcabc"
输出:"abc"

题解

首先思考这个问题的一个简单版本。给一个字符串删除一个字符,使得字典序最小。

解法: 字典序就是字母的大小顺序,我们想字典序最小,那应删除满足 s[i] > s[i+1] 的最小位置 i 上的字符。 回到这个问题,我们也是想尽可能的删除满足 s[i] > s[i+1] 的最小位置 i 上的字符,如果每次都是遍历一遍字符串删除一个字符,这样时间复杂度可能退化到 O(n^2)

优化方法: 单调栈。

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] count = new int[30];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }
        boolean[] vis = new boolean[30];
        StringBuffer ans = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';
            if (!vis[c]) {
                while ((ans.length() > 0) && (count[ans.charAt(ans.length() - 1) - 'a'] > 0) 
                			&& ((ans.charAt(ans.length() - 1) - 'a') > c)) {
                    vis[ans.charAt(ans.length() - 1) - 'a'] = false;
                    ans.deleteCharAt(ans.length() - 1);
                }
                vis[c] = true;
                ans.append(s.charAt(i));
            }
            count[c]--;
        }
        return ans.toString();
    }
}

无序数组第 K 大的数字

  • partition 算法每次返回的都是 pivot 所在的索引
  • partition 算法实现的思路,i 指向的是小于 pivot 的数列的最后一个值的索引。j 在前面探路,如果遇见小于等于 pivot 的值 arr[j],说明这个值应该放在前半段,那么它应该前半段的谁交换呢?答案就是这个 arr[j] 应该添加到 i 的下一个位置。也就是需要 swap(++i, j)
  • 最后 swap(++i, high),将 pivot 放到中间。
小小小小小大大大大小...pivot
       i       j
public int findKthLargest(int[] nums, int k) {
    k = nums.length - k;

    // 1 2 3 4 5 6
    //         ↑(第 2 大)
    //   ↑(partition = 2 的时候,实际上指向的是这里)

    int lo = 0;
    int hi = nums.length - 1;

    // ==========================
    // while (lo < hi)
    // nums = [1],这种情况进入不了循环
    //
    // ==========================
    while (lo <= hi) {
        int index = partition(nums, lo, hi);
        if (index == k) {
            return nums[index];
        } else if (index < k) {
            lo = index + 1;
        } else {
            hi = index - 1;
        }
    }

    return -1;
}

private int partition(int[] nums, int lo, int high) {
    int i = lo - 1;
    int pivot = nums[high];

    for (int j = lo; j <= high - 1; j++) {
        if (nums[j] <= pivot) {
            i++;
            swap(nums, i, j);
        }
    }

    swap(nums, i + 1, high);
    return i + 1;
}

private void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

快速排序

  • pivot 选择的是 array[end]
// T(n) = T(n - 1) + T(0),每次都分为 n - 1 个和 0 个元素
// T(n - 1) = T(n - 2) + T(0)
// ...
// 迭代想加
// T(n) = O(n^2)
//
// - 最坏情况:
// T(n) = 2T(n / 2) + O(n)
// T(n / 2) = 2T(n / 4) + O(n)
//
// 画出树,整颗树高 log2^n 然后每次都是 O(n) 所以 nlogn
// 
//        n.................O(n)
//    n/2   n/2.............O(n)
// n/4 n/4 n/4 n/4..........O(n)
//
public class QuickSort {

    public void sort(int[] array) {
        sort(array, 0, array.length - 1);
    }

    private void sort(int[] array, int begin, int end) {
        if (begin < end) {
            int index = partition(array, begin, end);
            
            // ================================
            // begin ~ index - 1
            // ================================
            sort(array, begin, index - 1);

            // ================================
            // index + 1 ~ end
            // ================================
            sort(array, index + 1, end);
        }
    }

    private int partition(int[] array, int begin, int end) {
        int i = begin - 1;
        int pivot = array[end];

        for (int j = begin; j < end; j++) {
            if (array[j] <= pivot) {
                // i++ 之后 array[i] 就是一个比 pivot 大的值
                // 当前 array[j] 是一个比 pivot 小的值
                // 因此二者进行交换
                i++;
                swap(array, i, j);
            }
        }

        swap(array, i + 1, end);
        
        // 返回的是 pivot 所在的索引
        return i + 1;
    }

    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}

三数之和

注意这道题返回的是数字

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);

    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        List<int[]> twoSumList = twoSum(nums, i + 1, nums.length - 1, 0 - nums[i]);
        if (!twoSumList.isEmpty()) {
            for (int[] twoSumArray: twoSumList) {
                res.add(new ArrayList<>(Arrays.asList(
                    nums[i], twoSumArray[0], twoSumArray[1]
                )));
            }
        }
    }

    return res;
}

private List<int[]> twoSum(int[] nums, int lo, int hi, int target) {
    List<int[]> list = new ArrayList<>();

    for (int i = lo; i <= hi - 1; i++) {
        if (i > lo && nums[i] == nums[i - 1]) {
            continue;
        }

        // target = a + b
        int a = nums[i];
        int bIndex = binarySearch(nums, i + 1, hi, target - a);
        if (bIndex != -1) {
            list.add(new int[]{ a, nums[bIndex] });
        }
    }

    return list;
}

// 二分搜索
private int binarySearch(int[] nums, int lo, int hi, int target) {
    while (lo <= hi) {
        int m = lo + ((hi - lo) >> 1);

        if (nums[m] == target) {
            return m;
        } else if (nums[m] > target) {
            hi = m - 1;
        } else {
            lo = m + 1;
        }
    }

    return -1;
}

两数之和

注意这道题返回的是两个数的索引

  • 借助一个 Map 即可简化思路,达到 O(1) 的复杂度
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(target - nums[i])) {
            return new int[]{ map.get(target - nums[i]), i };
        }

        map.put(nums[i], i);
    }

    return new int[]{};
}

搜索旋转排序数组

  • 第一种思路,先查找 min 值所在位置,然后分别在 min 的左右两侧使用二分搜索查找 target

实际面试的时候,我感觉使用第二种思路会好一些。

public int search0(int[] nums, int target) {
    // ================================
    // 忘记这一步骤了
    // ================================
    if (nums.length == 0) {
        return -1;
    }

    int minIndex = searchMin(nums);

    int index = -1;
    if ((index = binarySearch(nums, minIndex, nums.length - 1, target)) != -1) {
        return index;
    }

    return binarySearch(nums, 0, minIndex - 1, target);
}

private int searchMin(int[] nums) {
    int lo = 0; // always point to 前半部分
    int hi = nums.length - 1; // always point to 后半部分

    if (nums[lo] > nums[hi]) {
        while (lo < hi) {
            if (hi - lo == 1) {
                return hi;
            }

            int m = lo + ((hi - lo) >> 1);

            if (nums[m] < nums[0]) {
                // middle 位于后半部分
                hi = m;
            } else if (nums[m] > nums[nums.length - 1]) {
                // middle 位于前半部分
                // min 在后半部分
                //
                // ==================================
                // 注意这个地方, lo = m,而不是 lo = m + 1
                // m + 1 有可能越界,跑到后半部分
                // ==================================
                lo = m;
            }
        }
    }

    return 0;
}

private int binarySearch(int[] nums, int lo, int hi, int target) {
    while (lo <= hi) {
        int m = lo + ((hi - lo) >> 1);

        if (nums[m] == target) {
            return m;
        } else if (nums[m] > target) {
            hi = m - 1;
        } else {
            lo = m + 1;
        }
    }

    return -1;
}
  • 第二种思路,直接运用一次二分搜索来定位:

这里面最关键的两次决策:

  1. nums[m] 数值位于左侧还是右侧?如果位于右侧,那么如下条件为 truenums[m] <= nums[hi]
  2. 确定左侧右侧以后,再看 targetnums[m] 的大小,以便确定 lohi 是如何变化
// 核心思想: 确定 m 位于哪一边,然后确定 target 是不是位于有序的一边
public int search(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length - 1;

    while (lo <= hi) {
        int m = lo + ((hi - lo) >> 1);
        if (nums[m] == target) {
            return m;
        }

        // 6 7 1 2 3 4 5
        //     ↑ ↑ ↑ ↑ ↑
        //
        // 1 2 3 4 5 6 7
        // ↑ ↑ ↑ ↑ ↑ ↑ ↑
        //
        // 右侧有序
        // target 是不是位于有序右侧空间
        if (nums[m] <= nums[hi]) {
            if (target > nums[m] && target <= nums[hi]) {
                lo = m + 1;
            } else {
                hi = m - 1;
            }
        } else {
            // 6 7 1 2 3 4 5
            // ↑ ↑
            //
            // target 是否位于左侧有序空间内
            if (target >= nums[lo] && target < nums[m]) {
                hi = m - 1;
            } else {
                lo = m + 1;
            }
        }

    }

    return -1;
}

螺旋顺序打印矩阵

这是我能想到的比较妥善、好记、不容易出错的办法:

public List<Integer> spiralOrder(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;

    // 行
    int rowUp = 0, rowDown = m - 1;
    // 列
    int colLeft = 0, colRight = n - 1;

    List<Integer> result = new ArrayList<>(m * n);

    while (true) {
        for (int i = colLeft; i <= colRight; i++) {
            result.add(matrix[rowUp][i]);
        }
        rowUp++;
        if (rowUp > rowDown) {
            break;
        }

        for (int i = rowUp; i <= rowDown; i++) {
            result.add(matrix[i][colRight]);
        }
        colRight--;
        if (colRight < colLeft) {
            break;
        }

        for (int i = colRight; i>= colLeft; i--) {
            result.add(matrix[rowDown][i]);
        }
        rowDown--;
        if (rowDown < rowUp) {
            break;
        }

        for (int i = rowDown; i >= rowUp; i--) {
            result.add(matrix[i][colLeft]);
        }
        colLeft++;
        if (colLeft > colRight) {
            break;
        }
    }

    return result;
}

过半数的元素

使用**摩尔投票法**:

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        
        for (int num : nums){
            if (votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }

        return x;
    }
}

二分查找

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return -1;
}

用栈实现队列

实现思路肯定是两个栈。有注意事项:

  • peek()/pop() 的时候,只有 s2 为空的时候,才需要将 s1 里面的所有元素 pop 并重新 pushs2 里面
class MyQueue {

    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();

    public MyQueue() {

    }
    
    public void push(int x) {
        s1.push(x);
    }
    
    public int pop() {
        // 注意
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }

        return s2.pop();
    }
    
    public int peek() {
        // 注意
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }

        return s2.peek();
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }

}

x 的平方根

  • end 元素最少是 1,不能直接是 x / 2,否则 x = 1 的时候,end = 0
  • x / mid >= mid 这个条件的时候,mid 有可能就是 ans

变形要求小数点精确到 xxx;求平方根,误差小于0.00001——虾皮shopee-IOS一面-2021.04;字节强化学习一面,精确到小数点后10位,二分,每次移动1e-10

public int mySqrt(int x) {
    int ans = 0;

    int begin = 1;
    int end = Math.max(1, x / 2);

    while (begin <= end) {
        int mid = begin + ((end - begin) >> 1);
        
        // 1, 2, 3, 4
        if (x / mid >= mid) {
            ans = mid;
            begin = mid + 1;
        } else {
            end = mid - 1;
        }
    }

    return ans;
}

合并区间

  • 得将 prev 指针保留下来,不停调整 prev.end 的值
  • 通过使用 lambda 表达式可以简化代码量,Arrays.sort,相同 beginend 的大小谁在前谁在后是无所谓
public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

    List<int[]> resultList = new ArrayList<>();

    for (int[] interval : intervals) {
        if (resultList.isEmpty()) {
            resultList.add(interval);
        } else {
            int[] prev = resultList.get(resultList.size() - 1);
            if (interval[0] <= prev[1]) {
                prev[1] = Math.max(prev[1], interval[1]);
            } else {
                resultList.add(interval);
            }
        }
    }

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

下一个排列

即下一个最大的整数。

  1. 示例 1 5 8 4 7 6 5 3 1
  2. 从后往前看,3 1 是否有更大的数字?没有;5 3 1 有吗,也没有;7 6 5 3 1 都没有;为什么它们都没有,因为它们处于降序
// 1 5 8 4 7 6 5 3 1
//       ↑
//             ↑(5 > 4 最后一个大于它的)
// 1 5 8 5 7 6 4 3 1 (交换)
//         ↑(reverse)↑
// 1 5 8 5 1 3 4 6 7
//
// 找到第一个不符合从右到左升序对的数字 i = 4
// 找到第一个刚刚大于 nums[i] 的数字 j = 5
// swap(i, j)
// reverse(i + 1)
// 
//   ↓ (第一个不符合的数字 3,如果相等,比如多个 3 还要再往前找)
// 7 3 6 4 2
//       ↑ (第一个刚刚大于 3 的数字 4)
//
// 7 4 6 3 2 (交换)
//
// 7 4 2 3 6 (4 后面的数字也交换)
public void nextPermutation(int[] nums) {
    int i = nums.length - 1;

    while (i > 0) {
        // ===========================
        // 这个地方是 >=
        // [1,1,2,2,5,2]
        //        ↑
        //        i
        // ===========================
        if (nums[i - 1] >= nums[i]) {
            i--;
        } else {
            break;
        }
    }
    // 指向前一个
    i--;

    if (i >= 0) {
        int j = i;
        // ===========================
        // 这个地方是 > 必须大于,不能等于
        // [1,1,2,2,5,2]
        //        ↑ ↑
        //        i j
        //
        // 如果允许等于的话,那么 2 最终 j 还会指向 2
        // reverse(i, j) 没什么用
        // ===========================
        while (j + 1 < nums.length && nums[j + 1] > nums[i]) {
            j++;
        }

        swap(nums, i, j);
    }

    reverse(nums, i + 1, nums.length - 1);
}

private void reverse(int[] nums, int i, int j) {
    while (i < j) {
        swap(nums, i, j);

        i++;
        j--;
    }
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

下一个更大元素②

原题