Fant.J

7862

Fant.J
2019-10-23 07:19
class Solution {
public List<List<Integer>> permutation(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int length = nums.length;
boolean [] visited = new boolean[length];
dfs(res, nums, visited, new ArrayList<>());
return res;
}

public void dfs(List<List<Integer>> res, int[] nums, boolean[] visited, List<Integer> temp){
// 如果长度够nums.length 则添加到res中并return
if(temp.size() == nums.length){
return;
}
// 遍历nums
for(int i = 0; i< nums.length; i++){
// 如果当前数字已读， 则跳到下一个, 如果重复的话
if(visited[i] || i>0 &&  nums[i] == nums[i-1] && visited[i-1]){
continue;
}
// 设置已读， temp存储
visited[i] = true;
//System.out.println(temp);
dfs(res, nums, visited, temp);
visited[i] = false;
temp.remove(temp.size()-1);
}
}
}


Fant.J
2019-09-30 03:05
class Solution {
public String reverseWords(String s) {
// 反转整个字符串
char[] chars = s.toCharArray();
reverse(chars,0, chars.length-1);
// 反转每个单词
int index = 0;
for(int i = 0; i< chars.length; i++){
// 检测到' '就执行翻转
if(chars[i] == ' '){
reverse(chars, index, i-1);
index = i+1;
}
// 处理最后一个字符
if(i == chars.length-1){
reverse(chars, index, i);
}
}
return new String(chars);

}
public void reverse(char[] chars, int start, int end){
for(int i = start; i< end; i++){
char temp = chars[i];
chars[i] = chars[end];
chars[end] = temp;
end--;
}
//System.out.println(Arrays.toString(chars));
}
}


Fant.J
2019-09-30 02:45
class Solution {
public List<List<Integer> > findContinuousSequence(int sum) {
// 前后指针法
// int i = 1;
int j = 1;
int count = 1; // 计数器
List<List<Integer>> res = new ArrayList<>();
// 这里的i就是前指针
for(int i = 1; i<= sum/2; i++){

// 如果计数值小鱼sum， 则j往后移动
while(count < sum){
count += ++j;
}
if(count == sum && i<j){
List<Integer> temp = new ArrayList<>();
// 将i-j之间的数放进去
for(int k = i; k <= j; k++){
}
}
// 每次遍历完都要将当前的i去掉， 即i往后移动
count -= i;
}
return res;
}
}


Fant.J
2019-09-30 02:27
class Solution {
public int[] findNumbersWithSum(int[] nums, int target) {
// 存值Set
Set<Integer> map = new HashSet<>();
for(int i = 0; i< nums.length; i++){
// 边放边比较，返回符合的结果
int diff = target - nums[i];
if(map.contains(diff)){
return new int[]{nums[i],diff};
}
}
return null;

}
}


Fant.J
2019-09-29 10:14
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {

public int[] numberOfDice(int n) {
// n~6n 一共有6n-n+1个数
int[] res = new int[6 * n - n + 1];
int[][]f=new int[n+1][6*n+1];
f[0][0] = 1;
// 次数
for(int i = 1; i <= n ; i++){
// 点数
for(int j = 1; j <= i*6; j ++){
// 点数从1开始减，一直
for(int k = 1; k <=Math.min(j, 6); k ++)
f[i][j] += f[i-1][j - k];
}
}
for (int i = n,j=0; i <= 6 * n; i++,j++) {
res[j] = f[n][i];
}
return res;
}

}


Fant.J
2019-09-28 15:30
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public int getMaxValue(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int res[] = new int[cols];
for(int i = 0; i< rows; i++){
for(int j = 0; j< cols; j++){
int up = 0;
int left = 0;
if(i > 0){
// 把res的当前元素赋值
up = res[j];
}
if( j > 0){
// 把res的上一个元素赋值
left = res[j-1];
}
res[j] = Math.max(up,left) + grid[i][j];
}
}
return res[cols-1];
}
}


