A Code

Code ( Language :C++) ( Judger :cloudjudge-cluster-9) Edit class Solution { public : /** * @param s: the given string * @return: if a permutation of the string could form a palindrome */ bool canPermutePalindrome ( string &s) { // write your code here const int size = s.size(); if (size == 0 ){ return true ; } unordered_map < int , int > mp; for ( char c : s){ mp[c]++; } int evenCnt = 0 , oddCnt = 0 ; for ( auto i : mp){ if (i.second % 2 ){ oddCnt++; } else { evenCnt++; } } if (oddCnt > 1 ){ return false ; } else if (oddCnt == 1 ){ return size % 2 ; } else { return true ; } } };

Code ( Language :C++) ( Judger :cloudjudge-cluster-5) Edit class Solution { public : /** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @return: The maximum size */ int backPack ( int m, vector < int > &A) { // write your code here vector < int > dp(m + 1 , 0 ); dp[ 0 ] = 1 ; for ( int i = 0 ; i < A.size(); i++){ for ( int j = m; j >= A[i]; j--){ //for(int j = A[i]; j <= m; j++){ //记住这里反向，没想明白为什么 dp[j] = dp[j] || dp[j - A[i]]; } } for ( int i = m; i >= 0 ; i--){ if (dp[i]){ return i; } } } };

Code ( Language :C++) ( Judger :cloudjudge-cluster-4) 转成背包问题 Edit class Solution { public : /** * @param nums: the given array * @return: the minimum difference between their sums */ int findMin ( vector < int > &nums) { // write your code here int sum = 0 ; for ( int i = 0 ; i < nums.size(); i++){ sum += nums[i]; } int halfNear = backPack(sum / 2 , nums); return abs (sum - halfNear - halfNear); } int backPack ( int m, vector < int > A) { // write your code here vector < int > res(m + 1 ); res[ 0 ] = 1 ; for ( int j = 0 ; j < A.size(); j++) { for ( int i = m; i >= A[j]; i--) { res[i] = res[i] || res[i - A[j]]; } } for ( int i = m; i >= 0 ; i--) { if (res[i]) { return i; }...

//Binary search + sorted matrix search class Solution { public : /** * @param matrix: a matrix of integers * @param k: An integer * @return: the kth smallest number in the matrix */ int findNumLess ( vector < vector < int >> &matrix, int target) { const int m = matrix.size(); const int n = matrix[ 0 ].size(); int i = m - 1 ; int j = 0 ; int cnt = 0 ; while (i >= 0 && j < n){ if (matrix[i][j] <= target){ cnt += (i + 1 ); j++; } else { i--; } } return cnt; } int kthSmallest ( vector < vector < int >> &matrix, int k) { // write your code here const int m = matrix.size(); if (m == 0 ){ return 0 ; } const int n = matrix[ 0 ].size(); int start = matrix[ 0 ]...

Code ( Language :C++) ( Judger :cloudjudge-cluster-4) Edit class Solution { public : /** * @param length: the length of the array * @param updates: update operations * @return: the modified array after all k operations were executed */ vector < int > getModifiedArray( int length, vector < vector < int >> &updates) { // Write your code here vector < int > nums(length + 1 , 0 ); for ( int i = 0 ; i < updates.size(); i++){ nums[updates[i][ 0 ]] += updates[i][ 2 ]; nums[updates[i][ 1 ] + 1 ] -= updates[i][ 2 ]; } int preSum = 0 ; vector < int > res; for ( int i = 0 ; i < length; i++){ preSum += nums[i]; res.push_back(preSum); } return res; } };

Code ( Language :C++) ( Judger :cloudjudge-cluster-5) Edit class Solution { public : /** * @param num: a string contains only digits 0-9 * @param target: An integer * @return: return all possibilities */ vector < string > addOperators( string &num, int target) { // write your code here // DFS，recursion的body 更复杂些。 vector < string > res; dfs(num, target, res, "" , 0 , 0 , 0 ); return res; } void dfs ( string &num, int target, vector < string > &res, string resElem, int start, int sum, int diff) { //DFS body的关键是以什么规则，拆成子问题。 //首先要看的是：在当前看，有哪些情况case。先解决当前的所有case。 //然后，每个当前case下都有子问题。 if (start == num.size()){ if (sum == target){ res.push_back(resElem); } return ; } for ( int i = start; i < num.size(); i++){ if (num[start] ==...

class Solution { public : /** * @param nums: an array * @return: the Next Greater Number for every element */ vector < int > nextGreaterElements( vector < int > &nums) { // Write your code here const int n = nums.size(); vector < int > res(n, -1 ); std :: stack < int > stk; for ( int i = 0 ; i < 2 * n; i++){ while (!stk.empty() && nums[stk.top()] < nums[i % n]){ res[stk.top()] = nums[i % n]; stk.pop(); } stk.push(i % n); } return res; } };

Code ( Language :C++) ( Judger :cloudjudge-cluster-9) Edit class Solution { public : /** * @param N: The number of buses * @param route: The route of buses * @param A: Start bus station * @param B: End bus station * @return: Return the minimum transfer number */ int getMinTransferNumber ( int N, vector < vector < int >> &route, int A, int B) { // Write your code here // BFS // 当有一些思路，不知道怎么进行时，就考虑建立变量之间的mapping关系 const int size = route.size(); unordered_map < int , vector < int >> station2Bus; for ( int i = 0 ; i < size; i++){ for ( int j = 0 ; j < route[i].size(); j++){ station2Bus[route[i][j]].push_back(i); } } std :: queue < int > q; q.push(A); int res = 1 ; unordered_set < int > visited; visited.insert(A); while (!q.empty...