Interview-Notes

class Solution { List<List<Integer>> res = new ArrayList(); List<Integer> path = new LinkedList(); public List<List<Integer>> subsets(int[] nums) { backTracking(nums,0); return res; } public void backTracking(int[] nums,int startIndex){ res.add(new ArrayList(path)); if(startIndex >= nums.length){ return; } for(int i = startIndex; i < nums.length ; i++){ path.add(nums[i]); backTracking(nums,i+1); // 这里是i + 1 path.removeLast(); } } }

class Solution { // 1.暴力求解，两重for循环分别代表起始元素 // 2.用HashMap,时间复杂度为O(n),空间复杂度为O(n); // 两个数之和 = target 那么就是target - 其中一个数 = 另外一个target // 一重for循环，遍历整个数组，将出现过的值加入到hashmap中，key为值，value为索引 // 对于当前元素，hashmap.contiansKey(target - value) ，则找到两个数 public int[] twoSum(int[] nums, int target) { int[] res = new int[2]; HashMap<Integer, Integer> hs = new HashMap(); for (int i = 0; i < nums.length; i++) { int value = target - nums[i]; if (hs.containsKey(value)) { res[1] = i; res[0] = hs.get(value); break; } hs.put(nums[i],i); } return res; } }

class Solution { public int maxArea(int[] height) { // 暴力复杂度为O(n^2) // 双指针：时间复杂度为）（n） //最大容量：索引的差*两个索引最小高度； int left = 0, right = height.length - 1; int maxArea = 0; while (left < right) { int area = Math.min(height[left], height[right]) *(right - left); maxArea = Math.max(area, maxArea); if (height[left] > height[right]) { //宽已经是最大了，想要更大的面积只能是更大的高 right--; } else { left++; } } return maxArea; } }

class Solution { // 排序之后，使用双指针,左右指针，注意去重 // 时间复杂度O(n^2)，空间复杂度:排序的复杂度O(logn) + 三数列表的个数O(m) public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); // 排序 int n = nums.length; for (int i = 0; i < n - 2; i++) { if (i > 0 && nums[i]== nums[i-1]) { //外部去除 continue; } int target = -nums[i]; int left = i + 1, right = n - 1; while (left < right) { if (nums[left] + nums[right] < target) { left++; } else if (nums[left] + nums[right] > target) { right--; } else { res.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left < right && nums[right] == nums[right - 1]) { //内部去重 right--; } while (left < right && nums[left] == nums[left + 1]) { left++; } left++; right--; } } } return res; } }

class Solution { //用堆排序实现，删除前k-1个元素皆可以得到第k大的元素 // 要求O(n),但是O(nlogn)可以通过 public int findKthLargest(int[] nums, int k) { // int n = nums.length; // buildMaxHeap(nums); // for (int i = n - 1; i > n - k; i--) { // swap(nums,0,i); // heapify(nums,i,0); // } // return nums[0]; PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)-> b-a); for (int i = 0; i < nums.length; i++) { pq.offer(nums[i]); } for (int i = 0; i < k - 1; i++) { pq.poll(); } int val = pq.poll(); return val; } // public void buildMaxHeap(int[] arr) { // int n = arr.length; // for (int i = n / 2 - 1; i >= 0; i--) { // heapify(arr,n,i); // } // } // public void heapify(int[] arr, int n ,int i) { // int largest = i; // int left = 2 * i + 1; // int right = 2 *i + 2; // if (left < n && arr[left] > arr[largest]) { // largest = left; // } // if (right < n && arr[right] > arr[largest]) { // largest = right; // } // if (largest != i) { // swap(arr,largest,i); // heapify(arr,n,largest); // } // } // public void swap(int[] arr, int i ,int j) { // int temp = arr[i]; // arr[i] = arr[j]; // arr[j] = temp; // } }

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 boolean searchMatrix(int[][] matrix, int target) { //从矩阵的左下角或者右上角开始遍历,时间复杂度O(m + n) int m = matrix.length; int n = matrix[0].length; int i = m - 1; int j = 0; while (i >= 0 && j < n) { if (matrix[i][j] == target) { return true; } else if(matrix[i][j] > target) { i--; } else { j++; } } return false; } }

class Solution { // 用一个指针标记此新的数组的当下元素的索引 // 对整个数组进行遍历，遍历完之后剩下的部分全部赋值为0 // 或者说快慢指针，快指针用来遍历数组，慢指针用来指向移动后当前索引的元素 public void moveZeroes(int[] nums) { int slow = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] != 0) { nums[slow++] = nums[i]; } } for (int i = slow; i < nums.length; i++) { nums[i] = 0; } } }

class Solution { public int findDuplicate(int[] nums) { // 1.二分查找 计算数组中小于等于该元素数量的个数，如果数量 > 该元素的值，说明，重复元素在l,元素区间内 // 2.Floyd判圈算法 // 快慢指针找相遇点 慢指针一次走一步，快指针一次走两步 // 然后将其中一个指针移动到出发点 // 两个指针的相遇点即为所求 // 可以以i->nums[i]构建链表，有重复数字，说明有环 int low = 0, high = nums.length -1; while (low < high) { int mid = low + (high - low) / 2; int count = 0; for (int i = 0; i < nums.length ; i++) { if (nums[i] <= mid) { count++; } } if (count <= mid) { low = mid + 1; } else { high = mid ; } } return low; // int slow = nums[0]; // int fast = nums[nums[0]]; // while (slow != fast) { // slow = nums[slow]; // fast = nums[nums[fast]]; // } // fast = 0; // while (slow != fast) { // slow = nums[slow]; // fast = nums[fast]; // } // return fast; } }

class Solution { //动态规划 //动态规划四部曲：确定dp[]数组及下标对应的含义，递推公式、初始化、遍历顺序 // 三种状态： 持有股票，不持有股票并且处于冷冻期，不持有股票并且不处于冷冻期对应dp[i][0],dp[i][1],dp[i][2]; // 递推公式：dp[i][0] = dp[i-1][2] - prices[0]; // dp[i][1] = dp[i][0] + prices[i] dp[i][2] = dp[i-1][1]; public int maxProfit(int[] prices) { int n = prices.length; int[][] dp = new int[n][3]; dp[0][0] = -prices[0]; dp[0][1] = 0; dp[0][2] = 0; for (int i = 1; i < prices.length; i++) { dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2] - prices[i]); dp[i][1] = dp[i-1][0] + prices[i]; dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1]); } return Math.max(dp[n-1][1],dp[n-1][2]); } }