LingLing practices 40 hours per day. How about you?
动态规划
很多动态规划问题大致可以按照下面5个步骤取解释： 1、状态定义 2、状态转移方程 3、初始化 4、输出 5、思考状态压缩
动态规划原理
都是把大问题拆分成小问题。寻找大问题和小问题的递推关系。解决一个个小问题，最终达到解决原问题的效果。动态规划有记忆性，填表把所有已经解决的子问题答案记录下来,在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。
198 打家劫舍
如果房间数量 大于 2间。偷前k间房屋的最大金额。
- 如果偷第k间屋子，就不能偷第k-1间屋子，总金额为前k-2间房屋的最高总金额和第k间房屋的金额之和。
- 不偷第k间屋子，总金额为偷前k-1间屋子的最高金额。
用dp[i]表示偷前i间屋子可以偷到的最高金额。
class Solution {
public int rob(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
int length = nums.length;
if(length == 1)
return nums[0];
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for(int i=2;i<length;i++){
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[length-1];
}
}
213 打家劫舍2
题目描述：房屋都围成一圈，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
解题思路：在打家劫舍1的基础上，说给出的房子是环形排列首尾相接的。区别就是第一栋房子和最后一栋房子不能同时偷。只需要计算两种情况：
- 不偷第一个，问题就是在后边n-1个房子可以偷的最大价值。
- 不偷最后一个，问题就是在前边n-1个房子可以偷的最大价值。
这样转换就没有首尾连接的约束了，可以直接采用上一题的解法。取两种情况的最大值
class Solution {
public:
//首尾之能选一个偷
int rob(vector<int>& nums) {
//思想很简单，不偷第一家，就在后面n-1家里偷，不偷最后一家，就在前n-1家里偷
int len=nums.size();
if(len==0)
return 0;
if(len==1)
return nums[0];
int ans1 = rob1(nums, 0, len-2);
int ans2 = rob1(nums, 1, len-1);
return max(ans1,ans2);
}
int rob1(vector<int> &nums, int l, int r){
int ans = 0;
int pre=0,prepre=0;
for(int i=l;i<=r;i++){
ans = max(prepre+nums[i], pre);
prepre = pre;
pre = ans;
}
return ans;
}
};
213 打家劫舍3
题目描述：房屋成一个二叉树结构，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
解题思路：结点r，分为偷和不偷两种情况。
偷r结点：左右儿子不能偷。最大价值等于不偷左儿子的最大价值+不偷右儿子的最大价值+r的价值
不偷r节点： 最大价值等于偷或不偷左儿子的最大价值+偷或不偷右儿子的最大价值。
class Solution {
public:
typedef pair<int, int> pii;
int rob(TreeNode* root) {
// 可行窃地区是二叉树
if(root==nullptr)
return 0;
pii ans = helper(root);
return max(ans.first, ans.second);
}
//偷r结点：左右儿子不能偷。最大价值等于不偷左儿子的最大价值+不偷右儿子的最大价值+r的价值
//不偷r节点： 最大价值等于**偷或不偷**左儿子的最大价值+**偷或不偷**右儿子的最大价值。
pii helper(TreeNode* root){
if(root==nullptr)
return {0,0};
//helper 返回 偷 这个结点能取到的最大价值，还有 不偷 这个结点时能取到的最大价值
pii l = helper(root->left);
pii r = helper(root->right);
//偷
int r0 = l.second+r.second+root->val;
//不偷当前
int r1 = max(l.first,l.second)+max(r.first,r.second);
return make_pair(r0,r1);
}
};
740. 删除与获得点数
给定一个整数数组 nums ，你可以对它进行一些操作。 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
解题思路：
转换成打家劫舍：我们在原来的 nums 的基础上构造一个临时的数组 all，这个数组，以元素的值来做下标，下标对应的元素是原来的元素的个数。 举个例子： nums = [2, 2, 3, 3, 3, 4] 构造后： all=[0, 0, 2, 3, 1]; 就是代表着 22 的个数有两个，33 的个数有 33 个，44 的个数有 11 个。 其实这样就可以变成打家劫舍的问题了
class Solution {
public int deleteAndEarn(int[] nums) {
int n = nums.length;
if(n==0) return 0;
int max = 0;
for(int num: nums){
max = Math.max(max, num);
}
int[] all = new int[max+1];
for(int i=0; i<n;i++){
all[nums[i]]++;
}
int[] dp = new int[max+1];
if(max==1)
return all[1];
if(max==2)
return Math.max(all[1], 2*all[2]);
dp[1] = all[1];
dp[2] = Math.max(all[1], 2*all[2]);
for(int i=3;i<=max;i++){
dp[i] = Math.max(dp[i-2]+all[i]*i,dp[i-1]);
}
return dp[max];
}
}
72 编辑距离
题目描述：删除，修改，插入，把word1变成word2的最小编辑距离
思路：动态规划，D[i][j]表示word1的前i个字母和word2的前j个之间的编辑距离。
-
D[i][j-1]为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们在 A 的末尾添加了一个相同的字符，那么D[i][j]最小可以为D[i][j-1] + 1； -
D[i-1][j]为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题。即对于 A 的第 i 个字符，我们在 B 的末尾添加了一个相同的字符，那么D[i][j]最小可以为D[i-1][j] + 1； -
D[i-1][j-1]为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们修改 A 的第 i 个字符使它们相同，那么D[i][j]最小可以为D[i-1][j-1] + 1。特别地，如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。在这种情况下，D[i][j]最小可以为D[i-1][j-1]。
如果word1[i]==word2[j]: \(\begin{aligned} D[i][j] &=\min (D[i][j-1]+1, D[i-1][j]+1, D[i-1][j-1]) \\ &=1+\min (D[i][j-1], D[i-1][j], D[i-1][j-1]-1) \end{aligned}\) 如果word1[i]!=word2[j]: \(D[i][j]=1+\min (D[i][j-1], D[i-1][j], D[i-1][j-1])\)
int minDistance(string word1, string word2) {
int n = word1.length();
int m = word2.length();
// 有一个字符串为空串
if (n * m == 0) return n + m;
// DP 数组
int D[n + 1][m + 1];
// 边界状态初始化
for (int i = 0; i < n + 1; i++) {
D[i][0] = i;
}
for (int j = 0; j < m + 1; j++) {
D[0][j] = j;
}
// 计算所有 DP 值
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
int left = D[i - 1][j] + 1;
int down = D[i][j - 1] + 1;
int left_down = D[i - 1][j - 1];
if (word1[i - 1] != word2[j - 1]) left_down += 1;
D[i][j] = min(left, min(down, left_down));
}
}
return D[n][m];
}
32. 最长有效括号 7月4日
题目链接 给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
栈的思想，栈底是「最后一个没有被匹配的右括号的下标」
class Solution {
public int longestValidParentheses(String s) {
//最长有效括号
//栈的思想的话，栈底是「最后一个没有被匹配的右括号的下标」
Stack<Integer> stc = new Stack<>();
stc.push(-1);
int len = s.length();
int ans = 0;
for(int i=0;i<len;i++){
if('('==s.charAt(i)){
stc.push(i);
}else{
stc.pop();
if(stc.empty()){
stc.push(i);
}else{
ans = Math.max(ans, i-stc.peek());
}
}
}
return ans;
}
}
416 分割等和子集
题目描述：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
解题思路：
动态规划，转换01背包问题
boolean[][] dp 数组初始化的时候默认就是false，dp[i][j] 表示 编号范围在[0,i] 的数字，能够从中选出和为j的数组出来。
2种边界情况：
- 对于所有的
i，dp[i][0] = true i==0时，dp[0][nums[0]] = true;
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
if (n < 2) {
return false;
}
int sum = 0, maxNum = 0;
for (int num : nums) {
sum += num;
maxNum = Math.max(maxNum, num);
}
if (sum % 2 != 0) {
return false;
}
int target = sum / 2;
if (maxNum > target) {
return false;
}
boolean[][] dp = new boolean[n][target + 1]; //初始状态 dp全部都是`false`
for (int i = 0; i < n; i++) {
dp[i][0] = true;
}
dp[0][nums[0]] = true;
for(int i=1; i< n; i++){
int num = nums[i];
for(int j=1; j <= target; j++){
if(j>=num)
dp[i][j] = dp[i-1][j-num] | dp[i-1][j];
else
dp[i][j] = dp[i-1][j];
}
}
return dp[n-1][target];
}
}
125. 乘积最大子数组
因为乘法有正负数的情况，子问题可能不是从i-1这个状态变过来的。
也没有用复杂的动态规划，就是在维护一个数组记录以nums[i]结尾的子数组乘积的最小值。
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int[] Fmax = new int[n];
int[] Fmin = new int[n];
System.arraycopy(nums, 0, Fmax, 0, n);
System.arraycopy(nums, 0, Fmin, 0, n);
for(int i=1;i<n;i++){
int num = nums[i];
Fmax[i] = Math.max(Fmax[i-1]*num, Math.max(Fmin[i-1]*num, num));
Fmin[i] = Math.min(Fmax[i-1]*num, Math.min(Fmin[i-1]*num, num));
}
int ans = Fmax[0];
for(int i=1;i<n;i++){
ans = Math.max(ans, Fmax[i]);
}
return ans;
}
}
1143. 最长公共子序列
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
char[] chars1 = text1.toCharArray();
char[] chars2 = text2.toCharArray();
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m+1][n+1];
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if( chars1[i-1]==chars2[j-1] ){
dp[i][j] = dp[i-1][j-1]+1;
}else{
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[m][n];
}
}
97. 交错字符串
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length();
int n = s2.length();
int t = s3.length();
if (n + m != t) {
return false;
}
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true;
for(int i=0; i<=m; i++)
for(int j=0; j<=n; j++)
{
int p = i + j - 1;
if(i > 0){
dp[i][j] = dp[i][j] || (dp[i-1][j] && s1.charAt(i-1)==s3.charAt(p));
}
if(j > 0)
{
dp[i][j] = dp[i][j] || (dp[i][j-1] && s2.charAt(j-1)==s3.charAt(p));
}
}
return dp[m][n];
}
}
二叉树非递归遍历
前序遍历非递归
class Solution{
public void flatten(TreeNode root){
List<TreeNode> list = new ArrayList<TreeNode>();
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode node = root;
while(node!=null || !stack.isEmpty()){
while(node!=null){
list.add(node);
stack.push(node);
node=node.left;
}
node=stack.pop();
node=node.right;
}
int size = list.size();
for(int i=1; i<size;i++){
TreeNode prev = list.get(i-1);
prev.left=null;
prev.right=list.get(i);
}
}
}
中序遍历非递归
用辅助栈
class Solution{
public List<Integer> inorderTraversal(TreeNode root){
List<Integer> list = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
if(root!=null) return list;
TreeNode node = root;
while(node!=null || !stack.empty()){
while(node!=null){
stack.push(node);
node=node.left;
}
if(!stack.empty()){
node=stack.pop();
list.add(node); //访问节点
node=node.right;
}
}
return list;
}
}
后序遍历非递归
- 思路一：
依次将根结点，右节点，左节点押入栈。根->右->左，和先序遍历的
根->右->左，很像，就把先序的左右交换，访问改成压栈，压另一个栈。
class Solution{
public List<Integer> postorderTraversal(TreeNode root){
Stack<Integer> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
if(root==null) return list;
TreeNode node = root;
while(node!=null || !stack.empty()){
while(node!=null){
list.add(node);
stack.push(node);
node=node.right;
}
if(!stack.empty()){
node=stack.pop();
node=node.left;
}
}
Collections.reverse(list);
return list;
}
}
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> ans = new LinkedList<>();
if (null == root) return ans;
stack.addFirst(root);
while(!stack.isEmpty()) {
TreeNode node = stack.removeFirst();
ans.addFirst(node.val);
if (null != node.left) {
stack.addFirst(node.left);
}
if (null != node.right) {
stack.addFirst(node.right);
}
}
return ans;
}
}
- 思路二：
要访问一个节点的条件上一个访问的节点是右儿子。我们可以增加一个变量Prev来判断当前节点Curr的上一个节点与它的关系来执行相应的操作。
- 若Prev为空(Curr节点是根节点)或者Prev是Curr的父节点，将Curr节点的左孩子和右孩子分别压入栈；
- 若Prev是Curr的左儿子，则将Curr的右儿子压入栈；
- 否则Prev是Curr的右儿子，访问Curr;
class Solution{
public List<Integer> postorderTraversal(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
if(root==null) return list;
TreeNode prev = null, cur = null;
stack.push(root);
while(!stack.empty()){
cur = stack.peek();//不要弹出
if(prev==null || prev.left==cur || prev.right==cur){
if(cur.left!=null)
stack.push(cur.left);
else if(cur.right!=null)
stack.push(cur.right);
}else if(prev == cur.left){
if(cur.right!=null)
stack.push(cur.right);
}else{
list.add(cur.val);
stack.pop();
}
prev = cur;
}
return list;
}
}
贪心
55. 跳跃游戏
贪心策略，总是跳到“最大下一跳距离最大”的位置
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
if(n<=1){
return true;
}
int now = 0;
int next = 0;
while(now < n-1){
int maxDistance = now + nums[now];
if(maxDistance < now+1) return false;
next = now+1;
int max = now+1 + nums[now+1];
for(int i=now+2; i<=maxDistance && i<n;i++){
if(i+nums[i] > max){
max = i + nums[i];
next = i;
}
}
now = next;
}
return true;
}
}
二分查找
left，right。怎么确定每一步left和right的移动方式。
mid = (left+right)/2和mid = (left+right+1)/2两种不一样，第一种需要right=mid;else left=mid+1。第二种需要left = mid; else right = mid-1。原因在于计算确定mid的方法有区别。
378. 有序矩阵中第K小的元素
二分法是解法之一，每次得到二分数组mid，然后计算矩阵中 <mid的个数。
class Solution {
public int kthSmallest(int[][] matrix, int k) {
//二分法查找
int n = matrix.length;
if(n<=0){
return -1;
}
//假设K永远有效
int left = matrix[0][0];
int right = matrix[n-1][n-1];
int mid;
while(left<right){
mid = (left+right)/2;
if(check(matrix, k, n,mid)){
right = mid;
}else{
left = mid+1;
}
}
return left;
}
private boolean check(int[][] matrix, int k, int n, int mid){
int num=0;
//左下角开始搜索
int i=n-1;
int j=0;
while( i>=0 && j<n ){
if(matrix[i][j]<=mid){
j++;
num+=(i+1);
}else{
i--;
}
}
return num>=k;
}
}
778. 水位上升的泳池中游泳
在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。
现在开始下雨了。当时间为 t 时，此时雨水导致水池中任意位置的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。
你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1, N-1)？
什么时候可以联通，答案是一个单调函数，就可以用二分查找来做，找到最少耗时。
class Solution {
private int[] di = {1,-1,0,0};
private int[] dj = {0,0,-1,1};
public int swimInWater(int[][] grid) {
int N = grid.length;
if(N<=0) return -1;
int low = 0;
int high = N*N;
while(low<high){
int mid = (low+high) / 2;
if(possible(mid, grid)){
high = mid;
}else{
low = mid+1;
}
}
return low;
}
private boolean possible(int T, int[][] grid){
int N = grid.length;
Stack<Integer> stack = new Stack<Integer>();
Set<Integer> seen = new HashSet<Integer>();
stack.push(0);
seen.add(0);
if(grid[0][0]>T) return false;
while(!stack.empty()){
int z = stack.pop();
int i = z/N, j = z%N;
if(i==N-1 && j==N-1)
return true;
for(int k = 0; k < 4;k++ ){
int ii = i+di[k], jj = j+dj[k];
int next = ii*N + jj;
if(ii>=0 && ii<N && jj>=0 && jj<N && !seen.contains(next) && grid[ii][jj]<=T){
seen.add(next);
stack.push(next);
}
}
}
return false;
}
}
33. 搜索旋转排序数组
一个升序排列的整数数组 nums ，和一个整数 target 。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1。
条件： nums 中的每个值都 独一无二 nums 肯定会在某个点上旋转
class Solution {
public int search(int[] nums, int target) {
int length = nums.length;
if(length<1)
return -1;
if(length==1) {
return target == nums[0] ? 0 : -1;
}
int left = 0, right = length - 1;
while(left <= right){
int mid = (left + right) / 2;
if(nums[mid]==target)
return mid;
if(nums[0] <= nums[mid]){
if(nums[0] <= target && nums[mid] > target){
right = mid-1;
}else{
left = mid+1;
}
}else{
if(nums[mid]< target && target <= nums[right]){
left = mid+1;
}else{
right = mid-1;
}
}
}
return -1;
}
}
这里的二分查找是一种特殊情况，在[left,right]的范围中只有一个答案满足要求，设答案为ans。
while(left<=right){
mid = (left+right)/2;
p = func(mid);
if(condition(p)){
//找答案
return mid;
}else if(mid大了){
right=mid-1;
}else if(mid小了){
left=mid+1;
}
}
34. 在排序数组中查找元素的第一个和最后一个位置
O(log n) 级别，二分查找
方法一
class Solution {
// returns leftmost (or rightmost) index at which `target` should be
// inserted in sorted array `nums` via binary search.
private int extremeInsertionIndex(int[] nums, int target, boolean left) {
int lo = 0;
int hi = nums.length;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] > target || (left && target == nums[mid])) {
hi = mid;
}
else {
lo = mid+1;
}
}
return lo;
}
public int[] searchRange(int[] nums, int target) {
int[] targetRange = {-1, -1};
int leftIdx = extremeInsertionIndex(nums, target, true);
// assert that `leftIdx` is within the array bounds and that `target`
// is actually in `nums`.
if (leftIdx == nums.length || nums[leftIdx] != target) {
return targetRange;
}
targetRange[0] = leftIdx;
targetRange[1] = extremeInsertionIndex(nums, target, false)-1;
return targetRange;
}
}
方法二，两次二分查找，分别使用(L+R)/2 和 (L+R+1)/2。
class Solution {
public int[] searchRange(int[] nums, int target) {
// 在数组中的开始位置 和 结束位置
// 时间复杂度O(log n)
// 1 找左边
int[] ans = new int[2];
int n = nums.length;
if(n==0) return new int[]{-1,-1};
if(n==1){
if(nums[0]==target) return new int[]{0,0};
return new int[]{-1,-1};
}
int L = 0;
int R = n-1;
while(L < R){
int mid = (L + R) / 2;
if(nums[mid] >= target){
R = mid;
}else{
L = mid+1;
}
}
if(nums[L]!=target) return new int[]{-1,-1};
ans[0] = L;
R = n-1;
while(L < R){
int mid = (L+R+1)/2;
if(nums[mid] <= target){
L = mid;
}else{
R = mid-1;
}
}
ans[1] = R;
return ans;
}
}
数组
31. 下一个排列
class Solution {
public void nextPermutation(int[] nums) {
int length = nums.length;
for(int i=length-2;i>=0; i--){
if(nums[i+1]>nums[i]){
int max = i+1;
for(int j=i+2;j<length;j++){
if(nums[j]>nums[i] && nums[j]<nums[max]){
max=j;
}
}
swap(nums, max, i);
Arrays.sort(nums,i+1,length);
return;
}
}
Arrays.sort(nums);
return;
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
169. 多数元素
分治
class Solution {
public int majorityElement(int[] nums) {
//
int n = nums.length;
return fenzhi(nums, 0, n-1);
}
private int fenzhi(int[] nums, int left, int right){
if(left == right){
return nums[left];
}
int mid = (left+right) / 2;
int leftM = fenzhi(nums, left, mid);
int rightM = fenzhi(nums, mid+1, right);
int leftCount = count(nums, leftM, left, right);
int rightCount = count(nums, rightM, left,right);
return leftCount > rightCount ? leftM : rightM;
}
private int count(int [] nums, int target, int left, int right){
int ans = 0;
for(int i= left; i <= right; i++)
if(nums[i]==target)
ans++;
return ans;
}
}
Boyer-Moore 投票算法
class Solution {
public int majorityElement(int[] nums) {
//
int count = 0;
int target = 0;
for(int num: nums){
if(count == 0){
target = num;
}
count += (target == num) ? 1 : -1;
}
return target;
}
}
数学
279. 完全平方数
搜索、回溯
N皇后
搜索回溯，从左上到右下这个方向的同一条斜线上，行下标和列下标的差相同；从右上到左下这个方向，行下标和列下标的和相同。
通过$\left(2^{n}-1\right) \&\left(\sim\left(\text {columns} \mid \text {diagonals}{1} \mid \text {diagonals}{2}\right)\right)$获得这一行合法的位置。其中$2^{n}$用$1«n$得到
有两个重要位运算性质：
- $x \&(-x)$可以获得$x$的二进制表示中最低位1的位置
- $x \&(x-1)$将$x$的二进制表示中的最低位的 1 置成 0
position二进制的10，表示尝试下标为1的列. queens[row]=1; 100为下标为2的列queens[row]=2;用下面位运算
- 下标等于：
Integer.bitCount(position-1)。
class Solution {
public List<List<String>> solveNQueens(int n) {
int[] queens = new int[n];
Arrays.fill(queens, -1);
List<List<String> > solutions = new ArrayList<List<String>>();
solve(solutions, queens, n, 0, 0, 0, 0);
return solutions;
}
// n, 当前搜索行数，当前列标志，当前 \ 方向斜线标志，当前 / 方向斜线标志。
private void solve(List<List<String>> solutions, int[] queens, int n, int row, int columns, int diagonals1, int diagonals2 ) {
if(row==n){
List<String> board = generateBoard(queens, n);
solutions.add(board);
return;
}
int avaliablePosition = ((1<<n) -1) & (~(columns | diagonals1 | diagonals2));
while(avaliablePosition!=0){
int position = avaliablePosition & (-avaliablePosition); // 比如二进制的10，表示尝试下标为1的列. queens[row]=1; 100为下标为2的列。
avaliablePosition = avaliablePosition & (avaliablePosition - 1);
//计算占用哪一列
int column = Integer.bitCount(position-1);
queens[row] = column;
solve(solutions, queens, n, row+1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
queens[row] = -1; //回溯
}
}
private List<String> generateBoard(int[] queens, int n){
// queens放的是每一行，皇后所在列的下标
List<String> board = new ArrayList<String>();
for(int i=0; i<n ; i++){
char[] row = new char[n];
Arrays.fill(row , '.');
row[queens[i]] = 'Q';
board.add(new String(row));
}
return board;
}
}
N皇后II
返回N皇后问题的不同解决方案数量。同样的方法，solve函数返回int，累加起来。
class Solution {
public int totalNQueens(int n) {
return solve(n, 0, 0, 0, 0);
}
public int solve(int n, int row, int columns, int diagonals1, int diagonals2) {
if (row == n) {
return 1;
} else {
int count = 0;
int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
while (availablePositions != 0) {
int position = availablePositions & (-availablePositions);
availablePositions = availablePositions & (availablePositions - 1);
count += solve(n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
}
return count;
}
}
}
139. 单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
- 暴力，超时
class Solution { public boolean wordBreak(String s, List<String> wordDict) { if("".equals(s)) return true; for(int i = 0; i < s.length(); i++){ String str = s.substring(0,i+1); if(wordDict.contains(str) && wordBreak(s.substring(i+1), wordDict)) return true; } return false; } } - 回溯+记忆化，一个
Boolean数组保存后缀是否可以匹配class Solution { public boolean wordBreak(String s, List<String> wordDict) { return help(s, new HashSet(wordDict), new Boolean[s.length()], 0); } public boolean help(String s, List<String> wordDict, Boolean [] memo, int start){ if(start==s.length()) return true; if(memo[start]!=null)//true和false都保存 return memo[start]; for(int i = start; i < s.length(); i++){ String str = s.substring(start,i+1); if(wordDict.contains(str) && help(s, wordDict, memo, i+1)){ return memo[start]=true; } } return memo[start] = false; } }
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
if("".equals(s))
return true;
int length = s.length();
HashSet<String> dict = new HashSet<>(wordDict);
Boolean[] memo = new Boolean[length]; //要用 大写开头的 Boolean
return wordBreak(s, 0, length, dict, memo);
}
private boolean wordBreak(String s, int startIndex, int length, HashSet<String> dict, Boolean[] memo){
if(startIndex==length)
return true;
if(memo[startIndex]!=null)
return memo[startIndex];
for(int i=startIndex; i<length; i++){
String substr = s.substring(startIndex, i+1);
if(dict.contains(substr)){
if(wordBreak(s, i+1, length, dict,memo)){
return memo[startIndex] = true;
}
}
}
return memo[startIndex] = false;
}
}
Leetcode 37 数独
像游戏的题目，9*9的格子。 输入9行，每行为空格隔开的9个数字，为0的地方就是需要填充的。 要求每行每列数字各不相同，并且每个小九宫格里面的数字也各不相同。典型的方法是回溯法，根据某一个格子里填入的数字，继续搜索下一个可以填入的数字。
| 参考：[编程题 | 解数独问题 （Leetcode 37题）](https://blog.csdn.net/weixin_43795395/article/details/105404358) |
DFS，成功了返回True，不继续往下面搜索，也跟着返回true；如果搜索失败了，回溯，继续搜索。
下面的方法用3个成员，记录了每行，每列，每个小方格已经使用的数字数量。利用bitset.count()，bitset.test()，bitset.size()来处理。
c++
class Solution {
public:
//得到所有能填的数字
bitset<9> getPossibleStatus(int x, int y)
{
return ~(rows[x] | cols[y] | cells[x/3][y/3]);
}
//使用 getNext() 选择能填的数字最少的格子开始填，这样填错的概率最小，回溯次数也会变少
vector<int> getNext(vector<vector<char>>& board)
{
vector<int> ret;
int minCnt = 10;
for(int i=0; i<9; i++)
for(int j=0; j < 9; j++)
{
if(board[i][j]!='.')continue;
auto remain = getPossibleStatus(i,j);
if(remain.count()>=minCnt) continue;
ret = {i, j}; // ret表示位置
minCnt = remain.count();
}
return ret;
}
// 在填入和回溯时负责更新存储信息
void fillNum(int x, int y, int n, bool fillFlag)
{
rows[x][n] = fillFlag ? 1 : 0;
cols[y][n] = fillFlag ? 1 : 0;
cells[x/3][y/3][n] = fillFlag ? 1 : 0;
}
bool dfs(vector<vector<char>>& board, int cnt)
{
if(cnt==0) return true;
auto next = getNext(board);
auto bits = getPossibleStatus(next[0], next[1]);
for(int i=0; i<bits.size(); i++){
if(!bits.test(i)) continue;
board[next[0]][next[1]] = '1'+i;
fillNum(next[0],next[1],i, true);
if(dfs(board, cnt-1)){
return true;
}
fillNum(next[0],next[1],i, false);
board[next[0]][next[1]] = '.';
}
return false;
}
void solveSudoku(vector<vector<char>>& board) {
// board
rows = vector<bitset<9>>(9, bitset<9>());
cols = vector<bitset<9>>(9, bitset<9>());
cells = vector<vector<bitset<9>> >(3,vector<bitset<9>>(3, bitset<9>()));
int cnt = 0;
for (int i=0; i < 9; i++)
{
for(int j=0; j < 9; j++){
if(board[i][j]=='.') {
cnt++;
continue;
}
int n = board[i][j] - '1';
rows[i] |= (1<<n);
cols[j] |= (1<<n);
cells[i/3][j/3] |= (1<<n);
}
}
dfs(board, cnt);
}
private:
vector<bitset<9>> rows; // 9行
vector<bitset<9>> cols; // 9列
// 小九宫格 2维,3*3
vector<vector<bitset<9>> > cells;
};
93 复原IP地址
题目链接 需要找出所有方案，进行DFS 回溯搜索。使用Stringbuilder，可以将当前查找的数字用int记录（不需要用string。还可以方便判断是否超过0~255的范围）
class Solution {
private int[] segments;
private List<String> result;
public List<String> restoreIpAddresses(String s) {
int n = s.length();
if (n < 4 || n > 12) {
return new ArrayList<>();
}
char[] chars = s.toCharArray();
segments = new int[4];
result = new ArrayList<>();
// dfs搜索，回溯剪枝条
dfs(s, 0, 0);
return result;
}
private void dfs(String s, int curSeg, int startIndex) {
if(curSeg == 4 && startIndex == s.length()) {
// 完成一个了
StringBuilder sb = new StringBuilder();
for(int i=0; i<4; i++) {
sb.append(segments[i]);
if (i!=3) {
sb.append('.');
}
}
result.add(sb.toString());
return;
}
if (curSeg == 4 || startIndex == s.length()) {
return;
}
// 第一个字符是 ‘0’，不能当作前导0
if (s.charAt(startIndex)=='0') {
segments[curSeg] = 0;
dfs(s, curSeg + 1, startIndex + 1);
return; // 可以return了
}
int curSegNumber = 0;
for(int i = startIndex; i<startIndex+3 && i<s.length() ; i++) {
int num = (s.charAt(i)-'0');
if (curSegNumber < 255 / 10 || (curSegNumber == 255 / 10 && num <= 5)){ //这个逻辑应该用自 超过 int32 的情况下，这里不用这么小心翼翼。
curSegNumber = curSegNumber * 10 + num;
segments[curSeg] = curSegNumber;
dfs(s, curSeg + 1, i + 1);
} else {
break;
}
}
}
}
- 动态规划 状态转移方程：
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int length = s.length();
if(length==0)
return true;
HashSet<String> dict = new HashSet<>(wordDict);
boolean[] dp = new boolean[length+1];
dp[0]=true;
for(int i=1; i<=length; i++){
for(int j=0;j<i;j++){
if(dp[j]==true && dict.contains(s.substring(j,i))){
dp[i]=true;
break;
}
}
}
return dp[length];
}
}
17. 电话号码的字母组合
用两个辅助数组，方便打印选择字符
class Solution {
int[] tint = {0,0,2,5,8,11,14,18,21,25};
int[] count = {0,0,3,3,3,3,3,4,3,4};
public List<String> letterCombinations(String digits) {
//2～9
List<String> ans = new ArrayList<>();
int length = digits.length();
if(length==0) return ans;
char[] chars = new char[length];
dfs(digits, 0, length, ans, chars);
return ans;
}
private void dfs(String digits, int cur, int length, List<String> ans, char[] chars){
if(cur == length){
ans.add(new String(chars));
return;
}
int num = digits.charAt(cur) - '0';
int start = tint[num] - count[num] + 1;
int end = tint[num];
for(int i=start; i<= end; i++){
chars[cur] = (char)('a' + i);
dfs(digits, cur+1, length, ans, chars);
}
}
}
39. 组合总和
数字可以重复使用多次。
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer> > res = new ArrayList<List<Integer>>();
List<Integer> path = new ArrayList<>();
int n = candidates.length;
if( n == 0 ){
return res;
}
search(candidates, res, path, 0, n, target);
return res;
}
private void search(int[] candidates, List<List<Integer> >res, List<Integer> path, int idx, int n, int target){
if(idx == n){
return;
}
if(target == 0){
res.add(new ArrayList<Integer>(path));
return;
}
// 不要第idx个
search(candidates, res, path, idx+1, n, target);
if(target >= candidates[idx]){
path.add(candidates[idx]);
search(candidates, res, path, idx, n, target - candidates[idx]);
path.remove(path.size()-1);
}
}
}
对candidates排序，以减少回溯次数。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<Integer> path = new ArrayList<>();
Arrays.sort(candidates);
backtrack(path,candidates,target,0,0);
return res;
}
private void backtrack(List<Integer> path,int[] candidates,int target,int sum,int begin) {
if(sum == target) {
res.add(new ArrayList<>(path));
return;
}
for(int i = begin;i < candidates.length;i++) {
int rs = candidates[i] + sum;
if(rs <= target) {
path.add(candidates[i]);
backtrack(path,candidates,target,rs,i);
path.remove(path.size()-1);
} else {
break;
}
}
}
}
394. 字符串解码
class Solution {
int ptr;
public String decodeString(String s) {
int n = s.length();
Stack<String> stack = new Stack<>();
ptr = 0;
while(ptr<n){
char c = s.charAt(ptr);
if(Character.isDigit(c)){
String digits = getDigits(s);
stack.push(digits);
} else if(Character.isLetter(c) || c == '['){
stack.push(String.valueOf(c));
ptr++;
} else {
// ']'
++ptr;
Stack<String> sub = new Stack<String>();
while(!"[".equals(stack.peek())){
sub.push(stack.pop());
}
Collections.reverse(sub);
// 左括号出栈
stack.pop();
//之后是个数字
int repeat = Integer.parseInt(stack.pop());
String o = decodeString(sub);
while((repeat--)>0){
stack.push(o);
}
}
}
return decodeString(stack);
}
private String getDigits(String s){
StringBuilder sb = new StringBuilder();
while (Character.isDigit(s.charAt(ptr))){
sb.append(s.charAt(ptr));
ptr++;
}
return sb.toString();
}
private String decodeString(List<String> v){
StringBuilder sb = new StringBuilder();
for(String s : v){
sb.append(s);
}
return sb.toString();
}
}
339 除法求值
思路：链接
class Solution {
static Map<String, String> parents;
static Map<String, Double> val;
public String find(String x) {
if (!x.equals(parents.get(x))) {
String tmpParent = parents.get(x);
String root = find(tmpParent);
double oldVal = val.get(x);
val.put(x, oldVal * val.get(tmpParent));
parents.put(x, root);
}
return parents.get(x);
}
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
parents = new HashMap<>();
val = new HashMap<>();
int i = 0;
for (List<String> equation : equations) {
String from = equation.get(0);
String to = equation.get(1);
double cur = values[i];
if (!parents.containsKey(from) && !parents.containsKey(to)) {
parents.put(from, to);
val.put(from, cur);
parents.put(to, to);
val.put(to, 1.0);
} else if (!parents.containsKey(from)) {
parents.put(from, to);
val.put(from, cur);
} else if (!parents.containsKey(to)) {
parents.put(to, from);
val.put(to, 1 / cur);
} else {
String pa = find(from);
String pb = find(to);
if (!pa.equals(pb)) {
parents.put(pa, pb);
val.put(pa, cur * val.get(to) / val.get(from));
}
}
i++;
}
i = 0;
double[] res = new double[queries.size()];
for (List<String> query : queries) {
String from = query.get(0);
String to = query.get(1);
if (!parents.containsKey(from) || !parents.containsKey(to)) {
res[i++] = -1;
continue;
}
String pa = find(from);
String pb = find(to);
if (!pa.equals(pb)) res[i] = -1;
else {
res[i] = val.get(from) / val.get(to);
}
i++;
}
return res;
}
}
90. 子集 II
数组有重复数字，列举所有子集。
先排序，：[1, 2, 2, 2]
如果上一个位置没有采纳，并且上一个位置的数字和当前数字相同，则return剪枝。
class Solution {
private int n;
private List<List<Integer>> ans;
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
n = nums.length;
ans = new ArrayList<List<Integer> >();
List<Integer> set = new ArrayList<Integer>();
dfs(false, 0, nums, set);
return ans;
}
private void dfs(boolean useLast, int cur, int[] nums, List<Integer> set) {
if( cur==n ){
ans.add(new ArrayList<Integer>(set));
return;
}
// 不要当前
dfs(false, cur+1, nums, set);
if(!useLast && cur>0 && nums[cur-1]==nums[cur])
return;
set.add(nums[cur]);
dfs(true, cur+1, nums, set);
set.remove(set.size()-1);
}
}
链表
反转链表
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev=null;
ListNode cur=head;
while(cur!=null){
ListNode next = cur.next;
cur.next=prev;
prev=cur;
cur=next;
}
return prev;
}
};
反转部分链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (m > 1) {
prev = prev.next;
m--;
n--;
}
head = prev.next;
while (n > 1) {
ListNode next = head.next;
head.next = head.next.next;
next.next = prev.next;
prev.next = next;
n--;
}
return dummy.next;
}
}
或
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode con=null;
ListNode prev=null;
ListNode cur=null;
ListNode next=null;
ListNode tail=null;
cur=head;
while(m>1){
prev=cur;
cur=cur.next;
m--;n--;
}
con=prev;
tail=cur;
while(n>0){
next=cur.next;
cur.next=prev;
prev=cur;
cur=next;
n--;
}
tail.next=cur;
if(con!=null){
con.next=prev;
return head;
}
return prev;
}
}
143. 重排链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
if(head==null || head.next==null){
return;
}
ListNode ptr1=head;
ListNode ptr2=head;
//这种方式找到的 ptr1是中间节点或者 中间靠右的节点 mid=(left+right+1)/2，找到的节点就是最后结果中的尾部
while(ptr2!=null && ptr2.next!=null){
ptr1=ptr1.next;
ptr2=ptr2.next.next;
}
ListNode last = ptr1;
//把last节点后面的全部压入栈里面
Stack<ListNode> stack = new Stack<>();
ptr1=ptr1.next;
while(ptr1!=null){
stack.push(ptr1);
ptr1=ptr1.next;
}
ptr1=head;
while(!stack.empty()){
ptr2=stack.pop();
ptr2.next=ptr1.next;
ptr1.next=ptr2;
ptr1=ptr2.next;
}
last.next=null;
}
}
字符串
面试题 17.13. 恢复空格
把文章断开，要求未识别的字符最少，返回最少的未识别字符数。
这里Tire数是从单词结尾往单词头部倒着连接的。
private Class Trie{
public Trie[] next;
boolean isEnd;
public Trie(){
next = new Trie[26];
isEnd = false;
}
public void insert(String sentence){
char[] chars = sentence.toCharArray();
int n = chars.length;
Trie cur = this;
for(int i=n-1; i>=0; i--){
int t = chars[i]-'a';
if(cur.next[t]==null){
cur.next[t] = new Trie();
}
cur = cur.next[t];
}
cur.isEnd = true;
}
}
动态规划
class Solution {
private class Trie{
public Trie[] next;
boolean isEnd;
public Trie(){
next = new Trie[26];
isEnd = false;
}
public void insert(String sentence){
char[] chars = sentence.toCharArray();
int n = chars.length;
Trie cur = this;
for(int i=n-1; i>=0; i--){
char c = chars[i];
if(cur.next[c-'a']==null){
cur.next[c-'a'] = new Trie();
}
cur = cur.next[c-'a'];
}
cur.isEnd = true;
}
}
public int respace(String[] dictionary, String sentence) {
// 尽量让未匹配的字符数最少
Trie trieTree = new Trie();
for(String s: dictionary){
trieTree.insert(s);
}
int n = sentence.length();
char[] chars = sentence.toCharArray();
int[] dp = new int[n+1];
//动态规划
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0]=0;
for(int i=1;i<=n;i++){
dp[i] = dp[i-1]+1;
Trie cur = trieTree;
for(int j=i;j>=1;j--){
int t = chars[j-1]-'a';
if(cur.next[t]==null) break;
else if(cur.next[t].isEnd){
dp[i] = Math.min(dp[i],dp[j-1]);
}
cur = cur.next[t];
}
}
return dp[n];
}
}
字符串
Z字形变换
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) return s;
StringBuilder sb = new StringBuilder();
int n = s.length();
int period = 2*numRows - 2;
for(int i=0;i<numRows;i++){
for( int j=0; j+i<n;j+=period ){
sb.append(s.charAt(j+i));
if(i!=0 && i!=numRows-1 && j+period-i<n)
sb.append(s.charAt(j+period-i));
}
}
return sb.toString();
}
}
概率题目
比如蓄水池算法相关题目
398. 随机数索引
概率相同，蓄水池抽样算法。 扫描，然后以1, 1/2, 1/3, 1/4…的概率保留当前扫描到的数字。
class Solution {
private int[] nums;
public Solution(int[] nums) {
this.nums = nums;
}
public int pick(int target) {
Random r = new Random();
int index=1;
int ans=0;
int n = nums.length;
for(int i=0;i<n;i++){
if(nums[i]==target){
int j=r.nextInt() % index;
if(j==0){
ans=i;
}
index++;
}
}
return ans;
}
}
382. 链表随机节点
给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
class Solution {
private ListNode head;
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
public Solution(ListNode head) {
this.head = head;
}
/** Returns a random node's value. */
public int getRandom() {
Random r = new Random();
int ans=0;
ListNode node = head;
int i=1;
while(node!=null){
int j = r.nextInt()%i;
if(j==0){
ans = node.val;
}
node=node.next;
i++;
}
return ans;
}
}
结构设计
LRU
用双向链遍，集合，链表中的元素包含<key, value>。包含key是为了，在容量满的时候添加一个元素，删除链表最后的那个数据，能哥获取到key，删除map中的记录。
c++ 可以直接用STL实现
class LRUCache {
private:
list<pair<int, int> > cache;
//
unorder_map<int, list<pair<int, int>>::iterator> map;
int capacity;
public:
LRUCache(int capacity) {
this->capacity = capacity;
}
int get(int key) {
//get
if(map.find(key)!=map.end()){
pair<int,int> p = *map[key];
int val = p.second;
cache.erase(map[key]);
cache.push_front(make_pair(key, val));
map[key]=cache.begin();
return p.second;
}
return -1;
}
void put(int key, int value) {
//put
if(map.find(key)!=map.end()){
pair<int,int> p = *map[key];
list.erase(map[key]);
list.push_front(make_pair(key,value));
map[key]=list.begin();
}else{
if(list.size()>=this->count){
pair<int,int >p = list.back();
int lastKey = p.first;
list.pop_back();
map.erase(lastKey);
}
list.push_front(make_pair(key, value));
map[key]=list.begin();
}
}
};
java稍微写的代码多一点。
public class LRUCache {
private int capacity;
private HashMap<Integer, Node> map = new HashMap<Integer, Node>();
private LinkedList<Node> list = new LinkedList<Node>();
public LRUCache(int capacity) {
this.capacity = capacity;
}
/**
* 如果存在，把当前结点移动到双向链表的头部
*/
public int get(int key) {
if(map.get(key) != null) {
// map找不到
Node node = map.get(key);
list.remove(node);
list.addFirst(node);
map.put(key, node);
return node.value;
}
return -1;
}
/**
* 如果哈希表的容量满了，就要删除一个链表末尾元素，然后在链表头部插入新元素
*
* @param key
* @param value
*/
public void put(int key, int value) {
if(map.get(key)!=null) {
Node node = map.get(key);
list.remove(node);
node.value=value;
list.addFirst(node);
map.put(key,node);
}else{
if(list.size()==this.capacity) {
Node node = list.getLast();
list.removeLast();
map.remove(node.key);
}
Node newNode = new Node(key,value);
list.addFirst(newNode);
map.put(key, newNode);
}
}
}
class Node{
int key;
int value;
Node(int key, int value){
this.key = key;
this.value = value;
}
}
Trie 前缀树
全部都是小写。就用一个26位的数组，代表小写字母的’a’-‘z’。如果包含大写字母或者中文，可以该用字典数据结构HashMap<Character, Trie>的方法。
class Trie {
private Trie[] children;
private boolean isEnd = false;
/** Initialize your data structure here. */
public Trie() {
this.children = new Trie[26];
this.isEnd=false;
}
/** Inserts a word into the trie. */
public void insert(String word) {
char[] chars = word.toCharArray();
Trie node = this;
int n = chars.length;
for(int i=0;i<n;i++){
int t = chars[i]-'a';
if(node.children[t]==null){
node.children[t]=new Trie();
}
node = node.children[t];
}
node.isEnd=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
char[] chars = word.toCharArray();
int n = chars.length;
Trie node = this;
for(int i=0;i<n;i++){
int t = chars[i]-'a';
if(node.children[t]==null){
return false;
}
node = node.children[t];
}
return node.isEnd;
}
/** Returns true if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
char[] chars = prefix.toCharArray();
int n = prefix.length();
Trie node = this;
for(int i=0;i<n;i++){
int t = chars[i]-'a';
if(node.children[t]==null){
return false;
}
node = node.children[t];
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
LFU
最不经常最少使用 LFUCache。
定义两个哈希表，第一个Map<key,node>。第二个Map<freq, list
class LFUCache {
int minfreq, capacity;
Map<Integer, Node> key_table;
Map<Integer, LinkedList<Node>> freq_table;
public LFUCache(int capacity) {
this.minfreq = 0;
this.capacity = capacity;
key_table = new HashMap<Integer, Node>();
freq_table = new HashMap<Integer, LinkedList<Node>>();
}
public int get(int key) {
// 提前预判容量
if (capacity == 0) {
return -1;
}
// 没找到
if (!key_table.containsKey(key)) {
return -1;
}
// 增加访问次数，根据情况看是否需要更新minfreq
Node node = key_table.get(key);
int val = node.val, freq = node.freq;
freq_table.get(freq).remove(node);
if(freq_table.get(freq).size()==0) {
freq_table.remove(freq);
if(minfreq == freq)
minfreq++;
}
// 在频率为`freq+1`对应的双向链表中加入更新后的节点信息
LinkedList<Node> list = freq_table.getOrDefault(freq+1, new LinkedList<Node>());
node = new Node(key, val, freq+1);
list.offerFirst(node);
freq_table.put(freq+1, list);
key_table.put(key, node);
return val;
}
public void put(int key, int val) {
if (capacity==0) {
return;
}
int freq = 1;
if (!key_table.containsKey(key)) {
if (key_table.size() == this.capacity) {
Node node = freq_table.get(minfreq).peekLast();
key_table.remove(node.key);
freq_table.get(minfreq).pollLast();
if(freq_table.get(minfreq).size()==0) {
freq_table.remove(minfreq);
}
}
minfreq = 1;
} else {
Node node = key_table.get(key);
int prevFreq = node.freq;
freq = prevFreq+1;
freq_table.get(prevFreq).remove(node);
if(freq_table.get(prevFreq).size()==0) {
freq_table.remove(prevFreq);
if (minfreq==prevFreq) {
minfreq++;
}
}
}
LinkedList<Node> list = freq_table.getOrDefault(freq, new LinkedList<Node>());
list.offerFirst(new Node(key, val, freq));
freq_table.put(freq, list);
key_table.put(key, freq_table.get(freq).peekFirst());
}
}
class Node {
int key, val, freq;
Node(int key, int val, int freq) {
this.key = key;
this.val = val;
this.freq = freq;
}
}
拓扑排序
课程表
- 深度优先拓扑排序，
class Solution {
private List<List<Integer>> edges;
private int[] visited; // 需要有3个状态
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 深度优先遍历，需要转变为领接矩阵
edges = new ArrayList<List<Integer>>();
visited = new int[numCourses]; //初始化都是0
for(int i=0; i < numCourses; i++){
edges.add(new ArrayList<Integer>());
}
for(int[] info: prerequisites){
edges.get(info[1]).add(info[0]);
}
for(int i=0; i<numCourses; i++){
if(visited[i]==0){
if(!dfs(i)){
return false;
}
}
}
return true;
}
private boolean dfs(int u){
visited[u] = 1;
for(int v : edges.get(u)){
if(visited[v]==1)
return false;
else if(visited[v]==0){
if(!dfs(v)){
return false;
}
}
}
visited[u] = 2;
return true;
}
}
- 广度优秀
深度优先是一种【逆向思维】，最先进入栈里面的节点是排在拓扑排序最后面的节点。也可以正向思维，顺序地生成拓扑排序。
用一个队列存储现在入度为0 的节点，访问一次就poll一次
队列 + while循环 + 邻接矩阵扫描
class Solution {
private List<List<Integer>> edges;
private int[] indeg;
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 深度优先遍历，需要转变为领接矩阵
edges = new ArrayList<List<Integer>>();
indeg = new int[numCourses];
for(int i=0; i < numCourses; i++){
edges.add(new ArrayList<Integer>());
}
for(int[] info: prerequisites){
edges.get(info[1]).add(info[0]);
indeg[info[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for(int i=0; i< numCourses; i++){
if(indeg[i]==0)
queue.offer(i); //入度为0的全部放进去
}
int visited = 0;
while(!queue.isEmpty()){
int u = queue.poll();
visited++;
for(int v : edges.get(u)){
indeg[v]--;
if(indeg[v]==0){
queue.offer(v);
}
}
}
return visited == numCourses;
}
}
课程表II
方法和上一题相同，可以多使用一些数据结构答案。
- 广度优先
class Solution {
// 存储有向图
private List<List<Integer>> edges;
// 存储每个节点的入度
private int[] indeg;
// 存储答案
private int[] result;
// 答案下标
private int index;
public int[] findOrder(int numCourses, int[][] prerequisites) {
indeg = new int[numCourses];
result = new int[numCourses];
edges = new ArrayList<List<Integer>>();
for(int i=0; i< numCourses; i++){
edges.add(new ArrayList<Integer>());
}
for(int[] info : prerequisites){
edges.get(info[1]).add(info[0]);
indeg[info[0]]++;
}
Queue<Integer> queue = new LinkedList<Integer>();
// 把所有入度为0的课程编号放进队列
for(int i = 0; i < numCourses; i++){
if(indeg[i]==0){
queue.offer(i);
}
}
index = 0;
while(!queue.isEmpty()){
int u = queue.poll();
result[index++]=u;
for(int v : edges.get(u)){
--indeg[v];
if(indeg[v]==0){
queue.offer(v);
}
}
}
if(index!=numCourses)
return new int[0];
return result;
}
}
- 深度优先
class Solution {
// 存储有向图
List<List<Integer>> edges;
// 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
int[] visited;
// 用数组来模拟栈，下标 n-1 为栈底，0 为栈顶
int[] result;
// 判断有向图中是否有环
boolean valid = true;
// 栈下标
int index;
public int[] findOrder(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
for (int i = 0; i < numCourses; ++i) {
edges.add(new ArrayList<Integer>());
}
visited = new int[numCourses];
result = new int[numCourses];
index = numCourses - 1;
for (int[] info : prerequisites) {
edges.get(info[1]).add(info[0]);
}
// 每次挑选一个「未搜索」的节点，开始进行深度优先搜索
for (int i = 0; i < numCourses && valid; ++i) {
if (visited[i] == 0) {
dfs(i);
}
}
if (!valid) {
return new int[0];
}
// 如果没有环，那么就有拓扑排序
return result;
}
public void dfs(int u) {
// 将节点标记为「搜索中」
visited[u] = 1;
// 搜索其相邻节点
// 只要发现有环，立刻停止搜索
for (int v: edges.get(u)) {
// 如果「未搜索」那么搜索相邻节点
if (visited[v] == 0) {
dfs(v);
if (!valid) {
return;
}
}
// 如果「搜索中」说明找到了环
else if (visited[v] == 1) {
valid = false;
return;
}
}
// 将节点标记为「已完成」
visited[u] = 2;
// 将节点入栈
result[index--] = u;
}
}
数组
48. 旋转图像
给定一个 n × n 的二维矩阵表示一个图像。 将图像顺时针旋转 90 度。
方法1，两次矩阵操作， 转置 + 每行反转
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
if(n==0)return;
// 转置操作
for(int i=0; i<n; i++)
for(int j=i; j<n; j++){
int tmp = matrix[j][i];
matrix[j][i] = matrix[i][j];
matrix[i][j] = tmp;
}
// 反转每一层
for(int i=0; i<n; i++){
int l = 0, r = n-1;
while(l < r){
int tmp = matrix[i][l];
matrix[i][l] = matrix[i][r];
matrix[i][r] = tmp;
l++;r--;
}
}
}
}
方法2，一次操作（略）
75. 颜色分类
题目链接 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
双指针
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
int red = -1, blue = n;
for(int i=0; i<blue;i++){
while(i < blue && nums[i]==2){
blue--;
swap(nums, blue, i);
}
if(nums[i]==0){
red++;
swap(nums, red, i);
}
}
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
字符串
49. 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
方法1：排序数组分类
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 字母相同，排列不同
int n = strs.length;
Map<String, ArrayList> dict = new HashMap<>();
for(int i=0; i<n; i++){
char[] chars = strs[i].toCharArray();
Arrays.sort(chars);
String key = new String(chars);
if(!dict.containsKey(key)) dict.put(key, new ArrayList());
dict.get(key).add(strs[i]);
}
return new ArrayList(dict.values());
}
}
方法2:按计数分类。字符计数（每个字符的出现次数）相同时。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList();
Map<String, List> ans = new HashMap<String, List>();
int[] count = new int[26];
for (String s : strs) {
Arrays.fill(count, 0);
for (char c : s.toCharArray()) count[c - 'a']++;
StringBuilder sb = new StringBuilder("");
for (int i = 0; i < 26; i++) {
sb.append('#');
sb.append(count[i]);
}
String key = sb.toString();
if (!ans.containsKey(key)) ans.put(key, new ArrayList());
ans.get(key).add(s);
}
return new ArrayList(ans.values());
}
}
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
中位数问题，转换为在两个有序数组里一起找第k小的数字。 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较。 这里的 “/” 表示整除，nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个。 nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个。 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个 这样 pivot 本身最大也只能是第 k-1 小的元素 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 “删除”，剩下的作为新的 nums1 数组 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 “删除”，剩下的作为新的 nums2 数组 由于我们 “删除” 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n1 = nums1.length;
int n2 = nums2.length;
int totalLength = n1 + n2;
if(totalLength % 2 == 1) { // 最小
int midIndex = totalLength / 2;
// 第mindIndex小的数字
double median = getKthElement(nums1, nums2, midIndex+1);
return median;
} else {
int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
double median = (getKthElement(nums1, nums2, midIndex1+1) + getKthElement(nums1, nums2, midIndex2+1)) / 2.0;
return median;
}
}
public int getKthElement(int[] nums1, int[] nums2, int k) {
/* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
* 这里的 "/" 表示整除
* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
* 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
* 这样 pivot 本身最大也只能是第 k-1 小的元素
* 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
* 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
* 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
*/
int length1 = nums1.length, length2 = nums2.length;
int index1 = 0, index2 = 0;
while(true) {
if(index1==length1)
return nums2[index2+k-1];
if(index2==length2)
return nums1[index1+k-1];
if(k==1)
return Math.min(nums1[index1],nums2[index2]);
int half = k /2;
int newIndex1 = Math.min(index1+half, length1) - 1;
int newIndex2 = Math.min(index2+half, length2) - 1;
int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
if(pivot1<=pivot2){
k -= (newIndex1-index1+1);
index1 = newIndex1+1;
}else{
k -= (newIndex2-index2+1);
index2 = newIndex2+1;
}
}
}
// public int getKthElement(int[] nums1, int[] nums2, int k) {
// int index1 = 0, index2 = 0;
// int length1 = nums1.length, length2 = nums2.length;
// // 这里的二分需要一直循环
// while(true){
// // 先看nums1, nums2哪个数组先排除完了
// if (index1 == length1)
// return nums2[index2+k-1];
// if (index2 == length2)
// return nums1[index1+k-1];
// if(k==1){
// return Math.min(nums1[index1], nums2[index2]);
// }
// int half = k/2;
// int half_index1 = Math.min(index1 + half - 1, length1-1);
// int half_index2 = Math.min(index2 + half - 1, length2-1);
// int pivot1 = nums1[half_index1], pivot2 = nums2[half_index2];
// if(pivot1 < pivot2){
// k -= (half_index1 - index1+1);
// index1 = half_index1+1;
// } else {
// k -= (half_index2 - index2+1);
// index2 = half_index2+1;
// }
// }
// }
}
每日练习（不分题型）
765 情侣牵手
题目描述：N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。
人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。
这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。
解题：
用贪心的方法解决比较方便，可以制定按顺序让每张沙发上情侣开心的策略。对于每张沙发，找到沙发上第一个人的情侣，如果不在同一个沙发上，就把沙发上的第二人换成第一个人的情侣。
如果一个人的编号为 x，那么他的情侣的编号为 x ^ 1， ^在这里是异或操作。对于每张沙发上的第一个人 x = row[i]，找到他们的同伴所在的位置 row[j]，将 row[j] 和 row[i + 1] 互相交换。
class Solution {
public:
int minSwapsCouples(vector<int>& row) {
int res=0;
int len = row.size();
for(int i=0;i<len; i = i+2){
int x = row[i];
if(row[i+1] == (x^1))
continue;
for(int j=i+2;i<len;j++){
if(row[j]==(x^1)){
row[j]=row[i+1];
row[i+1]=x^1;
break;
}
}
res++;
}
return res;
}
};
680 验证回文字符串 5月19日
题目描述：给定一个非空字符串s，最多删除一个字符。判断是否能成为回文字符串。
解题思路：两个指针low,high分别从头和从尾向中间靠拢，遇到不一样字符时候，只需要字符串中 [low,high-1]和[low+1,high]这两个子字符串其中一个是回文就行了。
class Solution {
public:
bool validPalindrome(string s) {
int low = 0, high = s.size()-1;
while(low<high){
if(s[low]==s[high]){
low++;high--;
}else{
return check(s,low+1,high) || check(s,low,high-1);
}
}
return true;
}
private:
bool check(string s, int low, int high)
{
while(low<high){
if(s[low]!=s[high])
return false;
low++;high--;
}
return true;
}
};
1371 每个元音包含偶数次的最长子字符串 5月20日
题目描述：给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，’e’，’i’，’o’，’u’ ，在子字符串中都恰好出现了偶数次。
解题思路：将5个元音字母出现次数的奇偶视为一种状态，共有32种状态。
而如果子串 [0，i] 与字串 [0,j] 状态相同，那么字串 [i+1,j] 的状态一定是 00，因此可以记录每个状态第一次出现的位置，此后再出现该状态时相减即可。 需要注意状态 00 首次出现的位置应该设定为 -1。
在计算状态的时候可以利用异或运算。
class Solution {
public:
int findTheLongestSubstring(string s) {
vector<int> pre(32,INT_MAX);
pre[0]=-1;
const int N=s.size();
int cur=0;
int ans=0;
for(int i=0;i<N;++i){
switch(s[i]){
case 'a':cur^=1;break;
case 'e':cur^=2;break;
case 'i':cur^=4;break;
case 'o':cur^=8;break;
case 'u':cur^=16;break;
default:break;
}
if(pre[cur]==INT_MAX) pre[cur]=i;
else ans=max(ans,i-pre[cur]);
}
return ans;
}
};
105 从前序与中序遍历序列构造二叉树 5月22日
题目描述：剑指Offer原题，根据一棵树的前序遍历与中序遍历构造二叉树。 题目链接
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int preorder_len = preorder.size();
int inorder_len = inorder.size();
if(inorder_len==0)
return nullptr;
unordered_map<int,int> kv;
for(int i=0;i<inorder_len;i++)
{
kv[inorder[i]]=i;
}
TreeNode* root = build(preorder, 0,preorder_len-1,inorder, 0, inorder_len-1,kv);
return root;
}
TreeNode* build(vector<int>& preorder, int preorder_start, int preorder_end, vector<int>& inorder, int inorder_start, int inorder_end, unordered_map<int,int>& kv)
{
if(preorder_start > preorder_end)
return nullptr;
int root_val = preorder[preorder_start];
TreeNode* root = new TreeNode(root_val);
int inorder_rootindex = kv[root_val];
if(preorder_start == preorder_end)
return root;
int left_count = inorder_rootindex - inorder_start, right_count = inorder_end - inorder_rootindex;
root->left = build(preorder, preorder_start+1,preorder_start+left_count, inorder, inorder_start, inorder_start+left_count-1,kv);
root->right = build(preorder, preorder_start+left_count+1, preorder_end, inorder, inorder_rootindex+1,inorder_end,kv);
return root;
}
};
76 最小覆盖子串 5月23日
题目描述：给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
1.右边界先移动，找到一个满足题意的包含T中所有字符的子区间，然后左边界尝试向右移动，让满足要求的子区间越来越小。直到左区间在向右移动过程中子区间不再包含所有T中的字符。 2.接着左边界放在满足当前最小区间位置向右一格，右边界继续向右移动，重复1的过程。
class Solution {
Map<Character, Integer> ori = new HashMap<Character, Integer>();
Map<Character, Integer> cnt = new HashMap<Character, Integer>();
public String minWindow(String s, String t) {
int tLen = t.length();
for (int i = 0; i < tLen; i++) {
char c = t.charAt(i);
ori.put(c, ori.getOrDefault(c, 0) + 1);
}
int l = 0, r = -1;
int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
int sLen = s.length();
while (r < sLen) {//向右移动
++r;
if (r < sLen && ori.containsKey(s.charAt(r))) {
cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
}
while (check() && l <= r) {
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
ansR = l + len;
}
if (ori.containsKey(s.charAt(l))) {
cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
}
++l;
}
}
return ansL == -1 ? "" : s.substring(ansL, ansR);
}
public boolean check() {
Iterator iter = ori.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Character key = (Character) entry.getKey();
Integer val = (Integer) entry.getValue();
if (cnt.getOrDefault(key, 0) < val) {
return false;
}
}
return true;
}
}
331. 验证二叉树的前序遍历 5月28日
题目描述：”9,3,4,#,#,1,#,#,2,#,6,#,#”验证是否是前序遍历。
解题思路：二叉树中任意一个节点或者空孩子节点都要占据一个槽位。二叉树的建立也伴随着槽位数量的变化。开始时只有一个槽位，如果根节点是空节点，就只消耗掉一个槽位，如果根节点不是空节点，除了消耗一个槽位，还要为孩子节点增加两个新的槽位。之后的节点也是同理。
_9_
/ \
3 2
/ \ / \
4 1 ## 6
/ \ / \ / \
## ## ## ## ## #
class Solution {
public boolean isValidSerialization(String preorder) {
int slots=1;
for(String node: preorder.split(",")){
slots--;
if(slots<0)
return false;
if(!node.equals("#")){
slots = slots + 2;
}
}
return slots==0;
}
}
394. 字符串解码 5月28日
题目描述：给定一个经过编码的字符串，返回它解码后的字符串。 示例
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
class Solution {
int ptr;
public String decodeString(String s) {
LinkedList<String> stk = new LinkedList<String>();
ptr = 0;
while(ptr < s.length()){
char cur = s.charAt(ptr);
if(Character.isDigit(cur)){ //是数字
String digits = getDigits(s);
stk.addLast(digits);
}else if (Character.isLetter(cur) || cur == '[') { //是字符和左括号
// 获取一个字母并进栈
stk.addLast(String.valueOf(s.charAt(ptr++)));
}else{ //右括号，要开始出栈了
++ptr;
LinkedList<String> sub = new LinkedList<String>();
while(!"[".equals(stk.peekLast())){
sub.addLast(stk.removeLast());
}
Collections.reverse(sub);
stk.removeLast();
int repTime = Integer.parseInt(stk.removeLast());
StringBuffer t = new StringBuffer();
String o = getString(sub);
while(repTime-- > 0){
t.append(o);
}
stk.addLast(t.toString());
}
}
return getString(stk);
}
private String getDigits(String s){
StringBuffer ret = new StringBuffer();
while(Character.isDigit(s.charAt(ptr))){
ret.append(s.charAt(ptr++));
}
return ret.toString();
}
public String getString(LinkedList<String> v) {
StringBuffer ret = new StringBuffer();
for (String s : v) {
ret.append(s);
}
return ret.toString();
}
}
28. 实现strStr().
题目描述：找出字符串B在字符串A中第一次出现的位置
解题思路：KMP算法，KMP算法目的就是：在出错时，利用原有的匹配信息，尽量减少重新匹配的次数。 (1) 搜索串与主串匹配过程中如果遇到不匹配字符，重复利用之前已经匹配过可免匹配的部分。 (2) KMP 算法（三个人名）思路就是找到搜索串每个字符之前可以免匹配的最大长度。 *** 比如搜索串 abaabb 匹配到最后一个字符不匹配，则前面可免匹配的部分为 ab ，从第三个字符开始继续。
构造next数组。参考视频。next数组的作用是为了重复利用之前已经匹配过，可以免匹配的部分。
class Solution {
public int strStr(String haystack, String needle) {
if(needle.isEmpty()){
return 0;
}
char [] h = haystack.toCharArray();
char [] n = needle.toCharArray();
int h_len = h.length;
int n_len = n.length;
if(n_len > h_len)
return -1;
int[] next = getNext(needle);
int i=0,j=0;
while(i < h_len && j < n_len){
if(j==-1 || h[i]==n[j]){
i++;j++;
}else{
j = next[j];
}
}
if(j==n_len)
return i-j;
else{
return -1;
}
}
private int[] getNext(String needle) {
char[] n = needle.toCharArray();
int[] next = new int[n.length];
next[0]=-1;
int j=0;
int k=-1;
while(j < n.length-1){
if(k==-1 || n[k]==n[j]){
next[++j]=++k;
}else{
k = next[k];
}
}
return next;
}
}
101. 对称二叉树 5月31日
题目描述：给定一个二叉树，检查它是否是镜像对称的。
解题思路：剑指Offer原题
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null)
return true;
return help(root.left, root.right);
}
private boolean help(TreeNode root1, TreeNode root2){
if(root1==null && root2==null)
return true;
if(root2==null || root1==null){
return false;
}
if(root1.val != root2.val)
return false;
return help(root1.left, root2.right) && help(root1.right, root2.left);
}
}
1431. 拥有最多糖果的孩子 6月1日
题目说明：给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。
对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目
class Solution {
public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
int len = candies.length;
int maxcandie = 0;
for(int i=0;i<len;i++){
maxcandie = Math.max(maxcandie, candies[i]);
}
List<Boolean> res = new ArrayList<Boolean>();
for(int i=0;i<len;i++){
res.add(candies[i]+extraCandies>=maxcandie);
}
return res;
}
}
剑指Offer64. 求1+2+…+n 6月2日
Java递归
class Solution {
public int sumNums(int n) {
boolean flag = n > 0 && (n += sumNums(n - 1)) > 0;
return n;
}
}
class Solution {
public:
int sumNums(int n) {
return quick_sum(n+1,n) >> 1;
}
int quick_sum(int a, int n)//a*n
{
int ans=0;
(n>0) && (ans = ans + quick_sum(a<<1,n>>1) );
(n & 1) && (ans = ans + a);
return ans;
}
};
837. 新21点 6月3日
题目链接 以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。 每次抽取都是独立的，其结果具有相同的概率。
当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？
class Solution {
public double new21Game(int N, int K, int W) {
if (K == 0) {
return 1.0;
}
double[] dp = new double[K + W + 1];
for (int i = K; i <= N && i < K + W; i++) {
dp[i] = 1.0;
}
dp[K - 1] = 1.0 * Math.min(N - K + 1, W) / W;
for (int i = K - 2; i >= 0; i--) {
dp[i] = dp[i + 1] - (dp[i + W + 1] - dp[i + 1]) / W;
}
return dp[0];
}
}
128. 最长连续序列 6月6日
题目链接 给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
用并查集做
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<Integer>();
for(int num:nums){
num_set.add(num);
}
int longest = 0;
for(int num: num_set){
if(!num_set.contains(num-1)){
int cur = num;
int curLong = 1;
while(num_set.contains(cur+1)){
cur++;
curLong++;
}
longest = Math.max(longest, curLong);
}
}
return longest;
}
}
990. 等式方程的可满足性 6月8日
题目描述：给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：”a==b” 或 ”a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
解题思路：
class Solution {
public boolean equationsPossible(String[] equations) {
int len = equations.length;
if(len<1)return true;
int [] parent = new int[26];//并查集初始化,26个字母
for(int i=0;i<26;i++){
parent[i]=i;
}
for(String str:equations){
if(str.charAt(1)=='='){
int index1 = str.charAt(0) - 'a';
int index2 = str.charAt(3) - 'a';
union(parent, index1, index2);
}
}
for(String str: equations){
if(str.charAt(1)=='!'){
int index1 = str.charAt(0) - 'a';
int index2 = str.charAt(3) - 'a';
if(find(parent,index1) == find(parent,index2) ){
return false;
}
}
}
return true;
}
private void union(int[] parent, int x, int y){
int a = find(parent,x);
int b = find(parent,y);
if(a == b)
return;
parent[a] = b;
//需要考虑rank的并查集，防止算法退化
/*
if(rank[a]<rank[b])
parent[a] = b;
else{
parent[b] = a;
if(rank[a] == rank[b]) rank[a] = rank[a]+1;
}
*/
}
private int find(int[] parent, int x){
return parent[x]==x ? x : (parent[x] = find(parent,parent[x]));
}
}
1014. 最佳观光组合 6月17日
给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。
一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。
返回一对观光景点能取得的最高分。
class Solution {
public int maxScoreSightseeingPair(int[] A) {
int mx = A[0]+0;
int ans = 0;
for(int j=1;j<A.length;j++){
ans = Math.max(ans, mx+A[j]-j);
mx = Math.max(mx,A[j]+j);
}
return ans;
}
}
221. 最大正方形 6月17日
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例：
输入:
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
输出: 4
动态规划，dp[i][j]表示 (i,j)为右下角的最大正方向边长。状态转移规律也比较好找。
class Solution {
public int maximalSquare(char[][] matrix) {
int maxSide = 0;
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return maxSide;
}
int rows = matrix.length, columns = matrix[0].length;
int[][] dp = new int[rows][columns];
for(int i=0; i<rows; i++)
for(int j=0; j<columns; ++j){
if(matrix[i][j]=='1'){
if(i==0 || j==0){
dp[i][j]=1;
maxSide = Math.max(maxSide,dp[i][j]);
}else{
dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
maxSide = Math.max(maxSide,dp[i][j]);
}
}
}
int ans = maxSide * maxSide;
return ans;
}
}
79. 单词搜索 6月18日
题目链接 剑指 offer原题04 DFS回溯搜索
class Solution {
public boolean exist(char[][] board, String word) {
int rows = board.length;
if (rows<=0)
return false;
int cols = board[0].length;
for(int i = 0;i<rows; i++)
for(int j=0; j<cols; j++){
if(search(board, word,rows,cols, 0, i, j))
return true;
}
return false;
}
private boolean search(char[][] board, String word,int rows, int cols, int k,int i, int j){
if(i<0 || i>=rows || j<0 || j>=cols || board[i][j]!=word[k])
return false;
char tmp = board[i][j];
board[i][j]='/';
int[] dx = {-1,1,0,0};
int[] dy = {0,0,-1,1};
for(int k=0;k<4;k++){
if(search(board,word,rows,cols,k+1,i+dx[k],j+dy[k]))
return true;
}
board[i][j]=tmp;
return false;
}
}
1028. 从先序遍历还原二叉树 6月18日
有一个题目中，重建二叉树，需要中序遍历和先序遍历才能重建二叉树。这里重建时只有一个先序遍历字符串就可以重建，是因为这个题目当中可以判断哪个节点是叶节点。思想同37题序列化二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
String internalString;
public TreeNode recoverFromPreorder(String S) {
internalString = S;
return helper(0);
}
public TreeNode helper(int curdepth){
int i = 0;
if("".equals(internalString))
return null;
while(internalString.charAt(i)=='-')
i++;
if(i!=curdepth){
return null;
}
String tmpString = internalString.substring(i);
int index = tmpString.indexOf('-');
String node = index==-1? tmpString : tmpString.substring(0,index);
internalString = index==-1? "" : tmpString.substring(index);
TreeNode root = new TreeNode(Integer.parseInt(node));
root.left = helper(curdepth+1);
root.right = helper(curdepth+1);
return root;
}
}
42. 接雨水 6月18日
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
首先想清楚这个雨水高度是怎么算的，每个位置能放的雨水高度 = 两边最大高度的较小值 - 当前高度。
- 动态规划方法，用动态规划计算每个位置两边最大高度。
class Solution { public int trap(int[] height) { int length = height.length; if(length<=0) return 0; int ans=0; int[] right_max = new int[length]; int[] left_max = new int[length]; left_max[0]=height[0]; right_max[length-1]=height[length-1]; for(int i=1;i<length;i++){ left_max[i] = Math.max(left_max[i-1],height[i]); } for(int i=length-2;i>=0;i--){ right_max[i] = Math.max(right_max[i+1],height[i]); } for(int i=0;i<length;i++){ ans += (Math.min(left_max[i],right_max[i]) - height[i]); } return ans; } } - 双指针方法，想办法一次完成遍历 如果一端有更高的条形块（例如右端），积水的高度依赖于当前方向的高度（从左到右）。当我们发现另一侧（右侧）的条形块高度不是最高的，我们则开始从相反的方向遍历（从右到左）。 我们必须在遍历时维护 $\text{left_max}$ 和 $\text{right_max}$ ，但是我们现在可以使用两个指针交替进行，实现 1 次遍历即可完成。
class Solution {
public int trap(int[] height) {
int left=0,right=height.length-1;
int left_max = 0, right_max = 0;
int ans = 0;
while(left<right){
if( height[left] < height[right] ){
if(height[left] >= left_max)
left_max = height[left];
else
ans += (left_max-height[left]);
left++;
}else{
if(height[right] >= right_max)
right_max = height[right];
else
ans+=(right_max - height[right]);
right--;
}
}
return ans;
}
}
139. 单词拆分 6月18日
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
- 暴力，超时
class Solution { public boolean wordBreak(String s, List<String> wordDict) { if("".equals(s)) return true; for(int i = 0; i < s.length(); i++){ String str = s.substring(0,i+1); if(wordDict.contains(str) && wordBreak(s.substring(i+1), wordDict)) return true; } return false; } } - 回溯+记忆化，一个
Boolean数组保存后缀是否可以匹配class Solution { public boolean wordBreak(String s, List<String> wordDict) { return help(s, new HashSet(wordDict), new Boolean[s.length()], 0); } public boolean help(String s, List<String> wordDict, Boolean [] memo, int start){ if(start==s.length()) return true; if(memo[start]!=null)//true和false都保存 return memo[start]; for(int i = start; i < s.length(); i++){ String str = s.substring(start,i+1); if(wordDict.contains(str) && help(s, wordDict, memo, i+1)){ return memo[start]=true; } } return memo[start] = false; } }
785. 判断二分图 6月20日
给定一个无向图graph，当这个图为二分图时返回true。
如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。
Graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。
深度优先搜索着色。用栈深度优先搜索。
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n];
Arrays.fill(color, -1);
for(int i=0;i<n;i++){
if(color[i]==-1){
Stack<Integer> stack = new Stack<>();
stack.push(i);
color[i]=0;
while(!stack.empty()){
Integer node = stack.pop();
for(int nn : graph[node]){
if(color[nn]==-1){
stack.push(nn);
color[nn]=color[node]^1;
}else if(color[nn]==color[node]){
return false;
}
}
}
}
}
return true;
}
}
210. 课程表 II 6月20日
现在你总共有 n 门课需要选，记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1] 给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。 可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
使用 DFS 来实现拓扑排序，使用一个栈存储后序遍历结果，这个栈的逆序结果就是拓扑排序结果。
证明：对于任何先序关系：v->w，后序遍历结果可以保证 w 先进入栈中，因此栈的逆序结果中 v 会在 w 之前。
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<Integer>[] graphic = new List[numCourses];
for (int i = 0; i < numCourses; i++) {
graphic[i] = new ArrayList<>();
}
for (int[] pre : prerequisites) {
graphic[pre[0]].add(pre[1]);
}
Stack<Integer> postOrder = new Stack<>();
boolean[] globalMarked = new boolean[numCourses];
boolean[] localMarked = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (hasCycle(globalMarked, localMarked, graphic, i, postOrder)) {
return new int[0];
}
}
int[] orders = new int[numCourses];
for (int i = numCourses - 1; i >= 0; i--) {
orders[i] = postOrder.pop();
}
return orders;
}
private boolean hasCycle(boolean[] globalMarked, boolean[] localMarked, List<Integer>[] graphic,
int curNode, Stack<Integer> postOrder) {
if (localMarked[curNode]) {
return true;
}
if (globalMarked[curNode]) {
return false;
}
globalMarked[curNode] = true;
localMarked[curNode] = true;
for (int nextNode : graphic[curNode]) {
if (hasCycle(globalMarked, localMarked, graphic, nextNode, postOrder)) {
return true;
}
}
localMarked[curNode] = false;
postOrder.push(curNode);
return false;
}
class Solution {
List<List<Integer>> edges;
int[] res;
int[] visited;
int index;
public int[] findOrder(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
for(int i=0; i< numCourses; i++){
edges.add(new ArrayList<>());
}
visited = new int[numCourses];
index = numCourses-1;
res = new int[numCourses];
for(int [] info:prerequisites){
edges.get(info[1]).add(info[0]);
}
for(int i=0;i<numCourses;i++){
if(visited[i]==0){
if(!dfs(i)){
return new int[0];
}
}
}
return res;
}
private boolean dfs(int u){
visited[u] = 1;
for(int v: edges.get(u)){
if(visited[v]==0){
if(!dfs(v))
return false;
}else if(visited[v]==1){
return false;
}
}
res[index--] = u;
visited[u] = 2;
return true;
}
}
124. 二叉树中的最大路径和 6月21日
题目链接 每一层返回的是当前节点的贡献值，通过两边子节点的最大贡献值，计算经过当前root节点的最大路径和。维护一个全局变量搜索（有的题目，递归函数返回的值只是一个辅助，有时候答案需要用一个全局的变量去存储）。
class Solution {
int ans = 1<<31;
public int maxPathSum(TreeNode root) {
if(root==null)return 0;
contribution(root);
return ans;
}
private int contribution(TreeNode root){
if(root==null){
return 0;
}
int left = Math.max(0, contribution(root.left));
int right = Math.max(0, contribution(root.right));
ans = Math.max(ans , root.val+left+right);
return root.val + Math.max(left,right);
}
}
面试题 16.18. 模式匹配
挺难的
class Solution {
public boolean patternMatching(String pattern, String value) {
String s[]=new String[2];
return solve(s,pattern,0,value,0);
}
/**
* 回溯遍历设置a,b的对应值，尝试每一种可能。
* @param s s[0]=a对应的字符串 s[1]=b对应的字符串
* @param pattern 模式串
* @param index1 模式串匹配位置
* @param value 匹配串（待匹配的字符串）
* @param index2 匹配串匹配位置
* @return
*/
public boolean solve(String []s,String pattern,int index1,String value,int index2){
//匹配完成
if(index1==pattern.length()&&index2==value.length()) return true;
//注意匹配串匹配位置等于长度的时候也可以继续匹配，因为模式串的a，b可以匹配空串。
if(index1>=pattern.length()||index2>value.length()) return false;
int num=pattern.charAt(index1)-'a';
if(s[num]==null){
//从当前尝试a或b对应的字符串的每一种可能
for(int i=index2;i<=value.length();i++){
s[num]=value.substring(index2,i);
//(!s[num].equals(s[num^1])) [是指a，b对应的字符串不可相等]
if(!s[num].equals(s[num^1])&&solve(s,pattern,index1+1,value,i)) return true;
}
//失配时应将设置过的对应字符串为空
s[num]=null;
return false;
}else{
//若此前a或b已有对应的字符串匹配了，则查看当前位置时候能够匹配上。
int end=index2+s[num].length();
if(end> value.length()||!value.substring(index2,end).equals(s[num])) return false;
return solve(s,pattern,index1+1,value,end);
}
}
}
718. 最长重复子数组 7月1日
题目链接 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
class Solution {
public int findLength(int[] A, int[] B) {
int aLength = A.length;
int bLength = B.length;
int[][] dp = new int[aLength+1][bLength+1];
dp[0][0] = 0;
int ans = 0;
for(int i=1; i <= aLength; i++)
for(int j=1; j <= bLength; j++){
if(A[i-1]==B[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=0;
}
ans = Math.max(ans, dp[i][j]);
}
return ans;
}
}
378. 有序矩阵中第K小的元素 7月2日
解题思路：二分查找
class Solution {
public int kthSmallest(int[][] matrix, int k) {
//二分法查找
int n = matrix.length;
if(n<=0){
return -1;
}
//假设K永远有效
int left = matrix[0][0];
int right = matrix[n-1][n-1];
int mid;
while(left<right){
mid = (left+right)/2;
if(check(matrix, k, n,mid)){
right = mid;
}else{
left = mid+1;
}
}
return left;
}
private boolean check(int[][] matrix, int k, int n, int mid){
int num=0;
//左下角开始搜索
int i=n-1;
int j=0;
while( i>=0 && j<n ){
if(matrix[i][j]<=mid){
j++;
num+=(i+1);
}else{
i--;
}
}
return num>=k;
}
}
108. 将有序数组转换为二叉搜索树 7月3日
二叉搜索树的中序遍历是递增的，每次构建只要每次取中间那个节点，就可以保证得到比较平衡的二叉搜索树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
int len = nums.length;
//中序遍历是递增遍历
if(len<1)
return null;
return buildTree(nums, 0, len-1);
}
private TreeNode buildTree(int[] nums, int left, int right){
if(left <= right){
int mid = (left+right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = buildTree(nums, left, mid-1);
root.right = buildTree(nums, mid+1, right);
return root;
}
return null;
}
}
32. 最长有效括号 7月4日
题目链接 给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
栈的思想，栈底是「最后一个没有被匹配的右括号的下标」
class Solution {
public int longestValidParentheses(String s) {
//最长有效括号
//栈的思想的话，栈底是「最后一个没有被匹配的右括号的下标」
Stack<Integer> stc = new Stack<>();
stc.push(-1);
int len = s.length();
int ans = 0;
for(int i=0;i<len;i++){
if('('==s.charAt(i)){
stc.push(i);
}else{
stc.pop();
if(stc.empty()){
stc.push(i);
}else{
ans = Math.max(ans, i-stc.peek());
}
}
}
return ans;
}
}
动态规划的思想去做
class Solution {
public int longestValidParentheses(String s) {
int n = s.length();
int[] dp = new int[n];
int ans = 0;
// 默认初始化为0
for(int i=1; i < n; i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i-1) == '(') {
dp[i] = (i-2 >= 0 ? dp[i-2] : 0) + 2;
} else if (dp[i-1] > 0) {
if (i-dp[i-1]-1 >=0 && s.charAt(i - dp[i-1] - 1) == '(') {
dp[i] = (i-dp[i-1]-2 >= 0 ? dp[i-dp[i-1]-2] : 0) + dp[i-1] + 2;
}
}
ans = Math.max(ans, dp[i]);
}
}
return ans;
}
}
44. 通配符匹配 7月5日
题目描述： 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ’?’ 和 ’*‘ 的通配符匹配。
’?’ 可以匹配任何单个字符。 ‘*’ 可以匹配任意字符串（包括空字符串）。
解题思路： 动态规划
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1; i <= n; ++i) {
if (p.charAt(i - 1) == '*') {
dp[0][i] = true;
} else {
break;
}
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
}
63. 不同路径 II 7月6日
题目描述： 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
回溯搜索，超时
class Solution {
private int ans=0;
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if(obstacleGrid.length <=0 ){
return 0;
}
if(obstacleGrid[0].length<=0){
return 0;
}
this.ans = 0;
help(obstacleGrid, 0, 0);
return ans;
}
private void help(int[][] obstacleGrid, int i, int j)
{
if(i<0 || i>= obstacleGrid.length || j<0 || j>=obstacleGrid[0].length || obstacleGrid[i][j]!=0)
return;
if(i == obstacleGrid.length-1 && j == obstacleGrid[0].length-1){
this.ans++;
return;
}
obstacleGrid[i][j]=-1;
int[] dx = {0,1};
int[] dy = {1,0};
for(int k=0;k<2;k++)
{
help(obstacleGrid, i+dx[k], j+dy[k]);
}
obstacleGrid[i][j]=0;
}
}
动态规划+状态压缩
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length, m = obstacleGrid[0].length;
int[] dp = new int[m];
//注意有障碍
dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(obstacleGrid[i][j]==1){
dp[j]=0;
continue;
}
if(j>=1 && obstacleGrid[i][j-1]==0)
dp[j]+=dp[j-1];
}
return dp[m-1];
}
}
6112. 路径总和 7月7日
题目描述： 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。
解题思路：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null)
return false;
if(root.left == null && root.right==null)
return sum == root.val;
return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
}
}
面试题 16.11. 跳水板 7月8日
题目描述： 你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
返回的长度需要从小到大排列。
示例：
输入： shorter = 1 longer = 2 k = 3 输出： {3,4,5,6}
解题思路：
class Solution {
public int[] divingBoard(int shorter, int longer, int k) {
if (k == 0) {
return new int[0];
}
if (shorter == longer) {
return new int[]{shorter * k};
}
int[] ans = new int[k+1];
for(int i=0;i<=k;i++){
ans[i] = shorter*(k-i) + longer*i;
}
return ans;
}
}
面试题 17.13. 恢复空格 7月9日
题目描述： 哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子”I reset the computer. It still didn’t boot!”已经变成了”iresetthecomputeritstilldidntboot”。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。
注意：本题相对原题稍作改动，只需返回未识别的字符数
输入： dictionary = [“looked”,”just”,”like”,”her”,”brother”] sentence = “jesslookedjustliketimherbrother” 输出： 7 解释： 断句后为”jess looked just like tim her brother”，共7个未识别字符
解题思路： Trie树 + 动态规划
官方题解重的Trie树数据结构
class Trie{
Trie[] next;
boolean isEnd;
public Trie(){
next = new Trie[26];
isEnd = false;
}
public void insert(String s){
Trie curPos = this;
for(int i=0; i<s.length(); i++ ){
int t = s.charAt(i) - 'a';
if(curPos.next[t]==null){
curPos.next[t] = new Trie();
}
curPos = curPos.next[t];
}
curPos.isEnd = true;
}
}
动归过程
dp[i]表示前i个字符最少字符未匹配数
class Solution {
private class Trie{
Trie [] next;
boolean isEnd;
public Trie(){
next = new Trie[26];
isEnd = false;
}
public void insert(String s){
int len = s.length();
Trie cur = this;
for(int i=len-1;i>=0;i--){
int t = s.charAt(t) - 'a';
if(cur.next[t]==null){
cur.next[t] = new Trie();
}
cur = cur.next[t];
}
cur.isEnd = true;
}
}
public int respace(String[] dictionary, String sentence) {
// 尽量让未匹配的字符数最少
int n = sentence.length();
int[] dp = new int[n+1];
Trie root = new Trie();
for(String s: dictionary){
root.insert(s);
}
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i=1;i<=n;i++){
dp[i] = dp[i-1]+1;
Trie cur = root;
for(int j=i;j>=1;j--){
int t = sentence.charAt(j-1) - 'a';
if(cur.next[t]==null){
break;
}else if(cur.next[t].isEnd){
dp[i] = Math.min(dp[i], dp[j-1]);
}
// if(dp[i]==0) break; 这里可以更快
cur = cur.next[t];
}
}
return dp[n];
}
}
84. 柱状图中最大的矩形 7月10日
题目描述： 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
解题思路： 使用单调栈，还可以再单调栈的基础上进行常数优化。
class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int n = heights.length;
if (n==0) return 0;
int ans = 0;
for(int i=0;i<n ;i++){
while( !(stack.peek()).equals(-1) && heights[stack.peek()] > heights[i] ){
int topHeight = heights[stack.pop()];
int width = i - stack.peek()-1;
ans = Math.max(ans, topHeight*width);
}
stack.push(i);
}
while(!(stack.peek()).equals(-1) ){
int topHeight = heights[stack.pop()];
int width = n - stack.peek()-1;
ans = Math.max(ans, topHeight*width);
}
return ans;
}
}
309. 最佳买卖股票时机含冷冻期 7月10日
题目描述： 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
解题思路： 状态机 二维数组 加入 冷冻期
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) return 0;
//0表示本不持有，1表示持有，2表示当天卖出，不持有
int[][] dp = new int[len][3]; //用二维数组记录当天各种情况的最优解(收益的最大值)
dp[0][1] = -prices[0]; //第一天若持有，则收益为负；不持有则收益为零
for (int i = 1; i < len; i++){
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]); //当天的本不持有可以由前一天本不持有或前一天卖出得到
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); //当天的持有可以由前一天的持有或前一天的本不持有-当天的股票价格得到, 即买进一只股票
dp[i][2] = dp[i - 1][1] + prices[i]; //当天卖出可以由前一天的持有+当天的股票价格得到, 即卖出手中的股票
}
return Math.max(dp[len - 1][0], dp[len - 1][2]); //返回最后一天不持有股票的状态，此处可以得到收益的最大值
}
}
315. 计算右侧小于当前元素的个数 7月11日
题目描述： 给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例:
解题思路：
用归并排序，因为归并排序会更改元素位置，用一个初始下标数组记录就可以了。
174. 地下城游戏 7月12日
题目描述：
解题思路：
从左上到右下的方向不满足动态规划的无后效性，所以才用从右下到左上的遍历方式。
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int n = dungeon.length, m = dungeon[0].length;
int[][] dp = new int[n+1][m+1];
for(int i = 0; i<=n; i++){
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
// 从dp[n][m]倒过来开始dp。
dp[n-1][m] = 1;
dp[n][m-1] = 1;
for(int i=n-1; i >= 0 ;i--)
for(int j=m-1; j >= 0; j--){
/*
if(dungeon[i][j]<=0){
dp[i][j] = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
}else{
dp[i][j] = Math.max( Math.min(dp[i+1][j],dp[i][j+1] ) - dungeon[i][j] , 1);
}*/
//简化
int minn = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
dp[i][j] = Math.max(minn, 1);
}
return dp[0][0];
}
}
174. 地下城游戏 7月12日
题目描述： 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
解题思路：
杨辉三角类型的动态规划。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int ans = 0;
int n = triangle.size();
int[] dp = new int[n];
for(int i=0;i<n;i++){
dp[i] = triangle.get(n-1).get(i);
}
for(int i=n-2;i>=0;i--){
for(int j=0;j<=i;j++){
dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
}
96. 不同的二叉搜索树 7月15日
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
动态规划，G[n] = $\sum^{n}_{i}$ G[i-1] $\times$ G[n-i]
class Solution {
public int numTrees(int n) {
int G[] = new int[n+1];
G[0] = 1;
G[1] = 1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
G[i]+=G[j-1]*G[i-j];
}
}
return G[n];
}
}
350. 两个数组的交集 II 7月16日
给定两个数组，编写一个函数来计算它们的交集。
思路：
1 排序后，分别从两个数组的头部开始匹配。根据两个数组当前数字之间的大小，移动各自数组中的index。
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int length1 = nums1.length, length2 = nums2.length;
int[] intersection = new int[Math.min(length1, length2)];
int index1 = 0, index2 = 0, index = 0;
while (index1 < length1 && index2 < length2) {
if (nums1[index1] < nums2[index2]) {
index1++;
} else if (nums1[index1] > nums2[index2]) {
index2++;
} else {
intersection[index] = nums1[index1];
index1++;
index2++;
index++;
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}
2 HashMap
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return intersect(nums2, nums1);
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums1) {
int count = map.getOrDefault(num, 0) + 1;
map.put(num, count);
}
int[] intersection = new int[nums1.length];
int index = 0;
for (int num : nums2) {
int count = map.getOrDefault(num, 0);
if (count > 0) {
intersection[index++] = num;
count--;
if (count > 0) {
map.put(num, count);
} else {
map.remove(num);
}
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 7月19日
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
思路： 用快排的代码作，一次遍历。本质是双指针。
class Solution {
public int[] exchange(int[] nums) {
int n = nums.length;
if (n==0)
return nums;
int x = nums[n-1];
int i = -1;
for(int j=0;j<n-1;j++){
if((nums[j] & 1)==1){
i++;
swap(nums,i,j);
}
}
swap(nums,i+1,n-1);
return nums;
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i]=nums[j];
nums[j] = tmp;
}
}
312. 戳气球 7月19日
有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
思路：
自底向上，不是戳爆气球，而是从0添加气球🎈。
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[][] dp = new int[n + 2][n + 2];
int[] val = new int[n + 2];
val[0] = val[n + 1] = 1;
for (int i = 1; i <= n; i++) {
val[i] = nums[i - 1];
}
for(int i=n-1; i>=0;i-- )
for(int j=i+2;j<=n+1;j++)
for(int k=i+1;k<=j-1;k++){
int sum = dp[i][k]+dp[k][j];
sum += val[i]*val[k]*val[j];
dp[i][j] = Math.max(dp[i][j], sum);
}
return dp[0][n + 1];
}
}
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
vector<vector<int> > dp(n+2, vector<int>(n+2,0));//dp初始化为0
vector<int> val(n+2);
val[0]=val[n+1]=1;
for(int i=1; i<=n; i++){
val[i]=nums[i-1];
}
for(int i=n-1; i>=0;i--)
for(int j=i+2;j<=n+1; j++)
for(int k=i+1;k<j;k++){
int sum = val[i]*val[k]*val[j];
sum += dp[i][k]+dp[k][j];
dp[i][j]=max(sum, dp[i][j]);
}
return dp[0][n+1];
}
};
329. 矩阵中的最长递增路径 7月26日
超时的代码
class Solution {
private int ans = 0;
private int[][] vis;
public int longestIncreasingPath(int[][] matrix) {
int n = matrix.length;
if(n<=0)
return 0;
int m = matrix[0].length;
if(m<=0)
return 0;
vis = new int[n][m];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
dfs(matrix,i,j,0,null);
}
return ans;
}
private void dfs(int[][] matrix, int i, int j, int k, Integer last){
if(i<0 || i>=matrix.length || j<0 || j>=matrix[0].length || vis[i][j]==1 || (last!=null && matrix[i][j]<=last))
{
ans = Math.max(ans, k);
return;
}
int []dx = {0,0,1,-1};
int[] dy = {1,-1,0,0};
vis[i][j]=1;
for(int p=0;p<4;p++){
dfs(matrix, i+dx[p],j+dy[p], k+1, matrix[i][j]);
}
vis[i][j]=0;
}
}
增加记忆性
class Solution {
public int[][] directions = { {-1,0},{1,0},{0,-1},{0,1}};
public int n, m;
public int longestIncreasingPath(int[][] matrix) {
n = matrix.length;
if(n<=0)
return 0;
m = matrix[0].length;
if(m<=0)
return 0;
int[][] memo = new int[n][m];
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
ans = Math.max(ans,dfs(matrix,i,j,memo));
}
return ans;
}
private int dfs(int[][] matrix, int i, int j, int[][] memo){
if(memo[i][j] != 0){
return memo[i][j];
}
++memo[i][j];
for(int [] dir:directions){
int ii = i + dir[0];
int jj = j + dir[1];
if(ii>=0 && ii<n && jj>=0 && jj<m && matrix[ii][jj]>matrix[i][j]){
memo[i][j] = Math.max(memo[i][j], dfs(matrix,ii,jj,memo)+1);
}
}
return memo[i][j];
}
}
343. 整数拆分 7月30日
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
贪心，剑指Offer切绳子，尽量拆成长度为3的短绳子。
class Solution {
public int integerBreak(int n) {
if(n<3){
return 1;
}
if(n==3){
return 2;
}
int ans=1;
while(n>4){
ans*=3;
n-=3;
}
ans*=n;
return ans;
}
}
114. 二叉树展开为链表 8月2日
给定一个二叉树，原地将它展开为一个单链表。
class Solution {
public void flatten(TreeNode root) {
if(root==null)
return;
TreeNode right = root.right;
TreeNode next = root.left;
if(root.left==null)
flatten(right);
else{
root.left==null;
root.right = next;
while(next.right!=null){
next = next.right;
}
next.right = right;
flatten(root.right);
}
}
}
前序遍历递归，在前序遍历的过程中得到
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
preorderTraversal(root, list);
int size = list.size();
TreeNode cur = root;
for(int i=1;i<size;i++){
TreeNode node = list.get(i);
cur.left=null;
cur.right=node;
cur = node;
}
}
public void preorderTraversal(TreeNode root, List<TreeNode> list) {
if(root==null)
return;
list.add(root);
preorderTraversal(root.left, list);
preorderTraversal(root.right, list);
}
}
二叉树非递归遍历
前序遍历非递归
class Solution{
public void flatten(TreeNode root){
List<TreeNode> list = new ArrayList<TreeNode>();
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode node = root;
while(node!=null || !stack.isEmpty()){
while(node!=null){
list.add(node);
stack.push(node);
node=node.left;
}
node=stack.pop();
node=node.right;
}
int size = list.size();
for(int i=1; i<size;i++){
TreeNode prev = list.get(i-1);
prev.left=null;
prev.right=list.get(i);
}
}
}
后序遍历非递归。
- 思路一：
依次将根结点，右节点，左节点押入栈。根->右->左，和先序遍历的
根->右->左，很像，就把先序的左右交换，访问改成压栈，压另一个栈。
class Solution{
public List<Integer> postorderTraversal(TreeNode root){
Stack<Integer> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
if(root==null) return list;
TreeNode node = root;
while(node!=null || !stack.empty()){
while(node!=null){
list.add(node);
stack.push(node);
node=node.right;
}
if(!stack.empty()){
node=stack.pop();
node=node.left;
}
}
Collections.reverse(list);
return list;
}
}
- 思路二：
要访问一个节点的条件上一个访问的节点是右儿子。我们可以增加一个变量Prev来判断当前节点Curr的上一个节点与它的关系来执行相应的操作。
- 若Prev为空(Curr节点是根节点)或者Prev是Curr的父节点，将Curr节点的左孩子和右孩子分别压入栈；
- 若Prev是Curr的左儿子，则将Curr的右儿子压入栈；
- 否则Prev是Curr的右儿子，访问Curr;
class Solution{
public List<Integer> postorderTraversal(TreeNode root){
Stack<Integer> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
if(root==null) return list;
TreeNode prev = null, cur = null;
stack.push(root);
while(!stack.empty()){
cur = stack.peek();//不要弹出
if(prev==null || prev.left==cur || prev.right==cur){
if(cur.left!=null)
stack.push(cur.left);
else if(cur.right!=null)
stack.push(cur.right);
}else if(prev == cur.left){
if(cur.right!=null)
stack.push(cur.right);
}else{
list.add(cur);
stack.pop();
}
prev = cur;
}
return list;
}
}
中序遍历非递归
用辅助栈
class Solution{
public List<Integer> inorderTraversal(TreeNode root){
List<Integer> list = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
if(root!=null) return list;
TreeNode node = root;
while(node!=null || !stack.empty()){
while(node!=null){
stack.push(node);
node=node.left;
}
if(!stack.empty()){
node=stack.pop();
list.add(node); //访问节点
node=node.right;
}
}
return list;
}
}
207. 课程表 8月4日
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
class Solution {
List<List<Integer>> edges;
int[] visited;
boolean valid = true;
public boolean canFinish(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
for(int i=0; i<numCourses; ++i){
edges.add(new ArrayList<Integer>());
}
// 用List把 边缘表示。转换成 邻接 图
visited = new int[numCourses];
for(int[] info : prerequisites){
edges.get(info[1]).add(info[0]);
}
for(int i=0; i<numCourses && valid; ++i){
if(visited[i] == 0){
if(!dfs(i)){
return false;
}
}
}
return valid;
}
public boolean dfs(int u){
visited[u] = 1;
for(int v : edges.get(u)){
if(visited[v]==1){
return false;
}else if(visited[v]==0){
if(!dfs(v)){
return false;
}
}
}
visited[u] = 2;
return true;
}
}
class Solution {
List<List<Integer>> edges;
int[] visited;
boolean valid = true;
public boolean canFinish(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
for(int i=0; i<numCourses; ++i){
edges.add(new ArrayList<Integer>());
}
// 用List把 边缘表示。转换成 邻接 图
visited = new int[numCourses];
for(int[] info : prerequisites){
edges.get(info[1]).add(info[0]);
}
for(int i=0; i<numCourses && valid; ++i){
if(visited[i] == 0){
if(!dfs(i)){
return false;
}
}
}
return valid;
}
public boolean dfs(int u){
visited[u] = 1;
for(int v : edges.get(i)){
if(visited[v]==1){
return false;
}else if(visited[v]==0){
if(!dfs(v)){
return false
}
}
}
visied[u] = 2;
return true;
}
}
很多动态规划问题大致可以按照下面5个步骤取解释： 1、状态定义 2、状态转移方程 3、初始化 4、输出 5、思考状态压缩
动态规划原理
都是把大问题拆分成小问题。寻找大问题和小问题的递推关系。解决一个个小问题，最终达到解决原问题的效果。动态规划有记忆性，填表把所有已经解决的子问题答案记录下来,在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。
198 打家劫舍
class Solution {
public int rob(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
int length = nums.length;
if(length == 1)
return nums[0];
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for(int i=2;i<length;i++){
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[length-1];
}
}
213 打家劫舍2
题目链接 题目描述：房屋都围成一圈，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
解题思路：在打家劫舍1的基础上，说给出的房子是环形排列首尾相接的。区别就是第一栋房子和最后一栋房子不能同时偷。只需要计算两种情况：
- 不偷第一个，问题就是在后边n-1个房子可以偷的最大价值。
- 不偷最后一个，问题就是在前边n-1个房子可以偷的最大价值。
这样转换就没有首尾连接的约束了，可以直接采用上一题的解法。取两种情况的最大值
class Solution {
public:
//首尾之能选一个偷
int rob(vector<int>& nums) {
//思想很简单，不偷第一家，就在后面n-1家里偷，不偷最后一家，就在前n-1家里偷
int len=nums.size();
if(len==0)
return 0;
if(len==1)
return nums[0];
int ans1 = rob1(nums, 0, len-2);
int ans2 = rob1(nums, 1, len-1);
return max(ans1,ans2);
}
int rob1(vector<int> &nums, int l, int r){
int ans = 0;
int pre=0,prepre=0;
for(int i=l;i<=r;i++){
ans = max(prepre+nums[i], pre);
prepre = pre;
pre = ans;
}
return ans;
}
};
337 打家劫舍3
题目链接 题目描述：房屋成一个二叉树结构，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
解题思路：结点r，分为偷和不偷两种情况。
偷r结点：左右儿子不能偷。最大价值等于不偷左儿子的最大价值+不偷右儿子的最大价值+r的价值
不偷r节点： 最大价值等于偷或不偷左儿子的最大价值+偷或不偷右儿子的最大价值。
class Solution {
public:
typedef pair<int, int> pii;
int rob(TreeNode* root) {
// 可行窃地区是二叉树
if(root==nullptr)
return 0;
pii ans = helper(root);
return max(ans.first, ans.second);
}
//偷r结点：左右儿子不能偷。最大价值等于不偷左儿子的最大价值+不偷右儿子的最大价值+r的价值
//不偷r节点： 最大价值等于**偷或不偷**左儿子的最大价值+**偷或不偷**右儿子的最大价值。
pii helper(TreeNode* root){
if(root==nullptr)
return {0,0};
//helper 返回 偷 这个结点能取到的最大价值，还有 不偷 这个结点时能取到的最大价值
pii l = helper(root->left);
pii r = helper(root->right);
//偷
int r0 = l.second+r.second+root->val;
//不偷当前
int r1 = max(l.first,l.second)+max(r.first,r.second);
return make_pair(r0,r1);
}
};
72 编辑距离
题目描述：删除，修改，插入，把word1变成word2的最小编辑距离
思路：动态规划，D[i][j]表示word1的前i个字母和word2的前j个之间的编辑距离。
-
D[i][j-1]为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们在 A 的末尾添加了一个相同的字符，那么D[i][j]最小可以为D[i][j-1] + 1； -
D[i-1][j]为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题。即对于 A 的第 i 个字符，我们在 B 的末尾添加了一个相同的字符，那么D[i][j]最小可以为D[i-1][j] + 1； -
D[i-1][j-1]为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们修改 A 的第 i 个字符使它们相同，那么D[i][j]最小可以为D[i-1][j-1] + 1。特别地，如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。在这种情况下，D[i][j]最小可以为D[i-1][j-1]。
如果word1[i]==word2[j]: \(\begin{aligned} D[i][j] &=\min (D[i][j-1]+1, D[i-1][j]+1, D[i-1][j-1]) \\ &=1+\min (D[i][j-1], D[i-1][j], D[i-1][j-1]-1) \end{aligned}\)
如果word1[i]!=word2[j]: \(D[i][j]=1+\min (D[i][j-1], D[i-1][j], D[i-1][j-1])\)
<img src='/edit-distance.png'>
int minDistance(string word1, string word2) {
int n = word1.length();
int m = word2.length();
// 有一个字符串为空串
if (n * m == 0) return n + m;
// DP 数组
int D[n + 1][m + 1];
// 边界状态初始化
for (int i = 0; i < n + 1; i++) {
D[i][0] = i;
}
for (int j = 0; j < m + 1; j++) {
D[0][j] = j;
}
// 计算所有 DP 值
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
int left = D[i - 1][j] + 1;
int down = D[i][j - 1] + 1;
int left_down = D[i - 1][j - 1];
if (word1[i - 1] != word2[j - 1]) left_down += 1;
D[i][j] = min(left, min(down, left_down));
}
}
return D[n][m];
}
class Solution {
public int minDistance(String word1, String word2) {
int n1 = word1.length();
int n2 = word2.length();
int[][] dp = new int[n1+1][n2+1];
for(int j=1;j<=n2;j++) dp[0][j] = dp[0][j-1]+1;
for(int i=1;i<=n1;i++) dp[i][0] = dp[i-1][0]+1;
for(int i=1;i<=n1;i++)
for(int j=1;j<=n2;j++){
if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]), dp[i-1][j-1])+1;
}
return dp[n1][n2];
}
}
99. 恢复二叉搜索树
二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下，恢复这棵树。
Morris遍历，时间复杂度O(N)，空间复杂度O(H)
class Solution {
public void recoverTree(TreeNode root) {
// 二叉搜索树
TreeNode x = null, y = null, pred = null, predecessor = null;
while(root!=null){
if(root.left!=null){
predecessor = root.left;
while(predecessor.right!=null && predecessor.right != root){
predecessor = predecessor.right;
}
if(predecessor.right == null){
predecessor.right = root;
root = root.left;
}else{
//左子树遍历完成
if(pred!=null && root.val < pred.val){
y = root;
if(x==null){
x = pred;
}
}
pred = root;
predecessor.right = null;
root = root.right;
}
}else{
if(pred!=null && pred.val > root.val){
y = root;
if(x==null){
x = pred;
}
}
pred = root;
root = root.right;
}
}
swap(y,x);
}
private void swap(TreeNode node1, TreeNode node2){
int tmp = node1.val;
node1.val = node2.val;
node2.val = tmp;
}
}
93. 复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 ‘.’ 分隔。
深度搜索，剪枝，回溯，注意前导0时候的剪枝。
class Solution {
private static final int SEG_COUNT = 4;
int[] segments;
List<String> ans = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
segments = new int[SEG_COUNT];
dfs(s, 0, 0);
return ans;
}
public void dfs(String s, int segId, int segStart) {
// 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
if(segId == SEG_COUNT && segStart == s.length()){
StringBuilder sb = new StringBuilder();
for( int i=0; i<SEG_COUNT-1; i++ ){
sb.append(segments[i]);
sb.append('.');
}
sb.append(segments[SEG_COUNT-1]);
ans.add(sb.toString());
}
if( segId == SEG_COUNT || segStart == s.length() )
return;
if(s.charAt(segStart)=='0'){
segments[segId] = 0;
dfs(s,segId+1,segStart+1);
}
int cur = 0;
for(int segEnd = segStart; segEnd < segStart+3 && segEnd < s.length() ; segEnd++){
cur = cur*10 + (s.charAt(segEnd)-'0');
if( cur>0 && cur <= 0XFF ){ //如果cur==0，也可以直接break
segments[segId] = cur;
dfs(s, segId+1, segEnd+1);
}else{
break;
}
}
}
}
696. 计数二进制子串
题目描述： 给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。 重复出现的子串要计算它们出现的次数。
解题思路：
例如0011000110的字符串转换为这样的整数数组；{2,2,3,2,1}
class Solution {
public int countBinarySubstrings(String s) {
char[] chars = s.toCharArray();
int n = chars.length;
int ans = 0;
int one = 0;
int[] count = new int[2];
int flag = 0;
int i=0;
while(i<n){
while(i<n && flag == chars[i]-'0'){
count[flag]++;
i++;
}
ans += Math.min(count[1-flag], count[flag]);
count[1-flag] = 0;
flag = 1-flag;
}
return ans;
}
}
130. 被围绕的区域 8月11日
题目描述： 给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。 找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
解题思路： 和边界的’O’直接或间接连通的’O’就是不用打叉的O。
class Solution {
private int[][] d = { {0,-1},{0,1},{1,0},{-1,0}};
public void solve(char[][] board) {
int n = board.length;
if(n==0)
return;
int m = board[0].length;
if(m==0)
return;
for(int i=0;i<n;i++){
dfs(board, i,0,n,m);
dfs(board, i, m-1,n,m);
}
for(int i=0;i<m ;i++){
dfs(board, 0,i,n,m);
dfs(board, n-1,i,n,m);
}
for(int i=0;i<n;i++)
for(int j=0; j<m;j++){
if(board[i][j]=='A')
board[i][j]='O';
else if(board[i][j]=='O')
board[i][j] = 'X';
}
}
private void dfs(char[][] board, int i, int j,int n, int m ){
if(i<0 || i>=n || j<0 || j>=m || board[i][j]!='O'){
return ;
}
board[i][j] = 'A';
for(int i=0;i<4;i++){
dfs(board,i+d[i][0],j+d[i][1],n,m);
}
}
}
107. 二叉树的层次遍历 II 9月6日
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
if (root == null) {
return levelOrder;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>(); //队列
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<Integer>();
for(int i=0;i<size;i++){
TreeNode node = queue.poll();
level.add(node.val);
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
}
levelOrder.add(0, level);
}
return levelOrder;
}
}
77. 组合 9月6日
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
- 方法一 找出所有组合，不重复，就按照某种顺序来展开搜索，这样就能做到不重复不遗漏。
class Solution {
public List<List<Integer>> combine(int n, int k) {
Stack<Integer> stack = new Stack<>();
List<List<Integer>> res = new ArrayList<List<Integer>>();
dfs(res, stack, k, 1,n);
return res;
}
private void dfs(List<List<Integer>> res, Stack<Integer> stack, int k, int start, int n){
if(n - start + 1 < k){ //减少搜索情况
return;
}
if(k<=0){
res.add(new ArrayList<>(stack));
return;
}
for(int i = start; i <= n; i++){
stack.push(i);
dfs(res, stack, k-1, i+1, n);
stack.pop(i);
}
return;
}
}
- 方法二 按每一个数，选还是不选画出二叉树。
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(k<=0 || n<k)
return ans;
Stack<Integer> stack = new Stack<Integer>();
dfs(res, stack, k, 1, n);
return res;
}
private void dfs(List<List<Integer>> res, Stack<Integer> stack, int k, int start, int n){
if(k == 0 ){
res.add(new ArrayList<Integer>(stack));
return;
}
if( start > n - k + 1 ){
return;
}
// 当前数字不要
dfs(res, stack, k, start+1, n);
// 要当前数字
stack.push(start);
dfs(res, stack, k-1, start+1, n);
stack.pop();
return;
}
}
15. 三数之和 9月14日
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。 参考
class Solution {
List<List<Integer>> res;
public List<List<Integer>> threeSum(int[] nums) {
res = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) break; // min > 0 后续没必要找了
if (i == 0 || nums[i] != nums[i - 1]) twoSum(nums, i); // 1层去重
}
return res;
}
public void twoSum(int[] nums, int index) {
int i = index + 1, j = nums.length - 1, item = nums[index], target = -item;
long sum;
while (i < j) {
sum = (long) nums[i] + (long) nums[j];
if (sum == target) {
res.add(Arrays.asList(item, nums[i], nums[j]));
// 2层去重，111333这种情况，只需要算一次，i,j 移动到 最内部 1，3
while (i + 1 < j && nums[i+1] == nums[i]) i++;
while (j - 1 > i && nums[j-1] == nums[j]) j--;
}
if (sum > target) j--;
else i++;
}
}
}
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i<n;i++){
if(i>0 && nums[i]==nums[i-1]) continue;
if(nums[i]>0) break;
int L=i+1;
int R=n-1;
while(L<R){
int sum = nums[i]+nums[L]+nums[R];
if(sum==0){
list.add(Arrays.asList(nums[i],nums[L],nums[R]));
//去除结果
while(L<R && nums[L]==nums[L+1])L++;
while(L<R && nums[R-1]==nums[R])R--;
L++;
R--;
}else if(sum>0){
R--;
}else if(sum<0){
L++;
}
}
}
return list;
}
}
685. 冗余连接 II 9月17日
并查集，入度都应该是1，根的入度为0。若有多个答案，返回最后出现的那条边。
- 不能有入度为2的点
- 在没有入度为2的点的时候，不能有环
class Solution {
public int[] findRedundantDirectedConnection(int[][] edges) {
//1 初始化
int n = edges.length;
int[] inDegree = new int[n+1];
for(int[] edge:edges){
inDegree[edge[1]]++;
}
//2 检查入度为2的点
for(int i=n-1; i>=0; i--){
if(inDegree[edges[i][1]]>1){
if(!judgeCircle(edges,n,i)){
return edges[i];
}
}
}
//3 再试试删除入度为1的边
for(int i=n-1; i>=0; i--){
if(inDegree[edges[i][1]]==1){
if(!judgeCircle(edges,n,i)){
return edges[i];
}
}
}
return new int[0];
}
//用并查集看看有没有环
public boolean judgeCircle(int[][] edges, int len, int removeEdgeIndex){
//
UnionFind ufset = new UnionFind(len);
for(int i=0;i<len;i++){
if(i==removeEdgeIndex) continue;
if(!ufset.same(edges[i][0], edges[i][1])){
ufset.union(edges[i][0], edges[i][1]);
}else{
return true;//有环
}
}
return false;
}
private class UnionFind{
private int[] parent;
public UnionFind(int n){
parent = new int[n+1];
for(int i=0; i<n+1; i++){
parent[i] = i;
}
}
public void union(int x, int y){
x=find(x);
y=find(y);
//有向图，x设为y的父节点
if(x!=y){
parent[y]=x;
}
}
public boolean same(int x,int y){
int rootx = find(x);
int rooty = find(y);
return rootx==rooty;
}
public int find(int x){
return (parent[x]==x) ? x : (x = find(parent[x]));
}
}
}
47. 全排列 II 9月19日
给定一个可包含重复数字的序列，返回所有不重复的全排列。
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
class Solution {
private boolean[] vis;
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer> > res = new ArrayList<List<Integer>>();
List<Integer> aPerm = new ArrayList<>();
int length = nums.length;
vis = new boolean[length];
Arrays.fill(vis, false);
// 排序是为了更好的去重。
Arrays.sort(nums);
backtrace(nums, res, 0, length, aPerm);
return res;
}
private void backtrace(int[] nums, List<List<Integer>> res, int index, int length, List<Integer> aPerm){
if(index == length){
res.add(new ArrayList<Integer>(aPerm));
return;
}
for( int i = 0; i < length; i++){
if(vis[i] || (i>0 && nums[i]==nums[i-1] && !vis[i-1])) continue;//去重复
vis[i]=true;
aPerm.add(nums[i]);
backtrace(nums, res, index+1, length, aPerm);
vis[i]=false;
aPerm.remove(index);
}
}
}
46. 全排列 9月19日
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
class Solution {
private boolean[] vis;
public List<List<Integer>> permute(int[] nums) {
int length = nums.length;
vis= new boolean[length];
Arrays.fill(vis, false);
List<List<Integer>> res = new ArrayList<>();
List<Integer> aPerm = new ArrayList<>();
//可以不排序
backtrace(nums, res, aPerm, 0 , length);
return res;
}
private void backtrace(int[] nums, List<List<Integer>> res, List<Integer> aPerm,int index, int length){
if(index==length){
res.add(new ArrayList<>(aPerm));
return;
}
for(int i=0;i<length; i++){
if(vis[i]) continue;
vis[i]=true;
aPerm.add(nums[i]);
backtrace(nums, res, aPerm, index+1, length);
vis[i]=false;
aPerm.remove(index);
}
}
}
404. 左叶子之和 9月19日
非递归遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
int ans=0;
Stack<TreeNode> stack = new Stack<>();
if(root==null) return ans;
TreeNode node = root;
while(node!=null || !stack.empty()){
while(node!=null){
stack.push(node);
node=node.left;
}
node = stack.pop();
if(!stack.empty() && node.left==null && node.right==null && stack.peek().left==node){
ans+=node.val;
}
node=node.right;
}
return ans;
}
}
递归便遍历，深度优先 或 广度优先
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null) return 0;
return dfs(root);
}
public int dfs(TreeNode root){
int ans = 0;
if(root.left!=null){
ans += isLeaf(root.left) ? root.left.val : dfs(root.left);
}
if(root.right!=null){
ans += isLeaf(root.right) ? 0 : dfs(root.right);
}
return ans;
}
private boolean isLeaf(TreeNode node){
return node.left==null && node.right==null;
}
}
117. 填充每个节点的下一个右侧节点指针 II 9月28日
常数级额外空间
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
private Node last = null, nextStart = null;
public Node connect(Node root) {
if(root==null)
return null;
Node start = root;
while(start!=null){
nextStart=null;
last=null;
for(Node p = start; p!=null; p=p.next){
if(p.left!=null){
help(p.left);
}
if(p.right!=null){
help(p.right);
}
}
start=nextStart;
}
return root;
}
private void help(Node node){
if(last!=null){
last.next=node;
}
if(nextStart==null)
nextStart=node;
last=node;
}
}
145. 二叉树的后序遍历 9月29日
非递归方法 TreeNode prev = null, cur = null;
- prev
是空或者prev是cur的父节点，尝试把cur的做左子节点或右子节点压栈 - prev是cur的
左子节点，把cur的右子节点压栈 else: prev是cur的右子节点或者其他情况。访问cur。
/**
* 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 {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
if(root==null) return list;
TreeNode cur = null, prev = null;
stack.push(root);
while(!stack.empty()){
cur = stack.peek();
if(prev = null || prev.left==cur || prev.right==cur){
if(cur.left!=null){
stack.push(cur.left);
}else if(cur.right!=null){
stack.push(cur.right);
}
}else if(prev==cur.left){
if(cur.right!=null)
stack.push(cur.right);
}else{
list.add(cur);
stack.pop();
}
prev = cur;
}
return list;
}
}
Morris遍历
利用树的大量空闲指针，实现空间开销的极限缩减。
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
TreeNode p1 = root, p2 = null;
while (p1 != null) {
p2 = p1.left;
if (p2 != null) {
while (p2.right != null && p2.right != p1) {
p2 = p2.right;
}
if (p2.right == null) {
p2.right = p1;
p1 = p1.left;
continue;
} else {
p2.right = null;
addPath(res, p1.left);
}
}
p1 = p1.right;
}
addPath(res, root);
return res;
}
public void addPath(List<Integer> res, TreeNode node) {
List<Integer> tmp = new ArrayList<Integer>();
while (node != null) {
tmp.add(node.val);
node = node.right;
}
for (int i = tmp.size() - 1; i >= 0; --i) {
res.add(tmp.get(i));
}
}
}
LCP 19. 秋叶收藏集 10月1日
求字符串最少调整次数。 状态机思想
class Solution {
public int minimumOperations(String leaves) {
int n = leaves.length();
char[] chars = leaves.toCharArray();
int[][] dp = new int[n][3];
dp[0][0] = isYellow(chars[0]);
dp[1][2] = dp[0][1] = dp[0][2] = Integer.MAX_VALUE;
for(int i=1; i<n; i++){
dp[i][0] = dp[i-1][0] + isYellow(chars[i]);
dp[i][1] = Math.min(dp[i-1][0], dp[i-1][1]) + isRed(chars[i]);
if(i>1)
dp[i][2] = Math.min(dp[i-1][1], dp[i-1][2]) + isYellow(chars[i]);
}
return dp[n-1][2];
}
private int isYellow(char c){
return c=='y' ? 1 : 0;
}
private int isRed(char c){
return c=='r' ? 1 : 0;
}
}
状态压缩
class Solution {
public int minimumOperations(String leaves) {
int n = leaves.length();
char[] chars = leaves.toCharArray();
int f1=0, f2=0, f3=0;
f1 = isYellow(chars[0]);
f2=f3=Integer.MAX_VALUE;
for(int i=1; i<n; i++){
if(i>1)
f3 = Math.min(f2, f3) + isYellow(chars[i]);
f2 = Math.min(f1, f2) + isRed(chars[i]);
f1= f1 + isYellow(chars[i]);
}
return f3;
}
private int isYellow(char c){
return c=='y' ? 1 : 0;
}
private int isRed(char c){
return c=='r' ? 1 : 0;
}
}
125. 乘积最大子数组 10月16日
因为乘法有正负数的情况，子问题可能不是从i-1这个状态变过来的。
也没有用复杂的动态规划，就是在维护一个数组记录以nums[i]结尾的子数组乘积的最小值。
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int[] Fmax = new int[n];
int[] Fmin = new int[n];
System.arraycopy(nums, 0, Fmax, 0, n);
System.arraycopy(nums, 0, Fmin, 0, n);
for(int i=1;i<n;i++){
int num = nums[i];
Fmax[i] = Math.max(Fmax[i-1]*num, Math.max(Fmin[i-1]*num, num));
Fmin[i] = Math.min(Fmax[i-1]*num, Math.min(Fmin[i-1]*num, num));
}
int ans = Fmax[0];
for(int i=1;i<n;i++){
ans = Math.max(ans, Fmax[i]);
}
return ans;
}
}
977. 有序数组的平方 10月16日
给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
- 简单的计算后排序
- 双指针
原数组非递减，把负数和正数分开，双指针类似归并排序
class Solution {
public int[] sortedSquares(int[] A) {
int length = A.length;
int negSize=0;
for(int i=0;i<length; i++){
if(A[i]<0) negSize++;
A[i] = A[i]*A[i];
}
int Ptr1 = negSize-1, Ptr2=negSize;
int[] ans = new int[length];
int index=0;
while(Ptr1>=0 && Ptr2<length){
if(A[Ptr1]<=A[Ptr2]){
ans[index++]=A[Ptr1--];
}else{
ans[index++]=A[Ptr2++];
}
}
while(Ptr1>=0 && index<length){
ans[index++]=A[Ptr1--];
}
while(Ptr2<length && index<length){
ans[index++]=A[Ptr2++];
}
return ans;
}
}
双指针二 使用两个指针分别指向位置 $0$ 和 $n-1$，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况。
class Solution {
public int[] sortedSquares(int[] A) {
int n = A.length;
int[] ans = new int[n];
for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
if (A[i] * A[i] > A[j] * A[j]) {
ans[pos] = A[i] * A[i];
++i;
} else {
ans[pos] = A[j] * A[j];
--j;
}
--pos;
}
return ans;
}
}
234. 回文链表 10月23日
请判断一个链表是否为回文链表。 快慢指针，从中间找
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head==null)
return true;
Stack<ListNode> stack = new Stack<>();
ListNode node1 = head;
ListNode node2 = head;
while(node2!=null && node2.next!=null){
stack.push(node1);
node1=node1.next;
node2=node2.next.next;
if(node2!=null && node2.next==null){
stack.push(node1);
}
}
while(!stack.empty() && node1!=null){
ListNode left = stack.pop();
if(left.val!=node1.val)
return false;
node1=node1.next;
}
return true;
}
}
347. 前 K 个高频元素 11月22日
堆的方法
class Solution {
public int[] topKFrequent(int[] nums, int k){
Map<Integer, Integer> occurences = new HashMap<Integer, Integer>();
for(int num: nums){
occurences.put(num, occurences.getOrDefault(num, 0)+1);
}
// 最小堆. int[]，int[0]是数字，int[1]是出现的次数。 堆里的元素 应该包含 num和频率，因为根据频率比大小
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>(){
public int compare(int[] m, int[] n){
return m[1] - n[1];
}
});
for(Map.Entry<Integer, Integer> entry: occurences.entrySet()){
int num = entry.getKey(), count = entry.getValue();
if(queue.size() >= k){
if(queue.peek()[1] < count){
queue.poll();
queue.offer(new int[]{num, count});
}
}else{
queue.offer(new int[]{num, count});
}
}
int[] ret = new int[k];
for(int i=0; i<k; i++){
ret[i] = queue.poll()[0];
}
return ret;
}
}
快排
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
for (int num : nums) {
occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
}
List<int[]> values = new ArrayList<int[]>();
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
values.add(new int[]{num, count});
}
int[] ret = new int[k];
qsort(values, 0, values.size() - 1, ret, 0, k);
return ret;
}
public void qsort(List<int[]> values, int start, int end, int[] ret, int retIndex, int k) {
int picked = (int) (Math.random() * (end - start + 1)) + start;
Collections.swap(values, picked, start);
int pivot = values.get(start)[1];
int index = start;
for (int i = start + 1; i <= end; i++) {
if (values.get(i)[1] >= pivot) {
Collections.swap(values, index + 1, i);
index++;
}
}
Collections.swap(values, start, index);
if (k <= index - start) {
qsort(values, start, index - 1, ret, retIndex, k);
} else {
for (int i = start; i <= index; i++) {
ret[retIndex++] = values.get(i)[0];
}
if (k > index - start + 1) {
qsort(values, index + 1, end, ret, retIndex, k - (index - start + 1));
}
}
}
}
437. 路径总和 III 11月29日
class Solution {
int ans = 0;
public int pathSum(TreeNode root, int target) {
if(root==null )
return 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0,1);
pathSum(root, 0, target, map);
return ans;
}
private void pathSum(TreeNode root, int cur, int target, HashMap<Integer,Integer> map){
if(root==null)
return;
cur = cur + root.val; //现在的和
ans += map.getOrDefault(cur-target, 0);
map.put(cur, map.getOrDefault(cur, 0) + 1);
pathSum(root.left, cur, target, map);
pathSum(root.right, cur, target, map);
// 要去掉
map.put(cur, map.getOrDefault(cur,0)-1);
}
}
338. 比特位计数 12月7日
打表方法。看起来像动态规划 $res[i] = res[i&(i-1)] + 1$
class Solution {
public int[] countBits(int num) {
int[] res = new int[num+1];
res[0] = 0;
for(int i=1; i<= num; i++){
res[i] = res[i&(i-1)] + 1;
}
return res;
}
}
494. 目标和 12月7日 ⭐️
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从
+或-中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 提示：
数组非空，且长度不会超过 20 。 初始的数组的和不会超过 1000 。 保证返回的最终结果能被 32 位整数存下。
解析： 类似于 0 1 背包的动态规划。
public class Solution{
public int findTargetSumWays(int[] nums, int S){
//初始化都是0
int[][] dp = new int[nums.length][2001];
dp[0][nums[0]+1000] = 1;
dp[0][1000-nums[0]] += 1;
for(int i=1;i<nums.length;i++){
for(int j=-1000;j<=1000;j++){
if(dp[i-1][j+1000] > 0){ // 可不可以达到
dp[i][j+1000+nums[i]] += dp[i-1][j+1000];
dp[i][j+1000-nums[i]] += dp[i-1][j+1000];
}
}
}
return S > 1000 ? 0 : dp[nums.length - 1][S + 1000];
}
}
538. 把二叉搜索树转换为累加树 12月7日
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
解析：中序遍历先访问右子节点。
class Solution {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
if(root==null){
return null;
}
convertBST(root.right);
root.val += sum;
sum = root.val;
convertBST(root.left);
return root;
}
}
560. 和为K的子数组 12月7日
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
前缀和，哈希
class Solution {
public int subarraySum(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0;
int ans = 0;
for(int num: nums){
sum += num;
ans += map.getOrDefault(sum-k,0);
map.put(sum, map.getOrDefault(sum,0)+1);
}
return ans;
}
}
617. 合并二叉树 12月7日
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if(t1 == null && t2 == null){
return null;
}
if(t1 == null)
return t2;
if(t2 == null)
return t1;
t1.val += t2.val;
t1.right = mergeTrees(t1.right, t2.right);
t1.left = mergeTrees(t1.left, t2.left);
return t1;
}
}
621. 任务调度器 12月9日
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间
解析：贪心，队列，数组
class Solution{
public int leastInterval(char[] tasks, int n){
Map<Character, Integer> freq = new HashMap<>();
for(char ch: tasks){
freq.put(ch, freq.getOrDefault(ch, 0) + 1);
}
int m = freq.size();
List<Integer> nextValids = new ArrayList<>();
List<Integer> res = new ArrayList<>();
int n = tasks.length;
int time = 0;
for(Map.Entry<Character, Integer> entry : freq.entrySet()){
int value = entry.getValue();
nextValids.add(1);
res.add(value);
}
// 遍历n次就结束
for( int i=0 ; i < n; i++ ){
time++;
int minValid = Integer.MAX_VALUE;
for(int j = 0; j < m; j++){
if( res.get(j) > 0 && nextValids.get(j) < minValid ){
minValid = nextValids.get(j);
}
}
time = Math.max(time, minVlid);
int best = -1;
for (int j = 0; j < m; ++j) {
if (res.get(j) != 0 && nextValids.get(j) <= time) {
if (best == -1 || res.get(j) > res.get(best)) {
best = j;
}
}
}
nextValids.set(best, time + n + 1);
res.set(best, res.get(best) - 1);
}
return time;
}
}
739. 每日温度 12月10日
Link
栈，哈希表。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
class Solution {
public int[] dailyTemperatures(int[] T) {
Stack<Integer> stack = new Stack<Integer>();
int length = T.length;
int[] ans = new int[length];
for(int i=0; i < length; i++){
int num = T[i];
while(!stack.empty() && num > T[stack.peek()]){
int index = stack.pop();
ans[index] = i-index;
}
stack.push(i);
}
return ans;
}
}
406. 根据身高重建队列 12月10日
贪心
解析： hi 升序排列，ki降序排列。 按照排序后的顺序一次进入队列。进入队列的位置找第ki+1个空位置。
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, new Comparator<int[]>(){
public int compare(int[] p1, int[] p2){
if(p1[0] != p2[0]){
return p1[0] - p2[0];
}else{
return p2[1] - p1[1];
}
}
});
int n = people.length;
int[][] ans = new int[n][];// 为啥这么写
for(int[] person : people ){
int space = person[1]+1;//找第p[i]+1个空位置
for(int i=0;i<n;i++){
if(ans[i]==null){
space--;
if(space==0){
ans[i] = person;
break;
}
}
}
}
return ans;
}
}
438. 找到字符串中所有字母异位词 12月10日 ⭐️
哈希表
自己写的比较复杂
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<Integer>();
int length_p = p.length();
int length_s = s.length();
if(length_s < length_p){
return res;
}
// 哈希表
Map<Character, Integer> map = new HashMap<>();
for(int i=0; i<length_p; i++){
map.put(p.charAt(i), map.getOrDefault(p.charAt(i),0)+1);
}
int count = map.size();
for(int i=0; i<length_p; i++){
Integer value = map.get(s.charAt(i));
if(value!=null){
map.put(s.charAt(i), value-1);
if(value==1){
count--;
}else if(value==0){
count++;
}
}
}
if(count==0){
res.add(0);
}
for(int i=length_p; i<length_s; i++)
{
int lastRemoveIndex = i - length_p;
char lastChar = s.charAt(lastRemoveIndex);
Integer value;
if((value=map.get(lastChar))!=null){
// value
map.put(lastChar, value+1);
if(value+1==0){
count--;
}else if(value==0){
count++;
}
}
char curChar = s.charAt(i);
if((value=map.get(curChar))!=null){
map.put(curChar, value-1);
if(value-1==0){
count--;
}else if(value==0){
count++;
}
}
if(count==0){
res.add(lastRemoveIndex+1);
}
}
return res;
}
}
1203. 项目管理 1月12日
拓扑排序，确定一个序列，满足边\<u->v\>之间的依赖，拓扑不能有环。
题目中有2中拓扑序
- 项目和项目之间的依赖
- 组和组之间的依赖
首先解决组间的依赖顺序。之后在每个组里面，把属于同一组的任务顺序确定。这两个步骤里面发现有环就表示不能确定顺序。
/*
输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
输出：[6,3,4,1,5,2,0,7]
*/
class Solution {
public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
List<List<Integer>> groupItem = new ArrayList<List<Integer>>();
for (int i = 0; i < n + m; ++i) {
groupItem.add(new ArrayList<Integer>());
}
List<List<Integer>> groupGraph = new ArrayList<List<Integer>>();
for(int i=0; i<n+m; i++)
{
groupGraph.add(new ArrayList<Integer>());
}
List<List<Integer>> itemGraph = new ArrayList<List<Integer>>();
for(int i = 0; i < n; i++)
{
itemGraph.add(new ArrayList<Integer>());
}
// 入度数组，组间和组内
int[] groupDegree = new int[n+m];
int[] itemDegree = new int[n];
// id?
List<Integer> id = new ArrayList<>();
for(int i=0; i < n + m; i++)
{
id.add(i);
}
int leftId = m;
// 无人接手的项目，单独一个group
for(int i=0; i<n; i++)
{
if(group[i]==-1)
{
group[i]=leftId++;
}
groupItem.get(group[i]).add(i);
}
// 建立依赖图关系, 遍历Tasks
for(int i=0; i < n; i++)
{
int curGroupId = group[i];
for(int item: beforeItems.get(i))
{
int beforeGroupId = group[item];
if(beforeGroupId!=curGroupId)
{
groupGraph.get(beforeGroupId).add(curGroupId);
groupDegree[curGroupId]++;
}else{
itemDegree[i]++;
itemGraph.get(item).add(i);
}
}
}
//建立好图过后，组间关系拓扑排序
List<Integer> groupTopSort = topSort(groupDegree, groupGraph, id);
if (groupTopSort.size() == 0) {
return new int[0];
}
int[] ans = new int[n];
int index = 0;
// 组内关系排序
for (int curGroupId : groupTopSort) {
int size = groupItem.get(curGroupId).size();
if (size == 0) {
continue;
}
List<Integer> res = topSort(itemDegree, itemGraph, groupItem.get(curGroupId));
if (res.size() == 0) {
return new int[0];
}
for (int item : res) {
ans[index++] = item;
}
}
return ans;
}
public List<Integer> topSort(int[] deg, List<List<Integer>> graph, List<Integer> items) {
Queue<Integer> queue = new LinkedList<Integer>();
for (int item : items) {
if (deg[item] == 0) {
queue.offer(item);
}
}
List<Integer> res = new ArrayList<Integer>();
while (!queue.isEmpty()) {
int u = queue.poll();
res.add(u);
for (int v : graph.get(u)) {
if (--deg[v] == 0) {
queue.offer(v);
}
}
}
return res.size() == items.size() ? res : new ArrayList<Integer>();
}
}
25. K 个一组翻转链表 2月12日
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
设置一个函数，反转其中一段链表，输入为这段链表的首尾节点，在里面in-place的反转
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 只能使用常数额外空间
if(k<=1) return head;
ListNode hair = new ListNode(0);
hair.next = head;
ListNode prev = hair;
while(head!=null){
ListNode tail = head;
for(int i=0; i<k-1; i++) {
tail = tail.next;
if(tail==null){
return hair.next;
}
}
ListNode next = tail.next;
reverse(head, tail);
prev.next = tail;
head.next = next;
prev = head;
head = next;
}
return hair.next;
}
// myreverse, 只把从 head 到 tail 这段颠倒顺序，返回新的 head和 tail 节点
public void reverse(ListNode head, ListNode tail) {
ListNode prev = tail.next;
ListNode p = head;
while(prev != tail) {
ListNode next = p.next;
p.next = prev;
prev = p;
p = next;
}
}
}
91. 解码方法 4月21日
动态规划，自己的代码
class Solution {
public int numDecodings(String s) {
// 多少种解码方式. 1~26的数字
// 动态规划， 暴力搜索肯定可以，为什么这里可以动态规划呢
int n = s.length();
if (n==0) return 0;
int[] dp = new int[n+1];
dp[0]=1;
char[] chars = s.toCharArray();
for(int i=1; i<=n; i++)
{
if( chars[i-1]=='0'){
if(i>=2 && (chars[i-2]=='1'||chars[i-2]=='2')){
dp[i] = dp[i-2];
}
}else{
dp[i]=dp[i-1];
if(i>=2 && chars[i-2]!='0'){
int num = string2int(s.substring(i-2,i));
if( num>=1 && num<=26){
dp[i]+=dp[i-2];
}
}
}
}
return dp[n];
}
private int string2int(String s){
int n=s.length();
int ans = 0;
for(int i=0;i<n;i++){
ans = ans*10+(s.charAt(i)-'0');
}
return ans;
}
}
官方代码
class Solution {
public int numDecodings(String s) {
int n = s.length();
int[] f = new int[n + 1];
f[0] = 1;
for (int i = 1; i <= n; ++i) {
if (s.charAt(i - 1) != '0') {
f[i] += f[i - 1];
}
if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
f[i] += f[i - 2];
}
}
return f[n];
}
}
403. 青蛙过河 4月29日
class Solution {
public boolean canCross(int[] stones) {
HashMap<Integer, Set<Integer> > map = new HashMap<>();
for(int i=0; i < stones.length; i++) {
map.put(stones[i], new HashSet<Integer>());
}
map.get(stones[0]).add(0);
for(int i=0; i < stones.length; i++){
for(int laststep : map.get(stones[i])){
for(int step = laststep-1; step<=laststep+1; step++){
if(step>0 && map.containsKey(stones[i]+step)){
map.get(stones[i]+step).add(step);
}
}
}
}
return map.get(stones[stones.length-1]).size()>0;
}
}
224. 基本计算器 5月15日
题目链接 本题只有连续的加减法，计算最后的答案可以用类似栈的结构，扫描的过程作同时做括号展开。 本意就是将所有的数字展开相加。 比如，- (- 10 + (6 - (-2 + 3))) 被展开成 (–10) + (-6) + (—2) + (–3)
class Solution {
public int calculate(String s) {
char[] chars = s.toCharArray();
int n = s.length();
Stack<Integer> stack = new Stack<Integer>();
int sign = 1;
stack.push(sign);
int res = 0;
for(int i=0; i < n; ) {
char c = chars[i++];
switch (c){
case ' ':
case '+':break;
case '-':
sign = -sign;
break;
case '(':
stack.push(sign);
break;
case ')':
stack.pop();
sign = stack.peek();
break;
default:
int num = c - '0';
while(i<n && chars[i]>='0' && chars[i]<='9') {
num = num*10 + (chars[i] - '0');
i++;
}
res += sign*num;
sign = stack.peek();
break;
}
}
return res;
}
}
772. 基本计算器III 5月15日
四则运算，支持括号。逆波兰表达式解法
参考：772 计算器III
class Solution {
// 包含递归
public int calculate(String s) {
int n = s.length();
int curRes = 0, res = 0;
long num = 0; // num 非负整数，表示当前正在读取的数字
char op = '+';
for( int i=0; i<n; i++) {
char c = s.charAt(i);
if (isDigit(c)) {
num = num * 10 + c - '0';
}
else if (c == '(') {
int j = i, cnt = 0; // 找与当前左括号对应的 ')'
for(; i < n; i++) {
if (s.charAt(i) == '(') ++cnt;
if (s.charAt(i) == ')') --cnt;
if (cnt == 0) break;
}
num = calculate(s.substring( j+1, i ));
}
if (c == '+' || c == '-' || c == '*' || c =='/' || i == n - 1) {
switch (op){
case '+': curRes += num; break;
case '-': curRes -= num; break;
case '*': curRes *= num; break;
case '/': curRes /= num; break;
}
if (c == '+' || c == '-' || i == n-1) {
res += curRes;
curRes = 0;
}
op = c;
num = 0;
}
}
return res;
}
private boolean isDigit(char c) {
return c >= '0' && c <= '9';
}
}
150. 逆波兰表达式求值 5月15日
class Solution {
private Set<String> operators;
private Stack<Long> operands;
public int evalRPN(String[] tokens) {
operators = new HashSet<String>(){ {
add("*");
add("/");
add("+");
add("-");
}};
// stack 解法
operands = new Stack<>();
for( String token : tokens) {
if(operators.contains(token)){
HandleOperator(token);
}else{
HandleNumber(token);
}
}
return operands.peek().intValue();
}
private void HandleOperator(String token){
Long a = operands.pop();
Long b = operands.pop();
switch (token){
case "+":
operands.push(a+b);
break;
case "-":
operands.push(b-a);
break;
case "*":
operands.push(b*a);
break;
case "/":
operands.push(b/a);
break;
}
}
private void HandleNumber(String token){
Long ret = (long)0;
int sign = 1;
int i=0;
if(token.charAt(i)=='-'){
sign = -sign;
i++;
}
for(; i < token.length(); i++){
char c = token.charAt(i);
ret = ret*10 + c - '0';
}
ret = sign*ret;
operands.push(ret);
}
}
930. 和相同的二元子数组 7月8日
前缀表的方法。扫描数组的过程记录和为x的数量。
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
int n = nums.length;
Map<Integer, Integer> prefixSumMap = new HashMap<>();
// 前缀和
int sum = 0;
int res = 0;
for (int num: nums) {
prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0)+1);
sum += num;
res += prefixSumMap.getOrDefault(sum-goal,0);
}
return res;
}
}
滑动窗口
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
int n = nums.length;
int left1 = 0, left2 = 0, right = 0;
int sum1 = 0, sum2 = 0;
int ret = 0;
while (right < n) {
sum1 += nums[right];
while (left1 <= right && sum1 > goal) {
sum1 -= nums[left1];
left1++;
}
sum2 += nums[right];
while (left2 <= right && sum2 >= goal) {
sum2 -= nums[left2];
left2++;
}
ret += left2 - left1;
right++;
}
return ret;
}
}
468. 验证IP地址 7月31日
分治验证，也可用正则表达式库，Pattern: ([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])
注意 java 的 split函数：如果limit = -1 。那么返回的数组会保留 空字符串”“。
class Solution {
public String validIPAddress(String IP) {
// 编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址。
if (IP.chars().filter(ch -> ch == '.').count() == 3) {
return validateIPv4(IP);
} else if (IP.chars().filter(ch -> ch == ':').count() == 7) {
return validateIPv6(IP);
}
return "Neither";
}
private String validateIPv4(String IP) {
String[] nums = IP.split("\\.",-1); // 正则表达式，.需要转义！！ limit = -1 。那么nums数组会保留 空字符串""。
for(String num : nums) {
if (num.length() == 0 || num.length() >= 4) return "Neither";
if (num.charAt(0) == '0' && num.length() != 1) return "Neither";
int number = 0;
for(char c : num.toCharArray()) {
if (c < '0' || c > '9') return "Neither";
number = number * 10 + (c-'0');
if (number > 255) {
return "Neither";
}
}
}
return "IPv4";
}
public String validateIPv6(String IP) {
String[] nums = IP.split(":", -1);
String hexdigits = "0123456789abcdefABCDEF";
for (String x : nums) {
if (x.length() == 0 || x.length() > 4) return "Neither";
for (Character ch : x.toCharArray()) {
if (hexdigits.indexOf(ch) == -1) return "Neither";
}
}
return "IPv6";
}
}
任意进制转换
编译后的程序用在我的dotfiles中 使用：
➜ radix FFF 16 32
3VV
➜ radix FFF 16 2
111111111111
➜ radix FFF 16 3
12121200
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;
string getQuotientAndRemainder(
string originNumber,
int radix_from,
int radix_to,
int & remainder) {
remainder = 0;
int a = 0;
for(int i=0; i<originNumber.size(); i++) {
// 任何进制的数，都可以和不同的radix做除法，
// 模拟 除法手算的方法的，
// remainder 和 自己的进制radix_from相乘
a = (remainder * radix_from) + (originNumber[i] - '0');
originNumber[i] = a / radix_to + '0';
remainder = a % radix_to;
}
int startIndex = 0;
while (originNumber[startIndex] == '0') {
startIndex++;
}
return originNumber.substr(startIndex);
}
string convert(string originNumber, int radix_from, int radix_to) {
string result = "";
char c;
int remainder = 0;
while(originNumber.size() != 0) {
originNumber = getQuotientAndRemainder(originNumber, radix_from, radix_to, remainder);
result = char(remainder+'0') + result;
}
return result;
}
int main(int argc, char*argv[]) {
// 表示数字的字符串，radix from，radix to
if (argc < 4) {
cout<<"radixConverter number radix_from radix_to"<<endl;
return 0;
}
string originalNumber = string(argv[1]);
int radix_from = atoi(argv[2]);
int radix_to = atoi(argv[3]);;
string bistring = convert(originalNumber, radix_from, radix_to);
cout<<bistring;
}
847. 访问所有节点的最短路径 8月7日
题目链接、
class Solution {
// https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes/
public int shortestPathLength(int[][] graph) {
// 用三元组来搜索
int n = graph.length;
// 队列
Queue<int[]> que = new LinkedList<int[]>();
// 同一个节点u， 和 到达它时节点经过情况，只能被搜索一次，防止重复搜索
boolean[][] seen = new boolean[n][1 << n];
for(int i=0; i<n; i++) {
// 三元组， 节点编号，节点经过请款过，当前走过距离
que.offer(new int[]{i, 1<<i, 0});
seen[i][1<<i] = true;
}
while (!que.isEmpty()) {
// 如果队列不是空的
int[] state = que.poll();
int u = state[0];
int bitmap = state[1];
int dist = state[2];
if (bitmap == (1<<n) - 1) {
return dist;
}
for (int v : graph[u]) {
int nBitMap = bitmap | (1<<v);
if (!seen[v][nBitMap]) {
int[] nextState = new int[]{v, nBitMap, dist+1};
que.offer(nextState);
seen[v][nBitMap] = true;// 因为是广度优先搜索，所以不可能之后遇到这个状态，走过的路径会更小
}
}
}
return -1;
}
}
1786. 从第一个节点出发到最后一个节点的受限路径数 8月13日
受限路径 为满足 distanceToLastNode(zi) > distanceToLastNode(zi+1) 的一条路径
记忆化搜索，Dijkstra
#include <cstdio>
#include <utility>
#include <algorithm>
#include <queue>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
struct DijkNode{
// 需要知道 该节点当前距离
int d;
// 需要知道该节点是谁
int u;
bool operator > (const DijkNode& a) const
{
return d > a.d;
}
DijkNode(int u, int d):u(u), d(d){}
};
class Solution {
private:
// 把图的输入 边，转为 邻接表
vector<vector<pair<int, int> > > E;
// Dijkstra 计算每个节点当前得到的最短路
vector<int> dist;
// 访问标志，在 Dijkstra求最短路， 和 Dfs搜索路径时需要用到
vector<bool> vis;
const int MODE = 1000000007;
public:
int countRestrictedPaths(int n, vector<vector<int> >& edges) {
dist = vector<int>(n+1, INT_MAX);
vis = vector<bool>(n+1, false);
// E 邻接表设为n+1 的大小
E = vector<vector<pair<int, int> > >(n+1);
for(vector<vector<int> >::iterator it = edges.begin(); it != edges.end(); it++) {
E[(*it)[0]].push_back(make_pair((*it)[1], (*it)[2]));
E[(*it)[1]].push_back(make_pair((*it)[0], (*it)[2]));
}
// 初始化一个优先队列, 优先队列默认是 大顶堆，可以用小顶堆替代。
priority_queue<DijkNode, vector<DijkNode>, greater<DijkNode> > queue;
// 进行Dijkstra 计算每个节点到 n的最短路径
dist[n] = 0;
queue.push(DijkNode(n, 0));
while (!queue.empty()) {
int u = queue.top().u; queue.pop();
if (vis[u]) continue; // 队列里有多个相同 u 的DijkNode，d最小的那个已经访问过了。
// 标记
vis[u] = true;
for(vector<pair<int, int> >::iterator it = E[u].begin(); it != E[u].end(); it++) {
pair<int, int> edge = *it;
if (vis[edge.first]) continue;
if (dist[edge.first] > dist[u] + edge.second) {
dist[edge.first] = dist[u] + edge.second;
queue.push(DijkNode(edge.first, dist[edge.first]));
}
}
}
// 搜索路径， 记忆化搜索
vector<ll> memo(n+1, -1);
fill(vis.begin(), vis.end(), false);
ll ans = memoSearch(1, n, memo);
return (int)ans;
}
ll memoSearch (int u, int n, vector<ll> &memo)
{
if (memo[u] != -1)
return memo[u];
if (u == n)
return 1;
vis[u] = true;
ll pathcount = 0;
for(vector<pair<int, int> >::iterator it = E[u].begin(); it != E[u].end(); it++) {
pair<int, int> edge = *it;
if (!vis[edge.first] && dist[u] > dist[edge.first]) {
// 因为只找有限路径，dfs时有条件：dist[u] > dist[edge.first]，
// 所以可以用记忆化搜索，查找时不会重复
pathcount = (pathcount + memoSearch(edge.first, n, memo)) % MODE;
}
}
vis[u] = false;
memo[u] = pathcount;
return pathcount;
}
};
229. 求众数 II 10月22日
摩尔投票：抵消阶段 + 计数阶段
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n = nums.size();
int major1 = 0;
int major2 = 0;
int vote1 = 0, vote2 = 0;
int limit = n / 3;
// 抵消阶段
for(auto num: nums) {
if (vote1 > 0 && num == major1) {
vote1++;
} else if (vote2 > 0 && num == major2){
vote2++;
} else if (vote1 == 0) {
major1 = num;
vote1++;
} else if (vote2 == 0) {
major2 = num;
vote2++;
} else {
vote1--;
vote2--;
}
}
// 计数阶段
vector<int> ans;
int count1 = 0, count2 = 0;
for (auto num : nums) {
if (num == major1)
count1++;
else if (num == major2)
count2++;
}
if (count1 > limit)
ans.push_back(major1);
if (count2 > limit)
ans.push_back(major2);
return ans;
}
};
496. 下一个更大元素 I 10月26日
单调栈
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
map<int,int> dict;
int n2 = nums2.size();
int n1 = nums1.size();
stack<int> stc;
vector<int> ans(n1);
for(int num : nums2) {
while(!stc.empty() && stc.top() < num) {
dict[stc.top()] = num;
stc.pop();
}
stc.push(num);
}
while(!stc.empty()) {
dict[stc.top()] = -1;stc.pop();
}
for(int i=0; i<n1; i++) {
ans[i] = dict[nums1[i]];
}
return ans;
}
};
503. 下一个更大元素 II 10月26日
数组里有重复数字了，所以入栈内容的应该是下标位置。
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
stack<int> stc;
vector<int> ans(n, -1);
for(int i=0; i<2*n-1; i++) {
while (!stc.empty() && nums[stc.top()] < nums[i%n]) {
ans[stc.top()] = nums[i%n];
stc.pop();
}
stc.push(i%n);
}
return ans;
}
};
836. 矩形重叠 10月26日
向X和Y轴投影，两个矩形重叠的充分必要条件就是，两个方向上的投影都重叠。
// 左下角
#define x1 0
#define y1 1
// 右上角
#define x2 2
#define y2 3
class Solution {
public:
bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
// 向2个方向投影 都有重叠才是重合
bool x_overlap = !(rec1[x2] <= rec2[x1] || rec1[x1] >= rec2[x2] );
bool y_overlap = !(rec1[y2] <= rec2[y1] || rec1[y1] >= rec2[y2] );
return x_overlap && y_overlap;
}
};
223. 矩形面积 10月26日
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
using namespace std;
class Solution {
public:
int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
int s1 = (ax2-ax1) * (ay2-ay1);
int s2 = (bx2-bx1) * (by2-by1);
int x1 = max(ax1, bx1);
int x2 = min(ax2, bx2);
int y1 = max(ay1, by1);
int y2 = min(ay2, by2);
if (x2 <= x1) return s1+s2;
if (y2 <= y1) return s1+s2;
return s1+s2-abs(x2-x1) * abs(y2-y1);
}
};
869. 重新排序得到 2 的幂 10月28日
预处理法，体检记录每个2次幂数字，0～9这10个数字各出现多少次。
class Solution {
Set<String> powerOf2Set;
private void init() {
powerOf2Set = new HashSet<String>();
for(int i=1; i < 1e9; i = i<<1) {
String res = countNumber(i);
powerOf2Set.add(res);
}
}
String countNumber(int n) {
char[] counter = new char[10];
while (n >0 ) {
++counter[n % 10];
n /= 10;
}
return new String(counter);
}
public boolean reorderedPowerOf2(int n) {
init();
return powerOf2Set.contains(countNumber(n));
}
}
307 区域和检索 4月5日
前缀和的方式会超时。 用线段树的来做。下面的方法用数组表示一个线段树。
class NumArray {
private:
vector<int> segmentTree;
vector<int> nums;
int sz;
// SegNode* buildTree(vector<int>& nums, int l, int r)
// {
// if(l == r){
// SegNode leaf;
// leaf.start = leaf.end = l;
// leaf.value = nums[l];
// return &leaf; //warning: address of stack memory associated with local variable 's' returned [-Wreturn-stack-address]
// }
// SegNode node;
// node.start = l; node.end = r;
// return &node;
// }
void buildTree(vector<int> & nums, int nodeId, int l, int r){
if (l == r){
segmentTree[nodeId] = nums[l];
return;
}
int mid = l + (r-l)/2;
buildTree(nums, nodeId*2+1, l, mid);
buildTree(nums, nodeId*2+2, mid+1, r);
segmentTree[nodeId] = segmentTree[nodeId*2+1] + segmentTree[nodeId*2+2];
}
int searchRange(int target_l, int target_r, int nodeId, int cur_l, int cur_r){
// no overlap
if(cur_l>target_r || cur_r < target_l)
return 0;
// total overlap
if(cur_l >= target_l && cur_r <= target_r)
return segmentTree[nodeId];
// partial overlap
int mid = cur_l + (cur_r-cur_l)/2;
return searchRange(target_l, target_r, nodeId*2+1, cur_l, mid) + searchRange(target_l, target_r, nodeId*2+2, mid+1, cur_r);
}
void updateRange(int targetIndex, int target_val, int nodeId, int cur_l, int cur_r){
if (targetIndex < cur_l || targetIndex > cur_r) //这个范围就不用改动了
return;
segmentTree[nodeId] = segmentTree[nodeId] - this->nums[targetIndex] + target_val;
if(cur_l < cur_r){
int mid = cur_l + (cur_r - cur_l) / 2;
updateRange(targetIndex, target_val, nodeId*2+1, cur_l, mid);
updateRange(targetIndex, target_val, nodeId*2+2, mid+1, cur_r);
}
}
public:
NumArray(vector<int>& nums) {
sz = nums.size();
segmentTree = vector<int>(sz*4, 0);
this->nums = nums;
buildTree(nums, 0, 0, sz-1);
}
void update(int index, int val) {
updateRange(index, val, 0, 0, sz-1);
this->nums[index] = val;
}
int sumRange(int left, int right) {
return searchRange(left, right, 0, 0, sz-1);
}
};
384 打乱数组 4月7日
#include <vector>
#include <cstdio>
using namespace std;
class Solution {
public:
Solution(vector<int>& nums) {
sz = nums.size();
this->nums = nums;
this->original.resize(sz);
copy(nums.begin(), nums.end(), original.begin());
}
vector<int> reset() {
copy(original.begin(), original.end(), nums.begin());
return original;
}
vector<int> shuffle() {
int last_index = sz-1;
for(;last_index>0; last_index--){
int target_index = rand() % (last_index+1);
int tmp = nums[target_index];
nums[target_index] = nums[last_index];
nums[last_index] = tmp;
}
return nums;
}
private:
int sz;
vector<int> nums;
vector<int> original;
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* vector<int> param_1 = obj->reset();
* vector<int> param_2 = obj->shuffle();
*/
796. 旋转字符串 4月7日
链接 整体旋转不改变字母顺序。
class Solution {
public:
bool rotateString(string s, string goal) {
return s.size() == goal.size() && (s + s).find(goal) != string::npos;
}
};
870. 优势洗牌 4月7日
贪心:先从小到大排序，nums2的第一个数字，对应 用nums1中第一个能大于它的数字，以此类推。
struct Node{
int v, originIndex;
Node(int v, int originIndex):v(v), originIndex(originIndex){}
bool operator < (const Node& b) const
{
return v < b.v;
}
};
// 贪心
class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int sz = nums2.size();
vector<int> ans(nums2.size());
sort(nums1.begin(), nums1.end());
stack<int> stc;
vector<Node> sorted2;
for(int i = 0; i<nums2.size(); i++){
sorted2.push_back(Node(nums2[i], i));
}
sort(sorted2.begin(), sorted2.end());
int r=0;
for(Node node : sorted2){
while(r<sz && nums1[r] <= node.v){
stc.push(nums1[r]);
r++;
}
if(r<sz){
ans[node.originIndex] = nums1[r];
r++;
}else{
ans[node.originIndex] = stc.top();
stc.pop();
}
}
return ans;
}
};
703. 数据流中的第 K 大元素 4月8日
用一个最小堆，不停pop()直到堆只剩k个元素，此时堆顶元素top()就是数据流中的第K大元素。
class KthLargest {
private:
priority_queue<int, vector<int>, greater<int> > min_heap;
int k;
public:
KthLargest(int k, vector<int>& nums) {
this->k = k;
for(int num: nums){
add(num);
}
}
int add(int val) {
min_heap.push(val);
while(min_heap.size() > k){
min_heap.pop();
}
return min_heap.top();
}
};
780. 到达终点 4月9日
需要数学数字分析，从终点走到起点。
最小堆，c++可以用lambda语法结合 priority_queue构造最小堆。
class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
while(tx > sx && ty > sy && tx != ty){
if (tx > ty){
tx = tx%ty;
}else if (tx < ty){
ty = ty%tx;
}
}
if (tx==sx && ty==sy) return true;
if (tx == sx && ty > sy) return (ty-sy) % sx == 0;
if (ty == sy && tx > sx) return (tx-sx) % sy == 0;
return false;
}
};
347. 前 K 个高频元素 4月9日
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
// O(1) time
if (k == nums.size()) {
return nums;
}
// 1. build hash map : element and how often it appears
// O(N) time
map<int, int> count_map;
for (int n : nums) {
count_map[n] += 1;
}
// initialise a heap with least frequent elements at the top
auto comp = [&count_map](int n1, int n2) { return count_map[n1] > count_map[n2]; };
priority_queue<int, vector<int>, decltype(comp)> heap(comp);
// 2. keep k top fequent elements in the heap
// O(N log k) < O(N log N) time
for (pair<int, int> p : count_map) {
heap.push(p.first);
if (heap.size() > k) heap.pop();
}
// 3. build an output array
// O(k log k) time
vector<int> top(k);
for (int i = k - 1; i >= 0; i--) {
top[i] = heap.top();
heap.pop();
}
return top;
}
};
380. O(1) 时间插入、删除和获取随机元素 4月13日
题目链接
普通数组+哈希表，哈希表以val为键，以数组索引为值。
#include <vector>
#include <map>
#include <cstdio>
#include <cstring>
using namespace std;
class RandomizedSet {
private:
int sz;
map<int,int> value_idx;
int arr[200002];
public:
RandomizedSet() {
sz = 0;
}
bool insert(int val) {
if (value_idx.find(val) == value_idx.end()){
arr[sz]=val;
value_idx[val] = sz;
sz++;
return true;
}
return false;
}
bool remove(int val) {
if (value_idx.find(val) == value_idx.end()){
return false;
}
int idx = value_idx[val];
arr[idx] = arr[sz-1];
if (idx!=sz) {
value_idx[arr[sz-1]]=idx;
}
value_idx.erase(val);
sz--;
return true;
}
int getRandom() {
int targetIdx = rand() % sz;
return arr[targetIdx];
}
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/
907. 子数组的最小值之和
class Solution {
private:
int MOD = 1e9 + 7;
public:
int sumSubarrayMins(vector<int>& arr) {
int sz = arr.size();
vector<int> left(sz, 0);
vector<int> right(sz, 0); // 最右边，最小
stack<int> rightStack; // 找第一个比自己小的
stack<int> leftStack;
for(int i = 0; i < sz; i++) {
while(!leftStack.empty() && arr[leftStack.top()] >= arr[i] )
leftStack.pop();
if (leftStack.empty()) {
left[i] = 0;
} else {
left[i] = leftStack.top()+1;
}
leftStack.push(i);
}
for(int i = sz-1; i >= 0; i--) {
while(!rightStack.empty() && arr[rightStack.top()] > arr[i] )
rightStack.pop();
if (rightStack.empty()) {
right[i] = sz-1;
} else {
right[i] = rightStack.top()-1;
}
rightStack.push(i);
}
int ans = 0;
for(int i=0; i<sz; i++) {
ans = (ans + (long)(i-left[i]+1)*(right[i]-i+1)*arr[i])%MOD;
}
return ans;
}
};
class Solution {
private static final int MOD = 1000000007;
// 重写根据下标取值方法，-1和n返回MIN_VALUE
private int getElement(int[] arr, int n, int i) {
if (i == -1 || i == n) {
return Integer.MIN_VALUE;
}
return arr[i];
}
public int sumSubarrayMins(int[] arr) {
// 处理边界情况
if (arr == null || arr.length == 0) {
return 0;
}
int n = arr.length;
long ans = 0;
Deque<Integer> stack = new LinkedList<>();
// 将下标-1和n作为两个哨兵元素，它们对应的元素为MIN_VALUE
// -1作为最左边界，n作为最右边界
for (int i = -1; i <= n; i++) {
// 向左寻找第一个小于等于A[i]的元素
while (!stack.isEmpty() && getElement(arr, n, stack.peek()) > getElement(arr, n, i)) {
// A[cur]就是之前思路中的A[i]，注意区分和上面代码的区别
// 对于每个出栈元素来说，i就是它们的右边界，而栈顶元素就是左边界
int cur = stack.pop();
// 计算贡献值
ans = (ans + (long)(cur - stack.peek()) * (i - cur) * arr[cur]) % MOD;
}
stack.push(i);
}
return (int)ans;
}
}
【Hard】题
273. 整数转换英文表示
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
class Solution {
private:
vector<string> singles = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"}; // < 10
vector<string> teens = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"}; // < 20
vector<string> tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"}; // >= 20, < 100
vector<string> thousands = {"", "Thousand", "Million", "Billion"};
public:
string numberToWords(int num) {
//num <=
if (num == 0)
return "Zero";
string strbuff;
for(int i=3, unit=1000000000; i>=0; i--, unit /= 1000) {
int curNum = num / unit;
if (curNum != 0){
num = num % unit;
strbuff = strbuff + help(curNum) + " " + thousands[i]+ " ";
}
}
while(strbuff.back() == ' ')
strbuff.pop_back();
return strbuff;
}
string help(int num){
string res;
if(num<10) {
return singles[num];
} else if (num<20){
return teens[num-10];
} else if (num<100){
res = tens[num/10];
res = res + " " + help(num%10);
} else {
res = singles[num/100]+ " Hundred " + help(num%100);
}
while(res.back() == ' ')
res.pop_back();
return res;
}
};
int main(int argc, char* argv[]){
char * s = argv[1];
int num = atoi(s);
Solution sol;
cout<<sol.numberToWords(num);
}
295.数据流的中位数
两个堆，一个小顶堆存放 数据流中最大的一半数字，大顶堆存放最小的一半数字
class MedianFinder {
private:
priority_queue<int> half_bottom; // 大顶堆
priority_queue<int, vector<int>, greater<int>> half_up; // 小顶堆
int sz;
public:
MedianFinder() {
this->sz = 0;
}
void addNum(int num) {
// num
if (sz==0){
half_bottom.push(num);
} else if(sz==1) {
half_bottom.push(num);
num = half_bottom.top();half_bottom.pop();
half_up.push(num);
} else {
if(sz & 1) {
// 已经有基数个了，应该多放一个进 half_top
if (num < half_bottom.top()) {
half_bottom.push(num);
num = half_bottom.top();half_bottom.pop();
}
half_up.push(num);
} else {
if (num > half_up.top()){
half_up.push(num);
num = half_up.top(); half_up.pop();
}
half_bottom.push(num);
}
}
sz += 1;
}
double findMedian() {
if (sz & 1) {
return (double) half_bottom.top();
}
return (double)(half_bottom.top() + half_up.top()) / 2.0;
}
};
60. 排列序列
数学 + 缩小问题规模 从左到右依次确定 a1,a2,a3,a4…an
#include <vector>
#include <cstdlib>
#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> factorial(n);
factorial[0] = 1;
// 提前打表
for(int i=1; i<n; i++){
factorial[i] = factorial[i-1]*i;
}
vector<int> valid(n+1, 1);
k = k-1; // 改为从0开始编号
string ans = "";
for(int i=1; i<=n; i++){
int order = k/factorial[n-i] + 1;
for(int j=1; j<=n; j++){
// if(valid[i]==1){
// order -= 1;
// }
order -= valid[j];
if (order == 0){
ans = ans + char(j+'0');
valid[j]=0;
k = k%factorial[n-i];
break;
}
}
}
return ans;
}
};
int main(int c, char * argv[]){
if (c!=3){
return 0;
}
int n = atoi(argv[1]);
int k = atoi(argv[2]);
Solution sol;
cout<<sol.getPermutation(n, k);
}
330. 按要求补齐数组
数学 + 贪心 对于正整数 x，如果区间$[1,x-1]$ 内的所有数字都已经被覆盖，且 x 在数组中，则区间 $[1,2x−1]$ 内的所有数字也都被覆盖。
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int minPatches(vector<int>& nums, int n) {
int index=0, sz=nums.size();
long x=1;
int cnt=0;
while(x<=n){
if(index < sz && nums[index]<=x){
x+=nums[index];
index++;
} else {
x*=2;
cnt++;
}
}
return cnt;
}
};
135. 发糖果
class Solution {
public:
int candy(vector<int>& ratings) {
int sz = ratings.size();
vector<int> left(sz, 1);
for(int i=1; i < sz; i++)
{
if (ratings[i] > ratings[i-1])
left[i] = left[i-1]+1;
}
int right = 0;
int ret = 0;
for(int i=sz-1; i>=0; i--){
if (i<sz-1 && ratings[i] > ratings[i+1]){
right++;
} else {
right = 1;
}
ret += max(left[i], right);
}
return ret;
}
};
-
如果当前同学比上一个同学评分高，说明我们就在最近的递增序列中，直接分配给该同学 $pre + 1$ 个糖果即可。
-
否则我们就在一个递减序列中，我们直接分配给当前同学一个糖果，并把该同学所在的递减序列中所有的同学都再多分配一个糖果，以保证糖果数量还是满足条件。
-
我们无需显式地额外分配糖果，只需要记录当前的递减序列长度，即可知道需要额外分配的糖果数量。
-
同时注意当当前的递减序列长度和上一个递增序列等长时，需要把最近的递增序列的最后一个同学也并进递减序列中。
-
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
int ret = 1;
int inc = 1, dec = 0, pre = 1;
for (int i = 1; i < n; i++) {
if(ratings[i]>=ratings[i-1]){
pre = ratings[i]==ratings[i-1] ? 1 : pre+1;
ret += pre;
inc = pre;
dec = 0;
}else{
dec ++;
if(dec == inc){
dec++;
}
ret += dec;
pre = 1;
}
}
return ret;
}
};
214. 最短回文串
题目链接
KMP，对整个字符串s构建next数组，然后从后往前地在s中匹配.
class Solution {
public:
string shortestPalindrome(string s) {
int maxPrefixPalidromLength = 1;
int sz = s.size();
if(sz==0)
return "";
vector<int> next = getNext(s);
// for(int kmp: next){
// cout<<kmp<<" ";
// }
int p = sz - 1;
int needle = 0;
while(p >= 0 && needle < p){
if (needle==-1 || s[needle]==s[p]){
p--;needle++;
} else {
needle = next[needle];
}
}
// 求最长回文前缀长度
if (p==needle){
// 碰在一起
maxPrefixPalidromLength = 2*needle+1;
}else{
maxPrefixPalidromLength = 2*needle;
}
if(maxPrefixPalidromLength >= sz)
return s;
string prefix = s.substr(maxPrefixPalidromLength);
reverse(prefix.begin(), prefix.end());
return prefix+s;
}
vector<int> getNext(string needle) {
int needleSz = needle.size();
vector<int> next(needleSz);
next[0] = -1;
int j = 0;
int k = -1;
while(j < needleSz - 1){
if(k==-1 || needle[k]==needle[j])
next[++j]=++k;
else
k = next[k];
}
return next;
}
};
164. 最大间距
分桶，选择合适的桶大小，使得最大间隔的情况不会出现在任何桶内的元素里面。然后依次比对相邻桶的最大值和最小值
class Solution {
public:
int maximumGap(vector<int>& nums) {
int sz = nums.size();
if (sz < 2)
return 0;
int minValue = *min_element(nums.begin(), nums.end());
int maxValue = *max_element(nums.begin(), nums.end());
int d = max(1, (maxValue - minValue) / (sz - 1)); // 这是向下取整数， 每个桶的大小
int bucketSz = (maxValue - minValue) / d + 1;
vector<pair<int, int>> bucket(bucketSz, {-1,-1});
for(int num: nums){
int idx = (num-minValue) / d;
if(bucket[idx].first == -1){
bucket[idx].first = bucket[idx].second = num;
}else {
bucket[idx].first = min(num, bucket[idx].first);
bucket[idx].second = max(num, bucket[idx].second);
}
}
int ret = 0;
int prev = -1;
for(int i = 0; i < bucketSz; i++){
if (bucket[i].first==-1) continue;
if(prev!=-1){
ret = max(ret, bucket[i].first - bucket[prev].second);
}
prev = i;
}
return ret;
}
};
68. 左右文本左对齐
class Solution {
private:
string blank(int n) {
return string(n, ' ');
}
// join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串
string join(vector<string>& words, int left, int right, string sep) {
string s = words[left];
for (int i = left + 1; i < right; ++i) {
s += sep + words[i];
}
return s;
}
string join(vector<string>& line, int maxWidth) {
int numWords = line.size();
int numChar = 0;
for(string word: line){
numChar += word.length();
}
if (numWords == 1){
return line[0] + blank(maxWidth-numChar);
}
int numSpace = maxWidth - numChar;
int avgSpace = numSpace / (numWords-1);
string baseSep = blank(avgSpace);
int extraSpace = numSpace % (numWords - 1);
if (extraSpace == 0){
return join(line, 0, numWords, baseSep);
} else {
return join(line, 0, extraSpace+1, blank(avgSpace + 1)) + baseSep + join(line, extraSpace + 1, numWords, baseSep);
}
}
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
int sz = words.size();
int p = 0;
int remain = maxWidth;
vector<string> res;
vector<string> line;
int need;
bool first_in_line = true;
string lastline = "";
while(p < sz){
string word = words[p];
if (first_in_line){
need = word.length();
first_in_line = false;
}else {
need = word.length() + 1;
}
if (need <= remain){
line.push_back(word);
remain-=need;
p++;
}else{
// 最后一行 肯定不会进入这里
res.push_back(join(line, maxWidth));
first_in_line = true;
line.clear();
remain = maxWidth;
}
}
lastline = join(line, 0, line.size(), " ");
lastline = lastline + string(maxWidth - lastline.length(), ' ');
res.push_back(lastline);
return res;
}
};
🌟282. 给表达式添加运算符
只能用DFS，在处理 乘法优先级的时候，需要用一个参数mul表示当前最后一个连乘的结果
#include <vector>
#include <string>
#include <cstdio>
#include <iostream>
using namespace std;
class Solution {
private:
void backtrace(string &num, string&expr, vector<string>& ans, int pos, long res, long mul, int &target) {
if (pos == num.size()){
if (res == target){
ans.push_back(expr);
}
return;
}
int signIndex = expr.size();
if (pos!=0){
expr.push_back(0); // 站位
}
long val = 0;
for(int i = pos; i < num.size() && (i==pos || num[pos]!='0'); i++) {
val = val * 10 + num[i] - '0';
expr.push_back(num[i]);
if( pos == 0 ){
backtrace(num, expr, ans, i+1, res + val, val, target);
} else {
expr[signIndex] = '+'; backtrace(num, expr, ans, i+1, res + val, val, target);
expr[signIndex] = '-'; backtrace(num, expr, ans, i+1, res - val, -val, target);
expr[signIndex] = '*'; backtrace(num, expr, ans, i+1, res - mul + mul*val, mul*val, target);
}
}
expr.resize(signIndex);
}
public:
vector<string> addOperators(string num, int target) {
int n = num.length();
vector<string> ans;
if (num.size()==0) return ans;
string expr;
backtrace(num, expr, ans, 0, 0, 0, target);
return ans;
}
};
int main(int c, char *argv[]){
if (c != 3){
return 0;
}
string num = string(argv[1]);
cout<< num << endl;
int target = atoi(argv[2]);
cout<< target << endl;
Solution sol;
vector<string> ans = sol.addOperators(num, target);
for(string s: ans){
cout<< s << endl;
}
return 0;
}
301. 删除无效的括号
删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。 说明: 输入可能包含了除 ( 和 ) 以外的字符。
深度优先搜索+回溯
如果整个字符串是有效的，则从左到右遍历的时，n(左括号) 一定 >= n(右括号)。删除最少括号的要求就可以根据这条的规律来做 1 确定要删除多少左括号和多少右括号 2 dfs搜索，避免重复答案
class Solution {
private:
void dfs_search(const string& s, int& s_sz, vector<string> &ans, string& expr, int pos, int currentLeftCount, int currentRightCount, int leftNeedRemove, int rightNeedRemove)
{
if (pos==s_sz){
if (leftNeedRemove == 0 && rightNeedRemove == 0){
ans.push_back(expr);
}
return;
}
char c = s[pos];
// 要当前字符
expr.push_back(c);
if (c!='(' && c!=')'){
// 普通字母
dfs_search(s, s_sz, ans, expr, pos+1, currentLeftCount, currentRightCount, leftNeedRemove, rightNeedRemove);
}else if(c=='('){
dfs_search(s, s_sz, ans, expr, pos+1, currentLeftCount+1, currentRightCount, leftNeedRemove, rightNeedRemove);
}else if(c==')' && currentLeftCount > currentRightCount){
dfs_search(s, s_sz, ans, expr, pos+1, currentLeftCount, currentRightCount+1, leftNeedRemove, rightNeedRemove);
}
expr.pop_back();
// 不要当前字符
if(expr.length()==0 || expr.back() != c){ // 避免重复答案， 不要当前字符时，如果expr中的上一个字符和当前字符相等，就不用再考虑去掉当前字符的情况
if (c == '(' && leftNeedRemove > 0){
dfs_search(s, s_sz, ans, expr, pos+1, currentLeftCount, currentRightCount, leftNeedRemove-1, rightNeedRemove);
}
if (c == ')' && rightNeedRemove > 0){
dfs_search(s, s_sz, ans, expr, pos+1, currentLeftCount, currentRightCount, leftNeedRemove, rightNeedRemove-1);
}
}
}
public:
vector<string> removeInvalidParentheses(string s) {
int leftNeedRemove = 0;
int rightNeedRemove = 0;
string expr = "";
vector<string> ans;
int sz = s.length();
for(int i = 0; i < sz; i++){
if(s[i]=='('){
leftNeedRemove++;
}else if(s[i]==')'){
if (leftNeedRemove > 0){
leftNeedRemove--;
} else {
rightNeedRemove++;
}
}
}
dfs_search(s, sz, ans, expr, 0, 0, 0, leftNeedRemove, rightNeedRemove);
return ans;
}
};
int main(int argc, char *argv[]){
Solution sol;
string s = string(argv[1]);
vector<string> ans = sol.removeInvalidParentheses(s);
for(string item : ans){
cout<<"\""<<item<<"\""<<endl;
}
}
407. 接雨水 II
和接雨水1的做法完全不一样，利用最短木板，最小优先队列从外朝内搜索。
#include <iostream>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
// https://leetcode.cn/problems/trapping-rain-water-ii/
// 接雨水II
using pii = pair<int, int>;
class Solution {
public:
int trapRainWater(vector<vector<int> >& heightMap) {
int m = heightMap.size();
int n = heightMap[0].size();
priority_queue<pii, vector<pii>, greater<pii> > que;
vector<vector<bool>> vis(m, vector<bool>(n, false));
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, +1, -1};
int res = 0;
for(int j = 0; j < n; j++) {
que.push({heightMap[0][j], j});
vis[0][j] = true;
}
for(int i = 1; i < m; i++) {
que.push( {heightMap[i][n-1], i*n+n-1} );
vis[i][n-1] = true;
}
for(int j = n-2; j>=0; j--){
que.push( {heightMap[m-1][j], (m-1)*n + j});
vis[m-1][j] = true;
}
for(int i = m-2; i>0; i--){
que.push( {heightMap[i][0], i*n});
vis[i][0] = true;
}
while(!que.empty()){
// 最短的这一木板
pii p = que.top(); que.pop();
int waterface = p.first;
for(int k=0; k<4; k++){
int nx = p.second / n + dx[k];
int ny = p.second % n + dy[k];
if( nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny]) {
if (heightMap[nx][ny] < waterface){
res += (waterface - heightMap[nx][ny]);
}
vis[nx][ny] = true;
que.push({ max(heightMap[nx][ny], waterface), nx*n+ny});
}
}
}
return res;
}
};
321. 拼接最大数
链接
单调栈，以及一个比较重要的compare方法。
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
class Solution {
private:
vector<int> getMaxSubsequence(vector<int>& nums, int n){
vector<int> subseq;
int sz = nums.size();
for(int i=0; i<sz; i++){
while(!subseq.empty() && subseq.back() < nums[i] && subseq.size()-1+sz-i>=n){
subseq.pop_back();
}
subseq.push_back(nums[i]);
}
return subseq;
}
int compare(vector<int>& subsequence1, int index1, vector<int>& subsequence2, int index2) {
// 这个比较函数比较 重要
int x = subsequence1.size(), y = subsequence2.size();
while (index1 < x && index2 < y) {
int difference = subsequence1[index1] - subsequence2[index2];
if (difference != 0) {
return difference;
}
index1++;
index2++;
}
return (x - index1) - (y - index2);
}
vector<int> mergeSeq(vector<int>& seq1, vector<int>& seq2, int k){
int m = seq1.size(), n = seq2.size();
if(m==0){
return seq2;
}
if (n==0){
return seq1;
}
vector<int> merge(k, 0);
int i=0, j=0;
for(int z=0; z<k; z++){
if(compare(seq1, i, seq2, j) > 0){
merge[z] = seq1[i++];
}else{
merge[z] = seq2[j++];
}
}
return merge;
}
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
// k = 5;
int sz1 = nums1.size();
int sz2 = nums2.size();
int start = max(0, k-sz2);
vector<int> maxRes;
int end = min(sz1, k);
for(int i=start; i<=end;i++){
vector<int> subseq1 = getMaxSubsequence(nums1, i);
vector<int> subseq2 = getMaxSubsequence(nums2, k-i);
vector<int> merge = mergeSeq(subseq1, subseq2, k);
if(compare(merge,0, maxRes,0) > 0){
maxRes = merge;
}
}
return maxRes;
}
};