RSS
SITEMAP
Articles
-
二叉树根节点到叶子节点和为指定值的路径集问题
分析 寻找满足指定值的路径集转换为二叉树的前序遍历（根-左-右） 使用回朔（递归）的方式实现 /** * * @param root TreeNode类 * @param sum int整型 * @return int整型ArrayList<ArrayList<>> */ ArrayList<ArrayList<Integer>> res = new ArrayList<>(); ArrayList<Integer> list = new ArrayList<Integer>(); public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) { if(root == null)return res; dsf(root,sum,0); return res; } public void dsf(TreeNode root, int sum,int count){ //设置递归终止条件 if(root == null)return ; list.add(root.val); count += root.val; if(root.left == null && root.right == null){ if(count == sum)res. -
矩阵的最小路路径
求解最值问题利用动态规划算法解决 题目描述：给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。 示例1： 输入：[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]] 返回值：12 备注：1≤n,m≤2000 思路分析： 求最值问题首先就是构建辅助数组dp 路径的走向只能是向右或者是向下，则可以将没有元素的对于的和求解出来构建一个新的二维表 二维表中国填写当前值与前一次值之和，取左下右上的两值的最小值与当前值求和填充表格 /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { if(matrix==null)return 0; //构建列 int row = matrix.length; int column = matrix[0].length; //构建列的值 for(int i = 1;i<row;i++)matrix[i][0] = matrix[i-1][0]+matrix[i][0]; //构建行的值 for(int j = 1;j<column;j++)matrix[0][j] = matrix[0][j-1] + matrix[0][j]; //填充中间数据 for(int i = 1;i<row;i++){ for(int j=1;j<column;j++) matrix[i][j] = Math. -
二叉树的之字型层次遍历
题目描述： 解题思路 设置一个标志位flag，当flag为true时，执行从左到右的遍历，反之则为从右到左 将数放入到队列中，判断队列是否为空，作为树遍历的结束条件 代码如下 /** * * @param root TreeNode类 * @return int整型ArrayList<ArrayList<>> */ public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) { // write code here ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if(root==null)return res; // 设置一个标志位 Boolean flag = true; Queue<TreeNode> que = new LinkedList<>(); que.offer(root); while(!que.isEmpty()){ int size = que.size(); ArrayList<Integer> list = new ArrayList<>(); for(int i = 0; i< size; i++){ TreeNode node = que. -
二进制中1的个数
题解 1.暴力方法 分析：题目给一个有符号的整数int，求整数转化成二进制数后，1的个数。 直接根据题目的描述来提出方法一。有2个问题： 问题1: 如何从十进制数转化到二进制数？ 问题2:转化为二进制数后，如果判断有1的个数？ 1.1 除2取模法。 int val; // input data int ans = 0; while (val != 0) { int tmp = val % 2; if (tmp == 1) ++ans; val /= 2; } 当然这种方法，对于大部分数据是对的，但是对于-2147483648,二进制为1000…000，一共有31个0.因为计算机使用补码存储二进制数据的。对于这个数据，我们的方***输出0，实际上为1.所以这种方法不对。 1.2 二进制移位法 直接将整数看成二进制，然后采用移位的方法。 int val; // input data int ans = 0; while (val != 0) { if (val & 1) ++ans; val >>= 1; } 代码中val & 1表示val 与 0x000…0001（其中有31个0）进行 & 操作。 val >>= 1表示，如果val的二进制是110，则操作之后会变成011,也就是舍去最低位，然后最高位补0. -
字符串变形
1. 解决此题的关键是如何将大小写字符转换 1.1 判断 字符是a-z 或者 A-Z是关键 每一个字符都有一个对应的ASII码，因此可以利用这一点来做 1.2 大小写转换 将字符串从小写转换为大写可以如下表达： ch[j] = (char)(ch[j]-‘a’+‘A’); 将字符串从大写转换为小写可以如下表达： ch[j] = (char)(ch[j] -‘A’+‘a’); 题目描述如下 public String trans(String s, int n) { // write code here String[] str = s.split(" ",-1); StringBuilder res = new StringBuilder(); for(int i = str.length-1;i>=0;i--){ String tmp = str[i]; char[] ch = tmp.toCharArray(); for(int j = 0;j<ch.length;j++){ if(ch[j]>='a' && ch[j]<='z') ch[j] = (char)(ch[j]-'a'+'A'); else if(ch[j] >= 'A' && ch[j]<='Z') ch[j] = (char)(ch[j] -'A'+'a'); } res.
