Interview-Notes

class Solution { public void nextPermutation(int[] nums) { //Arrays.sort(int[] nums, int fromIndex, int toIndex) 这个方法对nums中的fromIndex到toIndex - 1的部分进行排序 // 从后向前遍历，一旦出现一个数大于前面的数，说明存在更大的数，记录该索引i // 下一个更大的数是，后面的数按从小到大排，将后面的数中第一个比i-1 大的数据与之交换 int n = nums.length; for (int i = n - 1; i >= 0; i--) { if (i == 0) { Arrays.sort(nums); //当前排序是最大排序，返回最小排序 } else if (nums[i] > nums[i-1]) { //nums[i] > nums[i-1] 说明存在下一个更大的排列 Arrays.sort(nums, i, n); //并且nums[i]之后的部分满足最大排列，下一个更大的排列，即对nums[i]和之后的部分排序 for (int index = i; index < n; index++) { // 并取出第一个比nums[i-1]大的部分，进行交换 if (nums[index] > nums[i-1]) { int temp = nums[i - 1]; nums[i - 1] = nums[index]; nums[index] = temp; return; } } } } } }

class Solution { // 题目要求o(n)的时间复杂度 // 题目类型dp public int[] productExceptSelf(int[] nums) { //除nums[i]之外的所有数的乘积也就是将nums[i]当做1 // 可以计算这个数左乘积和右乘积 // 用三个数组分别存储前缀、后缀和乘积 // 对于元素nums[0]，我们设定初始值left[0] = 1; // 对于元素nums[nums.length - 1] 设定初始值right[nums.length - 1] = 1; int n = nums.length; int[] left = new int[n]; int[] right = new int[n]; int[] res = new int[n]; left[0] = 1;right[n - 1] = 1; for (int i = 1; i < n; i++) { left[i] = left[i-1] * nums[i-1]; } for (int j = n - 2; j >= 0; j--) { right[j] = right[j + 1] * nums[j + 1]; } for (int i = 0; i < n; i++) { res[i] = left[i] * right[i]; } return res; class Solution { // 背包问题，完全背包 public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; // dp[i] 代表组成金额为i的最少硬币数 Arrays.fill(dp, amount + 1); dp[0] = 0; for (int i = 0; i < coins.length; i++) { for (int j = coins[i]; j <= amount; j++) { dp[j] = Math.min(dp[j], dp[j-coins[i]] + 1); } } return dp[amount]== amount+1 ? - 1 : dp[amount]; } }} }

class Solution { // o(log n) 二分法 // 二分法的难点在于等号 // 判断nums[mid] 与 nums[left] 的关系，如果nums[mid] >= nums[left] ,说明 left 到 mid 有序 // if (nums[mid] < nums[left]) 说明 mid 到right 有序， // 判断target是否落在有序部分，若不在则切换子数组 // 据此缩小范围 public int search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] >= nums[left]) { if (target >= nums[left] && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } else { if (target > nums[mid] && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return -1; } }

class Solution { // 时间复杂度O(log n) 空间复杂度O(1) 常量空间存放变量 // 二分法 // 寻找第一次target的位置，更新右边界 // 最后一次target的位置，更新左边界 public int[] searchRange(int[] nums, int target) { int firstPos = findBoundary(nums, target, true); if (firstPos == -1) {return new int[]{-1, -1};} int lastPos = findBoundary(nums, target, false); return new int[]{firstPos, lastPos}; } public int findBoundary(int[] nums, int target, boolean first) { int left = 0, right = nums.length - 1; int pos = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else { // nums[mid] == target pos = mid; if (first) { right = mid - 1; // 寻找第一次出现target的位置，向左移动右边界 } else { left = mid + 1; // 寻找最后一次出现target的位置，向右移动左边界 } } } return pos; } }

class Solution { // 算法的时间复杂度为O(log(min(m,n))) // 二分 public double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.length > nums2.length) { return findMedianSortedArrays(nums2, nums1); } int m = nums1.length; int n = nums2.length; int left = 0, right = m; while (left <= right) { int i = left + (right - left) / 2; int j = (m + n + 1) / 2 - i; int nums1LeftMax = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]); int nums1RightMin = (i == m ? Integer.MAX_VALUE : nums1[i]); int nums2LeftMax = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]); int nums2RightMin = (j == n ? Integer.MAX_VALUE : nums2[j]); if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) { if ((m + n) % 2 == 0) { return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0; } else { return Math.max(nums1LeftMax, nums2LeftMax); } } else if (nums1LeftMax > nums2RightMin) { right = i - 1; } else { left = i + 1; } } return -1; } }

class Solution { public void rotate(int[][] matrix) { // 题目要求需要原地旋转，不能新建数组 // 直接matrix[col][n-1-row] = matrix[row][col]的交换会导致原位置的值被覆盖，后续的交换无法进行 //两步实现：1.转置matrix,使得matrix[i][j]变为matrix[j][i] //2.将matrix[j][i] 与 matrix[j][n-1-i]交换 // 先转置或者先交换行都一样，需要注意的是：交换和转置的边界 int n = matrix.length; for (int row = 0; row < n / 2; row++) { for (int col = 0; col < n; col++) { int temp = matrix[row][col]; matrix[row][col] = matrix[n - 1 - row][col]; matrix[n - 1 - row][col] = temp; } } for (int row = 0; row < n ; row++) { for (int col = row; col < n; col++) { int temp = matrix[row][col]; matrix[row][col] = matrix[col][row]; matrix[col][row] = temp; } } } }

class Solution { //贪心算法，局部最优得全局最优 //每一步取最大,看最终能否走到nums[nums.length - 1] // if (coverrange == i) 说明到i为止就不能购在跳动了 public boolean canJump(int[] nums) { int coverrange = 0; for (int i = 0; i < nums.length; i++) { coverrange = Math.max(nums[i] + i, coverrange); if (coverrange == i) { break; } } return coverrange >= nums.length - 1 ? true : false; } }

class Solution { // 按照第数组中的第一个元素排序，排序之后 // 后一个数组的左端点如果小于前一个数组的右端点则需要合并 // 两种情况：1.后一个数组的左端点小于前一个数组的右端点，则直接合并前一个数组 // 2.后一个数组的左端点大于于前一个数组的右端点，则取前一个数组的左端点和后一个数组的右端点 // 由于合并之后的元素个数我们并不知道，所以一开始要用一个list存储结果 public int[][] merge(int[][] intervals) { int n = intervals.length; // 列已知为2 Arrays.sort(intervals, (a,b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0])); List<int[]> merge = new ArrayList<>(); for (int i = 0; i < n; i++) { // intevlas[i][1]与merge中最后一个数组的[1]进行比较 if (merge.isEmpty() || intervals[i][0] > merge.get(merge.size() - 1)[1]) { merge.add(intervals[i]); } else { merge.get(merge.size() - 1)[1] = Math.max(merge.get(merge.size() - 1)[1], intervals[i][1]); } } int row = merge.size(); int[][] res = new int[row][2]; for (int i = 0; i < row; i++) { for (int j = 0; j < 2; j++) { res[i][j] = merge.get(i)[j]; } } return res; } }

class Solution { // 动态规划 // dp[i][j] 代表从（0,0）出发到(i,j)有多少条不同的路径 // dp[i][j] = dp[i-1][j] + dp[i][j-1]; // 左边界和上边界都只有1种可能 // 从上向下，从左往右遍历 int res = 0; public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; dp[0][0] = 1; for(int i = 1; i < m;i++){ dp[i][0] = 1; } for(int j = 1; j < n; j++){ dp[0][j] = 1; } for(int i = 1 ; i < m; i++){ for(int j = 1; j < n; j++){ dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m-1][n-1]; } }

class Solution { // 原地排序 冒泡排序 选择排序 快速排序 插入排序 // 快排 平均 O（nlogn） 最差O(n^2) 最好是O(nlogn) public void sortColors(int[] nums) { quickSort(nums, 0, nums.length - 1); } public void quickSort(int[] nums, int low, int high) { if (low < high) { int index = partition(nums, low ,high); quickSort(nums, low ,index - 1); quickSort(nums, index + 1,high); } } public int partition(int[] nums, int low, int high) { // partition分区 int pivot = nums[high]; // pivot基准 int j = low; for (int i = low; i < high; i++) { if (nums[i] < pivot) { swap(nums, i, j); j++; } } swap(nums,j, high); return j; } public void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }