Interview-Notes

class Solution { // 动态规划 // dp[i] 代表以i结尾的最长有效括号子串的长度 // s.charAt(i) == '( dp[i] = 0; // s.charAt(i) == ')' s.charAt(i - 1) = '(' dp[i] = dp[i - 2] + 2 // if (i - dp[i - 1] - 2 >= 0)s.charAt(i - dp[i - 1] - 1) == '(' dp[i] = dp[i-1] + 2 + dp[i - dp[i - 1] - 2] // 初始化dp[0] = 0; // 遍历顺序 从左向右 public int longestValidParentheses(String s) { int len = s.length(); int[] dp = new int[len]; int maxLen = 0; for (int i = 1; i <= len - 1; i++) { if (s.charAt(i) == ')') { if (s.charAt(i-1) == '(') { dp[i] = (i >= 2 ? dp[i-2] : 0) + 2; maxLen = Math.max(maxLen,dp[i]); } else if (i-1 >= dp[i-1] && dp[i-1] > 0 && s.charAt(i-dp[i-1]-1) == '(') { // 需要判断dp[i-1] > 0 dp[i] = (i - dp[i-1] >= 2)? dp[i-1] + dp[i-dp[i-1]-2] + 2 : dp[i-1] + 2; } maxLen = Math.max(dp[i],maxLen); } } return maxLen; } }

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]; } }

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { //对于每一个节点，都有选或者不选两种决定 //选了该节点，则它的左子节点和右子节点不能选 //设定一个数组，下标0代表选了该节点的最大偷盗金额，下标1代表未选择该节点的最小偷盗金额 // dfs + dp // 时间复杂度O(n),空间复杂度O(n); 每个节点遍历一次 public int rob(TreeNode root) { int[] res = dfs(root); // res[]记录选root和不选root可以偷窃的最大值 return Math.max(res[0], res[1]); } public int[] dfs(TreeNode root) { if (root == null) { return new int[]{0,0}; } int[] left = dfs(root.left); int[] right = dfs(root.right); int selected = root.val + left[1] + right[1]; int noSelected = Math.max(left[0], left[1]) + Math.max (right[0], right[1]); return new int[]{selected, noSelected}; } }

class Solution { //两重for循环计算 public boolean canPartition(int[] nums) { int sum = 0; for(int i = 0; i < nums.length; i++) { sum += nums[i]; } if(sum % 2 == 1) return false; int target = sum / 2; boolean[] dp = new boolean[target + 1]; //dp数组代表容量为j的背包能否恰好装满 dp[0] = true; for (int i = 0; i < nums.length; i++) { for (int j = target; j >= nums[i]; j--) { dp[j] = dp[j] || dp[j-nums[i]]; } } return dp[target]; } }

class Solution { //下标i处能接的雨水为左右两边的最大值里的最小值- height[i] // 这里可以用双指针的思想 时间复杂度O(n),空间复杂度O(1) // 动态规划更直接， 用两个数组记录左右两边的最大值 时间复杂度O(n),空间复杂度O(1) public int trap(int[] height) { int n = height.length; // int[] leftMax = new int[n]; // int[] rightMax = new int[n]; // leftMax[0] = height[0]; // rightMax[n - 1] = height[n - 1]; // for (int i = 1; i < n; i++) { // leftMax[i] = Math.max(leftMax[i-1], height[i]); // } // for (int i = n - 2; i >= 0; i--) { // rightMax[i] = Math.max(rightMax[i + 1], height[i]); // } // int sum = 0; // for (int i = 0; i < n; i++) { // sum += Math.min(leftMax[i], rightMax[i]) - height[i]; // } // return sum; int leftMax = 0, rightMax = 0; int left = 0,right = n - 1, sum = 0; while (left <= right) { leftMax = Math.max(height[left], leftMax); rightMax = Math.max(height[right], rightMax); if (leftMax < rightMax) { sum += leftMax - height[left]; left++; } else { sum += rightMax - height[right]; right--; } } return sum; } }

class Solution { // 首先想到的是回溯，但是回溯的时间复杂度过大（2^n); // 想到背包问题： // 两个背包，一个放正数，一个放负数， // pos[i] - neg[i] = target; // pos[i] + neg[i] = sum; // pos[i] = (target + sum) / 2 public int findTargetSumWays(int[] nums, int target) { int sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; } //(target + sum)必须是偶数（否则 P 不是整数） //(target + sum)不能是负数（否则不可能） if ((target + sum) % 2 != 0 || (target + sum) < 0) { return 0; } int[] pos = new int[(target + sum) / 2 + 1]; pos[0]= 1; //pos[i] 代表容量为i的背包有多少种方式填满 for (int i = 0; i < nums.length; i++) { for (int j = (target + sum) / 2; j >= nums[i]; j--) { pos[j] += pos[j-nums[i]]; } } return pos[(target + sum) / 2]; } }

class Solution { //最长回文子串，动态规划， //dp[i][j]代表从i到j的最长回文子串的长度 //初始化的dp[i][i] = 1 //遍历顺序：按长度遍历，再从左到右按索引遍历 public String longestPalindrome(String s) { // char[] arr = s.toCharArray(); // 反序与原始字符串相同，动态规划 // 如果s.substring(i,j)是回文子串，则s.substring(i+1,j-1)一定也是回文子串 // 每一个字符一定是回文子串，判断2个长度的字符串是不是回文子串只需要判断两个字符是否相等 // 用二维哈希表来表示所有子串是不是回文子串，行下标与列下标的最大差值代表长度 // int len = arr.length; // if(len < 2){ //长度小于2说明是动态数组 // return s; // } // boolean[][] hash = new boolean[len][len]; // int maxLen = 1; // int begin = 0; // for(int i = 0 ; i < len; i++){ // hash[i][i] = true; // 单个字符一定是回文串 // } // for(int L = 2; L <= len; L++){ //L代表的长度 // for(int i = 0 ; i < len; i++){ //左边界，字符串的起始下标 // int j = L + i - 1; //子字符串的长度为L, j - i + 1 = L; // if( j >= len){ // break; // } // if(arr[i] != arr[j]){ // 子字符串长度小于等于3的时候，只需要看左右边界 // hash[i][j] = false; // 子字符串长度>3的时候，hash[i][j] = hash[i+1][j-1]; // }else { // if(L <= 3){ // hash[i][j] = true; // }else{ // hash[i][j] = hash[i+1][j-1]; // } // } // if(hash[i][j]&& L > maxLen){ // maxLen = L; // begin = i; // } // } // } // return s.substring(begin,begin+maxLen); // 不包括begin+maxLen int n = s.length(); if (n == 1) { return s; } boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = true; } int maxLen = 1; int begin = 0; for (int i = 2; i <= n; i++) { for (int j = 0; j < n;j++) { int k = j + i - 1; if(k >= n) { break; } if (i <= 3) { if (s.charAt(j) == s.charAt(k)) { dp[j][k] = true; }else { dp[j][k] = false; } } else { if (s.charAt(j) == s.charAt(k)) { dp[j][k] = dp[j +1][k - 1] ; }else { dp[j][k] = false; } } if (dp[j][k] && i > maxLen ) { maxLen = i; begin = j; } } } return s.substring(begin,begin+maxLen); } }

class Solution { public int maxSubArray(int[] nums) { // dp数组代表以nums[i]结尾的的最大子数组和，i代表索引 // if (dp[i-1] < 0) dp[i] = nums[i]; // else dp[i] = dp[i-1] + nums[i]; // 找到dp数组的最大值 int[] dp = new int[nums.length]; int max = nums[0]; dp[0] = nums[0]; for (int i = 1; i < nums.length; i++) { dp[i] = Math.max(dp[i-1] + nums[i], nums[i]); max = Math.max(dp[i],max); } return max; } }

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 { //二维动态规划 public int countSubstrings(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = 1; } for(int len = 2; len <= n; len++) { for (int i = 0; i <= n-len; i++) { int j = i + len - 1; if(s.charAt(i) == s.charAt(j)){ if (len > 2) { dp[i][j] = dp[i + 1][j - 1]; } else { dp[i][j] = 1; } }else { dp[i][j] = 0; } } } int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dp[i][j] != 0){ count++; } } } return count; } }