LeetCode刷题笔记

/*********************************************
状态转移方程：
f[i][j]=max{f[i−1][x]-∣j−x∣}+points[i][j]
优化：
j>=x时
f[i][j]=max{f[i−1][x]+x∣}+points[i][j]-j
j<=x时
f[i][j]=max{f[i−1][x]-x∣}+points[i][j]+j
**********************************************/
class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        int m=points.size();                //行数
        int n=points[0].size();             //列数
        vector<long long> end(n);           //建立保存状态的数组
        for(int i=0;i<m;i++){               //遍历每一行
            vector<long long> temp(n);      //保存某一行的数据
            long long best=LLONG_MIN;  
            //best存储上一行，并且小于等于当前列的最大值,即max{f[i−1][x]+x∣}
            for(int j=0;j<n;j++){            //正序遍历,每次j++保证j>x;
                best=max(best,end[j]+j);
                temp[j]=best+points[i][j]-j;  //第i行第j列正序的最大值
            }
            best=LLONG_MIN;
            for(int j=n-1;j>=0;j--){           //倒叙序遍历,每次j--保证j<x;
                best=max(best,end[j]-j);
                //best存储上一行，并且大于等于当前列的最大值,即max{f[i−1][x]-x∣}
                temp[j]=max(temp[j],best+points[i][j]+j);  
                                                //第i行第j列的最大值(正序倒叙取最大值)
            }
            end=move(temp);                     //把temp状态转移到end，end在本次循环存储上一行的状态
        }
        return *max_element(end.begin(), end.end());
    }
};

class TreeAncestor {
public:
    vector<vector<int>> ance;
    const static int MAX_MAX=16;
    TreeAncestor(int n, vector<int>& parent) {
        ance=vector<vector<int>>(n,vector(MAX_MAX,-1));
        for(int i=0;i<n;i++){
            ance[i][0]=parent[i];    //初始化父节点
        }
        for(int j=1;j<MAX_MAX;j++){
            for(int i=0;i<n;i++){
                if(ance[i][j-1]!=-1){
                    ance[i][j]=ance[ance[i][j-1]][j-1];  //倍增
                     //ance[i][j]=ance[ance[i][j-1]][0]; //下一位是父节点
                }
            }
        }
    }
    int getKthAncestor(int node, int k) {
        for(int i=0;i<MAX_MAX;i++){
            if((k>>i)&1){
                node=ance[node][i];
                if(node==-1){
                    return -1;
                }
            }
        }
        return node;
    }
};
/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor* obj = new TreeAncestor(n, parent);
 * int param_1 = obj->getKthAncestor(node,k);
 */

class Solution {
public:
    string toLowerCase(string s) {
        int len=s.size();
        for(int i=0;i<len;i++){
            if('A'<=s[i]&&s[i]<='Z'){
                s[i]|=32;
            }
        }
        return s;
    }
};
/* 位运算（解题区的思路
        大写变小写、小写变大写 : 字符 ^= 32;
        大写变小写、小写变小写 : 字符 |= 32;  
        小写变大写、大写变大写 : 字符 &= -33;
        eg：
        65(A)->二进制表示为100 0001
        32的二进制表示为 010 0000 
        100 0001|010 0000=110 0001->97(a)
 */