public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); String s=input.nextLine(); //一定要用nextLine() 因为字符串有空格!!!!!! System.out.println(replaceSpace(s)); //调用方法返回结果 }
public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); int n=input.nextInt(); System.out.println("递归:"+fib(n)); System.out.println("动态规划:"+fiber(n)); }
public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); int n=input.nextInt(); /*for (int i = 0; i < n; i++) { a[i]=input.nextInt(); }*/ System.out.println("递归:"+numWays(n)); System.out.println("动态规划:"+numWayser(n)); }
public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); int n=input.nextInt(); int[] a=new int[n]; for (int i = 0; i < n; i++) { a[i]=input.nextInt(); } System.out.println(minArray(a)); }
//排序输出 public static int minArray(int[] numbers) { Arrays.sort(numbers); //排序 return numbers[0]; //输出最小的第一位 }
//二分法 public static int minArray(int[] numbers) { int i=0; //左指针 int j=numbers.length-1; //右指针 while(i<j){ int z=(i+j)/2; //找中间位置 if(numbers[z]>numbers[j]){ i=z+1; //min值在右边出现 }else if(numbers[z]<numbers[j]){ j=z; //min值在左边出现 }else { j--; //无法确定范围 缩小范围继续找 } } return numbers[i]; }
//board是要找的路径集合 words字符串转的字符数组 i和j是board下标 k是找到了几个 private static boolean dfs(char[][] board, char[] words, int i, int j, int k) { if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[k]){ return false; // i和j越界 / 找不到符合 } if(k == words.length - 1) { //已经全部找到了!!! return true; } char temp=board[i][j]; //中间值 board[i][j]='/'; //用过之后改成 ‘/’ //上下左右都找找 boolean res=dfs(board, words, i + 1, j, k + 1) || dfs(board, words, i - 1, j, k + 1) || dfs(board, words, i, j + 1, k + 1) || dfs(board, words, i , j - 1, k + 1); board[i][j]=temp; //用完之后再回溯返回原值 return res; }
}
结果
机器人的运动范围
题目
分析
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); int m=input.nextInt(); int n=input.nextInt(); int k=input.nextInt(); System.out.println(movingCount(m,n,k)); }
public static int movingCount(int m, int n, int k) { int res=123; return res; }
public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); int m=input.nextInt(); System.out.println(cuttingRope(m)); }
public static int cuttingRope(int n) { if(n<=3){ return n-1; } int a=n/3; int b=n%3; if(b==0){ return (int)Math.pow(3,a); } if(b==1){ return (int)Math.pow(3,a-1)*4; } return (int)Math.pow(3,a)*2; }
public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); int m=input.nextInt(); System.out.println(cuttingRope(m)); }
public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); int m=input.nextInt(); System.out.println(hammingWeight(m)); }
public static int hammingWeight(int n) { int res=0; //接最后结果 while(n!=0){ res++; n=n&(n-1); //消除数字n最右边的1 } return res; }
public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); String s=input.next(); System.out.println(isNumber(s)); }
public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); int n=input.nextInt(); int[] a=new int[n]; for (int i = 0; i < a.length; i++) { a[i]=input.nextInt(); } System.out.println(Arrays.toString(exchange(a))); }
public static int[] exchange(int[] nums) { int i=0; //左指针 int j=nums.length-1; //右指针 int temp=0; //临时交换用 while(i<j) { while (i < j && ((nums[i] % 2) != 0)) { i++; //奇数往后移动 } while (i < j && ((nums[j] % 2) == 0)) { j--; //偶数往前移动 } //左边是偶数 右边是奇数的话就交换 temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } return nums; }
public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); int[][] a=new int[][]{{1,2,3},{4,5,6},{7,8,9}}; System.out.println(Arrays.toString(spiralOrder(a))); }
public static int[] spiralOrder(int [][] matrix) { if(matrix.length == 0) { return new int[0]; //数组空就弹出空数组 } int row=matrix.length; //行 int col=matrix[0].length; //列 int left=0; //二维数组上面行的最左边 int right=col-1; //二维数组上面行的最右边 int top=0; //二维数组左边的最上边 int bottom=row-1; //二维数组左边的最下边 int[] a=new int[row*col]; int q=0; //控制结果数组下标 while(left<=right&&top<=bottom){ //从左到右 for(int i=left;i<=right;i++){ a[q++]=matrix[top][i]; //top行 } //从上到下(从下一行开始向下走) for(int i=top+1;i<=bottom;i++){ a[q++]=matrix[i][right]; //right列 } //从右到左(从左边一列开始向左走) if(top!=bottom) { //如果是一行的话就不需要返回去(已经左到右) for (int i=right-1;i>=left;i--) { a[q++]=matrix[bottom][i]; //bottom行 } } //从下到上(从上一行开始向上走) if(left!=right) { //如果是一列的话就不需要返回去(已经上到下) for (int i=bottom-1;i>top;i--) { a[q++]=matrix[i][left]; //left列 } } //下一个正方形矩阵(往里缩小 -- 变换四个下标) top++; right--; left++; bottom--; } return a; //返回a数组 }
class MinStack { Stack<Integer> A, B; public MinStack() { A = new Stack<>(); B = new Stack<>(); } public void push(int x) { A.add(x); if(B.empty() || B.peek() >= x) B.add(x); } public void pop() { if(A.pop().equals(B.peek())) B.pop(); } public int top() { return A.peek(); } public int min() { return B.peek(); } }
public class ErChaShu { public static void main(String[] args) { Scanner input=new Scanner(System.in); int n=input.nextInt(); int[] a=new int[n]; for (int i = 0; i < n; i++) { a[i]=input.nextInt(); } System.out.println(verifyPostorder(a)); }
public static boolean verifyPostorder(int[] postorder) { return recur(postorder, 0, postorder.length - 1); // 调用方法( 数组postorder i j ) }
public static boolean recur(int[] postorder, int i, int j) { if(i >= j){ return true; //子树节点<=1 肯定true } //找左子树 int chang = i; while(postorder[chang] < postorder[j]){ //左边肯定比根节点小(第一个大的数字就是右节点的开始位置) chang++; } //找右子树 int zhong = chang; //找到第一个 > postorder[j]的值就是右子树的开始位置 while(postorder[chang] > postorder[j]) { //右边肯定都比根节点大 chang++; }
//1. 按位拆除判断(超时) public static int countDigitOne(int n) { int res=1; if(n==0){ //0的话出现0次 res=0; } if(n==1){ //1的话出现1次 res=1; } for(int i=2;i<=n;i++){ //从2开始 res+=jige(i); } return res; } //统计1的次数 public static int jige(int i){ int sum=0; while(i!=0){ //缩小范围到0 if(i%10==1){ sum++; //出现1的时候计数器+1 } i=i/10; //不断缩小 } return sum; }
//2. 数学归纳法 public int countDigitOne(int n) { int res = 0; for (long m = 1; m <= n; m *= 10) { long a = n / m; long b = n % m; res += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0); } return res; }
结果
数字序列中某一位的数字(数学归纳)
题目
分析
1. 第一个while用来判断多少个
2. 用char数组存放结果,然后不断地取出到哪一位
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
public static int findNthDigit(int n) { int res=0; if(n<10){ return n; //前10位是按照顺序0123456789 } int i=1; while(n>i*(Math.pow(10,i-1)*9)){ // 9(10个) 99(90个) 999(900个) n-=i*Math.pow(10,i-1)*9; i++; } char[] result=String.valueOf((int)Math.pow(10,i-1)+(n-1)/i).toCharArray();//我们用字符串来接收值，方便找位数 result结果为我们要的那个数的 int value=result[(n-1)%i]-'0'; //(n-1)%位数 得出我们要的第x位的数 return value; }
class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int ans = 0; Map<Character, Integer> map = new HashMap<>();//key出现的字符，value对应的最新的位置 // try to extend the range [i, j] int start=0; for (int end = 0; end < n; end++) { if (map.containsKey(s.charAt(end))) { start = Math.max(map.get(s.charAt(end)) + 1, start);//由于重复的坐标不知道在start的前方还是后方，所以要取个最大值 } ans = Math.max(ans, end - start + 1); //更新最大长度 map.put(s.charAt(end), end); //存放的字符对应位置更新 } return ans; } }
public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); int n=input.nextInt(); System.out.println(nthUglyNumber(n)); //调用方法 }
public static int nthUglyNumber(int n) { int p2=0; //只乘2 int p3=0; //只乘3 int p5=0; //只乘5 int[] dp=new int[n]; //存放所有的丑数 dp[0]=1; //第一个丑数是1 for(int i=1;i<n;i++){ dp[i]=Math.min(dp[p2]*2,Math.min(dp[p3]*3,dp[p5]*5)); //从第二位开始求当前位置丑数 //看是哪个指针走了就跳后面 if(dp[i]==dp[p2]*2){ p2++; } if(dp[i]==dp[p3]*3){ p3++; } if(dp[i]==dp[p5]*5){ p5++; } } return dp[n-1]; //最后返回n-1结果 } }
public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); String s=input.next(); System.out.println(firstUniqChar(s)); }
public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int[] a = new int[]{10,26,30,31,47,60}; int target=input.nextInt(); System.out.println(Arrays.toString(twoSum(a,target))); }
public static int[] twoSum(int[] nums, int target) { int i = 0, j = nums.length - 1; //定义两个指针 while(i < j) { int s = nums[i] + nums[j]; //求和 if(s < target){ i++; //太小了往后挪 } else if(s > target){ j--; //太大了往前挪 } else return new int[]{nums[i], nums[j]}; //找到了就返回这两个值 } return new int[0]; //默认返回空 }
public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int target=input.nextInt(); System.out.println(findContinuousSequence(target)); }
public static int[][] findContinuousSequence(int target) { int i = 1; // 滑动窗口的左边界 int j = 1; // 滑动窗口的右边界 int sum = 0; // 滑动窗口中数字的和 //res集合接收结果 List<int[]> res = new ArrayList<>(); while(i<=target/2){ //只能到一半的位置 if(sum<target){ sum+=j; //太小了 往右移动找新的 j++; }else if(sum>target){ sum-=i; //太大了 往右移动把最左边的删除 i++; }else{ //找到了结果集 int[] arr=new int[j-i]; //长度是j-i for(int k=i;k<j;k++){ arr[k-i]=k; //要把i和j开始遍历放入数组 } //将每一个结果数组放入res集合 res.add(arr); //左边界限向右移动(找到了i就要往后挪动) sum-=i; //sum要减去i i++; } } return res.toArray(new int[res.size()][]); //集合转数组 }
public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); String s=input.nextLine(); //nextLine()输入格式 System.out.println(reverseWords(s)); }
public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); String s=input.next(); int n=input.nextInt(); System.out.println(reverseLeftWords(s,n)); }
Queue<Integer> queue; LinkedList<Integer> max; public MaxQueue() { queue = new LinkedList<>(); max = new LinkedList<>();//LinkedList是双端链表 } public int max_value() { return max.size()==0?-1:max.getFirst(); } public void push_back(int value) { queue.add(value); while(max.size()!=0&&max.getLast()<value){//注意：这里第二个判断条件不能带等号，即max中对于当前queue中的具有相同值的元素会全部存储，而不是存储最近的那个。 max.removeLast(); } max.add(value); } public int pop_front() { if(max.size()!=0&&queue.peek().equals(max.getFirst()))//Integer类型的值的比较不能直接使用== max.removeFirst(); return queue.size()==0?-1:queue.poll(); } }
public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n=input.nextInt(); int m=input.nextInt(); System.out.println(lastRemaining(n,m)); }
public static int lastRemaining(int n, int m) { //新建list集合 ArrayList<Integer> list = new ArrayList<>(); //将所有元素都加入list集合 for (int i=0;i<n;i++){ list.add(i); } //定义下标--确定每次删除的位置 int i=0; //循环删除 while(n>1){ i=(i+m-1)%n; list.remove(i); //list删除 n--; //总数减少1个 } return list.get(0); //剩下的唯一一个数字 }
public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int[] a=new int[]{7,1,5,3,6,4}; System.out.println(maxProfit(a)); }
public static int maxProfit(int[] prices) { if(prices.length==0){ return 0; //数组长为0 } int min=prices[0]; //购买的日子 int[] dp=new int[prices.length]; //存每个位置的利润 for (int i=1;i<prices.length;i++) { min=Math.min(min,prices[i-1]); //找最小值 dp[i]=Math.max(dp[i-1],prices[i]-min); //每个位置的利润 } return dp[prices.length-1]; }
}
结果
求1+2+..+n的和(归纳)
题目
分析
1. 递归
2. 迭代
3. 数学归纳法
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n=input.nextInt(); System.out.println(sumNums(n)); }
public static int sumNums(int n) { int res=0; res=((n+1)*n)/2; return res; }
public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n=input.nextInt(); int m=input.nextInt(); System.out.println(add(n,m)); }
public static int add(int a, int b) { while(b!=0){ int tempSum=a^b; //求不考虑进位的相加和 int carrySum=(a&b)<<1; //进位的和 //不断循环迭代 直到没有进位(b==0) a=tempSum; b=carrySum; } return a; }
public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int[] a=new int[]{1,2,3,4,5}; System.out.println(Arrays.toString(constructArr(a))); }
public static int[] constructArr(int[] a) { if(a.length==0){ return new int[0]; //返回0 } int[] b=new int[a.length]; b[0]=1; int temp=1; //计算左下角 for(int i=1;i<a.length;i++){ //从上到下 b[i]=b[i-1]*a[i-1]; } //计算右上角 for(int i=a.length-2;i>=0;i--){ //从下往上 temp=temp*a[i+1]; b[i]=b[i]*temp; }
public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); String s=input.next(); System.out.println(strToInt(s)); }
