31 下一个排列
class Solution {
public void nextPermutation(int[] nums) {
/** 前面尽量让他们不动，找到最小的一个值进行小范围的交换。
* 两种情况一种是最大值 也就是有序集合的逆序， 5 4 3 2 1 ，返回就是 逆序
* 如果是存在着逆序的 1 3 4 8 5 4 这种情况就进行倒序查找 如果整体呈现升序 从后往前， 直到找到一个转折点 这里就是 8 8的前一个节点就是4
* 将4 与后面第一个出现比4要大的数字进行交换， 1 3 5 8 4 4 然后再将后面的 进行升序 13 5 4 4 8 该集合就是第一个大于序列
**/
int k = nums.length - 1;
// 从后往前判断查找
while(k > 0 && nums[k - 1] >= nums[k]) k--;
if (k <= 0) { // 证明整体是从大到小 情况一
Arrays.sort(nums);
} else {
// 情况二 这个带你就是转折带你
int index = k - 1;
// 查找后面第一个大于自己的数，然后进行互换。
while (k < nums.length && nums[k] > nums[index] ) {
k++;
}
int temp = nums[index];
nums[index] = nums[k - 1];
nums[k - 1] = temp;
// 然后在进行转折点后面的部分排序从大到小
Arrays.sort(nums, index + 1, nums.length);
}
}
}32 最长有效括号
class Solution {
// 能往里面放又括号的前提是左括号的数量大于右括号
// 当我们放进去一个左括号的时候就可以求出来他能够组成的最长的长度。他能匹配出来最长的长度。
public int longestValidParentheses(String s) {
Deque<Integer> deque = new LinkedList();
int res = 0;
for (int i = 0, start = -1; i < s.length(); i ++) {
if (s.charAt(i) == '(') {
deque.offerFirst(i);
}else {
if (deque.size() != 0) {
deque.pollFirst();
if(deque.size() != 0) {
res = Math.max(res, i - deque.peekFirst());
} else {
res = Math.max(res, i - start);
}
}else {
start = i;
}
}
}
return res;
}
}33 搜索旋转排序数组 (这题我面试问到了三次 我吐了)
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) { //[left, right]
int mid = right + left + 1 >> 1;
if (nums[mid] >= nums[0]) {
left = mid;
}else {
right = mid - 1;
}
}
//此时right 和 left 都归一个坐标了。
if (target >= nums[0]) {
left = 0;
}else {
right = nums.length - 1;
left = left + 1;
}
while(left < right) {
int mid = right + left >> 1;
if(nums[mid] >= target) {
right = mid;
}else {
left = mid + 1;
}
}
if(target == nums[right]) {
return right;
}else {
return -1;
}
}
}34 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[]{-1, -1};
if(nums.length <= 0) {
return res;
}
int left = 0, right = nums.length - 1;
while(left < right) {
int mid = left + right >> 1;
if (nums[mid] >= target) {
right = mid;
}else {
left = mid + 1;
}
}
if(nums[right] == target) {
res[0] = left;
}
left = 0;
right = nums.length - 1;
while(left < right) {
int mid = right + left + 1 >> 1;
if (target >= nums[mid]) {
left = mid;
} else {
right = mid - 1;
}
}
if(nums[right] == target) {
res[1] = left;
}
return res;
}
}35 搜索插入位置
class Solution {
public int searchInsert(int[] nums, int target) {
//我们最后移动到的位置要不就是等于这个target 要不就是第一个大于这个的数，也就是有区间的分界点，
int left = 0, right = nums.length;
while(left < right) {
int mid = right + left >> 1;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}36 有效的数独
class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[] st = new boolean[9];
// 判断行
for (int i = 0; i < 9; i++) {
Arrays.fill(st, false);
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int t = board[i][j] - '1';
if (st[t]) {
return false;
} else {
st[t] = true;
}
}
}
}
// 判断列
for (int i = 0; i < 9; i++) {
Arrays.fill(st, false);
for (int j = 0; j < 9; j++) {
if (board[j][i] != '.') {
int t = board[j][i] - '1';
if (st[t]) {
return false;
} else {
st[t] = true;
}
}
}
}
//判断每个小分组
for (int i = 0; i < 9; i += 3) {
for (int j = 0; j < 9; j += 3) {
Arrays.fill(st, false);
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
if (board[i + x][j + y] != '.') {
int t = board[i + x][j + y] - '1';
if (st[t]) {
return false;
} else {
st[t] = true;
}
}
}
}
}
}
return true;
}
}37 解数独
class Solution {
boolean[][] row, col;
boolean[][][] cell;
public void solveSudoku(char[][] board) {
// 9 行，每一行保存改行出现数字的状态
row = new boolean[9][9];
// 9行，每一行保存列出现数字的状态
col = new boolean[9][9];
// 3* 3 一共九个小区域，最后的9代表区域内数字出现的状态。
cell = new boolean[3][3][9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int t = board[i][j] - '1';
row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
}
}
}
dfs(board, 0, 0);
}
boolean dfs(char[][] board, int x, int y) {
if (y == 9) {x++; y = 0;}
if( x == 9) return true;
if (board[x][y] != '.') { // 有数
return dfs(board, x, y + 1);
}
//没有数的情况
for (int i = 0; i < 9; i++) {
if(!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {
board[x][y] = (char)('1' + i);
row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
// 走的通的话
if (dfs(board, x, y + 1)) {
return true;
}
//走不通回溯
board[x][y] = '.';
row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
}
}
return false;
}
}38 外观数列
class Solution {
public String countAndSay(int n) {
String res = "1";
for(int i = 0; i < n - 1; i ++) {
String s = res;
res = "";
for (int j = 0; j < s.length(); ) {
int k = j + 1;
while(k < s.length() && s.charAt(k) == s.charAt(j)) {
k++;
}
res += (k - j) ;
res += s.charAt(j);
j = k;
}
}
return res;
}
}39 组合总和
class Solution {
List<List<Integer>> res;
List<Integer> path;
int[] candidates;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
this.candidates = candidates;
res = new LinkedList();
path = new LinkedList();
dfs(0, target);
return res;
}
public void dfs(int index, int target) {
if(target == 0) {
res.add(new LinkedList(path));
return;
}
if (index == candidates.length) {
return;
}
for (int i = 0; i * candidates[index] <= target; i++) {
dfs(index + 1, target - candidates[index] * i);
path.add(candidates[index]);
}
for (int i = 0; i * candidates[index] <= target; i++) {
path.remove(path.size() - 1);
}
}
}40. 组合总和 II
//相比较上一题变换了一种形式。
class Solution {
List<List<Integer>> res;
List<Integer> path;
int[] candidates;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
this.candidates = candidates;
res = new LinkedList();
path = new LinkedList();
Arrays.sort(this.candidates);
dfs(0, target);
return res;
}
public void dfs(int index, int target) {
if (target == 0) {
res.add(new LinkedList(path));
return;
}
if (index == candidates.length) {
return;
}
// 在这里进行了判断能有几个重复的数
int k = index + 1;
while(k < candidates.length && candidates[k] == candidates[index]) {
k++;
}
int cnt = k - index;
for (int i =0; candidates[index] * i <= target && i <= cnt; i++) {
dfs(k, target - candidates[index] * i);
path.add(candidates[index]);
}
for (int i = 0; candidates[index] * i <= target && i <= cnt; i++) {
path.remove(path.size() - 1);
}
}
}
京公网安备 11010502036488号