day2
14-1 剪繩子 (重點)
思路1:動態(tài)規(guī)劃
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
思路：
-
因為數(shù)據(jù)量大,所以不適合用動態(tài)規(guī)劃(?為什么),要用貪婪算法。
- 在貪婪算法中為了防止位數(shù)溢出,要模1000000007，可以保證值永遠在int的范圍內(nèi),且res本身要設(shè)為long
- 在大數(shù)求余中可以使用循環(huán)求余和快速冪求余,時間復雜度依次為O(n)和O(logn) 下面代碼是循環(huán)求余，快速冪求余沒有研究
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的個數(shù)
ps:這道題要求的輸入是uint32_t n，可以看到是無符號int32位，給出的輸入例子是00000000000000000000000000001011形式，但是如果cout<<num<<endl;會發(fā)現(xiàn)輸出是11，所以你不要以為可以直接遍歷字符串n，數(shù)1的個數(shù)。
思路1:
只要不是負數(shù)，就沒事。
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
常規(guī)解法，針對負數(shù)也有效
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:整數(shù)中有幾個1就只需循環(huán)幾次
把一個整數(shù)減去1之后再和原來的整數(shù)做位的與運算，得到的結(jié)果相當于把整數(shù)的二進制表示中最右邊的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.數(shù)值的整數(shù)次方
思路1:暴力循環(huán)
超時 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:快速冪
注意
- 如果指數(shù)是負數(shù)怎么辦？求倒數(shù)么？那么又萬一x是0呢？0是不能求倒數(shù)的。
-
注意n的取值范圍，如果n取最小的負值，取反后便無法裝入了。
遞歸寫法：
可以用右移運算符代替除以2，用位與運算符代替%來判斷一個數(shù)是奇還是偶。位運算的效率比乘除、求余都高。
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是負數(shù)也沒關(guān)系
if(nn&1){
ans*=x;
}
nn>>=1;
x*=x;
}
return ans;
}
};
17.打印從1到最大的n位數(shù)
這道題應(yīng)該考大數(shù)問題的，所以思路1理論上行不通
思路1:暴力解法，找到最大的n位數(shù)，然后從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:大數(shù) 模擬加法
課本p114-116
代碼
思路3:全排列
課本p117:由于模擬整數(shù)的加法不是簡單的事，我們可以轉(zhuǎn)換思路。題意中n位所有十進制數(shù)其實就是n個從0到9的全排列。我們把數(shù)字的每一位都從0到9排列一遍，就得到了所有的十進制數(shù)。只是在打印的時候，排在前面的0不打印出來，而且leetcode要求從1開始而不是從0開始。全排列使用遞歸實現(xiàn)，遞歸結(jié)束的條件是我們已經(jīng)設(shè)置了數(shù)字的最后一位。
算法筆記p115也有全排列，但是與這題略有不同。
自己寫的代碼，使用的是int數(shù)組而不是string也不是char數(shù)組
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){
//理論來說應(yīng)該輸出當前產(chǎn)生的p數(shù)組，也就是一個大數(shù),而不是轉(zhuǎn)換成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;
}
};
下次實現(xiàn)課本上的兩個方法的代碼以及他人的方法的代碼，加強理解。
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.刪除鏈表的節(jié)點
leetcode對比原題有改動，太簡單了，就是鏈表刪除節(jié)點的常規(guī)操作。
節(jié)點的題目主要考慮邊界情況
特殊情況：頭節(jié)點為空，刪除頭節(jié)點，刪除尾節(jié)點，只有一個節(jié)點
思路：遍歷，然后刪掉
/**
* 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; //當刪除頭節(jié)點時
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)時間內(nèi)刪除鏈表節(jié)點。
注意題目說的是給定一個節(jié)點指針，在o(1)時間內(nèi)刪除該節(jié)點。
思路：119-122f
19.正則表達式匹配(重點)
不會寫
思路1:遞歸
p124-126
超時(是不是substr太慢了，或許應(yīng)該使用迭代器?,或者用兩個索引記錄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:動態(tài)規(guī)劃
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/
迭代：
注意人家是采用|，看和不看兩種情況，不知道到底看不看，反正兩個都試試，有一個能成功就行。
所以不用糾結(jié) bcc 與 bcc* 這個情況。之前糾結(jié)如何寫出我只用c*一次的代碼。
20.表示數(shù)值的字符串(重點)
不會寫
思路1:p127
class Solution {
public:
bool isNumber(string s) {
if(s.empty()){
return false;
}
//去除首尾空格，中間出現(xiàn)空格就不對了，但是首尾出現(xiàn)空格是可以的
//"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. 表示數(shù)值的字符串（有限狀態(tài)自動機，清晰圖解）
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/
(評論區(qū)也有上面的寫法，但是沒有用到庫函數(shù))
21.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
思路1：首尾雙指針
定義頭指針left ，尾指針right
left 一直往右移，直到它指向的值為偶數(shù)
right 一直往左移， 直到它指向的值為奇數(shù)
交換nums[left] 和 nums[right] .
重復上述操作，直到 left==right .
關(guān)鍵點在于：當l指向偶數(shù)且r指向奇數(shù)的時候才進行互換?。?！
ps:x&1 位運算 等價于 x%2 取余運算，皆可用于判斷數(shù)字奇偶性
注意自己進行功能性測試:偶數(shù)在奇數(shù)前；奇數(shù)全在偶數(shù)前
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){ //如果用!，注意!的優(yōu)先級大于%
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 的作用是向前搜索奇數(shù)位置，low 的作用是指向下一個奇數(shù)應(yīng)當存放的位置
- fast 向前移動，當它搜索到奇數(shù)時，將它和 nums[low] 交換，此時low 向前移動一個位置 .
- 重復上述操作，直到fast 指向數(shù)組末尾 .
總而言之：fast是遍歷整個數(shù)組的快指針，目標是找出所有的奇數(shù)，low是記錄奇數(shù)位置的慢指針
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;
}
};
