使用java开发的平台可以套用php吗

  • 时间:
  • 浏览:645
  • 来源:成都艾邦软件开发

有php和js当然也有html、mysql、css等一系列相关的开发基础也有linux服务器搭建的基础。

但是对java一窍不通(我也不想学)

能做手机应用的开发吗ios或者android。

我主要是有个需求实现一个类GTD工具现在可以在web端实现。

但是我想做成手机端的app把移动端的提醒功能加上这样才像个GTD工具。

请问在没有java基础的情况下能否只靠js或者其他语言实现

回复内容

有php和js当然也有html、mysql、css等一系列相关的开发基础也有linux服务器搭建的基础。

但是对java一窍不通(我也不想学)

能做手机应用的开发吗ios或者android。

我主要是有个需求实现一个类GTD工具现在可以在web端实现。

但是我想做成手机端的app把移动端的提醒功能加上这样才像个GTD工具。

请问在没有java基础的情况下能否只靠js或者其他语言实现

react native

react native 在向你招手

真的会js和PHP的话就不会这样问了哈哈

完全可以weex。angular ionoic 。react都可以

你可以了解下appcan

完全可以

例如你会的

php 提供api amaze UI (页面)appcan或者Hbuilder(工具) app

我最近在做的一个项目就是用web做的app因为没移动端开发的人只能硬着头皮用web写app。后端是django前端框架用了weui。

两种解决方案。

第一种因为我会一点android跟ios开发所以在github上找了一个开源的tabbar,改一下然后相关的按钮指向我网站跳转的页面然后主视图部分用webview(UIWebView)直接显示。这个做的会比较像app。

第二种使用打包工具我使用crosswalk,crosswalk可以把一个应用打包成android和iOS。原理差不多就是编辑crosswalk的配置文件里面有个app首页的配置把进入app的时展示的首页指向你网站的首页就可以了。不过这需要自己来写个web版的tabbar。我就用weui写了个类似微信公众号的网站。

兄弟 meteor(/) 在向你招手。

可以的按照你目前会的这些东西完全可以做一个app

使用 NativeScript你可以用现有的 JavaScript 和 CSS 技术来编写 iOS、Android 和 Windows Phone 原生移动应用程序。由原生平台的呈现引擎呈现界面而不是 WebView正因为如此应用程序的整个使用体验都是原生的。

NativeScript 使您可以使用跨平台的 API 来编写应用程序的代码或者如果你需要你可以使用 JavaScript 直接访问所有特定平台的原生 API。

应该提到ionic纯javascript实现跨平台的应用开发同一套代码既可以用在android上也可以用在ios上你值得拥有

/

可以用JS和PHP来开发Android/iOS移动应用.

PHP主要用来做服务器端.

JS则基于Cordova开发Android/iOS客户端.

Cordova是基于WebView的,所以你可以用传统的HTML/CSS/JS来构建应用.

类似的Hybrid App混合应用开发框架还有很多:

国外: Cordova(PhoneGap,Ionic), Titanium, Sencha Touch, Intel XDK, Xamarin

国内: AppCan, DCloud(MUI), APICloud(SuperWebview), WeX5

最后说点有趣的,其实在Android/iOS上跑PHP也是可以的.

比如我在Ubuntu上交叉编译打包的ARM版PHP解释器,可以直接跑在Android和树莓派Raspbian上.

然后我打包成了一个名为PHPDroid的APK,先启动PHP内置的HTTP服务器,然后打开一个WebView来访问这个服务,实现图形界面交互.iOS上的一个名为DraftCode的应用,在iOS跑PHP也是类似原理.所以说,在Android和iOS上用PHP开发应用也是可行的,虽然有局限性.

本文原创发布php中文网转载请注明出处感谢您的尊重

学习目标

辨别 什么是DFS深度优先 什么是back tracking回溯 什么是recursion递归

学习内容

1、 DFS深度优先的高频题

学习时间

1、 周一至周日晚上 7 点—晚上9点

学习产出

1、 技术笔记 博客 1 篇


什么是DFS深度优先
什么是back tracking回溯
什么是recursion递归

在学习leetcode中backtracking题目时碰到了经典的DFS题目N-Queens。
为啥这个题目既是backtracking又是DFS呢
DFS中为啥又有base caserecursion rule呢


