- 31 Next Permutation
贴一个我不太明白的解法，相关的链接：https://leetcode.com/problems/next-permutation/discuss/13921/1-4-11-lines-C++
void nextPermutation(vector<int>& nums) {
int i = nums.size() - 1, k = i;
while (i > 0 && nums[i-1] >= nums[i])
i--;
for (int j=i; j<k; j++, k--)
swap(nums[j], nums[k]);
if (i > 0) {
k = i--;
while (nums[k] <= nums[i])
k++;
swap(nums[i], nums[k]);
}
}
下面是我比较认可的解法：但是细节上还是容易出错，比如<=和>=的地方，i和j的初始化等等
class Solution {
public:
void nextPermutation(vector<int>& nums) {
// next_permutation(nums.begin(), nums.end());
int size = nums.size();
if(size == 0 || size == 1) return;
for(int i = size - 2, j = size - 1; i >= 0; i--) if(nums[i + 1] > nums[i]){
while(nums[j] <= nums[i]) j --;
swap(nums[i], nums[j]);
reverse(nums.begin() + i + 1, nums.end());
return;
}
reverse(nums.begin(), nums.end());
}
};
- 33 Search in Rotated Sorted Array
- 34 Find First and Last Position of Element in Sorted Array
记录几个以后可能会经常用到的工具：
lower_bound：时间复杂度为O(logn)返回第一个target，如果没有就返回第一个比target大的数字，如果所有的数字都比target小，会导致数组越界，使用时需要注意这一点。
upper_bound：和lower_bound相似
equal_bound：和上边两个类似。
使用上边几个STL函数可以有下面两种：
vector<int> searchRange(vector<int>& nums, int target) {
auto bounds = equal_range(nums.begin(), nums.end(), target);
if (bounds.first == bounds.second)
return {-1, -1};
return {bounds.first - nums.begin(), bounds.second - nums.begin() - 1};
}
vector<int> searchRange(vector<int>& nums, int target) {
int lo = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
if (lo == nums.size() || nums[lo] != target)
return {-1, -1};
int hi = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
return {lo, hi};
}
但是，题目中的意思明显是要求使用二分法来求解，请慎重使用这些小工具。
- 35 Search Insert Position
思路：二分法
需要注意的地方：end的初始化使用的是size - 1
不过这个题目可以直接用lower_bound()来解。
return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int begin = 0;
int end = nums.size() - 1;
int mid;
while(begin <= end){
mid = begin + (end - begin) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] > target) end = mid - 1;
else begin = mid + 1;
}
return begin;
}
};
- 36 Valid Sudoku
记录一种牛逼的方法：
public boolean isValidSudoku(char[][] board) {
Set seen = new HashSet();
for (int i=0; i<9; ++i) {
for (int j=0; j<9; ++j) {
char number = board[i][j];
if (number != '.')
if (!seen.add(number + " in row " + i) ||
!seen.add(number + " in column " + j) ||
!seen.add(number + " in block " + i/3 + "-" + j/3))
return false;
}
}
return true;
}
- 38 Count and Say
思路：注意细节就好 - 39 Combination Sum
思路：回溯backtracking - 40 Combination Sum II
思路：回溯backtracking，注意重复的数字
