youngyangyang04 / leetcode-master Goto Github PK

// #37 解数独
class Solution {
private:
	vector<vector<int>> usedRowNum = vector<vector<int>>(9, vector<int>(9));
	vector<vector<int>> usedColNum = vector<vector<int>>(9, vector<int>(9));
	vector<vector<int>> usedQurNum = vector<vector<int>>(9, vector<int>(9));
	vector<vector<char>> result;
	bool solveSudoIter(vector<vector<char>>& board, int curRow, int curCol) {
		if (curRow == 9)
		{
			result = board;
			return true;
		}
		if (board[curRow][curCol] != '.') {
			return solveSudoIter(board, curRow + (curCol + 1) / 9, (curCol + 1) % 9);
		}
		for (int num = 0; num < 9; num++) {
			if (usedRowNum[curRow][num] == 1) continue;
			if (usedColNum[curCol][num] == 1) continue;
			int curQur = 3 * (curRow / 3) + curCol / 3;
			if (usedQurNum[curQur][num] == 1) continue;
			

			//push
			usedRowNum[curRow][num] = 1;
			usedColNum[curCol][num] = 1;
			usedQurNum[curQur][num] = 1;
			board[curRow][curCol] = '1' + num;

			// iter
			bool ifFound = solveSudoIter(board, curRow + (curCol + 1) / 9, (curCol + 1) % 9);
			if (ifFound) return true;

			//pop back
			usedRowNum[curRow][num] = 0;
			usedColNum[curCol][num] = 0;
			usedQurNum[curQur][num] = 0;
			board[curRow][curCol] = '.';
		}
		return false;
	}
public:
	void solveSudoku(vector<vector<char>>& board) {
		for (int row = 0; row < 9; row++) {
			for (int col = 0; col < 9; col++)
			{
				if (board[row][col] == '.') continue;
				int curNum = board[row][col] - '1';
				usedRowNum[row][curNum] = 1;
				usedColNum[col][curNum] = 1;
				int curQur = 3 * (row / 3) + col/3;
				usedQurNum[curQur][curNum] = 1;
			}
		}
		solveSudoIter(board, 0, 0);
	}
};

// #51 N皇后问题
class Solution {
	vector<vector<string>> result;
	vector<string> curPath;
	void solveNQueensIter(int curRow, int targetRow, vector<int>& usedCol, unordered_set<int>& usedDiff, unordered_set<int>& usedSum) {
		if (curRow == targetRow) {
			result.emplace_back(curPath);
			return;
		}
		for (int curCol = 0; curCol < targetRow; curCol++) {
			if (usedCol[curCol] == 1) continue;
			if (usedDiff.find(curRow - curCol) != usedDiff.end()) continue;
			if (usedSum.find(curRow + curCol) != usedSum.end()) continue;
			string path(targetRow, '.' );
			path[curCol] = 'Q';
			curPath.emplace_back(path);
			usedCol[curCol] = 1;
			usedDiff.insert(curRow - curCol);
			usedSum.insert(curRow + curCol);
			solveNQueensIter(curRow + 1, targetRow, usedCol, usedDiff, usedSum);
			usedDiff.erase(curRow - curCol);
			usedSum.erase(curRow + curCol);
			usedCol[curCol] = 0;
			curPath.pop_back();
		}
	}
public:
	vector<vector<string>> solveNQueens(int n) {
		vector<int> usedCol(n, 0);
		unordered_set<int> usedDiff, usedSum;
		solveNQueensIter(0, n, usedCol, usedDiff, usedSum);
		return result;
	}
};

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA;
        ListNode pB = headB;
        while (true) {
            if (pA == null && pB == null) return null;
            if (pA == null) {
                pA = headB;
            }
            if (pB == null) {
                pB = headA;
            }
            if (pA == pB) return pB;
            pA = pA.next;
            pB = pB.next;
        }
    }
}

vector<vector<int>> generateMatrix(int n) {

    vector<vector<int>> M;
    M.resize(n, vector<int>(n, 0));
    int final_num = n*n;
    int start = 1;
    int i = 0;
    int r,c;
    r=c=0;
    while(start <= final_num){
        M[r][c] = start++;
        if(r + dirs[i][0] < n && 
           c + dirs[i][1] < n && 
          r + dirs[i][0] >= 0 && 
           c + dirs[i][1] >= 0 && 
           M[r + dirs[i][0]][c + dirs[i][1]] == 0){
            r = r + dirs[i][0];
            c = c + dirs[i][1];
        }else{
            i = (i+1) % 4;
            r = r + dirs[i][0];
            c = c + dirs[i][1];
        }
    }
    return M;    
}   

class Solution {
public:
    void invert (TreeNode* cur){
        if (cur!=nullptr){
            invert(cur->left);
            swap(cur->left, cur->right);
            invert(cur->left);
        }
    }
    TreeNode* invertTree(TreeNode* root) {
        invert(root);
        return root;
    }
};

对于 0-1 背包问题上的滑动数组写法时，我有一个自己的理解，不知道是否正确。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length < 2) return 0;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] != o2[1]) {
                    return Integer.compare(o1[1],o2[1]);
                } else {
                    return Integer.compare(o2[0],o1[0]);
                }
            }
        });

        int count = 0;
        int edge = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < edge) {
                count++;
            } else {
                edge = intervals[i][1];
            }
        }
        return count;
    }
}

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices.length==0)return 0;
        int[] res=new int[2*k+1];
        for (int i = 1; i <2*k ; i+=2) {
            res[i]=-prices[0];
        }
        for (int i = 0; i <prices.length ; i++) {
            for (int j = 1; j <2*k ; j+=2) {
                res[j]=Math.max(res[j],res[j-1]-prices[i]);
                res[j+1]=Math.max(res[j+1],res[j]+prices[i]);
            }
        }
        return res[2*k];
    }
}

    for (int t = 0; t < target + 1; ++ t) {
        for (int x : nums) {
            
            if (t >=x && dp[t]  <= INT_MAX - dp[t-x]) {
            
                if (t > x) dp[t] += dp[t-x];

                if (t == x && dp[t]  <= INT_MAX - 1) {
                    dp[t] += 1; //当前这个数字可以组成一个集合 满足target
                }
            }
        }
    }
    return dp[target];
}

class Solution {
	static bool peopleCompare(vector<int>& pre, vector<int>& next) {
		if (pre[0] != next[0]) return pre[0] < next[0];
		else
		{
			return pre[1] > next[1];
		}
	}
public:
	vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
		sort(people.begin(), people.end(), peopleCompare);

		int preHeight = people[people.size() - 1][0];
		for (int i = people.size() - 1; i >= 0; i--) {
			int swapTime = people[i][1];
			for (int j = 0; j < swapTime; j++) {
				swap(people[i + j], people[i + j + 1]);
			}
		}
		return people;
	}
};

    backtrack(s, 0)
    return ans