The reason I designed it that way is to increase the likelihood that when shuffle is called it is shuffling based on the original array, not the previously shuffled array. This will increase the chance of detecting bugs in the main algorithm in shuffle.
classSolution { vector<int> orignalNums, ret; public: Solution(vector<int> nums) { srand((unsigned)time(NULL)); ret = orignalNums = nums; } /** Resets the array to its original configuration and return it. */ vector<int> reset(){ ret = orignalNums; // 这条语句其实没什么影响 return orignalNums; } /** Returns a random shuffling of the array. */ vector<int> shuffle(){ for(int i = 0; i < ret.size(); i++){ int index = rand() % (ret.size() - i); swap(ret[i], ret[i + index]); } return ret; } };
/** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(nums); * vector<int> param_1 = obj.reset(); * vector<int> param_2 = obj.shuffle(); */
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library’s sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
Could you come up with an one-pass algorithm using only constant space?
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
Note:
You may assume that both strings contain only lowercase letters.
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
**Follow up:**Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
classSolution { public: voidsetZeroes(vector<vector<int>>& matrix){ int m = matrix.size(); if(!m){ return; } int n = matrix[0].size(); vector<int> rowFlag(m, 1), colFlag(n, 1); for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(matrix[i][j] == 0){ rowFlag[i] = 0; colFlag[j] = 0; } } } for(int i = 0; i < m; i++){ if(!rowFlag[i]){ setZeroRow(matrix, i, n); } } for(int i = 0; i < n; i++){ if(!colFlag[i]){ setZeroCol(matrix, i, m); } } } voidsetZeroRow(vector<vector<int>> &matrix, int row, int n){ for(int i = 0; i < n; i++) matrix[row][i] = 0; } voidsetZeroCol(vector<vector<int>> &matrix, int col, int m){ for(int i = 0; i < m; i++) matrix[i][col] = 0; } };
Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.
Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?
Example:
1 2 3 4 5 6 7 8
// Init a singly linked list [1,2,3]. ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); Solution solution = new Solution(head);
// getRandom() should return either 1, 2, or 3 randomly. Each element >should have equal probability of returning. solution.getRandom();
classSolution { vector<ListNode*> nodes; public: /** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */ Solution(ListNode* head) { srand(time(NULL)); ListNode *p = head; while(p){ nodes.push_back(p); p = p->next; } } /** Returns a random node's value. */ intgetRandom(){ int r = rand() % nodes.size(); return nodes[r]->val; } };
/** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(head); * int param_1 = obj.getRandom(); */
classSolution { ListNode *head, *mp; int listLen; public: /** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */ Solution(ListNode* h) { srand(time(NULL)); this->head = h; this->mp = this->head; listLen = 0; ListNode *p = h; while(p){ listLen++; p = p->next; } } /** Returns a random node's value. */ intgetRandom(){ int r = rand() % listLen; for(int i = 0; i < r; i++){ mp = mp->next; if(mp == nullptr) mp = head; } return mp->val; } };
/** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(head); * int param_1 = obj.getRandom(); */
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"path = "/a/./b/../../c/", => "/c"Corner Cases:
Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".
题目要求简化一个路径, 要做到两点:
去掉无效的/, 比如连续的/和结尾的/
把.和..这种相对路径转换为绝对路径
先使用栈保存/分割的每个节点, 在处理过程中分为三种情况:
节点为.: 不做任何处理
节点为..: 若栈不为空则弹出栈顶元素
否则将节点入栈
最后把栈变为字符串输出.
class Solution {
public:
string simplifyPath(string path) {
vector<string> pathStack = splitPath(path);
return getFinPath(pathStack);
}
string getFinPath(vector<string> &finStack){
string re = "";
for(int i = 0 ; i < finStack.size(); i++){
re += "/";
re += finStack[i];
}
if(re == "")
re = "/";
return re;
}
vector<string> splitPath(string path){
vector<string> re;
for(int i = 0; i < path.size(); i++){
if(path[i] != '/'){
int end = getEnd(path, i);
string node = string(path.begin() + i, path.begin() + end);
if(node == string(".")){
// do nothing
}
else if(node == string("..")){
if(!re.empty()) re.pop_back();
}
else{
re.push_back(node);
}
i = end;
}
}
return re;
}
int getEnd(string path, int start){
int i = start;
for(; i < path.size() && path[i] != '/'; i++);
return i;
}
};
class Solution {
public:
int climbStairs(int n) {
if(n == 1)return 1;
if(n == 2)return 2;
int a = 1, b = 2, t;
for(int i = 2; i < n; i++){
t = b;
b = a + b;
a = t;
}
return b;
}
};