刷题常用的代码段

刷题常用的代码段

1. 二分法

int left = 0, right = nums.length - 1;
while(left <= right) {
	int mid = left + (right - left) / 2;
	if(nums[mid] == target) return mid;
	else if(nums[mid] > target) right = mid - 1;
	else left = mid + 1;

2.计算位数

while(num != 0){
	cou++;
	num /= 10;
}

3.一些函数用法

//返回s的第0 - n的字符串（不包括n）
str.substring(0,n);
//将栈的值从栈底依次取出 sb为StringBuilder
for(char c : stack){
	sb.append(c);
}
//切断链表 将pre.next-rightnode从链表中截取

4.计算二进制的1

//只考虑x > 0
public int countOnes(int x) {
	int ones = 0;
	while(x > 0){
		x &= (x - 1);
		ones++;
	}
	return ones;
}
//考虑有负数的情况
public int countOnes(int x) {
	int ones = 0;
	int flag = 1;
	while(flag != 0) {
		if((flag & n) != 0) ones++;
		flag = flag << 1;
	}
	return ones;
}

5.反转链表

//反转全部
public ListNode reverse(ListNode head){
	ListNode pre =null;
	while(head != null){
		ListNode next = head.next;
		head.next = pre;
		pre = head;
		head = next;
	}
	return pre;
}
//反转部分
public void reverse(ListNode head, ListNode tail) {
	ListNode p1 = head, p2 = head.next, p = head, last = tail.next;
     while (p2 != last && p2 != null) {
	 	p1.next = p2.next;
		p2.next = p;
		p = p2;
		p2 = p1.next;
     }
}

6.BFS & DFS

#1. BFS

public List<List<Integer>> levelOrder(TreeNode root) {
    //边界条件判断
    if (root == null)
        return new ArrayList<>();
    //队列
    Queue<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();
    //根节点入队
    queue.add(root);
    //如果队列不为空就继续循环
    while (!queue.isEmpty()) {
        //BFS打印，levelNum表示的是每层的结点数
        int levelNum = queue.size();
        //subList存储的是每层的结点值
        List<Integer> subList = new ArrayList<>();
        for (int i = 0; i < levelNum; i++) {
            //出队
            TreeNode node = queue.poll();
            subList.add(node.val);
            //左右子节点如果不为空就加入到队列中
            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
        //把每层的结点值存储在res中，
        res.add(subList);
    }
	return res;
}

#2.DFS

//访问内当前节点 递归地访问右子树、左子树；
class Solution {
	List<Integer> res = new ArrayList<>();
	public List<Integer> rightSideView(TreeNode root) {
		dfs(root, 0);
		return res;
	}
	public void dfs(TreeNode root, int depth){
		if(root == null) return;
		if(depth == res.size()) res.add(root.val);
		depth++;
		dfs(root.right, depth);
		dfs(root.left, depth);
	}
}

public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        //stack记录的是节点，而level中的元素和stack中的元素
        //是同时入栈同时出栈，并且level记录的是节点在第几层
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> level = new Stack<>();
        stack.push(root);
        level.push(1);
        int max = 0;
        while (!stack.isEmpty()) {
            //stack中的元素和level中的元素同时出栈
            TreeNode node = stack.pop();
            int temp = level.pop();
            max = Math.max(temp, max);
            if (node.left != null) {
                //同时入栈
                stack.push(node.left);
                level.push(temp + 1);
            }
            if (node.right != null) {
                //同时入栈
                stack.push(node.right);
                level.push(temp + 1);
            }
        }
        return max;
    }

7.最大公约数

public int max(int a, int b){
	int result = a % b;
	while(result != 0){
		a = b;
		b = result;
		result = a % b;
	}
	return b;
}

8.二位数组排序 & map排序

//二位数组排序
Arrays.sort(nums,new Comparator<int[]>(){
	public int compare(int[] a,int[] b){
		//若a[0] b[0]值相同则比较a[1] b[1]，按升序
		if(a[1]==b[1]){                   
			return a[0]-b[0];
        }else{
			return a[1]-b[1];
        }
    }
});

//map 排序
ArrayList<Map.Entry<String,Integer>> list = new ArrayList<>(map.entrySet());
Collections.sort(list, 
	(o1, o2) -> (o1,getValue().compareTo(o2.getValue())==0 ? o1,getKey().compareTo(o2.getKey()) :
	 o1,getValue().compareTo(o2.getValue()))
);

9.丑数

//是否为丑数
public boolean isUgly(int n) {
        if ( n <= 0 ) return false;
        while(n % 2 == 0) n /= 2;
        while(n % 3 == 0) n /= 3;
        while(n % 5 == 0) n /= 5;        
        return n == 1;
}
//返回第n个丑数 动态规划
 public int nthUglyNumber(int n) {
        if(n <= 6) return n;
        int i2 = 0, i3 = 0, i5 = 0;
        int [] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++) {
             int next2 = dp[i2] * 2;
             int next3 = dp[i3] * 3;
             int next5 = dp[i5] * 5;
             dp[i] = Math.min(next2, Math.min(next3, next5));
             if(dp[i] == next2) i2++;
             if(dp[i] == next3) i3++;
             if(dp[i] == next5) i5++;
        }
        return dp[n-1];    
}

10.返回最长回文子串

 public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        
        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
}

11.最长公共子串 && 子序列

//返回子串
    public String LCS (String str1, String str2) {
        // write code here
         String result = "";
        int start = 0;
        int end = 1;
        while(end<=str2.length()){
            String subStr = str2.substring(start,end);
            if(str1.contains(subStr)){
                result = subStr;
            }else{
                start++;
            }
            end++;
        }
        return result;
    }
//返回序列
	public String LCS (String s1, String s2) {
        // write code here
        String str = new Solution().process(s1,s2);
        return "".equals(str)?"-1":str;
    }
     public static String process(String str1, String str2) {
        if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0) {
            return "";
        }
        char[] char1 = str1.toCharArray();
        char[] char2 = str2.toCharArray();
        int[][] dp = dp(char1, char2);
        int m = str1.length() - 1;
        int n = str2.length() - 1;
        char[] res = new char[dp[m][n]];
        int index = res.length - 1;

        while (index >= 0) {
            if (n > 0 && dp[m][n] == dp[m][n - 1]) {
                n--;
            } else if (m > 0 && dp[m][n] == dp[m - 1][n]) {
                m--;
            } else {
                res[index--] = char1[m];
                m--;
                n--;
            }
        }

        return String.valueOf(res);
    }

    public static int[][] dp(char[] str1, char[] str2) {
        int[][] dp = new int[str1.length][str2.length];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;

        for (int i = 1; i < str1.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], str1[i] == str2[0] ? 1 : 0);
        }
        for (int i = 1; i < str2.length; i++) {
            dp[0][i] = Math.max(dp[0][i - 1], str2[i] == str1[0] ? 1 : 0);
        }
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                int max = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (str1[i] == str2[j]) {
                    max = Math.max(dp[i - 1][j - 1] + 1, max);
                }
                dp[i][j] = max;
            }
        }
        return dp;
    }