一。区别几个定义

recursion是将当前的问题分解成小一号的问题divide and conquer。在解决小问题的时候然后recursively用同样的逻辑就把大问题“递归”好了。
recursion中我们关心
子问题是什么当前做点什么返回给上一层什么

DFS是在进行“”的搜索或者问题可以被逻辑视为“树”、“层”、“叉”时人为规定一个深度优先搜索的方式。
DFS有base case规定何时return触底反弹。
有recursion rule“递归”规则为
cur.add(i);
dfs(index1,res,cur); //这里是recursion进入下一层问题
cur.remove(cur.size()-1);
即加入一个元素iindex1进入下一层若回溯时需要移除该元素方可回到这一层然后试另外一个元素叉。
N-Queens可以视为每一个row是一层有N个可能性放好第一个Q就进入下一层。


深度优先遍历顺序为 1-2-4-8-5-3-6-7 from jianshu.com
其实是pre-order traversal根左右的顺序。

public void depthOrderTraversal(){if(rootnull){System.out.println(empty tree);return;}ArrayDequeTreeNode stacknew ArrayDequeTreeNode();stack.push(root);while(stack.isEmpty()false){TreeNode nodestack.pop();System.out.print(node.value );if(node.right!null){stack.push(node.right);}if(node.left!null){stack.push(node.left);}}System.out.print();}

联系recursion
进入下一层又可以视为分解为小一号的问题
小一号的问题一直被递归到最小然后触底反弹“归来”解决了大问题。
无特殊情况DFS就用递归实现

back tracking回溯定义
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.
回溯法是一种选优搜索法按选优条件向前搜索以达到目标。但当探索到某一步时发现原先选择并不优或达不到目标就退回一步重新选择这种走不通就退回再走的技术为回溯法。
即放进去进入下一层剔除返回上一层的过程。
cur.add(i);
dfs(index1,res,cur);
cur.remove(cur.size()-1);//这里是back tracking回溯
这岂不就是dfs
其实回溯是dfs的核心动作。
但不是所有DFS都有回溯这个动作。
例如在下面的几个“岛屿”题中并不需要回溯


二。back tracking算法

51. N-Queens
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
如果返回值是ListInteger
这里利用DFS深度优先搜索的方法

