算法思想

这道题我已经在 面经上 见到好多次了，所以一定要弄懂;

双指针算法：声明两个指针，i指针循环s字符串，j指针用于去除重复元素，一有重复元素就进行跳转

java 代码

class Solution {
    public int longestSubstringWithoutDuplication(String s) {
        Map<Character, Integer> map = new HashMap<>();   // 记录 字符索引的位置
        int res = 0;
        for(int i = 0, j = 0; i < s.length(); i ++)
        {
            if(map.containsKey(s.charAt(i)))            // 说明出现了重复的
                j = Math.max(j, map.get(s.charAt(i)) + 1);
            map.put(s.charAt(i), i);
            res = Math.max(res, i - j + 1);
        }
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();

        while(root != null || stk.size() != 0)
        {
            while(root != null)
            {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
}

class LRUCache {
    static Map<Integer, Node> map = new HashMap<>();
    static Node head, tail;
    static int n;

    public LRUCache(int capacity) {
        n = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.right = tail;
        tail.left = head;
        map.clear();
    }

    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        Node p = map.get(key);
        remove(p);
        insert(p);
        return p.val;
    }

    public void put(int key, int value) {
        if(map.containsKey(key))       //更新操作
        {
            Node p = map.get(key);
            p.val = value;
            remove(p);
            insert(p);
        }
        else
        {
            if(map.size() == n)      //超出容量
            {
                Node p = tail.left;
                remove(p);
                map.remove(p.key);
            }
                Node p = new Node(key, value);
                insert(p);
                map.put(key, p);
        }
    }

    private static void remove(Node p)
    {
        p.right.left = p.left;
        p.left.right = p.right;
    }

    private static void insert(Node p)
    {
        p.right = head.right;
        p.left = head;
        head.right.left = p;
        head.right = p;
    }
}

class Node
{
    int key, val;
    Node left, right;
    Node (int key, int val)
    {
        this.key = key;
        this.val = val;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int res = quick_sort(nums, 0, nums.length - 1, k - 1);
        return res;
    }

    private static int quick_sort(int[] nums, int l, int r, int k)
    {
        if(l >= r) return nums[r];
        int mid = nums[l + r >> 1];
        int i = l - 1, j = r + 1;
        while(i < j)
        {
            do i ++; while(nums[i] > mid);
            do j --; while(nums[j] < mid);
            if(i < j)
            {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        if(k <= j) return quick_sort(nums, l, j, k);
        else return quick_sort(nums, j + 1, r, k);
    }
}

class Solution {
    public void setZeroes(int[][] matrix) {

        int n = matrix.length, m = matrix[0].length;      //n行m列
        int r0 = 1, c0 = 1;
        for(int i = 0; i < m; i ++)          //循环第0行
            if(matrix[0][i] == 0) 
                r0 = 0;
        for(int i = 0; i < n; i ++)          //循环第0列
            if(matrix[i][0] == 0)
                c0 = 0;

        for(int i = 1; i < n; i ++)          //对于每一行循环每一列
            for(int j = 0; j < m; j ++)
                if(matrix[i][j] == 0)
                    matrix[i][0] = 0;
        for(int i = 1; i < m; i ++)          //对于每一列循环每一行
            for(int j = 0; j < n; j ++)
                if(matrix[j][i] == 0)
                    matrix[0][i] = 0;
        for(int i = 1; i < n; i ++)
            if(matrix[i][0] == 0)
                for(int j = 0; j < m; j ++)
                    matrix[i][j] = 0;
        for(int i = 1; i < m; i ++)
            if(matrix[0][i] == 0)
                for(int j = 0; j < n; j ++)
                    matrix[j][i] = 0;
        if(r0 == 0)
        {
            for(int i = 0; i < m; i ++) matrix[0][i] = 0;
        }
        if(c0 == 0)
        {
            for(int i = 0; i < n; i ++) matrix[i][0] = 0;
        }

    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;                   //如果不声明指针的话，dummy.next就到最后了
        while(l1 != null && l2 != null)
        {
            if(l1.val <= l2.val)
            {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            }
            else
            {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }

        if(l1 != null) cur.next = l1;
        else if(l2 != null) cur.next = l2;

        return dummy.next;
    }
}

import java.util.Scanner;

public class Main{
    static int N = 110;

    public static void main(String[] args){

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int m = in.nextInt();

        int[][] a = new int[N][N];
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
                a[i][j] = in.nextInt();

        for(int i = 0; i < m; i ++)
        {
            for(int j = n - 1; j >= 0; j --)
                System.out.print(a[j][i] + " ");
            System.out.println();
        }
    }
}

算法详解

通常看到题目写不能使用加减乘除....一些限制信息，就可以想到使用位运算或者递归来做

1：两个数做^运算，得到各位相加不进位的计算结果

2：两个数做&运算，得到进位，(因为&是11得1，只有两位都是1时，才会进位)，因为进位是要加到左一位的，所以需要左移1

3：因为可能有些位数加上进位后还要进位，所以要迭代直到进位为0
比如111和001，第一位11所以要进一位，第二位1 + 0 + 1也需要进位，第三位也是如此，最后为1000

知识点

两个二进制数相加规则
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10 //进位余0
二进制数相加的个位之和为：a ^ b; //所以异或运算可以用于计算两个二进制数之和
进位为：(a & b) << 1;

二进制减法运算
1 - 0 = 1
1 - 1 = 0
0 - 0 = 0
0 - 1 = 1 //借2余1

java代码

class Solution {
    public int add(int num1, int num2) {
        while(num2 != 0)
        {
            int sum = num1 ^ num2;                
            int carry = (num1 & num2) << 1;       
            num1 = sum;
            num2 = carry;
        }
        return num1;
    }
}

class Solution {
    public int add(int num1, int num2) {
        while(num2 != 0)
        {
            int sum = num1 ^ num2;                //两数相加不进位的计算结果
            int carry = (num1 & num2) << 1;       //进位
            num1 = sum;
            num2 = carry;
        }
        return num1;
    }
}

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        for(int i = 0; i < 32; i ++)
        {
            if((n >> i & 1) == 1) res ++;
        }
        return res;
    }
}