day2
14-1 剪绳子 (重点)
思路1:动态规划
p94-98
class Solution {
public:
int cuttingRope(int n) {
if(n==3){
return 2;
}
else if(n==2){
return 1;
}
int product[n+1];
product[0]=0;
product[1]=1;
product[2]=2;
product[3]=3;
for(int i=4;i<=n;i++){
int max=-1;
for(int j=1;j<=i/2;j++){
if(max<product[j]*product[i-j]){
max=product[j]*product[i-j];
}
}
product[i]=max;
}
return product[n];
}
};
思路2:贪心算法
p94-98
class Solution {
public:
int cuttingRope(int n) {
if(n==3){
return 2;
}
else if(n==2){
return 1;
}
int res=1;
while(n>=5){
res*=3;
n-=3;
}
res*=n;
return res;
}
};
课本的代码
class Solution {
public:
int cuttingRope(int n) {
if(n==3){
return 2;
}
else if(n==2){
return 1;
}
int timesOf3=n/3;
if(n-timesOf3*3==1){
timesOf3--;
}
int timesOf2=(n-timesOf3*3)/2;
return (int)(pow(3,timesOf3)*(int)(pow(2,timesOf2)));
}
};
14-2 剪绳子 II
该题的变动在于2 <= n <= 1000
思路：
-
因为数据量大,所以不适合用动态规划(?为什么),要用贪婪算法。
- 在贪婪算法中为了防止位数溢出,要模1000000007，可以保证值永远在int的范围内,且res本身要设为long
- 在大数求余中可以使用循环求余和快速幂求余,时间复杂度依次为O(n)和O(logn) 下面代码是循环求余，快速幂求余没有研究
class Solution {
public:
int cuttingRope(int n) {
if(n==3){
return 2;
}
else if(n==2){
return 1;
}
long res=1;
while(n>=5){
res=(res*3)%1000000007;
n-=3;
}
res=(res*n)%1000000007;
return res;
}
};
15.二进制中1的个数
ps:这道题要求的输入是uint32_t n，可以看到是无符号int32位，给出的输入例子是00000000000000000000000000001011形式，但是如果cout<<num<<endl;会发现输出是11，所以你不要以为可以直接遍历字符串n，数1的个数。
思路1:
只要不是负数，就没事。
p100
class Solution {
public:
int hammingWeight(uint32_t n) {
int count=0;
while(n){
if(n&1){
count++;
}
n=n>>1;
}
return count;
}
};
思路2:
p101
常规解法，针对负数也有效
class Solution {
public:
int hammingWeight(uint32_t n) {
uint32_t flag=1;
int count=0;
while(flag){
if(n&flag){
count++;
}
flag=flag<<1;
}
return count;
}
};
思路3:
p102:整数中有几个1就只需循环几次
把一个整数减去1之后再和原来的整数做位的与运算，得到的结果相当于把整数的二进制表示中最右边的1变成0
很多二进制的问题都可以用这个思路解决。
class Solution {
public:
int hammingWeight(uint32_t n) {
int count=0;
while(n){
n=(n-1)&n;
count++;
}
return count;
}
};
思路4:
class Solution {
public:
int hammingWeight(uint32_t n) {
return ((bitset<32>)n).count();
}
};
16.数值的整数次方
思路1:暴力循环
超时 o(n)
class Solution {
public:
double myPow(double x, int n) {
if(n<0){
x=1.0/x;
n=-n;
}
else if(n==0){
return 1;
}
double ans=x;//不要习惯写成int
for(int i=1;i<n;i++){
ans*=x;
}
return ans;
}
};
思路2:快速幂
注意
- 如果指数是负数怎么办？求倒数么？那么又万一x是0呢？0是不能求倒数的。
-
注意n的取值范围，如果n取最小的负值，取反后便无法装入了。
递归写法：
可以用右移运算符代替除以2，用位与运算符代替%来判断一个数是奇还是偶。位运算的效率比乘除、求余都高。
class Solution {
public:
double myPow(double x, int n) {
long nn=n;
if(x==0){
return 0;
}
else if(n==0){
return 1;
}
else if(n<0){
x=1.0/x;
nn=-nn;
}
return binaryPow(x,nn);
}
double binaryPow(double x,long n){
if(n==1){
return x;
}
else if(n%2==0){
double ans=binaryPow(x,n/2);
return ans*ans;
}
else{
return binaryPow(x,n-1)*x;
}
}
};
迭代写法：
算法笔记p136
class Solution {
public:
double myPow(double x, int n) {
long nn=n;
if(x==0){
return 0;
}
else if(n==0){
return 1;
}
else if(n<0){
x=1.0/x;
nn=-nn;
}
double ans=1;
while(nn){//是n要右移，所以x是负数也没关系
if(nn&1){
ans*=x;
}
nn>>=1;
x*=x;
}
return ans;
}
};
17.打印从1到最大的n位数
这道题应该考大数问题的，所以思路1理论上行不通
思路1:暴力解法，找到最大的n位数，然后从1开始输出。
时间复杂度o(10^n)
class Solution {
public:
vector<int> printNumbers(int n) {
int max=0;
for(int i=0;i<n;i++){
max+=9*pow(10,i);
}
vector<int> ans;
for(int i=1;i<=max;i++){
ans.push_back(i);
}
return ans;
}
};
class Solution {
public:
vector<int> printNumbers(int n) {
int max=pow(10,n);//一举求出最大值
vector<int> ans;
for(int i=1;i<max;i++){
ans.push_back(i);
}
return ans;
}
};
思路2:大数 模拟加法
课本p114-116
代码
思路3:全排列
课本p117:由于模拟整数的加法不是简单的事，我们可以转换思路。题意中n位所有十进制数其实就是n个从0到9的全排列。我们把数字的每一位都从0到9排列一遍，就得到了所有的十进制数。只是在打印的时候，排在前面的0不打印出来，而且leetcode要求从1开始而不是从0开始。全排列使用递归实现，递归结束的条件是我们已经设置了数字的最后一位。
算法笔记p115也有全排列，但是与这题略有不同。
自己写的代码，使用的是int数组而不是string也不是char数组
class Solution {
public:
vector<int> printNumbers(int n) {
vector<int> p(n+1),ans;
generateP(1,n,p,ans);
return ans;
}
void generateP(int index,const int& n,vector<int> &p,vector<int> &ans){ //p引用?
if(index==n+1){
//理论来说应该输出当前产生的p数组，也就是一个大数,而不是转换成int加到ans里面。
int sum=0,ten=1;
for(int i=n;i>0;i--){
sum+=p[i]*ten;
ten*=10;
}
if(sum){
ans.push_back(sum);//去掉0
}
return;
}
for(int i=0;i<10;i++){
p[index]=i;
generateP(index+1,n,p,ans);
}
return;
}
};
下次实现课本上的两个方法的代码以及他人的方法的代码，加强理解。
https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/mian-shi-ti-17-da-yin-cong-1-dao-zui-da-de-n-wei-2/
https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/c-3chong-jie-fa-by-xdb/
18.删除链表的节点
leetcode对比原题有改动，太简单了，就是链表删除节点的常规操作。
节点的题目主要考虑边界情况
特殊情况：头节点为空，删除头节点，删除尾节点，只有一个节点
思路：遍历，然后删掉
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(head==NULL) return head;
if(head->val==val) return head->next; //当删除头节点时
ListNode* cur=head;
ListNode* pre;
while(cur){
if(cur->val==val){
pre->next=cur->next;
break;
}
pre=cur;
cur=cur->next;
}
return head;
}
};
别人写的递归代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(!head) return NULL;
if(head->val == val) return head->next;
head->next = deleteNode(head->next,val);
return head;
}
};
原题目:要求在o(1)时间内删除链表节点。
注意题目说的是给定一个节点指针，在o(1)时间内删除该节点。
思路：119-122f
19.正则表达式匹配(重点)
不会写
思路1:递归
p124-126
超时(是不是substr太慢了，或许应该使用迭代器?,或者用两个索引记录s和p的匹配位置?)
"aaaaaaaaaaaaab"
"aaaaaaaaaac"
class Solution {
public:
bool isMatch(string s, string p) {
return isMatchCore(s,p);
}
bool isMatchCore(string s,string p){
if(s.empty()&&p.empty()){
return true;
}
else if(!s.empty() && p.empty()){
return false;
}
if(p.size()>1 && p[1]=='*'){
if(s[0]==p[0]||(p[0]=='.'&& !s.empty())){
return isMatchCore(s.substr(1),p.substr(2)) || isMatchCore(s.substr(1),p) || isMatchCore(s,p.substr(2));
}
else{
return isMatchCore(s,p.substr(2));
}
}
if(s[0]==p[0] || (p[0]=='.'&&!s.empty())){
return isMatchCore(s.substr(1),p.substr(1));
}
return false;
}
};
使用索引之后通过了，但是4% 97%..
1668 ms 6.1 MB
class Solution {
public:
int n, m;
bool isMatch(string s, string p) {
n = s.size();
m = p.size();
return backtrack(s, p, 0, 0);
}
bool backtrack(string& str, string& pattern, int str_loc, int p_loc) {
if(str_loc == n && p_loc == m) {
return true;
}
// 如果串还有剩余，模式空了，那么必定返回 false
// 但反之不一定，因为模式后面可能是 a* 这样的不需要匹配字符
if(str_loc < n && p_loc == m) {
return false;
}
bool flag = false;
char pattern_ch = pattern[p_loc]; // 模式肯定还有剩余
// 有 * 的情况
if(p_loc < m-1 && pattern[p_loc+1]=='*') {
if(str[str_loc] == pattern_ch || (pattern_ch == '.'&&str_loc<n)){
return backtrack(str,pattern,str_loc+1,p_loc+2)||
backtrack(str,pattern,str_loc+1,p_loc)||
backtrack(str,pattern,str_loc,p_loc+2);
//return flag;
}
else{
return backtrack(str,pattern,str_loc,p_loc+2);
}
} else { // 没有 * 的情况，只需要看当前位置的字符是否相等
if(str_loc < n) {
// 如果这种情况下串没有剩余，模式有剩余，那就是错误的
char str_ch = str[str_loc];
char pattern_ch = pattern[p_loc];
if(str_ch == pattern_ch || pattern_ch == '.') {
flag = backtrack(str, pattern, str_loc+1, p_loc+1);
}
}
}
return flag;
}
};
为什么这个人的递归代码这么好?
40 ms 6 MB
class Solution {
public:
int n, m;
bool isMatch(string s, string p) {
n = s.size();
m = p.size();
return backtrack(s, p, 0, 0);
}
bool backtrack(string& str, string& pattern, int str_loc, int p_loc) {
if(str_loc == n && p_loc == m) {
return true;
}
// 如果串还有剩余，模式空了，那么必定返回 false
// 但反之不一定，因为模式后面可能是 a* 这样的不需要匹配字符
if(str_loc < n && p_loc == m) {
return false;
}
bool flag = false;
char pattern_ch = pattern[p_loc]; // 模式肯定还有剩余
// 有 * 的情况
if(p_loc < m-1 && pattern[p_loc+1]=='*') {
// 可以直接跳过 pattern 中这两个字符
flag = backtrack(str, pattern, str_loc, p_loc+2);
if(!flag && str_loc<n && (str[str_loc] == pattern_ch || pattern_ch == '.')) { // 如果不能直接跳过，那么进行匹配
flag = backtrack(str, pattern, str_loc+1, p_loc);
}
} else { // 没有 * 的情况，只需要看当前位置的字符是否相等
if(str_loc < n) {
// 如果这种情况下串没有剩余，模式有剩余，那就是错误的
char str_ch = str[str_loc];
char pattern_ch = pattern[p_loc];
if(str_ch == pattern_ch || pattern_ch == '.') {
flag = backtrack(str, pattern, str_loc+1, p_loc+1);
}
}
}
return flag;
}
};
思路2:动态规划
https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/jian-zhi-offer-19-zheng-ze-biao-da-shi-pi-pei-dong/
https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode-s3jgn/
https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/zhu-xing-xiang-xi-jiang-jie-you-qian-ru-shen-by-je/
迭代：
注意人家是采用|，看和不看两种情况，不知道到底看不看，反正两个都试试，有一个能成功就行。
所以不用纠结 bcc 与 bcc* 这个情况。之前纠结如何写出我只用c*一次的代码。
20.表示数值的字符串(重点)
不会写
思路1:p127
class Solution {
public:
bool isNumber(string s) {
if(s.empty()){
return false;
}
//去除首尾空格，中间出现空格就不对了，但是首尾出现空格是可以的
//"1 " " 1" true
//". 1" false
//如下代码是去除了所有空格
// char blank=' ';
// if(s.find(blank) != string::npos){
// for(int i=0;i<s.size();i++){
// if(s[i]==blank){
// s.erase(i,1);
// }
// }
// }
//如下代码是去除首尾空格
size_t n = s.find_last_not_of(" \r\n\t");
if (s.find_last_not_of(" \r\n\t") != string::npos){
s.erase(n + 1, s.size() - n);
}
n = s.find_first_not_of(" \r\n\t");
if (n != string::npos){
s.erase(0, n);
}
int start=0;
bool numeric=scanInteger(s,start);
if(s[start]=='.'){
start++;
numeric=scanUnsignedInteger(s,start)||numeric;
}
if(start<s.size()&&(s[start]=='e'||s[start]=='E')){
start++;
numeric=numeric&&scanInteger(s,start);
}
return numeric&&(start==s.size());
}
bool scanUnsignedInteger(string &s,int &start){
int temp=start;
while(start<s.size()&&s[start]>='0'&&s[start]<='9'){
start++;
}
return start>temp;
}
bool scanInteger(string &s,int &start){
if(s[start]=='+'||s[start]=='-'){
start++;
}
return scanUnsignedInteger(s,start);
}
};
ps: c++ string去除首尾 空格、\n、\r、\t
还没有看:
面试题20. 表示数值的字符串（有限状态自动机，清晰图解）
https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/solution/mian-shi-ti-20-biao-shi-shu-zhi-de-zi-fu-chuan-y-2/
(评论区也有上面的写法，但是没有用到库函数)
21.调整数组顺序使奇数位于偶数前面
思路1：首尾双指针
定义头指针left ，尾指针right
left 一直往右移，直到它指向的值为偶数
right 一直往左移， 直到它指向的值为奇数
交换nums[left] 和 nums[right] .
重复上述操作，直到 left==right .
关键点在于：当l指向偶数且r指向奇数的时候才进行互换！！！
ps:x&1 位运算 等价于 x%2 取余运算，皆可用于判断数字奇偶性
注意自己进行功能性测试:偶数在奇数前；奇数全在偶数前
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
for(int l=0,r=nums.size()-1;l<r;){
if(nums[l]%2){
l++;
}
if( l<r && nums[r]%2==0){ //如果用!，注意!的优先级大于%
r--;
}
if( l<r && (nums[r]%2) && (nums[l]%2==0)){
int temp=nums[r];
nums[r]=nums[l];
nums[l]=temp;
r--;l++;
}
}
return nums;
}
};
其他人的代码:
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
while (left < right && nums[left] % 2 != 0) {
left++;
}
while (left < right && nums[right] % 2 == 0) {
right--;
}
if (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
right--;left++;
}
}
return nums;
}
};
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int l=0,r=nums.size()-1;
while(l<=r){
if(nums[l]%2){
l++;
}
else if(nums[r]%2==0){
r--;
}
else{
int temp=nums[r];
nums[r]=nums[l];
nums[l]=temp;
r--;l++;
}
}
return nums;
}
};
思路2:快慢双指针
- 定义快慢双指针 fast 和 low ，fast 在前， low 在后 .
- fast 的作用是向前搜索奇数位置，low 的作用是指向下一个奇数应当存放的位置
- fast 向前移动，当它搜索到奇数时，将它和 nums[low] 交换，此时low 向前移动一个位置 .
- 重复上述操作，直到fast 指向数组末尾 .
总而言之：fast是遍历整个数组的快指针，目标是找出所有的奇数，low是记录奇数位置的慢指针
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int low = 0, fast = 0;
while (fast < nums.size()) {
if (nums[fast] & 1) {
swap(nums[low], nums[fast]);
low ++;
}
fast ++;
}
return nums;
}
};