public class Solution {  public ListListInteger nqueens(int n) {ListListInteger resnew ArrayList();ListInteger oneResnew ArrayList();dfs(n,res,oneRes);return res;  }  private void dfs (int n,ListListIntegerres,ListIntegeroneRes){//base caseif(oneRes.size()n){res.add(new ArrayListInteger(oneRes));//new !return;}//recurs rule这里没有使用idx因oneRes.size()即 idxfor(int i0;in;i){if(checkValid(oneRes,i)){oneRes.add(i);dfs(n,res,oneRes);oneRes.remove(oneRes.size()-1);//back tracking}}  }  private boolean checkValid (ListInteger oneRes,int colIdx){int currowoneRes.size();for(int i0;icurrow;i){if(oneRes.get(i)colIdx || Math.abs(oneRes.get(i)-colIdx)currow-i){return false;}}return true;  }}

78. Subsets
Given an integer array nums, return all possible subsets (the power set).
The solution set must not contain duplicate subsets.

class Solution {public ListListInteger subsets(int[] nums) {ListListInteger resnew ArrayList();ListInteger curnew ArrayList();int nnums.length;dfs(nums,res,cur,0,n);return res;}void dfs(int[] nums,ListListInteger res,ListInteger cur,int index,int n){//baseif(indexn){res.add(new ArrayList(cur));return;}//recursion rule//不dfs(nums,res,cur,index1,n);//cur.add(nums[index]);dfs(nums,res,cur,index1,n);cur.remove(cur.size()-1);//back tracking}}

22. Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

class Solution {public ListString generateParenthesis(int n) {ListString resnew ArrayListString ();StringBuilder sbnew StringBuilder();dfs(res,sb,0,n,n);return res;}public void dfs(ListString res,StringBuilder sb,int index,int leftRemain,int rightRemain){//baseif(leftRemain0  rightRemain0){res.add(sb.toString());return;}//recursive ruleif(leftRemain0){sb.append(();dfs(res,sb,index1,leftRemain-1,rightRemain);sb.deleteCharAt(sb.length()-1);//back tracking}if(leftRemainrightRemain){sb.append());dfs(res,sb,index1,leftRemain,rightRemain-1);sb.deleteCharAt(sb.length()-1);//back tracking}}}

46. Permutations
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

class Solution {public ListListInteger permute(int[] nums) {//swap and swapListInteger curnew ArrayList();ListListInteger resnew ArrayList();for(int num:nums){cur.add(num);}int nnums.length;dfs(n,cur,res,0);return res;}void dfs(int n, ListInteger cur,ListListInteger res,int index){//base caseif(indexn){res.add(new ArrayList(cur));return;}//recursion rulefor(int iindex;in;i){Collections.swap(cur,index,i);dfs(n,cur,res,index1);Collections.swap(cur,index,i);//back tracking//区别laicode原题 这里是swap ArrayList内的数 所以直接调用Collections.swap}}// void swap(int[] nums,int a,int b){//int tmpnums[a];//nums[a]nums[b];//nums[b]tmp;// }}

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates [2,3,6,7], target 7
Output: [[2,2,3],[7]]

class Solution {public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger resnew ArrayList();ListInteger oneResnew ArrayListInteger();dfs(res,oneRes,candidates,target,0);return res;}void dfs(ListListInteger res,ListInteger oneRes,int[] candidates, int target,int index){//base caseif(target0){res.add(new ArrayList(oneRes));return;}else if(target0){return; //bug}//recursive ruleint ncandidates.length;for(int iindex;in;i){oneRes.add(candidates[i]); //bug2dfs(res,oneRes,candidates,target-candidates[i],i);//bug2: 这里是有没有实现level如何实现数字的重复想清楚看图oneRes.remove(oneRes.size()-1);//back tracking}}}

延伸高频题
698. Partition to K Equal Sum Subsets
Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.
example:[2,3,5,6],k3 result:false
思路排序然后先排除一些可能明显错误的例子如上无法整除为三份或者6大于1/3。
如果[2,3,5,5]可以整除3那么得到target为5。

class Solution {public boolean canPartitionKSubsets(int[] nums, int k) {if(numsnull || nums.length0){return false;}int sumArrays.stream(nums).sum();if(sum%k!0) return false;int target sum/k;//subsumArrays.sort(nums);int beginIndexnums.length-1;if(nums[beginIndex]target){return false;}while(beginIndex0  nums[beginIndex]target){beginIndex--;//自成一组k--;}return partition(new int[k],nums,beginIndex,target);//child problem}boolean partition(int[]subsets,int[] nums,int index, int target){//base caseif(index0) return true;//recursion rule    1 2 3 4int selectednums[index];for(int i0;isubsets.length;i){ //对subset每一个数尝试放入if(subsets[i]selectedtarget){ //if 小于目标还可以放入subsets[i]selected;if(partition(subsets,nums,index-1,target)){return true;//如果index-1子问题成立那么当前层成立//即成功放入subset中就返回true}subsets[i]-selected;//back tracking//如果不能的话就减掉}}return false;}}

Restore IP Addresses
这题也是用back tracking但细节处理比较多
下面这个解法会出现Time Limit Exceeded。
bug:限制了s的长度后下面解法可行了。
if(s.length()12) return res;
重点理解offset的作用
用来iterate字符array三种情况中offset是指针每次尝试跳一个char两个char三个char。

class Solution {public ListString restoreIpAddresses(String s) {ListString resnew ArrayListString();if(snull || s.length()0 || s.length()12) return res;StringBuilder sbnew StringBuilder();dfs(s.toCharArray(),res,sb,0,0);return res;}void dfs(char[] s,ListString res,StringBuilder sb,int index,int offset){//base caseif(index4){//第四层放入第四个点后if(sb.length()s.length4){//并且长度增加四个charres.add(sb.substring(0,sb.length()-1)); //常规是sb从0到sb.length-1这里排除sb.length-1这一位}}//offset的作用就是iterate字符array三种情况中offset是尝试每次跳一个char两个char三个charif(offsets.length){  //offset每次会加1加2或者加3//只要长度还在要求范围内就可以添加、删除。sb.append(s[offset]).append(.);//2.   删除2位dfs(s,res,sb, index1,offset1);sb.delete(sb.length()-2,sb.length()); //back tracking//比如2.   可以删除2.}if(offset1s.length){char as[offset];char bs[offset1];if(a!0){//10.19.   99.sb.append(a).append(b).append(.);dfs(s,res,sb, index1,offset2);sb.delete(sb.length()-3,sb.length()); //25.删除3位}}if(offset2s.length){ //a,b,c char as[offset];char bs[offset1];char cs[offset2];if(a1 //0-199||a2  b0  b4 //200  249||a2  b5  c0  c 5){ //250-255sb.append(a).append(b).append(c).append(.);dfs(s,res,sb, index1,offset3);sb.delete(sb.length()-4,sb.length());//255.删除4位}}}}

迷宫
给定一个M*N的矩阵二维数组分别用0和1表示通路和障碍物。即 0 表示 通路1 表示 障碍物。从矩阵的左上角开始每次只能向右下左上移动位置不能斜着走。请给出从入口到出口的路线。

public class Maze {\tstatic String path  ;static String shortestPath  ;public static void searchInMaze(int x, int y, int[][] maze) {int mmaze.length;int nmaze[0].length;//base cases: out of bound, 1,  //cut the branches,if(x0 || y0) return;if (x  m - 1 || y  n - 1) return;if(maze[x][y]1) return;//the destination : m-1,n-1if(xm-1  yn-1){pathpath(x,y);//update the shortest pathif(shortestPath.length()0 || path.length()shortestPath.length()){shortestPathpath;}//System.out.println(找到路线:  path);return;}//recursion rule:String temppath;pathpath(x,y)-;maze[x][y]1;searchInMaze(x  1, y, maze);  //向右搜索searchInMaze(x, y  1, maze);  //向下搜索searchInMaze(x, y - 1, maze);  //向上搜索searchInMaze(x - 1, y, maze);  //向左搜索//清除maze[x][y]0;//back trackingpathtemp;}public static void main(String[] args) {int[][] maze  {{0, 0, 1, 1, 1, 1, 1, 1, 1},{1, 0, 0, 0, 0, 0, 0, 0, 1},{1, 0, 1, 1, 0, 1, 1, 0, 1},{1, 0, 1, 0, 0, 1, 0, 0, 1},{1, 0, 1, 0, 1, 0, 1, 0, 1},{1, 0, 0, 0, 0, 0, 1, 0, 1},{1, 1, 0, 1, 1, 0, 1, 1, 1},{1, 0, 0, 0, 0, 0, 0, 0, 0},{1, 1, 1, 1, 1, 1, 1, 1, 0}};searchInMaze(0, 0, maze);if (shortestPath.length() ! 0)System.out.println(最短路线  shortestPath);elseSystem.out.println(没有找到路线);}}

最短路线(0,0)-(0,1)-(1,1)-(2,1)-(3,1)-(4,1)-(5,1)-(5,2)-(6,2)-(7,2)-(7,3)-(7,4)-(7,5)-(7,6)-(7,7)-(7,8)-(8,8)

注意

能不能找到路径时是否存在某一条路径需要进行回溯。
查找走过的最大格子数时也就是路径的长度不需要进行回溯。
涉及“岛屿”的相关问题都不需要进行回溯。200.岛屿的数量463. 岛屿的周长、695. 岛屿的最大面积 from csdn blog

二。Depth First Search算法(不含back tracking)
岛屿题
200. Number of Islands

class Solution {static final int[][]dirs{{0,1},{0,-1},{1,0},{-1,0}};public int numIslands(char[][] grid) {int mgrid.length;int ngrid[0].length;int num0;for(int i0;im;i){for(int j0;jn;j){if(grid[i][j]1){dfs(grid,i,j);//infectnum;}}}return num;}void dfs(char[][] grid,int i,int j){//base case if(i0 || igrid.length ||j0 || jgrid[0].length || grid[i][j]!1){return;}grid[i][j]0;//标记走过for(int[] dir:dirs){dfs(grid,idir[0],jdir[1] );//dfs往下一层走}}}

BFS solution:

class Solution {int[][] dirs{{1,0},{-1,0},{0,1},{0,-1}};public int numIslands(char[][] grid) {if(gridnull ||grid.length0) return 0;//bugint count0;for(int i0;igrid.length;i){for(int j0;jgrid[0].length;j){if(grid[i][j]1){count;QueueListInteger qnew LinkedList();ListInteger startArrays.asList(i,j);q.offer(start);grid[i][j]0;while(!q.isEmpty()){int sizeq.size();ListInteger curq.poll();for(int s0;ssize;s){for(int[] dir:dirs){int nextXcur.get(0)dir[0];int nextYcur.get(1)dir[1];if(nextX0  nextXgrid.length  nextY0  nextYgrid[0].length  grid[nextX][nextY]1){q.offer(Arrays.asList(nextX,nextY));grid[nextX][nextY]0;}}}}}}}return count;}}

463. Island Perimeter
推荐DFS

public class Solution {public static int islandPerimeter(int[][] grid) {if(grid.length  0) {return 0;}int m  grid.length;int n  grid[0].length;boolean visited[][]  new boolean[m][n];for(int i  0; i  m; i) {for(int j  0; j  n; j) {if(grid[i][j]  1) {// 题目限制只有一个岛屿,计算一个岛屿即可,即找到一个岛屿后立刻返回即可return dfs(i, j, m, n, grid, visited);}}}return 0;}public int dfs(int i, int j, int m, int n, int grid[][], boolean visited[][]) {// 从一个岛屿方格走向网格边界周长加 1if(i  0 || i  m || j  0 || j  n) {return 1;}// 从一个岛屿方格走向水域方格周长加 1if(grid[i][j]  0) {return 1;}if(visited[i][j]) {return 0;}//标记访问visited[i][j]  true;return dfs(i  1, j, m, n, grid, visited)  dfs(i - 1, j, m, n, grid, visited)  dfs(i, j  1, m, n, grid, visited)  dfs(i, j - 1, m, n, grid, visited);}}

from csdn blog

数学方法

class Solution {public int islandPerimeter(int[][] grid) {if(gridnull || grid.length0) return 0;int mgrid.length;int ngrid[0].length;int res0;for(int i0;im;i){for(int j0;jn;j){if(grid[i][j]1){//规定下方有1右方有1都-2res4;if(im-1  grid[i1][j]1){res-2;}if(jn-1  grid[i][j1]1){res-2;}}}}return res;}}

695. Max Area of Island

class Solution {static int[][] dirs{{0,1},{0,-1},{1,0},{-1,0}};public int maxAreaOfIsland(int[][] grid) {if(gridnull || grid.length0) return 0;int mgrid.length;int ngrid[0].length;int res0;for(int i0;im;i){for(int j0;jn;j){//  if(grid[i][j]1){resMath.max(res,dfs(i,j,grid));// }}}return res;}public int dfs(int i, int j, int[][] grid) {//base caseif(i0 || igrid.length ||j0 || jgrid[0].length || grid[i][j]!1){return 0;}//recursion ruleint count1;grid[i][j]0;for(int[] dir:dirs){countdfs(idir[0],jdir[1],grid);}return count;}}
在这里插入代码片
在这里插入代码片


四。剪枝(算法优化)

在DFS 和 BFS 搜索算法中剪枝策略就是寻找过滤条件提前减少不必要的搜索路径。
from csnd blog

例题1N个城市编号1到N。城市间有R条单向道路。每条道路连接两个城市有长度和过路费两个属性。Bob只有K块钱他想从城市1走到城市N。问最短共需要走多长的路。如果到不了N输出-1

2N100
0K10000
1R10000
每条路的长度 L, 1 L 100
每条路的过路费T , 0 T 100
from csnd blog
思路从城市 1开始深度优先遍历整个图找到所有能过到达 N 的走法选一个最优的。

如何剪枝
1.最优化剪枝如果当前已经找到的最优路径长度为L ,那么在继续搜索的过程中总长度已经大于等于L的走法就可以直接放弃不用走到底了
2.可行性剪枝如果当前到达城市的路费已大于k或者等于k且没有到达终点就可以直接放弃。

例题2maze题中base case的判断可以视为提前剪枝。

