力扣198.打家劫舍
题目：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
示例：输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：动态规划。dp[i] 表示从nums[0]到nums[i]可以打劫的最大的金额。条件是不能打劫相邻2个
如果打劫i ，那么dp[i] = dp[i-2] + nums[i]。如果不打劫i ，那么dp[i] = dp[i-1]。
则可得出公式：dp[n]=max(dp[n-2]+nums[n]，dp[n-1])
代码：
class Solution {
public:
int rob(vector<int>& nums) {
int i,n=nums.size();
int dp[n+1];
if(n==0)
return 0;
dp[0]=0;
dp[1]=nums[0];
for(i=2;i<=n;i++)
{
dp[i]=max(dp[i-2]+nums[i-1],dp[i-1]);
}
return dp[n];
}
};
力扣周赛182
5368. 找出数组中的幸运数
题目：在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。给你一个整数数组 arr，请你从中找出并返回一个幸运数。 如果数组中存在多个幸运数，只需返回 最大 的那个。 如果数组中不含幸运数，则返回 -1 。来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-lucky-integer-in-an-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：设最大幸运数为max，初始值max=-1，然后利用双重循环进行计数，i循环表示需要计数的数值，j循环记录arr[i]出现的次数count，如果count==arr[i]，并且count>max，则令max=count，通过i，j双重循环找到最大的幸运数max并返回。如果数组中没有幸运数，则max为初始值-1，满足题目要求。
代码：
class Solution {
public:
int findLucky(vector<int>& arr) {
int i,j,n,count,max=-1;
n=arr.size();
for(i=0;i<n;i++)
{
count=0;
for(j=0;j<n;j++)
{
if(arr[i]==arr[j])
count++;
}
if(arr[i]==count && count>max)
max=count;
}
return max;
}
};
5369. 统计作战单位数
题目： n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。每 3 个士兵可以组成一个作战单位，分组规则如下：
从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]。作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中 0 <= i < j < k < n。请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-number-of-teams
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：利用三重循环，先定rating[i]，然后在i+1~rating.size()之间寻找是否有rating[j]，如果有rating[j]，再在j+1~rating.size()之间寻找是否有rating[k]，如果有，那么数量num++，遍历全部数后得出的数量num就是结果。
代码：
class Solution {
public:
int numTeams(vector<int>& rating) {
int i,j,k,n,num=0;
n=rating.size();
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(rating[j]>rating[i])
{
for(k=j+1;k<n;k++)
{
if(rating[k]>rating[j])
num++;
}
}
if(rating[j]<rating[i])
{
for(k=j+1;k<n;k++)
{
if(rating[k]<rating[j])
num++;
}
}
}
}
return num;
}
};
力扣926
题目：如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是单调递增的。
我们给出一个由字符 '0' 和 '1' 组成的字符串 S，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。返回使 S 单调递增的最小翻转次数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flip-string-to-monotone-increasing
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
这一题刚开始写并没有好的思路，也并不了解题的各种情况，就通过比较0和1的个数来确定最少翻转次数，结果却不对。后来看群里讨论，经过老师的提点，就知道解题的关键就是要找到01的临界点，不过，找这个临界点并不容易，自己琢磨了大半天才琢磨出来。要找到临界点的条件就是该点的左边全0，右边全1，也就是说临界点左边1的个数必定要比0少，这就是找到临界点的关键。
于是我就从左到右去遍历数列，从第一个1开始计数，每当1的个数小于等于0的个数并且当前位置为1，就把这个点当作临界点处理，即左边的1都应当翻转，而翻转后又是一轮新的比较，即翻转次数num=num+count1-1，1的个数count1=1，0的个数count0=0。如此遍历完数列，此时如果1的个数大于0的个数，那么临界点就是上一次进行“翻转”处理的位置，则此时的记录应当翻转0，即num=num+count0。否则，将翻转1，即全0数列，num=num+count1.
代码：class Solution {
public:
int minFlipsMonoIncr(string S) {
int i=0,count0=0,count1=0,num=0;
if(S.size()<=1) return 0;
while(S[i]=='0')
i++;
for(i;i<S.size();i++)
{
if(S[i]=='0')
count0++;
else
count1++;
if(count1<=count0 && S[i]=='1')
{
num+=count1-1;
count1=1;
count0=0;
}
}
if(count0 < count1)
num+=count0;
else
num+=count1;
return num;
}
};
力扣每日一题：面试题62.圆圈中最后剩下的数字
题目：0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：看到题就发现了这是一个循环链表，然后就根据循环链表写了模拟删除的代码，提交后却发现超时，这就很难受了。然后就看了讨论区，发现了倒推法比较容易。
倒推法：从最后剩下的那个数反推，推回到n个数时的位置。
人数为1时：0；
人数为2时：（0+m）%2
人数为3时：（（0+m）%2+m）%3
...
如此推到n就可以得出答案了。
即递推公式：f=（f+m）% i；
代码：
class Solution {
public:
int lastRemaining(int n, int m) {
int i,f=0;
for(i=2;i<=n;i++)
{
f=(f+m)%i;
}
return f;
}
};
力扣每日一题：912.排序数组
题目：给你一个整数数组 nums，请你将该数组升序排列。
解题思路：这题一看就想到了快速排序。
代码：
class Solution {
int partition(vector<int>& arr, int low, int high) {
int i = low, j = high;
int tmp = arr[low];
while (i < j) {
while (i < j && arr[j] > tmp)
j--;
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] < tmp)
i++;
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = tmp;
return i;
}
void quicksort(vector<int>& arr, int low, int high) {
if(low > high)
return;
int j = partition(arr, low, high);
quicksort(arr, low, j - 1);
quicksort(arr, j + 1, high);
}
public:
vector<int> sortArray(vector<int>& nums) {
int n=nums.size();
quicksort(nums,0,n-1);
return nums;
}
};
力扣每日一题：1111.有效括号的嵌套深度
题目：有效括号字符串 定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。详情参见题末「有效括号字符串」部分。
嵌套深度 depth 定义：即有效括号字符串嵌套的层数，depth(A) 表示有效括号字符串 A 的嵌套深度。详情参见题末「嵌套深度」部分。
有效括号字符串类型与对应的嵌套深度计算方法如下图所示：给你一个「有效括号字符串」 seq，请你将其分成两个不相交的有效括号字符串，A 和 B，并使这两个字符串的深度最小。
不相交：每个 seq[i] 只能分给 A 和 B 二者中的一个，不能既属于 A 也属于 B 。
A 或 B 中的元素在原字符串中可以不连续。
A.length + B.length = seq.length
深度最小：max(depth(A), depth(B)) 的可能取值最小。
划分方案用一个长度为 seq.length 的答案数组 answer 表示，编码规则如下：
answer[i] = 0，seq[i] 分给 A 。
answer[i] = 1，seq[i] 分给 B 。
如果存在多个满足要求的答案，只需返回其中任意 一个 即可。
示例 1：
输入：seq = "(()())"
输出：[0,1,1,1,1,0]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：这道题就是道阅读理解题。。。题目很长，简而言之就是把一组组合的括号遍历全部按顺序分成A、B两组，并且这两组的括号嵌套层数都要最小。我的思路就是把第一个放在A组，然后i从1开始遍历，若seq[i]==seq[i-1],就把seq[i]分到和seq[i-1]不同的组，即当有连续相同的括号时就把它们分开，一个在A组，一个在B组。若是不同，则seq[i]和seq[i-1]刚好组成一组无嵌套的括号。
这个方法的重点就是如何区分开AB组，题目中要求分到A组是0，分到B组是1。如果seq[i]和seq[i-1]不同比较容易，让a[i]=a[i-1]即可。而不同的话，我便让a[i]=a[i-1]+1，而当a[i]==2时就把a[i]重新赋值为0，即a[i]=0，这样就解决了分到B组后回到A组的问题。
代码：
class Solution {
public:
vector<int> maxDepthAfterSplit(string seq) {
int i,n=seq.size();
vector<int> a(n,0);
a[0]=0;
for(i=1;i<n;i++)
{
if(seq[i]==seq[i-1])
{
a[i]=a[i-1]+1;
if(a[i]==2)
a[i]=0;
}
else
a[i]=a[i-1];
}
return a;
}
};