Fant.J
2019-09-21 14:41
class Solution {
public int[] printMatrix(int[][] matrix) {
if(matrix == null|| matrix.length == 0){return new int[0];}
int startX = 0;
int endX = matrix.length;
int startY = 0;
int endY = matrix[0].length;
//System.out.println(startX + " " + endX + " " + startY + " " + endY);
int res[] = new int[endX * endY ];
while((startX <= endX) && (startY<=endY)){
printMatrix(res, matrix, startX, endX-1, startY, endY-1);
startX++;
startY++;
endX--;
endY--;
}
return res;
}
public int index = 0;
public void printMatrix(int res[], int[][] matrix, int startX, int endX, int startY, int endY){
// 向右 ➡
if(startX == endX){
// 说明只能竖着来了, 为什么要等于， 因为怕拉下最后一个元素了
for(int i = startY; i <= endY; i++){
res[index++] = matrix[startX][i];
}
return;
}

// 向下 ⬇
if(startY == endY){
// 说明只能竖着来了
for(int i = startX; i <= endX; i++){
res[index++] = matrix[i][startY];
}
return;
}
// 向右 ➡
for(int i = startY; i < endY; i++){
res[index++] = matrix[startX][i];
}
// 向下 ⬇
for(int i = startX; i < endX; i++){
res[index++] = matrix[i][endY];
}
// 向左 ⬅
for(int i = endY; i > startY; i--){
res[index++] = matrix[endX][i];
}
// 向上 ⬆  y不变x变
for(int i = endX; i > startX; i--){
res[index++] = matrix[i][startY];
}

}
}


Fant.J
2019-09-20 10:12
class Solution {
public boolean isPopOrder(int [] pushV,int [] popV) {
// 如果两个数组为空， 直接返回true， 两个数组长度不等， 返回false
if(pushV == null && popV == null){
return true;
}
if(pushV.length != popV.length){
return false;
}
// 新建一个栈， 将push一个一个放入， 并判断
// 如果元素与popV的top元素相等， 则弹出popV， 否则继续在stack里放元素
// 如果顺序正确的话， PopV应该会为空值
Stack<Integer> stack = new Stack<>();
int index = 0;
for(int i = 0; i< popV.length; i++){
stack.push(pushV[i]);
while(!stack.isEmpty() && stack.peek() == popV[index]){
stack.pop();
index++;
}
}
return stack.isEmpty();
}
}


Fant.J
2019-09-20 10:11
class Solution {
public boolean isPopOrder(int [] pushV,int [] popV) {
// 如果两个数组为空， 直接返回true， 两个数组长度不等， 返回false
if(pushV == null && popV == null){
return true;
}
if(pushV.length != popV.length){
return false;
}
// 新建一个栈， 将push一个一个放入， 并判断
// 如果元素与popV的top元素相等， 则弹出popV， 否则继续在stack里放元素
// 如果顺序正确的话， PopV应该会为空值
Stack<Integer> stack = new Stack<>();
int index = 0;
for(int i = 0; i< popV.length; i++){
stack.push(pushV[i]);
while(!stack.isEmpty() && stack.peek() == popV[index]){
stack.pop();
index++;
}
}
return stack.isEmpty();
}
}


Fant.J
2019-09-18 13:25
class Solution {

public boolean hasPath(char[][] matrix, String str) {
if(matrix == null || str == "" || matrix.length == 0){
return false;
}
int length = 0;
int rows = matrix.length;
int cols = matrix[0].length;
// 对元素进行打标
boolean[][] visited = new boolean[rows][cols];

for(int i = 0; i< rows; i++){
for(int j = 0; j < cols; j++){
// 遍历调用方法
if(findPath(matrix, str, rows, cols, i, j, visited, length)){
return true;
}
}
}
return false;
}

public static boolean findPath(char[][] matrix, String str, int rows, int cols, int row, int col, boolean[][] visited, int length){
int strLen = str.length();
boolean flag = false;
// System.out.println(str + " " + row +" " + col + " " + length+ " "+ visited[row][col] + " " + str.charAt(length));
// 如果行号和列号合法， 并且打标为未路过
if(row>=0 && row<rows && col>=0 && col<cols && visited[row][col] == false
&& matrix[row][col] == str.charAt(length)){
// 路长+1
length++;
visited[row][col] = true;
if(length == strLen){
return true;
}
flag = findPath(matrix, str, rows, cols, row+1, col, visited, length)||
findPath(matrix, str, rows, cols, row, col+1, visited, length)||
findPath(matrix, str, rows, cols, row-1, col, visited, length)||
findPath(matrix, str, rows, cols, row, col-1, visited, length);
if(!flag){
length--;
visited[row][col] = false;
}

}
return flag;
}
}