 public static void searchInMaze(int x, int y, int[][] maze) {int mmaze.length;int nmaze[0].length;//base cases: out of bound, 1,  //cut the branches,if(x0 || y0) return;if (x  m - 1 || y  n - 1) return;if(maze[x][y]1) return;//the destination : m-1,n-1

526. Beautiful Arrangement
提前剪枝每层符合条件才加入
keep checking the elements while being added to the permutation array at every step for the divisibility condition and can stop creating it any further as soon as we find out the element just added to the permutation violates the divisiblity condition.

 class Solution {int res0;public int countArrangement(int n) {int[] arraynew int[n];for(int i1;in;i){array[i-1]i;}dfs(array,0);return res;}public void dfs(int[] array,int index){//base caseif(indexarray.length){res;//return;不加return速度更快}//recur rule  restrictionfor(int iindex;iarray.length;i){swap(array,index,i);if(array[index]%(index1)0 || (index1)%array[index]0){//每层index当前层符合条件就加入dfs(array,index1);}swap(array,index,i);}}public void swap(int[] nums, int x, int y) {int temp  nums[x];nums[x]  nums[y];nums[y]  temp;}}

常常碰到这样的问题由第一个得到的结果再放入同样的公式中得到第二个结果同理得到第三个结果…
这就是recursion的厉害之处利用同样的逻辑一直往下走俄罗斯套娃一样解题。
797. All Paths From Source to Target
这题要得到所有的路径那么肯定是DFS套路。
每次触底反弹则添加一条路径到答案集里。

class Solution {public ListListInteger allPathsSourceTarget(int[][] graph) {ListListInteger resnew ArrayList();ListInteger oneresnew ArrayList();oneres.add(0);dfs(graph,res,oneres,0);return res;}void dfs(int[][] graph,ListListInteger res,ListInteger oneres,int curnode){//base case//curNode  nextNodeif(curnodegraph.length-1){//bugres.add(new ArrayList(oneres));return;}//recursion rulefor(int next:graph[curnode]){//关系在这里拿到curnode然后graph[curnode]才能得到nextNode//这里有个recursion一直往下走oneres.add(next);//如何继续调用下一个答利用nextnode接下去dfs(graph,res,oneres,next);//bug:这里不是index1而是下一个nextnode接下去oneres.remove(oneres.size()-1);}}}

这面这题中大神的解法真是太妙了。
1.对称观察发现1379是对称的2468对称的5单独为一个情况。
2.skipdp的想法设置skip数组。解决了大难题。
skip[i][j]表示从i数到j数之间skip了谁。那么skip[i][j]0则表示i、j两个数相邻。

skip[1][3] skip[3][1] 2;

3.remain如果从1出发那么如果m为2表示有两个数构成密码那么remain为1步即站在1可以任意走一步。
所以主函数中remain为i-1

rst DFS(vis, skip, 1, i - 1) * 4;

351. Android Unlock Patterns

public class Solution {public int numberOfPatterns(int m, int n) {// Skip array represents number to skip between two pairsint skip[][]  new int[10][10];skip[1][3]  skip[3][1]  2;skip[1][7]  skip[7][1]  4;skip[3][9]  skip[9][3]  6;skip[7][9]  skip[9][7]  8;skip[1][9]  skip[9][1]  skip[2][8]  skip[8][2]  skip[3][7]  skip[7][3]  skip[4][6]  skip[6][4]  5;boolean vis[]  new boolean[10];int rst  0;// DFS search each length from m to nfor(int i  m; i  n; i) {rst  DFS(vis, skip, 1, i - 1) * 4;// 1, 3, 7, 9 are symmetricrst  DFS(vis, skip, 2, i - 1) * 4;// 2, 4, 6, 8 are symmetricrst  DFS(vis, skip, 5, i - 1);// 5}return rst;}// cur: the current position// remain: the steps remainingint DFS(boolean vis[], int[][] skip, int cur, int remain) {if(remain  0) return 0;if(remain  0) return 1;vis[cur]  true;int rst  0;for(int i  1; i  9; i) {// If vis[i] is not visited and (two numbers are adjacent or skip number is already visited)if(!vis[i]  (skip[cur][i]  0 || (vis[skip[cur][i]]))) {rst  DFS(vis, skip, i, remain - 1);}}vis[cur]  false;return rst;}}

980. Unique Paths III
Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
1 represents the starting square. There is exactly one starting square.
2 represents the ending square. There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents obstacles that we cannot walk over.
Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.
即每个非-1的格子都必须走过。

//1.看到1就可以作为入口开始走了默认也是只有一个1;  拿到坐标后记住startx,starty//2.向四个方向延伸a.在范围内有效 b. grid[x][y]0就算有效行走格子;//3.走过改成一个-4这样就算走过了不重复。//4.每次结束后dfsnextxnexty往下走一层//5.DFS扎到底碰到#最后一个是2#的时候就返回并且count//6.#back tracking# 在合适的格子里将0/2改成-4的过程中不断查看2是不是出口/最后一个。否的话把原来的数字还给那个格子。
//recursion ruleint tempgrid[x][y];dfs();grid[x][y]temp;
class Solution {//  1// /| | // 0 0 0 0///|//000//|//2static final int[][] dirs{{1,0},{-1,0},{0,-1},{0,1}};int m;int n;int res;public int uniquePathsIII(int[][] grid) {mgrid.length;ngrid[0].length;//dfsint validCell0;int startx0;int starty0;for(int i0;im;i){for(int j0;jn;j){if(grid[i][j]0){validCell;}if(grid[i][j]1){//visited[i][j]true;startxi;startyj;}}}res0;dfs(grid,startx,starty,validCell);return res;}public void dfs(int[][] grid,int x,int y,int validCell){//base caseif(grid[x][y]2  validCell1){res;return;}//recursion ruleint tempgrid[x][y];//bug1grid[x][y]-4;//visited 过validCell--;for(int[]dir:dirs){int nextxxdir[0];int nextyydir[1];if(nextx0 || nextxm || nexty0 || nextyn){  //跳过无效区间的continue;}if(grid[nextx][nexty]0){ //0 2都可以走continue;}dfs(grid,nextx,nexty,validCell);}grid[x][y]temp;//bug2: back tracking}}

huahua讲解996题
996. Number of Squareful Arrays

/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/996

DFS方法

class Solution {private int res;public int numSquarefulPerms(int[] A) {if(A.length  1) return 0;Arrays.sort(A);dfs(A, new ArrayListInteger(), new boolean[A.length]);return this.res;}private void dfs(int[] A, ListInteger temp, boolean[] visited){if(temp.size()  A.length){if(square(temp.get(temp.size() - 1)  temp.get(temp.size() - 2))) this.res;}else if(temp.size()  1 || square(temp.get(temp.size() - 1)  temp.get(temp.size() - 2))){for(int i  0; i  A.length; i){if(visited[i]) continue;if(i  0  A[i]  A[i - 1]  !visited[i - 1]) continue;temp.add(A[i]);visited[i]  true;dfs(A, temp, visited);visited[i]  false;temp.remove(temp.size() - 1);}}}private boolean square(int x){return x  (int)Math.sqrt(x) * (int)Math.sqrt(x);}}

Graph的方法

class Solution {MapInteger, Integer count;MapInteger, ListInteger graph;public int numSquarefulPerms(int[] A) {int N  A.length;count  new HashMap();graph  new HashMap();// count.get(v) : number of vs in Afor (int x: A)count.put(x, count.getOrDefault(x, 0)  1);// graph.get(v) : values w in A for which v  w is a square//(ie., vw is an edge)for (int x: count.keySet())graph.put(x, new ArrayList());for (int x: count.keySet())for (int y: count.keySet()) {int r  (int) (Math.sqrt(x  y)  0.5);if (r * r  x  y)graph.get(x).add(y);}// Add the number of paths that start at x, for all possible xint ans  0;for (int x: count.keySet())ans  dfs(x, N - 1);return ans;}public int dfs(int x, int todo) {count.put(x, count.get(x) - 1);int ans  1;  // default if todo  0if (todo ! 0) {ans  0;for (int y: graph.get(x)) if (count.get(y) ! 0) {ans  dfs(y, todo - 1);}}count.put(x, count.get(x)  1);return ans;}}


五。套路

void dfs(int 当前状态){//base case if(当前状态为边界状态) {记录或输出return;}//recursion rulefor(i0;in;i) {//横向遍历解答树所有子节点//扩展出一个子状态。修改了全局变量if(子状态满足约束条件){dfs(子状态)}恢复全局变量//回溯部分}}